UNIVERSIDAD TECNOLÓGICA DE SANTIAGO

(UTESA)

ASIGNATURA

Investigación de Operaciones 2

TEMA

Dualidad

NOMBRES Y MATRICULAS

Wellington Aybar Torres

106-3874

PROFESOR/A

José C. López

Santo-Domingo RD.

Fecha

15/junio 2020
 INTRODUCCION

Uno de los descubrimientos más importantes durante el desarrollo inicial de la programación

lineal fue el concepto de dualidad y sus muchas e importantes ramificaciones.

Este descubrimiento revelo que asociado a todo problema de programación lineal existe otro
problema lineal llamado dual. Las relaciones entre el dual y su original (llamado primal) son
extremadamente útiles en una gran variedad de situaciones. Por ejemplo, se verá que de
hecho la solución optima del problema dual es la que proporciona los precios sombra
descritos en las practicas al introducir el análisis de sensibilidad.

Uno de los papeles clave que juega la teoría de la dualidad es la interpretación y realización
del análisis de sensibilidad. De hecho la dualidad nos permitirá tratar dicho análisis desde el
punto de vista algebraico pudiendo así generalizarlo y aplicarlo a cualquier problema de
programación lineal, independientemente de cuál sea su tamaño i.e., número de variables y/o
restricciones.
DUALIDAD

Todo problema de optimizacion (primal), tiene un problema asociado (dual) con numerosas
propiedades que los relacionan y nos permiten hacer un mejor analisis de los problemas.

CONSTRUCCION DE L PROBLEMA DUAL

1. Si es problema de minimizacion el dual sera maximizacion

2. En el dual habra tantas variables como restricciones en el primal
3. En el dual habra tantas restriciones como variables en el primal
4. Los coeficientes de la funcion objetivo del dual vendran dados por los coeficientes del
lado derecho de las restricciones del primal
5. Los coeficientes del lado derecho del dual vendran dados por los coeficientes de la
funcion objetivo del primal
6. Los coeficientes que acompañaran a las variable en una restriccion del dual
corresponderan, a aquellos coeficientes que acompañan a la variable primal
correspondiente a la restriccion prima
7. Para saber si las restricciones duales son menor o mayor, se recurre a la tabla de
relaciones primal-dual.
8. Para saber si las variables duales son < 0 = 0 o > 0 se recurre a la tabla de relaciones
primal dual.

RELACIONES PRIMAL DUAL

Relaciones Primal-Dual Estas relaciones nos permiten pasar de un problema de primal a su

dual en forma bastante algorítmico, tanto para problemas de minimización como de
maximización.

PROBLEMA DE MINIMIZACION PROBLEMA DE MAXIMIZACION

Restricciones Variables

≥ ≥0
= Irrestricta
≤ 0≤

Variables Restricciones
≥0 <
Irrestricta =
≥0 >

ALGUNOS TEOREMAS DE DUALIDAD

 Teorema Débil de Dualidad

Si ¯x e ¯y son factibles para (P) y (D) respectivamente, entonces z (¯x) ≥ w (¯y).

  Teorema Fundamental de Dualidad

Dados un par de problemas primal-dual, si uno de ellos admite solución ´optima, entonces el
otro también la admite y los respectivos valores óptimos son iguales.

 Teorema de holgura complementaria

Sean ¯x e ¯y soluciones factibles para los problema (P) y (D) respectivamente. ¯x e ¯y son
´óptimos si y solo si:

i) (αi · x¯ − bi) · y¯i = 0 i=1,...,m.

ii) ii) (cj − y¯ · βj ) · x¯j = 0 j=1,...,n.

Obs: Notar que (αi · x¯ − bi) y (cj − y¯ · βj ) son las variable de holgura de los problemas (P)
y (D) respectivamente.

ACERCA DE LOS PRECIOS SOMBRA

Se le llama precio sombra al vector de variables duales en el ´optimo.

ACERCA DE SENSIBILIDAD

En este ´ámbito, podemos distinguir 2 tipos de análisis:

 Análisis de sensibilidad: Consiste en determinar cuál es el rango de variación de los

parámetros del problema de modo que la base ´optima encontrada siga siendo
´optima.
 Análisis post optimal: Consiste en determinar como varia la base ´optima si cambia
