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?

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$
3
  • $\begingroup$ Welcome to OR.SE! I've edited your question to use MathJax instead of code blocks, which is our preferred style. $\endgroup$ Feb 4, 2020 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, 2020 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, 2020 at 19:01

3 Answers 3

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?

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

$\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$.

$\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.