Example-2 Big M method Contd

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 detailed, step-by-step tutorial on solving a linear programming problem using the Big M Method, a technique for handling constraints that do not have an obvious initial basic feasible solution. The instructor begins by presenting a maximization problem with three variables (x1, x2, x3) and three constraints, one of which is a greater-than-or-equal-to inequality. The core of the lesson involves transforming this problem into standard form by introducing slack variables (s1, s2), surplus variables (s3), and artificial variables (A1). The instructor then constructs the initial simplex tableau, carefully assigning coefficients of 'M' (a very large positive number) to the artificial variables in the objective function to penalize their presence. The video demonstrates the entire simplex algorithm process, including identifying the entering variable (the most negative coefficient in the z-row), calculating the minimum ratio to determine the leaving variable, and performing row operations to pivot. The instructor walks through multiple iterations, showing the updated tableaus, until the optimal solution is reached, where all coefficients in the z-row are non-negative. The final solution is x1=0, x2=2, x3=0, with a maximum objective value of 8.

Chapters

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

   The video opens with a whiteboard displaying a Linear Programming Problem. The objective is to maximize Z = 6x1 + 4x2 + 0x3, subject to the constraints: 2x1 + 3x2 ≤ 30, 3x1 + 2x2 ≤ 24, and x1 + x2 ≥ 3, with all variables being non-negative. The instructor explains that the third constraint is a 'greater than or equal to' type, which means the standard simplex method cannot be applied directly because it does not have an initial basic feasible solution. The solution is to use the Big M Method, which involves introducing artificial variables to create an initial basis. The instructor writes 'Big M Method' and 'artificial variable' on the board, setting up the problem for the next steps.

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

   The instructor proceeds to convert the problem into standard form. For the first two constraints (≤), slack variables s1 and s2 are introduced. For the third constraint (≥), a surplus variable s3 is introduced, and an artificial variable A1 is added to create an initial basic feasible solution. The constraints are rewritten as: 2x1 + 3x2 + s1 = 30, 3x1 + 2x2 + s2 = 24, and x1 + x2 - s3 + A1 = 3. The objective function is modified to include the artificial variable with a large penalty, resulting in Max Z = 6x1 + 4x2 + 0s1 + 0s2 + 0s3 - MA1. The instructor then begins to set up the initial simplex tableau, writing the coefficients of the variables in the first row.

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

   The instructor completes the initial simplex tableau. The first row (Z-row) is filled with the coefficients of the objective function, which are 6, 4, 0, 0, 0, -M. The next three rows represent the constraints, with the coefficients of x1, x2, s1, s2, s3, and A1. The right-hand side (RHS) values are 30, 24, and 3. The initial basic variables are s1, s2, and A1. The instructor explains that the goal is to make the Z-row coefficients non-negative. The most negative coefficient in the Z-row is -M, which corresponds to the artificial variable A1, so A1 is the entering variable. The minimum ratio test is performed to find the leaving variable: 30/0 (invalid), 24/0 (invalid), and 3/1 = 3. The minimum ratio is 3, so A1 is the leaving variable. The pivot element is 1.

4. 10:00 – 15:00 10:00-15:00

   The instructor performs the first pivot operation. The pivot row (A1 row) is divided by the pivot element (1), which leaves it unchanged. The new Z-row is calculated by adding M times the pivot row to the old Z-row. This eliminates the -M coefficient for A1. The new Z-row becomes: Z = 6x1 + 4x2 + 0s1 + 0s2 + 0s3 + 0A1 + 3M. The new tableau is shown. The instructor identifies the entering variable for the next iteration. The most negative coefficient in the Z-row is -6 (for x1), so x1 is the entering variable. The minimum ratio test is performed: 30/2 = 15, 24/3 = 8, 3/1 = 3. The minimum ratio is 3, so A1 is the leaving variable. The pivot element is 1 in the x1 row.

5. 15:00 – 20:00 15:00-20:00

   The instructor performs the second pivot operation. The pivot row (x1 row) is divided by the pivot element (1), which leaves it unchanged. The new Z-row is calculated by adding 6 times the pivot row to the old Z-row. The new Z-row becomes: Z = 0x1 + 4x2 + 0s1 + 0s2 + 0s3 + 6x1 + 3M. The new tableau is shown. The instructor identifies the entering variable for the next iteration. The most negative coefficient in the Z-row is -4 (for x2), so x2 is the entering variable. The minimum ratio test is performed: 15/2 = 7.5, 8/2 = 4, 3/1 = 3. The minimum ratio is 3, so A1 is the leaving variable. The pivot element is 1 in the x2 row.

6. 20:00 – 25:00 20:00-25:00

   The instructor performs the third pivot operation. The pivot row (x2 row) is divided by the pivot element (1), which leaves it unchanged. The new Z-row is calculated by adding 4 times the pivot row to the old Z-row. The new Z-row becomes: Z = 0x1 + 0x2 + 0s1 + 0s2 + 0s3 + 6x1 + 4x2 + 3M. The new tableau is shown. The instructor identifies the entering variable for the next iteration. The most negative coefficient in the Z-row is -6 (for x1), so x1 is the entering variable. The minimum ratio test is performed: 15/2 = 7.5, 8/2 = 4, 3/1 = 3. The minimum ratio is 3, so A1 is the leaving variable. The pivot element is 1 in the x1 row.

7. 25:00 – 28:32 25:00-28:32

   The instructor performs the fourth pivot operation. The pivot row (x1 row) is divided by the pivot element (1), which leaves it unchanged. The new Z-row is calculated by adding 6 times the pivot row to the old Z-row. The new Z-row becomes: Z = 0x1 + 0x2 + 0s1 + 0s2 + 0s3 + 6x1 + 4x2 + 3M. The new tableau is shown. The instructor identifies the entering variable for the next iteration. The most negative coefficient in the Z-row is -6 (for x1), so x1 is the entering variable. The minimum ratio test is performed: 15/2 = 7.5, 8/2 = 4, 3/1 = 3. The minimum ratio is 3, so A1 is the leaving variable. The pivot element is 1 in the x1 row. The final tableau shows that the optimal solution is x1=0, x2=2, x3=0, with a maximum objective value of 8.

The video provides a comprehensive, step-by-step demonstration of the Big M Method for solving linear programming problems. It begins by identifying the challenge of a 'greater than or equal to' constraint, which prevents the use of the standard simplex method. The solution is to introduce an artificial variable, which is penalized with a large cost 'M' in the objective function. The instructor systematically constructs the initial simplex tableau, performs multiple iterations of the simplex algorithm, and uses the minimum ratio test to determine the pivot element. The process continues until the optimal solution is found, where all coefficients in the objective row are non-negative, and the artificial variable is driven out of the basis. The final solution is x1=0, x2=2, x3=0, with a maximum value of Z=8.