1

are following statements correct:

1) when solving an LP problem with the graphical method and the acceptable range is bounded. Then there is always a unique solution. in addition, the unique solution finds himself in a corner point of the acceptable range

Following statement:

2) As a pure ILP with 50 decision variables and with a restricted acceptable range have only a finite number of solutions, it is a good idea to go over all solutions in order to find the optimal solution

1) & 2) are wrong but can't explain why.

8bitboy
  • 15

1 Answers1

2

Ad 1)

The solution can be also on a line between two corners (inclusive).

For example you have the following LP problem:

$\texttt{max} \ \ z=4.8x+6.4y$

$0.6x+0.8y\leq 480$

$0.4x+0.2y\leq 220$

$x,y \geq 0$

You can solve the objective function and the first constraint for y.

$y=\frac{z}{6.4}-\color{blue}{\frac{3}{4}}x$

$y\leq 600-\color{blue}{\frac{3}{4}}x$

You see that both have the same slope. This is one necessary condition to have a multiple solution. This can be shown graphically. The grey area represents the permissible region. The green and the red line are the constaints. The blue lines represents the objective function, which is shifted towards the limit of the permissible region. At the end of this process there is a match of the red line and the blue line. The solution is between $(0/600)$ and $(400/300)$. enter image description here

Ad 2)

If you have no idea of linear programming, then it would be a good idea to go over all solutions in order to find the optimal solution. But there a more efficient algorithms, i.e. branch and bound. Here you solve first the LP-problem. Then you search a integer solution which is close as possible to the solution of the LP-problem.

callculus42
  • 30,550