metodo dual simplex

Instituto tecnológico superior de Coatzacoalcos

Materia:
Investigación de operaciones
Docente:
Karina Sastre Antonio
Integrantes:
Barradas Méndez Ramón Daniel
Figueroa Hernández Cindy Paola
Helston Vara Gabriela
Marín Valdivieso Fernando
Carrera:
4 A Ing. Industrial



INDICE

Introducción………………………………..…………………..1

Desarrollo……………………………………………………….2Conclusión……………………………………………………..9

Referencias bibliográficas………………………………….10




INTRODUCCIÓN
El método simplex es un algoritmo iterativo que iniciando en una solución básica factible pero no óptima, genera soluciones básicas factibles cada vez mejores hasta encontrar la solución óptima (sí esta existe). Nótese que la base de su lógica es mantener la factibilidad, mientras busca la optimalidad. Pero surge la posibilidad de usar otro esquemaigualmente iterativo, que como contraparte del simplex, comienza en una solución básica óptima, pero no factible y mantiene la inmejorabilidad mientras busca la factibilidad. Con este procedimiento se llega igualmente a la solución óptima.
El nuevo algoritmo fue desarrollo en 1954 por C. E. Lemke y se conoce con el nombre de Método Dual-Simplex. A continuación se presenta su estructura y unejemplo para ilustrar su aplicación.
Se aplica a problemas que tienen factibilidad dual inicial, es decir, que son óptimos pero infactibles simples.
La factibilidad dual se reconoce expresando las restricciones en la forma canónica (£). La función objetivo puede ser de maximización o minimización.
El método simplex dual resulta ser una estrategia algoritmica eficiente cuando luego de llevar unmodelo de programación lineal a su forma estándar, la aplicación del método simplex no es inmediata o más bien compleja, por ejemplo, puede requerir la utilización del método simplex de 2 fases.
Una aplicación típica del método simplex dual es en la resolución de problemas con una función objetiva de minimización, con restricciones del tipo mayor o igual y donde las variables de decisión son mayoreso iguales a cero.



DESARROLLO
El método dual simplex se aplica a problemas que tienen factibilidad dual inicial, es decir, que son óptimos pero infactibles simples.La factibilidad dual se reconoce expresando las restricciones en la forma canónica (£). La función objetivo puede ser de maximización o minimización. Condiciones:
Factibilidad
La variable de salida es la variable básica quetiene el valor más negativo, en caso de empate procedemos de forma arbitraria, y si todas las variables básicas son no negativas, el proceso finaliza y la solución factible óptima se encuentra.
 Optimalidad
La variable de entrada es seleccionada de las variables no básicas, se hacen cocientes cuyos denominadores serán necesariamente negativos y se toman de la ecuación pivote. Los numeradores seránlos números correspondientes en la función objetivo.

Ejemplo 1




Paso 1: Se lleva el modelo a su forma estándar. Esto se logra agregando variables de exceso en cada una de las restricciones (3 primeras: S1, S2, S3, respectivamente). Luego, se multiplica cada fila de las restricciones por -1 de modo de disponer una solución básica inicial (infactible) en las variables de exceso S1, S2 yS3. De esta forma se obtiene la siguiente tabla inicial.
A
B
C
S1
S2
S3

-15
-2
-1
1
0
0
-200
-7,5
-3
-1
0
1
0
-150
-5
-2
-1
0
0
1
-120
315
110
50
0
0
0
0
Paso 2: Se selecciona el lado derecho "más negativo" lo cual indicará cuál de las actuales variables básicas deberá abandonar la base. En el ejemplo el lado derecho más negativo se encuentra en la primerafila, por tanto S1 deja la base. Para determinar cuál de las actuales variables no básicas (A, B, C) entrará a la base se busca el mínimo de {-Yj/aij} donde aij es el coeficiente de la respectiva variable no básica en la fija i (del lado derecho más negativo, marcado en verde) y donde Yj es el costo reducido de la respectiva variable no básica. De esta forma se...