The following LLP \(\text{Maximize } z=100x_1 +2x_2+5x_3\) Subject to…
2018
The following LLP
\(\text{Maximize } z=100x_1 +2x_2+5x_3\)
Subject to
\(14x_1+x_2-6x_33+3x_4=7 \\ 32x_1+x_2-12x_3 \leq 10 \\ 3x_1-x_2-x_3 \leq 0 \\ \ \ \ \ \ \ \ \ \ \ \ \ \ x_1, x_2, x_3, x_4 \geq 0\)
has
- A.
Solution :
\(x_1=100, \: x_2=0, \: x_3=0\) - B.
Unbounded solution
- C.
No solution
- D.
Solution :
\(x_1=50, \: x_2=70, \: x_3=60\)
Attempted by 5 students.
Show answer & explanation
Correct answer: B
Conclusion: the linear program is unbounded.
From the equality constraint express x2 in terms of the other variables: x2 = 7 - 14 x1 + 6 x3 - 3 x4.
Substitute this into the objective: z = 100 x1 + 2 x2 + 5 x3 = 72 x1 + 17 x3 - 6 x4 + 14.
Substitute x2 into the second inequality to obtain: 6 x1 - 2 x3 - x4 <= 1.
Construct a feasible ray that increases the objective: set x4 = 0, let x3 = t >= 0, and choose x1 = (1 + 2 t)/6. Then x2 = 7 - 14 x1 + 6 x3 = 14/3 + (4/3) t >= 0, so all constraints are satisfied for t >= 0.
Along this ray the objective is z = 72 x1 + 17 x3 - 6 x4 + 14 = 41 t + 26, which grows without bound as t -> infinity. Hence the linear program is unbounded.