5. pl análisis de sensibilidad e interpretación de la solución(1)

5. Programación lineal: análisis de sensibilidad e interpretación de la solución

Mtra. Maribel Beltrán Castelo Métodos Cuantitativos

Métodos Cuantitativos

5. ANÁLISIS DE SENSIBILIDAD.

5.1 CAMBIOS EN LOS TÉRMINOS INDEPENDIENTES DE LAS

RESTRICCIONES.

5.2 CAMBIOS EN LOS COEFICIENTES DE LA FUNCIÓN OBJETIVO.

5.3 LOS COEFICIENTES DE LAS TASAS FÍSICAS DE SUSTITUCIÓN.

5.4 ADICIÓN DE UNA NUEVA VARIABLE.

PROGRAMACIÓN LINEAL

INTRODUCCION

En el tema anterior se analizó el planteamiento de un modelo

lineal (es decir, identificación de las variables de decisión, la forma de

desarrollar una función objetivo, las restricciones y las condiciones de no

negatividad), y se describió el empleó de un método gráfico para resolver

problemas de PL. También se señaló que el método gráfico se limita a la

solución de problemas con dos variables y se hizo notar que los

problemas de programación lineal con numerosas variables y/o

restricciones pueden resolvedrse utilizando un procedimiento matemático

(algoritmo) conocido como método símplex. El objetivo de este tema es

presentar paso a paso el método símplex y de algunas de las condiciones

especiales que pueden encontrarse cuando se utiliza el método simplex.

Mtra. Maribel Beltrán Castelo Investigación de Operaciones I

• Repaso Caso Agro Tech Inc.

Planteamiento del problema

1) Variables de decisión:

X1 = Toneladas del fertilizante de 5-5-10 que se fabrican

X2 = Toneladas del fertilizante de 5-10-5, que se fabrican

2) Función objetivo:

• MAXIMIZAR: Z = 18.5 X1 + 20X2

3) Restricciones:

SUJETO A: 0.05X1 + 0.05X2 1100 Nitrato

0.05X1 + 0.10X2 1800 Fosfato

0.10X1 + 0.05X2 2000 Potasio

4) Restricción de no negatividad:

X1, X2 0


• Repaso Caso Agro Tech Inc.

Método gráfico:

1) Encontrar cruces con los ejes de las restricciones (dando

valor cero a cada variable de cada restricción)

2) Graficar cada restricción con su respectiva dirección de

barrido ( hacia donde barre)

3) Delimitar la región factible ( de acuerdo a los barridos de las

restricciones )

4) Encontrar los puntos (coordenadas) de los vértices

5) Sustituir cada par de puntos en la función objetivo

6) Encontrar los cruces con los ejes de función objetivo(dando

valores arbitrarios a la igualación de la función objetivo para

encontrar los cruces en los ejes)

7) Graficar las rectas de isoutilidad con su respectiva dirección

de barrido ( hacia donde barre)

8) Identificar el punto óptimo y proporcionar cuanto vale la

función objetivo de este punto.


• Repaso: Glosario

• Base: conjunto de variables básicas que constituyen una solución

básica factible. cj: coeficiente de la j-ésima variable en la función

objetivo. Con frecuencia se le denomina contribución por unidad.

• cj - zj : contribución neta por unidad asociada con la j-ésima variable.

En la tabla refleja el cambio neto en la función objetivo de un cambio

unitario de Xj .

• Columna que entra: columna asociada con la variable que debe

introducirse en la base para mejorar la solución.

• Críterios de optimidad: condición que existe en el proceso tubular,

asociada con un problema de maximización, y en la que todos los

coeficientes del renglón (cj - zj ) son cero o negativos.

• Degeneración: condición que ocurre en (1) una tabla símplex durante

el proceso de pivoteo si se obtiene un empate al determinar la

variable que debe eliminarse de la base y (2) en la tabla final cuando

las variables básicas no son estrictamente positivas.



• Elemento pivote: elemento que se encuentra en la intersección de la

columna que entra y el renglón que sale. Se utiliza para actualizar la

tabla en el método símplex.

• Enfoque algebraico: procedimiento iterativo que permite la sustitución

y la solución de ecuaciones simultaneas para obtener la solución

óptima de un problema de PL.

• Método símplex: procedimiento iterativo que da una solución óptima a

un problema de PL. El método emplea la lógica del enfoque

algebraico, pero utiliza una estructura tabular para ayudar en el

proceso de solución.

• Optimo alternativos: solución alternativa a un problema de PL;

