MÉTODO DUAL

A cualquier problema que llamamos primal tiene mas restricciones que variables, esto simplifica la solución porque el problema se representa como un problema dual y se maneja con menos restricciones.

Esto es:

1.- si el primal se refiere a maximizar, el problema dual sera minimizar.

2.- los coeficientes de la funcion objetivo del primal seran los coeficientes del vector de disponibilidad de recursos en el dual.

3.- asi, los coeficientes del vector disponibilidsd de recursos del problema primal seran los coeficientes de la funcion objetivo (vector costos, precios o utilidad) en el programa dual.

4.- los coeficientes d e las restricciones en el primal ( transpuesta de la matriz), sera la matriz de los coeficientes tecnológicos en el dual.

5.- los signos de desigualdad del problema dual son contrarios a los del primal.

6.- las variables “x” del primal, se convierten en nuevas variables “y” en el dual.

1.- considerando el siguiente problema primario, calcular su modelo dual.

Sea máx. = Z= 3x + 5y

Ponemos los coeficientes disponibilidad en forma de vector columna ( matriz) primal

y estos se convierten en vector, horizontal o vertical ( matriz fila ) transpuesta; esto es

Hacemos las restricciones del primal en forma de matriz

Por lo tanto su transpuesta Dual Sera:

Y al maximizar:

METODO DE ASIGNACION

MÉTODO de ASIGNACIÓN:

El problema de asignación tiene que ver con la asignación de tareas a empleados, de territorios a vendedores, de contratos a postores o de trabajos a plantas. Al aplicar el método de transporte y el método de asignación la gerencia está buscando una ruta de distribución o una asignación que optimizará algún objetivo; éste puede se la minimización del costo total, la maximización de las utilidades o la minimización del tiempo total involucrado.
Al igual que el método de transporte el método de asignación es computacionalmente más eficiente que el método simplex para una clase especial de problemas. El método de asignación también conocido como la Técnica de flood o el método Húngaro de asignación. Hay básicamente tres pasos en este método
Determine la tabla de costo de oportunidad:
Reste el elemento del costo más bajo en cada columna de la tabla de costo dada, de todo los elementos en esa columna.
Reste el asiento más bajo en cada renglón de la tabla obtenida en la parte 1.1 de todos los números en ese renglón.
Determine si se puede hacer una asignación óptima: El procedimiento es dibujar líneas rectas (verticales y horizontales) a través de la tabla de costos total de oportunidad, de tal manera que se minimice el número de líneas necesarias para cubrir todos los cuadros CERO. Si el número de líneas dibujadas es menor que el número de renglones o columnas, no se puede hacer una asignación óptimas y el problema no está resuelto.
Revise la tabla de costo total de oportunidad.
Seleccione el número más pequeño en la tabla no cubierto, por una línea recta y reste este número de todos los números no cubiertos por una línea recta.
Añada este mismo número a los números que están en la intersección de dos líneas cualesquiera. Regrese al paso 2 .

METODO DE LAS DOS FASES

Método de las Dos Fases

Éste método difiere del Simplex en que primero hay que resolver un problema auxiliar que trata de minimizar la suma de las variables artificiales. Una vez resuelto este primer problema y reorganizar la tabla final, pasamos a la segunda fase, que consiste en realizar el método Simplex normal.
En esta primera fase, se realiza todo de igual manera que en el método Simplex normal, excepto la construcción de la primera tabla, la condición de parada y la preparación de la tabla que pasará a la fase 2.
- Construcción de la primera tabla: Se hace de la misma forma que la tabla inicial del método Simplex, pero con algunas diferencias. La fila de la función objetivo cambia para la primera fase, ya que cambia la función objetivo, por lo tanto aparecerán todos los términos a cero excepto aquellos que sean variables artificiales, que tendrán valor "-1" debido a que se está minimizando la suma de dichas variables (recuerde que minimizar F es igual que maximizar F·(-1)).
La otra diferencia para la primera tabla radica en la forma de calcular la fila Z. Ahora tendremos que hacer el cálculo de la siguiente forma: Se sumarán los productos Cb·Pj para todas las filas y al resultado se le restará el valor que aparezca (según la columna que se éste haciendo) en la fila de la función objetivo.

