POST-OPTIMIZACIÓN Y SENSIBILIDAD EN PROBLEMAS LINEALES. Una de las hipótesis básicas de los problemas lineales es la constancia de los coeficientes que aparecen en el problema. Esta hipótesis solamente es admisible a muy corto plazo, dado que para periodos de planificación más amplios las condiciones y circunstancias del análisis pueden ir cambiando. El análisis de post-optimización propiamente dicho, que estudia como quedan afectadas las condiciones de optimalidad y de factibilidad de la solución actual, cuando se produce una modificación o un cambio en alguno de los coeficientes de problema. Además, permite establecer la solución cuando se introducen nuevas variables o nuevas restricciones en el problema. El análisis de sensibilidad, en este caso lo que se determina es el rango o campo de variación admisible para los diferentes coeficientes del problema, dentro del cual la solución actual se mantiene como factible y como óptima. El análisis paramétrico o programación lineal parametrica, en este tipo de análisis es posible determinar el conjunto de soluciones que aparecen cuando alguno (o algunos) de los coeficientes del problema varía de forma continua respecto de algún parámetro.

Condición de factibilidad: xB = B-1 · b ≥ 0

Condición de optimalidad : wj = cj - [ cB B-1 Pj ] ≤ 0

Sea:

Max F(x) = x1 + 2 x2 x1 + x 2 ≤ 4

s.a:

2 x1 + x2 ≤ 6 x1 ≥ 0, x2 ≥ 0 La tabla óptima es: 1

2

0

0

X1

x2

s1

s2

2 x2

1

1

1

0

4

0 s2

1

0

-1

1

2

zj

2

2

2

wj

-1

0

-2

0

8

La gráfica es: 5

4

3

2

1

0 0

1

2

3

4

5

6

7

8

Dentro del análisis de post-optimización se pueden plantear los siguientes casos que estudiaremos a continuación:

1.- Cambio o variación en los coeficientes de la función objetivo, cj. 2.- Modificación en los términos independientes de las restricciones, bi. 3.- Variación en los coeficientes técnicos de las restricciones, aij. 4.- Introducción de nuevas variables. 5.- Adición de nuevas restricciones.

CAMBIO O VARIACIÓN EN LOS COEFICIENTES DE LA FUNCIÓN OBJETIVO, cj

Cambio en un cj de una variable no básica. Sólo al wj de la variable cj Así si ck pasa al valor ck’. wk = ck - [ cB B-1 Pk ] wk’ = ck’ - [ cB B-1 Pk ]

Ejemplo 1. Sobre el ejemplo planteado en la introducción, realizamos una modificación del coeficiente asociado a la variable x1, suponemos que cambia de su valor actual c1 = 1 al valor de c1 = 3/2. El actual w1 es :   1 0  1    = 1 - 2 = -1 < 0. w1 = 1- (2 0) 1 1   2   El nuevo valor w1’ será:   1 0  1    = 3/2 - 2 = -1/2 < 0. w1’ = 3/2 - (2 0) 1 1   2  

1.5

2

0

0

x1

X2

s1

s2

2 x2

1

1

1

0

4

0 s2

1

0

-1

1

2

zj

2

2

2

0

wj

-.5

0

-2

0

8

Ejemplo 2. Supongamos ahora que el coeficiente en la función objetivo de la variable x1 es ahora de 3. Al igual que en el ejemplo 1, solamente se verá afectado el rendimiento marginal de esta variable. Con lo cual el nuevo rendimiento marginal de x1 es:   1 0  1    = 3 - 2 = 1 > 0. w1’ = 3 - (2 0)  - 1 1  2  

3

2

0

0

x1

X2

s1

s2

2 x2

1

1

1

0

4

0 s2

1

0

-1

1

2

zj

2

2

2

0

wj

1

0

-2

0

3

2

0

0

la nueva tabla :

8

x1

X2

s1

s2

2 x2

0

1

2

-1

2

3 x1

1

0

-1

1

2

zj

3

2

1

1

wj

0

0

-1

-1

10

Gráficamente, este cambio equivale a una modificación de la pendiente de la función objetivo original (1/2) a una nueva pendiente de (3/2), lo cual supone que el punto (0,4) ya no es el punto extremo de tangencia de la función objetivo con el conjunto de oportunidades, sino que se desplaza hasta el punto (2,2). La nueva solución gráfica es: 5

4

3

2

1

0 0

1

