0
$\begingroup$

I'm currently studying linear programming and I came across this MIT resource. In the very first page of the pdf, under BT Exercise 2.10 the 6th statement reads:

  1. Consider the problem of minimizing max{c’x, d’x } over the set P. If this problem has an optimal solution, it must have an optimal solution which is an extreme point of P.

And on the next page, the solution manual author claims that the above statement is false and proceeds to provide a counter-example:

  1. False. Consider the problem of minimizing $x_1−0.5 = \max\{x_1−0.5x_3, −x_1+ 0.5x_3\}$ subject to $x_1+x_2 = 1, x_3 = 1$ and $x_1 + x_2 = 1, x_3 = 1$ and $(x_1,x_2,x_3) ≥ (0, 0, 0)$. Its unique optimal solution is $(x_1, x_2, x_3) = > (0.5, 0.5, 1)$ which is not a BFS.

This confuses me. I was under the impression that extreme points are the same as basic solutions. Is this true?

If it is true and if one of basic solutions is not the optimal solution, then what is even the point of calculating the basic solutions? What am I missing here? Any help to get out of this confusion is appreciated!

$\endgroup$
1
$\begingroup$

$(0.5,0.5,1)$ is not a BFS and it is also not an extreme point of $P$. There are only $2$ independent constraints that are active.

Notice that $$\min_{x_1,x_2,x_3} \max\{ x_1 -0.5, -x_1+0.5\}$$

subject to $$x_1+x_2=1$$ $$x_3=1$$ $$x\ge 0$$

is not a linear programming problem.

However, it can be converted to a linear programming problem.

$$\min_{x_1,x_2,x_3,z} z$$

subject to $$z \ge x_1 - 0.5$$ $$z \ge -x_1+0.5$$ $$x_1+x_2=1$$ $$x_3=1$$ $$x\ge 0$$

Notice that $4$ independent constraints are active. The BFS in the new feasible set is $(0.5,0.5,1,0)$

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