Programación Lineal

Método de las Dos Fases

Método de Penalidad

IO1 R.Delgadillo 2

Método Simplex

Idea conceptual:

El simplex inicia cuando se tiene una solución factible. Cuando las restricciones son ≤, una solución factible ocurre en el origen de coordenadas.

¿qué sucede cuando el origen no es solución factible?

IO1 R.Delgadillo 3

Método Simplex

Cuando las restricciones son “≥”, “=“,

y/o bi <0, el origen no es una solución factible. El problema ahora radica en determinar una solución básica inicial

Dos métodos:

Método de las dos fases

Método de penalidad

IO1 R.Delgadillo 4

Método de las dos fases

Iniciar de acuerdo a:

Hacer todas las bi’s ≥ 0 ( si alguna bi≤0, multiplicar a la restricción correspondiente por (-1) )

Agregar (o sustraer) variables de holgura a las restricciones “≤” (“≥”)

A cada restricción “≥” ó “=“, agregar una variable artificial

Crear una función objetivo artificial, según

aiX

IO1 R.Delgadillo 5

Método de las dos fases Si el problema es de min =>

Si el problema es de máx =>

Al nuevo problema se le denomina Problema artificial

Ejemplo:

max z = 6x1 - x2

s.a. 4x1 + x2 < 21

2x1 + 3x2 ≥ 13

x1 – x2 = -1

x1, x2 > 0

aia XZMin

aia XZMax

IO1 R.Delgadillo 6

Método de las dos fases

Luego:

max z = 6x1 - x2 <= Función objetivo original

max zα = - - <= Función objetivo artificial

s.a. 4x1 + x2 + x3 = 21

2x1 + 3x2 -x4 + = 13

- x1 + x2 + = 1

x1, x2, x3, x4, , > 0

aX1

aX2

aX1aX2

aX1aX2

IO1 R.Delgadillo 7

Método de las dos fases

Método

1º fase: En la primera fase se resuelve el problema artificial

Si el problema original tiene solución factible al término de la primera fase, se halla la sol óptima del problema artificial

y , y zα =0 ( las , son VNB)0aiX i 0a

iX

IO1 R.Delgadillo 8

Método de las dos fases

2º fase: Se inicia cuando el término de la primera fase indica viabilidad del problema original (esto es, y zα =0),

=>

Base inicial = Base óptima de la primera fase

resolver el problema original a partir de la solución factible hallada (Base inicial)

Nota: el problema original no tiene solución cuando , para algún i, y por lo tanto zα≠0

0aiX

0aiX

IO1 R.Delgadillo 9

Método de las dos fases

Dado el problema:

max z = 6x1 - x2 <= Función objetivo original

max zα = - - <= Función objetivo artificial

s.a. 4x1 + x2 + x3 = 21

2x1 + 3x2 -x4 + = 13

- x1 + x2 + = 1

x1, x2, x3, x4, , > 0

Coloquemos en el tablero

aX1

aX2

aX1aX2

aX1aX2

IO1 R.Delgadillo 10

Método de las dos fasesx1 x2 x3 x4

x3 4 1 1 0 0 0 21

2 3 0 -1 1 0 13

-1 1 0 0 0 1 1

-z 6 -1 0 0 0 0 0

-zα 0 0 0 0 -1 -1 0

x3 4 1 1 0 0 0 21

2 3 0 -1 1 0 13

-1 1* 0 0 0 1 1

-z 6 -1 0 0 0 0 0

-zα 1 4 0 -1 0 0 14

aX1aX2

aX2

aX1

Las VB, deben tener coeficiente 0,

aX1

aX2

Ahora, iniciamos el pivoteamiento

IO1 R.Delgadillo 11

Método de las dos fasesx1 x2 x3 x4

x3 5 0 1 0 0 -1 20

5* 0 0 -1 1 -3 10

x2 -1 1 0 0 0 1 1

-z 5 0 0 0 0 1 1

-zα 5 0 0 -1 0 -4 10

x3 0 0 1 1 -1 2 10

x1 1 0 0 -1/5 1/5 -3/5 2

x2 0 1 0 -1/5 1/5 -2/5 3

-z 0 0 0 1 -1 4 -9

-zα 0 0 0 0 -1 -1 0

aX1aX2

aX1

Fin de la 1ª fase,Za = 0 y 0a

iX

IO1 R.Delgadillo 12

Método de las dos fasesx1 x2 x3 x4

x3 0 0 1 1 10

x1 1 0 0 -1/5 2

x2 0 1 0 -1/5 3

-z 0 0 0 1 -9

x4 0 0 1 1 10

x1 1 0 1/5 0 4

x2 0 1 1/5 0 5

-z 0 0 -1 0 -19

Inicio de la 2ª fase. Se eliminan Fila

correspondiente Za, y columnas de a

iX

Sol. ÓptimaX4=10X1=4X2=5Z=19

IO1 R.Delgadillo 13

Método de las dos fases