puédese identificar en la tabla por la presencia de un cero en el

renglón (cj - zj ) bajo una variable no básica.



• Renglón que sale: se refiere al renglón asociado con la variable que

debe eliminarse de la base para dar lugar a la variable que entra.

• Restricciones incosistentes: condición que ocurre en la tabla simplex

si se llega al óptimo, pero una variable artificial permanece en la base

a un nivel positivo.

• Segundo término negativo: condición que existe cuando se dan

valores negativos en el segundo término (o lado derecho) de las

restricciones asociadas con un problema de PL. Éstas deben

convertirse en valores positivos antes de aplicar el método simplex.

• Solución básica: solución en la que todas las variables no básicas se

igualan a cero cuando se despejan m variables en términos de las n-

m variables restantes. No se restringen los signos de las variables en

la solución; son aceptables valores tanto positivos como negativos.

• Solución factible básica: solución básica en la cual todos los valores

de las variables de la solución son mayores o iguales que cero.



• Solución no acotada: condición que ocurre en la tabla simplex cuando

se detiene el método porque no existen coeficientes positivos en la

columna que entra.

• Variable artificial: variable que se utiliza en el método simplex para

ayudar a identificar una solución factible básica inicial.

• Variable básica: una de las m variables que se utilizan para resolver

un problema de PL.

• Variable no básica: una de la n-m variables que se igualan a cero al

resolver un problema de PL. zj: contribución que se pierde por unidad

para la j-ésima variable en el problema . En la tabla ésta representa la

porción del valor objetivo de la solución básica que se tiene y a la cual

se debe renunciar para fabricar una unidad de xj.



• MÉTODO SÍMPLEX

– Conversión de desigualdades a igualdades:

• Variables de holgura (añadir una variable S1 cuando tengamos )

Sobrante.

6X1 + 5X2 30

6X1 + 5X2 + S1 = 30

• Variable de excedente (restar una variable S2 cuando tengamos )

Faltante

10X1 + 2X2 50

10X1 + 2X2 - S2 = 50




Caso Agro Tech Inc.

S1 es la cantidad (en toneladas) de nitrato que no se usa

S2 es la cantidad (en toneladas) de fosfato que no se emplea

S3 es la cantidad (en toneladas) de Potasio que no se utiliza

– Problema de los fertilizantes.

MAX 18.5X1 + 20.0X2+ 0S1 + 0S2+ 0S3

S.T. 0.05X1 + 0.05X2 + 1S1 + 0S2 + 0S3 = 1,100

0.05X1 + 0.10X2 + 0S1+ 1S2 + 0S3 = 1,800

0.10X1 + 0.05X2 + 0S1 + 0S2+ 1S3 = 2,000

– Queremos la solución del sistema de tres ecuaciones que

maximiza la función objetivo.



MÉTODO SÍMPLEX

Todas las soluciones básicas para el Caso Agro Tech Inc.

n! .

m! (n – m )!

m = # ecuaciones

n = # variables

5! / 3! ( 5-3)! = 5! / 3! ( 2!) = 10 soluciones básicas

SOLUCIÓN X1 X2 S1 S2 S3 Z

1

2

3

4

5

6

7

8

9

10

0

0

0

0

36,000

20,000

22,000

8,000

18,000

14,667

0

22,000

18,000

40,000

0

0

0

14,000

4,000

10,667

1,100

0

200

-900

-700

100

0

0

0

-167

1,800

-400

0

-2,200

0

800

900

0

500

0

2,000

900

1,100

0

-1,600

0

-200

500

0

0

$0

No-factible

$360,000

No-factible

No-factible

$370,000

No-factible

$428,000

$413,000

No-factible


PROGRAMACIÓN LINEAL • MÉTODO SÍMPLEX


X1

X2

3

2

4

5

1

10 20

10

20

30

40

30 40

8

6

7

9

10



– Obtención de soluciones básicas

“En un sistema de “m” ecuaciones y “n” variables, con n>m, si

existe solución, ésta puede encontrarse igualando (n-m) de las

variables a cero y resolviendo el conjunto restante de “m”

ecuaciones y “m” variables”.




– Obtención de soluciones básicas

• Variables no-básicas: las que se igualan a cero.

• Variables básicas: las que se determinan resolviendo el

sistema.

Ejemplo: si X1=0, X2=0, la solución básica es:

X1=0; X2=0; S1=1,100; S2=1,800; S3=2,000;

Z=0.

– ¿Cuántas soluciones básicas hay?