2

3

4

5

6

7

8

La curva de nivel de la función objetivo está representada por la recta que une el punto (10/3,0) con el punto (0,5), siendo el punto de contacto el punto (2,2) donde la función objetivo alcanza el valor de 10. Cambio en un cj de una variable básica.

Esta modificación afectará al vector de coeficientes de la función objetivo de las variables básicas, es decir, al vector cB , y con ello a todos los rendimientos marginales de las variables no básicas (los de las básicas seguirán siendo cero), los cuales es necesario recalcular para adecuarlos a los cambios producidos en el vector cB . wj = cj - [ cB B-1 Pj ] Ejemplo 3 Supongamos para el ejemplo de la introducción que se ha producido una modificación en el coeficiente de la función objetivo de la variable x2, pasando del valor actual de c2 = 2 a c2’ = 4. Como la variable x2 es una variable básica, esto afectará al vector de coeficientes de variables básicas, el vector cB era cB = ( 2, 0)t, con el cambio en el coeficiente c2 el nuevo vector cB’ será cB’ = ( 4, 0)t. Como este cambio afecta a todos los rendimientos marginales de las variables no básicas (x1 y s1), los nuevos rendimientos marginales serán:   1 0  1    = 1 - 4 = -3 < 0 w1 = 1- (4 0 ) − 1 1   2     1 0  1    = 0 - 4 = -4 < 0 ws1 = 0 - (4 0 ) − 1 1   2   Siendo el nuevo valor de la función objetivo

 4 F(x) = c tB ’ xB = (4,0)   = 16  2 O lo que es lo mismo, que sustituyendo en la tabla óptima el valor del nuevo coeficiente c2 , es decir: 1

4

0

0

x1

x2

s1

s2

4 x2

1

1

1

0

4

0 s2

1

0

-1

1

2

zj

4

4

4

0

wj

-3

0

-4

0

16

5

4

3

2

1

0 0

1

2

3

4

Gráfico 3

5

6

7

8

MODIFICACIÓN

EN

LOS

TÉRMINOS

INDEPENDIENTES

DE

LAS

RESTRICCIONES , bi

Afecta a la condición de factibilidad, es decir, a xB = B-1·b si se mantiene la condición de no negatividad de las variables (mayor o igual que cero) la solución actual (entendida como que las variables básicas son las mismas, y no como valor de estas variables) sigue siendo óptima. Los cambios pueden violar esta condición de factibilidad, es decir, que xB tenga alguna o algunas componentes menores que cero. En este caso, cuando se rompe la factibilidad del problema, ya no es posible seguir iterando dado que se mantiene la condición de optimalidad ( wi ≤ 0 ∀i ) y por tanto no hay criterio de entrada. La forma de restablecer la factibilidad es por la vial del dual, ya que a una solución factible primal le corresponde una solución optima dual, por tanto, si la solución es infactible, la solución del dual deja de ser óptima, y es posible seguir iterando por la vía del dual hasta encontrar una solución óptima y factible, momento en el cual es posible establecer la solución correspondiente de primal.

Ejemplo 4. Supongamos sobre el problema que estamos manejando a lo largo de la exposición: Max f(x) = x1 + 2 x2 x 1 + x2 ≤ 4

s.a:

2 x1 + x2 ≤ 6 x1 ≥ 0, x2 ≥ 0 que se produce una modificación del término independiente de la primera restricción pasando a tomar el valor de 5. La matriz B está formada por los vectores P2 y Ps2 , es decir: 1 0   → B =  1 1 

 1 0  B-1 =   − 1 1

el nuevo valor de los términos independientes es 5 b =   6 por lo que el valor de las variables básicas será:  1 0  5  5    =   ≥ 0 xB =  − 1 1    6 1

Como el nuevo valor de las variables básicas mantiene la factibilidad, la solución actual se mantiene como óptima, solamente se habrá producido un cambio en el valor de las variables y en el valor de la función objetivo, es decir x2 = 5, s2 = 1 , F(x) = 2·5 + 0·1 = 10 La tabla óptima será la misma que la original salvo los cambios en el valor de las variables y en la función objetivo: 1

2

0

0

x1

x2

s1

s2

2 x2

1

1

1

0

5

0 s2

1

0

-1

1

1

zj

2

2

2

0

wj

-1

0

-2

0

10

