cap tulo 5 analisis de sensibilidad y programacion …

Capıtulo 5

ANALISIS DE SENSIBILIDAD YPROGRAMACIONPARAMETRICA

Indice

1. Introduccion. . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

2. ANALISIS DE SENSIBILIDAD . . . . . . . . . . . . . . . 2

2.1. Cambios discretos en el vector de disponibilidades. . . . . . . 2

2.2. Cambios discretos en el vector de costos. . . . . . . . . . . . . 4

2.3. Cambio de un coeficiente tecnologico de una variable no basica. 6

2.4. Adicion de nuevas actividades xj . . . . . . . . . . . . . . . . 7

2.5. Adicion de nuevas restricciones . . . . . . . . . . . . . . . . . 9

2.6. Eliminacion de variables y restricciones . . . . . . . . . . . . 11

2.7. Significado del costo marginal. . . . . . . . . . . . . . . . . . 11

3. PROGRAMACION PARAMETRICA . . . . . . . . . . . 12

3.1. Introduccion a la programacion parametrica . . . . . . . . . . 12

3.2. Cambios continuos en el vector de costos. . . . . . . . . . . . 12

3.3. Cambio continuo en el vector de disponibilidades. . . . . . . . 16

3.4. Cambio continuo en una columna de coeficientes tecnologicosno basica. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

4. Precios sombra . . . . . . . . . . . . . . . . . . . . . . . . . . 20

0

En este tema veremos en que consiste el analisis de sensibilidad y estudiaremostodos los cambios discretos que se pueden producir en los parametros de un problemade programacion lineal.

1. Introduccion.

Una vez resuelto un problema de programacion lineal, puede darse el caso de queuno o varios de los parametros de entrada del problema original cambien, dando origena un nuevo problema.

Afortunadamente en este caso no es necesario volver a resolver el problema desde elprincipio, sino que existen los metodos llamados de analisis de sensibilidad que nospermiten resolver el nuevo problema a partir de la tabla optima del problema original.

El nuevo problema puede diferir del original en uno o varios de los siguientes cam-bios:

a) cambios en ~b (vector de disponibilidades)

b) cambios en ~c (vector de costos o precios unitarios)

c) cambios en A (matriz de coeficientes tecnologicos)

d) cambios en ~x (aumento o disminucion del numero de actividades)

e) cambios en el numero de restricciones (aumento o disminucion)

Los tres primeros cambios pueden ocurrir de una forma discreta o continua. Deforma discreta significa que una o varios de los valores originales, son reemplazados pornuevos valores. El cambio continuo es aquel en el que los vectores Aj, ~c o ~b varıan dela forma:

~b+ θ∆b, −∞ < θ <∞

~c+ θ∆c, −∞ < θ <∞

Aj + θ∆Aj, −∞ < θ <∞

El analisis de sensibilidad que estudia los cambios continuos es lo que llamamosPROGRAMACION PARAMETRICA.

Vamos a hacer el analisis de sensibilidad para los cambios discretos. Recordemosque en la matriz A encajabamos una identidad A = (A, I):

xBkxB ~cB otras variables variables de la base inicial

B−1~b ~cB B−1A B−1

z = ~cBB−1~b ~c− ~cBB−1A ~c− ~cBB−1

1

2. ANALISIS DE SENSIBILIDAD

2.1. Cambios discretos en el vector de disponibilidades.

Consideremos el problema original (PO), cuya solucion conocemos:

Max z = ~c · ~xs. a. A~x ≤ ~b

~x ≥ 0

Si cambiamos el vector ~b por ~b+ ∆b el nuevo problema sera:

(NP) Max z = ~c · ~xs. a. A~x ≤ ~b+ ∆b

~x ≥ 0

Entonces, si B−1 es la inversa de la base optima del PO, entonces, la solucion optimadel PO vendra dada por:

~xB = B−1 · b ≥ 0, z = ~cB · ~xB.

Al hacer el cambio, obtendremos otro vector ~xB, de la forma:

~xB = B−1(b+ ∆b)

Entonces, si ~xB ≥ 0, significa que ~xB es la solucion del NP.En caso contrario, significa que ~xB no es factible, y por lo tanto habra que aplicar elmetodo dual del simplex para restaurar la factibilidad y por lo tanto la optimalidad enel NP.

El dual del simplex debe aplicarse a la tabla optima del problema original en laque previamente se habra cambiado la columna ~xB = B−1 · ~b, por la nueva columna~xB = B−1(b+ ∆b).

Ejemplo. Sea el problema original:Tenemos que producir un volumen X de un producto quımico A, que se vende a5u.m./litro, y otro volumen Y de un producto B que se vende a $3/litro. Contamos conun maximo de 15 trabajadores y el costo de produccion no puede exceder los 10u.m.por hora de trabajo. Los coeficientes tecnologicos son los siguientes:

A B

personal 3 5costo produccion 5 2

¿Como obtendrıamos el maximo beneficio?

Solucion.-Max z = 5x1 + 3x2s. a: 3x1 + 5x2 ≤ 15

5x1 + 2x2 ≤ 10xi ≥ 0

tabla inicial:

2

xBkxB cB x1 x2 x3 x4

15 x3 0 3 5 1 010 x4 0 5 2 0 1

z = 0 5 3 0 0

tabla optima:


45/19 x2 3 0 1 5/19 -3/1920/19 x1 5 1 0 -2/19 5/19

z = 235/19 0 0 -5/19 -16/19

~x =

(~xB

~xN

)=

x1x2

x3x4

=

20/1945/19

00

y B−1 =

(5/19 −3/19−2/19 5/19

)

a) Supongamos ahora que por una depresion economica, el numero de trabajadoresha de reducirse a 5, y el costo maximo de produccion a 5u.m. por hora.

El nuevo vector de disponibilidad de recursos sera: ~b+∆b =

(1510

)+

(−10−5

)=

(55

)y el nuevo problema sera:

(N.P.) Max z = 5x1 + 3x2s. a: 3x1 + 5x2 ≤ 5

5x1 + 2x2 ≤ 5xi ≥ 0

En lugar de resolver todo el problema de nuevo, estudiaremos la factibilidad delnuevo vector: ~xB = B−1(~b+ ∆b).

~xB = B−1(~b+ ∆b) =

(5/19 −3/19−2/19 5/19

)·(

55

)=

