Dualidad

An´lisis de dualidad y sensibilidad a
La soluci´n optima de una programaci´n lineal se basa en una toma instant´nea o ´ o a de las condiciones que prevalecen en el momento de formular y resolver el modelo. En el mundo real, los ambientes de decisi´n rara vez permanecen est´ticos, y es esencial o a determinar c´mo cambia la soluci´n optima cuando cambian los par´metros del modelo. o o ´ a Eso eslo que hace el an´lisis de sensibilidad. Proporciona t´cnicas de c´mputo eficientes a e o para estudiar el comportamiento din´mico de la soluci´n optima que resulta al hacer a o ´ cambios en los par´metros del modelo. a Ya explicamos el an´lisis de sensibilidad a un nivel elemental. Ahora, usaremos la a teor´ de la dualidad para presentar un tratamiento algebraico de este importante asıa pectopr´ctico. a
´ DEFINICION DEL PROBLEMA DUAL

El problema dual es una programaci´n lineal definida en forma directa y sistem´tica a o a o a partir del modelo original (o primal) de programaci´n lineal. Los dos problemas est´n relacionados en forma tan estrecha que la resoluci´n optima de un problema produce en o ´ forma autom´tica la resoluci´n optima del otro. a o ´ En la mayor parte de laspresentaciones de programaci´n lineal, el dual se define para o varias formas del primal, dependiendo del sentido de la optimizaci´n (maximizaci´n o o o mini-mizaci´n), tipos de restricciones (≤, ≥ o =), y la orientaci´n de las variables (no o o negativa o no restringida). Este tipo de tratamiento puede confundir Por esta raz´n o presentaremos una sola definici´n que comprenda en forma autom´tica a todas lasformas o a del primal. Nuestra definici´n del problema dual requiere expresar el problema primal en forma o de ecuaciones, como se present´ anteriormente: todas las restricciones son ecuaciones, o con lado derecho no negativo y todas las variables son no negativos. Este requisito es consistente con el formato de la tabla de inicio s´ ımplex. En consecuencia, todo resultado obtenido a partir de lasoluci´n primal optima se aplican en forma directa al problema o ´ dual asociado. Para mostrar c´mo se forma el problema dual, se define el primal en forma de o ecuaci´n como sigue: o
n

Maximizar o minimizarz =
j=1

cj x j

(1)

sujeta a

1

n

aij xj
j=1

= bi , i = 1, 2, . . . , m ≥ 0, j = 1, 2, . . . , n

(2) (3)

xj

Las variables xj , j = 1, 2, . . . , n, incluyen lasvariables excedentes, holguras y artific´ ıales, si las hay. La tabla 1 muestra c´mo se construye el problema dual a partir del primal. De hecho o se tiene que:

Cuadro 1: Construcci´n del dual a partir del primal o Variables primales x1 x2 . . . xj . . . xn Variables duales c1 c2 ... cj . . . cn y1 a11 a12 . . . a1j . . . a1n b1 y2 a21 a22 . . . a2j . . . a2n b2 . . . . . . . . . . . . . . . .. . . . . . . . ym amj am1 am2 . . . . . . amn bm ↑ ↑ j-´sima e Coeficientes restricci´n dual o objetivo duales 1. Se define una variable dual por cada ecuaci´n primal (restricci´n). o o 2. Se define una restricci´n dual por cada variable primal. o 3. Los coeficientes de restricci´n (columna) de una variable primal definen los o coeficientes en el lado izquierdo de la restricci´n dual, y su coeficienteobjetivo define el o lado derecho. 4. Los coeficientes objetivo del dual son iguales al lado derecho de las ecuaciones de restricci´n primal. o Las reglas para determinar el sentido de la optimizaci´n (maximizaci´n o minimizao o ci´n), el tipo de restricci´n (≤, ≥ o =), y el signo de las variables duales (siempre no o o restringido) se resumen en la tabla 2. N´tese que el sentido de la optimizaci´nen el dual o o siempre es el opuesto al del primal. Una forma f´cil de recordar el tipo de restricci´n (es a o decir, ≤ o ≥) en el dual es que si el objetivo del dual es minimizaci´n (es decir, “apunta o hacia abajo”), las restricciones son todas del tipo ≥ (es decir, “apuntan hacia arriba”). Cuando el objetivo del dual es maximizaci´n lo contrario es v´lido. o a

2

Cuadro 2: Reglas para...