Metodo simplex dual ejemplos

Solo disponible en BuenasTareas
  • Páginas : 11 (2597 palabras )
  • Descarga(s) : 0
  • Publicado : 16 de noviembre de 2011
Leer documento completo
Vista previa del texto
Algoritmo Dual-Simplex para un modelo de maximización
Introducción
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 un ejemplo para ilustrar su aplicación.
Primero se debe expresar el modelo en formato estándar, agregando las variables de holgura y de exceso que se requieran.
Enseguida, enlas ecuaciones que tengan variables de exceso (resultantes de restricciones de tipo >), se debe multiplicar por (-1) en ambos lados , para hacer positivo el coeficiente de la variable de exceso, y formar así un vector unitario que nos permita tomar esta variable de exceso como una variable básica inicial. sin necesidad de agregar una variable artificial en esa restricción.

Al hacer lo anteriorse logra que debajo de las variables básicas aparezca una matriz identidad, que es la que el simplex siempre toma como base inicial.
Obtendremos que los términos del lado derecho de las ecuaciones multiplicadas por (-1) quedan con signo negativo, lo cual hace que la solución inicial sea infactible.
Es importante destacar que este proceso es muy útil ya que en muchos modelos evita la inclusión devariables artificiales en el momento de transformar un modelo a formato estándar.

Ejemplo del Método Simplex Dual
Sea el siguiente modelo:
Maximizar Z= -2X1 -2X2 -3X3
Sujeto a : 2X1 +4X2 +2X3 > 10
3X1 -3X2 +9X3 = 12

con X1, X2, X3 > 0
Expresemos el modelo en formato estándar
Maximizar Z= -2X1 -2X2 -3X3
Sujeto a : 2X1 +4X2 +2X3 -IE1 = 10
3X1 -3X2+9X3 -IE2 = 12
multipliquemos por (-1) en ambos lados de las ecuaciones, para formar los vectores unitarios, requeridos para contar con una base inicial unitaria.
Maximizar Z= -2X1 -2X2 -3X3
Sujeto a : -2X1 -4X2 -2X3 +IE1 = -10
-3X1 +3X2 -9X3 +IE2 = -12
paso 1.
Tomando las variables básicas iniciales hacemos lo siguiente:
Cj -2 -2 -3 0 0 XB
CB X1 X2 X3 E1 E2 SoluciónBásicas
0 -2 -4 -2 1 0 -10 E1
0 -3 3 -9 0 1 -12 E2
Zj 0 0 0 0 0 0
Ej -2 -2 -3 0 0 0 Z
Paso 2
Sale E2 = (XB)2 o sea s = 2
Paso 3
a. Calculando los cocientes para todo (Sj)2 < 0 obtenemos:

o sea que X3 es la variable de entrada( entonces e = 3) y el elemento pivote es el (Se)s = (S3)2 = -9
b. Efectuando el pivoteo obtenemos la tabla siguiente:
Tabla 1 (maximizar)
Cj -2 -2 -3 0 0 XBCB X1 X2 X3 E1 E2 Solución Básicas
0 -4/3 -14/3 0 1 -2/9 -22/3 E1
-3 -1/3 -1/3 1 0 -1/9 4/3 X3
Zj -1 1 -3 0 1/3
Ej -1 -3 0 0 -1/3 -4 Z
c. Repitiendo el algoritmo desde el paso 1, obtenemos:
sale E1 = (XB)1 y entra X2 por lo cual obtenemos la siguiente tabla
Tabla 2
Cj -2 -2 -3 0 0 XB
CB X1 X2 X3 E1 E2 Solución Básicas
-2 2/7 1 0 -3/14 1/21 11/7 X2
-3 3/7 0 1 -1/14 -2/21 13/7 X3Zj -13/7 1 -3 -9/14 4/21
Ej -1/7 0 0 -9/14 -4/21 -61/7 Z
Como se observa, ahora estamos en el óptimo.
En definitiva: X2* = 11/7
X3* = 13/7

Z* = - 61/7

SEGUNDO EJEMPLO:Resolver el siguiente modelo usando el método Dual-Simplex
Minimizar Z= 2X1 + 2X2
Sujeto a : 3X1 +X2 > 10
4X1 +3X2 > 12
X1 +2X <
con X1, X2 > 0
Expresando el modelo en formato estándar y ajustándolo para que las variables básicas sean las variables de holgura tenemos:
Minimizar Z= 2X1 + 2X2
Sujeto a : -3X1 -X2 +IE1 = -3
-4X1 -3X2 +IE2 = -6X1 +2X +IE3 = 3
Usando el método Dual Simplex obtenemos, sucesivamente:

Tabla 0
Basicas X1 X2 E1 E2 H3 Solución
E1 -3 -1 1 0 0 -3
E2 -4 -3 0 1 0 -6
H3 1 2 0 0 1 3
Ej 2 1 0 0 0 0
Sale E2
Entonces los cocientes son


Nota: Obsérvese que cuando el objetivo es minimizar, se toma el valor absoluto de los cocientes.
Tabla 1
Basicas X1 X2 E1 E2 H3 Solución
E1 -5/3 0 1 -1/3 0 -1...
tracking img