Gráficamente un cambio en el término independiente significa una alteración del conjunto de oportunidades original. Para el ejemplo que estamos analizando el cambio de b1 = 4 a b1’ = 5, significa una ampliación del conjunto de oportunidades, con lo que el vértice solución ha pasado de ser el (0,4) a ser el (0,5), es decir:

5

4

3

2

1

0 0

1

2

3

4

5

6

7

8

Ejemplo 5 . Vamos a suponer ahora, un incremento superior en el término independiente de la primera restricción para que pase a ser de 8, lo que significa que b1’ = 8. El valor de las variables básicas será:  1 0  8   ·  = xB =  − 1 1    6

 8     − 2

Con estos valores de las variables básicas se ha perdido la factibilidad del problema, es decir, la nueva solución (variables básicas x2= 8, s2 =-2 ) no pertenece al conjunto de oportunidades que se ha formando con el aumento del término independiente de la primera restricción. Gráficamente esto significa :

10

8

6

4

2

0 0

2

4

6

8

10

12

14

16

El nuevo conjunto de oportunidades viene definido única y exclusivamente por la segunda restricción, por tanto la primera se comporta como inactiva. El punto que nos ha proporcionado el análisis anterior, el punto (0,8) está fuera del nuevo conjunto, por lo que se trata de una solución infactible, es decir, se trata de una solución imposible para este problema. La forma de restablecer la factibilidad es a través del paso al problema dual asociado: La tabla correspondiente, aunque infactible, es la siguiente: 1

2

0

0

x1

x2

s1

s2

2 x2

1

1

1

0

8

0 s2

1

0

-1

1

-2

zj

2

2

2

0

wj

-1

0

-2

0

16

Desde esta tabla ya no se puede seguir iterando por el método primal del simplex, dado que se verifica la condición de optimalidad (wj≤0). El problema dual asociado será: Min G(λ) = 8 λ1 + 6 λ2 λ1 + 2 λ2 ≥ 1

s.a:

λ1 + λ2 ≥ 2 λ1 ≥ 0 ; λ2 ≥ 0 La tabla de dual asociada a la solución infactible del primal será: -8

-6

0

0

λ1

λ2

d1

d2

-8 λ1

1

1

0

-1

2

0 d1

0

-1

1

-1

1

zj

-8

-8

0

8

wj

0

2

0

-8 -16

donde d1 y d2 son las variables de holgura del dual asociadas a las dos restricciones. Para obtener la tabla dual se ha procedido de la forma que hemos visto con anterioridad, es decir, en primer lugar hemos de conocer las variables básicas del problema. En este caso serán las variables (λ1 y d1) que son las variables del dual asociadas a las variables no básicas del primal s1 y x1 respectivamente. Una vez conocidas las variables básicas, el paso siguiente es obtener la matriz B y su inversa, es decir:

 1 − 1  B =  1 0  

 0 1  B-1 =  − 1 1  

Una vez determinada la matriz B-1 , multiplicamos la matriz de coeficientes técnicos del dual y así obtenemos las componentes de la tabla. El valor de las variables básicas se obtiene al multiplicar B-1 por el vector de términos independientes. Como puede observarse, la tabla anterior del dual es factible, pero no es óptima, por tanto podemos introducir la variable λ2 en la base eliminando de ella a la variable λ1, obteniéndose la siguiente tabla: -8

-6

0

0

λ1

λ2

d1

d2

-6 λ2

1

1

0

-1

2

0 d1

1

0

1

-2

3

zj

-6

-6

0

6

wj

-2

0

0

-6 -12

En este caso se trata de una tabla que es factible y óptima, por tanto, para determinar la solución óptima del primal debemos realizar el paso del dual al primal de la forma que hemos expuesto con anterioridad. Las variables básicas del primal son x2 y s1, ya que son las variables del primal asociadas a las variables no básicas del dual ( d2 y λ1). Con estas variables determinamos la matriz B, y a través de su inversa ya podemos completar todo el proceso.

1 1   B =  1 0  

0 1   B-1 =  − 1 1  

Por tanto, la tabla óptima del problema primal es: 1

2

0

0

x1

x2

s1

s2

2 x2

2

1

0

1

6

0 s1

-1

0

1

-1

2

4

2

0

2

-3

0

0

-2

12

Solución que se corresponde con el vértice (0,6), siendo la primera restricción inactiva, tal como hemos podido constatar por el gráfico anterior. Todo lo que acabamos de exponer se puede simplificar si en lugar de emplear el algoritmo del simplex, usamos el algoritmo dual simplex, ya que en este caso se hace innecesario el paso al problema dual y su posterior transformación al primal.

