METODO DUAL

MÉTODO DUAL

JULIETH PATRICIA BOCANEGRA NIETO

KAREN JULIETH VILLADIEGOBAENA

NILSA PEÑALOZA GONZALEZ

Estudiantes

CARMEN MATÍAS

Docente

UNIVERSIDAD DE LA GUAJIRA EXTENSIÓN MAICAO

PROGRAMA DE ADMINISTRACION DE EMPRESAS

MAICAO-LA GUAJIRA

I P.A

2010

PROBLEMA DUAL

Todo problema de programación lineal tiene un problema relacionado con él, el cual se le llama problema dual o, simplemente dual. En un problema original de programación lineal, denominado problema primario o, simplemente primario, el dual puede formularse con la información obtenida en el primario. El problema dual es importante por muchas razones teóricas y, además, por motivos prácticos. Una de sus propiedades es que, al ser resuelto, suministra información indispensable sobre la solución del problema primario. De manera análoga, la solución del primario da toda la solución esencial relativa a la solución del problema dual. En un problema de programación lineal, su solución puede determinarse resolviendo el problema original o su dual. Las propiedades estructurales de los dos problemas pueden provocar una decidida preferencia por cuál problema solucionar. Aun con los métodos computarizados, las eficiencias del cómputo pueden provenir de la solución de una forma de problema.

En la mayoría de los procedimientos de Programación Lineal, el dual se define para varias formas del primal, dependiendo de los tipos de restricciones, de los signos de las variables y del sentido de la optimización. La experiencia nos indica que en ocasiones, los principiantes se confunden con los detalles de esas definiciones. Más importante aún es que el uso de esas definiciones múltiples puede conducir a interpretaciones inconsistentes de los datos en la tabla simplex, sobre todo en lo que respecta a los signos de las variables.

El concepto de dualidad indica que para cada problema de Programación Lineal hay una asociación y una relación muy importante con otro problema de programación lineal, llamado precisamente dual.

 La relación entre el problema dual y su asociado, es decir el problema original llamado primal, presenta varias utilidades:

 Aporta elementos que aumentan sustancialmente la compresión de la Programación Lineal.

 El análisis de dualidad es una herramienta útil en la solución de problemas de Programación Lineal, por ejemplo: más restricciones que variables.

 El problema dual tiene interpretaciones e informaciones importantes que muestran que los análisis marginales están siempre involucrados implícitamente al buscar la solución óptima a un problema de Programación Lineal.

LAS RELACIONES EXISTENTES ENTRE AMBOS PROBLEMAS

El dual tiene tantas variables como restricciones existen en el primal.

1. El dual tiene tantas restricciones como variables en el primal.

2. Los coeficientes de la función objetivo del primal son los términos independientes de las restricciones del dual.

3. Los términos independientes de las restricciones del primal son los coeficientes en la función objetivo del dual.

4. la matriz de coeficientes de las restricciones del dual es igual a la transpuesta de la del primal.

TIPOS DE PROBLEMAS DUALES

1. Duales Simétricos: para primales que incluyan restricciones de desigualdad.

2. Duales Asimétricos: para primales en forma estándar, es decir con restricciones de igualdad.

Otro tipo de restricciones entre los problemas primal y dual son las siguientes:

1. para duales simétricos el sentido de desigualdad de las restricciones del dual es inverso a las del primal; mientras que para asimétricos, las restricciones del dual son de sentido menor e igual en caso de que el problema dual sea de minimización, y de mayor e igual en caso de maximización. Además, las variables del dual, variables duales, no están sujeta a la condición de no negatividad.

2. El problema dual de uno de minimización es de maximización y viceversa.

3. El dual del dual es el primal.

La siguiente tabla sintetiza la simetría de los dos tipos de problema y sus relaciones:

Problema de maximización Problema de minimización

Numero de restricciones

Numero de variables

Restricción

Variable no negativa

Restricción

Variable no positiva

Restricción

Variable no restringida

Numero de Variables

Numero de restricciones

Variable no negativa

Restricción

Variable no positiva

Restricción

Variable no restringida

Restricción

Coeficiente de la función objetivo para la j-ésima variable

Constante del miembro derecho para la restricción j-ésima

Constante del miembro derecho para la j-ésima restricción

Coeficiente de la función objetivo para la variable j

Coeficiente en restricción i para la variable j

Coeficiente en restricción j para la variable i

Sin distinguir en el caso de duales simétricos o asimétricos, podemos formular una tabla general, que reúne las relaciones entre el problema primal y Dual sea cual sea su formulación:

PROBLEMA DE MINIMIZACION PROBLEMA DE MAXIMIZACION

VARIABLES ≥ 0

≤ 0

No restringidas ≤

≥

=

RESTRICCIONES

RESTRICCIONES ≥

≤

=

≥ 0

≤ 0

No restringidas

VARIABLES

TEOREMAS DE DUALIDAD

Los siguientes teoremas establecen las relaciones entre el problema primal, el dual y sus soluciones. En todas ellas se utiliza la forma primal-dual simétrica.

Teorema 1 El dual del dual es el primal.

Teorema 2 (Dualidad débil) Sean x e y soluciones factibles para los problemas primal y dual respectivamente. Se verifica

z = cTx ≤ bTy = G

Corolario 1 Si las soluciones factibles x* e y* verifican

cTx* = bTy*, entonces x e y son soluciones óptimas para el primal y el dual respectivamente.

Corolario 2 Si el problema primal es factible y no acotado, el dual no tiene solución.

Corolario 3 Si el problema dual es factible y no acotado, el

...