programación lineal - bombones - primal maximizante - tableaux secuenciales programación lineal - bombones - primal maximizante - tableaux secuenciales
Desarrollo - En este artículo transcribimos del Storm los siguientes datos (bombonp.dat)...
@LP : caja de bombones- primal maximizante 3 2 NO MAX VAR 1 VAR 2 VAR 3 CONST TYPE R H S RANGE OBJ COEFF 35 320 -65 XXXX XXXX XXXX CONSTR 1 1 16 -2 = 0.2 . CONSTR 2 1 8 -1 = 0.1 . VARBL TYPE POS POS POS XXXX XXXX XXXX LOWR BOUND . . . XXXX XXXX XXXX UPPR BOUND . . . XXXX XXXX XXXX INIT SOLN 0 0 0 XXXX XXXX XXXX
+------------ STORM EDITOR : Linear & Integer Programming Module ã------------+ ¦ Title : caja de bombones- primal maximizante ¦ ¦ Number of variables : 3 ¦ ¦ Number of constraints : 2 ¦ ¦ Starting solution given : NO ¦ ¦ Objective type (MAX/MIN) : MAX ¦ ¦------------------------------------------------------------------------------¦ ¦ R1 : C1 VAR 1 VAR 2 VAR 3 CONST TYPE R H S RANGE ¦ ¦ OBJ COEFF 35. 320. -65. XXXX XXXX XXXX ¦ ¦ CONSTR 1 1. 16. -2. = 0.2 . ¦ ¦ CONSTR 2 1. 8. -1. = 0.1 . ¦ ¦ VARBL TYPE POS POS POS XXXX XXXX XXXX ¦ ¦ LOWR BOUND . . . XXXX XXXX XXXX ¦ ¦ UPPR BOUND . . . XXXX XXXX XXXX ¦ ¦ INIT SOLN 0. 0. 0. XXXX XXXX XXXX ¦ NOTA: Si por equivocación se pone la fila VARBL TYPE con las tres entradas POS, POS y NEG, ya no coincidirá la función objetivo del primal con la del dual.
ITERACION 0 TABLEAU REPORT --------- Basis Information -------- Constraint Variable Cost Value CONSTR 1 ARTIF 1 1.0000 0.2000 CONSTR 2 ARTIF 2 1.0000 0.1000
TABLEAU REPORT VAR 1 VAR 2 VAR 3 ARTIF 1 Cost 0.0000 0.0000 0.0000 1.0000 ---------------------------------------------------- ARTIF 1 1.0000 16.0000 -2.0000 1.0000 ARTIF 2 1.0000 8.0000 -1.0000 0.0000 ---------------------------------------------------- Red. cost 2.0000 24.0000 -3.0000 0.0000 ARTIF 2 Cost 1.0000 ------------- ARTIF 1 0.0000 ARTIF 2 1.0000 ------------- Red. cost 0.0000
ITERACION 1 TABLEAU REPORT --------- Basis Information -------- Constraint Variable Cost Value CONSTR 1 ARTIF 1 1.0000 0.1000 CONSTR 2 VAR 1 0.0000 0.1000
TABLEAU REPORT VAR 1 VAR 2 VAR 3 ARTIF 1 Cost 0.0000 0.0000 0.0000 1.0000 ---------------------------------------------------- ARTIF 1 0.0000 8.0000 -1.0000 1.0000 VAR 1 1.0000 8.0000 -1.0000 0.0000 ---------------------------------------------------- Red. cost 0.0000 8.0000 -1.0000 0.0000 ARTIF 2 Cost 1.0000 ------------- ARTIF 1 -1.0000 VAR 1 1.0000 ------------- Red. cost 0.0000
ITERACION 2 (ÚLTIMA) TABLEAU REPORT --------- Basis Information -------- Constraint Variable Cost Value CONSTR 1 VAR 2 320.0000 0.0125 CONSTR 2 VAR 1 35.0000 0.0000
TABLEAU REPORT VAR 1 VAR 2 VAR 3 Cost 35.0000 320.0000 -65.0000 --------------------------------------- VAR 2 0.0000 1.0000 -0.1250 VAR 1 1.0000 0.0000 0.0000 --------------------------------------- Red. cost 0.0000 0.0000 -25.0000
OPTIMAL SOLUTION - DETAILED REPORT Variable Value Cost Red. cost Status 1 VAR 1 0.0000 35.0000 0.0000 Basic 2 VAR 2 0.0125 320.0000 0.0000 Basic 3 VAR 3 0.0000 -65.0000 -25.0000 Lower bound Objective Function Value = 4
OPTIMAL SOLUTION - DETAILED REPORT Constraint Type RHS Slack Shadow price 1 CONSTR 1 = 0.2000 0.0000 5.0000 2 CONSTR 2 = 0.1000 0.0000 30.0000 Objective Function Value = 4
Al estudiar el correspondiente dual se observa coincidencia con el valor 4 de la función objetivo. Los dos valores registrados de precios sombra (5 y 30) y el costo reducido de la variable de decisión 3 (-25), coinciden con las soluciones óptimas de las tres variables, dos de ellas de decisión y una lógica (5, 30 y 25) que entraron en la base del dual minimizante correspondiente. Hay habituales diferencias de signo cuando se usan los costos reducidos, que siempre aparecen. por haber multiplicado por -1 una de las restricciones del dual. Como es de esperar, los valores óptimos de las variables de decisión de eficencias de la caja (0 para la primera, 0,0125 para la segunda y 0 para la tercera) coincide con los tres precios sombra de las tres restricciones de la caja del dual minimizante en su óptimo.
El costo reducido recordable es el de la tercera variable de decisión, -25. El resto son nulos. El signo señala que es una ineficiencia. El signo de los costos reducidos de un primal suelen ser, en cambio, positivos.
10.may.1999
Pulsar tecla de vuelta
Glosario de Carlos von der Becke.