Capítulo 3 Dualidad y sensitividad

LOGRO: Plantea y resuelve problema dual
LOGRO: Hace análisis de senstividad a la solución de un problema de programación lineal

3.1 Dualidad

Indicadores de logro:

INDICADOR: Plantea el dual de un problema de programación linea y lo emplea para resolver el primal

3.1.1 Teoría

Dual

Dado un problema de minimización en forma canónica:

min	c^Tx
s.a	Ax≥ v
	x≥ 0

su dual es el problema

max	w^Tb
s.a	w^T A≤ c^T
	w≥ 0

Para un problema de programación lineal en forma estándar:

min	c^Tx
s.a	Ax=v
	x≥ 0

el dual es

max	w^Tb
s.a	w^T A≤ c^T

Se cumplen las siguientes propiedades:

Si x₀ es solución del primal y w₀ es solución del dual entonces w₀^Tb≤c^Tx₀
Si x es solución factible del primal y w es solución factible del dual, y además w^Tb=c^Tx entonces x y w son soluciones óptimas de primal y dual respectivamente.
Si uno de los problemas tiene solución factible no acotada, el otro no tiene solución factible.

Teorema 1 (Teorema fundamental de dualidad). Con respecto a problemas primal y dual:

Abmos problemas tiene soluciones óptimas x^* y w^* con c^Tx^*=w^*Tb
Uno de los problemas tiene solución factible no acotada en cuyo caso el otro debe ser no factible.
Ambos problemas son no factibles

Teorema 2 (Holgura complementaria) Si x y w son soluciones óptimas de primal y dual respectivamente de un problema en forma canónica:

x_j>0→ w^Ta_j=c_j
w^Ta_j<c_j → x_j=0
w_i>0→ aⁱx=b_i
aⁱx>b_i → w_i=0

Teorema 3 Si x es solución de un problema primal en forma canónica, con base B y con coeficientes de función objetivo asociados a variables básicas c_B, entonces el dual es resuelto por w^T=c_B^TB⁻¹.

Retomando Problema de Inventario o Almacenamiento

Se trata de manejar un almacen de capacidad C durante n periodos. El costo por unidad almacenada un periodo es r. El precio de venta en el periodo i es v_i. El almacen debe estar vacío al comienzo y final. x_i representa existencias en almacen al principio del periodo i. u_i cantidad producida en el periodo i. s_i cantidad vendida en el periodo i.

max

i=1

(v_is_i−rx_i)

s.a

x_i+1=x_i+u_i−s_i

i=1,2,... n

0=x₁

0=x_n+u_n−s_n

x_i≤ C

i=2,... n

x_i≥ 0, u_i≥ 0, s_i≥ 0

i=1,2,... n

Dual del problema de la dieta

x_i unidades de alimento i cada una con costo c_i (i=1,2,... n)
b_j mínimo del j-esimo requerimiento nutricional (j=1,2,... m).
a_ij aporte nutricional del j-esimo alimento para el i-esimo requerimiento.

El problema de la dieta es

min	c^Tx
s.a	Ax≥ b
	x≥ 0

su dual es

max	w^Tb
s.a	w^TA≤ c^T
	w≥ 0

El dual puede pensarse como el planteamiento que hace una farmaceútica que quiere competir con los alimentos, vendiendo m tipos de pildoras, cada una de las cuales satisface justamente 1 unidad del j-esimo requerimiento. w_j es el precio de venta unitario de la j-esima pildora.

Como los compradores podrán comprar justamente el mínimo necesario de pildoras para satisfacer los requerimientos b, debe buscarse maximizar el precio de venta de esos requerimientos mínimos.

Para poder competir con los alimentos reales, el costo de las pildoras que cubren precisamente los mismos requerimientos del i-esimo alimento debe ser menor o igual al precio de ese alimento (i.e esos requerimientos están en la i-esima columna de A, que denotamos aⁱ), es decir w^Taⁱ≤ c_i o w^TA≤c^T.

Dual del problema de transporte

El problema de transporte para 3 origenes y 2 destinos puede plantearse como

min	c₁₁x₁₁+c12x12+c21x21+c22x22+c31x31+c32x32
s.a	x₁₁+x₁₂=a₁
	x₂₁+x₂₂=a₂
	x₃₁+x₃₂=a₃
	x₁₁+x₂₁+x₃₁=b₁
	x₁₂+x₂₂+x₃₂=b₂
	x₁₁,x12,x21,x22,x31,x32 ≥ 0

La matriz A es

[

1	1	0	0	0	0
0	0	1	1	0	0
0	0	0	0	1	1
1	0	1	0	1	0
0	1	0	1	0	1

]

Para plantear su dual puede dividirse el vector de variables duales w^T=(u^T,v^T) y plantearse como

max	u₁a₁+u₂a₂+u₃a₃+v₁b₁+v₂b₂+v₃b₃
s.a	u₁+v₁≤ c₁₁
u₁+v₂≤ c₁₂
u₂+v₁≤ c₂₁
u₂+v₂≤ c₂₂
u₃+v₁≤ c₃₁
u₃+v₂≤ c₃₂

