Use the simplex algorithm to find two optimal solutions to t

Use the simplex algorithm to find two optimal solutions to the following LP. How many optimal solutions does this LP have? Find a third optimal solution. max z = 4x_1 + x_2 s.t. 2x_1 + 3x_2 lessthanorequalto 4 x_1 + x_2 lessthanorequalto 1 4x_1 + x_2 lessthanorequalto 2 x_1, x_2 greaterthanorequalto 0

Solution

Solve by simplex method:

Table 1
-------------------------------------------------
x₁     x₂     s₁     s₂     s₃     z           
-------------------------------------------------
2      3      1      0      0      0      4    
1      1      0      1      0      0      1    
4      1      0      0      1      0      2    
-4     -1     0      0      0      1      0    

Table 2
-------------------------------------------------
x₁     x₂     s₁     s₂     s₃     z           
-------------------------------------------------
0      2.5    1      0      -0.5   0      3    
0      0.75   0      1      -0.25 0      0.5  
1      0.25   0      0      0.25   0      0.5  
0      0      0      0      1      1      2    

Hence Optimal Solution: z = 2; x₁ = 0.5, x₂ = 0