MÉTODO SÍMPLEX

◦ Procedimiento matemático

MAX 18.5X1 + 20.0X2+ 0S1 + 0S2+ 0S3

a) Solución básica factible inicial:

X1=0; X2=0; S1=1,100; S2=1,800; S3=2,000; Z=0.

b) ¿Qué variable no básica debe convertirse en básica? “X2” contribuye más a las utilidades, ósea tiene mayor coeficiente

c) ¿Qué tan grande puede ser “X2”?

X2 1,100/0.05 = 22,000

X2 1,800/0.10 = 18,000

X2 2,000/0.05 = 40,000

¡ X2 = 18,000!




– Procedimiento matemático

d) Se hace X2=18,000. La segunda solución básica

factible será:

X1=0; X2=18,000; S1=200; S2=0; S3=1,100;

Z=$360,000.

e) Etc..

– Procedimiento tabular: se elabora la tabla inicial para el

origen y se cambia de una solución básica factible a otra

hasta encontrar la óptima.




– Tabla Símplex inicial (1) Caso Agro Tech Inc.

Cj

18.5

20.0

0

0

0

CONTRIBUCIÓN

POR UNIDAD

Cb

BASE

SEGUNDO

TÉRMINO

(solución)

X1

X2

S1

S2

S3

ENCABEZADOS

Y VARIABLES

0

0

0

S1

S2

S3

1100

1800

2000

0.05

0.05

0.10

0.05

0.10

0.05

1

0

0

0

1

0

0

0

1

COEFICIENTES

Zj

0

0

0

0

0

0

CONTRIBUCIÓN

QUE SE PIERDE

Cj - Zj

18.5

20.0

0

0

0

CONTRIBUCIÓN

NETA


Coeficientes en la función objetivo

Suma (Base x Cb) utilidad

Suma ( Cb x X1)

Suma ( Cb x X2)

Suma ( Cb x S1)

Suma ( Cb x S2)

Suma ( Cb x S3)

Intersección


– Procedimiento tabular

• Verificar el renglón Cj-Zj. Si tiene algún valor positivo la

solución no es óptima. Se escoge el mayor valor positivo y la

variable correspondiente pasa a ser básica.

X1 X2 * S1 S2 S3

cj-zj 18.5 20 0 0 0

• ¿Qué variable de la base debe retirarse? Se dividen los valores

del “segundo término” por los coeficientes positivos de la

variable “Xi” seleccionada en el paso anterior. El menor

resultado indica qué variable deja de ser básica.

S1 = 1,100/ 0.05 = 22,00

S2 = 1,800/ 0.10 = 18,000 * menor valor

S3 = 2,000/ 0.05 = 40,000

• Realizar el pivoteo: “pivote es el elemento que se encuentra

en la intersección de la columna de la variable que entra y el

renglón de la variable que sale”. = .10

Se divide entonces el renglón que sale entre el pivote. El

renglón resultante se denomina reemplazante.

1,800/ 0.10 = 18,000 0.05/0.10 = .5 0.10/0.10 = 1




– Procedimiento tabular

• Multiplicar el elemento intersección en el renglón antiguo por los

elementos correspondientes en el renglón reemplazante y restar el

resultado del renglón antiguo. “Elemento intersección es aquél que

se encuentra en la intersección de la columna de la variable que

entra y el renglón que se está considerando”.

(ANTIGUO)-(INTERSECCIÓN)(REEMPLAZANTE)=NUEVO

Renglón 1 Renglón 3

A =1,100 – (0.05) (18,000) = 200 A =2,000 – (0.05) (18,000) = 1100

B= 0.05 – (0.05) (0.5) =0.025 B= 0.10 – (0.05) (0.5)

=0.075

C= 0.05 – (0.05) (1) = 0 C= 0.05 – (0.05) (1) = 0

D= 1 – (0.05) (0) = 1 D= 0 – (0.05) (0) = 0

E= 0 – (0.05) (10) =-0.5 E= 0 – (0.05) (10) =-.5

F= 0 – (0.05) (0) =0 F= 1 – (0.05) (0) =1

• Actualizar los coeficientes de CB.

• Actualizar el renglón Zj.

• Actualizar el renglón Cj-Zj.

• Repetir el procedimiento a partir del paso #2. Mtra. Maribel Beltrán Castelo Investigación de Operaciones I



– Tabla Símplex (2) Caso Agro Tech Inc.

Cj

18.5

20.0

0

0

0

CONTRIBUCIÓN

POR UNIDAD

