05_ind2209_alumno_15

Investigación de OperacionesIND2209

Profesor: Pamela Álvarez M.

Facultad de IngenieríaDepartamento de Ciencias de la Ingeniería

Unidad Nº 3

IND2209. Prof.: Pamela Álvarez M.

• Algunas preguntas que debemos responder:

• ¿Cómo encontrar una base factible inicial si no es evidente?:

• Método de las dos fases• Método de la Big‐M

• ¿Cómo identificar?:

• Múltiples soluciones• Problemas no acotados• Problemas degenerados

2

MÉTODO SIMPLEX


• Dado el problema:

3

MÚLTIPLES SOLUCIONES

1 2

1 2

1 2

1 2

2. . 3 9

2 6, 0

Max x xs a x x

x xx x

-1 3 1 0 92 1 0 1 6-2 -1 0 0 0

x1 x2 x3 x4 b

0 7/2 1 1/2 121 1/2 0 1/2 30 0 0 1 6

x1 x2 x3 x4 b

Solución óptima, pero veamos qué pasa si entramos x2a la base.

IND2209. Prof.: Pamela Álvarez M. 4


1 2

1 2

1 2

1 2

2. . 3 9

2 6, 0

Max x xs a x x

x xx x

0 7/2 1 1/2 121 1/2 0 1/2 30 0 0 1 6

x1 x2 x3 x4 b

También solución óptima. Veamos qué pasa si entramos x3 a la base.

0 1 2/7 1/7 24/71 0 -1/7 6/14 9/70 0 0 1 6

x1 x2 x3 x4 b



1 2

1 2

1 2

1 2

2. . 3 9

2 6, 0

Max x xs a x x

x xx x

También solución óptima. 0 7/2 1 1/2 121 1/2 0 1/2 30 0 0 1 6

x1 x2 x3 x4 b

0 1 2/7 1/7 24/71 0 -1/7 6/14 9/70 0 0 1 6

x1 x2 x3 x4 b

Existe solución múltiple si los costos reducidos de las variables no básicas son

iguales a cero.


Es decir, cualquier combinación

convexa de los 2 vértices es una

solución óptima también.

6


1 2

1 2

1 2

1 2

2. . 3 9

2 6, 0

Max x xs a x x

x xx x

x2

x1

*

3 9 / 7 9 12 / 70 24 / 7 24 1 / 7

1 , 0,112 0 120 0 0

x



7

PROBLEMAS NO ACOTADOS

-1 1 1 0 2-1 2 0 1 6-2 -1 0 0 0

x1 x2 x3 x4 b

Problema no acotado

1 2

1 2

1 2

1 2

2. . 2

2 6, 0

Max z x xs a x x

x xx x

?

x2

x1



8

SOLUCIONES DEGENERADAS

1 2

1 2

1

2

1 2

. 4 5 4054

, 0

Max x xs a x x

xxx x

4 5 1 0 0 401 0 0 1 0 50 1 0 0 1 4-1 -1 0 0 0 0

x1 x2 x3 x4 x5 b

Empate, pero veamos qué pasa si sale x5 de la base.

0 5 1 -4 0 201 0 0 1 0 50 1 0 0 1 40 -1 0 1 0 5

x1 x2 x3 x4 x5 b



1 2

1 2

1

2

1 2

. 4 5 4054

, 0

Max x xs a x x

xxx x

Solución óptima

0 5 1 -4 0 201 0 0 1 0 50 1 0 0 1 40 -1 0 1 0 5

x1 x2 x3 x4 x5 b

0 0 1 -4 -5 01 0 0 1 0 50 1 0 0 1 40 0 0 1 1 9

x1 x2 x3 x4 x5 b

Existe solución degenerada el valor de una variable básica es igual a cero.



• Vamos a ver las iteraciones de este ejemplo:

10


1

0350190

21

0925160

41..

501150

43min

3

4321

4321

321

x

xxxx

xxxxas

xxx



1

0350190

21

0925160

41..

501150

43min

3

4321

4321

321

x

xxxx

xxxxas

xxx



• Y en esta iteración entra x6 y sale x4.• Nueva base: {5,6,7}


• Definición:

• Una solución degenerada es tal que hay variables básicas con valor cero

• ¿Cómo se forman soluciones degeneradas?

• Ocurre cuando se produce un “empate” en:

• Cuando eso ocurre, una variables básica quedará con valor = 0.

• También significa que el punto está sobredeterminado.

13


0:min ijij

i aab


• Un punto puede estar sobredeterminado.....

• Pero eso no implica que haya restricciones redundantes.....

• ¿Qué pasa en el punto (0,0,1)?

14


0,,11

321

32

31

xxxxxxx


• Es importante detectar que una solución es degenerada,

podríamos estar iterando eternamente.

• Un vértice degenerado puede ser óptimo o no.

15



• Si tenemos el siguiente problema:

• Al llevarlo a su forma estándar tenemos inmediatamente una base

factible inicial

16

¿CÓMO ENCONTRAR UNA BASE FACTIBLE INICIAL?:

1 2

1 2

1 2

