INTRODUCCIÓN

Hemos visto como la programación lineal puede ser usada para resolver una extensa

variedad de problemas propios de los negocios, ya sea para maximizar utilidades o

minimizar costos. Las variables de decisión en tales problemas fueron, por ejemplo, el

número de productos a producir, la cantidad de pesos a emplear, etc. En cada caso la

solución óptima no explicó cómo podrían ser asignados los recursos (ejemplo: materia

prima, capacidad de las máquinas, el dinero, etc.) para obtener un objetivo establecido.

A cada problema de programación lineal se le asocia otro problema de programación

lineal, llamado el problema de programación dual. La solución óptima del problema de

programación dual, proporciona la siguiente información respecto del problema de

programación original:

1. La solución óptima del problema dual proporciona los precios en el mercado o los

beneficios de los recursos escasos asignados en el problema original.

2. La solución óptima del problema dual aporta la solución óptima del problema original

y viceversa.

Normalmente llamamos al problema de programación lineal original el problema de

programación primal.

Encontrar el optimo de un problema de optimización, es solo una parte del proceso de

solución. Muchas veces nos interesar +a saber como varía la solución si varía alguno de

los parámetros del problema que frecuentemente se asumen como determinısticos,

pero que tienen un carácter intrínsecamente aleatorio. Mas específicamente nos

interesar +a saber para qué rango de los parámetros que determinan el problema sigue

siendo válida la solución encontrada.

Otro aspecto interesante es el tema de dualidad. Dualidad resulta de buscar relaciones

que permitan obtener información adicional de un problema de optimización general.

Esto, traducido a PL nos conduce a relaciones primal-dual. Además veremos algunos

teoremas +útiles de dualidad y el concepto de precio sombra

HISTORIA

Nace como una aportación más del matemático Von Neumann, el primero en destacar

la existencia de la dualidad en la programación lineal y a partir de allí el concepto sigue

usando hasta ahora en nuestros tiempos en una infinidad de problemas.

Se dice que Todo problema de Programación Lineal tiene asociado un segundo

problema, conocido como su problema Dual. Los dos juntos son llamados problemas

duales ya que ambos están formados por el mismo conjunto de datos. La solución

básica factible óptima de estos problemas es tal que una puede fácilmente ser usada

para la solución de la otra tenemos que si el problema original es de maximización, su

dual será de minimización y viceversa. Para la resolución de dualidad se tiene lo

siguiente:

Los coeficientes de la función objetivo del primo se convierten en las

restricciones constantes de las ecuaciones del dual.

Las restricciones de las ecuaciones de la ecuación original se convierten en los

coeficientes de la función objetivo del dual.

Los coeficientes de las variables del dual en las ecuaciones restrictivas son

obtenidas sacando la transpuesta de la matriz de coeficientes del primo ( los

arreglos de los coeficiente en las columnas del problema original se convierten

en los coeficientes de las filas en el dual y viceversa ).

Los signos de la desigualdad son invertidos.

Las Xn variables del primo son remplazadas por Wm variables en el dual.

ACERCA DE DUALIDAD

Todo problema de optimización (primal), tiene un problema asociado (dual) con

numerosas propiedades que los relacionan y nos permiten hacer un mejor análisis de

los problemas. A continuación se describen los resultados que se ocuparan en la

resolución de los problemas.

Construcción del problema dual

Bastante en general, para encontrar el dual de un problema lineal:

1. Si es problema de minimización el dual ser +a de maximización y viceversa.

2. En el dual habrá tantas variables como restricciones en el primal.

3. En el dual habrá tantas restricciones como variables en el primal.

4. Los coeficientes de la función objetivo del dual vendrán dados por los coeficientes

del lado derecho de las restricciones del primal.

5. Los coeficientes del lado derecho del dual vendrán dados por los coeficientes de la

función objetivo del primal.

6. Los coeficientes que acompañaran a las variables en una restricción del dual

corresponderán a aquellos coeficientes que acompañan a la variable primal.

correspondiente a la restricción dual.

7. Para saber si las restricciones duales son de ≤, = +o ≥, se recurre a la tabla de

relaciones primal-dual.

8. Para saber si las variables duales son ≤ 0, = 0 +o ≥ 0, se recurre a tabla de relaciones

primal dual.

RELACIONES PRIMAL-DUAL

Estas relaciones nos permiten pasar de un problema de primal a su dual en forma

bastante algorítmica, tanto para problemas de minimización como de maximización

.

ACERCA DE LOS PRECIOS SOMBRA

Los valores de las variables duales en el optimo tienen una interpretación económica

interesante en problemas de programación lineal: Corresponde a las tasas marginales

de variación del valor de la función objetivo ante variaciones unitarias del lado derecho

de una restricción.

Por este motivo se le llama precio sombra al vector de variables duales en el +optimo.

ACERCA DE SENSIBILIDAD

Como ya se dijo, nos interesa ver como se ve afectada la solución de un problema de

optimización si cambia alguno de los parámetros del problema. En este + ámbito,

podemos distinguir 2 tipos de análisis:

Análisis de sensibilidad: Consiste en determinar cuál es el rango de variación de

los parámetros del problema de modo que la base + optima encontrada siga

siendo +optima.

Análisis post optimal: Consiste en determinar como varía la base + optima si

cambia alguno de los parámetros del problema.

PÁGINAS DE INTERNET

http://antiguo.itson.mx/dii/elagarda/apagina2001/PM/dualidad.html#inicio

http://www.contrib.andrew.cmu.edu/~mgoic/files/documents/optimization/dualidad.pdf

http://www.sites.upiicsa.ipn.mx/polilibros/portal/Polilibros/P_terminados/InvOperac-1-

Virginia/InvOperac/UMD/Unidad%205/Contenido/dualidadyanalisisdesensibi.htm