dualidad y analisis de sencibilidad

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 es lo 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 esteimportante asıa
pecto pr´ctico.
a
´
DEFINICION DEL PROBLEMA DUAL

El problema dual es una programaci´n lineal definida en forma directa y sistem´tica a
o
a
partir del modelo original (o primal) de programaci´n lineal. Los dos problemas est´n
o
a
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.
ao ´
En la mayor parte de las presentaciones 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 soladefinici´n que comprenda en forma autom´tica a todas las formas
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 la soluci´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 =

cj x j
j=1

sujeta a

1

(1)

n

aij xj

= bi , i = 1, 2, . . . , m

(2)

≥ 0, j = 1, 2, . . . ,n

(3)

j=1

xj

Las variables xj , j = 1, 2, . . . , n, incluyen las variables 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
y1a11 a12 . . .
a1j
. . . a1n
b1
y2
a21 a22 . . .
a2j
. . . a2n
b2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
ym
am1 am2 . . .
amj
. . . 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 coeficiente objetivo 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 tipode 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´n en 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...