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
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 can be stated as follows:
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:
Step 1: Set up the initial simplex tableau. The tableau for this problem is:
| y1 | y2 | RHS | |
|---|---|---|---|
| x1 | -40 | -4 | -1 |
| x2 | -30 | -10 | -1 |
| x3 | -20 | -4 | -1 |
| z | 10 | 15 | 0 |
Step 2: Identify the pivot column. The pivot column is the one with the most negative number in the bottom row. In this case, it's the y1 column.
Step 3: Identify the pivot row. The pivot row is the one with the smallest non-negative ratio of the RHS to the pivot column. In this case, it's the x2 row.
Step 4: Perform row operations to make the pivot element 1 and all other elements in the pivot column 0. The new tableau is:
| y1 | y2 | RHS | |
|---|---|---|---|
| x1 | 0 | 2 | 1 |
| y1 | 1 | 1/3 | 1/30 |
| x3 | 0 | -2/3 | -1/3 |
| z | 0 | 35/3 | 1/3 |
Step 5: Repeat steps 2-4 until there are no more negative numbers in the bottom row. The final tableau is:
| y1 | y2 | RHS | |
|---|---|---|---|
| y2 | 0 | 1 | 1/2 |
| y1 | 1 | 0 | 1/5 |
| x3 | 0 | 0 | -1/6 |
| z | 0 | 0 | 7/6 |
So the optimal solution to the dual problem is y1 = 1/5, y2 = 1/2, and w = 7/6.
Similar Questions
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
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.
Maximize Z- 3x1 + 2x2 subject to constraints 2 x1 + x2 18 2x1+3x2=42 3 x1 + x2 ≥ 20 i. Prepare initial simplex table for the above LPP. ii. Also find entering vector and departing vector from this table.
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
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)
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.