VARIACIÓN EN LOS COEFICIENTES TÉCNICOS DE LAS RESTRICCIONES, aij Los cambios o modificaciones en los coeficientes técnicos de las restricciones pueden afectar tanto a la condición de factibilidad como a la de optimalidad, según se trate de un coeficiente asociado a una variable no básica o a una variable básica. Los coeficientes técnicos forman parte de los vectores asociados a las diferentes variables, vectores Pi .Como la repercusión según se trate de una variable básica o no básica, puede ser muy distinta, estudiaremos los dos casos por separado. Variación en un coeficiente técnico de una variable no básica. El cambio en un coeficiente aij afecta al vector Pj, y por tanto al correspondiente vector transformado en la tabla óptima, dado que Pj’ = B-1 · Pj . Estos cambios afectan a los rendimientos indirectos de esta variable y por consiguiente a los rendimientos marginales, es decir, a la condición de optimalidad: wj = cj - [ cB B-1 Pj ] Si wj es menor que cero, la solución actual seguirá siendo optima, y además de vértice, si la original era así.

Si wj es cero, quiere decir que la solución actual es óptima, pero ya no es única, sino que existe una solución alternativa a esta. En el caso de que wj sea positivo la solución actual deja de ser óptima , y deberemos seguir iterando hasta encontrar una nueva solución óptima. Ejemplo 6. Sobre el problema que venimos usando a lo largo de esta exposición, vamos a suponer que se ha producido un cambio en el coeficiente de la variable x1 de la primera restricción pasando del valor actual de 1 al nuevo valor de 1/3. Esta modificación afecta al rendimiento marginal de la variable x1 , que será en este caso:   1 0 1 / 3    = 1/3 > 0 w1 = 1 - (2 0) − 1 1 2     Con lo que la solución actual deja de ser óptima, por tanto debemos seguir iterando a través del método simplex hasta encontrar la nueva solución óptima. La tabla correspondiente será:

1

2

0

0

x1

x2

s1

s2

2 x2 .33

1

1

0

4

0 s2 1.66

0

-1

1

2

.66

2

2

0

wj .33

0

-2

0

zj

8

Por tanto, introduciendo la variable x1 en la base y eliminando a la variable s2 , tenemos la tabla siguiente: 1

2

0

0

x1

x2

s1

s2

2 x2

0

1

1.2 -.2 3.6

1 x1

1

0

-.6

.6

zj

1

2

1.8

.2

wj

0

0

-1.8 -.2 8.4

1.2

En el gráfico 5, podemos observar que se ha producido una alteración del conjunto de oportunidades, y con ello un cambio del vértice solución óptima, del vértice (0,4) se ha pasado al vértice (1.2, 3.6).

5

4

3

2

1

0 0

1

2

3

4

5

6

7

8

Variación en un coeficiente técnico de una variable básica . Los cambios en un vector básico afectan tanto a las condiciones de optimalidad como a las de factibilidad, dado que el vector Pj pertenece a la matriz B, y por tanto sus modificaciones pueden afectar sustancialmente al problema actual. Los cambios pueden ser múltiples, desde hacer que B sea una matriz singular, y por tanto sin inversa, hasta que las modificaciones de B mantengan la factibilidad y la optimalidad de la solución actual. En el caso que B devenga una matriz singular, ya no tenemos procedimiento para poder continuar, y la alternativa en este caso es reiniciar el problema desde su origen. En el caso de que B siga siendo regular, y por tanto sea posible obtener B-1, pueden darse los casos siguientes:

a)

xB = B-1 · b ≥ 0 wj = cj - [ cB B-1 Pj ] ≤ 0

La solución actual sigue siendo factible y óptima. b)

xB = B-1 · b ≥ 0 wj = cj - [ cB B-1 Pj ] > 0

La solución se mantiene como factible, pero deja de ser óptima, en este caso es posible seguir iterando a través del método simplex hasta encontrar la solución óptima. c)

xB = B-1 · b < 0 wj = cj - [ cB B-1 Pj ] ≤ 0

En esta caso la solución es infactible pero se verifica la condición de optimalidad, por tanto, la alternativa es seguir el proceso explicado para esta situación, es decir, pasar al dual (factible pero no óptimo) y seguir iterando por la vía del dual hasta encontrar la solución óptima y una vez alcanzada esta solución, regresar al programa primal para poder determinar su solución óptima. d)