En general con n origenes y m destinos, si se denota por c_ij el costo de transportar del i-esimo origen al j-esimo destino, y por x_ij la cantidad a transportar por la misma ruta, el problema de transporte es:

min

i=1

j=1

c_ijx_ij

s.a

j=1

x_ij=a_i

i=1,2,... n

i=1

x_ij=b_i

j=1,2,... m

y el dual puede plantearse como:

max

i=1

u_ia_i

j=1

v_jb_j

s.a

u_i+v_j≤ c_ij

i=1,2... n

j=1,2... m

Obtención de la solución dual de la tabla simplex

Como ya se mostró, dada la solución del primal, la solución dual es

w^T=c_B^TB⁻¹

en ocasiones es posible obtener este valor rapidamente de la tabla simplex final. Suponga que las variables básicas son las m primeras, y que la matriz identidad se forma al comienzo del procedimiento simplex con las últimas m variables, entonces la tabla simplex inicial es:

B	D	I	b
c_B	c_D	c_I	0

que se resuelve como:

I	B⁻¹D	B⁻¹	B⁻¹b
0	c_D−c_BB⁻¹D	c_I−c_BB⁻¹	−c_BB⁻¹b

Si llamamos p a los valores que aparecen en la última fila en las columnas donde inicialmente estaba la matriz identidad (i.e p=c_I−c_BB⁻¹), podemos obtener la solución dual como:

w=−(p−c_I)

donde c_I son los coeficientes de la última fila que aparecen en la tabla simplex inicial.

Esto puede extenderse cuando B e I aparecen en diversas columnas en la tabla simplex inicial, si al final del procedimiento las columnas que formaban la matriz identidad no hacen parte de las básicas, en esas columnas se tendrá B⁻¹. En las celdas de la última fila de las columnas de la matriz I en la primera tabla simplex, estará c_I en la primera iteración y aparecerá p en la última.

3.1.2 Lecturas recomendadas

La presentación de esta guía se basa en [6] (secciones 2.2, 4.1 y 4.3).

3.1.3 Ejercicios

Considera un problema en forma canónica de minimización, muestre que el dual del dual es el primal.
(Ejercicio 6.2 de [4]) Considere el problema

min 2x₁+3x₂+5x₃+6x₄

s.a x₁+2x₂+3x₃+x₄≥ 2

−2x₁+x₂−x₃+3x₄ ≤ −3

x₁,x₂,x₃,x₄≥ 0
- Plantee el problema dual
- Resuelve el dual geométricamente
- Utilice información sobre la solución del dual y los teoremas de dualidad para resolver rapidamente el primal.
A partir de la definición de problema dual para un problema de minimización en forma canónica deduzca el planteamiento de dualidad para un problema en forma estándar.
(Ejercicio 6.8 de [4]) La siguiente tabla simplex muestra la solución óptima de un problema de programación lineal. Se sabe que x₄ y x₅ son las variables de holgura en la primera y segunda restricciones del problema original. Las restricciones son del tipo ≤.

0

1

2
1

1

2
0

5

2

1

−

1

2

0

−

1

6

1

3

5

2

0 4 0 4 2 40
(Ejercicio 6.10 de [4]) Considere el problema: Minimizar cx sujeto a Ax=b, x≥ 0, en donde m=n, c=b y A=A^T. Usando dualidad demostrar que si existe un x₀ tal que Ax₀=b, entonces x₀ es un punto óptimo.
(Ejercicio 4.1.4 de [9]) Encuentre el dual del siguiente problema de dos maneras (a) reduciendo a forma canónica y (b) reduciendo a forma estándar.

max −5x₁+2x₂

s.a −x₁+x₂≤ −2

2x₁+3x₂ ≤ 5

x₁,x₂≥ 0
(Ejercicio 4.2.4 de [9]) Se tiene el siguiente problema de programación lineal

max x₁+5x₂+3x₃

s.a x₁+2x₂+x₃=3

2x₁−x₂ =4

x₁,x₂,x₃≥ 0
- Escriba el problema dual asociado
- Dado que las variables básicas óptimas son x₁ y x₃, determine la solución dual óptima asociada.

3.2 Sensibilidad

Indicadores de logro:

INDICADOR: Plantea y realiza análisis de sensibilidad

3.2.1 Teoría

Simplex Dual

Simplex Generalizado

3.2.2 Lecturas recomendadas

La presentación de esta guía se basa especialmente en [9].

3.2.3 Ejercicios

(Ejercicio 2.5.12 de [9]) Un fabricante produce tres modelos I, II y III de cierto producto usando las materias primas A y B. La tabla siguiente muestra los datos para el problema.

Modelo I II III Disponibilidad

A 2 3 5 4000

B 4 2 7 6000

Demanda mínima 200 200 150

Utilidad por unidad 30 20 50