Cb

BASE

SEGUNDO

TÉRMINO

(solución)

X1

X2

S1

S2

S3

ENCABEZADOS

Y VARIABLES

0

20.0

0

S1

X2

S3

200

18,000

1,100

0.025

0.5

0.075

0

1

0

1

0

0

-0.5

10

-0.5

0

0

1

COEFICIENTES

Zj

360,000

10

20

0

200

0

CONTRIBUCIÓN

QUE SE PIERDE

Cj - Zj

8.5

0

0

-200

0

CONTRIBUCIÓN

NETA




– Tabla Símplex óptima Caso Agro Tech Inc.

Es la solución óptima: Todos los valores del renglón cj- zj son

cero o negativos.

Cj

18.5

20.0

0

0

0

CONTRIBUCIÓN

POR UNIDAD

Cb

BASE

SEGUNDO

TÉRMINO

(solución)

X1

X2

S1

S2

S3

ENCABEZADOS

Y VARIABLES

18.5

20.0

0

X1

X2

S3

8000

14000

500

1

0

0

0

1

0

40

-20

-3

-20

20

1

0

0

1

COEFICIENTES

Zj

428000

18.5

20.0

340

30

0

CONTRIBUCIÓN

QUE SE PIERDE

Cj - Zj

0

0

-340

-30

0

CONTRIBUCIÓN

NETA




Para el caso de minimización solo existen dos

consideraciones:

1. Que entre variables a la base con números más

negativos.

2. La Solución óptima serán cuando existan en cj-zj

números ceros o positivos.




Variaciones en el método simplex:

*Otra manera de proceder para solucionar un problema

de minimización por el método símplex es cambiar solo

la función objetivo por Maximización multiplicando esta

por (-1).

*Cuando los segundos términos son negativos: (Se

tienen que cambiar los signos de la restricción y los

signos de la desigualdad.

2x1 -4x2 = -8 -2x1 + 4x2 = 8

3x1 -5x2 ≤ -2 -3x1 + 5x2 ≥ 2

2x1 -9x2 ≥ -7 -2x1 + 9x2 ≤ 7

–





* Variable artificiales: Estas variables se utilizan en el método simplex sólo

como auxiliares para identificar una solución factible básica inicial para el

problema. Estas variables son necesarias cuando un problema contiene

restricciones de mayor que o igual a (≥) y de igualdad (=). Las variables

artificiales se utilizan para completar la matriz identidad, y de esta manera

permitir una solución inicial.

Max Z= -30x1 – 10x2 + 0s1 +s2

sujeto a: 2x1 + 4x2 + s1+ 0s2 = 80 ( X1 =0, X2 =0, S1 =80)

x1 + x2 + 0s1 + 0s2 = 25 (0 = 25, NO ARRANCA)

8X1 + 6X2 + 0S1- 1S2 =120 ( NO TIEN QUE SE NEGATIVO)

x1,x2,s1,s2 ≥ 0

–





* Variable artificiales: Para asegurar que estas variables no tengas valores

al final de tabla, sus coeficientes en la función objetivo son negativos y son

10 veces mayor coeficiente que aparece en la función objetivo.

Para nuestro caso el máximo es 30, multiplicado por 10 son -300

Max Z= -30x1 – 10x2 + 0s1 +s2 -300A1 – 300A2

sujeto a: 2x1 + 4x2 + s1+ 0s2 + 0A1 + 0A2 = 80

x1 + x2 + 0s1 + 0s2 + 1A1 + 0A2 = 25

8X1 + 6X2 + 0S1- 1S2 + 0A1 + 1A2 =120

x1,x2,s1,s2,A1,A2 ≥ 0



• VARIACIONES DEL SÍMPLEX – VARIABLES ARTIFICIALES

TABLA SIMPLEX INICIAL

Cj

-30

-10

0

0

-300

-300

Cb

BASE

SEGUNDO

TÉRMINO

(solución)

X1

X2

S1

S2

A1

A2

0

-300

-300

S1

A1

A2

80

25

120

2

1

8

4

1

6

1

0

0

0

0

-1

0

1

0

0

0

1

Zj

-43,500

-2,700

-2,100

0

300

-300

-300

Cj - Zj

2,670

2,090

0

-300

0

0



Ejemplo de la Agrotech:

MAXIMIZAR: Z = 18.5 X1 + 20X2

SUJETO A: 0.05X1 + 0.05X2 1100 Nitrato

0.05X1 + 0.10X2 1800 Fosfato

0.10X1 + 0.05X2 2000 Potasio

END

OBJECTIVE FUNCTION VALUE

1) 428000.0

