Programación lineal: ¿significados variables dobles simples?

Question

Acabo de aprender el método símplex para resolver programas lineales, y estoy tratando de entender qué representa el problema dual.

Entiendo la mecánica de resolver un problema dual: no necesito ayuda con eso. Lo que no puedo obtener (incluso después de leer sobre él en Wikipedia) es los significados reales de las variables y en el dual.

me gustaría dar un ejemplo todos juntos con significados variables en el problema primal, y lo que me di cuenta de la doble, y pediría a nadie tan amable de explicar los significados en el doble:

Primal:

max z = 3*x1 + 5*x2 

subject to: 
      x1   <= 4 
       2*x2 <= 12 
     3*x1 + 2*x2 <= 18 

     x1, x2 >= 0 

En el problema primal, x1 y x2 son cantidades de productos a y B a producir. y son sus precios de venta unitarios, respectivamente. Los productos se producen en 3 máquinas, M1-M3. Para producir un primer producto, se necesita una hora de trabajo en M1 y 3 horas en M3. Para producir el segundo, se necesitan dos horas de trabajo en M2 y M3. Las máquinas M1, M2, M3 pueden funcionar para un máximo de 4, 12 y horas, respectivamente. Finalmente, no puedo producir una cantidad negativa de ninguno de los productos.

Ahora, me puse el doble problema:

min z = 4*y1 + 12*y2 + 18*y3 

subject to: 
      y1   + 3*y3 >= 3 
        y2 + 2*y3 >= 5 

      y1, y2, y3 >= 0 

Ahora, la única cosa que creo que puedo entender es que las restricciones significan: - por una hora de trabajo sobre M1 y 3 horas en M3, que debería conseguir pagado al menos 3 unidades de dinero - de dos horas de trabajo en M2 y 2 horas en M3, que debería conseguir pagado al menos 5 unidades monetarias

Pero, no puedo entender los significados de y1 y y2 variables. Cuando finalmente hago la minimización, el resultado en z es el mismo en el primal (aunque el primordial en el aumento del límite inferior del resultado mientras el dual está disminuyendo el límite superior), pero ¿cuál es la función objetiva del dual? problema consiste en?

Answer 1

La función Objetivo de su Dual es minimizar el Costo/Hora de las 3 máquinas (recursos).

Por lo tanto, la función objetivo del dual (4*y1 + 12*y2+ 18*y3) puede leerse como:

Minimize 4*(cost/hour of Machine1) + 12*(cost/hour of M2) + 18*(cost/hr of M3) 

Desde el Primal ocupado de maximizar los beneficios de la producción, la doble puede ser pensado como minimizar la producción costos para la empresa.

(a veces ayuda a pensar en la empresa "alquilar" las máquinas M1, M2 y M3.) Si van a alquilarlo, lo que es lo máximo que se debe prestar [$/hora] para cada máquina y todavía fabricar x1 y x2 de forma rentable?

El significado de sus variables duales y1, y2, and y3 son los costos por hora de propiedad/alquiler.

Las variables de doble problema y a menudo se conocen como "precios sombra" de los recursos.

Ya que están en busca de penetración en los duales comprensión:

1. Un truco es reducir la dimensión de la doble. (Imagine que solo había una Máquina M1). Ahora, formule la dual y trate de comprender la función objetivo y las restricciones.
2. Ayuda a pensar en términos de "costos de oportunidad". Si la empresa manufacturera tuviera que alquilar máquinas (recursos), ¿qué precio/hora debería pagar? Alternativamente, si hubiera muchos otros productos (rentables), a qué costo/hora se asignarán las máquinas a X1 y X2 en lugar de fabricar estos otros productos.
3. Tenga en cuenta que no todos los duales se pueden "entender" fácilmente. Sin embargo, puede tener una idea de muchas restricciones duales al observar la variable correspondiente en el primal. De manera similar, puede obtener ideas sobre una variable dual mediante el estudio de la restricción primaria correspondiente.