How to minimize two variables in a set of equations?

Question

I was working on a problem which I reduced to as follows:

• $a + 2b + 3c + 4d = 665$
• $a + b + c + d = 200$

I want to find the value of $(c+d)$ which is minimum which also satisfies the given 2 constraints.

I tried to substitute values in $1^{st}$ equation by substituting, $c=200$ but then that wont work we need to have some non-zero value of $c$ and $ d$. But I am confused as to how to arrive at the right value? Do i have to check all the values by brute-force or is there a smarter way to get about it?

Answer 1

Multiplying the first constraint by $0.5$, the second constraint by $-1$, and each of the lower bounds $a\ge 0$ and $c \ge 0$ by $0.5$ yields $c+d\ge 132.5$, hence integrality implies that 133 is a lower bound on the optimal objective value. Now $(1,66,0,133)$ satisfies the constraints and achieves that bound and is therefore optimal. The magic dual multipliers come from linear programming.