• Author / Uploaded
• Diego Guzman

Citation preview

UNIVERSIDAD ESTATAL DE BOLIVAR FACULTAD DE CIENCIAS AGROPECUARA RECURSO NATURALES Y DEL AMBIENTE

ESCUELA DE INGENIERIA AGRINDUSTRIAL CICLO: 5 GRUPO 5

ASIGNATURA: INVESTIGACION OPERATIVA

INTEGRANTES: FREIRE CHAMORRO MARJORIE MIREYA LLUMIQUINGA GALEAS KERLY VANESSA TORRES CANDO TAHINA ELIZABETH

FECHA: 19/07/2020

TAREA 7 TRABAJO AUTONOMO TEMA: REALIZAR LOS EJERCICIOS DEL CAPITULO 5

SIMBOLOGIA CAPITULO 5 Los símbolos a la izquierda de algunos problemas (o de sus incisos) significan lo siguiente: D: El ejemplo de demostración que se presentó antes puede ser útil. I: Puede verificar algunos de sus trabajos por medio de los procedimientos listados anteriormente. Un asterisco en el número del problema indica que al fi nal del libro se da al menos una respuesta parcial.

Problemas 5.1-1. Considere el siguiente problema. Maximizar Z=3 x1 +2 x 2 sujeta a 2 x1 + x 2 ≤ 6 x 1+ 2 x 2 ≤ 6 x1 ≥ 0 x2 ≥ 0 Solución: a) Resuelva este problema en forma gráfica. Identifique las soluciones FEV en la gráfica encerrándolas en un círculo.

b) Identifique todos los conjuntos de dos ecuaciones de definición del problema. En cada uno obtenga (si existe) la solución correspondiente en el vértice y clasifíquela como solución FEV o como no factible. Definiendo

CP

Factible?

Solución

Variables

Ecuaciones

ecuaciones x 1=0

(0, 0)

x 2=0 x 1=0

(0, 6)

2 x1 + x 2=6 x 1=0 x 1+ 2 x 2=6 x 2=0 2 x1 + x 2=6 x 2=0 x 1+ 2 x 2=6 2 x1 + x 2=6

(0, 3) (3, 0) (6, 0) (2, 2)

si no Si Si No si

x 1+ 2 x 2=6

Básica

Indicadora

(0, 0, 6, 6)

s x1

x 3=6

(0, 6, 0, 6)

x2 x1

x 4 =6 x 2=6

(0, 3, 3, 0)

x2 x1

2 x1 + x 4 =6 x 2+ x3 =6

(3, 0, 0, 3)

x4 x2

2 x2 =6 2 x1 =6

(6, 0, -6, 0)

x3 x2

x 1+ x 4=6 2 x1 + x 3=6

(2, 2, 0, 0)

x4 x3

x 1=6 2 x1 + x 2=6

x4

x 1+ 2 x 2=6

c) Introduzca las variables de holgura con objeto de expresar las ecuaciones funcionales en la forma aumentada. Utilice estas variables de holgura para identificar la solución básica que corresponde a cada solución en un vértice, que haya encontrado en el inciso b). Maximizar Z=3 x1 +2 x 2 sujeta a 2 x1 + x 2 + x 3=6 x 1+ 2 x 2 + x 4=6 x1 , x2 , x3 , x4 ≥ 0 d) Haga lo siguiente en cada conjunto de dos ecuaciones de definición del inciso b): identifique las variables indicativas de cada ecuación de definición; escriba los conjuntos de ecuaciones del inciso c) después de eliminar estas dos variables indicativas (no básicas); luego use el último conjunto de ecuaciones para obtener las dos variables restantes (variables básicas); compare la solución básica que resulta con la solución básica correspondiente que obtuvo en el inciso c).

Definiendo

CP

Factible?

ecuaciones x 1=0

(0, 0)

x 2=0 x 1=0

si

(0, 6)

2 x1 + x 2=6 x 1=0 x 1+ 2 x 2=6 x 2=0 2 x1 + x 2=6 x 2=0 x 1+ 2 x 2=6 2 x1 + x 2=6

no

(0, 3)

Si

(3, 0)

Si

(6, 0)

No

(2, 2)

si

Solución

Variables

Ecuaciones

Básica

Indicadora

(0, 0, 6, 6)

s x1

x 3=6

(0, 6, 0, 6)

x2 x1

x 4 =6 x 2=6

(0, 3, 3, 0)

x2 x1

2 x1 + x 4 =6 x 2+ x3 =6

(3, 0, 0, 3)

x4 x2

2 x2 =6 2 x1 =6

(6, 0, -6, 0)

x3 x2

x 1+ x 4=6 2 x1 + x 3=6

(2, 2, 0, 0)

x4 x3

x 1=6 2 x1 + x 2=6

x 1+ 2 x 2=6 x4 x 1+ 2 x 2=6 e) Sin ejecutar el método símplex, utilice su interpretación geométrica (y la función objetivo) para identificar la trayectoria (secuencia de soluciones FEV) que seguiría para llegar a la solución óptima. En cada solución FEV identifique la decisión tomada para la siguiente iteración: i) cuál ecuación de definición se elimina y cuál se agrega; ii) cuál variable indicativa se elimina (variable básica entrante) y cuál se introduce (variable básica que sale). Pas

CPF Sol.'n

o

Ecuaciones de

Agregación de

Eliminación de

Agregación

definición eliminada

ecuación

variables

de variables

1

(0, 0)

x 1=0

2 x1 + x 2=6

x1

x3

2

(3, 2)

x 2=0

x 1+ 2 x 2=6

x2

x4

3

(2, 2) solución optima

5.1-2. Repita el problema 5.1-1 en el modelo del problema 3.1-6. Maximizar Z=10 x1 +20 x 2

sujeta a −x 1+ 2 x 2 ≤ 15 x 1+ x2 ≤12 5 x 1+3 x 2 ≤ 45 y x 1 ≥ 0 , x2 ≥ 0 Solución: a) Resuelva este problema en forma gráfica. Identifique las soluciones FEV en la gráfica encerrándolas en un círculo.

b) Identifique todos los conjuntos de dos ecuaciones de definición del problema. Definiendo ecuaciones x 1=0 x 2=0

CP (0, 0)

Factible ? Si

Solución Básica (0, 0, 15, 12,45)

Variables Indicadoras x1 x2

Ecuaciones x 3=15 x 4 =12

x 1=0 −x 1+ 2 x 2=15

(0, 0.75)

si

(0, 7.5, 0, 4.5, 22.5)

x1 x3

x 1=0 x 1+ x2=12

(0, 12)

No

(0, 12, -9, 0, 9)

x1 x4

x 1=0 5 x 1+3 x 2=45

(0, 15)

No

(0, 15, -15, -3, 0)

x1 x5

x 2=0 −x 1+ 2 x 2=15

(-15, 0)

No

(-15, 0, 0, 3, 120)

x2 x3

x 2=0 x 1+ x2=12

(12, 0)

No

(12, 0, 27, 0, -15)

x2 x4

x 2=0 5 x 1+3 x 2=45

(9, 0)

Si

(9, 0, 24, 3, 0)

x2 x5

x 1+ x2=12 −x 1+ 2 x 2=15

(3, 9)

Si

(3, 9, 0, 0, 3)

x3 x4

5 x 1+3 x 2=45 −x 1+ 2 x 2=15

(45/13, 120/13)

No

(45/13, 120/13, 0, -19/13, 0)

x3 x5

x 1+ x2=12 5 x 1+3 x 2=45

(4.5, 7.5)

Si

(4.5, 7.5, 3.5, 0, 0)

x4 x5

x 5=45 2 x2 =15 x 2+ x 4=12 3 x 2+ x 5=45 2 x2 + x 3=15 x 2+ x 4=12 3 x 3=45 2 x2 + x 3=15 x 2+ x 4=12 3 x 3=45 x 1+ x 4=12 −x 1=15 5 x 1+ x 5=45 x 1=12 −x 1+ x3 =15 5 x 1+ x 5=45 x 1=12 −x 1+ x3 =15 5 x 1+ x 5=45 x 1+ x 4=12 −x 1+ x3 =15 5 x 1+3 x 2 + x5 =45 x 1+ x2 + x 4 =12 −x 1+ 2 x 2=15 5 x 1+3 x 2=45 x 1+ x2=12 −x 1+ 2 x 2 + x 4=15 5 x 1+3 x 2=45

c) Introduzca las variables de holgura con objeto de expresar las ecuaciones funcionales en la forma aumentada. Utilice estas variables de holgura para identificar la solución básica que corresponde a cada solución en un vértice, que haya encontrado en el inciso b). Maximizar Z=10 x1 +20 x 2 sujeta a

−x 1+ 2 x 2 + x 3=15 x 1+ x2 + x 4 =12 5 x 1+3 x 2 + x5 =45

x1 , x2 , x3 , x4 , x5 ≥ 0 d) Haga lo siguiente en cada conjunto de dos ecuaciones de definición del inciso b): identifique las variables indicativas de cada ecuación de definición; escriba los conjuntos de ecuaciones del inciso c) después de eliminar estas dos variables indicativas (no básicas); luego use el último conjunto de ecuaciones para obtener las dos variables restantes (variables básicas); compare la solución básica que resulta con la solución básica correspondiente que obtuvo en el inciso c). Definiendo ecuaciones x 1=0 x 2=0

CP

Solución Básica

(0, 0)

Factible ? Si

x 1=0 −x 1+ 2 x 2=15

(0, 0.75)

si

(0, 7.5, 0, 4.5, 22.5)

x1 x3

x 1=0 x 1+ x2=12

(0, 12)

No

(0, 12, -9, 0, 9)

x1 x4

x 1=0 5 x 1+3 x 2=45

(0, 15)

No

(0, 15, -15, -3, 0)

x1 x5

x 2=0 −x 1+ 2 x 2=15

(-15, 0)

No

(-15, 0, 0, 3, 120)

x2 x3

x 2=0 x 1+ x2=12

(12, 0)

No

(12, 0, 27, 0, -15)

x2 x4

x 2=0 5 x 1+3 x 2=45

(9, 0)

Si

(9, 0, 24, 3, 0)

x2 x5

(0, 0, 15, 12,45)

Variables Indicadoras x1 x2

