Big-M_Method_Maths_Project_Detailed.pptx

txrfryxvygiuctfctctctc

1. Big-M Method of LPP Maths Mini Project Group Members: [Add Names] Guide: [Teacher Name]

2. Introduction • Linear Programming optimizes an objective function under constraints. • Big-M Method modifies the simplex method to handle ≥ and = constraints. • Introduces artificial variables and assigns large penalty (M) to remove them.

3. Need for Big-M Method • Handles constraints of type ≥ or =. • Adds slack, surplus & artificial variables. • Uses a large penalty M to push artificial variables out of solution.

4. Steps of Big-M Method 1. Convert constraints to standard form. 2. Add artificial variables for ≥ and = constraints. 3. Modify objective function (Max: subtract M*A, Min: add M*A). 4. Solve using Simplex method. 5. Ensure artificial variables are zero in final solution.

5. Example Problem Maximize: Z = 3x₁ + 2x₂ Subject to: x₁ + x₂ ≥ 4 x₁ + 2x₂ ≤ 6 x₁, x₂ ≥ 0

6. Standard Form Conversion x₁ + x₂ - s₁ + A₁ = 4 x₁ + 2x₂ + s₂ = 6 Modified Objective: Z = 3x₁ + 2x₂ - M*A₁

7. Initial Simplex Table Show initial table with A₁ in basis & Z-row with -M.

8. Iterations Perform simplex iterations until A₁ leaves basis. Highlight pivot steps.

9. Final Solution x₁ = [value], x₂ = [value], Z = [value] A₁ = 0 → feasible solution found.

10. Applications • Operations Research: Resource allocation. • Manufacturing: Production planning. • Transportation: Logistics cost optimization. • Finance: Portfolio optimization.

11. Advantages & Limitations Advantages: • Handles any type of constraint. • Extends simplex method. Limitations: • Requires very large M. • More computational steps.

12. Conclusion • Big-M Method is a robust way to handle ≥ and = constraints. • Ensures feasible solutions by penalizing artificial variables. • Widely used in real-world optimization problems.

13. Initial Big-M Tableau & Removing Artificial Variable Initial tableau (with artificial variable A1 and big M): Basis | x1 | x2 | s1 | A1 | s2 | RHS A1 | 1 | 1 | -1 | 1 | 0 | 4 s2 | 1 | 2 | 0 | 0 | 1 | 6 Z-row | 3-M|2-M | M |-M | 0 | -4M To remove artificial variable contribution from Z-row, add M * (A1 row) to Z-row: New Z-row becomes: [3, 2, 0, 0, 0 | 0] — which is the original objective coefficients.

14. Tableau after Eliminating Artificial from Z-row Tableau after removing artificial variable from Z-row (algebraic elimination): Basis | x1 | x2 | s1 | A1 | s2 | RHS A1 | 1 | 1 | -1 | 1 | 0 | 4 s2 | 1 | 2 | 0 | 0 | 1 | 6 Z-row | 3 | 2 | 0 | 0 | 0 | 0 Now perform regular Simplex iterations using this tableau.

15. Simplex Iteration 1 (Pivot x1) Pivot 1: Entering variable = x1 (most positive in Z-row = 3). Ratio test: A1 -> 4/1 = 4 ; s2 -> 6/1 = 6 => Pivot row = A1 (smaller ratio). Pivot at (A1, x1). After pivot (x1 replaces A1): Basis | x1 | x2 | s1 | A1 | s2 | RHS x1 | 1 | 1 | -1 | 1 | 0 | 4 s2 | 0 | 1 | 1 | -1 | 1 | 2 (row2 - row1) Z-row | 0 | -1 | 3 | -3 | 0 | -12 (Z - 3*row1)

16. Simplex Iteration 2 (Pivot s1) Pivot 2: Z-row has positive coefficient for s1 = 3 -> entering variable = s1. Ratio test (only positive column entries): row1 coef = -1 (ignore), row2 coef = 1 => row2 ratio = 2 -> pivot row = s2. Pivot at (s2 row, s1 column). After pivot (s1 replaces s2): Basis | x1 | x2 | s1 | A1 | s2 | RHS x1 | 1 | 2 | 0 | 0 | 1 | 6 (row1 + row2) s1 | 0 | 1 | 1 | -1 | 1 | 2 (row2) Z-row | 0 | -4 | 0 | 0 | -3 | -18 (Z - 3*row2)

17. Final Solution & Verification Final tableau shows all reduced costs ≤ 0 (for maximization) => optimal. Basic variables and values: x1 = 6, s1 = 2, x2 = 0, s2 = 0, A1 = 0 (artificial eliminated) Original decision variable values: x1 = 6, x2 = 0 Objective value: Z = 3*x1 + 2*x2 = 3*6 + 2*0 = 18 Verify constraints: 1) x1 + x2 = 6 + 0 = 6 ≥ 4 (first constraint satisfied) 2) x1 + 2x2 = 6 + 0 = 6 ≤ 6 (second constraint satisfied) Conclusion: Optimal solution using Big-M method is x1 = 6, x2 = 0 with Z = 18.