modelos de minimización si la f.o. es minimizar, existen 2 alternativas: 1. transformar el problema...

Modelos de MinimizaciónSi la F.O. es minimizar, existen 2 alternativas: 1. Transformar el problema de una minimización a una

maximización definiendo una nueva F.O.(Max z’=-z).

MIN Z=c1x1+c2x2+..+cnxn MAX Z’=-c1x1-c2x2-..-cnxn

2. Cambiar la regla para elegir la variable entrante. Se escoge la de zj – cj más positivo. El óptimo se alcanza cuando todos los costos reducidos (zj – cj) de las variables no básicas son negativos.

Restricciones del tipo(=)

ai1x1 + ai2x2 +... + ainxn = bi

Para este tipo de restricciones existen 2 alternativas:

Transformarla en dos restricciones: ai1x1 + ai2x2 +... + ainxn bi ai1x1 + ai2x2 +... + ainxn bi

Restricciones del tipo(=) ai1x1 + ai2x2 +... + ainxn = bi

La otra alternativa es introducir en la restricción otro tipo de variables llamadas artificiales (ti).

ai1x1 + ai2x2 +... + ainxn + ti = bi

Las variables artificiales sólo se usan como un ajuste matemático para poder utilizar el método simplex. Por ello, las variables artificiales no pueden aparecer en la solución óptima, porque lo que hacen es “relajar” las restricciones, para poder tener una solución inicial.

Mas adelante explicaremos la forma para resolver problemas con variables artificiales.

Restricciones del tipo()Si una o más restricciones son del tipo

ai1x1 + ai2x2 +... + ainxn bi

para poder usar el método Simplex, se debe restar una variable ei tal que la restricción se transforme en igualdad.

ai1x1 + ai2x2 +... + ainxn - ei = bi

La variable ei es denominada variable de excedente, pues

ei= ai1x1 + ai2x2 +... + ainxn - bi

Restricciones del tipo()

Con esta transformación no se puede empezar Simplex porque al dejar las variables de excedente en la base se obtiene una solución básica infactible. Luego, se hace necesario introducir variables artificiales (ti).

ai1x1 + ai2x2 +... + ainxn – ei + ti = bi

Las variables artificiales no tienen ningún significado y sólo se usan como un ajuste matemático para poder utilizar Simplex. Por ello, las variables artificiales no pueden aparecer en la solución óptima.

Modelos de con restricciones del tipo()

Existen 2 procedimientos para asegurar que las varibles artificiales no estarán en la solución óptima:

• El método de la “M” grande.

• El método de las dos fases.

Método de la “M” grande

Para asegurar que las varibles artificiales no estarán en la solución óptima, se incorporan en la F.O. cada una de las variables artificiales con un coeficiente “M” muy grande, infinito. Luego el modelo tenderá a sacarlos de la solución final para evitar dicha penalización. Luego la F.O. quedará:

MAX Z=c1x1+c2x2+..+cnxn-Mt1 -Mt2 -...-Mtk

oMIN Z=c1x1+c2x2+..+cnxn +Mt1 +Mt2 +...+Mtk

donde k: número de restricciones del tipo ().

Método de la “M” grande

Ejemplo:

MIN z = 200 x1 + 240 x2

s.a.10 x1+5 x2 50 x1 2

x1, x2 0

MIN z = 200x1 + 240x2 + Mt1

s.a. 10x1+5x2 -e1 +t1 = 50 x1 +h1 = 2

x1, x2, e1, t1, h1 0

Método de la “M” grande

Ejemplo:

VB CB XB x1 x2 e1 t1 h1

t1 M 50 10 5 -1 1 0 50/10=5

h1 0 2 1 0 0 0 1 2/1=2

50M

10M-

200

5M-240

-M 0 0

200 240 0 M 0

Min

Método de la “M” grande

Ejemplo (cont.):

VB CB XB x1 x2 e1 t1 h1

t1 M 30 0 5 -1 1 -10 30/5=6

X1 200

2 1 0 0 0 1 2/0=?

30M+40

0

0 5M-240

-M 0 200-10M

200 240 0 M 0

Min

Método de la “M” grande

Ejemplo (cont.):

VB CB XB x1 x2 e1 t1 h1

x2 240

6 0 1 -1/5

1/5 -2

X1 200

2 1 0 0 0 1

1840 0 0 -48 48-M -280

200 240 0 M 0

Sol. óptima

Método de las “2 fases”

Otro método para asegurar que las varibles artificiales no estarán en la solución óptima es el de las “2 fases”. Este método subdivide el problema en dos partes:

Fase I: Se trata de encontrar una solución factible al problema original, sin considerar para nada la F.O. propia del problema. Se genera una nueva F.O. que minimiza la suma de las variables artíficales del problema (ti):

MIN W = t1 + t2 +...+ tk

Método de las “2 fases”

Se resuelve por Simplex, y si al llegar al óptimo se tienen variables artificiales en la base, entonces se concluye que el problema no tiene solución por incompatibilidad de restricciones. De no haber variables artificiales en la base, se pasa a la fase II.

Fase II: Si el problema es factible, se resuelve el problema original, a partir de la solución básica factible hallada en la fase I. Esto es, reeemplazar en el último tableau de la fase I, los coeficientes de la F.O. (ci) por los del problema original, y actualizar la columba CB y los costos reducidos (zj-cj).

En las columnas de las variables artificiales no se considera el valor de los costos reducidos (zj-cj).

Método de las “2 fases”

Ejemplo:

MIN z = 200 x1 + 240 x2

s.a.10 x1+5 x2 50 x1 2

x1, x2 0

MIN z = 200x1 + 240x2