Ecuaciones x 3=15 x 4 =12 x 5=45 2 x2 =15 x 2+ x 4=12 3 x 2+ x 5=45 2 x2 + x 3=15 x 2+ x 4=12 3 x 3=45 2 x2 + x 3=15 x 2+ x 4=12 3 x 3=45 x 1+ x 4=12 −x 1=15 5 x 1+ x 5=45 x 1=12 −x 1+ x3 =15 5 x 1+ x 5=45 x 1=12 −x 1+ x3 =15

x 1+ x2=12 −x 1+ 2 x 2=15

(3, 9)

Si

(3, 9, 0, 0, 3)

x3 x4

5 x 1+3 x 2=45 −x 1+ 2 x 2=15

(45/13, 120/13)

No

(45/13, 120/13, 0, -19/13, 0)

x3 x5

x 1+ x2=12 5 x 1+3 x 2=45

(4.5, 7.5)

Si

(4.5, 7.5, 3.5, 0, 0)

x4 x5

5 x 1+ x 5=45 x 1+ x 4=12 −x 1+ x3 =15 5 x 1+3 x 2 + x5 =45 x 1+ x2 + x 4 =12 −x 1+ 2 x 2=15 5 x 1+3 x 2=45 x 1+ x2=12 −x 1+ 2 x 2 + x 4=15 5 x 1+3 x 2=45

e) Sin ejecutar el método símplex, utilice su interpretación geométrica (y la función objetivo) para identificar la trayectoria (secuencia de soluciones FEV) que seguiría para llegar a la solución óptima. En cada solución FEV identifique la decisión tomada para la siguiente iteración: i) cuál ecuación de definición se elimina y cuál se agrega; ii) cuál variable indicativa se elimina (variable básica entrante) y cuál se introduce (variable básica que sale). Paso CPF Sol.'n

Ecuaciones de

Agregación de

Eliminación de

Agregación

definición eliminada

ecuación

variables

de variables

1

(0, 0)

x 2=0

−x 1+ 2 x 2=15

x2

x3

2

(0, 7.5)

x 1=0

x 1+ x2=12

x1

x4

3

(3, 9) solución optima

5.1-3. Considere el siguiente problema. Maximizar Z=5 x 1+ 8 x 2 Sujeta a 4 x1 +2 x 2 ≤ 80 −3 x 1+ x 2 ≤ 4 −x 1+ 2 x 2 ≤ 20

4 x1 −x2 ≤ 40 y x1 ≥ 0 , x2 ≤ 0 a) Resuelva este problema en forma gráfica. Identifique las soluciones FEV y señálelas en la gráfica.

Solución óptima ( x 1 , x 2 )=( 12,16 ) y Z =18

b) Desarrolle una tabla que muestre cada solución FEV y las ecuaciones de definición correspondientes, la solución BF y las variables no básicas. Calcule Z de cada solución y utilice sólo esta información para identificar la solución óptima. El punto de la esquina (12,16) tiene el mejor valor objetivo 188, Así es óptimo

CPF Sol.'n

Definiendo Ecuaciones

BF Solución

NB

Z

Var.'s (0,0)

(0,4) (2.4,11.2) (12,16) (13.3,13.3) (12,0)

x 1=0 , x 2=0 x 1=0, -3 x 1+ x 2=4 -3 x 1+ x 2=4 ,−x1 +2 x 2=20 - x 1+ 2 x 2=20,4 x 1 +2 x 2=80 4 x 1+2 x2 =80,4 x 1−x 2=40 4 x 1−x 2=40 , x 2=0

(0,0,80,4,20,40) (0,4,72,0,12,44) (2.4,11.2,48,0,0,41.6) (12,16,0,24,0,8) (13.3,13.3,0,16.7,6.7,0) (10,0,40,34,30,0)

x1 , x2 x1 , x4 x 4 , x5 x3 , x5 x3 , x6 x2 , x6

0 32 101.6 188 1773.3 50

c) Desarrolle la tabla correspondiente de las soluciones no factibles en los vértices, etc. Además, identifique los conjuntos de ecuaciones de definición y las variables no básicas que no conducen a una solución. Todos los conjuntos dan una solución. CP Infeas. Sol.

Definiendo Ecuaciones

Infeas Básicas. Soluciones

NB Var.'s

()

-3 x 1+ x2=4, x 2=0

x2 , x4

(-20,0) (0,40) (0,10) (7.2,25.6) (44,136) 100 120 , ( ) 7 7 (20,0) (0,-40)

- x 1+ 2 x 2=20 , x 1=0 4 x 1+ 2 x 2=80 , x 1=0 - x 1+ 2 x 2=20 , x 1=0 4 x 1+ 2 x 2=80 ,−3 x1 + x 2=4 -3 x 1+ x2=4,4 x 1−x 2=40 4 x 1−x 2=40,- x 1+ 2 x 2=20

4 1 2 1 ( , 0,85 , 0,18 , 45 ) 3 3 3 3 (-20,0,160.-56,0,120) (0,40,0,-36, -60,80) (0,10,60, -6,0,50) (7.2,25.6,0,0 -24,36.8) (44,136, -368,0, -24,36.8) 100 120 80 208 , ,− , ,0,0 )) ( 7 7 7 7 (20,0,0,64,40,-40) (0, -40, 160, 44,100,0)

4 x 1+ 2 x 2=80, x 2=0 4 x 1−x 2=40 , x 1=0

5.1-4. Considere el siguiente problema Maximizar Z=2 x1 −x2 + x 3 Sujeta a

x2 , x5 x1 , x3 x1 , x5 x1 , x5 x3 , x4 x 4 , x6 x2 , x3 x1 , x6

3 x 1+ x 2 + x 3 ≤ 60 x 1−x 2+ 2 x 3 ≤ 10 x 1 + x 2−x 3 ≤ 20 y x 1 ≥ 0 , x2 ≥ 0 , x 3 ≥0 , Después de introducir las variables de holgura y de realizar una iteración completa del método simplex se obtiene la siguiente tabla simplex. Coeficiente de: Variable Iteración

1

básica

Lado derecho

Ec Z

X1

X2

X3

X4

X5

X6

-1

3

0

2

0

20

4 -5

1

-3

0

30

2

0

1

0

10

2 -3

0

-1

1

10

Z

(0)

1

0

X4

(1)

0

0

X1

(2)

0

1

X6

(3)

0

0

-1

a) Identifique la solución FEV que se obtuvo mediante la iteración ( x 1 , x 2 , x 3 ¿=( 10 ,0 , 0 , 0) b) Identifique las ecuaciones de frontera de restricción que definen la solución FEV x 2=0 , x 3=0 , x1 −x2 +2 x 3=10 5.1-5. Considere el problema de programación lineal de tres variables que se muestra en la fi gura 5.2.

a) Construya una tabla similar a la 5.1 que muestre el conjunto de ecuaciones de definición de cada solución FEV. b) ¿Cuáles son las ecuaciones de definición de la solución no factible en el vértice (6, 0, 5)? c) Identifique uno de los sistemas de tres ecuaciones de frontera de restricción que no conduzca a una solución FEV ni a una solución no factible en un vértice. Explique por qué ocurre esto en ese Sistema. Solución a) Construya una tabla similar a la 5.1 que muestre el conjunto de ecuaciones de definición de cada solución FEV.

CPF Sol.'n

Definiendo Ecuaciones x 1=0 , x 2=0 , x3 =0 x 1=4 , x 2=0 , x 3=0 x 1=4 , x 1 + x 2=6 , x 3=0 x 2=4 , x 1 + x 2=6 , x 3=0 x 1=0. x 2=4 , x 3=0 x 1=0 , x 2=4 ,−x 1+ 2 x 3=4 x 1+ x2=6 , x 2=4 ,−x 1+ 2 x 3=4 x 1+ x2=6 , x 1=4 ,−x1 +2 x 3=4 x 2=0 , x 1=4 ,−x 1 +2 x3 =4 x 2=0 , x 1=0 ,−x 1 +2 x3 =4

(0,0,0) (4,0,0) (4,2,0) (2,4,0) (0,4,0) (0,4,2) (2,4,3) (4,2,4) (4,0,4) (0,0,2)

b) ¿Cuáles son las ecuaciones de definición de la solución no factible en el vértice (6, 0, 5)? x 1+ x2=6 , x 2=4 ,−x1 +2 x 3=4 c) Identifique uno de los sistemas de tres ecuaciones de frontera de restricción que no conduzca a una solución FEV ni a una solución no factible en un vértice. Explique por qué ocurre esto en ese sistema.

x 1=4 . x 1=0 , x 2=0 → Sistema Inconsistente

5.1-6. Considere el siguiente problema.

Minimizar Z=8 x 1+5 x 2 , Sujeto a −3 x 1+2 x 2 ≤ 30 2 x1 + x 2 ≥ 50 x 1+ x2 ≥30 y x1 ≥ 0

x2 ≥

a) Identifique los 10 conjuntos de ecuaciones de definición del problema. Para cada uno, obtenga (si existe) la solución correspondiente en el vértice y clasifíquela como solución FEV o como solución no factible en un vértice.

b) En cada solución en un vértice, obtenga la solución básica correspondiente y su conjunto de variables no básicas.

Solución a) y b)

Definiendo Ecuaciones

CP

Factible Solución Básica

NB Var.'s

x 1=0 , x 2=0

(0, 0)

NO

(0, 0, 30, -50, -30)

x1 , x2

x 1=0 ,−3 x 1 +2 x2 =30

(0, 15)

NO

(0, 15, 0, -35, -15)

x1 , x3

x 1=0 , 2 x 1 + x 2=50

(0, 50)

NO

(0, 50, -70, 0, 20)

x1 , x4

x 1=0 , x 1+ x 2=30

(0, 30)

NO

(0, 30, -30, -20,0)

x1 , x5

x 2=0 ,−3 x 1 +2 x2 =30

(-10, 0)

NO

(-10, 0, 0, -70, -40)

x2 , x3

x 2=0 , 2 x 1 + x 2=50

(25, 0)

NO

(25, 0, 105, 0, -5)

x2 , x4

x 2=0 , x 1+ x 2=30

(30, 0)

SI

(30, 0, 120, 10, 0)

x2 , x5

−3 x 1+2 x 2=30 , 2 x 1 + x 2=50

(10, 30)

SI

(10, 30, 0, 0, 10)

x3 , x4

−3 x 1+2 x 2=30 , x1 + x 2=30

(6, 24)

