Question: 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](https://i.stack.imgur.com/HACvN.png)](https://i.stack.imgur.com/HACvN.png)

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)?

Answer: 
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](https://i.stack.imgur.com/QgCR2.png)](https://i.stack.imgur.com/QgCR2.png)

**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).
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)$.