xB = B-1 · b < 0 wj = cj - [ cB B-1 Pj ] > 0

Cuando la solución actual se convierte en infactible y además no verifica las condiciones de optimalidad, la alternativa más conveniente es iniciar nuevamente el proceso de obtención de la solución.

ADICIÓN DE NUEVAS VARIABLES. La incorporación de una nueva variable al problema original produce un aumento de la dimensionalidad de la tabla por la vía de las columnas. Para ver si esa adición altera la solución actualmente óptima, hay que comprobar la condición de optimalidad de esa variable, ya que el aumento de las columnas no afecta a la condición de factibilidad de la tabla. La nueva variable añadida xk, llevará asociado su coeficiente en la función objetivo ( ck ) y su vector de coeficientes técnicos ( Pk ), y habremos de calcular su rendimiento marginal. wk = ck - [ cB B-1 Pk ] Si este rendimiento marginal es menor que cero, la solución actual se mantiene como óptima. Si se anula el rendimiento marginal significa que hay soluciones alternativas a la actual pero con el mismo valor de la función objetivo. En el supuesto que dicho rendimiento marginal sea positivo hemos de introducir la nueva variable en la tabla como variable básica y seguir iterando hasta encontrar la nueva solución óptima.

Ejemplo 7. Al problema que venimos utilizando como base: Max F(x) = x1 + 2 x2 x 1 + x2 ≤ 4

s.a:

2 x1 + x2 ≤ 6 x1 ≥ 0, x2 ≥ 0 le añadimos una nueva variable (x3) con coeficiente en la función objetivo de c3 = 6 y un vector técnico:P3 = (2,2)t El rendimiento marginal de la nueva variable es :   1 0  2    = 2 > 0 w3 = 6 - (2 0 ) − 1 1   2   Al ser este rendimiento marginal positivo, la solución actual deja de ser óptima, y por tanto deberemos introducir la variable x3 en la tabla, para ello solo necesitamos conocer el vector transformado (P3’) respecto de la base B del vector original. (Vector que se ha calculado en w3), con ello la tabla será: 1

2

6

0

0

x1

x2

x3

s1

s2

2 x2

1

1

2

1

0

4

0 s2

1

0

0

-1

1

2

zj

2

2

4

2

0

wj

-1

0

2

-2

0

8

Introduciendo la variable x3 en lugar de x2 , la nueva tabla será: 1

2

6

0

0

x1

x2

x3

s1

s2

2 x2

1

1

2

1

0

4

0 s2

1

0

0

-1

1

2

zj

2

2

4

2

0

wj

-1

0

2

-2

0

8

La tabla es óptima ya que todos los rendimientos marginales de las variables no básicas son negativos.

INTRODUCCIÓN DE NUEVAS RESTRICCIONES. La introducción de una nueva restricción al problema original, conlleva un aumento de la dimensionalidad de la tabla por la vía de las filas, así como un aumento del número de variables básicas. Por tanto, el aumento del número de filas no afecta a la condición de optimalidad pero si a la de factibilidad. En términos de representación gráfica las nuevas restricciones afectan al poliedro (o politopo) que forman las restricciones, de manera que éste se puede ver reducido o no y en consecuencia la actual solución puede dejar de pertenecer al nuevo conjunto convexo. Para analizar si las nuevas restricciones afectan a la solución actual procederemos de la siguiente forma: 1) Para la nueva restricción: n

∑a j=1

kj

x j ≤ bk

Se añade la correspondiente variable de holgura, para convertirla en una igualdad, es decir: n

∑ a kj x j + s k j =1

= bk

2) Sustituyendo los valores de la variables xj por sus valores en la solución óptima, podremos determinar el valor de la variable sk . a) Si skh > 0 , la actual solución verifica la restricción y por tanto continua siendo óptima, únicamente necesitamos una nueva variable básica que será sk. b) Si sk = 0, la solución sigue siendo óptima, pero degenerada, ya que la nueva variable básica es nula. c) En el caso de que xkh < 0, la la solución actual no verifica la nueva restricción, y por tanto, es infactible para el nuevo problema, lo cual se puede resolver restituyendo la factibilidad por la vía del dual. Es decir, planteamos el programa dual asociado, y para este programa la nueva restricción equivale a introducir una variable adicional, para lo cual procedemos como hemos visto en el epígrafe anterior para añadir nuevas variables. Una vez alcanzada la solución óptima y factible del dual, tendremos que deshacer las transformaciones realizadas volviendo de nuevo al programa primal. Ejemplo 8 . Al problema original le añadimos la siguiente restricción: 3x1+x2 ≤ 6 En el gráfico 7 podemos observar que esta restricción modifica el conjunto de oportunidades original, pero en la porción de conjunto