El tiempo de mano de obra para el modelo I es el doble que para el modelo II y el triple de III, todo el personal de fabrica puede producir el equivalente de 1500 unidades del modelo I. Las necesidades del mercado especifican las relaciones 3:2:5 de las producciones de los tres modelos respectivos.
1. Formule el problema como un problema de programacion lineal y suponga que el fabricante puede comprar mas unidades de la materia prima A a $12 por unidad. ¿Seria adecuado?
2. Recomendaria usted al fabricante comprar mas unidades de la materia prima B a $5 por unidad.
(Ejercicio 4.4.B.1 de [9]) El modelo de programacion lineal siguiente no tiene solucion. Indique como se detecta la condición en el procedimiento simplex generalizado.

min −x₁−x₂

s.a x₁−4x₂≥ 5

x₁−3x₂ ≤ 1

2x₁−5x₂ ≥ 1

x₁,x₂≥ 0
(Ejercicio 4.4.B.2 de [9]) El modelo de programación lineal siguiente no tiene solución acotada. Indique como se detecta esta condición en el procedimiento simplex generalizado.
¿Cómo variar el metodo simplex para agregar una restricción después de conocer la solución al problema inicial?
¿Cómo variar el método simplex para cambiar la función de costo después de tener solución al problema inicial?

3.3 Análisis de sensibilidad

Indicadores de logro:

INDICADOR: Efectua análisis de sensibilidad
INDICADOR: Emplea métodos que complementan simplex y facilitan la realización de un análisis de sensibilidad

3.3.1 Teoría

Dual-Simplex

Simplex generalizado

Cambios en el vector b

Cambios en el vector c

Adición de una restricción

3.3.2 Lecturas recomendadas

La presentación de esta guía se basa especialmente en [9].

3.3.3 Ejercicios

(Ejercicio 6.27 de [4])Resolver usando dual simplex

max −4x₁−6x₂−18x₃

sujeto a x₁+x₃≥ 3

x₂+2x₃≥ 5

x₁, x₂, x₃≥ 0
Dar valores optimos de variables primales y duales(tanto dual del original como dual del problema en forma estandar) Mostrar que satisface holgura complementaria.
Plantee un problema de programnación lineal al menos con 8 variables, el cual requiera emplear simplex generalizado. Resuelvalo y halle valores óptimos del primal y del dual (tanto del original como del problema en forma estándar). Muestre que cumple holgura complementaria.
(Ejercicio 6.19 de [4]) Use el teorema principal de dualidad para demostrar el teorema de Farkas. (Sugerencia: Considere el siguiente problema primal y su dual:

min 0x

s.a. Ax=b

(x)≥ 0

max (x)^T(b)

s.a. (x)^TA≤0

x no restringido
(Ejercicio 6.49 de [4]) Considere el siguiente problema de programación lineal:

max 2x₁+x₂−x₃

s.a. x₁+2x₂+x₃≤ 8

−x₁+x₂−2x₃≤ 4

x₁, x₂, x₃≥ 0
1. Solucionelo.
2. Escriba el dual y encuentre las variables duales óptimas.
3. Usando análisis de sensitividad, encontrar la nueva solución óptima si el coeficiente de x₂ en la función objetivo se cambia de 1 a 5.
4. Hallar nueva solución, si el coeficiente de x₃ en la segunda restricción se cambia de -2 a 1.
5. Hallar nueva solución,si se añade la restricción x₂+x₃≥ 2.
6. Si hubiera que escoger entre aumentar el lado derecho de la primera restricción o el de la segunda ¿Cuál escogería? ¿Cuál es el efecto de tal incremento en la función objetivo?

(Ejercicio 6.19 de [4]) Considere la siguiente tabla simplex de un problema de maximización con restricciones de tipo ≥ :

⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣

−1

−2

−3

−17

⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦

¿Se alterará la solución si se añadiera al problema una nueva actividad x₉ con coeficientes (2,0,3)^T en las restricciones y precio 5?
¿Qué tan grande puede ser b₁ (la primera restricción sobre recursos) sin violar la factibilidad?

min	2x₁+3x₂+5x₃+6x₄
s.a	x₁+2x₂+3x₃+x₄≥ 2
	−2x₁+x₂−x₃+3x₄ ≤ −3
x₁,x₂,x₃,x₄≥ 0

max	−5x₁+2x₂
s.a	−x₁+x₂≤ −2
	2x₁+3x₂ ≤ 5
x₁,x₂≥ 0

max	x₁+5x₂+3x₃
s.a	x₁+2x₂+x₃=3
	2x₁−x₂ =4
x₁,x₂,x₃≥ 0

Modelo	I	II	III	Disponibilidad
A	2	3	5	4000
B	4	2	7	6000
Demanda mínima	200	200	150
Utilidad por unidad	30	20	50

min	−x₁−x₂
s.a	x₁−4x₂≥ 5
	x₁−3x₂ ≤ 1
	2x₁−5x₂ ≥ 1
x₁,x₂≥ 0

max	−4x₁−6x₂−18x₃
sujeto a	x₁+x₃≥ 3
	x₂+2x₃≥ 5
	x₁, x₂, x₃≥ 0

max	2x₁+x₂−x₃
s.a.	x₁+2x₂+x₃≤ 8
	−x₁+x₂−2x₃≤ 4
	x₁, x₂, x₃≥ 0