<p>I don't think taking the dual of the problem would help. I would direct attack this problem by discussing cases.</p>
<p>Your objective increases while all of your constraints become tighter as either <span class="math-container">$x_1$</span> or <span class="math-container">$x_2$</span> 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.</p>
<p>Having this in mind, we discuss cases about which two constraints are binding. Label
<span class="math-container">$$x_1 + x_2\leq 3\tag{1}$$</span>
<span class="math-container">$$2x_1 + x_2\leq 1+x_3\tag{2}$$</span>
<span class="math-container">$$x_1 + 2x_2\leq 1+2x_3\tag{3}$$</span>
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), <span class="math-container">$x_1$</span> is more costly (relative price <span class="math-container">$2/1$</span>) than in (3) (relative price <span class="math-container">$1/2$</span>), while the total budget is tighter (<span class="math-container">$1+x_3 &lt; 1+2x_3$</span>). 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].</p>
<p>Now, Case 1: suppose (1)(2) are binding. Then you are solving a system of equations
<span class="math-container">$$x_1 +x_2 = 3$$</span>
<span class="math-container">$$2x_1 + x_2 = 1+ x_3$$</span>
which has the solution
<span class="math-container">$$x_1 = x_3-2, x_2 = 5-x_3$$</span>
which gives the objective value
<span class="math-container">$$3(x_3-2) + 2(5-x_3) = 4 + x_3$$</span>
We need to verify that (3) holds. Plugging in <span class="math-container">$x_1$</span> and <span class="math-container">$x_2$</span>, we get
<span class="math-container">$$ x_3-2 + 2(5-x_3) \leq 1+2x_3 $$</span>
which implies <span class="math-container">$x_3 \geq \frac{7}{3}$</span>. Moreover, the primal constraint on <span class="math-container">$x_2$</span> requires <span class="math-container">$x_3 \leq 5$</span>. That is, this solution exists when <span class="math-container">$5 \geq x_3\geq \frac{7}{3}$</span>.</p>
<p>Case 2: suppose (2)(3) are binding. Then you are solving a system of equations
<span class="math-container">$$2x_1 + x_2= 1+x_3$$</span>
<span class="math-container">$$x_1 + 2x_2 = 1+2x_3$$</span>
This gives you <span class="math-container">$x_1 + x_2 = 2/3 + x_3$</span>. To satisfy (1), we need to require <span class="math-container">$x_3 \leq 7/3$</span>. Indeed, the range of the solution is complementary to Case 1. The solution is
<span class="math-container">$$x_1 = 1/3, x_2 = 1/3 + x_3$$</span>
which gives you a value of
<span class="math-container">$$2x_3 + \frac{5}{3}$$</span>
In particular, when <span class="math-container">$x_3 = 7/3$</span>, the solutions to Case 1 and Case 2 coincide.</p>
<p>To sum up, the solution to the linear programing is
<span class="math-container">$$(x_1, x_2) = \begin{cases}(1/3, 1/3 + x_3), \text{ when } 0 \leq x_3 &lt; 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}$$</span></p>
<p>Alternatively, you can also draw a graph in a <span class="math-container">$x_2-x_1$</span> plane because you have a 2D problem.</p>

CC BY-SA 4.0
2024-08-04T07:24:42.437Z
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?
AcadEconInd
CC BY-SA 4.0
2024-08-04T22:40:01.437Z
@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
CC BY-SA 4.0
2024-08-05T03:55:38.693Z
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?
AcadEconInd
CC BY-SA 4.0
2024-08-05T04:30:21.717Z
@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
CC BY-SA 4.0
2024-08-05T04:37:37.953Z
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
CC BY-SA 4.0
2024-08-01T23:00:06.343Z
2024-08-04T22:30:42.640Z
2024-08-04T22:30:42.640Z
DiZ
<p>The LP problem is given below:</p>
<p>max <span class="math-container">$3x_1+2x_2$</span> s.t.</p>
<p><span class="math-container">$x_1+x_2\leq3$</span></p>
<p><span class="math-container">$2x_1+x_2-x_3\leq1$</span></p>
<p><span class="math-container">$x_1+2x_2-2x_3\leq1$</span>.</p>
<p>Non-negativity constraints apply on each of the three variables.</p>
<p>Question statement: Formulate the problem for any fixed value of <span class="math-container">$x_3 \in [0,\infty)$</span>. The maximal value of <span class="math-container">$3x_1+2x_2$</span> is a function of <span class="math-container">$x_3$</span>. Find the function and maximize it.</p>
<p>My attempt:</p>
<p>The dual is:</p>
<p>min <span class="math-container">$3u_1+u_2+u_3$</span></p>
<p>s.t. <span class="math-container">$u_1+2u_2+u_3\geq3$</span></p>
<p><span class="math-container">$u_1+u_2+2u_3\geq2$</span></p>
<p><span class="math-container">$-u_2-2u_3\geq0$</span></p>
<p>From the third inequality constraint of the dual, it is clear that <span class="math-container">$u_2=u_3=0$</span>. Then, from the first two constraints, we get <span class="math-container">$u_1\geq3 \Rightarrow u_1&gt;0$</span>, 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 <span class="math-container">$x_2\geq 5-x_3$</span> and <span class="math-container">$x_2 \leq 2x_3-2$</span>.</p>
<p>Further, the criterion function of the primal is <span class="math-container">$9-x_2$</span> (after eliminating <span class="math-container">$x_1$</span> using the equality constraint. Clearly, 9 is the maximal value (also confirmed by the optimal value of the dual).</p>
<p>After this, I can write <span class="math-container">$11-2x_3\leq 9-x_2\leq 4-x_3\leq 9$</span>. But beyond this, I am stuck. How can I proceed?</p>

<linear-programming>
Need help with linear programming problem
AcadEconInd
# Need help with linear programming problem

(Asked by: username_0 on 2024-07-31)

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?

**Tags:** linear-programming

---

## 1 answers

### Answer by username_1 on 2024-08-01. Score: 1 | Accepted answer

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.

> **Comments:**
> **username_0**: 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?  
> **username_1**: @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.  
> **username_0**: 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?  
> **username_1**: @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.  
> **username_1**: 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).  

---