VARIABLE VALUE REDUCED COST

X1 8000.000000 .000000

X2 14000.000000 .000000

ROW SLACK OR SURPLUS DUAL PRICES

2) .000000 340.000000

3) .000000 30.000000

4) 500.000000 .000000

NO. ITERATIONS= 2



Continuación…3. MÉTODO SÍMPLEX

Interpretación de LINDO

Problema de la Agrotech:

* Se divide en dos partes:

1) Solución

2) Análisis de sensibilidad



1) 428000.0


X1 8000.000000 .000000

X2 14000.000000 .000000


2) .000000 340.000000

3) .000000 30.000000

4) 500.000000 .000000

NO. ITERATIONS= 2

RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 18.500000 1.500000 8.500000 X2 20.000000 17.000000 1.500000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 1100.000000 166.666700 200.000000 3 1800.000000 400.000000 500.000000 4 2000.000000 INFINITY 500.000000

MÉTODO SÍMPLEX


Problema de la Agrotech:


1) 428000.0


X1 8000.000000 .000000

X2 14000.000000 .000000


2) .000000 340.000000

3) .000000 30.000000

4) 500.000000 .000000

NO. ITERATIONS= 2



1. Por cada unidad que se le de a una variable que

tenga valor 0, se producirá un daño. Por algo Lindo no

le da valores a algunas variables porque no conviene

producirlo.

2. Cuando las variables tienen valor 0: en la

columna de ¨reduced cost¨ tienen un valor.

Puede ser daño o beneficio. Si se está

maximizando y es positivo el beneficio aumenta y si es

negativo el daño disminuye. Si se está

minimizando y es positivo el beneficio disminuye si es

negativo el daño aumenta. Todo repercute en la

función objetivo

3.Sobrante, porque se agregó una variable de holgura



*Existen problemas standard: Cuando tienen en Zj y en Cj – Zj los

mismos valores ej. MAX 2X1 + 4X2

SUBJECT TO

2) 4X1 + 3X2 ≤ 400

3) 5X1 + 10X3 ≤ 100

* Existen problemas no standard:

MAX 3X1 + 2X2 - 7X3

SUBJECT TO

2) X1 - X2 >= 0

3) X1 + 4X3 <= 5

4) 12X2 - 8X3 >= 20

END


1) 25.00000


X1 5.000000 .000000

X2 5.000000 .000000

X3 .000000 27.000000


2) .000000 -2.000000

3) .000000 5.000000

4) 40.000000 .000000

NO. ITERATIONS= 3 Mtra. Maribel Beltrán Castelo Investigación de Operaciones I




Corrida ejemplo #1:

MAX 3X1 + 2X2 - 7X3

SUBJECT TO

2) X1 - X2 >= 0

3) X1 + 4X3 <= 5

4) 12X2 - 8X3 >= 20

END

Si el lado derecho de la restricción aumenta una unidad:

El valor de la función objetivo disminuirá lo que tenga esa restricción en el

¨dual prices¨ en este caso 2.


1) 25.00000


X1 5.000000 .000000

X2 5.000000 .000000

X3 .000000 27.000000


2) .000000 -2.000000

3) .000000 5.000000

4) 40.000000 .000000

NO. ITERATIONS= 3



MÉTODO SÍMPLEX


Corrida ejemplo #2:

MAX 3X1 + 2X2 - 7X3

SUBJECT TO

2) X1 - X2 >= 1

3) X1 + 4X3 <= 5

4) 12X2 - 8X3 >= 20

END


1) 23.00000


X1 5.000000 .000000

X2 4.000000 .000000

X3 .000000 27.000000


2) .000000 -2.000000

3) .000000 5.000000

4) 28.000000 .000000

NO. ITERATIONS= 3



MÉTODO SÍMPLEX


Corrida ejemplo #3:

MIN 3X1 + 2X2 - 7X3

SUBJECT TO

2) X1 - X2 >= 0

3) X1 + 4X3 <= 5

4) 12X2 - 8X3 >= 20

END

Si el lado derecho de la restricción aumenta una unidad,

como es minimización:

El valor de la función objetivo aumentará lo que tenga esa restricción en

el ¨dual prices¨ en este caso 3.785714


1) 5.714286


X1 2.142857 .000000

X2 2.142857 .000000

X3 .714286 .000000


2) .000000 -3.785714

3) .000000 .785714

4) .000000 -.482143