eliminada no está la actual solución optima, la del punto (0,4), por lo quye se mantendrá como óptima. 5

4

3

2

1

0 0

1

2

3

4

5

6

7

8

Para resolverlo, repetiremos los pasos expuestos con anterioridad, es decir: 1) Añadimos la variable de holgura correspondiente: 3x1+x2+s3 = 6 2) Sustituimos x1 y x2 por sus valores en la solución óptima, es decir, x1=0 y x2=4, tenemos : s3 = 6 - 3·0 - 1·4 = 2 > 0 con ello, vemos que la nueva variable mantiene la factibilidad de la solución actual. Por tanto, solo cabe añadir el nuevo valor de la variable

básica s3 = 2., es decir, la nueva solución será: x2 = 4, s2 = 2 y s3 = 2 siendo el valor de la función objetivo de f(x) = 8. Si queremos reconstruir la tabla óptima hemos de recurrir al cálculo de la inversa de la nueva base B, y a partir de ella obtener todas las componentes de la tabla. Ejemplo 9 . Al problema original le añadimos la restricción siguiente: x1 + 3 x2 ≤ 6. Por tanto el nuevo problema será:

Max F(x) = x1 + 2 x2 s.a:

x 1 + x2 ≤ 4 2 x1 + x2 ≤ 6 x1 + 3 x2 ≤ 6. x1 ≥ 0, x2 ≥ 0

Antes de proceder a analizar el comportamiento de la nueva restricción, y dado que el problema tiene dos variables, podemos ver en el gráfico 8 el efecto de la introducción de la nueva restricción:

5

4

3

2

1

0 0

1

2

3

4

5

6

7

8

Como puede observarse la nueva restricción elimina una porción factible del conjunto original y entre los puntos eliminados, está la solución (vértice (0,4)). Con ello, la nueva solución se obtiene en el punto (12/5, 6/5), que es el punto de tangencia del nuevo conjunto de oportunidades con la recta de nivel de la función objetivo. Vamos a proceder ahora a través de la operación descrita con anterioridad, a convertir la restricción en una igualdad con la introducción de una nueva variable de holgura. 1) Añadimos la variable de holgura correspondiente: x1 + 3 x2 +s3 = 6. 2) Sustituimos x1 y x2 por sus valores en la solución óptima, es decir x1=0 y x2=4, con lo que tenemos : s3 = 6 - 0 - 3·4 = -6 < 0

el valor de la nueva variable es negativo, por tanto, se trata de una solución infactibe.

Para restituir la factibilidad, tenemos que introducir la nueva

restricción en el primal como una nueva variable en el dual, por ello, vamos a plantear los primales y duales correspondientes: Programa Primal Original (PPO): Max F(x) = x1 + 2 x2 x 1 + x2 ≤ 4

s.a:

2 x1 + x2 ≤ 6 x1 ≥ 0, x2 ≥ 0 A este programa le corresponde el siguiente Programa Dual Original (PDO): Min G(λ) = 8 λ1 + 6 λ2 s.a.

λ1 + 2 λ2 ≥ 1 λ1 + λ2 ≥ 2 λ1≥0, λ2≥0

Si añadimos la correspondiente restricción al primal, obtendremos el Programa Primal Ampliado (PPA): Max F(x) = x1 + 2 x2 s.a:

x 1 + x2 ≤ 4 2 x1 + x2 ≤ 6 x1 + 3 x2 ≤ 6. x1 ≥ 0, x2 ≥ 0

Asociado a este programa primal tenemos su correspondiente dual, Programa Dual Ampliado (PDA): Min G(λ) = 8 λ1 + 6 λ2 + 6 λ3 s.a.

λ1 + 2 λ2 + λ3 ≥ 1 λ1 + λ2 + 3 λ3 ≥ 2 λ1≥0, λ2≥0 , λ3≥0

Las tablas óptimas del PPO y del PDA son las siguientes: 1

2

0

0

x1

x2

s1