NO

(6, 24, 0, -14, 0)

x3 , x5

2 x2 + x 2=50 , x 1+ x 2=30

(20, 10)

SI

(20, 10, 70, 0, 0)

x 4 , x5

5.1-7. Reconsidere el modelo del problema 3.1-5. a) Identifique los 15 conjuntos de ecuaciones de definición de este problema. En cada uno, obtenga (si existe) la solución correspondiente en un vértice y clasifíquela como solución FEV o como solución no factible en un vértice.  Respuest a

  definiendo ecuaciones

 CP

  solución básica

NB Var‘s

x 1=0 , x 2=0

 (0.0)

 SI

 (0,0,10,60,18,44)

   x1 , x2

  x 1=0 , x 2=10

 (0.10)

 (0,10,0,10,8,34)

 x1 , x3

  x 1=0 , 2 x 2 +5 x 2=60

  (0.12)

SI    NO

 (0,12, -2,0,6,32)

 x1 , x4

  x 1=0 , x 1+ x 2=18

  (0.18)

 (0,18, -8, -30,0,26)

 x1 , x5

  x 1=0 , 3 x1 + x 2=44

  (0.44)

NO   NO  

 (0,44, -34, -160-26,0)

 x1 , x6

  x 2=0 , x 2=10   x 2=0 , 2 x 1 +5 x 2=60

Sin solucion     (30.0)

 (30,0,10,0,-12,-46)

 x2 , x3

  x 2=0 , x 1+ x 2=18

  (18.0)

 (18,0,10,24,0,-10)

   x 2 , x 4

  x 2=0 , 3 x1 + x 2=44

 (14.67,0)

 (14.67,0,10,30.67.3.33,0)

   x 2 , x 5

  x 2=10 , 2 x 1 +5 x2 =60

 (5,10)

 (5,10,0,0,3,19)

   x 2 , x 6

  x 2=10 , x1 + x 2=18

 (8.10)

NO   NO   SI   SI   NO  

 (8,10,0,-6,0,10)

   x 3 , x 4

x 2=10 , 3 x 1 + x 2=44  2 x1 +5 x 2=60 , x1 + x 2=18

 (11.33,10)  (10.8)

 2 x1 +5 x 2=60 , 3 x 1 + x 2=44

 (12.31,7.08 )

  2 x1 +5 x 2=18 , 3 x 1 + x 2=44

 (13.5)

NO   SI   NO   SI  

 (11.33,10,0, 3.33,0)

-12.67,-

   x 3 , x 5

 (10,8,2,0,0,6)

   x 3 , x 6

 (12.31,7.08,2.92,0,1.38,0)

   x 4 , x5

 (13,5,5,9,0,0)

   x 5 , x 6

b) En cada solución en un vértice obtenga la solución básica correspondiente y su conjunto de variables no básicas.  Respuest a

  definiendo ecuaciones

 CP

x 1=0 , x 2=0

 (0.0)

 SI

 (0,0,10,60,18,44)

   x1 , x2

  x 1=0 , x 2=10

 (0.10)

 (0,10,0,10,8,34)

 x1 , x3

  x 1=0 , 2 x 2 +5 x 2=60

  (0.12)

SI    NO

 (0,12, -2,0,6,32)

 x1 , x4

  x 1=0 , x 1+ x 2=18

  (0.18)

 (0,18, -8, -30,0,26)

 x1 , x5

  x 1=0 , 3 x1 + x 2=44

  (0.44)

NO   NO  

 (0,44, -34, -160-26,0)

 x1 , x6

  x 2=0 , x 2=10   x 2=0 , 2 x 1 +5 x 2=60

Sin solucion     (30.0)

 (30,0,10,0,-12,-46)

 x2 , x3

  x 2=0 , x 1+ x 2=18

  (18.0)

 (18,0,10,24,0,-10)

   x 2 , x 4

  x 2=0 , 3 x1 + x 2=44

 (14.67,0)

 (14.67,0,10,30.67.3.33,0)

   x 2 , x 5

  x 2=10 , 2 x 1 +5 x2 =60

 (5,10)

 (5,10,0,0,3,19)

   x 2 , x 6

  x 2=10 , x1 + x 2=18

 (8.10)

NO   NO   SI   SI   NO  

 (8,10,0,-6,0,10)

   x 3 , x 4

x 2=10 , 3 x 1 + x 2=44  2 x1 +5 x 2=60 , x1 + x 2=18

 (11.33,10)  (10.8)

NO   SI  

  solución básica

 (11.33,10,0, 3.33,0)  (10,8,2,0,0,6)

NB Var‘s

-12.67,-

   x 3 , x 5    x 3 , x 6

 2 x1 +5 x 2=60 , 3 x 1 + x 2=44

 (12.31,7.08 )

  2 x1 +5 x 2=18 , 3 x 1 + x 2=44

 (13.5)

NO   SI  

 (12.31,7.08,2.92,0,1.38,0)

   x 4 , x5

 (13,5,5,9,0,0)

   x 5 , x 6

5.1-8. Cada una de las siguientes afirmaciones es cierta en casi todas las circunstancias, pero no siempre. En cada caso, indique cuándo no lo es y por qué.

a) La mejor solución FEV es una solución óptima. Si la región factible no tiene límites, entonces puede que no haya una solución óptima. b) Una solución óptima es una solución FEV. Puede haber múltiples soluciones óptimas, en cuyo caso el promedio ponderado de cualquier Las soluciones óptimas de CPF también son óptimas.

c) Una solución FEV es la única solución óptima si ninguna de las soluciones FEV adyacentes es mejor (según la medida del valor de la función objetivo). Una solución de CPF adyacente puede tener un valor de función objetivo igual, entonces todos los puntos que se encuentran en el segmento de línea entre estos dos puntos de esquina son óptimos. 5.1-9. Considere la forma original (antes de aumentar) de un problema de programación lineal con n variables de decisión (cada una con una restricción de no negatividad) y m restricciones funcionales. Diga si las siguientes afirmaciones son falsas o verdaderas y después justifique su respuesta con referencias específicas al material del capítulo (incluya cita de la página). a) Si una solución factible es óptima, debe ser una solución FEV. FALSO. Propiedad 1: 

Si hay exactamente una solución óptima, entonces debe ser una solución CPF.



Si hay múltiples soluciones óptimas, entonces al menos dos de ellas deben ser soluciones de CPF adyacentes. Una solución óptima que no es una solución CPF puede ser obtenido al tomar una combinación convexa de dos soluciones óptimas de CPF.

b) El número de soluciones FEV es al menos.

( m+ n ) m !n! FALSO.El número de soluciones CPF es como máximo.

( m+n ) ! = (m+n n ) m !n! c) Si una solución FEV tiene soluciones adyacentes que son mejores (de acuerdo con el valor de Z), entonces una de estas soluciones FEV adyacentes debe ser óptima FALSO. La solución de CPF adyacente que tiene un mejor valor de función objetivo que la solución inicial de CPF puede ser adyacente a otra solución de CPF que tiene un par Mejor valor de la función objetivo.

5.1-10. Diga si las siguientes afirmaciones sobre problemas de programación lineal son falsas o verdaderas y después justifique su respuesta. a) Si una solución factible es óptima pero no FEV, existe un número infinito de soluciones óptimas. CIERTO. Por la Propiedad 1. 

Debe haber múltiples soluciones, ya que esta solución óptima no es una solución CPF. Pero entonces, debe haber infinitas soluciones óptimas, a saber, cualquier combinación convexa de soluciones óptimas.

b) Si el valor de la función objetivo es igual en dos puntos factibles diferentes x* y x**, entonces todos los puntos sobre el segmento de recta que conecta a x* y x** son factibles y Z tiene el mismo valor en todos ellos. CIERTO. Cualquier punto en la línea segmento conectando x ¿ y x ¿∗¿ ¿ puede expresarse como x=α x ¿ ¿ con ∝ ϵ [ 0.1 ] . ambas x* y x** tener el valor objetivo óptico Z¿ El valor de la función objetivo en x es.

Z=c T ¿ Entonces xes óptimo. Como la región factible es convexa, cualquier punto es factible. c) Si el problema tiene n variables (antes de aumentar), entonces la solución simultánea de cualquier conjunto de n ecuaciones de frontera de restricción es una solución FEV. FALSO. La solución simultánea de cualquier conjunto de ecuaciones de límite de restricción puede ser inviable o incluso puede no existir. 5.1-11. Considere la forma aumentada de los problemas de programación lineal que tienen soluciones factibles y una región factible acotada. Diga si cada una de las afirmaciones siguientes es falsa o verdadera y después justifique su respuesta con una referencia a afirmaciones específicas del capítulo (incluya cita de la página). a) Debe haber al menos una solución óptima. CIERTO. Si no hay soluciones óptimas, entonces el problema es inviable o el valor objetivo no tiene límites (Capítulo 3). El primero no es el caso por suposición del problema. También por suposición nuevamente, la región factible está limitada, por lo que el objetivo el valor está limitado, por lo que este último no puede ser el caso. Por lo tanto, debe haber al menos uno solución optima. b) Una solución óptima debe ser una solución BF. FALSO. Si una solución es óptima, no necesita ser una solución BF. Una combinación convexa de dos soluciones BF óptimas es óptimo, aunque no sea una solución BF. Esto sigue de la Propiedad 1, ya que las soluciones BF son soluciones CPF. c) El número de soluciones BF es finito. CIERTO. Como las soluciones BF corresponden a las soluciones CPF, esto se deduce directamente de Propiedad 2. 5.1-12. Reconsidere el modelo del problema 4.6-9. Ahora se sabe que las variables básicas de la solución óptima son x2 y x3. Use esta información para identificar un

sistema de tres ecuaciones de frontera de restricción cuya solución simultánea sea esta solución óptima. Resuelva este sistema de ecuaciones para obtener esa solución. x 1=0,2 x1 + x 2 +3 x3 =60,3 x 1 +3 x 2+5 x 3=120 ⟹ ( x 1 , x 2 , x 3 )=( 0,15,15 ) 5.1-13. Reconsidere el problema 4.3-6. Ahora use la información dada y la teoría del método símplex para identificar un sistema de tres ecuaciones de frontera de restricción ( en x 1 , x 2 , x 3 ) cuya solución simultánea sea la solución óptima, sin aplicar el método símplex. Resuelva el sistema de ecuaciones para encontrar la solución óptima. SOLUCION: Ya que x 2> 0 y x 3 >0 , x 2=0 y x 3=0 no puede ser parte de las tres ecuaciones de límite, por lo que las ecuaciones de límite son x 1=0 , 2 x 1 + x 2+ x3 =20 ,3 x 1+ x2 +2 x 3=30 Entonces, la solución óptima es ( x 1 , x 2 , x 3 )= ( 0,10,10 )

