Adaptacion a otras foramde modelo

Clase # 8

Hasta el momento sólo se han estudiado problemas en la forma estándar

ADAPTACIÓN A OTRAS FORMAS DEL MODELO.

• Maximizar Z. • Restricciones de la forma ≤ . • Todas las variables no negativas. • bi ≥ 0 para toda i = 1,2,...,m
8-1 8-2

Forma estándar Maximizar Z = 3X1 + 5X 2 Sujeto a X1 ≤4 2X 2 ≤ 12 3X 1 + 2X 2 ≤ 18

Existen variaciones cuando:

X1 , X2 ≥ 0
8-3•Restricciones en forma de igualdad. •Lados derechos negativos. •Restricciones de la forma ≥ . • Función objetivo minimizar.
8-4

1.Restricciones en forma de igualdad.
Cualquier restricción del tipo a 11X1 + a 12X2 + .............+ a 1nXn = b 1 Es equivalente a a 11X1 + a 12X2 + .............+ a 1nXn ≤ b 1 a 11X1 + a 12X2 + .............+ a 1nXn ≥ b 1 Esto es inconveniente pues se aumenta el número derestricciones
8-5

Lo que se hace entonces es introducir variables artificiales

Veamos un ejemplo
8-6

1

Cambiemos la tercera restricción de desigualdad en el ejemplo de la Wyndor Glas c.o , por una igualdad.
Maximizar Z = 3X1 + 5X 2 Sujeto a X1 ≤4 2X 2 ≤ 12 3X 1 + 2X 2 = 18

X1 , X2 ≥ 0
8-7

10 9 8 7 6 5 4 3 2 1

x2

( 2,6) Región factible

X2 =6

(4,3)
3X1 + 2X2 =18 12 3 4 5 X1 =4 6 7 8

0

x 9 10 1
8-8

La forma aumentada de este problema es:
(0) Z - 3X 1 - 5X 2 (1) (2) (3) X1 2X 2 3X 1 + 2X2 + X3 +X 4 =0 = 4 = 12 = 18

¿Cual es la S.B.F inicial?

Es necesario introducir variables artificiales (2 pasos).

Observe que no está completa la matriz identidad.
8-9 8-10

Variables artificiales.
Ä Facilitan hallar una S.B.F inicial. Ä Deben cumplirrequerimientos de no negatividad. Ä Se deben introducir penalizaciones muy grandes en la función objetivo. Ä Se convierten en V.B en la ecuación en que han sido introducidas. ÄEl proceso iterativo del simplex se deshace de ellas.
8-11

Paso 1.
Se introduce una variable artificial X 5 3X 1 + 2X 2 + X5 = 18

Es muy similar a introducir una variable de holgura
8-12

2

Paso 2.
Se asignauna penalización enorme en la función objetivo por el hecho de tener X5 ≥ 0

Se modifica la función objetivo

Este método se llama el método de la M grande, pues M representa un número muy grande

Maximizar Z = 3X1 + 5X 2 - M X5

8-13

8-14

La forma aumentada del problema artificial es:

La S.B.F inicial en este problema sería entonces:
+MX5 =0

(0) Z - 3X 1 - 5X 2 (1) (2) (3) X1+ X3 2X 2 3X 1 + 2X2

= 4 +X 4 = 12 +X 5 = 18

X1=0 , X 2=0 , X3=4 , X 4=12 , X5 =18

8-15

8-16

Comparemos los problemas. Problema real Problema artificial
10 9 8 7 6 5 4 3 2 1

x2

Problema real Región factible (solo el segmento de recta)

Max Z = 3X1 + 5X2 Max Z = 3X 1 + 5X2 - M X 5 Sujeto a Sujeto a X1 ≤4 X1 ≤4 2X2 ≤ 12 3X1 + 2X2 ≤ 18 2X2 ≤ 12 3X1 + 2X 2 = 18 X1 , X2 ≥ 0 Así3X1 + 2X 2 +X5= 18 X1 , X2, X5 ≥ 0
8-17

0

1 2 3

4 5

6 7 8

x 9 10 1
8-18

3

(0,6) Z=30 - 6M

Problema artificial
(2,6) Z= 36

10 9 8 7 6 5 4 3 Región 2 factible 1 1 2 3 (0,0) Z= 0 - 18M 0 4 5

x2

(4,3) Z= 27

Nótese que ambos problemas son similares cuando X5 = 0

6 7 8

x 9 10 1
8-20

(4,0) Z= 12 - 6M 8-19

Recordemos la forma aumentada del problemaartificial

Este sistema no se encuentra en la forma apropiada de la Eliminación Gaussiana.

(0) Z - 3X 1 - 5X 2 (1) (2) (3) X1 + X3 2X 2 3X 1 + 2X2

+MX5 =0 = 4 +X 4 = 12 +X 5 = 18
Ojo: En el renglón (0), los coeficientes de las variables artificiales deben ser cero
8-21 8-22

El renglón (0) debe modificarse antes de empezar a encontrar la solución óptima

Z - 3X 1 - 5X 2 - M ( 3X 1 + 2X2

+MX5 +X 5

=0 = 18) = -18M

Z - (3M+3) X 1 - (2M+5) X 2

Ya conocemos bien el procedimiento empleado por el método simplex. Este caso es igual y se procede de la misma manera.

Este nuevo renglón (0) queda expresado solamente en términos de las V.N.B Veamos las tablas simplex
8-23 8-24

4

1
Iter V.B Ec #

Coeficientes Z X1
-3M -3

2 X4 0 X5 0
L.D Iter V.B Ec #...