(10/1915/19

)≥ 0

Luego este vector es optimo, y la solucion optima del nuevo problema es:

x1 = 15/19, x2 = 10/19, con z = ~cB · ~xB = (3, 5) ·(

10/1915/19

)=

30 + 75

19=

105

19.

b) Supongamos ahora que aunque el personal se reduce a 10 personas, el costomaximo por hora se aumenta a 20u.m.

En este caso el nuevo problema sera:

(N.P.) Max z = 5x1 + 3x2s. a: 3x1 + 5x2 ≤ 10

5x1 + 2x2 ≤ 20xi ≥ 0

Entonces: ~xB = B−1(~b+ ∆b) =

(5/19 −3/19−2/19 5/19

)·(

1020

)=

(−10/1980/19

).

Como ~xB no es ≥ 0, habra que usar el metodo Dual del Simplex para obtener la nuevasolucion optima.

Construimos la tabla con el nuevo vector xB en lugar del anterior xB.

3


-10/19 x2 3 0 1 5/19 -3/1980/19 x1 5 1 0 -2/19 5/19

z = 370/19 0 0 -5/19 -16/19

10/3 x4 0 0 -19/3 -5/3 110/3 x1 5 1 5/3 1/3 0

z= 50/3 0 -16/3 -5/3 0

Luego, la solucion optima en este caso es x1 = 10/3 y z = 50/3.Notese que:

- la produccion de 10/3 del producto A implica el costo de : 3*10/3 +5*0 =10 obreros,que son los que se tienen, por lo que la holgura x3 = 0.

- para la otra restriccion tenemos: 5*10/3 + 2*0 = 50/3 , lo que genera una holguraen el costo de produccion de: x4 = 20− 50/3 = 10/3.

2.2. Cambios discretos en el vector de costos.

Consideremos el problema original (PO), cuya solucion conocemos:

Max z = ~c · ~xs. a. A~x ≤ ~b

~x ≥ 0

Si cambiamos el vector ~c por ~c+ ∆c el nuevo problema sera:

(NP) Max z = (~c+ ∆c) · ~xs. a. A~x ≤ ~b

~x ≥ 0

El analisis de sensibilidad para este tipo de problema, toma como punto de partida, lasolucion optima del problema original. Al cambiar ~c por ~c+ ∆c, los costos marginalescj − zj, cambian a:

(cj + ∆cj)− zj = (cj + ∆cj)− (~cB + ∆cB)B−1Aj = c′j + (∆cj −∆cBB−1Aj).

En el optimo, cj − zj tiene que ser no positivo, para los j de A que no esten en la base(B) y cero para los de B.

Luego, si estas condiciones se cumplen para los elementos de la base del PO, entoncesdiremos que la base optima es la misma, y el nuevo valor de la funcion objetivo es:z = (~cB + ∆cB) · ~xB.

En caso contrario, tendremos que aplicar el metodo del Simplex hasta obtener lasolucion optima.

Ejemplo. Siguiendo con el problema original anterior:

Max z = 5x1 + 3x2s. a: 3x1 + 5x2 ≤ 15

5x1 + 2x2 ≤ 10xi ≥ 0

cuya tabla optima es:

4


45/19 x2 3 0 1 5/19 -3/1920/19 x1 5 1 0 -2/19 5/19

z = 235/19 0 0 -5/19 -16/19

a) Supongamos que el precio unitario del producto B se reduce a 1 u.m.. El nuevoproblema sera:

Max z = 5x1 + x2s. a: 3x1 + 5x2 ≤ 15

5x1 + 2x2 ≤ 10xi ≥ 0

~c+ ∆c = (5, 3, 0, 0) + (0,−2, 0, 0) = (5, 1, 0, 0).

Como cambia c2 que es el costo de una variable basica, hay que corregir los costosmarginales:


45/19 x2 1 0 1 5/19 -3/1920/19 x1 5 1 0 -2/19 5/19

z = 145/19 0 0 5/19 -22/19

Luego la solucion que tenemos no es optima; aplicando el metodo del Simplex: entraen la base x3 y sale x2, entonces


9 x3 0 0 19/5 1 -3/52 x1 5 1 2/5 0 1/5

z = 10 0 -1 0 -1

Con lo que la nueva solucion optima es: x1 = 2; x3 = 9; y z = 10.b) supongamos ahora que el precio de los dos productos es de 1 u.m., entonces el

nuevo problema sera:Max z = x1 + x2s. a: 3x1 + 5x2 ≤ 15

5x1 + 2x2 ≤ 10xi ≥ 0

~c+ ∆c = (5, 3, 0, 0) + (−4,−2, 0, 0) = (1, 1, 0, 0).Modificamos los costos marginales con lo que:


45/19 x2 1 0 1 5/19 -3/1920/19 x1 1 1 0 -2/19 5/19

z = 65/19 0 0 -3/19 -2/19

Luego la solucion del problema original sigue siendo optima, aunque varıa el valorde la funcion objetivo: z = 65/19

5

2.3. Cambio de un coeficiente tecnologico de una variable nobasica.

Solo vamos a ver los cambios en los coeficientes tecnologicos de las variables nobasicas. Si el cambio afectase a una variable basica, es aconsejable resolver el problemadesde el principio, pues, aunque existe analisis de sensibilidad para este tipo de cambios,es muy complicado.

Un cambio en el vector Aj, ocasiona un cambio en el costo marginal correspondiente,cj − zj, ya que:

c′j = cj − zj = cj − ~cBB−1Aj

Si cambiamos Aj por Aj obtendremos un nuevo coste marginal:

c′j = cj − zj = cj − ~cBB−1Aj

Mientras el nuevo coste marginal siga siendo no positivo, la solucion del problemaoriginal seguira siendo optima.

En caso contrario, habra que aplicar el metodo del Simplex hasta llegar a la solucionoptima, modificando en la tabla optima del problema original, la columna correspon-diente: Yj = B−1Aj

Ejemplo. Consideremos el problema original:

(PO) Max z = 3x1 + 5x2s. a: x1 ≤ 4

3x1 + 2x2 ≤ 18xi ≥ 0



4 x3 0 1 0 1 09 x2 5 3/2 1 0 1/2

z = 45 -9/2 0 0 -5/2

a) Supongamos que cambiamos el vector A1 =

(13

)que no es basico por A1 =

(22

).