5.1-14. Considere el siguiente problema. Maximizar

Z=2 x 1 +2 x2 +2 x 3

Sujeta a 2 x1 + x 2 +2 x 3 ≤ 4 x 1 + x2 + x 3 ≤ 3 Y x 1 ≥ 0 , x2 ≥ 0 , x 3 ≥0. Sean x 4 y x 5 las variables de holgura de las restricciones funcionales respectivas. Comience con estas dos variables como las variables básicas de la solución BF inicial, y se obtiene la información de que el método símplex procede de la siguiente manera para obtener la solución óptima en dos iteraciones: 1) en la iteración 1, la variable básica entrante es x 3 y la variable básica saliente es x 4 ; 2) en la iteración 2, la variable básica entrante es x 2 y la que sale es x 5. a) Desarrolle un dibujo de tres dimensiones de la región factible del problema y muestre la trayectoria que sigue el método símplex. b) Dé una interpretación geométrica de las razones por las cuales el método símplex sigue esta trayectoria. c) En cada una de las dos aristas de la región factible por las que se desplaza el método símplex, dé la ecuación de las dos fronteras de restricción sobre las que

está y después la ecuación de la frontera de restricción adicional en cada punto extremo. d) Identifique el conjunto de ecuaciones de definición de las tres soluciones FEV (incluso la inicial) que obtuvo por el método símplex. Use las ecuaciones de definición para obtener estas soluciones. e) En cada solución FEV que obtuvo en el inciso d), proporcione la solución BF correspondiente y su conjunto de variables no básicas. Explique en qué forma estas variables no básicas identifican las ecuaciones de definición del inciso

a)

x3 3 2

Camino seguido largo simplex

1

(0,2,1)

10

2 3 4 5

2

3

4

5

x1

1

Solución Optima

x2

x 1+ x2 + x 3=3

2 x 1+ x2 +2 x 3=4

( x 1 , x 2 , x 3 ¿=( 0 , z , 1 )Solución Óptima con z=7

b) El método simplex sigue este camino porque se mueve a lo largo de los bordes elegidos proporciona el mayor aumento en el valor objetivo para un movimiento de unidad en el elegido dirección entre todos los bordes posibles en cada punto de vértice / decisión. c) Bord e 1 2

Ecuaciones límite restricción x 2=0 , x 1=0 2 x1 + x 2 +2 x 3=4 , x 1=0

de Punts finales

( 0,0,0 ) , ( 0,0,2 ) ( 0,0,2 ) , ( 0,2,1 )

Restricciones Adicionales x 3=0,2 x 1+ x 2 +2 x3 =4 x 2=0 , x 1+ x 2 + x 3=3

d – e) CP ( 0,0,0 ) ( 0,0,2 ) ( 0,2,1 )

Definiendo Ecuaciones x 1=0 , x 2=0 , x1 =0 x 1=0 , x 2=0 , 2 x 1 + x 2 +2 x3 =4 x 1=0 , 2 x 1 + x 2 +2 x 3=4 , x 1 + x 2+ x 3 =3

Solución BF ( 0,0,0,4,3 ) ( 0,0,2,0,1 ) ( 0,0,2,0,1 )

NB Var x1 , x2 , x3 x1 , x2 , x4 x 1 , x 4 , x5

Las variables no básicas que tienen valor cero son equivalentes a las variables indicadoras. Indican que sus restricciones de desigualdad asociadas son en realidad igualdades. Las igualdades asociadas son las ecuaciones definitorias.

5.1-15. Considere el siguiente problema. Maximizar

Z=3 x1 + 4 x 2+2 x 3

Sujeta a x 1+ x2 + x 3 ≤ 20 x 1+ 2 x 2 + x 3 ≤ 30 Y x 1 ≥ 0 , x2 ≥ 0 , x 3 ≥0. Sean x 4 y x 5las variables de holgura de las restricciones funcionales respectivas. Si se inicia con estas dos variables como variables básicas de la solución BF inicial, se recibe la información de que el a) ¿Cuál es la variable básica entrante? b) ¿Cuál es la variable básica que sale? c) ¿Cuál es la nueva solución BF? a)

x3 30

x 1+ 2 x 2 + x 3=30 Camino seguido por el simplex

20 0

x 1+ 2 x 2 + x 3=20 x1 10

30

20

40

10 20

x2

( 10,10,10 ) Solución Optima

30 ( x 1 , 2 x2 , x3 ¿=( 10,10,0 ) Optimo con z=70

b) El método simplex sigue este camino porque moverse a lo largo de los bordes elegidos proporciona el mayor aumento en el valor objetivo para un movimiento de unidad en la dirección elegida entre todos los bordes posibles en cada punto de vértice / decisión. Bord e 1 2

Ecuaciones límite restricción x 1=0 , x 3=0 x 3=0 , x 1+ 2 x 2+ x3 =30

de Puntos finales

( 0,0,0 ) , ( 0,15,0 ) ( 0,15,0 ) , ( 10,10,0 )

Restricciones Adicionales x 2=0 , x 1+2 x 2+ x3 =30 x 1=0 , x 1+ x 2 + x 3=20

d – e) CP ( 0,0,0 ) ( 0,0,2 ) ( 0,2,1 )

Definiendo Ecuaciones x 1=0 , x 2=0 , x3 =0 x 1=0 , x 3=0 , x1 +2 x 2 + x 3=30 x 3=0 , x 1+ 2 x 2 + x 3=30 , x 1+ x2 + x 3=¿ 20

Solución BF ( 0,0,0,20,30 ) ( 0,15,0,5,0 ) ( 10,10,0,0,0 )

NB Var x1 , x2 , x3 x1 , x3 , x5 x3 , x4 , x5

Las variables no básicas que tienen valor cero son equivalentes a las variables indicadoras. Indican que sus restricciones de desigualdad asociadas son en realidad igualdades. Las igualdades asociadas son las ecuaciones definitorias.

Ejercicio 5.1-16. Después de observar la figura 5.2, explique por qué la propiedad 1 b de las soluciones FEV se cumple en este problema si tiene la siguiente función objetivo. a) Maximizar Z=x 3 b) Maximizar Z=−x 1+ 2 x 3 a) Cuando el objetivo es maximizar Z=x 3 , ambos puntos de esquina ( 4,2,4 ) y ( 4,0,4 ) Son óptimos, con Z¿ =4. b) Cuando el objetivo es maximizar Z=−x 1+ 2 x 3todos los puntos de esquina ( 0,0,2 ) , ( 4,0,4 ) , ( 4,2,4 ) , ( 2,4,3 ) y ( 0,4,2 )Son óptimos, con Z¿ =4. Ejercicio 5.1-17 Considere el problema de programación lineal de tres variables que se muestra en la fi gura 5.2. a) Explique en términos geométricos por qué el conjunto de soluciones que satisfacen cualquier restricción individual es convexo según se define en el apéndice 2. -

Geométricamente, cada restricción es un plano y los puntos que son factibles para un determinado. La desigualdad forma un medio espacio, el segmento de la línea definido por dos posibles, los puntos deben estar completamente en el lado factible del avión y, por lo tanto, todo el punto debe estar completamente en el lado factible del avión y, por lo tanto, todo el punto en el segmento de línea es factible, lo que complica que el conjunto de soluciones para cualquier restricción es un conjunto convexo.

b) Utilice la conclusión del inciso a) para explicar por qué la región factible completa (el conjunto de soluciones que satisfacen de manera simultánea todas las restricciones) es un conjunto convexo. -

Debido a que los puntos en la región factible del problema satisfacen todas las restricciones simultáneamente, debe darse el caso de que, para dos puntos posibles, los puntos en la línea el segmento que los une también debe satisfacer cada restricción de (a). Por lo tanto, el conjunto de las soluciones que satisfacen todas las restricciones simultáneamente es un conjunto convexo.

Ejercicio 5.1-18

Suponga que el problema de programación lineal de tres variables que se presenta en la fi gura 5.2 tiene la función objetivo Maximizar Z 5 3x1 1 4x2 1 3x3. Sin emplear el álgebra del método simplex, aplique sólo el razonamiento geométrico (incluso la elección de la arista que proporcione la tasa máxima de incremento de Z) para determinar y explicar la trayectoria que seguiría en la fi gura 5.2 desde el origen hasta la solución óptima. Para maximizar Z=3 x1 + 4 x 2+3 x 3 comenzando en el origen (0,0,0), una primera

-

elige madurarse a (0,4,0) porque este borde ofrece la mejor tasa de mejora entre todos los bordes en el origen. Del borde que aumenta la función objetivo más rápido es el que se conecta a cualquiera (0,4,2) o (2,4,0) de cualquiera de estos, el borde que da la mejor tasa de aumento se conecta a (2,4,3) entonces, la única ventaja que proporciona una mejora en la conexión a la solución óptima ( 4,2,4).

5.1-19. Considere el problema de programación lineal de tres variables que se muestra en la fi gura 5.2. a) Construya una tabla similar a la 5.4 que muestre las variables indicativas de cada ecuación de frontera de restricción y cada restricción original. Restricción original

Ecuación de límite

Variable de indicación

x 1 ≥0

x 1=0

x1

x 2 ≥0

x 2=0

x2

x 3 ≥0

x 3=0

x3

x 1+ x

x 1=¿4 ¿

x4

x 2+ x

x 2=4

x5

x 1=x 2=6

x6

−x 1+ 2 x 5=4

x7

4 =4

5=4

x 1+ x

2+ ¿

x 6+ ¿=6 ¿ ¿

−x 1+ 2 x 3 + x 7=¿4 ¿

b) Para la solución FEV (2, 4, 3) y sus tres soluciones FEV adyacentes (4, 2, 4), (0, 4, 2) y (2, 4, 0) construya una tabla similar a la 5.5 que muestre las ecuaciones de definición correspondientes, las soluciones BF y las variables no básicas.

CPF Sol.

Definiendo Ecuaciones

