这是一篇英国的线性规划限时测试数学代写
Important instructions
- Start each question on a new sheet of paper.
- Number your sheets of paper to help you scan them in order.
- Only write on one side of each piece of paper.
- If you have rough work to do, simply include it within your overall answer – put brackets at the start and end of it if you want to highlight that it is rough work.
(1) For the following LP problem
maximize f =x1 + 2x2
subject to x1 +x2 ≤ 12
10x1 +x2 ≤ 30
x1 ≥ 2 x2 ≥ 0,
determine the simplest equivalent LP problem with bounds x ≥ 0 from which the solution of the LP problem above can be deduced. [10 marks]
(2) (a) Form the dual of the LP
minimize
f = 9x1 + 9x2 + 2x3
subject to 2x1 +x2≥ 1
x1 + 3x2 + x3 ≥ 6
x1 ≥ 0 x2 ≥ 0 x3 ≥ 0
(P) [10 marks]
(b) Show that the point y = 3 2 is an optimal solution of the dual problem, and hence deduce the optimal solution of (P), giving a reason for your answer. [10 marks]
(3) The simplex algorithm assumes that the basis matrix B at the start of an iteration is nonsingular. Show that this is true by assuming that it is so at the start of some iteration, and proving that B is nonsingular at the start of the next iteration (assuming that the algorithm does not terminate in that iteration). [20 marks]
(4) Prove that if the simplex algorithm starts from a basic feasible solution it terminates at either an optimal solution or by identifying the LP problem’s unboundedness.State any conditions that must hold for your proof to be valid. [20 marks]
(5) (a) Represent the following LP graphically and hence fifind its optimal solution
maximizef =x1 + 2x2
subject tox1 +x2 ≤ 12
10x1 +x2 ≤ 30
x1 ≥ 0 x2 ≥ 0 [10 marks]
(b) A researcher claims that, if a variable in a maximization LP problem has a lower bound of zero, is nonbasic at its optimal solution with reduced cost bc, and theoptimal objective value isbf, then the optimal objective valuef when the lowerbound is δ satisfifies f ≤ fb +δbc. Determine the extent to which this result is true for the LP in (a) if the lower bound onx1 is increased to δ in the casesδ = 2,δ = 3 and δ > 3. [10 marks]
(c) Subject to the condition that the LP remains feasible, prove that the result in
(b) holds for all LP problems for which the optimal solution is not degenerate.You may refer without proof to results proved in the course. [10 marks]