Basic Feasible solution And Optimality condition

Question

Maximize :

z = $ x_1 + 2 x_2 - 3 x_3 + 4 x_4 $

subject to

$ x_1 + x_2 + 2 x_3 +3 x_4 = 12$

$x_2 + 2 x_3 + x_4 = 8$ where $ x_1 , x_2 , x_3 , x_4 >= 0 $

I have calculated all the possible basic solution these are

1. (0,0,3,2) and z = -1

2. (0,6,0,2) and z = 20

3. (4,0,4,0) and z = -8

4. (4,8,0,0) and z = 20

doubt 1. since in above solution $ x_1 , x_2 , x_3 , x_4 >= 0 $ will we accept solution number 1 and 3 as basic solution for maximization.

2. I have also been asked to show that optimal solution exists without solving I don't know how to do that please help

Answer 1

1.

All the possible basic solution are: $$[0,0,3,2],[0,6,0,2],[4,0,4,0],[4,8,0,0].$$ Values of $z$ are $$z(0,0,3,2)=-1,\\ z(0,6,0,2)=20,\\ z(4,0,4,0)=-8,\\ z(4,8,0,0)=20.\\ $$ Set of optimal solutions is convex. Then set of maximum points is segment $$t[0,6,0,2]+(1-t)[4,8,0,0]=[4-4t,8-2t,0,2t],\quad 0\le t\le1.$$ $$z_{max}=z\left(4-4t,8-2t,0,2t\right)=20,\quad 0\le t\le1.$$

2. From constraints we get $$0\le x_1\le 12,\quad0\le x_2\le 12,\quad 0\le x_3\le 6,\quad 0\le x_4\le 8.\quad$$ Then constraint set is closed and bounded. From Weierstrass theorem optimal solution exists.