Chapter 4, Problem 8RP

Explanation of Solution

Optimal solution:

Consider the following linear programing problem:

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

Subject to the constraints:

  $\begin{array}{l}2x_1+x_2\le 6\\ 2x_1-x_2\le 0\\ x_1,x_2\ge 0\end{array}$

Slack variables s₁, s₂, s₃ are added. Therefore, the standard form of the linear programming problem is

  ${\text{max z = 5x}}_{\text{1}}{\text{+x}}_{\text{2}}$

Subject to the constraints:

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

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

The initial simplex table is:

z	x1	x2	s1	s2	rhs	Basic variable
1	-5	-1	0	0	0	z = 0
0	2	1	1	0	6	s1 = 6
0	1	-1	0	1	0	s2 = 0

Since the highest negative entry is -5, variable x₁ is entered

z	x1	x2	s1	s2	rhs	Ratio
1	-5	-1	0	0	0	-
0	2	1	1	0	6	$\frac{6}{2}=3$
0	1	-1	0	1	0	$\frac{0}{1}=0\leftarrow$

The pivot is 4 in row 3