Metodo Simplex Dual

Ejemplo (problemas primal y dual del carpintero). Un carpintero modesto fabrica dos tipos de mesas de madera. Cada mesa del tipo 1 necesita 4 horas de mecanizado primario (preparaci´n de piezas) y o 4 horas de mecanizado secundario (ensamblado y barnizado). An´logamente, a cada mesa del tipo 2 necesita 3 horas de mecanizado primario y 7 horas de mecanizado secundario. Las disponibilidades diariasde mecanizados primario y secundario son respectivamente de 40 y 56 horas-m´quina. La venta de una mesa del tipo a 1 reporta un beneficio de 70 d´lares, mientras que la venta de una mesa del o tipo 2 de 90 d´lares. El objeto de este problema es determinar el n´mero o u de mesas de cada tipo que han de producirse diariamente para maximizar el beneficio obtenido. Soluci´n: o Primero ordenamos losdatos en una tabla: Horas Mec. Prim. Sec. Variables x1 4 4 (mesas) x2 3 7 Horas (Max.) 40 56

Ahora escribimos el problema lineal:

Maximizar z = 70x1 + 90x2 sujeta a 4x1 + 3x2 ≤ 40 4x1 + 7x2 ≤ 56 Escribimos el problema en forma de ecuaci´n agregando variables de holgura: o

1

Maximizar z = 70x1 + 90x2 sujeta a 4x1 + 3x2 + x3 = 40 4x1 + 7x2 + x4 = 56 Escribimos la tabla simplex: B´sica x1x2 x3 a z -70 -90 0 x3 4 3 1 4 7 0 x4 x4 0 0 1 Soluci´n o 0 40 56

La tabla es consistente porque x1 y x2 son no b´sicas (x1 = 0, x2 = 0) a Iteraci´n o 0 entra x2 sale x4 1 entra x1 sale x3 2 o ´ptima B´sica a x1 x2 z -70 -90 x3 4 3 x4 4 7 z -18.57 0 x3 2.29 0 x2 0.57 1 z 0 0 x1 1 0 x2 0 1 x3 x4 Soluci´n o 0 0 0 1 0 40 0 1 56 0 12.86 720 1 -0.43 16 0 0.14 8 8.13 9.38 850 0.44 -0.19 7 -0.25 0.25 4Por lo tanto el carpintero de fabricar 7 mesas del tipo 1, 4 del tipo 2 y su ganancia ser´ de $850. a Para escribir el dual, reescribamos el primal como

Maximizar z = 70x1 + 90x2 + 0x3 + 0x4 sujeta a 4x1 + 3x2 + x3 + 0x4 = 40 4x1 + 7x2 + 0x3 + x4 = 56 2

Seg´n las reglas que ya se enunciaron resulta: u

Minimizar w sujeta a 4y1 + 4y2 3y1 + 7y2 y1 + 0y2 0y1 + y2 y1 , y 2 Reordenandoresulta

= 40y1 + 56y2 ≥ ≥ ≥ ≥ 70 90 0 0 no restringidas

Minimizar w sujeta a 4y1 + 4y2 3y1 + 7y2 y1 , y 2

= 40y1 + 56y2 ≥ 70 ≥ 90 ≥ 0

Para resolver el problema, tenemos que escribirlo en forma de ecuaci´n, o

Minimizar w sujeta a 4y1 + 4y2 − y3 + R1 3y1 + 7y2 − y4 + R2 yk

= 40y1 + 56y2 = 70 = 90 ≥ 0 ∀k

Resolveremos el problema por el m´todo de dos fases. Primero resolvemos: e

3Minimizar r sujeta a 4y1 + 4y2 − y3 + R1 3y1 + 7y2 − y4 + R2 yk Escribimos la tabla simplex: B´sica y1 a r 0 R1 4 3 R2 y2 0 4 7 y3 0 -1 0 y4 0 0 -1

= R1 + R2 = 70 = 90 ≥ 0 ∀k

R1 -1 1 0

R2 -1 0 1

Soluci´n o 0 70 90

que no es consistente, esto se soluciona sumando las filas R1 y R2 a la fila r: B´sica y1 a r 7 R1 4 3 R2 y2 y3 11 -1 4 -1 7 0 y4 -1 0 -1 R1 0 1 0 R2 0 0 1 Soluci´n o160 70 90

ahora podemos empezar a iterar. Fase 1 Iteraci´n o 0 entra y2 sale R2 1 entra y1 sale R1 2 o ´ptima B´sica a r R1 R2 r R1 y2 r y1 y2 y1 y2 y3 y4 R1 R2 Soluci´n o 7 11 -1 -1 0 0 160 4 4 -1 0 1 0 70 3 7 0 -1 0 1 90 2.29 0 -1 0.57 0 -1.57 18.57 2.29 0 -1 0.57 1 -0.57 18.57 0.43 1 0 -0.14 0 0.14 12.86 0 0 0 0 -1 -1 0 1 0 -0.44 0.25 0.44 -0.25 8.13 0 1 0.19 -0.25 -0.19 0.25 9.38

4Ahora el problema tiene la forma

Minimizar w sujeta a y1 − 0.44y3 + 0.25y4 y2 + 0.19y3 − 0.25y4 yk Fase 2 Iteraci´n o 0 consistente? Iteraci´n o 1 o ´ptima

= 40y1 + 56y2 = 8.13 = 9.38 ≥ 0 ∀k

B´sica y1 y2 a y3 y4 Soluci´n o z -40 -56 0 0 0 y1 1 0 -0.44 0.25 8.13 y2 0 1 0.19 -0.25 9.38 B´sica y1 y2 a y3 y4 Soluci´n o z 0 0 -7 -4 850 y1 1 0 -0.44 0.25 8.13 y2 0 1 0.19 -0.25 9.38

Entonces,la soluci´n del problema dual es y1 = 8.13, y2 = 9.38 y w = 850. o Como vemos, las funciones objetivo primal y dual tienen el mismo valor en el optimo zop = wop . ´ ¿C´mo obtenemos los valores del problema dual a partir del primal? o Metodo 1

Valores ´ptimos o de las variables duales dual (y1 , y2 ) = 70, 90

 Vector fila de los coeficientes × objetivos originales de las = variables b´sicas...