CvdB

programas primal y dual

Definición: "Programa Primal" suele ser el programa matemático original, ya sea el de buscar máxima eficiencia con una restricción de costos (que no pueden superar cierto valor dintel o cota superior o máxima) o bien buscar mínimos costos con una restricción de eficiencias que no pueden caer por debajo de un valor umbral (cota inferior o mínima). Para este estudio establecemos que todo problema maximizante sea denominado primal y todo problema minimizante sea denominado el dual del anterior. En general se puede indicar que todo problema primal tiene su dual y viceversa. A veces se requiere cierta perspicacia para conseguir que ambos coincidan en una única respuesta común a ambos planteos aparentemente distintos, pero que usan los mismos datos.

En el problema de los bombones y en el de la planta con tres talleres y dos productos, ambos están estudiados tanto bajo la forma de un primal como bajo la forma del dual. Se puede probar que ubicando los datos en una matriz adecuada, un tipo de problema es la traspuesta de la matriz del otro problema.

Supongamos entonces que el dual es Min{F(y): y in Y}. Entonces, F(y) >= f(x) para cualquier x factible en el primal y todo y en Y. Esto de inmediato se interpreta como que si el primal es factible, el dual no puede exhibir la patología de ser si límites. Viceversa, si el dual es factible, el primal estará acotado y no sin límites. Como corolario, si el dual no tiene límites, el primal deja de ser factible (y viceversa). Los coeficientes de uno son los RHS del otro, y viceversa. El precio sombra de uno es el costo reducido del otro, y viceversa.

En general la interpretación de la información de salida de un ejemplo de programación lineal es el resultado de la práctica.

5.may.1999

Pulsar tecla de vuelta

Vuelta a Portada


Glosario de Carlos von der Becke.

1