Algoritmo: 1ª Fase: Determine una solución óptima del

problema artificial

Si y zα =0), => pase a la 2ª fase

Caso contrario, el problema original no tiene solución (problema inviable)

2ª Fase: Utilice la solución del problema artificial como solución básica inicial posible para el problema original y resuelva el problema.

0aiX

IO1 R.Delgadillo 14

Método de las dos fases

Ejercicio:

Max z = 3x1 + 2x2 + 4x3

s.a.

2x1 + x2 + 3x3 = 60

3x1 +3x2 + 5x3 > 120

x1, x2, x3> 0

IO1 R.Delgadillo 15

Método de las dos fases

Ejercicio:

Max z = 2x1 + 5x2 + 3x3

s.a.

x1 - 2x2 > 20

2x1 +4x2 + x3 = 50

x1, x2, x3> 0

IO1 R.Delgadillo 16

Método de las dos fases

Análisis:

Al finalizar la 1ª fase se tiene ó

Si => el problema original no tiene solución

Si => puede ocurrir

fuera de la base => Se consiguió una solución básica factible.

cuando menos un esta en la base => Solución básica degenerada, pivotear y que entre algún en la base. (no

hay incremento del valor de la F.O.)

Si todos los coeficientes asociados a , en la fila correspondiente a , son ceros => es redundante, descartar esta restricción.

Continuar con la 2ª fase

0aiX 0a

iX

0aiX

0aiXaiX

aiX

aiX

jX

jXaiX

IO1 R.Delgadillo 17

Método de las dos fases

Ejemplo:Max z = x1 + 2x2 + x3

s.a.

x1 + x2 +x3 =16

2x1 +2x2 + 2x3 = 32

x1, x2, x3> 0

max zα = - -

s.a.

x1 + x2 +x3 + =16

2x1 +2x2 + 2x3 + = 32

x1, x2, x3, , > 0

aX1

aX2

aX2

aX1

aX1

aX2

IO1 R.Delgadillo 18

Método de las dos fasesx1 x2 x3

1 1 1 1 0 16

2 2 2 0 1 32

-z 1 2 1 0 0 0

-zα 0 0 0 -1 -1 0

1* 1 1 1 0 16

2 2 2 0 1 32

-z 1 2 1 0 0 0

-zα 3 3 3 0 0 0

x1 1 1 1 1 0 16

0 0 0 -2 1 0

-z 0 1 0 -1 -1 -16

-zα 0 0 0 -3 0 0

aX1aX2

aX2

aX1

aX1aX2

Se alcanzó la sol. Óptima de la 1ª fase.

Se observa que en la base , pero no puede entrar x2, ni

x3 => restricción redundante (se elimina esta fila)

aX2

aX2

IO1 R.Delgadillo 19

Método de las dos fasesx1 x2 x3

x1 1 1 1 16

-z 0 1 0 -16

x2 1 1 1 16

-z 0 0 0 -32

Sol. Óptimax2 = 16Z= 32

IO1 R.Delgadillo 20

Método de Penalidad

Iniciar de acuerdo a:

Hacer todas las bi’s ≥ 0 ( si alguna bi≤0, multiplicar a la restricción correspondiente por (-1) )

Agregar (o sustraer) variables de holgura a las restricciones “≤” (“≥”)

A cada restricción “≥” ó “=“, agregar una variable artificial a

iX

IO1 R.Delgadillo 21

Método de Penalidad

Asociar a cada variable artificial una Penalidad (M), que corresponde al mayor valor posible que cualquier otro que pueda aparecer en los cálculos

Adicionar:

Si el problema es de min => M

Si el problema es de máx => -M

a la función objetivo original

Resolver el nuevo problema

aiX

aiX

IO1 R.Delgadillo 22

Método de Penalidad

Se encuentra una solución factible del problema, cuando todas las variables artificiales están fuera de la base; esto es

La solución óptima se encuentra por un número cualquiera de iteraciones luego que las variables artificiales dejaron la base.

i 0aiX

IO1 R.Delgadillo 23

Método de Penalidad

Ejemplo:

max z = -8x1 +3x2 - 6x3

s.a. x1 + 3x2 + 5x3 = 4

5x1 + 3x2 - 4x3 ≥ 6

x1, x2, x3 > 0

Agregando variables artificiales

max z = -8x1 +3x2 - 6x3 + 0x4 –M - M

s.a. x1 + 3x2 + 5x3 + = 4

5x1 + 3x2 - 4x3 – x4 + ≥ 6

x1, x2, x3,x4, , > 0

aX1aX2

aX1

aX2

aX1aX2

IO1 R.Delgadillo 24

Método de Penalidadx1 x2 x3 x4

1 3 5 0 1 0 4

5 3 -4 -1 0 1 6

-z -8 3 -6 0 -M -M 0

1 3 5 0 1 0 4

5 3 -4 -1 0 1 6

-z -8+6M 3+6M -6+M -M 0 0 10M

