Chapter 4, Problem 1RP

Explanation of Solution

Optimal solutions:

Consider the following linear programing problem:

  ${\text{Max Z=5x}}_{\text{1}}{\text{+3x}}_{\text{2}}{\text{+x}}_{\text{3}}$

Subject to the constraints:

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

  $5x_1+3x_2+6x_3\le 15$

  ${\text{x}}_{\text{1}}{\text{,x}}_{\text{2}}{\text{,x}}_{\text{3 }}\ge \text{0}$

Calculate the optimum solution for the above linear programming problem by using the simplex algorithm as follows:

• The constraints are ≤ constraints, now it is necessary to convert it to an equality constraint by adding slack variables s₁, s₂ to the two constraints. The standard form of linear programming problem is as shown below:

  ${\text{Max Z=5x}}_{\text{1}}{\text{+3x}}_{\text{2}}{\text{+x}}_{\text{3}}{\text{+0s}}_{\text{1}}{\text{+0s}}_{\text{2}}$

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

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

  ${\text{x}}_{\text{1}}{\text{,x}}_{\text{2}}{\text{,x}}_{\text{3}}{\text{,s}}_{\text{1}}{\text{,s}}_{\text{2}}\ge \text{0}$

The initial simplex table is as follows:

• Choose base variables by observing that which values form an identity matrix in the table. Here X₄, X₅ variable values form an identity matrix. Take the corresponding C_j values of X₄, X₅ as C_b values.

  $\begin{array}{l} Z_j=C_b{X}_b\\ Z_b=(0\times 6)+(0\times 15) \\ Z_b=0\\ Z_1=C_b{X}_1\\ Z_1=(0\times 1)+(0\times 5)\\ Z_1=0\end{array}$

• Calculate the rest of variables and shown in the initial table:

	Cj		5	3	1	0	0
Base	Cb	Xb	X1	X2	X3	X4	X5
X4	0	6	1	1	3	1	0
X5	0	15	5	3	6	0	1
Zj	0	0	0	0	0	0	0
Zj-Cj		0	-5	-3	-1	0	0

• From the above simplex table, observe $Z_j-C_j$ values. -5 is the most negative number and therefore the negative entry is -5.
• Calculate the ratio value by using the following formula.

$\text{Ratio=}\frac{\text{Right hand side value fo the constraint}}{\text{Coefficient of entering variable in the constraint}}$

	Cj		5	3	1	0	0
Base	Cb	Xb	X1	X2	X3	X4	X5	Ratio= Xb/ X1
X4	0	6	1	1	3	1	0	(6/1)=6
X5	0	15	5	3	6	0	1	(15/5)=3
Zj	0	0	0	0	0	0	0
Zj-Cj		0	-5	-3	-1	0	0

${\text{R}}_{\text{2}}\to \frac{\text{1}}{\text{5}}\text{R}{\text{2}}_{}$

$R_1\to R_1-R_2$

The resultant iteration table is as shown below:

	Cj		5	3	1	0	0
Base	Cb	Xb	X1	X2	X3	X4	X5
X4	0	3	0	0.4	1.8	1	-0.2
X1	5	3	1	0.6	1.2	0	0.2
Zj		15	5	3	6	0	1
Zj-Cj		15	0	0	5	0	1

Since, the last row Z_j-C_j contains all positive entries, the solution is optimal. Therefore, the value decision variables and Max Z is,

$\begin{array}{l}{x}_1=5\\ x_2=0 \\ x_3=0 \\ MaxZ=5x_1+3x_2+x_3\\ MaxZ=(5\times 0)+(3\times 5)+(1\times 0)\\ MaxZ=15\end{array}$

The optimal maximized Z value is 15.