Chapter 4, Problem 6RP

Explanation of Solution

Optimal solution:

• Consider the following linear programing problem:

$Maxz=x_1+x_2$

Subject to the constraints:

  $\begin{array}{l}2x_1+x_2\ge 5\\ 3x_1+x_2\le 3.5\\ x_1+x_2\le 1\\ x_1,x_{2 }\ge 0\end{array}$

• From the linear programming problem, it can be observed that one constraint is less than or equal to type and two constraints are greater than or equal to type.
• Add the surplus variable e₁ to the constraints greater than or equal to type constraints and add slack variables s₁,s₂ to the constraints less than or equal to type.
• Therefore, the standard form of linear programming problem is as follows:
• Max z = x₁+x₂-Ma₁

Subject to the constraints:

  $\begin{array}{l} 2x_1+x_2-e_1+a_1=3\\ 3x_1+x_2+s_1=3.5\\ x_1+x_2+s_2=1\\ x_1,x_2,s_1,e_1,a_1,s_{2 }\ge 0\end{array}$

 The basic feasible solution is,

$\begin{array}{l}{a}_1=3 \\ s_1=3.5\\ s_2=1\end{array}$

• Since basic feasible solution contains artificial variable,
• The artificial variable is eliminated