BF Solución

NB Var.

(2,4,3)

x 1+ x2=6 x2=4 , x 1+ 2 x 3=4

( 2,4,3,2,0,0,0 )

x5 , x6 , x7

(4,2,4)

x 1+ x2=6−x 1 +2 x 3 =4 x 1=4

( 4,2,4,0,2,0,0 )

x 4 , x6 , x 7

(0,4,2)

x 1=0 x 2=4−x 1 +2 x3 =4

( 0,4,2,0,2,0 )

x1 , x5 , x7

(2,4,0)

x 3=0 x 1+ x2 =6 x2 =4

( 2,4,0,2,0,0,6 )

x3 , x5 , x6

c) Utilice los conjuntos de ecuaciones de definición del inciso b) para demostrar que (4, 2, 4), (0, 4, 2) y (2, 4, 0) son en realidad adyacentes a (2, 4, 3), pero que ninguna de estas tres soluciones FEV son adyacentes entre sí. Después utilice los conjuntos de variables no básicas del inciso b) para demostrar lo mismo. Debido a que los conjuntos de ecuaciones definitorias de ( 4,2,4 ) , ( 0,4,2 ) en (2,4,0) difieren del conjunto de ecuaciones definitorias de (2,4,3) por una sola ecuación, son adyacentes a (2,4,3) Por otro lado, los conjuntos de ecuaciones definitorias de (4,2,4) (0,4,2) difieren en más de una ecuación, no son adyacentes entre sí. Lo mismo la declaración es verdadera si sustituimos "variables no básicas" por "definir ecuaciones y variable" para ecuación". 5.1-20. La fórmula de la recta que pasa por (2, 4, 3) y (4, 2, 4) de la fi gura 5.2 se puede escribir como.

( 2,4,3 , ) +α [ ( 4,2,4 )− ( 2.4 .3 )=( 2,4,3 ) + α (2 ,−2,1) donde 0 # _ # 1 para el segmento de recta que une estos dos puntos. Después de aumentar las restricciones respectivas con las variables de holgura x4, x5, x6, x7 esta fórmula se convierte en. ( 2,4,3,0,0,0 ) +α (−2,2,1 ,−2,2,0,0) Utilice esta fórmula directamente para contestar lo siguiente y relacionar el álgebra y la geometría del método símplex al ir de una iteración a otra, desde el punto (2, 4, 3) hasta (4, 2, 4). (Se tiene información de que se mueve a lo largo de este segmento de recta.) a) ¿Cuál es la variable básica entrante? x 5 entra b) ¿Cuál es la variable básica que sale? x 4 de hojas c) ¿Cuál es la nueva solución BF?

( 4,2,4,0,2,0,0 ) 5.1-21. Considere un problema de programación matemática con dos variables cuya región factible se muestra en la gráfica; los seis puntos corresponden a las soluciones FEV. El problema tiene una función objetivo lineal y las dos rectas punteadas indican rectas de función objetivo que pasan por la solución óptima (4, 5) y por la segunda mejor solución FEV (2, 5). Observe que la solución no óptima (2, 5) es mejor que las dos soluciones FEV adyacentes, lo cual viola la propiedad 3 de programación lineal que se explicó en la sección 5.1 para soluciones FEV. Construya la región factible que resultaría si los seis segmentos de la frontera fueran restricciones de frontera para las restricciones de programación lineal, con el fi n de demostrar que este problema no puede ser un problema de programación lineal.

5.2-1. Considere el siguiente problema. Maximizar Z=8 x 1+ 4 x 2+ 6 x3 +3 x 4 +9 x 5 Sujeta a x 1+ 2 x 2 +3 x3 +3 x 4 ≤180 4 x1 +3 x 2+ 2 x 3 + x 4 + x 5 ≤ 270 x 1+ 3 x 2 + x 4 +3 x 5 ≤ 180 Y xj≤0

j=1 ,, , , , , ,5

Se sabe que las variables básicas de la solución óptima son x3, x1 y x5 y que

3 1 0 1 11 −3 1 2 4 1= −6 9 −3 27 0 1 3 2 −3 10

[ ] [

]

a) Con esta información identifique la solución óptima. x3 x1 x5

1 2

11 −3 1 180 50 −6 9 −3 270 = 30 2 −3 10 180 50

() ( −1 b=

=B

)( ) ( )

30 0 Z=cα =( 8 , 4 ,6 ,3 , 9 ) 50 =990 0 50

()

b) Use esta información para identificar los precios sombra de los tres recursos. Precios sombra:

−1=

cB B

11 −3 1 1.33 1 ( 6 8 9 ) −6 9 −3 = 1 27 2 −3 10 2.67

(

)( )

5.2-2. Aplique la forma matricial del método simplex para resolver el siguiente problema.

Maximizar Z=5 x1 +8 x 2 +7 x3 + 4 x 4 +6 x y sujeta a 2 x 1 +3 x2 +3 x 3+ 2 x 4 +2 x 5 ≤ 20 3 x 1+5 x 2 +4 x 3 +2 x 4 +4 x 5 ≤30 x j ≥ 0. j=1,2,3,4,5 . c= (5 8 7 4 6 0 0 ) , A= 2 3 3 2 2 1 0 , b= 20 3 5 44 0 11 30

(

) ( )

x Iteration 0: B=B−1= 1 0 , x B= 6 = 1 0 20 = 20 0 1 0 1 30 30 x7

( ) ( ) ( )( ) ( )

c B =( 0 0 ) ,−c=(−5−8−7−4−6 0 0 ) , entonces x 2 entra x 2 coeficiente :

(10 01 )(35)=(35 ) , entonces x

7

1 0 iteracion1 : B−1 nuevo= 0 1

−1

( ) =(10 )( ) ( )

Fila revisada 0:(0 8 /5)

¿

)

x6 = 1 −3/5 20 = 2 , c B =(0 8) 0 1/5 30 6 x7

( )(

xB=

−3/5 , 1/5

(23

3 3 2 2 10 ,−( 5 8 7 4 6 0 0 ) 5 4 4 0 11

)

( −15 0− 35 − 45 − 25 0 85 ) ,entonces x entra 6

coeficiente revisado x 4 : 1 −3 /5 2 = 4 /5 entonces x 6 0 1/5 2 2/5

(

)( ) ( )

2 3 interaccion2 : B−1 nuevo= 2 5

−1

5/4 ( ) =(−1/ 2

)

x4 = 5/4 −3/4 20 = 5 /2 , c B =(4 8) −1/2 1/2 30 5 x2

()(

xB=

−3/ 4 1/2

)( ) ( )

Fila revisada 0:(1 1)

(32

3 3 2 2 1 0 ,−( 5 8 7 4 6 0 0 ) 5 42 4 01

)

¿ ( 0 0 0 0 0 11 ) , por lo que la solucion actual es optima ¿ ¿ ¿ ¿ ¿ ¿ Optima solución:( x 1 , x 2 , x 3 , x 4 , x 5 )=( 0 ,5 , 0,5/2 , 0 ) y Z =50

5.2-3. Reconsidere el problema 5.1-1. Para la sucesión de soluciones FEV que se identificó en el inciso e), construya la matriz base B de cada solución BF correspondiente. En cada caso, invierta B en forma manual y utilice esta B–1 para calcular la solución actual; después realice la siguiente iteración (o demuestre que la actual es óptima). C=( 3 2 0 0 ) , A=

(21

1 10 6 ,b 2 01 6

) ()

x CP=( 0 , 0 ) : B=B−1= 1 0 , x B = 3 = 1 0 6 = 6 0 1 0 1 6 6 x4

( ) ( ) ( )( ) ( )

fila 0 : (−3 −2 0 0 )

CP ( 3 , 0 ) : B= 2 0 , B−1= 1/2 0 1 1 −1/2 1

( )

)

x1 = 1/2 0 6 = 3 , c B =(3 0) −1/2 1 6 3 x4

