Consider the following LP Maximize z 2x1 3x2 subject to x1

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.

Solution

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