Solve the following linear programming problem using the simplex method:
ššš„šššš§š š§ = 14š„ + 15š¦
š š¢ššššš” š”š
13š„ + 15š¦ ⤠80
ā12š„ ā 17š¦ ā„ ā120
š„ ā„ 0, š¦ ā„ 0
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} \n& 13 & x_{1} & + & 15 & x_{2} & \\leq 80 \\\\\n- & 12 & x_{1} & - & 17 & x_{2} & \\leq-120\n\\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\n \n \\ 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
Comments
Leave a comment