- A cargo plane has three compartments for storing cargo: front, centre and rear. These compartments have limits on both weight(tonnes) and space(cubic metres). Furthermore, the weight of the cargo in the respective compartments must be the same proportion of that compartment’s weight capacity to maintain the balance of the plane. In the following tables are shown the capacities and four cargoes are available for shipment on the next flight. Any proportion of these cargoes can be accepted.
The objective is to determine how much (if any) of each cargo C1, C2, C3 and C4 should be
accepted and how to distribute these among the compartments, so that the total profit for the flight is maximised.
(a) Formulate the above problem as a linear program. Use decision variables xij for the amount of cargo Ci in the compartment j(1-front, 2-centre, 3-rear)
(b) write down the dual problem
(c) Consider a feasible solution ¯x with ¯x11 = 5, ¯x13 = 4, ¯x22 = 3, ¯x42 = 5 and values of the remaining variables are zero. Use duality theory to check if the solution is optimal or not.
- To solve the problem min 2x1+5x2+x3 Subject to −x3+x4 = −5, 2x1+x2+x3 ≥ 2 and x2−2x3 ≥ 1 with xi ≥ 0 for all i an initial simplex tableau is constructed as follows:
x1 x2 x3 x4 x5 x6 b
0 0 -1 1 0 0 -5
-2 -1 -1 0 1 0 -2
0 -1 2 0 0 1 -1
2 5 1 0 0 0 0
After completing some iterations of the dual simplex method, the following tableau is produced:
x1 x2 x3 x4 x5 x6 b
0 .. . 1 -1 0 0 …
1 (ii) 0 0.50 -0.50 0 (i)
0 .. . 0 2 0 1 …
0 4 0 0 1 0 (iii)
(a) Compute (i) the right hand side b, (ii) the entries in the missing column for x2, (iii) the value for the bottom right corner.
(b) Perform two dual-simplex pivots to produce the next two tableaus. State how you have selected the variable entering and exiting the basis in each pivot.
- Consider the network for a maximum flow problem given below with arc capacities uij and initial flows xij between source node 1 and sink 6.
EasyDue™ 支持PayPal, AliPay, WechatPay, Taobao等各种付款方式!
E-mail: email@example.com 微信:easydue