NO. ITERATIONS= 3



MÉTODO SÍMPLEX


Corrida ejemplo #4:

MIN 3X1 + 2X2 - 7X3

SUBJECT TO

2) X1 - X2 >= 1

3) X1 + 4X3 <= 5

4) 12X2 - 8X3 >= 20

END


1) 9.500000


X1 3.000000 .000000

X2 2.000000 .000000

X3 .500000 .000000


2) .000000 -3.785714

3) .000000 .785714

4) .000000 -.482143

NO. ITERATIONS= 3



• PROBLEMAS ESPECIALES

– PROBLEMA NO ACOTADO

MAX X1 + X2

SUBJECT TO

2) - X1 + X2 <= 2

3) X1 - X2 <= 2

END

UNBOUNDED SOLUTION AT STEP 1 REDUCED COST= -2.00000

UNBOUNDED VARIABLES ARE:

X2

X1


1) .9999990E+08


X1 99999900.000000 .000000

X2 99999900.000000 3.000000


2) 4.000000 .000000

3) .000000 1.000000

Para estos problemas falta una restricción o se olvidaron de recursos importantes a considerar.

El valor de la función objetivo es infinita. Lindo manda una señal de UNBOUNDED SOLUTION .



• PROBLEMAS ESPECIALES – PROBLEMA INCONSISTENTE

MAX X1 + X2

SUBJECT TO

2) X1 + X2 >= 2

3) X1 + X2 <= 1

END

NO FEASIBLE SOLUTION AT STEP 1

SUM OF INFEASIBILITIES= 1.00000

VIOLATED ROWS HAVE NEGATIVE SLACK,

OR (EQUALITY ROWS) NONZERO SLACKS.

ROWS CONTRIBUTING TO INFEASIBILITY

HAVE NONZERO DUAL PRICE.


1) 1.000000


X1 1.000000 .000000

X2 .000000 .000000


2) -1.000000 -1.000000

3) .000000 1.000000

El problema no tiene región factible . Las restricciones son incompatibles. Lindo manda un el siguiente mensage: NO

FEASIBLE SOLUTION



• PROBLEMAS ESPECIALES – DEGENERACIÓN

MIN X1 + 3X2

SUBJECT TO

2) X1 + X2 >= 1

3) 2X1 + 3X2 >= 2

END


1) 1.000000


X1 1.000000 .000000

X2 .000000 2.000000


2) .000000 -1.000000

3) .000000 .000000

Cuando una variable de la base tenga cero, es un problema degenerado.



• PROBLEMAS ESPECIALES

– DEGENERACIÓN

Cj

-1

-3

0

0

-100

-100

CONTRIBUCIÓN

POR UNIDAD

Cb

BASE

SEGUNDO

TÉRMINO

(solución)

X1

X2

S1

S2

A1

A2

ENCABEZADOS

Y VARIABLES

-1

0

X1

S2

1

0

1

0

1

-1

-1

-2

0

1

1

2

0

-1

COEFICIENTES

Zj

-1

-1

-1

1

0

-1

0

CONTRIBUCIÓN

QUE SE PIERDE

Cj - Zj

0

-2

-1

0

-99

-100

CONTRIBUCIÓN

NETA



• PROBLEMAS ESPECIALES – PROBLEMAS CON SOLUCIONES MÚLTIPLES


1) 2650.000


X1 1400.000000 .000000

X2 500.000000 .000000

X3 .000000 .000000

X4 200.000000 .000000

X5 550.000000 .000000


2) .000000 -1.000000

3) .000000 -.500000

4) .000000 -.500000

5) .000000 -.500000

Se puede obtener muchas soluciones con la misma función objetivo, ya que toma

diferentes valores las variables óptimas y aun así la función objetivo mantiene su valor y

tiene ojo de serpiente.



• ANÁLISIS DE SENSIBILIDAD

– Preguntas típicas:

1. Cambio en la función objetivo del coeficiente de una variable no

básica.

2. Cambio en la función objetivo del coeficiente de una variable

básica.

3. Cambio en el nivel de un recurso (lado derecho).

4. Cambio obligado en el valor de una variable no básica.

5. Restricción adicional.




– Agrotech modificado: planteamiento

MAX 18.5X1 + 20.0X2 + 14.5X3

ST 0.05X1 + 0.05X2 + 0.05X3 <= 1,100

0.05X1 + 0.10X2 + 0.05X3 <= 1,800

0.10X1 + 0.05X2 + 0.05X3 <= 2,000

END




