# Need help with linear programming problem

The LP problem is given below:

max $$3x_1+2x_2$$ s.t.

$$x_1+x_2\leq3$$

$$2x_1+x_2-x_3\leq1$$

$$x_1+2x_2-2x_3\leq1$$.

Non-negativity constraints apply on each of the three variables.

Question statement: Formulate the problem for any fixed value of $$x_3 \in [0,\infty)$$. The maximal value of $$3x_1+2x_2$$ is a function of $$x_3$$. Find the function and maximize it.

My attempt:

The dual is:

min $$3u_1+u_2+u_3$$

s.t. $$u_1+2u_2+u_3\geq3$$

$$u_1+u_2+2u_3\geq2$$

$$-u_2-2u_3\geq0$$

From the third inequality constraint of the dual, it is clear that $$u_2=u_3=0$$. Then, from the first two constraints, we get $$u_1\geq3 \Rightarrow u_1>0$$, hence, the first constraint of the primal is met with an equality. Using the equality and the two inequality constraints of the primal problem, I get $$x_2\geq 5-x_3$$ and $$x_2 \leq 2x_3-2$$.

Further, the criterion function of the primal is $$9-x_2$$ (after eliminating $$x_1$$ using the equality constraint. Clearly, 9 is the maximal value (also confirmed by the optimal value of the dual).

After this, I can write $$11-2x_3\leq 9-x_2\leq 4-x_3\leq 9$$. But beyond this, I am stuck. How can I proceed?

I don't think taking the dual of the problem would help. I would direct attack this problem by discussing cases.

Your objective increases while all of your constraints become tighter as either $$x_1$$ or $$x_2$$ increases. Therefore, it is safe to conclude that as many as constraints are binding. However, you can have at most 2 constraints binding (if there are more they are redundant), because you only have 2 primal variables. More constraints (except for redundant) binding will give you an overdetermined linear system and lead to no solution.

Having this in mind, we discuss cases about which two constraints are binding. Label $$x_1 + x_2\leq 3\tag{1}$$ $$2x_1 + x_2\leq 1+x_3\tag{2}$$ $$x_1 + 2x_2\leq 1+2x_3\tag{3}$$ Then there are 3 cases, either (1)(2) are binding, (1)(3) are binding, or (2)(3) are binding. Note that if (3) binds, (2) must bind. The reason is that in (2), $$x_1$$ is more costly (relative price $$2/1$$) than in (3) (relative price $$1/2$$), while the total budget is tighter ($$1+x_3 < 1+2x_3$$). So we can remove the case of binding (1)(3) [of course, you can discuss this case and you will find that it is dominated by another case].

Now, Case 1: suppose (1)(2) are binding. Then you are solving a system of equations $$x_1 +x_2 = 3$$ $$2x_1 + x_2 = 1+ x_3$$ which has the solution $$x_1 = x_3-2, x_2 = 5-x_3$$ which gives the objective value $$3(x_3-2) + 2(5-x_3) = 4 + x_3$$ We need to verify that (3) holds. Plugging in $$x_1$$ and $$x_2$$, we get $$x_3-2 + 2(5-x_3) \leq 1+2x_3$$ which implies $$x_3 \geq \frac{7}{3}$$. Moreover, the primal constraint on $$x_2$$ requires $$x_3 \leq 5$$. That is, this solution exists when $$5 \geq x_3\geq \frac{7}{3}$$.

Case 2: suppose (2)(3) are binding. Then you are solving a system of equations $$2x_1 + x_2= 1+x_3$$ $$x_1 + 2x_2 = 1+2x_3$$ This gives you $$x_1 + x_2 = 2/3 + x_3$$. To satisfy (1), we need to require $$x_3 \leq 7/3$$. Indeed, the range of the solution is complementary to Case 1. The solution is $$x_1 = 1/3, x_2 = 1/3 + x_3$$ which gives you a value of $$2x_3 + \frac{5}{3}$$ In particular, when $$x_3 = 7/3$$, the solutions to Case 1 and Case 2 coincide.

To sum up, the solution to the linear programing is $$(x_1, x_2) = \begin{cases}(1/3, 1/3 + x_3), \text{ when } 0 \leq x_3 < 7/3\\(x_3-2, 5-x_3), \text{ when } 5 \geq x_3 \geq 7/3\\ (3, 0), \text{ when }x_3 \geq 5 \end{cases}$$

Alternatively, you can also draw a graph in a $$x_2-x_1$$ plane because you have a 2D problem.

• While your answer makes sense, this particular exercise comes after the complementary slackness section in the textbook, hence I am trying to solve it by taking the dual. Also, the book solution shows that $(x_3-2,5-x_3)$ is a solution with $7/3\leq x_3 \leq 5$. That doesn't match with your answer. Can you expand the answer? Commented Aug 4 at 7:24
• @AcadEconInd Sorry, I embarrassed myself by thought the first constraint to be $x_1 + x_2 \leq 1$ somehow... I have changed my answer accordingly, and the only change is to restore the first constraint to the correct one. The logic still goes through. I see the reasons that you wrote out the dual problem, but seems you only got partial solution from there (you conclude that "the first constraint of the primal is met with an equality", which is not the complete solution). One might need some rigorous cases discussion from there.
– DiZ
Commented Aug 4 at 22:40
• Thanks for updating the answer. Lastly, can you explain the second paragraph where you deduce that only 2 constraints can be binding? Is there a general result one can use to arrive at this conclusion? Commented Aug 5 at 3:55
• @AcadEconInd The intuition is what I described in the answer. There is a general way to prove it: Suppose at optimum, (3) binds while (2) is slack, for the sake of contradiction. We can increase $x_1$ by $\epsilon$, and decrease $x_2$ by $\epsilon/2$. This keeps (3) binding and (2) slack (if $\epsilon >0$ is small). However, this arrangement strictly improves the objective by $3\cdot \epsilon - 2\cdot \epsilon/2 = 2\epsilon > 0$. Note that there always exists such improvement if (3) is binding and (2) is slack. Hence, the solution can always be improved, i.e., not optimal. A contradiction.
– DiZ
Commented Aug 5 at 4:30
• The key intuition hinges on: 1. the relative contribution to the objective between $x_1$ and $x_2$ is $3/2$, so you need $x_1$ more; 2. the relative cost in (2) is $2/1$; 3. the relative cost in (3) is $1/2$; 4. constraint (2) has fewer resources than (3). Conclusion: your more need of $x_1$ is bottleneck-ed by constraint (2).
– DiZ
Commented Aug 5 at 4:37