DEFINICIÓN DEL PROBLEMA DUAL

DEFINICIÓN DEL PROBLEMA DUAL

El problema  dual es una programación lineal definida en forma directa  y sistemática a partir del modelo original (o primal) de programación lineal. Los dos problemas están relacionados en forma tan  estrecha  que resolución óptima de un problema  produce en forma automática la resolución óptima del otro.

En la mayor parte  de las presentaciones de programación lineal, el dual se define para varias  formas del primal,  dependiendo  del sentido de la optimización (maximización  o minimización), tipos  de restricciones  (≤, ≥ o =),  y la orientación de las variables  (no negativa  o no restringida). Este  tipo  de tratamiento puede  confundir  Por  esta razón presentaremos una sola definición que comprenda en forma automática a todas las formas del primal.

Nuestra definición del problema  dual requiere expresar  el problema  primal en forma de ecuaciones,  como se presentó  anteriormente: todas  las restricciones  son ecuaciones, 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 óptima se aplican  en forma directa  al problema dual asociados.

Para mostrar cómo se forma el problema dual, se define el primal en forma de

ecuación como sigue:

maximizar o minimizar=j=1n                        (1)

j=1  naijxj=bii=1,2,...m                              (2)

xj0,j=1,2,...n                                   (3)

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 se tiene que:

1. Se define una variable  dual por cada ecuación primal  (restricción).

2. Se define una restricción dual por cada variable  primal.

3. Los coeficientes  de restricción (columna)   de  una  variable  primal  definen  los coeficientes en el lado izquierdo de la restricción dual, y su coeficiente objetivo define el lado derecho.

4. Los coeficientes objetivo  del dual son iguales al lado derecho de las ecuaciones de restricción primal.

Las reglas para  determinar el sentido de la optimización (maximización o minimización), el tipo  de restriccio´n (≤, ≥ o =),  y el signo de las variables  duales  (siempre  no restringido) se resumen en la tabla  2. Nótese que el sentido de la optimización en el dual siempre es el opuesto al del primal. Una forma fácil de recordar  el tipo de restricción (es decir, ≤ o ≥) en el dual es que si el objetivo del dual es minimización  (es decir, “apunta hacia abajo”),  las restricciones  son todas  del tipo ≥ (es decir, “apuntan hacia arriba”). Cuando  el objetivo  del dual es maximizacion  lo contrario es válido.