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.
Question
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.
Solution
The dual of a linear programming problem is derived by switching the roles of the objective function coefficients and the right-hand side constants, switching the signs of the inequalities, and transposing the constraint matrix.
However, the problem you've given is not in standard form. The standard form of a linear programming problem is:
Maximize c^T x subject to Ax ≤ b and x ≥ 0
In your problem, the first constraint is a 'greater than' inequality, and the second constraint is an equality. Also, x1 is less than or equal to 0, x2 is greater than or equal to 0, and x3 is unrestricted.
To convert this problem to standard form, we need to make some changes:
- Multiply the first constraint by -1 to change the direction of the inequality: -x1 + 6x2 - x3 ≤ -25
- Split the unrestricted variable x3 into the difference of two non-negative variables, x3' and x3'', where x3 = x3' - x3''.
- Change the sign of x1 since it is less than or equal to 0. Let's denote the new variable as x1' where x1' = -x1 and x1' ≥ 0.
So, the problem in standard form is:
Maximize -8x1' + 3x2 - 2(x3' - x3'') subject to -x1' + 6x2 - x3' + x3'' ≤ -25 and -x1' - 7x2 + 2x3' - 2x3'' ≤ 4 and x1', x2, x3', x3'' ≥ 0
Now, we can write the dual of this problem:
Minimize -25y1 + 4y2 subject to -y1 - y2 ≥ -8 and 6y1 - 7y2 ≥ 3 and -y1 + 2y2 ≤ 2 and y1 - 2y2 ≤ 2 and y1, y2 ≥ 0
This is the dual of the given linear programming problem.
Similar Questions
Convert the following LP into its dual form:min 3x1 − x2 + x3s.t.x1 − 2x2 − x3 ≤ 42x1 − x2 + x3 = 8x1 − x2 ≤ 6x1 ≥ 0; x2, x3 free
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.
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)
Consider the quadratic program of the form min 𝑥 1 , 𝑥 2 ( 𝑥 1 − 1 ) 2 + ( 𝑥 2 − 1 ) 2 subject to 𝑥 1 ≥ 0 , 𝑥 2 ≥ 0 , 𝑥 1 + 𝑥 2 ≤ 1 min x 1 ,x 2 (x 1 −1) 2 +(x 2 −1) 2 subject tox 1 ≥0,x 2 ≥0,x 1 +x 2 ≤1 The optimal solution of the quadratic program is ( 1 / 2 , 1 / 2 ) (1/2,1/2). If 𝑦 ∗ y ∗ is the optimal dual solution, how many entries of the vector 𝑦 ∗ y ∗ are non-zero? (Hint: draw a picture of the level sets of the objective function and of the feasible region.) 0 1 2 3 4
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.
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.