Chapter 4, Problem 2RP

Explanation of Solution

Optimal solution:

Consider the following linear programing problem:

${\text{min z= -4x}}_{\text{1}}{\text{+x}}_{\text{2}}$

Subject to the constraints:

$3x_1+x_2\le 6$

$-x_1+2x_2\le 0$

$x_1,x_{2 }\ge 0$

We add slack variables s₁, s_2. Therefore, the standard form of linear programming problem is

 ${\text{min z = -4x}}_{\text{1}}{\text{+x}}_{\text{2}}$

Subject to the constraints:

${\text{3x}}_{\text{1}}{\text{+x}}_{\text{2}}{\text{+s}}_{\text{1}}\text{= 6}$

${\text{-x}}_{\text{1}}{\text{+2x}}_{\text{2}}{\text{+s}}_{\text{2}}\text{= 0}$

The initial simple table is shown below:

z	x1	x2	s1	s2	rhs	basic variable
1	4	-1	0	0	0	z=0
0	3	1	1	0	6	s1=6
0	-1	2	0	1	0	s2=0

• Since the highest positive entry is 4, we enter the variable x₁

z	x1	x2	s1	s2	rhs	Ratio
1	4	-1	0	0	0	-
0	3	1	1	0	6	2←
0	-1	2	0	1	0	-

The pivot is 3 in row 1