INTRODUCCIÓN

Cada problema de programación lineal ( Primal ) está estrechamente relacionado con otro problema simétrico a él, denominado problema dual.

El dualismo es una teoría que surge como consecuencia de una profundización en el estudio de la programación lineal porque la distribución de los recursos y la formación de los precios son dos aspectos del mismo problema. Entonces la doble formulación de la programación lineal no se debe considerar como un simple ejercicio matemático, sino que una y otra versión del problema vienen a explicar dos aspectos económicos distintos para una misma situación problémica. Una propiedad fundamental de la relación entre el primal y el dual es que la solución optima de cualquiera de estos problemas proporciona la solución óptima para el otro.

De allí la importancia de la realización de este blog donde se estará hablando de todo lo referente a la dualidad de programación lineal tema de mucha importancia en especial para los estudiantes de Informática. 

DUALIDAD EN PROGRAMACION LINEAL

Relaciones primal-dual

         Asociado a cada problema lineal existe otro problema de programación lineal denominado problema dual (PD) , que posee importantes propiedades y relaciones notables con respecto al problema lineal original, problema que para diferencia del dual se denomina entonces como problema primal (PP).

 Las relaciones las podemos enumerar como siguen:

 a) El problema  dual tiene tantas  variables como restricciones tiene el programa primal.

 b) El problema  dual tiene tantas  restricciones como variables tiene el programa primal

 c) Los coeficientes de la función objetivo del problema dualson los términos independientes de las restricciones o RHS del programa primal.  d) Los términos independientes de las restricciones o RHS del dual son los coeficientes de la función objetivo del problema primal.

 e) La matriz de coeficientes técnicos del problema dual es la traspuesta de la matriz técnica del problema primal.

 f) El sentido de las desigualdades de las restricciones del problema  dual y el signo de las variables del mismo problema, dependen de la forma de que tenga el signo de las variables del problema primal  y del sentido de las restricciones del mismo problema. ( Ver tabla de TUCKER)

 g) Si el programa primal es un problema de maximización, el programa dual es un problema de minimización.

 h) El problema  dual de un problema  dual es el programa primal original.

REGLAS DE OBTENCIÓN DE DUAL

Si el modelo está escrito de forma canónica, el dual resulta singularmente fácil de obtener; si se trata de obtener el dual del dual, se obtendrá el primal, siendo así se trata de una correspondencia biunívoca.

De forma general las reglas para obtener el dual en cualquier modelo lineal se indican de la siguiente forma.

INTERPRETACIÓN DE LAS VARIABLES DUALES

          Cada variable de dual está asociada a una restricción del programa primal, y su valor óptimo representa el incremento de la función objetivo del primal por cada unidad que aumente, el término independiente de dicha restricción, siempre que este último aumento no suponga un cambio de base. Los valores de estas variables se denominan precios sombra; los precios sombra obtenidos a partir del optimo del dual serán validos siempre que no varíe la base optima. En consecuencia los resultados obtenidos del dual están íntimamente ligados al análisis de sensibilidad de los términos independientes.

OBTENCIÓN DE LA SOLUCIÓN DUAL

       El dual de un modelo lineal es otro modelo lineal que puede solucionarse después de las oportunas trasformaciones, si alguna de las variables resultantes es no negativa o no restringida en signo, del mismo modo que el primal, sin embargo puede obtenerse la solución del dual resolviendo el primal. Existen dos modos de obtener una solución óptima del dual:

•   A partir de la tabla simplex optima del primal, la solución obtenida nos permitirá tener un importante resultado. El teorema de la holgura complementaria.
•   Mediante un programa informático, dado que los programas de resolución de modelos lineales realizan el análisis de sensibilidad, podemos realizar un análisis más exacto de la evolución de los precios sombra.

DUAL SIMÉTRICO Y ASIMÉTRICO

         Los problemas duales simétricos son los que se obtienen de un problema primal en forma canónica y normalizada, es decir, cuando llevan asociadas desigualdades de la forma mayor o igual en los problemas de minimización, y desigualdades, menor o igual para los problemas de maximización. Es decir, si el problema original es de la siguiente forma:

Máx. Z(x) = ct x

s.a:

A x ≤ b

x ≥ 0

El problema dual simétrico es:

Mín. G(λ) = λ b

s.a:

λ A ≥ c

λ ≥ 0

Los restantes tipos de combinaciones de problemas, se conocen con el nombre deduales asimétricos:

Máx. Z(x) = ct x

s.a:

A x = b

x ≥ 0

El problema dual asimétrico es:

Mín. G(λ) = λ b

s.a:

λ A ≥ c

λ >< 0, es decir, variables libres.

CARACTERÍSTICAS DE LAS SOLUCIONES DEL DUAL Y DEL PRIMAL

       Si el primal tiene solución óptima acotada x*, el dual también tendrá solución óptima acotada u*.

a) Ambas soluciones darán el mismo valor de la función objetivo:

c’· x* = b’ · u*

b) Si uno de los dos problemas tiene óptimo no acotado, el otro no tendrá solución (la región factible será un conjunto vacío)