s.a. 10 x1+ 5 x2 - e1 + t1 = 50 x1 + h1 = 2

x1, x2, e1, t1, h1 0

Método de las “2 fases”

Fase I:

VB CB XB x1 x2 e1 t1 h1

t1 1 50 10 5 -1 1 0 50/10=5

h1 0 2 1 0 0 0 1 2/1=2

50 10 5 -1 0 0

0 0 0 1 0Min

MIN w = t1

s.a. 10 x1 + 5 x2 - e1 + t1 = 50 x1 + h1 = 2 x1, x2, e1, t1, h1 0

Método de las “2 fases”

Fase I: VB CB XB x1 x2 e1 t1 h1

t1 1 30 0 5 -1 1 -10 30/5=6

x1 0 2 1 0 0 0 1 2/0=?

30 0 5 -1 0 -10

0 0 0 1 0Min

VB CB XB x1 x2 e1 t1 h1

x2 0 6 0 1 -1/5 1/5 -2

x1 0 2 1 0 0 0 1

0 0 0 0 -1 0

0 0 0 1 0Min

Óptimo Factible

Método de las “2 fases”

Fase II:

Min

VB

CB XB x1 x2 e1 t1 h1

x2 240 6 0 1 -1/5 1/5 -2

x1 200 2 1 0 0 0 1

1840 0 0 -48 -- -280

200

240 0 -- 0

Óptimo

VB CB XB x1 x2 e1 t1 h1

x2 0 6 0 1 -1/5 1/5 -2

x1 0 2 1 0 0 0 1

0 0 0 0 -1 0

0 0 0 1 0Min

Modelos con variables sin restricción de signoCuando aparecen variables sin restricción de signo, se hace el siguiente reemplazo para cada una de estas variables: xj = yj – uji

con yj ,uji 0

Situaciones EspecialesEmpate en la variable que sale: Técnicamente significa que más de una restricción corta el eje en un mismo punto. Si se elige cualquiera puede ser que se salga de la región factible. Esto se soluciona alterando en un pequeño delta el bi de una de las restricciones que empata.

Múltiples soluciones óptimas: Cuando existen múltiples soluciones en el método Simplex los coeficientes zj - cj de algunas variables no básicas son cero. En estos casos, se continúa realizando las iteraciones normalmente hasta llegar a una solución óptima. Luego, se vuelve al “tableau” donde apareció un coeficientes zj - cj =0 de alguna variable no básica, y se hace entrar a la base. Finalmente, se sigue iterando con este cambio hasta llegar a otra solución óptima.

Múltiples soluciones

Ejemplo:

MAX z = 6x1 + 3x2

s.a.x1+x2 302x1+x2 40

x1, x2 0

MAX z = 6x1 + 3x2

s.a. x1+x2+h1 = 30 2x1 +x2 +h2 = 40

x1, x2,h1, h2 0

Múltiples soluciones

Ejemplo:

VB CB XB x1 x2 h1 h2

h1 0 30 1 1 1 0 30/1=30

h2 0 40 2 1 0 1 40/2=20

0 -6 -3 0 0

6 3 0 0

Max

Múltiples soluciones

Ejemplo:

VB CB XB x1 x2 h1 h2

h1 0 10 0 ½ 1 -1/2 30/1=30

x1 0 20 1 ½ 0 ½ 40/2=20

120 0 0 0 3

6 3 0 0Sol.

Óptima 1

Múltiples soluciones

Ejemplo:

Max

VB CB XB x1 x2 h1 h2

h1 0 10 0 ½ 1 -½ 10/0.5=20

x1 0 20 1 ½ 0 ½ 20/0.5=40

120 0 0 0 3

6 3 0 0

Múltiples soluciones

Ejemplo:

VB CB XB x1 x2 h1 h2

x2 3 20 0 1 2 -1

x1 6 10 1 0 -½ 1

120 0 0 0 3

6 3 0 0Sol.

Óptima 2

Situaciones Especiales (Cont.)

Incompatibilidad de Restricciones : Puede ocurrir cuando el conjunto de restricciones no está conformado por un solo tipo. Es decir, debe tener restricciones () con resticciones del tipo () o (=). Si todas son de un mismo sentido casi nunca habrá incompatibilidad.

El método Simplex detecta la incompatibilidad de restricciones porque al observar la solución óptima se encuentran variables artificiales (ti) en la base, al utilizar el método de la “M” grande. El método de la “M” grande tiene la deficiencia que después de todas la iteraciones, recién ahí se detecta la incompatibilidad de restricciones, lo cual se evita a usar el método de las 2 fases, dado que si al final de la fase I quedan variables artificiales en la base, significa que el problema presenta inconsistencia.

Incompatibilidad de Restricciones

Ejemplo con método de la M grande:

MAX z = 3x1 + x2

s.a.x1+x2 10 x1 20

x1, x2 0

MAX z = 3x1 + x2 - Mt1

s.a. x1+x2+h1 = 10 x1 - e1 +t1 = 20

x1, x2, e1, t1, h1 0

VB CB XB x1 x2 h1 t1 e1

h1 0 10 1 1 1 0 0 10/1=10

t1 -M 20 1 0 0 1 -1 20/1=20

-20M -M-3 -1 0 0 M

3 1 0 -M 0

Incompatibilidad de Restricciones

Ejemplo:

Max

VB CB XB x1 x2 h1 t1 e1

x1 3 10 1 1 1 0 0

t1 -M 10 0 -1 -1 1 -1

30-10M

0 3+M-1

3+M

0 M

3 1 0 -M 0

Incompatibilidad de Restricciones

Ejemplo:

Inconsistencia