use the simplex algorithm Characterize all optimal solutions

use the simplex algorithm

Characterize all optimal solutions to the following LP: max z = -8x_5 s.t. x_1 + x_3 + 3x_4 + 2x_5 = 2 x_2 + 2x_3 + 4x_4 + 5x_5 = 5 All x_t greaterthanorequalto 0

Solution

Use the simplex algorithm. set in tablular form:

Table 1
------------------------------------------------
x₅     s₁     s₂     s₃     s₄     z           
--------------------------------------------------
2      1      0      0      0      0      2    
5      0      1      0      0      0      5    
2      0      0      -1     0      0      2    
5      0      0      0      -1     0      5    
8      0      0      0      0      1      0    

Table 2
------------------------------------------------
x₅     s₁     s₂     s₃     s₄     z           
--------------------------------------------------
0      1      0      0      0.4    0      0    
0      0      1      0      1      0      0    
0      0      0      -1     0.4    0      0    
1      0      0      0      -0.2   0      1    
0      0      0      0      1.6    1      -8   

Table 3
------------------------------------------------
x₅     s₁     s₂     s₃     s₄     z           
--------------------------------------------------
0      1      0      0      0.4    0      0    
0      0      1      0      1      0      0    
0      0      0      1      -0.4   0      0    
1      0      0      0      -0.2   0      1    
0      0      0      0      1.6    1      -8   

Hence Optimal Solution: z = -8; x₅ = 1