How to show that the lpp has optimal solution without solving it

Asked Nov 13 '19 at 17:59

Active Nov 13 '19 at 18:17

Viewed 386 times

I have got to maximize $$Z=x+2y-3z+4w$$

subject to constraints $$x+y+2z+3w=12$$ $$y+2z+w=8$$

$x,y,z,w\geq 0$ .

The question asks to show without actually solving the lpp that it has an optimal solution. For that I added the two constraints to get $x+2y+4z+4w=20$ and from this I put the value of $x+2y+4w$ in objective function which became $Z=20-7z$.

Thereafter I concluded that Z could not be greater than $20$ i.e. Z is bounded above. Corresponding to this maximum value of Z we have z=0 and using this I can find solutions such as $(0,6,0,2)$ and $(4,8,0,0)$ which are feasible. So the optimal solutions exist. But I want to know what are the other methods of showing it. Can we use duality theory?

edited Nov 13 '19 at 18:17

callculus42

30,550

asked Nov 13 '19 at 17:59

HARVEER RAWAT

You want to $\underline{\text{maximize}}$ $Z=20-7x$. You´re right that 20 is the upper bound. Therefore .... – callculus42 Nov 13 '19 at 18:29
This is a case where I was fortunate enough to write the objective function in terms of only one variable using the given constraints. But all cases won't be as simple as this. I am therefore looking for a general method of showing existence of optimal solution. – HARVEER RAWAT Nov 13 '19 at 18:54
Then post another example. – callculus42 Nov 13 '19 at 18:58
Let us then consider maximizing Z*=2x+y-3z+4w subject to the same constraints as in original problem. – HARVEER RAWAT Nov 13 '19 at 19:07
One approach is to calculate $2\cdot (I-II)=2x+4w=8$ and obviously $z=0$. Therefore $Z=8+y$ Thus $Z^*=8+8=16$ – callculus42 Nov 13 '19 at 19:32
How can we show existence of optimal solution without indulging in such manipulation of constraints? – HARVEER RAWAT Nov 13 '19 at 19:35
2

If it exists a solution for the constraints, then there exists an optimal solution. – callculus42 Nov 13 '19 at 19:45

How to show that the lpp has optimal solution without solving it

0 Answers0