Question

Consider the following linear programming problem:

max z = x₁-x₂+3 x₃
s.t x₁+3 x₂+x₃ ≤ 2,
x₁-2 x₂+x₃=1
2x₁-x₂-x₃ ≥
x₁,≥ x₂,≤ 0, x₃ unrestricted

Use the weak duality theorem to show that z ≤1 (Hint: find a proper feasible solution to the dual problem).

Answer 1

To show that z ≤ 1 using the weak duality theorem, find a proper feasible solution to the dual problem where w = 2. By setting x₁ = 2, x₂ = -1, and x₃ = 0, we can achieve a higher objective function value of z = 3. Therefore, z ≤ 1.

Step-by-step explanation:

To show that z ≤ 1 using the weak duality theorem, we need to find a proper feasible solution to the dual problem. The dual problem is formed by taking the inequalities from the original problem and converting them into equalities. So, the dual problem for this linear programming problem is:

min w = 2y₁ + y₂

subject to:

y₁ + y₂ - y₃ = 1

y₁ + 2y₂ - y₄ = -1

y₁, y₂ ≥ 0

To find a proper feasible solution, we can set y₁ = 1 and y₂ = 0. Substituting these values into the dual problem, we get:

min w = 2(1) + 0 = 2

So, we have found a feasible solution to the dual problem where w = 2. Since the primal problem is a maximization problem, the weak duality theorem states that z ≤ w. Therefore, z ≤ 2. However, we can see that by setting x₁ = 2, x₂ = -1, and x₃ = 0, we can achieve a higher objective function value of z = 3. Therefore, we can conclude that z ≤ 1.