Consider the following LP: Maximize z = 2x_1 + 3x_2 subject to x_1 + 3x^2 lessth

Question

Consider the following LP: Maximize z = 2x_1 + 3x_2 subject to x_1 + 3x^2 lessthanorequalto 6 3x_1 + 2x_2 lessthanorequalto 6 x_1, x_2 greaterthanorequalto 0 (a) Express the problem in equation form. (b) Determine all the basic solutions of the problem, and classify them as feasible and infeasible. (c) Use direct substitution in the objective function to determine the optimum basic feasible solution. (d) Verify graphically that the solution obtained in (c) is the optimum LP solution - hence, conclude that the optimum solution can be determined algebraically by considering the basic feasible solutions only. (e) Show how the infeasible basic solutions are represented on the graphical solution space.

Explanation / Answer

Solving the system of equations

Maximise z = 2x + 3y

x + 3y 6

3x + 2y 6

x 0

y 0

Table #1
==========================================================
x y s1 s2 s3 s4 z   
==========================================================
1 3 1 0 0 0 0 6
3 2 0 1 0 0 0 6
1 0 0 0 -1 0 0 0
0 1 0 0 0 -1 0 0
-2 -3 0 0 0 0 1 0

Table #2
==========================================================
x y s1 s2 s3 s4 z   
==========================================================
1 3 1 0 0 0 0 6
3 2 0 1 0 0 0 6
-1 0 0 0 1 0 0 0
0 1 0 0 0 -1 0 0
-2 -3 0 0 0 0 1 0

Table #3
==========================================================
x y s1 s2 s3 s4 z   
==========================================================
1 3 1 0 0 0 0 6
3 2 0 1 0 0 0 6
-1 0 0 0 1 0 0 0
0 -1 0 0 0 1 0 0
-2 -3 0 0 0 0 1 0

Table #4
==========================================================
x y s1 s2 s3 s4 z   
==========================================================
0.333333 1 0.333333 0 0 0 0 2   
2.33333 0 -0.666667 1 0 0 0 2   
-1 0 0 0 1 0 0 0   
0.333333 0 0.333333 0 0 1 0 2   
-1 0 1 0 0 0 1 6   

Table #5
==========================================================
x y s1 s2 s3 s4 z   
==========================================================
0 1 0.428571 -0.142857 0 0 0 1.71429   
1 0 -0.285714 0.428571 0 0 0 0.857143
0 0 -0.285714 0.428571 1 0 0 0.857143
0 0 0.428571 -0.142857 0 1 0 1.71429   
0 0 0.714286 0.428571 0 0 1 6.85714   

Optimal Solution: z = 6.85714; x = 0.857143, y = 1.71429

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.