– Agrotech modificado: tabla inicial

Cj

18.5

20.0

14.5

0

0

0

CONTRIBUCIÓN

POR UNIDAD

Cb

BASE

SEGUNDO

TÉRMINO

(solución)

X1

X2

X3

S1

S2

S3

ENCABEZADOS

Y VARIABLES

0

0

0

S1

S2

S3

1100

1800

2000

0.05

0.05

0.10

0.05

0.10

0.05

0.05

0.05

0.05

1

0

0

0

1

0

0

0

1

COEFICIENTES

Zj

0

0

0

0

0

0

0

CONTRIBUCIÓN

QUE SE PIERDE

Cj - Zj

18.5

20

14.5

0

0

0

CONTRIBUCIÓN

NETA




– Agrotech modificado: tabla óptima

Cj

18.5

20.0

14.5

0

0

0

CONTRIBUCIÓN

POR UNIDAD

Cb

BASE

SEGUNDO

TÉRMINO

(solución)

X1

X2

X3

S1

S2

S3

ENCABEZADOS

Y VARIABLES

18.5

20.0

0

X1

X2

S3

8000

14000

500

1

0

0

0

1

0

1

0

-0.05

40

-20

-3

-20

20

1

0

0

1

COEFICIENTES

Zj

428000

18.5

20.0

18.5

340

30

0

CONTRIBUCIÓN

QUE SE PIERDE

Cj - Zj

0

0

-4.0

-340

-30

0

CONTRIBUCIÓN

NETA




– Corrida de LINDO Agrotech modificado


1) 428000.0


X1 8000.000000 .000000

X2 14000.000000 .000000

X3 .000000 4.000000


2) .000000 340.000000

3) .000000 30.000000

4) 500.000000 .000000

NO. ITERATIONS= 2




– Corrida de LINDO de Agrotech modificado

RANGES IN WHICH THE BASIS IS UNCHANGED:

OBJ COEFFICIENT RANGES

VARIABLE CURRENT ALLOWABLE ALLOWABLE

COEF INCREASE DECREASE

X1 18.500000 1.500000 4.000000

X2 20.000000 17.000000 1.500000

X3 14.500000 4.000000 INFINITY

RIGHTHAND SIDE RANGES

ROW CURRENT ALLOWABLE ALLOWABLE

RHS INCREASE DECREASE

2 1100.000000 166.666700 200.000000

3 1800.000000 400.000000 500.000000

4 2000.000000 INFINITY 500.000000




1. Cambio en el coeficiente de una variable no-básica

Cj

18.5

20.0

14.5+3

0

0

0

CONTRIBUCIÓN

POR UNIDAD

Cb

BASE

SEGUNDO

TÉRMINO

(solución)

X1

X2

X3

S1

S2

S3

ENCABEZADOS

Y VARIABLES

18.5

20.0

0

X1

X2

S3

8000

14000

500

1

0

0

0

1

0

1

0

-0.05

40

-20

-3

-20

20

1

0

0

1

COEFICIENTES

Zj

428000

18.5

20.0

18.5

340

30

0

CONTRIBUCIÓN

QUE SE PIERDE

Cj - Zj

0

0

3-4.0

-340

-30

0

CONTRIBUCIÓN

NETA

3 <= 4, no cambia la base; 3 > 4, hay que volver a iterar




1. Cambio en el coeficiente de una variable no-básica

¿Qué pasa si el coeficiente de X3 es 16? (cumple el rango)

X3 = 16 -14.5 = 1.5 1.5 ≤ 4 INFINIT≤ x3 ≤ 4.0

Base: No cambia

Solución: No cambia

Función objetivo: No cambia, Porque la tabla sigue siendo óptima.

¿Qué pasa si el coeficiente de X3 es 22? (no cumple el rango)

X3 = 22 -14.5 = 7.5 7.5 ≤ 4

Base: Cambia

Solución: Cambia

Función objetivo: Cambia, Porque tenemos que volver a iterar.




2. Cambio en el coeficiente de una variable básica

Cj

18.5+1

20.0

14.5

0

0

0

Cb

BASE

SEGUNDO

TÉRMINO

(solución)

X1

X2

X3

S1

S2

S3

18.5+1

20.0

0

X1

X2

S3

8000

14000

500

1

0

0

0

1

0

1

0

-0.05

40

-20

-3

-20

20

1

0

0

1

Zj

428000+

80001

18.5+1

20.0

18.5+1

340+401

30-201

0

Cj - Zj

0

0

-4.0-1

