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

s.a: x1 + x2 ≤ 4

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:

0

1

2

3

4

5

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 :

w1 = 1-

21

11-01

0) (2 = 1 - 2 = -1 < 0.

El nuevo valor w1’ será:

w1’ = 3/2 -

21

11-01

0) (2 = 3/2 - 2 = -1/2 < 0.

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:

w1’ = 3 -

21

11-01

0) (2 = 3 - 2 = 1 > 0.

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 8

la nueva tabla :

3 2 0 0

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:

0

1

2

3

4

5

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:

w1 = 1- ( )

− 2

11101

04 = 1 - 4 = -3 < 0

ws1 = 0 - ( )

− 2

11101

04 = 0 - 4 = -4 < 0

Siendo el nuevo valor de la función objetivo

F(x) = cBt ’ xB = (4,0)

24

= 16

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

0

1

2

3

4

5

0 1 2 3 4 5 6 7 8 Gráfico 3

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

s.a: x1 + x2 ≤ 4

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:

B =

1101

→ B-1 =

− 11

01

el nuevo valor de los términos independientes es

b =

65

por lo que el valor de las variables básicas será:

xB =

− 11

01

65

=

15

≥ 0

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:

0

1

2

3

4

5

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á:

xB =

− 11

01·

86

=

− 28

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 :

0

2

4

6

8

10

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

s.a: λ1 + 2 λ2 ≥ 1

λ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:

B =

−0111

B-1 =

− 11

10

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.

B =

0111

B-1 =

−1110

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:

w1 = 1 - ( )

− 2

3/11101

02 = 1/3 > 0

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

zj .66 2 2 0

wj .33 0 -2 0 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 1.2

zj 1 2 1.8 .2

wj 0 0 -1.8 -.2 8.4

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).

0

1

2

3

4

5

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

s.a: x1 + x2 ≤ 4

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 :

w3 = 6 - ( )

− 2

21101

02 = 2 > 0

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:

a x bkj j k≤=∑j

n

1

Se añade la correspondiente variable de holgura, para convertirla en

una igualdad, es decir:

k1

jkj b xa∑=

=+n

jks

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.

0

1

2

3

4

5

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: x1 + 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:

0

1

2

3

4

5

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

s.a: x1 + x2 ≤ 4

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: x1 + 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 8

-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

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 =

31

. Por tanto el vector transformado respecto a las variables básicas del

dual será:

P3’ = B-1 · P3 =

− 11

10·

31

.=

23

.

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 6 0 -4 -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 B-

1, y toda la tabla óptima.

Las variables básicas son: (x1 , x2 , s1), la matriz formada por los

vectores asociados a estas variables es:

B=

031012111

la matriz inversa

B-1=

−−−

−

5/15/215/25/105/15/30

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:

B-1· A =

−−−

−

5/15/215/25/105/15/30

·

610031601012400111

Con lo cual la tabla óptima del problema primal será:

1 2 0 0 0

x1 x2 s1 s2 s3

0 s1 0 0 1 -2/5 -1/5 2/5

1 x1 1 0 3/5 -1/5 12/5

2 x2 0 1 0 -1/5 2/5 6/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).