()(

xB=

(

)( ) ( )

fila 0 :(3 /2 0) 2 1 1 0 , (−3 −2 0 0 )=(0−1/2 3 /2 0) 1 2 01

(

)

2/3 (21 12) , B =(−1/3 −1

CP ( 2 , 2 ) : B=

fila 0 :(3 2)

)

x1 = 2/ 3 −1/3 6 = 2 , c B=(3 2) −1/3 2/3 6 2 x2

( )(

xB=

−1 /3 2 /3

(21

)( ) ( )

1 10 , (−3 −2 0 0 )=( 0 0 1/3 1/3) 2 01

)

¿ ¿ ¿ Optima solución:( x 1 , x 2 , )=( 2 , 2 ) y Z =10

5.2-4. Aplique la forma matricial del método símplex para resolver el modelo que se presentó en el problema 4.1-5.

( 1 20 0 ) A=+ 1 3 1 0 b+ 8 11 0 1 4

(

) () 10 10 8 8 Interrelación 0: B=B =( ) . xB=( )( )=( ) 01 01 4 4 −1

La fila entera en la base x 2 cB=( 0 0 ) , (−1−2 0 0 ) Revisar los coeficientes x 2 en los niveles de la base

(10 01 )(31)=(1001)

30 Interrelación 1: B = 11 −1

−1

( )

1 0 3 = −1 1 3

( )

1 8 0 x 2 3 8 xB= = = 3 . cB ( 2 0 ) x4 −1 4 4 1 3 3

( )

( )( ) ( )

Revisión de la fila:

( 23 0)(11 31 10 01)−( 12 0 0 )

Es el entero de la base x 1 ¿

( −13 0 23 0)

Revisar los coeficientesx 1 con sus niveles 1 1 0 3 1= 3 −1 1 2 1 3 3

( )( ) ( ) −1 31 Interrelación 2: B = 11

−1

( )

1 1 − = 2 2 −1 3 2 2

( )

1 1 − xB= x 2 = 2 2 8 = 2 . cB=( 2 1 ) x1 −1 3 4 2 2 2

( )

( )( ) ( )

Revisando la fila 0:

( 12 12 )(11 3110 01 )−( 1 2 0 0) (

La solución correcta optima 0 0

11 22

)

Solución optima ( x 1 , x 2 )= ( 2,2 ) Z=6 5.2-5. Aplique la forma matricial del método símplex para resolver el modelo que se presentó en el problema 4.7-6.

c= (5 4−13 0 0 ) 32−3 11 0 ,b= 24 3 3 1 3 01 36

(

−1 Interrelación 0: B=B

) ( ) =(1 0 ) . xB=(1 0 )( 8 )=( 8 ) 01 01 4 4

La fila entera en la base x 1 cB=( 0 0 ) , (−5−4 1−3 0 0 ) Revisar los coeficientes x 2 en los niveles de la base

(10 01 )(34 )=( 33) −1 30 Interrelación 1: B = 11

−1

( )

1 0 = 3 −1 1 3

( )

1 0 24 = 8 . cB ( 5 0 ) xB= x 1 = 3 x6 −1 36 12 1 3

( )

( )( ) ( )

Revisión de la fila:

1 0 −( 5 4 1 3 0 0 ) ( 53 0)(332−31 3 13 0 1 )

Es el entero de la base x 3 2 45 ¿ 0− −4− 0 3 33

(

)

Revisar los coeficientesx 1 con sus niveles 1 0 3 −3 = −1 4 −1 1 1 3

( )( ) (

)

−1 31 Interrelación 2: B = 11

−1

( )

11 = 24 −1 1 4 4

( )

11 x 1 xB= = 2 4 24 = 11 . cB=( 5−1 ) x3 −1 1 36 9 4 4

( )

( )( ) ( )

Revisando la fila 0:

1 10 − (5 4 1 3 00 ) ( 23 1)(332−3 31 3 0 1 )

1 22 1 La solución correcta optima 0 0 3 33

(

)

Solución optima ( x 1 , x 2 , x 3 , x 4 )= (11,0,3,0 ) Z=52 5.3.1Considere el siguiente problema Maximizar Z=x 1−x 2+2 x 3 Sujeto a 2 x1 −2 x 2 +3 x3 ≤ 5 x 1+ x2−x 3 ≤3 x 1−x 2+ x 3 ≤2 Y, x 1 ≥ 0

x2 ≥ 0

x3 ≥ 0

Sean x 4 , x5 , x 6 las variables de holgura de las restricciones respectivas. Después de aplicar el método símplex, una parte de la tabla símplex final es como se muestra a continuación Variabl

.

Coeficiente de:

e básica

Ec. Z x 1 x 2 x 3 x 4 x 5 x 6

Z x2

(0) (1)

0 0

1 1 0

1 3 1

0 0 0

(2) x6 x3 (4) 0 1 2 0 a) Utilice la idea fundamental presentada en la sección 5.3 para identificar los números que faltan en esta tabla simplex final. Muestre sus cálculos. b) Identifique las ecuaciones de definición de la solución FEV correspondiente a la solución BF óptima de la tabla simplex final. Respuesta:

1 3 0 A= 0 1 1 1 2 0

(

a) B

−1

)

Columnas de restricción para: x 1 , x2 , x 3 1 3 0 2 −2 3 5 1 0 A= 0 1 1 1 1 −1 = 2 0 0 1 2 0 1 −1 1 4 0 1

(

−1

B

)(

)(

)

c B =(−10 2) Coeficientes objetivos finales para: : x 1 , x2 , x 3 5 1 0 c B B A−c=(−1 02 ) 2 0 0 −( 1−1 2 )= ( 0 02 ) 4 0 1

(

−1

)

Lado derecho: 1 3 0 5 14 14 B−1 b= 0 1 1 3 = 5 y Z =(−10 2 ) 5 =S 1 2 0 2 11 11

( )( ) ( )

()

b) Definiendo ecuaciones:2 x1 −2 x 2 +3 x3 =5 , x 1 + x 2−3 , x3 =0 5.3.2 Considere el siguiente problema. Maximizar Z=4 x 1−3 x 2 + x 3+ 2 x 4 Sujeto a 4 x1 +2 x 2+3 x 3 + x 4 ≤5 3 x 1+ x 2 +2 x3 + x 4 ≤ 3 x 1−x 2+ x 3 ≤2

Y, x 1 ≥ 0

x2 ≥ 0

x3 ≥ 0

x4 ≥ 0

Sean x 5 y x 6 las variables de holgura de las restricciones respectivas. Después de aplicar el método símplex, una parte de la tabla final es como se muestra a continuación:

Variable básica

.

Coeficiente de:

Ec.

Z

Z x2

(0) (1)

x4

(2)

1 0 0

Lado derecho

x1 x2 x3 x4 x5 x6 1 1 3

1 -1 2

9 1 3

a) Utilice la idea fundamental que se presentó en la sección 5.3 para identificar los números que faltan en esta tabla. Muestre sus cálculos. b) Identifique las ecuaciones de definición de la solución FEV que corresponde a la solución BF óptima de la tabla símplex final. Respuesta: −1

a) B

A= 1 −1 −1 2

(

)

Columnas de restricción para:( x 1 , x 2, x 3 , x 4 ) : −1

B A=

(−11 −12 )( 43

2 1 1 1 1 −1 0 = 12 1 2 0 3 1

)(

)

c B =(3 2) Coeficientes objetivos finales para: x 1 , x2 , x 3 , x 4 c B B−1 A−c =(3 2)

(12

1 −1 0 − ( 4 3 1 2 )=( 3 0 2 0 ) 0 3 1

)

Lado derecho: B−1 b= 1 −1 5 = 1 y Z=( 3 2 ) 1 =9 −1 2 4 3 3

(

)( ) ( )

()

b) Definiendo ecuaciones:4 x1 −2 x 2 + x 3+ x 4 =5 , 3 x 1 + x 2+ 2 x 3 +4 , x 4 =0 5.3-3. Considere el siguiente problema. Maximizar Z=6 X 1− X 2 +2 X 3 SUJETA A:

1 2 X 1 +2 X 2 + X 3 ≤ 5 2 3 −4 X 1−2 X 2 − X 3 ≤3 2 1 X 1 +2 X 2− X 3 ≤ 1 2 Y

X 1 ≥ 0 , X 2 ≥ 0 , X 3 ≥0 1 1 2 B−1= −2 0 4 1 0 −1

(

)

Columnas de restricción final para ( X 1 , X 2 , X 3)

1 1 2 2 2 1 /2 0 4 0 B−1= −2 0 4 −4 −2 −3 /2 = 0 4 1 1 0 −1 1 2 1 /2 1 0 0

(

)(

)(

)

c B =( 0 2 6 ) Coeficientes los objetivos finales para ( X 1 , X 2 , X 3)

0 4 0 c B B−1 A−c=( 0 26 ) 0 4 1 − ( 61 2 )=(0 7 0) 1 0 0

(

)

Lado derecho:

1 1 2 2 7 7 B b= −2 0 4 3 = 0 y Z=( 0 2 6 ) 0 =6 1 0 −1 1 1 1 −1

(

)( ) ( )

()

Sean x4, x5 y x6 las variables de holgura de las restricciones respectivas. Después de aplicar el método símplex, una parte de la tabla símplex final es como se muestra a continuación:

Cuadro final Bas Eq

LADO

Var No

Z

X1

X2

X3

X4

X5

X6

DERECHO

Z

0

1

0

7

0

2

0

2

6

X5

1

0

0

4

0

1

1

2

7

X3

2

0

0

4

1

-2

0

4

0

X1

3

0

1

0

0

1

0

-1

1

D 5.3-4. Considere el siguiente problema. Maximizar Z =20 x 1+6 x 2+ ¿8 x

3

¿

a) Utilice la idea fundamental que se presentó en la sección 5.3 para identificar el valor de (c1, c2, c3) que se usó.

3 /16 −1/8 0 0 B−1= −1/4 1/2 0 0 −3 /8 1/4 1 0 0 0 0 1

(

)

Columnas de restricción actuales para ( X 1 , X 2 , X 3)

3 /16 −1/8 0 0 B−1= −1/4 1/2 0 0 ¿ −3 /8 1/4 1 0 0 0 0 1

(

)

c B =( 206 0 0) Coeficientes de objetivos actuales

c B B−1 A−c=(20 6 0 0)¿ Lado derecho:

3 /16 −1/8 0 0 200 25 −1 −1/ 4 1/2 0 0 100 B b= = 0 y Z=(20 6 0 0) −3 /8 1/ 4 1 0 50 0 0 0 0 1 20 20

(

)( ) ( )

25 0 =500 0 20

()

Bas Eq

LADO

Var No

Z

X1

X2

X3

Z

0

1

0

0

X1

1

0

1

0

0.563

0.188

X2

2

0

0

1

-0.75

X6

3

0

0

0

-0.13

X7

4

0

0

0

1

-1.25

X4

X5

X6

X7

DERECHO

0.5

0

0

500

-0.13

0

0

25

-0.25

0.5

0

0

0

-0.38

0.25

1

0

0

0

0

0

1

20

2.25

b) Utilice la idea fundamental que se presentó en la sección 5.3 para identificar el valor de b que se usó. El método simplex revisado generaría los costos reducidos para la fila 0 y luego la columna revisada para X3 c) Calcule el valor de Z* de dos maneras; en una de ellas utilice los resultados del inciso a) y en la otra los resultados del inciso b). Muestre los métodos para encontrar Z*. Definiendo ecuaciones 8 x 1+ 2 x 2 +3 x3 =200 , 4 x 1+3 x 2=100 x 3=0 Tenga en cuenta que 2 x1 + x 3=50 también es vinculante en la solución actual.

5.3-5 Considere el siguiente problema. Maximizar

Z=C1 X 1 +C 2 X 2 +C 3 X 3

Sujeta a: X 1 +2 X 2 + X 3 ≤ b 2 X 1 + X 2 +3 X 3 ≤ 2b Y X 1 ≥ 0 , X 2 ≥ 0 , X 3 ≥0. Observe que no se asignaron valores a los coeficientes de la función objetivo ¿), y que la única especificación para los valores del lado derecho de las restricciones funcionales es que el segundo (2 b) es el doble del primero (b) . Ahora suponga que su jefe decidió insertar su mejor estimación de los valores de C 1 , C2 , C3 y b sin informarle y después corrió el método simplex. El resultado es la tabla simplex final resultante que se muestra a continuación (donde X 4 y X 5 son las variables de holgura de las restricciones funcionales respectivas), pero no puede leer el valor de Z∗.

VARIABLE BASICA Z

Ec. (0)

Coeficiente de: Z 1

x1

(1)

0

x3

(2)

0

x1 x2 x3 x4 x5 7 0 10 1 1 5 3 0 5

Lado derecho