El nuevo problema sera:Max z = 3x1 + 5x2s. a: 2x1 ≤ 4

2x1 + 2x2 ≤ 18xi ≥ 0

c′1 = c1−z1 = c1−~cBB−1A1 = 3−(0, 5)

(1 00 1/2

)(22

)= 3−(0, 5)

(21

)= 3−5 = −2 < 0

Luego la solucion optima del NP es igual a la del PO, y la tabla optima sera:

Como Y1 = B−1A1 =

(1 00 1/2

)(22

)=

(21

)y c′1 = −2.

6


4 x3 0 2 0 1 09 x2 5 1 1 0 1/2

z = 45 -2 0 0 -5/2

b) Si el cambio que hacemos consiste en tomar el nuevo A1 de la forma: A1 =

(101

),

el nuevo problema sera:

(NP) Max z = 3x1 + 5x2s. a: 10x1 ≤ 4

x1 + 2x2 ≤ 18xi ≥ 0

c′1 = c1−z1 = c1−~cBB−1A1 = 3−(0, 5)

(1 00 1/2

)(101

)= 3−(0, 5)

(101/2

)= 3−5

2=

1

2> 0

Como c′1 es mayor que cero, habra que aplicar el metodo del Simplex para llegar ala solucion optima:

la columna actualizada es: Y1 = B−1A1 =

(1 00 1/2

)(101

)=

(101/2

).


4 x3 0 10 0 1 09 x2 5 1/2 1 0 1/2

z = 45 1/2 0 0 -5/2

2/5 x1 3 1 0 1/10 044/5 x2 5 0 1 -1/20 1/2

z = 226/5 0 0 -1/20 -5/2

Por lo tanto, la nueva solucion es:

x1 = 2/5; x2 = 44/5; z = 226/5.

2.4. Adicion de nuevas actividades xj

La adicion de nuevas actividades xj, crea nuevos costos marginales c′j, y nuevascolumnas Yj en la tabla.

Si asociado a la nueva actividad xj, conocemos su precio unitario cj, y su vector decoeficientes tecnologicos Aj, los nuevos elementos se calculan como sigue:

c′j = cj − zj = cj − ~cBB−1Aj e Yj = B−1Aj.

Entonces, si el nuevo costo marginal es no positivo, la nueva variable xj, no debeentrar en la base, y su valor de utilizacion es cero. (La solucion del nuevo problema,coincide con la del PO).

En caso contrario (c′j > 0), la nueva variable xj, debe entrar en la base, y para ellolo que hacemos es anadir el vector Yj en la tabla y aplicar el metodo del Simplex hastallegar a la solucion optima.

7

Ejemplo. Consideremos el PO anterior

(PO) Max z = 3x1 + 5x2s. a: x1 ≤ 4

3x1 + 2x2 ≤ 18xi ≥ 0



4 x3 0 1 0 1 09 x2 5 3/2 1 0 1/2

z = 45 -9/2 0 0 -5/2

a) ¿Conviene producir una nueva actividad x5, cuyo precio unitario es de 7 u.m. y

sus coeficientes tecnologicos son: A5 =

(12

)?

(NP) Max z = 3x1 + 5x2 + 7x5s. a: x1 + x5 ≤ 4

3x1 + 2x2 + 2x5 ≤ 18xi ≥ 0

El nuevo costo marginal sera:

c′5 = c5−z5 = c5−~cBB−1A5 = 7−(0, 5)

(1 00 1/2

)(12

)= 7−(0, 5)

(11

)= 7−5 = 2 > 0

Como el nuevo costo marginal es mayor que cero, esto significa que la variable x5debe entrar en la base, por lo que hay que introducir su vector correspondiente en latabla y resolver el problema.

Y5 = B−1A5 =

(1 00 1/2

)(12

)=

(11

), entonces:

xBkxB cB x1 x2 x3 x4 x5

4 x3 0 1 0 1 0 19 x2 5 3/2 1 0 1/2 1

z = 45 -9/2 0 0 -5/2 2

4 x5 7 1 0 1 1 15 x2 5 1/2 1 -1 1/2 0

z = 53 -13/2 0 -2 -5/2 0

Luego, la nueva actividad debe producirse a un nivel de 4 unidades, y la actividadx2 debe reducirse de 9 a 5 unidades, con lo que se incrementa el beneficio de 45 a 53unidades.

8

b) Si en el problema anterior, el precio unitario de la nueva actividad x5 fuese de 4

u.m. y el vector A5 =

(104

), entonces, el nuevo problema serıa

(NP) Max z = 3x1 + 5x2 + 4x5s. a: x1 + 10x5 ≤ 4

3x1 + 4x2 + 2x5 ≤ 18xi ≥ 0

El nuevo costo marginal sera:

c′5 = c5−z5 = c5−~cBB−1A5 = 4−(0, 5)

(1 00 1/2

)(104

)= 4−(0, 5)

(102

)= 4−10 = −6 < 0

Luego, la solucion optima del PO lo es tambien del NP y x5 = 0.Es decir: en las condiciones actuales no se debe producir ninguna unidad de la

actividad x5.

2.5. Adicion de nuevas restricciones

Si al anadir k (k > 0) nuevas restricciones al problema original, la solucion optimade este, (~xB) las verifica todas, entonces, la solucion optima del nuevo problema es lamisma que la del problema original.

Pero si ~xB, viola alguna de las nuevas restricciones, entonces habra que restablecerla factibilidad del NP y obtener su solucion optima.

En este caso, cada una de las k restricciones debe anadirse en la tabla optimadel PO con su correspondiente variable de holgura (o artificial). Todos los vectoresunitarios asociados al PO deben restablecerse por medio de operacionesmatriciales, y luego se aplica el metodo Dual del Simplex (o el metodo del Simplex)hasta obtener una solucion optima.

Ejemplo.

Max z = 5x1 + 3x2s. a: 3x1 + 5x2 ≤ 15

5x1 + 2x2 ≤ 10xi ≥ 0



45/19 x2 3 0 1 5/19 -3/1920/19 x1 5 1 0 -2/19 5/19

z = 235/19 0 0 -5/19 -16/19

Si anadimos una restriccion de ≤.a) P. ej. consideramos una nueva restriccion: 4x1 + 3x2 ≤ 10. Esta claro que lasolucion optima del problema original no la verifica, ya que 4(20/19)+3(45/19) =215/19 = 10 + 25/19, que es mayor que 10.