s2

2 x2

1

1

1

0

4

0 s2

1

0

-1

1

2

zj

2

2

2

0

wj

-1

0

-2

0

-4

-6

0

0

λ1

λ2

d1

d2

-4 λ1

1

1

0

-1

2

0 d1

0

-1

1

-1

1

zj

-4

-4

0

4

wj

0

-2

0

-4

8

-8

La introducción de una nueva restricción en el PPO, equivale a introducir una nueva variable en el PDO, es decir a introducir la variable λ3 con coeficiente en la función objetivo de c3 = 6, y un vector asociado :P3 =

1   . Por tanto el vector transformado respecto a las variables básicas del  3 dual será:  0 1  1   ·   .= P3’ = B-1 · P3 =   − 1 1  3 

 3   .  2

Dado que podemos intuir que el rendimiento marginal asociado a esta nueva variable será positivo (variable asociada a un primal infactible) podemos insertar la nueva columna en la tabla dual correspondiente, y tenemos: -4

-6

-6

0

0

λ1

λ2

λ3

d1

d2

-4 λ1

1

1

3

0

-1

2

0 d1

0

-1

2

1

-1

1

zj

-4

-4 -12

0

4

wj

0

-2

0

-4

6

-8

Como podemos observar el rendimiento marginal de la variable λ3 es positivo (valor de la variable s3 cambiado de signo) por tanto esta tabla no es óptima, ya que podemos introducir en la base a la variable λ3 desplazando de la base actual a la variable d1. Con lo cual la nueva tabla es :

-4

-6

-6

0

0

λ1

λ2

λ3

d1

d2

-4

λ1

1

5/2

0

-3/2

1/2

1/2

-6

λ3

0

-1/2

1

1/2

-1/2

1/2

zj

-4

-7

-6

3

1

wj

0

1

0

-3

-1

-5

Esta tabla tampoco es óptima ya que el rendimiento marginal de la variable λ2 es positivo, por tanto la variable λ2 entra en la base desplazando de ella a la variable λ1. En este caso la nueva tabla es: -4

-6

-6

0

0

λ1

λ2

λ3

d1

d2

-6

λ2

2/5

1

0

-3/5

1/5

1/5

-6

λ3

1/5

0

1

1/5

-2/5

3/5

zj

-18/5

-6

-6

12/5

6/5

wj

-2/5

0

0

-12/5

-6/5

-24/5

Una vez llegados a la tabla óptima del programa dual, hemos de regresar al programa primal, es decir, hemos de establecer las relaciones entre la variables de ambos problemas: λ1 = 0

←→

s1 =2/5

λ2 = 1/5

←→

s2 = 0

λ3 = 3/5

←→

s3 = 0

d1 = 0

←→

x1 = 12/5

←→

d2 = 0

x2 = 6/5

G(λ) = 24/5 = F(x) A partir de las relaciones anteriores podemos determinar que la solución óptima es el vértice (12/5, 6/5), no obstante, si queremos obtener la tabla optima asociada a este programa primal ampliado (PPA), basta con determinar las variables básicas, y a partir de ellas la matriz B, y con ella B1

, y toda la tabla óptima. Las variables básicas son: (x1 , x2 , s1), la matriz formada por los

vectores asociados a estas variables es: 1 1 1   B=  2 1 0  1 3 0   la matriz inversa  0 3 / 5 − 1/ 5   B = 0 − 1/ 5 2 / 5   1 − 2 / 5 − 1/ 5   -1

Multiplicando la matriz B-1 por la matriz de coeficientes del problema, es decir la matriz A, obtendremos los coeficientes de la tabla óptima, es decir:  0 3 / 5 − 1/ 5  1 1 1 0 0 4     B-1· A =  0 − 1 / 5 2 / 5  ·  2 1 0 1 0 6   1 − 2 / 5 − 1/ 5  1 3 0 0 1 6      Con lo cual la tabla óptima del problema primal será:

1

2

0

0

0

x1

x2

s1

s2

s3

1

-2/5

-1/5

2/5

3/5

-1/5

12/5 6/5

0

s1

0

0

1

x1

1

0

2

x2

0

1

0

-1/5

2/5

zj

1

2

0

1/5

3/5

wj

0

0

0

-1/5

-3/5

24/5

Como era de esperar la nueva solución coincide con el vértice que se ha determinado previamente por el método gráfico, es decir, el vértice (12/5,6/5).