3 5 3 5 1 5

0 0 1

4 5 1 5 2 5

Z∗¿ 1 3

a) Utilice la idea fundamental que se presentó en la sección 5.3 para identificar el valor de ¿) que se usó. b) Utilice la idea fundamental que se presentó en la sección 5.3 para identificar el valor de b que se usó. c) Calcule el valor de Z* de dos maneras; en una de ellas utilice los resultados del inciso a) y en la otra los resultados del inciso b). Muestre los métodos para encontrar Z*. SOLUCIÓN: a) (−C 1−C 2−C3 ) ⋮ 0 0 ⋮0 ¿+ −C 1+

( 35 45 )(12

2 1 1 0 ⋮ b =¿ 1 30 1 2b

)

11 7 3 = ⟹ ,−C2 +2=0 ⟹C 2=2 ,−C 3 +3=0⟹ C 3=3 5 16 2

−1 3/5 −1/5 , B−1 b=b∗⟺ 3/5 −1/5 b = 1 ⟺ b=5 b) B = −1/5 2/5 −1/5 2/5 2 b 3 1 1 ¿ ¿ =( 2 3 ) =11 c) UTILIZANDO (a): Z =C B b =( C 2 C 3) 3 3

(

)

(

)( ) ( ) () ()

¿ b =( 3/5 4 /5 ) 5 =11 UTILIZANDO (b) Z =C´ B b=( 3/5 4 /5 ) 2b 10

( )

( )

5.3-6 La siguiente expresión se obtuvo en la iteración 2 del ejemplo de la sección 5.3: Renglón final 0=[ −3 −5 ⋮ 0 , 0 , 0 ⋮ 0 ]

[

+ 0,

3 2

1 0 1 0 0 4 1 0 2 ⋮ 0 1 0 ⋮ 12 . 3 2 0 0 1 18

][

]

Obtenga esta expresión mediante la combinación de las operaciones algebraicas (en forma matricial) que afectan el renglón 0, en las iteraciones 1 y 2. SOLUCION:

ITERACION 1: Multiplicar la fila 2 por 5/2 y agregar a la fila 0, es decir, pre multiplicar A0 por ( 0 5/2 0 ) y agregar a la fila 0, donde: 1 0 1 0 0 4 A0 = 0 2 ⋮ 0 1 0 ⋮ 12 3 2 0 0 1 18

(

)

ITERACION 2: Agregar la fila 3 a la fila , es decir, pre multiplicar A1 por ( 0 0 1 ) y agregue a la fila 0, donde: 1 0 1 0 0 4 1 0 0 A1= 0 1 ⋮ 0 1/2 0 ⋮ 6 = 0 1 /2 0 A 0 . 3 0 0 −1 1 6 0 −1 1

(

)(

)

(

Por lo tanto, la fila final 0 es: fila inicial 0+ 0

[

5 2

)

0 A0 + ( 0 0 1 ) A1 . 1

(

¿ (−3 −5 ⋮0 0 0 ⋮0 )+ 0

(

¿ (−3 −5 ⋮0 0 0 ⋮0 )+ 0

5 2

3 2

0 0 1 0 +( 0 0 1) 0 0 A0. 2 0 −1 1

)

( )]

)

1 A0 .

5.3-7. La mayor parte de la descripción de la idea fundamental que se presentó en la sección 5.3 supone que el problema se encuentra en nuestra forma estándar. Ahora considere otras formas que requieren los ajustes adicionales del paso inicial expuestos en la sección 4.6, inclusive el uso de variables artificiales y el método de la gran M cuando sea apropiado. Describa los ajustes que deben hacerse a la idea fundamental para: a) Restricciones de igualdad. Use las columnas correspondientes a variables artificiales exactamente de la misma manera que uní la variable de holgura habría sido utilizada. Tenga en cuenta que el precio sombra de esta columna puede ser positivo o negativo b) Restricciones funcionales de la forma ≥ Para las desigualdades invertidas, use el negativo de la columna correspondiente a la variable de holgura en exactamente las mismas fórmulas. La columna artificial puede descartarse.

c) Lados derechos negativos. Igual que (b) d) Variables que pueden tomar valores negativos (sin cota inferior). Sin cambios, use variables flojas y artificiales como se indicó anteriormente. 5.3-8. Reconsidere el problema 4.6-5. Utilice variables artificiales y el método de la gran M para construir la primera tabla simplex completa para el método simplex y después identifique las columnas que formarán S¿para aplicar la idea fundamental en la tabla simplex final. Explique por qué éstas son las columnas apropiadas. max Z=5 x1 + 4 x 2−Mx 5 Sujeto a 3 x 1 +2 x2 + x 3=6 2 x1 −x2 −x 4 + x5 =6 x1 , x2 , x3 , x4 , x 5 ≥ 0

Cuadro inicial: BV Z

Eq 0

Z 1

x1 −5−¿2

Coeficiente de x2 x3 x4 −4+ M 0 M

x5

RS 0

−6 M

M

x3 x5

1 2

0 0

3 2

2

1 0

−1

0

0 1

−1

6 6

Las columnas que contendrán para S¿ aplicar la información fundamental en el cuadro final son aquellos asociados con y, dado que x 3 y x 5 esas columnas forman la matriz 2x 2 de identidad en el cuadro inicial. Cuadro final: Coeficiente de

x1

BV Z

Eq 0

Z 1

x3

1

0

1

x5

2

0

0

0

x2 −2 + 3 7 M 3 2 3 −7 3

x3 5 + 3 2 M 3 1 3 −2 3

x4

x5

RS

M

0

10−6 M

0

0

2

−1

1

2

5.3-9. Considere el siguiente problema. Z=2 x 1 +2 x2 +2 x 3

Minimizar Sujeta a x 1+ 4 x 2 +2 x 3 ≥ 8

3 x 1+2 x 2+ 2 x 3 ≥6 Y x 1 ≥ 0 , x2 ≥ 0 , x 3 ≥0. Solución 3 10 (a) B = −2 10 −1

−1 10 2 5

( )

Columnas de restricción final para ( x ¿ ¿ 1 , x 2 , x 3 , x 4 , x 5 , x 6) :¿ 3 −1 10 (a) B A= −2 10

−1 10 2 5

( )

1/10 (13 42 20 −10 −10 ) = (01 10 −23 /5/5−32 /10/10 −2/5 )

c B =(−6 M +3−4 M + 2) Coeficientes objetivos finales para ( x ¿ ¿ 1 , x 2 , x 3 , x 4 , x 5 , x 6) :¿ −c B B−1 A +c=−(−6 M +3−4 M +2)

1/10 (01 10 −23 /5/5−32 /10/10−2/5 )

+ (−4 M +2−6 M +3−2 M +2 M M )=¿ Lado derecho: 3 10 B b= −2 10 −1

−1 10 2 5

( )

(86 )=( 9/5 4 /5 )

z=−14 M + c B x B=−14 M +(−6 M + 3−4 M + 2) 9/5 4 /5

( )

Cuadro final: Bas

Eq

Coeficiente de

Lado

Var No

derecho Z

Z x2 x1

0 1 2

x1

x2

-1 0 0

0 0 1

x3 0 1 0

x4

1 0.6 -0.4

0.5 -0.3 0.2

x5 0.5 0.1 -0.4

x6 1M -0.5 0.3 -0.2

x7 1M -0.5 -0.1 0.4

−7 1.8 0.8

(b) Las restricciones en el cuadro original se pueden expresar como ( A ⋮ I ⋮ I ⋮b) con la segunda matriz de identidad correspondiente a las variables artificiales. matriz por M para obtener:

( A¿ ⋮ S ¿ ⋮ L¿ ⋮ b ¿ )=M ( A ⋮ I ⋮ I ⋮ b ) =( MA ⋮ M ⋮ M ⋮ Mb ) , 3 ¿ ¿ 10 Donde M =S =L = −2 10

−1 10 . 2 5

( )

Fila original 0: t=( c+ eT AM ⋮ Me T ⋮0 ⋮−Me T b) Cuadro final: t ¿=t+ v T ( A ⋮ I ⋮ I ⋮ b) ¿¿ ¿ ( c +c T AM ⋮ Mc T ⋮0 ⋮ Mc T b ) + v T ( A ⋮ I ⋮ I ⋮ b ) ¿( c +e T AM + v T A ⋮ Me T + v ⋮ v ⋮−Me T b+ v T b) ¿ T Por lo tanto, v=− y + Me −(

−1 1 +M− +M ) 2 2

(c) t=( 2 3 20 M 0 M 0 ) =(c ⋮ 0⋮ Me T ⋮ Me T b) t ¿=t+ v T ( A ⋮ I ⋮ I ⋮ b ) ¿( Z ¿ + c ⋮− y ¿ ⋮ Me T − y ¿ ⋮ Z¿ ) ¿ ( c ⋮0 ⋮ MeT ⋮ Me T b )+ v T ( A ⋮ I ⋮ I ⋮ b ) ¿( c+ v T A ⋮ v ⋮ Me T + v ⋮ Me T b+ vT b)

( −12 − 12 )

¿ Por lo tanto, v= y =

(d) Definiendo ecuaciones: x=Mb ↔ M −1 x=b x 1+ 4 x 2 +2 x 3=8 , x 1 +2 x 2=6 x 3=0 5.3-10. Considere el siguiente problema. Z=3 x1 +7 x 2 +2 x 3 Maximizar Sujeta a −2 x1 +2 x 2+ x 3 ≤10 3 x 1+ x 2−x 3 ≤20 x1 ≥ 0 , x 2 ≥ 0, 0 x 3 ≥ 0 Se conoce el hecho de que las variables básicas de la solución óptima son x 1y x 3. a) Introduzca las variables de holgura y después utilice la información que se proporcionó para encontrar la solución óptima en forma directa mediante la eliminación gaussiana. x -2 1+2 x 2+ x 3+ x 4 =10(i) 3 x 1+ x 2- x 3+ x 5=20(ii) Multiplicar 4 x 1+1/2 x 3+3/4 x 4 + x 5=35 Optima solución ( x 1, x 2, x 3)= (30,0,70) b) Amplíe el trabajo del inciso a) para encontrar los precios sombra. 3 x 1+7 x 2+2 x 3 -3 x 1-9 x 2-3 x 3−3 x 5 -16 x 2-2 x 3-6 x 4 -4 x 5 -18 x 2-3 x 3-6 x 4 -7 x 5 c) Utilice la información que se proporcionó para identificar las ecuaciones de definición de la solución FEV óptima y después resuelva estas ecuaciones para obtener la solución óptima. -2 x 1+2 x 2+3 x 3=10,3 x 1+ x 2- x 3=20, x 2=0 d) Construya la matriz base B de la solución BF óptima, invierta B manualmente y después use esta B−1para obtener la solución óptima y los precios sombra y*. Luego aplique la prueba de optimalidad del método símplex revisado para verificar que esta solución es óptima. −2 2 1 1 0 e) ( )-(3 7 2 0 0 )=(0 18 0 9 7) 3 1 −1 0 1