x2 1/3 1 5/3 0 1/3 0 4/3

4 0 -9 -1 -1 1 2

-z -9+4M 0 -11-9M -M -1-2M 0 -4+2M

aX1aX2

aX2

aX1

Las VB, deben tener coeficiente 0,

aX2

Ahora, iniciamos el pivoteamiento

aX1

aX2

IO1 R.Delgadillo 25

Método de Penalidadx1 x2 x3 x4

x2 1/3 1 5/3 0 1/3 0 4/3

4 0 -9 -1 -1 1 2

-z -9+4M 0 -11-9M -M -1-2M 0 -4+2M

x2 0 1 29/12 1/12 5/12 -1/12 7/6

x1 1 0 -9/4 -1/4 -1/4 1/4 1/2

-z 0 0 -125/4 -9/4 -13/4-M 9/4-M 1/2

aX1aX2

aX2

Sol. ÓptimaX1=1/2X2=7/6Z=-1/2

IO1 R.Delgadillo 26

Ejercicios

Min 6x1 + 3x2+ 4x3

sujeto a:

x1 + 6x2+ x3 = 10

2x1 + 3x2 ≤ 15

x1, x2, x3 ≥ 0

IO1 R.Delgadillo 27

Ejercicio

Min 4x1 + x2

Sujeto a:

3x1 + x2 = 3

4x1 + 3x2 ≥ 6

x1 + 2x2 ≤ 4

x1, x2 ≥ 0

IO1 R.Delgadillo 28

Método de Penalidad

Análisis:

Al resolver el problema modificado P(M) puede ocurrir:

Se alcanza la sol óptima de P(M)

Se concluye que P(M) tiene sol. Óptima no acotada, es decir Z ->∞

IO1 R.Delgadillo 29

Método de Penalidad

Análisis:

¿Qué respecto del problema original, P?

Si se alcanzó sol óptima de P(M)

La Base no tiene variables artificial ( ), => sol óptima de P(M) = sol óptima de P

La Base continua con variables artificiales, => si M es un número negativo (positivo) muy grande => no existe sol factible de P

jX aj ,0

IO1 R.Delgadillo 30

Método de Penalidad

Análisis:

P(M) tiene sol. Óptima no acotada (esto es la columna pivot es ≤0)

Si todas las variables artificial son ceros ( ), => Problema original (P) tiene sol óptima no acotada

Cuando menos una variables artificial es positiva => P no tiene sol factible

jX aj ,0

IO1 R.Delgadillo 31

Método de Penalidad

Ejemplo:Min z = -x1 -x2

s.a.

x1 - x2 - x3 = 1

- x1 + x2 + 2x3 ≥ 1

x1, x2, x3> 0

Min z = -x1 - x2 +M +M

s.a.

x1 - x2 - x3 + =1

-x1 +x2 + 2x3 -x4 + = 1

x1, x2, x3, x4, , > 0

aX1

aX2

aX2

aX1

aX1

aX2

IO1 R.Delgadillo 32

Método de Penalidadx1 x2 x3 x4

1 -1 -1 0 1 0 1

-1 1 2 -1 0 1 1

-z -1 -1 0 0 M M 0

1 -1 -1 0 1 0 1

-1 1 2* -1 0 1 1

-z -1 -1 -M M 0 0 -2M

1/2* -1/2 0 -1/2 1 1/2 3/2

x3 -1/2 1/2 1 -1/2 0 1/2 1/2

-z -1-M/2 -1+M/2 0 M/2 0 M/2 -3M/2

x1 1 -1 0 -1 2 1 3

x3 0 0 1 -1 1 1 2

-z 0 -2 0 -1 2+M 1+M 3

aX1aX2

aX2

aX1

aX1

aX2

(PM) es no acotado

como , están

fuera de la base=> (P) tiene sol

óptima no acotada

aX2

aX1

aX1

IO1 R.Delgadillo 33

Método de Penalidad

Ejemplo:Min z = -x1 -x2

s.a.

x1 - x2 ≥ 1

- x1 + x2 ≥ 1

x1, x2> 0

Min z = -x1 - x2 +M +M

s.a.

x1 - x2 - x3 + =1

-x1 +x2 -x4 + = 1

x1, x2, x3, x4, , > 0

aX1

aX2

aX2

aX1

aX1

aX2

IO1 R.Delgadillo 34

Método de Penalidadx1 x2 x3 x4

1 -1 -1 0 1 0 1

-1 1 0 -1 0 1 1

-z -1 -1 0 0 M M 0

1* -1 -1 0 1 0 1

-1 1 0 -1 0 1 1

-z -1 -1 M M 0 0 -2M

x1 1 -1 -1 0 1 0 1

0 0 -1 -1 1 1 2

-z 0 -2 -1+M M 1 0 1-2M

aX1aX2

aX2

aX1

aX1

aX2(PM) es no acotado y

=> (P) no tiene sol factible

022a

X

aX2