alguno de los parámetros del problema.

 Variación en el parámetro b. Buscamos el rango en el que puede tomar valores b de

modo que la base B siga siendo ´optima.

Para ello debemos verificar:

1. Factibilidad: xB = B−1 b ≥ 0

2. Optimalidad: ¯cR = cR − cBB−1R ≥ 0

Como en la ecuación 2. No hay dependencia explicita de b, no impone condiciones y por

tanto solo debemos verificar 1.
  Variaciones en el parámetro c

Buscamos el rango en el que puede tomar valores c de modo que la base B siga siendo
´optima. Para ello debemos verificar:

1. Factibilidad: xB = B−1 b ≥ 0

2. Optimalidad: ¯cR = cR − cBB−1R ≥ 0

Como en la ecuación 1. No hay dependencia explicita de b, no impone condiciones y por

tanto solo debemos verificar 2. Notemos que al variar un coeficiente de cj a ˆcj e imponer la
condición 2. Surgen dos casos:

• Caso 1: variable xj es no básica.

c¯j = ˆcj − cBB−1βj cambia.

c¯k = ck − cBB−1βk no cambia (i 6= j).

Por lo tanto sólo tenemos que imponer 1 ecuación: la de costo reducido asociado a variable
que cambio.

• Caso 2: variable xj es básica.

c¯k = ¯ck − cˆBB−1βk puede cambiar ∀ k.

Por lo tanto, no basta con examinar una única ecuación y se debe inspeccionar todas las
ecuaciones de costo reducido. As´ı:

◦ Si cambia cj de variable no básica se impone ¯cj ≥ 0.

◦ Si cambia cj de variable básica se impone ¯ck ≥ 0 ∀ xk no básica.

PROBLEMA 1

Una florista sabe hacer solo 2 tipos distintos de arreglos florales (x1 y x2) para los cuales
dispone de 3 tipos distintos de flores: rozas, tulipanes e ibizcos. Los requerimientos de flores
para cada arreglo, la disponibilidad de flores y los precios de cada arreglo vienen dados por:

FLORES x1 x2 DISPONIBILIDAD

Rozas 3 1 300

Tulipanes 1 1 140

Ibizcos 1 3 300

PRECIO 2000 1000 -

1. Formule un PPL que resuelva el problema de maximización de ingresos por ventas sujeto a
la disponibilidad de recursos.

2. ¿Cual es el problema dual asociado? ¿Que situación podria estar optimizando?

3. Usando el teorema de holgura complementaria, encuentre el ´optimo del problema dual

sabiendo que el ´optimo primal viene dado por (x1 = 80, x2 = 60).

4. Suponga que retorna frustrado después que una bella dama le cerrara la puerta cuando
usted le llevaba amablemente una rosa, un tulipán y un ibizco 6 . Si se encuentra con la
florista, ¿Cuanto cree que estaria dispuesta a pagar ella por sus flores?

Solución

1. A estas alturas del curso, todos debieran de poder modelar un problema tan sencillo
como este por lo que ahorrare comentarios:

Max z = 2000x1 + 1000x2

S.a 3x1 + x2 ≤ 300
X1 + x2 ≤ 140
X1 + 3x2 ≤ 300
X1, x2 ≥ 0
2. Para encontrar el dual, procedemos como se describió en la introducción teórica de
esta clase aplicando las relaciones de dualidad:

Min w = 300y1 + 140y2 + 300y3

S.a 3y1 + y2 + y3 ≥ 2000
y1 + y2 + 3y3 ≥ 1000
y1, y2, y3 ≥ 0

3. La florista ha encontrado su combinación ´optima (¯x1 = 80, x¯2 = 60). Sabemos que en el
´optimo se cumple el teorema de holgura complementaria. Entonces, podemos aplicarlo:

a) (3¯x1 + ¯x2 − 300) · y¯1 = 0

b) (¯x1 + ¯x2 − 140) · y¯2 = 0

c) (¯x1 + 3¯x2 − 300) · y¯3 = 0

d) (2000 − 3¯y1 − y¯2 − y¯3) · x¯1 = 0

e) (1000 − y¯1 − y¯2 − 3¯y3) · x¯2 = 0

Como ¯x1 = 80 y ¯x2 = 60, se tiene que:

