Question

Solve the following linear programming problem using the simplex method:

𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝑧 = 14𝑥 + 15𝑦

𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜

13𝑥 + 15𝑦 ≤ 80

−12𝑥 − 17𝑦 ≥ −120

𝑥 ≥ 0, 𝑦 ≥ 0

Answer 1

Replace $x$ by $x_1$ and $y$ by $x_2.$

Problem is: $\operatorname{Max} Z=14 x_{1}+15 x_{2}$

subject to:

$\begin{array}{rllll} & 13 & x_{1} & + & 15 & x_{2} & \leq 80 \\ - & 12 & x_{1} & - & 17 & x_{2} & \leq-120 \end{array}$

Here, $b_{2}=-120<0$

so multiply this constraint by $-1$ to make $b_{2}>0 .$

$12 x_{1}+17 \quad x_{2} \geq 120 \ and \ x_{1}, x_{2} \geq 0$

The problem is converted to canonical form by adding slack, surplus and artificial variables as appropriate:

1. As the constraint-1 is of type '≤' we should add slack variable $S_1$

2. As constraint-2 is of type '≥' we should subtract surplus variable $S_2$  and add artificial variable $A_1.$

After introducing slack, surplus,artificial variables:

$\operatorname{Max} Z=14 x_{1}+15 x_{2}+0 S_{1}+0 S_{2}-M A_{1}$

subject to:

$13 x_{1}+15 x_{2}+S_{1} \quad=80 \\ 12 x_{1}+17 x_{2} \quad-S_{2}+A_{1}=120 \\ and \ x_{1}, x_{2}, S_{1}, S_{2}, A_{1} \geq 0$

Negative minimum Zj-Cj is -17M-15 and its column index is 2. So, the entering variable is x2.

Minimum ratio is 5.3333 and its row index is 1. So, the leaving basis variable is S1.

∴ The pivot element is 15.

Entering =x2, Departing =S1, Key Element =15

Since all Zj-Cj≥0

Hence, the optimal solution arrives with value of variables as :

x1=0,x2=5.3333

Max Z=80

But this solution is not feasible

because the final solution violates the 2nd constraint  12 x1 + 17 x2 ≥ 120.

and the artificial variable A1 appears in the basis with a positive value of 29.3333