2

I am trying to solve the following optimization problem using linear programming (deterministic operations research). According to the book, there are multiple optimal solutions, I don't understand why. I'll show you what I have done.

The problem is:

$max Z=500x_{1}+300x_{2}$

s.t.

$15x_{1}+5x_{2}\leq 300$

$10x_{1}+6x_{2}\leq 240$

$8x_{1}+12x_{2}\leq 450$

$x_{1},x_{2}\geqslant 0$

I have plotted the lines graphically to get:

enter image description here

The intersection points are:

$(15,15)$

$(\frac{135}{14},\frac{435}{14})$

$(\frac{5}{2},\frac{215}{6})$

The target function equals to 12000 for two of these points. If this value was the maximum, then I would say that the entire line, edge, between these intersection points is the optimal solution (multiple solutions). However, this is not the maximum. The second intersection I wrote gives a higher value, and therefore is the maximum. So I think there is a single solution.

What am I missing ?

And generally speaking, what is the mathematical justification for having multiple solutions when two points gives the maximum (or minimum)?

Community
  • 1
user2899944
  • 275

3 Answers3

2

If you solve the problem graphically you should solve the objective function $Z$ for $x_2$ as well.

$Z=500x_{1}+300x_{2}$

$Z-500x_{1}=300x_{2}$

$\frac{Z}{300}-\frac53x_1=x_2$

Now you set the level equal to zero, which means that $z=0$ and draw the line. This line goes through the origin and has a slope of $-\frac53$. Then you push the line parallel right upward till the objective function touches the last possible point(s) of the feasible solution(s). The graph below shows the process.

enter image description here

All the points on the green line for $\frac52 \leq x_1\leq 15$ are optimal solutions.

All the optimal solutions are on the the line of the second constraint. This result can be confirmed if we have a look on the coefficient of the second constraint and the objective function. The ratios of the coefficients are equal: $\frac{10}6=\frac{500}{300}$. And additionally The second constraint is fullfilled as a equality.

Conclusion: If you see that the slopes of the objective function is equal to one of the constraints then there eventually exists a solution which is a line and not a single point (2 variables).

callculus42
  • 30,550
0

The second intersection is the one of the red and blue lines. This point does not satisfy the constraint given by the green line.

The optimal solutions are given by the line segment of the green line with its intersection points as end points. This is because the constraint puts the same relative weights on $x_1,x_2$ as the objective function.

ertl
  • 619
  • Oh, that's embarrassing, how did I not see that ?!?! Can you kindly explain to me, theoretically, why if two vertices gives the same value, the entire edge is the maximum ? – user2899944 Jul 29 '18 at 07:19
  • You can show that for any linear programming problem, the optimum is achieved at a vertex. If we now have two vertices giving us an optimum, it must be the case that the LHS of its constraint is a multiple of the objective function. You should then be able to check that the value you get is the same along the constraint line, hence any feasible point (i.e. the whole line segment between the two vertices) gives an optimum! – ertl Jul 29 '18 at 07:34
0

Multiply the second constraint by $50$ to get: $$500x_1+300x_2\le 12000.$$ The value of $Z=500x_1+300x_2$ is $12000$ on every point $(x_1,x_2)$ of the constraint line $500x_1+300x_2=12000$, in particular between $(5/2,215/6)$ and $(15,15)$.

farruhota
  • 31,482