1

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.

  1. I have also been asked to show that optimal solution exists without solving I don't know how to do that please help
Abhishek Verma
  • 97
  • 1
  • 8

1 Answers1

2

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

  1. 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.
Aleksas Domarkas
  • 2,401
  • is the negative basic solution acceptable – Abhishek Verma Jan 25 '19 at 17:00
  • and can you possibly tell me about this Weierstrass theorem, are you talking about the one we study for essential singularity in complex analysis – Abhishek Verma Jan 25 '19 at 17:06
  • Weierstrass theorem: If a function is continuous on a closed and bounded set $X\subset\mathbb{R}^n$ , then has both a maximum and a minimum on $X$. see http://mathworld.wolfram.com/ExtremeValueTheorem.html – Aleksas Domarkas Jan 25 '19 at 19:17