Operations Research - Simplex Method Principles

Operations Research - Simplex Method Principles

1. Operations Research Chapter 03 - The Simplex Method Principles

2. 2 2 The Simplex Method Principles Definition: A variable is said to a basic variable in a given equation if it appears with a unit coefficient in that equation and zero coefficients in all other equations. Other variables are called nonbasic variables . Remark: Recall the reduced row-echelon form of the augmented matrix of a system of linear equations. Definition: A pivot operation is a sequence of elementary operations that reduces a given system to an equivalent system in which a specified variable has a unit coefficient in one equation and zero elsewhere. (this is a basic variable). Example: yields the system After a sequence of elementary row operations. This is called the canonical form of the system.

3. 3 3 The Simplex Method Principles Definition : A variable is said to be a basic variable in a given system of linear equations if it appears with a unit coefficient in one equation and zero coefficients in other equations. Other variables are called nonbasic variables . Definition: A pivot operation is a sequence of elementary row operations that reduces a given system to an equivalent system in which a specified variable has a unit coefficient in one equation and zero elsewhere. (Basic variable). Remark: The number of basic variables is determined by the number of equations in the system. (no. of basic variables is less than or equal to the no. of equations). Definition: The solution obtained from a canonical system by setting the nonbasic variables to zero and solving for the basic variables is called a basic solution. A basic feasible solution is a basic solution in which the values of the basic variables are all nonnegarive . In the previous example, the basic feasible solution is

4. 4 4 The Simplex Method Principles The simplex method is an iterative process for solving LPP’s expressed in standard form . In addition to that, the constraint equations are expressed in a canonical system. Steps: Start with an initial basic feasible solution in canonical form. Improve the initial solution (if possible) by finding another bfs with a better objective function value. The SM implicitly eliminates from consideration all those bfs’s whose objective function values are worse than the present (current) solution. Continue until a particular bfs cannot be improved further. It becomes an optimal solution, and the method terminates. Definition : A bfs that differs from the present bfs by exactly one basic variable is called an adjacent bfs . Definition : The relative profit of a variable is the change in the value of the objective function that results from increasing the value of this variable by 1.

5. 5 5 Example 1 Maximize S.T : Iteration # 1 Step 1: The system is in canonical form with respect to . T ake Notice that the current value of z= -1. (basic: , nonbasic : ) Step 2 : Compute relative profits of the nonbasic variables, as follows: 1) Z=5-7+4=2, relative profit=2-(-1)=3. 2) Z=2-6+3=-1, relative profit=-1-(-1)=0. 3)

6. 6 6 Example 1 z= 3-6+6=3, relative profit=3-(-1)=4. is the new basic variable (highest rel.profit ). Highest increase in is the minimum {4,7} = 4. Why?. Now, Iteration # 2: Step 1: Rewrite the system in canonical form with respect to {4,7}: what number we put instead of x3 in the two equations to get x4 and x5 = 0

7. 7 7 Example 1 Step 2 : Compute rel profits of the nonbasic variables. 1) 2)

8. 8 Example 1 3) is the new basic variable. = min{8,6/5} = 6/5.

9. 9 Example 1 Iteration # 3 Step 1: Rewrite the system in canonical form with respect to 1) 2)

10. 10 Example 1 3) Conclusion : All relative profits in this iteration are negative. Therefore, there is no new entering variables. The results of the previous iteration give the optimal solution . i.e DONE

11. 11 Example 2 Maximize Write the LPP in standard form, to get: Maximize

12. 12 Example 2

13. 13

14. 14

15. 15

16. 16

17. 17

18. Summary Summary of the simplex method: Start with an initial basic feasible solution ( bfs ) in canonical form. Check if the current solution is optimal or not as follows: ( i ) If the relative profits of the nonbasic variables are all zero or negative, then this is the optimal solution. STOP . (ii) Else, choose the nonbasic variable with highest relative profit as an entering variable. The leaving variable is determined by the constraint that gives the minimum value to the entering variable. (The minimum ratio rule). 3. Rewrite the system in canonical form with respect to the new basic variables. 4. GO TO STEP 2 .