Without using a computer, I have to solve the following integer linear programming:$$\min \quad x_1+x_2+x_3$$ $$\operatorname{sub} :\begin{cases}x_1\le9\\x_2\le7\\x_3\le5\\3x_1+6x_2+8x_3=80\\x_1,x_2,x_3\in\mathbb{N}\end{cases}$$ Is there any algebraic method to compute the solution (I can't use the simplex method)?
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ the problem was given to my son who's 11...so I can't explain this method to him. Any ideas? $\endgroup$user214188– user2141882015-02-09 16:09:33 +00:00Commented Feb 9, 2015 at 16:09
-
3$\begingroup$ @A.E In general the simplex method won't solve integer programming problems, unless one is lucky enough to get an integer-valued optimal solution in the relaxation. $\endgroup$Casteels– Casteels2015-02-09 16:14:21 +00:00Commented Feb 9, 2015 at 16:14
-
$\begingroup$ I found the solution using a computer, but what I miss is a working method which can be understood by someone who doesn't know algorithms concerning with linear programming... $\endgroup$user214188– user2141882015-02-09 16:18:59 +00:00Commented Feb 9, 2015 at 16:18
-
1$\begingroup$ You want $x_3$ to be as big as possible, and $x_1$ to be as small as possible. Use the greedy method to find $x_3, x_2,$ and $x_1$ satisfying the equations with these criteria (not necessarily integer). Now find the best integer solution. Think about the values of the variables mod 3. $\endgroup$Peter Shor– Peter Shor2015-02-09 17:21:43 +00:00Commented Feb 9, 2015 at 17:21
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
The problem is beyond the typical 11-year-old but if he is bright at math you should be able to explain how to solve it. Does he have simple algebra?
The first thing to notice is that $3x_1+6x_2$ is divisible by 3, so $80-8x_3$ must also be divisible by 3. The only two allowable $x_3$ that satisfy this are $1$ and $4$.
Say $x_3 = 1$. Then the problem becomes minimize $x1 + x_2 +1$ with $$ x_1 \leq 9 \\ x_2 \leq 7 \\ 3x_1 + 6x_2 = 72 $$ The last line of that says $x_1 = 24 - 2x_2$. But $x_2$ is at most $7$, so this means $x_1 \geq 10$ which contradicts $x_1 \leq 9$. So the choice $x_3 = 1$ doesn't allow a solution to the constraints at all.
Thus our solution will have $x_3 = 4$. Then the problem becomes minimize $x1 + x_2 + 4$ with $$ x_1 \leq 9 \\ x_2 \leq 7 \\ 3x_1 + 6x_2 = 48 $$ The last line of that says $x_1 = 16 - 2x_2$. Replace $x_1$ and the problem becomes to minimize $20-x_2$ subject to $$ 16 - 2x_2 \leq 9 \\ x_2 \leq 7 \\ 3x_1 + 6x_2 = 48 $$ The first of those equations says $$ 2x_2 \geq 7 $$ Now because $x_2$ appears in the objective with a minus sign, we want $x_2$ to be as large as possible, thus $x_2 = 7$ and $x_1 = 2$.
So the solution will be $$ x_1 = 2 \\ x_2 = 7 \\x_3 = 4 \\x_1+x_2+x_3 = 13$$
$\begingroup$
$\endgroup$
Yep, Peter Shor got the right approach. You also need to use divisibility concepts to reduce the amount of work. Start with $x_3=5$. This would mean that $3x_1+6x_2=40$. But this can't lead to a solution because the left-hand side is divisible by 3, but the right-hand side is not! So try $x_3=4$, which gives $3x_1+6x_2=48$, which is divisible by $3$. Now try the maximum value for $x_2$, which is 7 and that gives $x_1= 2$.
This may or may not be convincing enough as proof, depending how formally the greedy approach needs to justified. The intuition is that $x_3$ contributes the most to the equality constraint, $x_1$ the least, while their appearance in the objective function is equal, so one unit of $x_3$ "buys" 8/3 units of $x_1$ in the objective function.
But clearly, the only other choice for $x_3$ (divisibility-wise) is 1, and that can't be met by plugging even the maximum values in $x_1+2x_2=25$; the max you can get maxing both $x_1=5$ and $x_2=7$ is 19.
A similar greedy argument goes for maxing $x_2$ instead of $x_1$ (once $x_3 = 4$ is settled); One unit of $x_2$ buys two units of $x_1$ in the objective function. If instead of $x_1 = 2$, $x_2=7$ you satisfy $x_1+2x_2=16$ with $x_1=4, x_2=6$, the objective function increases (by 1).
Alternatively, this remainder optimization problem being in only two variables ($x_1$, $x_2$), you can solve it by graphing its polyhedron.
The fact that the greedy method can solve certain classes of I[L]Ps can be given quite a formal proof(s) of correctenss; see the paper by V.V. Shenmaier for example, although I don't dream to suggest that's going to be accessible to an 11-year old.