f) Dados B−1 y y* del inciso d), utilice la idea fundamental presentada en la sección 5.3 para construir la tabla simplex final. Var z x1 x2

No 0 1 2

Z 1 0 0

x1 0 1 0

x2 18 3 8

x3 0 0 1

x4 9 1 3

x5 7 1 2

R 230 30 70

5.4-1. Considere el modelo que se presentó en el problema 5.2-2. Sean x 7y x 7.las variables de holgura para la primera y segunda restricciones, respectivamente. Se le proporciona la información de que x 2 esa variable básica entrante y x 7 la variable básica saliente de la primera iteración del método símplex y, por lo tanto, x 4 es la variable básica de ingreso y x 6 es la variable básica de egreso de la segunda iteración (final). Utilice el procedimiento que se presentó en la sección 5.4 para actualizar B−1de una iteración a la siguiente con el fi n de encontrar B−1después de la primera iteración y, luego, después de la segunda. −1 1 0 B=B = Interaccion 0: 0 1 Revised x 2 coefficients:

( ) (10 01)(35)=(35 )

x 2 Entra y x 7 sale

Iteraccion 1:

−a 12 −3 ƞ= a 22 = 5 1 1 5 a 22

( )( )

−3 −3 1 −1 5 1 0 5 Bnew = = 1 0 1 1 0 0 5 5 1

( )( ) ( )

1

Revisando x 4 coeficientes:

−3 4 5 2= 5 1 2 2 5 5

( )( ) ( ) 0

x 4Entra y x 6 sale 1

5 á11́ 4 Iteración 2: ƞ= ́ = −1 −a 24 ́ 2 a

( )( ) 11

5 4 Bnew−1 ¿ −1 2

−3 5 5 4 = 1 −1 1 0 5 2 0 1

−3 4 1 2

( )( ) ( )

5.4-2. * Utilice el método símplex revisado paso a paso para resolver el modelo que se muestra en el problema 4.3-4. Z=4 x 1 +3 x 2+ 6 x 3 Sujeta a:

3 x 1+ x 2 +3 x 3 ≤ 30 2 x1 +2 x 2+3 x 3 ≤ 40 Y

x 1 ≥ 0 , x2 ≥ 0 , x 3 ≥0

3 15100 10 c= (1 2 4 0 0 0 ) , A= 1 4 1 0 1 0 ,b= 8 202001 7

(

Iteracion 0:

) ()

100 B=B−1 = 0 1 0 001

( )

x4 1 0 0 10 10 x B = x5 = 0 1 0 8 = 8 001 7 7 x6

( ) ( )( ) ( )

c B =( 0 0 0 ) ,Row 0: (−1−2−4 0 0 0 ) x B =¿ Entra en la base

1 5 −1 Interacion 1: ƞ= 5 −2 5

()

1 1 5 5 00 100 00 −1 −1 Bw−1= 10 010 = 10 5 5 01 001 01 −2 −2 5 5

( )( ) ( )

1 5 x3 0 0 10 2 −1 xB= x5 = 10 8 = 6 5 01 7 3 x6 −2 5

()

()

c B =( 4 0 0 ) Fila revisada 0:

( ) ()

3 15100 4 0 0 1 4 1 0 1 0 −( 1 2 4 0 0 0 ) 5 2 02001

( )( ¿

)

( 45 − 65 0 45 0 0)

x 2 entra en la base

1 1 5 5 00 1 −1 19 Revisando x 2 coeficientes: 10 4 = 5 5 01 0 −2 −2 5 5

( )( ) ( )

x 5 hojas

−1 19 5 ƞ= 19 2 19

() ( )( ) ( )

Iteraccion 2:

−1 1 4 1 19 5 19 19 1 0 00 0 5 −1 −1 5 Bw−1= 0 = 0 10 0 19 5 19 19 0 1 01 1 2 −2 −8 2 19 5 19 19

4 19 x3 −1 xB= x2 = 19 x6 −8 19

1 32 19 19 0 10 5 30 0 8 = 19 19 1 7 2 69 19 19

( ) ()

()

()

c B =( 4 20 )

Fila revisada 0:

(

315100 14 6 0 1 4 1 0 1 0 − (1 2 4 0 0 0 ) 19 19 202001

¿

( 2919 0 0 1419 196 0)

)(

)

La solucion actual es optima. ¿

¿

¿

(

Solucion optima: ( x 1 x 2 x3 ) = 0 ,

30 32 188 , y Z ¿= 19 19 19

)

I 5.4-3. Utilice el método símplex revisado paso a paso para resolver el modelo que se muestra en el problema 4.7-5. Z=2 x 1−2 x 2+ 3 x 3 Sujeta a:

−x 1+ x2 + x 3 ≤ 4 2 x1 −x2 + x 3 ≤ 2 x 1+ x2 +3 x 3 ≤ 12

Y

x 1 ≥ 0 , x2 ≥ 0 , x 3 ≥0

−1 1 1 1 0 0 4 c= (2−2 30 0 0 ) , A= 2 −1 1 0 1 0 ,b= 2 1 1 3001 12

(

Iteracion 0:

) ()

100 B=B = 0 1 0 001 −1

( )

x4 100 4 4 x B = x5 = 0 1 0 2 = 2 0 0 1 12 12 x6

( ) ( )( ) ( )

c B =( 0 0 0 ) ,Row 0: (−2 2−3 0 0 0 ) x 3=¿ Entra en la base. 100

4 4 2 = 2 0 0 1 12 12

( )( ) ( )

Coeficientes x 3 revisados 0 1 0

x 5Deja la base −1

1−1 0

() ( ) ( ) ( )( ) ( ) −1

Interacion 1: ƞ= 1 =B new = 0 1 0

−3

0−3 1

x4 1 −1 0 4 2 x B = x3 = 0 1 0 2 = 2 0 3 1 12 6 x6 c B =( 0 3 0 ) Fila revisada 0:

−1 1 1 1 0 0 ( 0 3 0 ) 2 −1 1 0 1 0 −( 2−2 4 0 0 0 ) 1 1 3001

(

¿ ( 4−1 0 0 3 0 )

)

x 2 entra en la base 1 −1 0 1 2 Revisando x 2 coeficientes: 0 1 0 −1 = −1 0 −3 1 1 4

( )( ) ( )

x 4 hojas

1 /2 1/2 −1/2 0 ƞ= 1 /2 , Bnew−1= 1/2 1/2 0 −2 −2 −1 1

( ) ( ( ) ( )( ) ( )

Iteraccion 2:

)

x2 1/2−1 /2 0 4 1 x B = x 3 = 1/2 1/2 0 2 = 3 −2 −1 1 12 2 x6

c B =(−2 3 0 )

Fila revisada 0:

−1 1 1 1 0 0 (1/2 5/20) 2 −1 1 0 1 0 −( 2−23 0 0 0 ) 1 1 3001

(

)

¿( 5/2 0 0 1/2 5/2 0 )

La solucion actual es optima. ¿

¿

¿

¿

Solucion optima: ( x 1 x 2 x3 ) =( 0 , 1 ,3 ) y Z =7

I 5.4-4. Utilice el método símplex revisado paso a paso para resolver el modelo que se muestra en el problema 3.1-6. Min Z=2 x 1−2 x 2+ 3 x 3 Sujeta a:

x 1+ 2 x 2 ≤ 12

2 x1 +3 x 2=2 2 x1 + x 2 ≥ 12

Y

x 1 ≥ 0 , x2 ≥ 0 , −1 2 1 0 0 15 ( ) c= 10 20 0 0 0 , A= 1 1 0 1 0 ,b= 12 5 3001 45

(

Iteracion 0:

) ()

100 B=B−1 = 0 1 0 001

( )

x3 1 0 0 15 15 x B = x 4 = 0 1 0 12 = 12 0 0 1 45 45 x5

( ) ( )( ) ( )

c B =( 0 0 0 ) ,Row 0: (−10−20 0 0 0 0 ) x 3=¿ Entra en la base. 100 2 2 x Coeficientes 2 revisados 0 1 0 1 = 1 001 3 3

( )( ) ( )

x 5Deja la base 1/2 1/2 0 0 −1 ƞ= =B = Interacion 1: −1/2 −1/2 1 0 new −3/2 −3/2 0 1

( ) ( ( ) ( )( ) ( )

x4 1/2 0 0 15 7.5 x B = x3 = −1 /2 1 0 12 = 4.5 −3 /2 0 1 45 22.5 x6 c B =( 20 0 0 )

)

Fila revisada 0:

−1 2 1 0 0 ( 10 0 0 ) 1 1 0 1 0 −( 10 20 0 0 0 ) 5 3001

(

)

¿ (−20 0 10 0 0 )

x 2 entra en la base 1 /2 0 0 −1 −1/2 Revisando x 2 coeficientes: −1 /2 1 0 1 = 3 /2 −3 /2 0 1 5 13/2

(

)( ) ( )

x 4 hojas

1/2 1/3 1/3 0 −1 ƞ= 2/3 , Bnew = −1/3 2/3 0 −13/3 2/3 −13/3 1

( ) ( )( ) ( ) ( )(

Iteraccion 2:

x2 1/3 1/3 0 15 9 x B = x 1 = −1/3 2/3 0 12 = 3 2/3 −13/3 1 45 3 x5

c B =( 20 10 0 )

Fila revisada 0:

−1 2 1 0 0 (10/3 40 /3 0) 1 1 0 1 0 − ( 1020 0 0 0 ) 5 3001

(

)

¿( 0 0 10/3 40/3 0 )

La solucion actual es optima. ¿

¿

¿

¿

Solucion optima: ( x 1 x 2 x3 ) =( 3 , 9 ) y Z =210

)