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)
Question
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)
Solution
i) The weak duality theorem states that for any feasible solution of the primal problem and any feasible solution of the dual problem, the objective function value of the dual problem is always less than or equal to the objective function value of the primal problem.
ii) The dual of the given primal problem is:
Max Z = 3x1 + 5x2 + 7x3 Subject to x1 - 4x2 - 3x3 ≤ 10 x1 + x2 - 2x3 ≤ -15 x1, x2, x3 ≥ 0
iii) The range of optimality of y1 and y2 can be found by solving the linear programming problem. This involves finding the feasible region defined by the constraints, and then finding the maximum value of the objective function within this region. This can be done graphically or using a method such as the simplex method.
If the coefficients of y1 and y2 in the objective function change to 17 and 24 respectively, the optimal basis may change. This is because the optimal basis is determined by the coefficients of the variables in the objective function. If these coefficients change, the relative values of the variables change, which can lead to a different set of variables being chosen as the optimal basis.
Similar Questions
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.
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.
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
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
Consider the quadratic program minx1,x2f(x1,x2)subject toCx≥dmin𝑥1,𝑥2𝑓(𝑥1,𝑥2)subject to𝐶𝑥≥𝑑where C𝐶 is a 5×25×2 matrix and d𝑑 is a length 5 vector. (c) How many variables does the dual quadratic program have? Answer 4 Question 1(d) What is the value of the dual quadratic program at the point y=0𝑦=0?
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.