jueves, 11 de julio de 2013
INTRODUCCION
Todo problema de programación lineal tiene asociado con él otro problema
de programación lineal llamado DUAL. El problema inicial es llamado PRIMO y el
problema asociado (sombra) es llamado el problema PRIMO. 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. La dimensión del problema de
programación lineal influencia la elección del cálculo del primo o del dual.
Si el primo tiene mas ecuaciones que variables, es frecuentemente
mas fácil obtener la solución del dual ya que menor numero de iteraciones son
requeridas. Además si el primo tiene solución, el dual tendrá solución. Una vez
que el problema dual es formulado, el procedimiento de solución es exactamente
el mismo que para cualquier problema de programación lineal.
Interpretación de las variables duales Cada variable del 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. Es, por tanto, el precio adicional máximo que estamos
dispuestos a pagar por el incremento del recurso. Los valores de estas
variables se denominan precios sombra.
DUALIDAD EN PROGRAMACION LINEAL
El dual es un problema de PL que se obtiene
matemáticamente de un modelo primal de PL dado. Los problemas dual y primal
están relacionados a tal grado, que la solución símplex óptima de cualquiera de
los dos problemas conduce en forma automática a la solución óptima del otro.
El método
símplex además de resolver un problema de PL llegando a una solución óptima nos
ofrece más y mejores elementos para la toma de decisiones. La dualidad y el análisis de sensibilidad son
potencialidades de éste método.
En la mayoría de los procedimiento de PL, 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 símplex, sobre todo en lo que respecta a los signos de las
variables.
El concepto de dualidad indica que para cada
problema de PL 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 PL.
ü El
análisis de dualidad es una herramienta útil en la solución de problemas de
PL, 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 PL.
La forma estándar general del primal se defina
como; para maximizar o minimizar.
sujeto a;
¿Cómo convertir un problema primal a dual?
Un problema dual se formula de un problema primal
de la siguiente forma:
Si el primal es un problema de maximización su dual
será un problema de minimización y viceversa.
Los coeficientes de la función objetivo del
problema primal se convierten en los coeficientes del vector de la
disponibilidad en el problema dual.
Los coeficientes del vector de disponibilidad del
problema original se convierten en los coeficientes de la función objetivo
(vector de costo o precio) en el problema dual.
Los coeficientes de las restricciones en el
problema primal, será la matriz de los coeficientes tecnológicos en el dual.
Los signos de desigualdad del problema dual son contrarios a los del
primal.
Cada restricción en un problema corresponde a una
variable en el otro problema. Si el primal tiene m restricciones y n variables,
el dual tendrá n restricciones y m variables. Así, las variables Xn del primal
se convierte en nuevas variables Ym en el dual.
PROBLEMA PRIMAL EN FORMA CANONICA:
MAX Z= CX
Sujeto a:
AX £ b
X ³ 0
PROBLEMA DUAL EN FORMA CANONICA:
MIN Z= BY
Sujeto a:
AY ³ C
Y ³ 0
Ejemplo.
Si el problema primal es: MAX Z=
45X1 + 17X2 + 55X3
Sujeto a:
X1 +
X2 + X3
£ 200
9X1 +
8X2 + 10X3 £
5000
10X1+ 7X2 + 21 X3
£ 4000
Xj ³ 0
El problema
dual será:
MIN Z= 200Y1 + 5000Y2 + 4000Y3
Sujeto a:
Y1 + 9Y2 + 10Y3
³ 45
Y1 + 8Y2 +
7Y3 ³ 17
Y1 + 10Y2 + 21Y3 ³ 55
Yj ³ 0
FORMA DE PRESENTAR EL PROBLEMA DUAL
MIN = 2X1 -
3X2
Sujeto a:
1X1
+ 2X2
£ 12
4X1
- 2X2
³ 3
6X1
- 1X2
= 10
X1,2 ³ 0
1. Llevar el problema a su equivalente de
maximización, multiplicando la función objetivo por –1:
MAX -2X1 +
3X2
Convertir las restricciones ³ en una restricción
equivalente £ multiplicando por –1 ambos lados:
-4x1 + 2x2 £
-3
Para las restricciones de igualdad, obtener 2
restricciones de desigualdad, una de forma £ y la otra de forma ³; después
regresar al punto anterior y cambiar la restricción ³ a la forma £:
6X1 – 1X2 £ 10
6X1 – 1X2 ³ 10
6X1 –
1X2 £ 10
-6X1 + 1X2
£ -10
Así el problema primal se ha replanteado en la
forma equivalente:
MAX Z= -2X1
+ 3X2
Sujeto a:
1X1 + 2X2
£ 12
-4X1 + 2X2
£ - 3
6X1 – 1X2
£ 10
-6X1 + 1X2 £
-10
X1,2 ³ 0
Teniendo el problema primal convertido a la forma
canónica de un problema de maximización, es fácil llevarlo al problema dual:
MIN 12Y1 –
3Y2 + 10Y3
Sujeto a:
Y1–4Y2 + 6Y3’–6Y3’’ ³-2 Y’3
y Y’’3 ambas se refieren a la tercera
restricción
2Y1 + 2Y2 – 1Y3’ + 1Y3’’ ³
3 del
problema primal.
Y1, 2, 3’, 3’’ ³ 0
Dado un modelo lineal determinado, podemos definir
otro modelo lineal que nos permitirá obtener propiedades interesantes del
primero y que será su dual. La solución del modelo dual, permite
obtener interesantes resultados, relativos al análisis de sensibilidad de
los términos independientes más concretamente, para los rangos de
valores de los términos independientes para los que se mantiene la
base optima (que podemos conocer mediante el análisis de sensibilidad). La
solución del dual nos permite conocer el precio sombra de la restricción, que
será la variación de la función objetivo por unidad incrementada del termino
independiente de la restricción.
REGLAS DE OBTENCIÓN DEL DUAL
Si el modelo está escrito en la forma canónica, el
dual resulta singularmente fácil de obtener. Por ejemplo, partiendo de la forma
canónica del modelo de máximo:
Primal Dual
[MIN] z= c’.
x [MAX]
w= b’. u
A
.x ≥
b A’. u ≤
c
xj ≥
0 ui ≥ 0
Cada variable del 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. Es, por tanto, el precio adicional máximo que estamos
dispuestos a pagar por el incremento del recurso. Los valores de estas
variables se denominan precios sombra.
OBTENCIÓN DE LA SOLUCIÓN DEL DUAL
El dual de un modelo lineal es otro modelo
lineal, que puede solucionarse (después de las oportunas transformaciones, si
algunas de las variables resultantes es no negativa o no restringida en signo)
del mismo modo que el primal. Sin embargo, en general puede obtenerse la
solución del dual resolviendo el primal.
Dual simétrico y asimetrico
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 menores 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 (dual simétrico) es:
Mín G (λ) = λ b
S. A:
λ A ≥ c
λ ≥ 0
DUAL ASIMÉTRICO
Son los restantes tipos de combinaciones de
problema. Como por ejemplo:
Máx Z(x) = ct x
S. A:
A x = b
X ≥ 0
El problema dual (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* ambas
soluciones darán el mismo valor de la función objetivo.
C’. x*=b’. u*
Si uno de los dos problemas tiene optimo no
acotado, el otro no tendrá solución (la región factible será un conjunto vacío)
Si uno de los dos problemas no tiene solución, el
otro puede tener optimo no acotado o no tener tampoco solución.
RELACIONES PRIMAL-DUAL
Asociado a cada problema lineal existe otro problema de
programación lineal denominado problema dual 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 dual son 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.
tabla de condiciones de kuhn-tucker
Optimización con restricciones de desigualdad: las condiciones de
Kuhn-Tucker.
Muchos modelos en economía son, naturalmente, formulados
como problemas de optimización con restricciones dedesigualdad.
En problemas más complejos, con más de una restricción, este
enfoque no funciona bien.
Las desigualdades λ ≥ 0 y g (x *) ≤ c se
denominan condiciones de holgura complementaria, la mayoría en una de estas
condiciones es floja (es decir, no una igualdad).
Por un problema con muchas limitaciones, a continuación, como
antes se introduce un multiplicador para cada restricción y obtener la
condiciones de Kuhn-Tucker, que se define de la siguiente manera.
|
Definición
Las condiciones de Kuhn-Tucker para el problema
máximo x f
(x) en g j (x) ≤ c j para j =
1, ..., m
se
donde
L (x) = f (x) - Σ j =
1 λ mj (j g (x) - c j).
|
Estas condiciones se nombran en honor de Harold W. Kuhn,
miembro emérito del Departamento de Matemáticas de Princeton, y Albert W.
Tucker, quien formuló por primera vez y estudió las condiciones. Por
consiguiente, también son utilizados para optimizar sistemas aplicando estas
condiciones para determinar las desigualdades estableciendo restricciones
dentro de los problemas y representar su máximo tomando en cuenta n variables
permitiendo analizar el problema tomando en cuenta todos los aspectos que
intervienen dentro del mismo así como sus limitaciones. Por ejemplo tenemos un
repartidor el cual presenta limitaciones como tiempo para realizar la entrega
en el lapso estipulado por el destinatario.
Importancia del teorema de Khun-Tucker en la tarea de toma de decisiones
organizacionales.
Para la toma de decisiones el administrador debe tomar en cuenta
su metodología y forma sistematica, los pasos que proponen los matematicos para
la solución de problemas son:
Diagnostico del problema.
Investigación u obtención de información.
Desarrollo de alternativas.
Experimentación.
Análisis de restricciones.
Evaluación de alternativas.
Formulación de un plan.
Ejecución y control.
Lo importante es tomar decisiones oportunas ya que un ejecutivo no
toma decisiones por miedo o indecisión está destinado al fracaso olvidando que
no hacer nada es tomar ya una decisión: La peor.
Desde un punto de vista práctico, los problemas con restricciones
de desigualdad pueden ajustarse mejor a situaciones reales. Una restricción de
igualdad significa agotar completamente cierto recurso; en cambio, la misma
restricción en forma de desigualdad resulta más realista, debido a que indica
la disponibilidad del recurso pero no obliga agotarlo completamente.
Suscribirse a:
Entradas (Atom)