Operations Research - The Dual Simplex Method

Operations Research - The Dual Simplex Method

1. Chapter 09 – The dual simplex method Operations research

2. Primal simplex Maximize or Minimize Z Subject to  

3. Rules of constructing duality For every primal constraint there is a dual variable. For every primal variable there is a dual constraint. The constraint coefficients of a primal variable from the left-hand side coefficients of the corresponding dual constraint and its objective function coefficient of the same variable becomes the right-hand side of the dual constraints. If the primal objective function is maximize (minimize), then the dual problem is minimize (maximize). If the primal problem is maximize (minimize), then the dual constraints must be >= (<=). All dual variables are originally unrestricted.

4. Example 1 Primal Min Z= 15x 1 + 12x 2 Subject to: x 1 + 2x 2 >= 3 2x 1 - 4 x 2 <= 5 x 1 , x 2 >= 0

5. Example 1 Standard from Min Z= 15x 1 + 12x 2 Subject to: x 1 + 2x 2 – x 3 = 3 2x 1 - 4 x 2 + x 4 = 5 x 1 , x 2 , x 3 , x 4 >= 0

6. Example 1 The dual problem Max W = 3y 1 + 5y 2 Subject to: y 1 + 2 y 2 <= 15 2y 1 – 4 y 2 <= 12 -y 1 + 0y 2 <= 0 y 1 >= 0 0y 1 + y 2 <= 0 y 2 <= 0, y 2 is unrestricted

7. Example 2 Primal Max Z= 5x 1 + 12x 2 +4x 3 Subject to: x 1 + 2x 2 + x 3 <= 10 2x 1 - x 2 + 3x 3 = 8 x 1 , x 2 , x 3 >= 0

8. Example 2 Standard form Max Z= 5x 1 + 12x 2 +4x 3 Subject to: x 1 + 2x 2 + x 3 + x 4 = 10 2x 1 - x 2 + 3x 3 + 0x 4 = 8 x 1 , x 2 , x 3 , x 4 >= 0

9. Example 2 The dual problem Min W = 10y 1 + 8y 2 Subject to: y 1 + 2y 2 >= 5 2y 1 - y 2 >= 12 y 1 + 3y 2 >= 4 y 1 + 0y 2 >= 0 y 1 >= 0, y 2 is unrestricted

10. Example 2 by two phase method By two phase method Min W = 10y 1 + 8y 2 Subject to: y 1 + 2y 2 >= 5 2y 1 - y 2 >= 12 y 1 + 3y 2 >= 4 y 1 + 0y 2 >= 0 y 1 >= 0, y 2 is unrestricted When y is unrestricted its equal to y’-y’’

11. Example 2 by two phase method Chanocial form Min W = 10y 1 + (8y 2 ’ – 8y 2 ’’) Subject to: y 1 + (2y 2 ’ – 2y 2 ’’) – y 3 + y 6 = 5, (y 3 is surplus, y 6 is artificial) 2y 1 – (y 2 ’ – y 2 ’’) – y 4 + y 7 = 12, ( y 4 is surplus, y 7 is artificial) y 1 + (3y 2 ’ – 3y 2 ’’) – y 5 + y 8 = 4 , ( y 5 is surplus, y 8 is artificial)

12. Example 2 by two phase method Phase 1: Min W’= y 6 + y 7 + y 8 Subject to: y 1 + 2y 2 ’ – 2y 2 ’’ – y 3 + y 6 = 5 2y 1 – y 2 ’ + y 2 ’’ – y 4 + y 7 = 12 y 1 + 3y 2 ’ – 3y 2 ’’ – y 5 + y 8 = 4

13. Example 2 by two phase method

14. Example 2 by two phase method

15. Example 2 by two phase method

16. Example 2 by two phase method Phase 2: Min W ’= 10y 1 + 8y 2 ’ – 8y 2 ’’ Subject to: y 1 + 2y 2 ’ – 2y 2 ’’ – y 3 = 5 2y 1 – y 2 ’ + y 2 ’’ – y 4 = 12 y 1 + 3y 2 ’ – 3y 2 ’’ – y 5 = 4 Basic: y5=3/5, y2’’=2/5, y1=29/5, W=54.8

17. Example 2 by two phase method

18. Optimal Dual Solution How to find the optimal solution of the dual problem, when the optimal solution of the primal problem is known? By 2 methods.

19. Example 3 Consider this problem Max Z= 5x 1 + 12x 2 + 4x 3 Subject to: x 1 + 2x 2 + x 3 <= 10 2x 1 - x 2 + 3x 3 = 8 x 1 , x 2 , x 3 >= 0

20. Example 3 Standard form Max Z= 5x 1 + 12x 2 +4x 3 – Mx 5 Subject to: x 1 + 2x 2 + x 3 + x 4 = 10, x 4 is a slack 2x 1 - x 2 + 3x 3 + x 5 = 8, x 5 is artificial x 1 , x 2 , x 3 , x 4 , x 5 >= 0

21. Example 3 The dual problem Min W = 10y 1 + 8y 2 Subject to: y 1 + 2y 2 >= 5 2y 1 - y 2 >= 12 y 1 + 3y 2 >= 4 y 1 + 0y 2 >= 0 y 1 >= 0, y 2 is unrestricted We now show how the optimal dual values are determined using the two methods described before.

22. Example 3