9

El nuevo problema es:Max z = 5x1 + 3x2s. a: 3x1 + 5x2 ≤ 15

5x1 + 2x2 ≤ 104x1 + 3x2 ≤ 10

xi ≥ 0

Anadiendo esta ultima restriccion con su correspondiente variable de holgura ala tabla optima anterior tenemos:


45/19 x2 3 0 1 5/19 -3/19 020/19 x1 5 1 0 -2/19 5/19 0

10 x5 0 4 3 0 0 1

z = 235/19 0 0 -5/19 -16/19 0

La tabla anterior no es una tabla del Simplex. Para que lo sea, en la tercera filahay que arreglar las columnas de x1 y x2. Ası, a la fila tercera, le resto 4 veces lasegunda fila y 3 veces la primera fila. Como resultado obtengo:


45/19 x2 3 0 1 5/19 -3/19 020/19 x1 5 1 0 -2/19 5/19 0-25/19 x5 0 0 0 -7/19 -11/19 1

z = 235/19 0 0 -5/19 -16/19 0

Notese que como el costo de x5 es cero, los costos marginales permanecen igualesque los del problema original. Ahora sı que podemos aplicar el metodo Dual delSimplex: sale x5 y entra x3, con lo que la tabla queda:


10/7 x2 3 0 1 0 -4/7 5/710/7 x1 5 1 0 0 3/7 -2/725/7 x3 0 0 0 1 11/7 -19/7

z= 80/7 0 0 0 -3/7 -5/7

con lo que la solucion del nuevo problema es: x1 = 10/7, x2 = 10/7, z = 80/7.

b) Si la nueva restriccion hubiera sido: x2 ≤ 10, como la solucion optima delproblema original la verifica, entonces la solucion de ambos problemas coincide.

Si anadimos una restriccion de ≥. Multiplicando por −1 la restriccion, la trans-formamos en una de ≤ y procedemos como en el caso anterior.

Si anadimos una restriccion de =. Si la nueva restriccion no es satisfecha por lasolucion optima del problema original, tenemos dos casos:

10

a) Si se satisface con <. Por ejemplo, 4x1 + 3x2 = 12, en la solucion optima delproblema original se cumple 4x1 + 3x2 < 12. Entonces, se anade una variableartificial (con coste penalizado) a la ecuacion y se inserta en la tabla. Despues,como en casos anteriores, se restablecen los vectores unitarios. Por ultimo seaplica el metodo del Simplex.

b) Si se satisface con >. Por ejemplo, 4x1 + 3x2 = 10, en la solucion optima delproblema original se cumple 4x1 + 3x2 = 10. Entonces, se multiplica por −1 laigualdad, resultando −4x1 − 3x2 = −10 y se procede como en el apartado a).

2.6. Eliminacion de variables y restricciones

En los apartados anteriores hemos discutido la situacion de la incorporacion devariables al problema o de la adicion de nuevas restricciones, que suelen ser las situa-ciones habituales, pero tambien nos podemos plantear la eliminacion de variables o lade restricciones.

Eliminacion de variables.- el procedimiento es muy sencillo:

Si la variable es no basica: se elimina del problema sin mas.

Si es basica: la penalizamos haciendo su costo muy grande1 cj = cj + M ,de modo que termine saliendo de la base. Con lo que el problema se reducea un cambio en los costos.

Eliminacion de restricciones.- el procedimiento es analogo al anterior:

Si la restriccion no es activa para la solucion optima (tiene variable deholgura > 0), se puede eliminar sin mas.

Si es activa (variable de holgura = 0): aumentamos la disponibilidad hastaconvertirla en no activa, bi = bi + M (restriccion que no restringe), y luegola eliminamos.

2.7. Significado del costo marginal.

El valor absoluto del costo marginal, indica la cantidad en la que debe aumen-tar el costo de una variable en el caso de maximizacion para que la variablecorrespondiente entre en la base.

Ejemplo. Sea el problema

Max z = 5x1 + 3x2s. a: 3x1 + 5x2 ≤ 10

5x1 + 2x2 ≤ 20xi ≥ 0.



10/3 x1 5 1 5/3 1/3 010/3 x4 0 0 -19/3 -5/3 1

z = 50/3 0 -16/3 -5/3 0

1o muy pequeno en un problema de maximizacion

11

a)Si queremos que x2 entre en la base, el precio de x2 debe aumentarse, de 3 u.m. a:

c2 = c2 + (−c′2) = 3 + 16/3 = 25/3

3. PROGRAMACION PARAMETRICA

3.1. Introduccion a la programacion parametrica

Hasta ahora hemos estudiado el analisis de sensibilidad para los cambios discretosen los valores de un modelo de programacion lineal. Pero no todos los cambios quese pueden producir en un problema de programacion lineal son de este tipo, ya queestos valores pueden estar sujetos a cambios continuos. Este tipo de cambios es lo queestudia la PROGRAMACION PARAMETRICA.

Este tipo de planteamiento se puede dar, no solo porque los datos cambien con eltiempo, sino tambien porque muchas veces los datos de un problema son el resultadode una cierta polıtica, y nos podemos plantear entre que valores pueden variar losparametros para que la solucion que tenemos siga siendo optima.

Como ya hemos dicho, solo vamos a ver tres tipos de cambios continuos:

a) Cambios continuos en el vector de costos: c = ~c+ θ~δ

b) Cambios continuos en el vector de disponibilidades: b = ~b+ θ~β

c) Cambios continuos en los coeficientes tecnologicos de una variable no basica: Aj =Aj + θαj.

En todo lo que sigue, vamos a considerar el estudio para θ ≥ 0; en el caso de θ ≤ 0el estudio es analogo.

Es decir, estudiaremos el rango de la base optima desde el momento actual haciael futuro; el estudio hacia el pasado es analogo.

3.2. Cambios continuos en el vector de costos.

El problema a estudiar es el siguiente:

Max z = (~c+ θ~δ)~xs. a: Ax ≤ b

~x ≥ 0

Sabemos que cuando el vector parametrico de costos (~c+ θ~δ) varıa, tambien varıanlos costos marginales. Para estudiar esta variacion, establecemos la siguiente notacion:

Sea B0 la base optima asociada al problema para θ = 0, es decir:

Max z = ~c · ~xs. a: Ax ≤ b

~x ≥ 0

Entonces, los costos marginales del problema parametrico vendran dados por:

c′j = cj − zj = (cj + θδj)− (~cB0 + θ~δB0)B−10 Aj =

12

= (cj − ~cB0B−10 Aj) + θ(δj − ~δB0B

−10 Aj) = c′j + θ(δj − ~δB0B

−10 Aj)

donde, ~cB0 y ~δB0 , son las componentes de ~c y de ~δ asociadas a la base B0.La pregunta que nos hacemos es la siguiente: “¿Para que valores del parametro,

la base B0 sigue siendo optima?”Sabemos que el optimo se obtiene cuando, para todo j, c′j < 0. Por lo tanto,

estudiamos para todo j, si c′j = c′j + θ(δj − ~δB0B−10 Aj) ≤ 0.

Y de aquı se obtiene la condicion que debe cumplir el parametro para que la basesiga siendo optima.

En este caso, la base B0 sera optima para valores del parametro tales que:

θ∗ ≤ θ ≤ θ∗

En caso de que exista ninguna condicion, la base es optima para todos los valores delparametro.

Veamos que pasa fuera de ese rango. Como el estudio es analogo lo explicamospara valores de θ > θ∗:se nos pueden presentar dos casos:

1) Si θ∗ corresponde a un unico costo marginal que se anula, entonces: Aplicamos elmetodo del Simplex hasta obtener una nueva solucion optima. La base asociada aesta nueva solucion la llamamos B1.

Se puede proseguir con el mismo analisis, en el sentido de que puede existir otrovalor crıtico de θ, al que llamaremos θ∗∗, para el cual la base B1 es optima en elrango θ∗ ≤ θ ≤ θ∗∗.

2) Si θ∗ corresponde a varios costos marginales que se anulan a la vez. En este casohabra que hacer varios cambios de base por el metodo del Simplex hasta comprobarque no hay ciclos, y entonces se actua como en el caso 1, o bien se ve que no haysolucion optima finita2 para θ > θ∗.

Ejemplo. Queremos resolver el problema parametrico:

Max z = (3− 6θ)x1 + (2− 2θ)x2 + (5 + 5θ)x3s. a: x1 + 2x2 + x3 ≤ 40

3x1 + 2x3 ≤ 60x1 + 4x2 ≤ 30x1, x2, x3 ≥ 0

es decir que ~c = (3, 2, 5) y ~δ = (−6,−2, 5); con −∞ < θ <∞.

Para θ = 0, el problema es:

Max z = 3x1 + 2x2 + 5x3s. a: x1 + 2x2 + x3 ≤ 40

3x1 + 2x3 ≤ 60x1 + 4x2 ≤ 30x1, x2, x3 ≥ 0


2Esto tambien puede ocurrir en el caso 1.

13

xBkxB cB x1 x2 x3 x4 x5 x6

5 x2 2 -1/4 1 0 1/2 -1/4 030 x3 5 3/2 0 1 0 1/2 010 x6 0 2 0 0 -2 1 1

z= 160 -4 0 0 -1 -2 0

Entonces, B0 = (A2, A3, A6), N0 = (A1, A4, A5), y B−10 =

1/2 −1/4 00 1/2 0−2 1 1

¿Para que valores del parametro θ la base B0 sigue siendo optima?.Dado que hemos cambiado los costos, estudiamos los nuevos costos marginales:

c′1 = (3− 6θ)− (2− 2θ, 5 + 5θ, 0) ·

−1/43/22

= −4− 14θ ≤ 0⇔ θ ≥ −4

14=−2

7

c′4 = 0− (2− 2θ, 5 + 5θ, 0) ·

1/20−2

= −1 + θ ≤ 0⇔ θ ≤ 1 = θ∗

c′5 = 0− (2− 2θ, 5 + 5θ, 0) ·

1/41/21

= −2− 3θ ≤ 0⇔ θ ≥ −2

3

Por lo tanto, la base B0 es optima en el rango −27≤ θ ≤ 1, y en este rango, el valor

de la funcion objetivo es:

z = (cB0 + θδB0)xB0 = (2− 2θ, 5 + 5θ, 0 + 0θ)

53010

= 160 + 140θ

Veamos ahora que pasa para valores de θ > 1:En este caso sabemos que c′4 se hace positivo, por lo tanto la base actual no es

optima. Para hacer el cambio de base, entra la variable x4, y sale la variable x2, con loque la tabla optima que se obtiene es:


10 x4 0 -1/2 2 0 1 -1/2 030 x3 5+5θ 3/2 0 1 0 1/2 030 x6 0 1 4 0 0 0 1

z= 150 + 150θ −92− 27

2θ 2-2θ 0 0 −5

2− 5

2θ 0

Entonces, B1 = (A4, A3, A6), N1 = (A1, A2, A5), y B−11 =

1 −1/2 00 1/2 00 0 1

.

Nos volvemos a plantear si:¿Existe algun valor crıtico de θ, θ∗∗, para el cual la base B1 deja de ser optima?.

Volvemos a estudiar los costos marginales:

c′1 = −9

2− 27

2θ ≤ 0 siempre que θ ≥ 1

3.

14

c′2 = 2− 2θ ≥ 0, cuando θ ≥ 1, y estamos en ese caso.

c′5 = −5

2− 5

2θ ≤ 0, siempre que θ ≥ −1.

Por lo tanto, no existe θ∗∗, o lo que es lo mismo, que la base B1 es optima paracualquier valor de θ > 1.

Veamos ahora que pasa para valores de θ < −414

:En este caso sabemos que c′1 se hace positivo, por lo tanto la base actual no es optima.Para hacer el cambio de base, entra la variable x1, y sale la variable x6, con lo que latabla optima que se obtiene es:


25/4 x2 2-2θ 0 1 0 1/4 -1/8 1/845/2 x3 5+5θ 0 0 1 3/2 -1/4 -3/4

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

z= 140 + 70 θ 0 0 0 -5-13θ 4θ 2+7θ

Entonces, B2 = (A2, A3, A1), N2 = (A4, A5, A6).Nos volvemos a plantear si:

¿Existe algun valor crıtico de θ, θ∗∗, para el cual la base B2 deja de ser optima?.Volvemos a estudiar los costos marginales:

c′4 = −5− 13θ ≤ 0, cuando θ ≥ −5

