Solutions 2
MSc Business Analytics 2021/22
Optimisation and Decision Models
Wolfram Wiesemann
Solutions 2
Solution to (1) (a): Using the decision variables suggested in the question, we obtain the following
linear program:
minimise 17 * (AO + AT + AH + AD) + 3AO + 2AT + 5AH + 7AD +
20 * (BO + BT + BH + BD) + 6BO + 4BT + 8BH + 3BD +
24 * (CO + CT + CH + CD) + 9CO + 1CT + 5CH + 4CD
subject to AO + AT + AH + AD ≤ 800
BO + BT + BH + BD ≤ 700
CO + CT + CH + CD ≤ 700
AO + BO + CO = 300
AT + BT + CT = 500
AH + BH + CH = 400
AD + BD + CD = 600
AO, AT, AH, AD, BO, BT, BH, BD, CO, CT, CH, CD ≥ 0
Solution to (1) (b): The AMPL file could look as follows:
var AO >= 0;
var AT >= 0;
var AH >= 0;
var AD >= 0;
var BO >= 0;
var BT >= 0;
var BH >= 0;
var BD >= 0;
var CO >= 0;
var CT >= 0;
var CH >= 0;
var CD >= 0;
minimize obj: 17 * (AO + AT + AH + AD) + 3 * AO + 2 * AT + 5 * AH + 7 * AD +
20 * (BO + BT + BH + BD) + 6 * BO + 4 * BT + 8 * BH + 3 * BD +
24 * (CO + CT + CH + CD) + 9 * CO + 1 * CT + 5 * CH + 4 * CD;
subject to Cap_A: AO + AT + AH + AD <= 800; subject to Cap_B: BO + BT + BH + BD <= 700; subject to Cap_C: CO + CT + CH + CD <= 700; subject to Demand_O: AO + BO + CO = 300; subject to Demand_T: AT + BT + CT = 500; subject to Demand_H: AH + BH + CH = 400; subject to Demand_D: AD + BD + CD = 600; The optimal objective is 40,400, and the transshipment plan is as follows: display AO, AT, AH, AD; AO = 300 AT = 100 AH = 400 AD = 0 display BO, BT, BH, BD; BO = 0 BT = 100 BH = 0 BD = 600 display CO, CT, CH, CD; CO = 0 CT = 300 CH = 0 CD = 0 Apart from the optimal production and transhipment plan itself, here are some possible conclusions that can be drawn from this information: In the optimal solution, Birmingham only serves two customers and Cardiff only serves one customer; this may enable us to generate further process efficiencies. In the optimal solution, the Cardiff factory only operates at ~43% of its capacity; one may therefore consider scaling down the operations (at least temporarily) at this plant (e.g., in terms of the actively used machines, as well as temporary staff). Increasing the capacity of the Aberdeen factory (Cap_A has a shadow price of -6) would be six times as beneficial (in terms of cost savings) as increasing the capacity of the Birmingham factory (Cap_B has a shadow price of -1); this should be considered in future capacity expansion plans. Based on the shadow prices of the customer demand constraints for the optimal solution, one could consider charging customer-specific prices (e.g., it is more expensive to serve Hilton Appliances than the other customers) — this may have an impact on the customer demands, however, and thus needs to be evaluated carefully. Also, we would need to check the valid ranges for the shadow prices first! Solution to (2) (a): We bring the problem into the standard form of the dual problem. To this end, we first replace the equality with two inequalties and subsequently transform all inequalities into greater-or-equal-to inequalities: minimise 3 x1 + 5 x2 - x3 subject to x1 + x3 ≥ 4 -x1 - x3 ≥ -4 -x2 + 2 x3 ≥ -2 x1, x2 ≥ 0, x3 unrestricted We now replace the unrestricted variable with the difference of two nonnegative ones: minimise 3 x1 + 5 x2 - x3+ + x3- subject to x1 + x3+ - x3- ≥ 4 [y1] -x1 - x3+ + x3- ≥ -4 [y2] -x2 + 2 x3+ - 2 x3- ≥ -2 [y3] x1, x2, x3+, x3- ≥ 0 We can now use the definition of the primal-dual pair to obtain: maximise 4 y1 - 4 y2 - 2 y3 subject to y1 - y2 ≤ 3 -y3 ≤ 5 y1 - y2 + 2 y3 ≤ -1 -y1 + y2 - 2 y3 ≤ 1 y1, y2, y3 ≥ 0 Note that this problem can be further simplified to (not necessary, though): maximise 4 y1 - 4 y2 - 2 y3 subject to y1 - y2 ≤ 3 -y3 ≤ 5 y1 - y2 + 2 y3 = -1 y1, y2, y3 ≥ 0 and maximise 4 y1 - 2 y3 subject to y1 ≤ 3 -y3 ≤ 5 y1 + 2 y3 = -1 y1 unrestricted, y3 ≥ 0 Solution to (2) (b): We create two variables y1 and y2 for the two constraints, as well as three constraints corresponding to the three variables of the primal: ??? 4 y1 + 2 y2 subject to y1 ??? 1 y1 ??? 0 y2 ??? -1 y1, y2 need to satisfy ??? We can now fill in the rest of the details, given that the primal is a maximisation problem: minimise 4 y1 + 2 y2 subject to y1 ≤ 1 [bizarre] y1 ≤ 0 [bizarre] y2 = -1 [odd] y1 unrestricted [odd] y2 ≥ 0 [sensible] Note: We can see that the dual problem is infeasible (due to the restrictions placed on y2) — hence the primal must be unbounded or infeasible. Indeed, one readily checks that the primal problem is infeasible as well (since there are no nonpositive x1 and x2 that add up to 4), so this is an example of a primal-dual pair where both problems are infeasible.