Chapter 4, Problem 7RP

Explanation of Solution

Optimal solution:

Consider the following linear programing problem:

$maxz=4x_1+x_2$

Subject to the constraints:

$\begin{array}{l} 2x_1+3x_2\le 4\\ 3x_1+x_2\le 1\\ x_1+x_2\le 2\\ 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

• max z = 4x₁+x₂
• Subject to the constraints:

  $\begin{array}{l}2x_1+3x_2+s_1=4\\ x_1+x_2+s_2=1\\ 4x_1+x_2+s_3=2\end{array}$

The initial simplex table is:

z	x1	x2	s1	s2	s3	rhs	Basic variable
1	-4	-1	0	0	0	0	z = 0
0	2	3	1	0	0	4	s1 = 4
0	1	1	0	1	0	1	s2 = 1
0	4	1	0	0	1	2	s3 = 2

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

z	x1	x2	s1	s2	s3	rhs	Basic variable
1	-4	-1	0	0	0	0	-
0	2	3	1	0	0	4	2
0	1	1	0	1	0	1	1
0	4	1	0	0	1	2	0.5

• The pivot is 4 in row 3.
• ${\text{R}}_3\to \frac{1}{4}{\text{R}}_3$
• R₀→R₀+4R₃
• R₁→R₁-R₂
• R₂→R₂-R₃

z	x1	x2	s1	s2	s3	rhs	Basic variable
1	0	0	0	0	1	2	z=2
0	0	$\frac{5}{2}$	1	0	$-\frac{1}{2}$	3	s1=3
0	0	$\frac{3}{4}$	0	1	$-\frac{1}{4}$	0