Explanation of Big M Method

This video lesson is available to enrolled students.

Enroll to watch — Coal India Management Trainee (CS) Recruitment 2026

AI Summary

An AI-generated summary of this video lecture.

This video is a lecture on solving a linear programming problem using the Big M Method. The instructor begins by presenting a maximization problem with three constraints, including one with a greater-than-or-equal-to sign. He explains that the standard simplex method cannot be applied directly because the initial basic feasible solution is not available. To address this, he introduces the Big M Method, which involves adding artificial variables (A1, A2, A3) to the constraints to create an initial identity matrix. The objective function is modified by adding a large penalty term, -M, for each artificial variable, ensuring they are driven to zero in the optimal solution. The instructor then constructs the initial simplex tableau, showing the coefficients for the decision variables (x1, x2), slack variables (s1, s2), and artificial variables (A1, A2, A3). He explains the process of selecting the entering variable (the one with the most negative coefficient in the z-row) and the leaving variable (using the minimum ratio test). The video demonstrates the first iteration of the simplex method, showing the pivot operation and the updated tableau, and concludes by explaining the next steps in the algorithm.

Chapters

1. 0:00 – 2:00 00:00-02:00

   The video opens with a completed simplex tableau for a linear programming problem, labeled 'Big M Method'. The instructor, standing with his back to the camera, points to the tableau, which includes the objective function row (z), the constraint rows, and the solution column. The tableau shows the initial basic variables as s1, s2, and A1, with their corresponding values. The instructor explains that the current solution is not feasible because the artificial variable A1 has a positive value of 3, indicating that the initial basic feasible solution is not valid. He points to the z-row, where the coefficient for A1 is -M, and explains that this is the penalty for having an artificial variable in the basis. The instructor then begins to explain the process of selecting the entering variable, pointing to the z-row and identifying the most negative coefficient, which is -M for A1, as the entering variable. He also points to the ratio column, explaining that the minimum ratio test will be used to determine the leaving variable.

2. 2:00 – 5:00 02:00-05:00

   The instructor continues to explain the Big M Method, focusing on the initial simplex tableau. He points to the z-row and explains that the goal is to make all coefficients in the z-row non-negative. He identifies the entering variable as A1, which has the most negative coefficient (-M) in the z-row. He then explains the minimum ratio test to find the leaving variable. He points to the pivot column (A1) and the solution column, calculating the ratios of the solution values to the pivot column values. He identifies the minimum ratio as 3, which corresponds to the row for A1, indicating that A1 is the leaving variable. He then explains that the pivot element is the intersection of the entering and leaving variables, which is 1 in the A1 row and A1 column. He proceeds to perform the pivot operation, dividing the pivot row by the pivot element (1) and then using row operations to make all other elements in the pivot column zero. He updates the tableau, showing the new basic variables as s1, s2, and x1, and the new values in the solution column.

3. 5:00 – 10:00 05:00-10:00

   The instructor now analyzes the updated simplex tableau after the first iteration. He points to the z-row and explains that the coefficient for the artificial variable A1 is now 0, which is good because it means the artificial variable is no longer in the basis. He then identifies the next entering variable by looking for the most negative coefficient in the z-row, which is -2 for x2. He explains that x2 will enter the basis. He then performs the minimum ratio test to find the leaving variable, pointing to the pivot column (x2) and the solution column. He calculates the ratios and identifies the minimum ratio as 8, which corresponds to the row for s2, indicating that s2 is the leaving variable. He then performs the pivot operation, dividing the pivot row (s2 row) by the pivot element (1) and using row operations to make all other elements in the pivot column zero. He updates the tableau, showing the new basic variables as s1, x2, and x1, and the new values in the solution column. He explains that the process will continue until all coefficients in the z-row are non-negative.

4. 10:00 – 11:27 10:00-11:27

   The instructor begins to write the original linear programming problem on the whiteboard. He writes the objective function: Max Z = 6x1 + 4x2. He then writes the constraints: 2x1 + 3x2 ≤ 30, 3x1 + 2x2 ≤ 24, and x1 + x2 ≥ 3. He explains that the first two constraints are of the less-than-or-equal-to type, so slack variables (s1, s2) can be added. The third constraint is of the greater-than-or-equal-to type, so it requires a surplus variable (s3) and an artificial variable (A1). He writes the standard form of the constraints: 2x1 + 3x2 + s1 = 30, 3x1 + 2x2 + s2 = 24, and x1 + x2 - s3 + A1 = 3. He then explains that the objective function must be modified to include the artificial variable with a large penalty, so the new objective function is Max Z = 6x1 + 4x2 + 0s1 + 0s2 + 0s3 - MA1. He explains that the Big M Method is used to handle this type of constraint and that the artificial variable will be driven to zero in the optimal solution.

The video provides a comprehensive, step-by-step demonstration of the Big M Method for solving linear programming problems with mixed constraints. It begins by identifying the core challenge: the lack of an initial basic feasible solution due to a greater-than-or-equal-to constraint. The instructor clearly explains the solution: introducing artificial variables to create an initial identity matrix and penalizing them heavily in the objective function. The core of the lesson is the application of the simplex method to this modified problem. The instructor meticulously walks through the process of selecting entering and leaving variables using the z-row and minimum ratio test, performing pivot operations to update the tableau. The progression from the initial tableau to the first iteration demonstrates the algorithm's mechanics, showing how the artificial variable is systematically eliminated from the basis. The final segment reinforces the method by deriving the problem from scratch, ensuring the student understands the entire process from formulation to solution.