Siendo Zj = Σ(Cb·Pj) - Cj y los Cj = 0 para todo j comprendido entre 0 y n-k (variables de decisión, holgura y exceso), y Cj = -1 para todo j comprendido entre n-k y n (variables artificiales).

- Condición de parada: La condición de parada es la misma que en el método Simplex normal. La diferencia estriba en que pueden ocurrir dos casos cuando se produce la parada: la función toma un valor 0, que significa que el problema original tiene solución, o que tome un valor distinto, indicando que nuestro modelo no tiene solución.


- Eliminar Columna de variables artificiales: Si hemos llegado a la conclusión de que el problema original tiene solución, debemos preparar nuestra tabla para la segunda fase. Deberemos eliminar las columnas de las variables artificiales, modificar la fila de la función objetivo por la original, y calcular la fila Z de la misma forma que en la primera tabla de la fase 1.

Método VOGEL

Método de transporte {Método de vogel (VAM)


Es un método de ahorro que trabaja sobre el ahorro y suele producir una mejor solución óptima o próxima al nivel óptimo.

Paso 1.-Requiere de una penalización para cada renglón (columna)
Restando el menor elemento de costo del renglón

Problema:

Supongamos que a una empresa transnacional que tiene tres plantas R , S, T estas surten de producto hacia almacenes A , B , C, D, E, F, G, que forman parte del grupo empresarial debemos considerar lo relacionado al costo de transporte desde la planta a cada almacén.

FORMULA

FC
M+N-1

3+8-1=10

PRUEBA DE OPTIMIDAD

CONCLUSION

Método SIMPLEX por minimización

Minimizar Z= 3m + 4n - 8ñ

3m – 4n ≤ 12
M + 2n + ñ ≥ 4
4m – 2n +5ñ ≤ 20

M ≥ 0, n ≥ 0, ñ ≥ 0

Como es un problema de minimización recordemos que tenemos que maximizar la función objetivo quedando así

-3m – 4n + 8ñ + Z = 0

Las inecuaciones las hacemos igualdades

3m – 4n = 12
m + 2n + ñ = 4
4m – 2n +5ñ = 20

Ahora tenemos que hacer nuestra tabla 1 y aplicaremos el mismo procedimiento del método SIMPLEX para maximizarlo

Ahora de la tabla tomaremos el MAYOR POSITIVO en este caso es el 8 y ya encontramos nuestra columna pivote.

Posteriormente dividimos 28/5 = 4 4/1 = 4 12/0 = 0, y tenemos que tomar el numero menor de estas divisiones en este caso tenemos dos, cuatros podemos tomar cualquiera

Y ya encontramos nuestro pivote operacional en este caso es 1, ahora tenemos que dividir toda esa fila entre este 1 para poder resolver la siguiente tabla

Ahora la ñ ya paso a la base

El problema se termina aquí porque ya nos quedaron puros negativos y ceros en nuestra PO que era nuestro objetivo

3m – 4n ≤ 12
3(0) – 4 (0) ≤ 12
0 ≤ 12 Si cumple

m + 2n + ñ ≥ 4
0 + 2(0) + ¼ ≥ 4
¼ ≥ 4 No cumple

4m – 2n + 5ñ ≤ 20
4 (0) – 2 (0) + 5 (1/4) ≤ 20
1.25 ≤= 20 Si cumple

3m + 4n – 8ñ
Z = 3 (0) + 4(0) – 8 (1/4)
Z = 2

Metodo de la Gran M

Este método empieza con la PL en la forma estándar Para cualquier ecuación i que no tiene una holgura, aumentamos una variable artificial R. Entonces esta variable se convierte en parte de la solución básica inicial. Debido a que es una variable artificial al modelo de PL se le asigna una penalidad en la función objetivo, para obligarlas aun nivel cero en una iteración del algoritmo SIMPLEX

Debido a que M es un valor positivo suficientemente grande, la variable R1 se penaliza en la función objetivo utilizando —MR, en el caso de la maximización, y +RM, en la minimización. Debido a esta penalidad El proceso de optimización lógicamente tratara de impulsar R1, al nivel cero

La forma estándar se obtiene restando un superávit X3 en la segunda restricción y añadiendo una holgura X en la tercera restricción. Por tanto obtenemos

Minimice Z= 4X1 +X2

La primera y segunda ecuación no tiene variables que desempeñen el papel de holguras. Por consiguiente, utilizamos las variables R1 y R2 en estas dos ecuaciones y las penalizamos en la función objetivo con MR1 + MR2. La PL resultante se da como

Minimice Z=4X1 +X2 + MR1 + MR2

En el modelo modificado, ahora podemos utilizar R1, R2 y X4 como la solución básica factible inicial como lo demuestra la siguiente tabla simplex

PROGRAMACION LINEAL

Programación Lineal
La PL es un método matemático de resolución de problemas donde el objetivo es optimizar (maximizar o minimizar) un resultado a partir de seleccionar los valores de un conjunto de variables de decisión, respetando restricciones correspondientes a disponibilidad de recursos, especificaciones técnicas, u otras condicionantes que limiten la libertad de elección.
La maximización de beneficios nos llevará a problemas en los que tengamos que determinar la producción: qué se debe fabricar y en qué cantidades para que se obtenga el máximo beneficio teniendo en cuenta las limitaciones técnicas y humanas. En el campo agrícola la adecuada utilización de los terrenos, los cupos de producción, ..., etc.
En los problemas de mínimos podremos calcular los costes mínimos para alimentar a los animales de una granja condicionado a los requerimientos nutricionales. Minimización de la contaminación atmosférica, optimización de recursos humanos, ..., etc.
Un problema de programación lineal es un problema en cual debemos hallar el valor máximo o mínimo de una expresión lineal
ax + by + cz + . . .
(llamada la función ojectiva), sujeta a unas restricciones lineales de la forma
Ax + By + Cz + . . .≤ N
o
Ax + By + Cz + . . .≥ N.
El valor más grande o más pequeño de la función objetiva se llama el valor óptimo, y un conjunto de valores de x, y, z, . . . que se resultan en el valor óptimo es la solución óptima. Las variables x, y, z, . . . se llaman las variables decisión.

Método gráfico
El método gráfico para solucionar a un problema de programación lineal es el siguiente:
Dibuje la región factible de los restricciones.
Calcule las coordenadas de los puntos extremos (puntos de esquina).
Sustituya las coordenadas de los puntos de esquina en la función objetiva para ver cual da el valor óptimo. Este punto da la solución del problema de programación lineal.
Si la región factible no es acotada, este método puede ser erróneo: soluciones óptimas siempre existen cuando la región factible está acotada, pero pueden no existir en el caso no acotado. Si la región factible no es acotada, estamos minimizando una función ojectiva cuyas coeficientes son no negativos, entonces existe una solución dado por este método.

Para determinar si existe una solución en el caso general no acotado:
Acote la región por añadir una recta horizontal por encima del punto de esquina más arriba, y una recta vertical a la derecha del punto de esquina que esté mas hacia la derecha.
Calcule las coordenadas de los puntos nuevos de esquina que se obtiene.
Halle el punto de esquina donde ocurre el valor óptimo de la función ojectiva.
Si el valor óptimo se ocurre a un punto de esquina de la región original (no acotada) entonces existe la solución óptima a aquel punto. Si ocurra el valor óptimo solo a un punto nuevo de esquina, entonces el problema de programación lineal no tiene soluciones.

Problema de maximización estándar
Una problema de maximización estándar con n incógnitas es un problema de programación lineal en lo que necesitamos maximizar (no minimizar) la función ojectiva, sujeta a restricciones de la forma
x ≥ 0, y ≥ 0, z ≥ 0, . . . ,
y restricciones adicionales de la forma
Ax + By + Cz + . . . ≤ N,
donde A, B, C, . . . y N son números con N no negativa.
Observe que la desigualdad aquí debe ser una "≤," y no "=" o "≥."
Método simplex para problemas de maximización estándar
Para solucionar un problema de maximización estándar por el método simplex, seguimos los siguientes pasos:
Paso 1. Convierta las desigualdades en igualdades por introducir variables de holgura por cada una de las restricciones, para convertirlas en igualdades, y escriba las restricciones en forma estándar como muestra enfrente en el ejemplo.
Paso 2. Escriba la tabla inicial simplex.
Paso 3. Escoja la columna pivote: Encuentre el número negativo mayor (en valor absoluto) en el último renglón (excluyendo la entrada más hacia la derecha). Su columna es la columna pivote. (Si hay más que una candidata, escoja alguna.) Si no hay números negativo en último renglón son cero (excluyendo la entrada más hacia la derecha), entonces está terminado: la corriente solución básica maximiza la función ojectiva (la solución básica está descrito más abajo).
Paso 4. Escoja el pivote en la columna pivote: El pivote debe ser una entrada positiva. Para cada entrada positiva b en la columna pivote, calcule la razón a/b, donde a es la entrada de la última columna (valores solución) del renglón. Entre estas razones de prueba, escoja la más pequeña. La entrada correspondiente b es el pivote.

Paso 5. Use el pivote para despejar la columna en la manera normal descrito en el tutorial del método Gauss Jordan, y sustituya la etiqueta de la columna pivote por la etiqueta del reglón pivote. La etiqueta original es la variable saliendo y la nueva etiqueta es la variable entrando.
Solución básica
Para obtener la solución básica que corresponde a alguna tabla del método simplex, iguale a cero a todas las variables que no aparecen como etiquetas de renglones (estas son las variables inactivas).
El valor de una variable que no aparece como una etiqueta de renglón (es decir, una variable activa) es la razón a/b, en la que a es la entrada de la última columna del renglón y a es la entrada de aquel renglón cuya columna tiene la misma etiqueta.
Método Simplex para problemas de minimización
Para solucionar un problema de minimización por el método simplex, se convierte el problema en un problema de maximización por negar la función objetiva: En vez de minimizar c, se maximiza p = -c.
Ejemplo


Minimizar C = 3x + 4y sujeta a
3x - 4y ≤ 12, x + 2y ≥ 4 x ≥ 1, y ≥ 0.
La región factible para este conjunto de restricciones fue mostrada más arriba. Aquí está otra vez con los puntos de esquinas indicados.

Programación Lineal
La PL es un método matemático de resolución de problemas donde el objetivo es optimizar (maximizar o minimizar) un resultado a partir de seleccionar los valores de un conjunto de variables de decisión, respetando restricciones correspondientes a disponibilidad de recursos, especificaciones técnicas, u otras condicionantes que limiten la libertad de elección.
La maximización de beneficios nos llevará a problemas en los que tengamos que determinar la producción: qué se debe fabricar y en qué cantidades para que se obtenga el máximo beneficio teniendo en cuenta las limitaciones técnicas y humanas. En el campo agrícola la adecuada utilización de los terrenos, los cupos de producción, ..., etc.
En los problemas de mínimos podremos calcular los costes mínimos para alimentar a los animales de una granja condicionado a los requerimientos nutricionales. Minimización de la contaminación atmosférica, optimización de recursos humanos, ..., etc.
Un problema de programación lineal es un problema en cual debemos hallar el valor máximo o mínimo de una expresión lineal
ax + by + cz + . . .
(llamada la función objetiva), sujeta a unas restricciones lineales de la forma
Ax + By + Cz + . . .≤ N
o
Ax + By + Cz + . . .≥ N.





Función Objetivo
La función objetivo puede ser:
ó
Donde:
f = coeficientes conocidos.
Ejemplo: Que es la función objetivo por maximizar.

Maíz
Trigo
Elementos disponibles
Horas
2
1

Hectáreas
1
1
800
Utilidad por unidad
$40
$30
480
La cantidad total de tiempo par hectáreas para sembrar maíz y trigo está dada por 2x+y horas que no debe exceder las 800 horas disponibles para el trabajo. Así se tiene la desigualdad:
2x+y<800>0
y>0
En resumen, el problema en cuestión consiste en maximizar la función objetivo P=40x+30y
sujeta a las desigualdades
2x+y<800>0
y>0

Solución Gráfica
Los problemas de programación lineal en dos variables tienen interpretaciones geométricas relativamente sencillas; por ejemplo, el sistema de restricciones lineales asociado con un problema de programación lineal bidimensional- si no es inconsistente- define una región plana cuya frontera está formada por segmentos de recta o semirrectas, por lo tanto es posible analizar tales problemas en forma gráfica.
Si consideremos el problema del granjero López, es decir, de maximizar P = 40x+ 30y sujeta a
2x+y<800>0, y>0 (7)
El sistema de desigualdades (7) define la región plana S que aparece en la figura 5. Cada punto de S es un candidato para resolver este problema y se conoce
Un problema de programación lineal es un problema en cual debemos hallar el valor máximo o mínimo de una expresión lineal
ax + by + cz + . . .
(llamada la función ojectiva), sujeta a unas restricciones lineales de la forma
Ax + By + Cz + . . .≤ N
o
Ax + By + Cz + . . .≥ N.
El valor más grande o más pequeño de la función objetiva se llama el valor óptimo, y un conjunto de valores de x, y, z, . . . que se resultan en el valor óptimo es la solución óptima. Las variables x, y, z, . . . se llaman las variables decisión.

Método gráfico
El método gráfico para solucionar a un problema de programación lineal es el siguiente:
Dibuje la región factible de los restricciones.
Calcule las coordenadas de los puntos extremos (puntos de esquina).
Sustituya las coordenadas de los puntos de esquina en la función objetiva para ver cual da el valor óptimo. Este punto da la solución del problema de programación lineal.
Si la región factible no es acotada, este método puede ser erróneo: soluciones óptimas siempre existen cuando la región factible está acotada, pero pueden no existir en el caso no acotado. Si la región factible no es acotada, estamos minimizando una función objetiva cuyos coeficientes son no negativos, entonces existe una solución dado por este método.




Para determinar si existe una solución en el caso general no acotado:
Acote la región por añadir una recta horizontal por encima del punto de esquina más arriba, y una recta vertical a la derecha del punto de esquina que esté mas hacia la derecha.
Calcule las coordenadas de los puntos nuevos de esquina que se obtiene.
Halle el punto de esquina donde ocurre el valor óptimo de la función ojectiva.
Si el valor óptimo se ocurre a un punto de esquina de la región original (no acotada) entonces existe la solución óptima a aquel punto. Si ocurra el valor óptimo solo a un punto nuevo de esquina, entonces el problema de programación lineal no tiene soluciones.
Problema de maximización estándar
Una problema de maximización estándar con n incógnitas es un problema de programación lineal en lo que necesitamos maximizar (no minimizar) la función ojectiva, sujeta a restricciones de la forma
x ≥ 0, y ≥ 0, z ≥ 0, . . . ,
y restricciones adicionales de la forma
Ax + By + Cz + . . . ≤ N,
donde A, B, C, . . . y N son números con N no negativa.
Observe que la desigualdad aquí debe ser una "≤," y no "=" o "≥."
Método simplex para problemas de maximización estándar
Para solucionar un problema de maximización estándar por el método simplex, seguimos los siguientes pasos:
Paso 1. Convierta las desigualdades en igualdades por introducir variables de holgura por cada una de las restricciones, para convertirlas en igualdades, y escriba las restricciones en forma estándar como muestra enfrente en el ejemplo.
Paso 2. Escriba la tabla inicial simplex.
Paso 3. Escoja la columna pivote: Encuentre el número negativo mayor (en valor absoluto) en el último renglón (excluyendo la entrada más hacia la derecha). Su columna es la columna pivote. (Si hay más que una candidata, escoja alguna.) Si no hay números negativo en último renglón son cero (excluyendo la entrada más hacia la derecha), entonces está terminado: la corriente solución básica maximiza la función ojectiva (la solución básica está descrito más abajo).
Paso 4. Escoja el pivote en la columna pivote: El pivote debe ser una entrada positiva. Para cada entrada positiva b en la columna pivote, calcule la razón a/b, donde a es la entrada de la última columna (valores solución) del renglón. Entre estas razones de prueba, escoja la más pequeña. La entrada correspondiente b es el pivote.
Paso 5. Use el pivote para despejar la columna en la manera normal descrito en el tutorial del método Gauss Jordan, y sustituya la etiqueta de la columna pivote por la etiqueta del reglón pivote. La etiqueta original es la variable saliendo y la nueva etiqueta es la variable entrando.