Example of Degeneracy - Part 2

Duration: 20 min

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 presents a step-by-step solution to a linear programming problem using the Simplex method. The instructor begins by writing the standard form of the problem, which includes a maximization objective function and three inequality constraints. Slack variables (S1, S2, S3) are introduced to convert the inequalities into equations, forming the initial simplex tableau. The instructor then demonstrates the first iteration of the Simplex algorithm, identifying the entering variable (x1) by selecting the most negative coefficient in the objective row (Cj-Zj), and the leaving variable (S1) by calculating the minimum ratio of the right-hand side to the pivot column's positive entries. The pivot element is 2, and the instructor performs row operations to create a new tableau. The process continues, with the instructor identifying the next entering variable (x2) and the leaving variable (S2), updating the tableau accordingly. The final tableau is shown to be optimal, with all Cj-Zj values non-negative, and the optimal solution is read from the table: x1 = 100/3, x2 = 100/3, x3 = 0, and the maximum value of Z is 1000/3.

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 = 22x1 + 30x2 + 25x3, subject to three constraints: 2x1 + 2x2 + x3 ≤ 100, 2x1 + x2 + 2x3 ≤ 100, and x1 + 2x2 + 2x3 ≤ 100, with all variables non-negative. The instructor begins by writing the initial simplex tableau, introducing slack variables S1, S2, and S3 to convert the inequalities into equations. The initial tableau shows the coefficients of the variables, the right-hand side (RHS) values, and the objective function row (Cj). The instructor identifies the first pivot element by finding the most negative value in the Cj-Zj row, which is -22 for x1, indicating x1 is the entering variable.

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

    The instructor proceeds to determine the leaving variable by calculating the minimum ratio of the RHS to the corresponding positive elements in the pivot column (x1's column). The ratios are 100/2 = 50 for S1, 100/2 = 50 for S2, and 100/1 = 100 for S3. The minimum ratio is 50, so S1 is the leaving variable. The pivot element is the intersection of the x1 column and S1 row, which is 2. The instructor then performs row operations to make the pivot element 1 and to eliminate the other entries in the x1 column. The new tableau is shown, with the updated values for the basic variables S1, S2, and S3, and the objective function row.

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

    The instructor analyzes the new tableau to find the next entering variable. The Cj-Zj row shows values of 0, 2, 0, 0, 11, and 0. The most negative value is -2, which corresponds to x2, so x2 is the entering variable. The leaving variable is determined by the minimum ratio test: 50/1 = 50 for S1, 50/0.5 = 100 for S2, and 100/1.5 = 66.67 for S3. The minimum ratio is 50, so S1 is the leaving variable. The pivot element is 1 in the S1 row and x2 column. The instructor performs row operations to update the tableau, making the pivot element 1 and eliminating other entries in the x2 column. The new tableau is displayed, showing the updated values for the basic variables S2, S3, and x2.

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

    The instructor checks the Cj-Zj row of the updated tableau. The values are 0, 0, 0, 0, 11, and 0. Since all values are non-negative, the current solution is optimal. The instructor identifies the optimal values of the variables from the final tableau: x1 = 100/3, x2 = 100/3, x3 = 0, S1 = 0, S2 = 0, S3 = 0. The maximum value of Z is calculated as 22*(100/3) + 30*(100/3) + 25*0 = 1000/3. The instructor also notes that the final tableau is the optimal solution table, and the process is complete.

  5. 15:00 – 19:33 15:00-19:33

    The instructor reviews the final optimal tableau, confirming that all Cj-Zj values are non-negative, which signifies an optimal solution. The values of the basic variables are read from the RHS column: x1 = 100/3, x2 = 100/3, and x3 = 0. The maximum value of the objective function Z is 1000/3. The instructor emphasizes that the Simplex method has successfully found the optimal solution to the linear programming problem. The video concludes with the final answer clearly stated on the whiteboard.

The video provides a comprehensive, step-by-step demonstration of the Simplex method for solving a linear programming problem. It begins with the formulation of the problem in standard form, including the objective function and constraints. The instructor then constructs the initial simplex tableau, which is the foundation for the algorithm. The core of the lesson is the iterative process of the Simplex method, where the instructor systematically identifies the entering and leaving variables using the minimum ratio test and pivot operations. Each iteration transforms the tableau, moving closer to the optimal solution. The video concludes by showing the final tableau, where the optimality condition is met, and the optimal values for the decision variables and the objective function are clearly read. This structured approach effectively teaches the mechanics of the Simplex algorithm, from setup to solution.