onsider the following primal problem:max z = −40x1 − 30x2 − 20x3s.t.10x1 + 3x2 + 5x3 ≤ 104x1 + 10x2 + 4x3 ≤ 15x1, x2, x3 ≥ 0 .(i) State its dual problem, and find the optimal solution of the latter using the SimplexMethod
Question
onsider the following primal problem:max z = −40x1 − 30x2 − 20x3s.t.10x1 + 3x2 + 5x3 ≤ 104x1 + 10x2 + 4x3 ≤ 15x1, x2, x3 ≥ 0 .(i) State its dual problem, and find the optimal solution of the latter using the SimplexMethod
Solution
The dual problem of the given primal problem is:
min w = 10y1 + 15y2 s.t. -40y1 - 4y2 ≥ -1 -30y1 - 10y2 ≥ -1 -20y1 - 4y2 ≥ -1 y1, y2 ≥ 0
To solve this problem using the Simplex Method, follow these steps:
- Set up the initial simplex tableau. The tableau should look like this:
| y1 | y2 | RHS | |
|---|---|---|---|
| z | -40 | -4 | -1 |
| y1 | 10 | 15 | 0 |
| y2 | -30 | -10 | -1 |
-
Identify the pivot column. In this case, the pivot column is y1 because it has the most negative coefficient in the objective function row.
-
Identify the pivot row. The pivot row is the one with the smallest non-negative ratio of the RHS to the corresponding element in the pivot column. In this case, the pivot row is y2.
-
Perform row operations to make the pivot element 1 and all other elements in the pivot column 0. The new tableau should look like this:
| y1 | y2 | RHS | |
|---|---|---|---|
| z | 0 | 2 | 0 |
| y1 | 1 | 1.5 | 0 |
| y2 | 0 | -2 | 1 |
-
Repeat steps 2-4 until there are no more negative coefficients in the objective function row. In this case, the tableau is already optimal because there are no more negative coefficients in the objective function row.
-
Read off the solution from the final tableau. The optimal solution is y1 = 0, y2 = 1, with an optimal value of w = 0.
Similar Questions
max z = −40x1 − 30x2 − 20x3s.t.10x1 + 3x2 + 5x3 ≤ 104x1 + 10x2 + 4x3 ≤ 15x1, x2, x3 ≥ 0 .(i) State its dual problem, and find the optimal solution of the latter using the SimplexMethod.
For a primal-dual pair of linear programs (where the primal is a minimisation problem and the dual is a maximisation problem), you are told that the optimal value of the dual linear program is 22. Which of the following statements is true?Question 1Answera.The primal linear program is infeasible.b.Any feasible point of the dual linear program has value at least 22.c.The primal linear program is unbounded.d.Any feasible point of the primal linear program has objective value of at least 22.
state the weak duality theorem (1 mark)ii) Write the dual of the given primal problem.Min W=10y1 − 15y2Subject toy1 − 4y2 ≥ 3y1 + y2 ≥ 53y1 − 2y2 = 7y1, y2 ≥ 0 (2 marks)iii) Given the linear programming problemMax z = 15y1 + 25y2Subject toy1 + y2 ≤ 450y2 ≤ 3504y1 + 5y2 ≤ 2000y1 ≤ 350y1, y2 ≥ 0Find the range of optimality of y1, y2. (3 marks)Will the optimal basis change when the objective function coefficient of y1, y2change to 17 and 24 respectively? (2 marks)
Write the dual of the following linear programming problem:Maximize 8x1 + 3x2 − 2x3subject to x1 − 6x2 + x3 > 25x1 + 7x2 − 2x3 = −4x1 ≤ 0, x2 ≥ 0, x3 unrestricted.
Solve the following LP by using the dual simplex method:min 3x1 + 2x2 + 10s.t.3x1 + x2 ≥ 3,4x1 + 3x2 ≥ 6,x1 ≥ 1,x2 free.2
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.