a) ⇒ y¯1 ∈ R

b) ⇒ y¯2 ∈ R

c) ⇒ y¯3 = 0

d) ⇒ 3¯y1 + ¯y2 = 2000

e) ⇒ y¯1 + ¯y2 = 1000

Resolviendo el sistema:

y¯1 = 500 ¯y2 = 500 ¯y3 = 0

Notar que z (¯x) = w (¯y) = 220000

¿Como se interpreta esto?. La florista venderá rosas y tulipanes a un precio de $500 cada una
y entregará como oferta los ibizcos gratis, pero esto solo si se vende todo como un paquete.

Problema 2

Considere el clásico problema de combinación de productos sujeto a restricciones de

disponibilidad de recursos:

Max z = x1 + 3x2

s.a x1 + 4x2 ≤ 100

X1 + 2x2 ≤ 60

X1 + x2 ≤ 50

X1, x2 ≥ 0

Hint: En el ´optimo, la base está formada por las variables x1, x2 y x5, en donde se han
asignado las variables x3, x4 y x5 como holgura de las restricciones según el orden
enunciado.

Solución

Antes de cualquier cosa, pasamos a forma estándar:

Min ˜z = −x1 − 3x2

s.a x1 + 4x2 + x3 = 100

x1 + 2x2 + x4 = 60
x1 + x2 + x5 = 50

x1, x2, x3, x4, x5 ≥ 0

Un análisis general nos conduciria a un espacio de soluciones en R3. Sin embargo, lo usual es
analizar la variación de la disponibilidad de un recurso dejando los otros constantes (ceteris
paribus).

Como ya se argumentó, ahora solo nos preocuparemos de la condición de optimalidad: c¯R =

cR − cBB−1R ≥ 0. Al igual que el caso anterior, se estudiará la sensibilidad de los parámetros
independientemente.

Adelantando un poco, este problema cabe dentro de análisis post optimal pues veremos cual
es nuevo ´optimo para una variación dada del los parámetros del problema. Claramente la
incorporación de este nuevo producto, como no se está produciendo (nuevo = 0), no viola la
factibilidad del problema. Luego, sólo tenemos que verificar la optimalidad:

En mas de alguna parte habrán leido que dualidad es una poderosa herramienta de análisis de
sensibilidad y post optimal, pero sin embargo nunca la hemos usado con esos propósitos. En
efecto, la parte 3. De este problema es equivalente a la verificación de una ´única condición
dada por la restricción dual asociada a la nueva variable

Nuevo: 5¯y1 + 3¯y2 + 3¯y3 ≥ 1

y¯1, ¯y2 e ¯y3 son los valores ´óptimos del problema original y se determinan a partir de la
solución primal.

Problema 3 Comente acerca de la veracidad o falsedad de las siguientes aseveraciones:

1. Si un problema de programación lineal es infactible su dual es necesariamente no acotado.

2. Si conozco la solución ´optima de un PPL, tengo inmediatamente el valor de la función

objetivo ´optima del problema dual asociado sin necesidad de utilizar el teorema de holgura
complementaria.

3. Si conozco los precios sombra de un problema de programación lineal puedo reconstruir

directamente la solución (primal) de este problema.

4. El precio sombra de toda restricción inactiva es cero.

5. Hacer análisis de sensibilidad corresponde a utilizar la información dada por la resolución

de un PPL para ver como sería la nueva solución si varía alguno de los parámetros del
problema.

Solución

1. Falso ya que el problema dual puede ser infactible.

 2. Verdadero porque se tendrá que el valor de la función objetivo dual ´optima coincidirá con
el valor de la función objetivo primal ´optima.

3. Verdadero pues el vector de precios sombras es el vector de variables duales ´optimas.

Luego, puedo aplicar el teorema de holgura complementaria para recuperar la solución
primal.

4. Verdadero. Basta aplicar el teorema de holgura complementaria. Otra forma de verlo es a

través de un problema de producción (combinación de productos): Al aumentar
marginalmente la disponibilidad de un recurso sobre el cual tenemos holguras, no nos aporta
ningún aumento de los beneficios.

5. Falso. Eso corresponderia a análisis post optimal. Análisis de sensibilidad estudia las
condiciones que deben darse sobre los parámetros para que la solución siga siendo ´optima.