MTH5114 Linear Programming and Game Theory, Spring 2024
Week 6 Coursework Questions
It is generally recommended (here and in the exam) that in your answers, as well as giving the tableaux, you also highlight the appropriate rows and columns and mention the row operations you are carrying out – this way, even if your final answer is incorrect, we can easily award you credit for using the right method.
1. Solve the following linear programmne using the 2-phase simplex algorithm. You should give the initial tableau and each further tableau produced during the exe-cution of the algorithm. If the program has an optimal solution, give this solution and state its objective value. If it does not have an optimal solution, say why.
maximize x1 − 2x2 + x3 − 4x4
subject to 2x1 + x2 − 2x3 − x4 ≥ 1,
5x1 + x2 − x3 − x4 ≤ −1,
2x1 + x2 − x3 − 3x4 ≥ 2,
x1, x2, x3, x4 ≥ 0.
2. Apply the first phase of the 2-phase simplex algorithm to the following linear pro-gramme giving the initial tableau and each further tableau produced. Give the starting tableau for the second phase if there is one.
maximize 2x1 + x2 + 3x3
subject to x2 − x3 ≤ 2,
x1 + 3x2 + 2x3 ≥ 3,
2x1 + 2x2 + x3 = 4,
x1, x2, x3 ≥ 0.