13.

c′5 = 4θ ≤ 0, cuando θ ≤ 0, y estamos en ese caso.

c′6 = 2 + 7θ ≤ 0, siempre que θ ≤ −2

7.

Por lo tanto, la base B2 es optima en el rango −513≤ θ ≤ −2

7, y en este rango, el

valor de la funcion objetivo es:

z = (cB0 + θδB0)xB0 = (2− 2θ, 5 + 5θ, 3− 6θ)

25/445/2

5

= 140 + 70θ.

Veamos ahora que pasa para valores de θ < −513

:En este caso sabemos que c′4 se hace positivo, por lo tanto la base actual no es

optima. Para hacer el cambio de base, entra la variable x4, y sale la variable x3, con loque la tabla optima que se obtiene es:


5/2 x2 2-2θ 0 1 -1/6 0 -1/2 1/415 x4 0 0 0 2/3 1 -1/6 -1/220 x1 3-6θ 1 0 2/3 0 1/3 0

z= 65- 125θ 0 0 −103

+ 263θ 0 −5

6+ 11

6θ −1

2+ 1

2θ

15

Entonces, B3 = (A2, A4, A1), N1 = (A3, A5, A6)Nos volvemos a plantear si: ¿Existe algun valor crıtico de θ, θ∗∗∗, para el cual la baseB3 deja de ser optima?. Volvemos a estudiar los costos marginales:

c′3 = −10

3+

26

3θ ≤ 0 siempre que θ ≤ − 5

13.

c′5 = −5

6+

11

6θ ≤ 0, cuando θ ≤ 5

11.

c′6 = −1

2+

1

2θ ≤ 0, siempre que θ ≤ 1.

Por lo tanto, no existe θ∗∗∗, o lo que es lo mismo, que la base B3 es optima paracualquier valor de θ < − 5

13.

Por lo tanto la solucion optima del problema es:

θ x1 x2 x3 x4 x5 x6 z

θ ≤ − 513

20 5/2 0 15 0 0 65 - 125θ

− 513≤ θ ≤ −2

75 25/4 45/2 0 0 0 140 + 70θ

0 ≤ θ ≤ 1 0 5 30 0 0 10 160 + 140θθ ≥ 1 0 0 30 10 0 30 150 + 150θ

3.3. Cambio continuo en el vector de disponibilidades.

En este caso, el problema que queremos resolver es:

Max z = ~c · ~xs. a: A~x ≤ ~b+ θ~β

~x ≥ 0

El estudio de este caso es similar al anterior.Sea B0 la base optima asociada al problema, para θ = 0, es decir:

Max z = ~c · ~xs. a: A~x ≤ ~b

~x ≥ 0

Sabemos que un cambio en el vector de disponibilidades, nos produce un cambio en elvector basico ~xB0 , y en el valor de la funcion objetivo. Este cambio es el siguiente:

xB0 = B−10 (~b+ θ~β) = B−10~b+ θB−10

~β = ~xB0 + θB−10~β

z = ~cB0xB0 = ~cB0B−10 (~b+ θ~β)

El problema a estudiar es el siguiente: “¿Para que valores de θ, la base B0

sigue siendo optima?”Como la factibilidad dual no se altera, sabemos que la base B0 seguira siendo optima

mientras el vector basico siga siendo positivo. Por lo tanto:

- Si ~xB0 = B−10 (~b+θ~β) ≥ 0 para todo θ ≥ 0, entonces la base B0 seguira siendo optimapara todo θ ≥ 0.

16

- Si existe alguna componente de ~xB0 que sea negativa, entonces la base B0 deja de seroptima, y el valor crıtico, θ∗, buscado se obtiene despejando en la ecuacion.

Para obtener la siguiente base B1, basta aplicar el metodo Dual del Simplex.Una vez obtenida la nueva solucion ~xB1 asociada a la nueva base B1, el analisis para

determinar un segundo valor crıtico de θ, θ∗∗, es analogo, y el rango para el que la baseel optima es: θ∗ ≤ θ ≤ θ∗∗.

Veamos un ejemplo:

Ejemplo. Consideremos el problema parametrico:

Max z = 3x1 + 2x2 + 5x3s. a: x1 + 2x2 + x3 ≤ 430 + 100θ

3x1 + 2x3 ≤ 460− 200θx1 + 4x2 ≤ 420 + 400θ

x1, x2, x3 ≥ 0


Max z = 3x1 + 2x2 + 5x3s. a: x1 + 2x2 + x3 ≤ 430

3x1 + 2x3 ≤ 460x1 + 4x2 ≤ 420x1, x2, x3 ≥ 0



100 x2 2 -1/4 1 0 1/2 -1/4 0230 x3 5 3/2 0 1 0 1/2 020 x6 0 2 0 0 -2 1 1

z= 1350 -4 0 0 -1 -2 0

Por lo tanto los valores de las variables en el problema parametrico son:

xB0 = B−10 (~b+ θ~δ) =

1/2 −1/4 00 1/2 0−2 1 1

·430 + 100θ

460− 200θ420 + 400θ

=

100 + 100θ230− 100θ

20 + 0θ

100 + 100θ ≥ 0 si θ ≥ −1.230− 100θ ≥ 0 ⇔ θ ≤ 2.3 = θ∗

20 ≥ 0 siempre.Por lo tanto, la base B0 es optima para: −1 ≤ θ ≤ 2.3 = θ∗.Veamos que ocurre para valores de θ ≥ 2.3:En este caso, la segunda variable basica se hace negativa, por lo que la base actual

es no factible y hay que cambiarla.Aplicamos el metodo Dual del Simplex:


100+100θ x2 2 -1/4 1 0 1/2 -1/4 0230-100θ x3 5 3/2 0 1 0 1/2 020+0θ x6 0 2 0 0 -2 1 1

z= 1350-300θ -4 0 0 -1 -2 0

17

sale la variable x3 pero no podemos aplicar el test del cociente para ver que variableentra en la base, por lo tanto, para valores de θ ≥ 2.3 el problema NO tienesolucion.

Veamos que ocurre para valores de θ ≤ −1:En este caso, la primera variable basica se hace negativa, por lo que la base actual

es no factible y hay que cambiarla (sale x2 y entra x5). Aplicamos el metodo Dual delSimplex:


