5
$\begingroup$

I want to solve a linear programming minimax problem here mathematically without using software:

$$\begin{align*} \text{min}\ \text{max} \quad & \{x_1,x_2,x_3\} \\ \text{s.t.} \quad & x_1 + x_2 + x_3 = 15 \end{align*}$$

Or it can be written

$$\begin{align*} \text{min} \quad & Z \\ \text{s.t.} \quad & x_1 + x_2 + x_3 = 15 \\ & Z \ge x_1 \\ & Z \ge x_2 \\ & Z \ge x_3 \\ \end{align*}$$

I was wondering if someone could help me or provide me with good lecture notes having an explanation with examples? Thanks in advance.

Edited: The above problem seems solvable by inspection method, but if we consider the following problem we can't get the optimal solution by inspection (optimal solution I have obtained using the software is $x_1=0$, $x_2=0.39216$, $x_3=0.29412$, $x_4=0.31373$ and $z=-1.1765$, but I don't know how to solve it manually/mathematically, as well): $$\begin{align*} \text{min} \quad & Z \\ \text{s.t.} \quad & x_1 + x_2 + x_3+x_4 = 1 \\ & Z \ge x_1-3x_2 \\ & Z \ge x_1-4x_3 \\ & Z \ge x_1-7x_4 \\ & Z \ge x_2-5x_4 \\ & Z \ge x_3-5x_4 \\ & x_1,x_2,x_3,x_4\ge 0 \\ \end{align*}$$

$\endgroup$
  • $\begingroup$ Welcome to OR.SE! I've edited your question to use MathJax instead of code blocks, which is our preferred style. $\endgroup$ – LarrySnyder610 Feb 4 at 14:26
  • $\begingroup$ Please check your second formulation. I get a different optimal solution $x=(0,20,15,16)/51$, with $z=-20/17$. $\endgroup$ – RobPratt Feb 4 at 18:11
  • $\begingroup$ @RobPratt Yes, you are right. Edited. Thanks. But do you know how to solve it mathematically without software please? $\endgroup$ – user123 Feb 4 at 19:01
7
$\begingroup$

Although this is a linear programming problem, it can really be solved by inspection. Think about how you'd solve the problem if there were only two variables, i.e.:

$$\begin{align*} \text{min}\ \text{max} \quad & \{x_1,x_2\} \\ \text{s.t.} \quad & x_1 + x_2 = 15 \end{align*}$$

Now can you extend your approach to handle 3 variables?

| improve this answer | |
$\endgroup$
  • $\begingroup$ Does it mean for every minmax problem, the inspection method works fine? $\endgroup$ – user123 Feb 4 at 16:21
  • 1
    $\begingroup$ No, definitely not! Only that this is a very simple one. $\endgroup$ – LarrySnyder610 Feb 4 at 16:59
  • $\begingroup$ Related: or.stackexchange.com/q/143/38 $\endgroup$ – LarrySnyder610 Feb 4 at 17:00
3
$\begingroup$

The optimal solution is 15/3 for the three variables. Any other assignment is such that at least one of the variables takes a value larger than 15/3.

| improve this answer | |
$\endgroup$
2
$\begingroup$

For a proof that the solution $x=(5,5,5)$ is optimal, use a dual multiplier $1/3$ for each constraint: \begin{align} \frac{1}{3}(x_1 + x_2 + x_3) &= \frac{1}{3}\cdot 15 \\ \frac{1}{3}Z &\ge \frac{1}{3}x_1 \\ \frac{1}{3}Z &\ge \frac{1}{3}x_2 \\ \frac{1}{3}Z &\ge \frac{1}{3}x_3 \\ \end{align} Adding these up yields $Z \ge 5$.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.