4 1002 60

500 1,2j

x xx xx x

x j

21 3min xxz

5,...,10500060002100004

521

421

321

jxxxx

xxxxxx

j

21 3min xxz


• Pero si tenemos:

• Aquí no se ve una “identidad” que genere solución factible en

forma evidente

17


0,,,6293..

22min

4321

421

321

21

xxxxxxx

xxxasxx


• Ordenándolo:

• Re‐escribiéndolo:

18


4,...,106293..

22min

421

321

21

jxxxx

xxxasxxz

j

4,...,106293..

22min

421

321

21

jxxxx

xxxasxxz

j


• Vamos a agregar “variables artificiales”:

• ¿Es el mismo problema original?

• ¿Realmente necesito la 2 variables artificiales?

19


2,1,04,...,1,0

6293..

22min

2421

1321

21

itjx

txxxtxxxas

xxz

i

j


• Cambiemos la función objetivo:

• Minimizar la suma de las variables artificiales

• (y olvidaremos momentáneamente la FO original)

• ¿Qué significa esta FO?

20


2,1,04,...,1,0

6293..

0000min

2421

1321

214321

itjx

txxxtxxxas

ttxxxxw

i

j


• Esto se conoce como problema de FASE I

• Y lo que ya habíamos visto como SIMPLEX es la FASE II

• En general:

• Se transforma en:

21

FASE I

. .0

TMin c xs a Ax b

x

1

. ., 0

m

ii

Min t

s a Ax t bx t


• Ejemplo 1:

22

FASE I

2,1,04,...,1,0

6293..

0000min

2421

1321

214321

itjx

txxxtxxxas

ttxxxxw

i

j1 3 1 0 1 0 9

2 1 0 ‐1 0 1 6

0 0 0 0 1 1 0

‐2 ‐2 0 0 0 0 0

x1 x2 x3 x4 t1 t2

1 3 1 0 1 0 9

2 1 0 ‐1 0 1 6

‐3 ‐4 ‐1 1 0 0 ‐15

‐2 ‐2 0 0 0 0 0

x1 x2 x3 x4 t1 t2

Tableau inicial


• Se aplica el Simplex como sabemos

23

FASE I

2,1,04,...,1,0

6293..

0000min

2421

1321

214321

itjx

txxxtxxxas

ttxxxxw

i

j

0 1 2/5 1/5 2/5 ‐1/5 12/5

1 0 ‐1/5 ‐3/5 ‐1/5 3/5 9/5

0 0 0 0 1 1 0

0 0 2/5 ‐4/5 1 1 42/5

x1 x2 x3 x4 t1 t2

Tableau final

Solución óptima Fase I


• Con esa base inicial optimizamos en Fase II:

• Eliminar las variables artificiales del problema

• El tableau de inicio de fase II es:

• Iterar…….

24

FASE II

0 1 2/5 1/5 12/5

1 0 ‐1/5 ‐3/5 9/5

0 0 2/5 ‐4/5 42/5

x1 x2 x3 x4


• Ejemplo 2:

• Dado el problema inicial:

• El problema Fase I es:

25

MÉTODO DE LAS DOS FASES

1 2

1 2

1 2

1 2

2 2. . 2 2 9

8, 0

Min x xs a x x

x xx x

1 2

1 2 3 1

1 2 4 2

. . 2 2 980, 1,.., 40, 1,2

j

i

Min w t ts a x x x t

x x x tx jt i


• Tableau final (Fase I):

• ¿Qué significa esto...?

26


1 1 1/2 0 1/2 0 3

‐1 0 ‐1 ‐1 ‐1 1 2

1 0 1 0 1 0 ‐2

x1 x2 x3 x4 t1 t2


• Ejemplo 3:

• Dado el problema inicial:

• El problema Fase I es:

27


1 2

1 2 3

1 2

1 2 3

. . 11

2 2 20, 1,.., 4j

Max z x xs a x x x

x xx x x

x j

1 2 3

1 2 3 1

1 2 2

1 2 3 3

. . 11

2 2 2, 0, 1,.., 4; 1,..,3j i

Min w t t ts a x x x t

x x tx x x t

x t j i


• Tableau final (Fase I):

• ¿Qué significa esto...?

28


1 1 0 1 0 0 1

0 0 1 0 1 0 0

0 0 0 0 0 1 0

0 0 0 0 0 0 0

x1 x2 x3 t1 t2 t3


• El algoritmo SIMPLEX se aplica de la siguiente forma:• Se reduce el problema a forma estándar• Si no hay una base factible inicial evidente, se formula el problema

de FASE I• Se resuelve el problema de FASE I

• El resultado de FASE I puede ser:• El problema es infactible• El problema es factible, tiene filas redundantes y se eliminan• El problema es factible y tengo una base inicial

• Si el problema es factible, se rescata la base factible inicial y se inicia la

FASE II:

• Se resuelve el problema hasta que:• Se llegue a una solución óptima• Se detecte que el problema es no acotado 29



• Consideración final:

30

MATRIZ/TABLEAU

05_ind2209_alumno_15

Documents