-400 -400θ x5 0 1 -4 0 -2 1 0430+100θ x3 5 1 2 1 1 0 0420+400θ x6 0 1 4 0 0 0 1

z= 2150 +500θ -2 -8 0 -5 0 0

−400− 400θ ≥ 0, siempre que θ ≤ −1.

430 + 100θ ≥ 0 ⇔ θ ≥ −430

100

420 + 400θ ≥ 0 ⇔ θ ≥ −420

400Por lo tanto, la base B1 es optima para: −420

400≤ θ ≤ −1.

Veamos que ocurre para valores de θ < −420400

= −1.05:En este caso, la tercera variable basica se hace negativa, por lo que la base actual

es no factible y hay que cambiarla.Sale la variable x6 pero no podemos aplicar el test del cociente para ver que variable

entra en la base, por lo tanto, para valores de θ ≤ −420400

el problema NO tienesolucion.

Luego, la solucion del problema parametrico sera:

θ x1 x2 x3 x4 x5 x6 z

θ < −1.05 el problema NO tiene solucion−1.05 ≤ θ < −1 0 0 430+100θ 0 -400-400θ 420+400θ 2150+500θ−1 ≤ θ ≤ 2.3 0 100+100θ 230-100θ 0 0 20 1350-300θ

θ > 2.3 el problema NO tiene solucion

3.4. Cambio continuo en una columna de coeficientes tec-nologicos no basica.

El problema a resolver es el siguiente:

Max z = ~c · ~xs. a: A~x ≤ ~b

~x ≥ 0

donde la matriz A difiere de la original en que la columna tecnologica no basica Aj

ahora es de la forma: Aj = Aj + θαj, j /∈ N .Este caso se diferencia de los anteriores en que, en esta ocasion, una vez calculado

un valor crıtico de θ, θ∗, ya NO SE PUEDE calcular un segundo valor, puesto que lavariable correspondiente, se ha convertido en variable basica.

18

Hecha esta advertencia proseguiremos con el analisis.Sea B0 la base optima del problema para θ = 0.Un cambio en la columna tecnologica Aj, ocasiona un cambio unicamente en el

costo marginal de la variable xj. El nuevo costo marginal es:

c′j = cj − ~cB0B−10 (Aj + θαj)

Entonces, mientras los nuevos costos marginales sean no positivos, (estudiamos losde todas las columnas con cambio parametrico), la base actual es optima.

Si existe algun valor del parametro, para el cual la base deja de ser optima, estevalor es θ∗ (en caso de que el cambio se produzca en varias columnas no basicas, θ∗

sera el mınimo de estos valores).Entonces, B0 solo es optima en el rango θ∗ ≤ θ ≤ θ∗, y para valores de fuera de ese

rango, no podemos decir nada.

Ejemplo. Queremos resolver el siguiente problema parametrico:

Max z = 3x1 + 2x2 + 5x3s. a: (1 + θ)x1 + 2x2 + x3 ≤ 430

(3− θ)x1 + 2x3 ≤ 460x1 + 4x2 ≤ 420x1, x2, x3 ≥ 0


Max z = 3x1 + 2x2 + 5x3s. a: x1 + 2x2 + x3 ≤ 430

3x1 + 2x3 ≤ 460x1 + 4x2 ≤ 420x1, x2, x3 ≥ 0



100 x2 2 -1/4 1 0 1/2 -1/4 0230 x3 5 3/2 0 1 0 1/2 020 x6 0 2 0 0 -2 1 1

z= 1350 -4 0 0 -1 -2 0

Para determinar el rango de θ, de modo que para valores de θ dentro de ese rango,la base B0 sigue siendo optima, hacemos lo siguiente:

Para cada columna no basica que sufra un cambio parametrico (en este caso soloes la de x1), calculamos su nuevo costo marginal:

c′1 = c1 − cB0B−10 (A1 + θα1) = 3− (2, 5, 0)

1/2 −1/4 00 1/2 0−2 1 1

1 + θ3− θ

1

=

= 3− (1, 2, 0)

1 + θ3− θ

1

= 3− (7− θ) = −4 + θ.

Entonces, c′1 ≤ 0 ⇔ θ ≤ 4 = θ∗.Luego, B0 es optima para θ ≤ 4 = θ∗, y para θ > 4, no podemos decir nada.

19

4. Precios sombra

En el tema anterior trabajamos con los precios sombra (costos sombra) de los re-cursos. Los recursos tienen asociada una restriccion, y cada restriccion tiene asociadauna variable del dual. Llamabamos precio sombra al valor que tomaba la variable dualen la solucion optima del problema dual.

La interpretacion economica del precio sombra viene a ser el rendimiento economicoque sacamos a cada unidad de recurso en la solucion optima. Es la cantidad en laque valoramos nuestros recursos de cara a venderlos o comprarlos. No obstante, estadefinicion es algo vaga y hay que emplearla con cuidado cuando se esta tratando de unrecurso individual y no de todos los recursos a bloque.

En este apartado daremos una definicion mas concreta y las claves para interpretarmas acertadamente este valor.

Definicion 1. El precio sombra para la i-esima restriccion (recurso) de un problemade programacion lineal se define como la cantidad que aumenta el valor optimo de zpor cada unidad que aumenta el lado derecho (termino independiente) de la i-esimarestriccion. Esta definicion se aplica solo si en el cambio en el lado derecho de larestriccion i, es optima la base actual.

Los signos de los precios sombra

En una restriccion de ≤, al aumentar el lado derecho, estamos agrandando laregion factible, luego el optimo mejorara (igual o mas grande el maximo e igualo menor el mınimo). Por eso, las restricciones de ≤ tienen precio sombra positivoen un problema de maximo, y precio sombra negativo en un problema de mınimo.

En una restriccion de ≥, al aumentar el lado derecho, estamos empequeneciendola region factible, luego los optimos empeoraran. Ası, una restriccion de de≥ tienecosto sombra negativo en un problema de maximo, y positivo en un problema demınimo.

En una restriccion de igualdad la region factible cambia y el optimo puede modi-ficarse en cualquier sentido. Ası, el precio sombra de las restricciones de igualdadpuede tener cualquier signo.

Calculo de los precios sombra

Supongamos que tenemos un problema lineal, cuya base optima es B. Su solucionoptima sera ~xB = B−1~b y el valor de la funcion objetivo z0 = ~cB~xB = ~cBB