-340-401

-30+201

0

-4<=1<=1.5, no cambia la base; 1< -4 ó 1>1.5, hay que volver a iterar




2. Cambio en el coeficiente de una variable básica

¿Qué pasa si el coeficiente de X1 es 15.5? (cumple el rango)

1 = 15.5 -18.5 = -3 -3 esta dentro del rango -4<=1<=1.5

Base: No cambia

Solución: No cambia

Función objetivo: Cambia, 428,000 + 8000 (-3) = 404,000

¿Qué pasa si el coeficiente de X2 es 40? (no cumple el rango)

2 = 40 -20 = 20 20 esta fuera de rango 17<=1<=-1.5

Base: Cambia

Solución: Cambia

Función objetivo: Cambia, Porque hay que volver a iterar.

Nota: si estás en los límites se puede hacer cero y puede haber ojos

de serpiente ya que se convierte en un problema de opción múltiple.




3. Cambio en el lado derecho de una restricción

Cj

18.5

20.0

14.5

0

0

0

CONTRIBUCIÓN

POR UNIDAD

Cb

BASE

SEGUNDO

TÉRMINO

(solución)

X1

X2

X3

S1

S2

S3

ENCABEZADOS

Y VARIABLES

18.5

20.0

0

X1

X2

S3

8000+40N

14000-20N

500-3N

1

0

0

0

1

0

1

0

-0.05

40

-20

-3

-20

20

1

0

0

1

COEFICIENTES

Zj

428000+

340N

18.5

20.0

18.5

340

30

0

CONTRIBUCIÓN

QUE SE PIERDE

Cj - Zj

0

0

-4.0

-340

-30

0

CONTRIBUCIÓN

NETA

-200<=N<=167, no cambia la base; N<-200 ó N>167 , hay que

volver a resolver




3. Cambio en el lado derecho de una restricción:

¿Qué pasa si cantidad de nitrato cambia a 1200? (cumple el rango)

N = 1200-1100 = 100 100 esta dentro del rango -200<=N<=167

Base: No cambia

Solución: Cambia a: X1 = 8000 + (40*100) = 12,000

X2 = 14000- (20*100) = 12,000

S3 = 500 - (3*100) = 200

Función objetivo: Cambia, Cambia, 428,000 + (340* 100) = 462,000

Nota: Si N 200 está fuera de rango, algún # de la solución se hizo (-),

la tabla deja de ser una tabla simplex, no puede iterar, como esta fuera

de rango permitido, tengo que volver a RESOLVER el problema.




Sistuaciones dentro del Análisis de Sensibilidad

ANALISIS

PREGUNTAS SENSIBLIDAD BASE SOLUCION FUNCION OPTIMA

Cambia a

Dentro de No cambia No cambia (Valor F. O. óptima + [valor óptimo de variable

Cambio rango básica * ∆ de esa variable básica en la F. O.])

variable

Fuera de Cambia Cambia Cambia

básica rango Porque hay que volver a iterar.

Dentro de No cambia No cambia No cambia

Cambio rango Sigue siendo óptima

variable

Fuera de Cambia Cambia Cambia

no básica rango Porque hay que volver a iterar.

Cambia a Cambia a

Dentro de No cambia Todos los valores de variables básicas se cambiaran a: (Valor de la F.O óptima + [(+ - valor en Zj *

Cambio rango (Valor óptimo de var. Básica + [(+ - tasa física de sust.) *( ∆ del recurso en la restricción)]

*( ∆ del recurso en la restricción)]

recurso Algún # de la solución se hizo negativo, la tabla

Fuera de deja de ser una tabla Simplex, no puedo iterar,

restricción rango como está fuera de rango permitido,

TENGO QUE VOLVER A RESOLVER el problema.

No cambia Cambia a Cambia a

Cambio Nos obligan Siguen siendo Todos los valores de variables básicas se cambiaran a: (Valor de la F.O óptima - [valor del daño *

obligado en a fabricar var. las mismas (Valor de la variable básica -[Tasa fisica de sustitución* # unidades producidas de variable no básica])

las variables no básicas variables # producidas])

Cambia Cambia No cambia

Añadir Si está Porque al agregar Porque hay un nuevo valor para la variable que entra al se mantiene el mismo valor de la función objetivo

restricción permitible una restricción agregar una nueva restricción

hay una variable nueva Corro en lindo y veo que valor tiene y lo pongo

en la base y la pongo

5. pl análisis de sensibilidad e interpretación de la solución(1)

Documents