−1~b.Si en la restriccion i-esima incrementamos en ε ∈ R unidades la parte derecha, y

suponiendo que no se cambia de base, tenemos como nueva solucion B−1(~b + εei) =~xB + εB−1ei. Por tanto z = ~cB~xB + ε~cBB

−1ei = z0 + ε~cBB−1ei.

En conclusion, el costo sombra de la restriccion i-esima es ~cBB−1ei, es decir, la

i-esima componente del vector fila ~cBB−1, o lo que es lo mismo, el producto de ~cB con

la i-esima columna de B−1. Recordemos que ~cBB−1 nos daba la solucion del problema

dual, por tanto el costo sombra de la i-esima restriccion es el valor de la i-esima variabledual en el optimo.

Notar que la definicion de costo sombra es en realidad la pendiente de la funcionz = ~cBB

−1~b en funcion de la variable bi bajo la suposicion de que B no cambia. Es

20

decir:

costo sombra de la restriccion i =∂z

∂bi= ~cBB

−1 ∂~b

∂bi= ~cBB

−1ei.

Ası, hemos visto otro modo (aunque en esencia es lo mismo) de obtener la mismaformula.

Rango de validez de los precios sombra

Los precios sombra tienen validez mientras no cambiemos de base.Si B es la base optima, ~xB ≥ 0 la solucion basica optima. Para la restriccion i-esima,

¿cuanto podemos modificar su termino independiente sin que la base actual deje de seroptima. Supongamos que aumentamos el recurso i-esimo en ε ∈ R unidades. La nuevasolucion sera factible si y solo si:

B−1(~b+ εei) = ~xB + εB−1ei = ~xB + ε(columna i-esima de B−1) ≥ 0.

Por tanto existiran −∞ ≤ ε∗ ≤ 0 ≤ ε∗ ≤ ∞ tales que para todo ε en el intervaloε∗ ≤ ε ≤ ε∗, la nueva solucion sigue siendo factible.

A ε∗ se le llama “allowable decrease” y a ε∗, “allowable increase” y representanla cantidad que bi se puede disminuir, o respectivamente aumentar, sin que la solu-cion optima cambie de base (suponiendo que el resto de parametros del problema seconserven sin cambios).

Si la solucion ~xB no es degenerada, el “allowable decrease” y “allowable increase”son no nulos, y por tanto siempre se podra aumentar y disminuir un poco el valor dela parte derecha de la restriccion i-esima (bi), sin cambiar de base.

Si ~xB es degenerada, es posible que el “allowable decrease” o “allowable increase”sean nulos. En ese caso cualquier mınima disminucion (o aumento, respectivamente)de bi nos llevarıa a una base diferente.

Ejemplo. Se tiene la posibilidad de fabricar dos productos, x1 y x2, que nos reportaran10 y 9 u.m. respectivamente por cada unidad fabricada. Para fabricar cada unidad deproducto x1 se consume un Kg. de materia prima A, de la que disponemos de 3Kg.Para fabricar cada unidad de producto x2 se consume un Kg. de materia prima B, dela que disponemos de 2Kg. Cada unidad de ambos productos necesita ser calentadauna hora en un horno. Se disponen de 4 horas de horno. Se pretende maximizar elbeneficio.

a) Plantea y resuelve el problema.

Max z = 10x1 + 9x2s. a: x1 ≤ 3

x2 ≤ 2x1 + x2 ≤ 4x1, x2 ≥ 0,


xBkxB cB x1 x2 h1 h2 h3

3 x1 10 1 0 1 0 01 h2 0 0 0 1 1 -11 x2 9 0 1 -1 0 1

z= 39 0 0 -1 0 -9

21

b) Si aumento δ ∈ R (pocas) horas de horno. ¿Cuanto aumenta mi beneficio?

En el modelo que hemos construido, la restriccion correspondiente al horno es latercera. La columna canonica e3 = (0, 0, 1)T es la correspondiente a h3 en la tablainicial del simplex. Por tanto, el costo sombra de la hora de horno sera −c′6 + c6 =−(−9) + 0 = 9 u.m. En conclusion, debido a la definicion de costo sombra, si δ essuficientemente pequeno que no cambia la base optima, el beneficio aumentara 9δu.m., Es decir, sera z = 39 + 9δ.

c) ¿Para que valores de δ es valido el resultado anterior?

Sera valido siempre que la base siga siendo optima. Esto es, siempre que la nuevasolucion siga siendo factible. La nueva solucion es:

~xB + δY6 =

311

+ δ

0−11

,

que sigue siendo factible si 3 ≥ 0, 1− δ ≥ 0, 1 + δ ≥ 0. Esto es, −1 ≤ δ ≤ 1.

Ejemplo. Sea el problema similar al anterior:

Max z = 10x1 + 9x2s. a: x1 + x2 ≤ 2 Kg. de materia prima A

x2 ≤ 1 Kg. de materia prima B2x1 + x2 ≤ 3 horas de hornox1, x2 ≥ 0,


xBkxB cB x1 x2 h1 h2 h3

0 h1 0 0 0 1 -1/2 -1/21 x2 9 0 1 0 1 01 x1 10 1 0 0 -1/2 1/2

z= 19 0 0 0 -4 -5

a) Como se puede ver, el costo sombra de la hora de horno es 5 u.m. ¿En que rangode δ ∈ R se cumple que el aumento de δ horas de horno aumenta nuestro beneficioen 5δ u.m.?

Es facil ver que la nueva solucion es:

011

+ δ

−1/20

1/2

, que sigue siendo factible

en el rango −1 ≤ δ ≤ 0.

b) Si tengo la posibilidad de aumentar horas de horno a 0.1u.m. cada hora, ¿deboaumentar?, ¿cuantas horas?

Como se supone que estoy aumentando un numero positivo de horas, no puedoaplicar el significado del costo sombra. No me queda mas remedio que resolver el

22

problema de analisis de sensibilidad

Max z = 10x1 + 9x2 − 0.1δs. a: x1 + x2 ≤ 2 Kg. de materia prima A

x2 ≤ 1 Kg. de materia prima B2x1 + x2 ≤ 3 + δ horas de horno

x1, x2, δ ≥ 0,

que se resuelve anadiendo la variable δ, que es el numero de horas que aumento.

23

cap tulo 5 analisis de sensibilidad y programacion …

Documents