Two Phase Method - Part 3

Duration: 16 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 is a detailed, step-by-step tutorial on solving a linear programming problem using the Two-Phase Method, a technique for handling problems with artificial variables. The instructor begins by presenting the original maximization problem, which includes constraints with inequality signs and non-negativity conditions. He then converts this into a standard form by introducing slack, surplus, and artificial variables (A1, A2) to create an initial basic feasible solution. The core of the video focuses on Phase 1 of the Two-Phase Method, where the objective is to minimize the sum of the artificial variables (Z = A1 + A2) to drive them to zero. The instructor demonstrates the Simplex method, showing the initial simplex tableau, identifying the entering variable (the most negative coefficient in the Z-row), and the leaving variable (using the minimum ratio test). He performs row operations to pivot, updating the tableau at each iteration. The process continues until the Z-row has no negative coefficients, indicating an optimal solution for Phase 1. The final step shown is the transition to Phase 2, where the artificial variables are removed, and the original objective function is used to find the optimal solution for the original problem. The video concludes with the final simplex tableau, showing the optimal values for the decision variables and the maximum value of the objective function.

Chapters

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

    The video opens with a whiteboard displaying a linear programming problem to be solved using the Two-Phase Method. The problem is to maximize Z = 5x1 - 4x2 + 3x3, subject to the constraints 2x1 + x2 - x3 = 20, x1 + 5x2 + 10x3 ≤ 76, and 8x1 - 3x2 + 6x3 ≤ 50, with all variables being non-negative. The instructor begins by explaining the need for the Two-Phase Method because the first constraint is an equality, which requires an artificial variable (A1) to start the Simplex method. He writes the initial simplex tableau for Phase 1, where the objective is to minimize Z = A1. The tableau includes the coefficients of the variables, the right-hand side (RHS) values, and the Z-row, which is initially set to 0 for all variables except A1, which has a coefficient of 1. The instructor identifies the entering variable as A1, which has the most negative coefficient in the Z-row, and the leaving variable as the one corresponding to the minimum ratio of the RHS to the pivot column's positive entries.

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

    The instructor proceeds with the first iteration of the Simplex method for Phase 1. He identifies the pivot element as the intersection of the A1 column and the S1 row, which is the value 2. He then performs row operations to make the pivot element 1 and to eliminate the other entries in the A1 column. The new S1 row is calculated as the old S1 row divided by 2. The new A1 row is calculated as the old A1 row minus 2 times the new S1 row. The new Z row is calculated as the old Z row minus 1 times the new S1 row. After these operations, the new tableau is shown, with the entering variable A1 now being replaced by S1 in the basis. The instructor then checks the Z-row for any negative coefficients, finding that the coefficient for A2 is -1, indicating that the solution is not yet optimal for Phase 1. He identifies A2 as the new entering variable and proceeds to find the leaving variable using the minimum ratio test.

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

    The instructor identifies the leaving variable for the second iteration. The pivot column is the A2 column, and the minimum ratio is calculated as 10/1 = 10, which corresponds to the S2 row. The pivot element is 1. He performs the row operations to make the pivot element 1 (which it already is) and to eliminate the other entries in the A2 column. The new S2 row is the old S2 row. The new A2 row is calculated as the old A2 row minus 1 times the new S2 row. The new Z row is calculated as the old Z row minus 1 times the new S2 row. After these operations, the new tableau is shown. The instructor checks the Z-row again and finds that all coefficients are now non-negative, indicating that the optimal solution for Phase 1 has been reached. The value of Z is 0, which means the artificial variables have been driven to zero, and a feasible solution has been found. The basis now consists of S1, S2, and x3.

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

    The instructor transitions to Phase 2 of the Two-Phase Method. He removes the artificial variables A1 and A2 from the tableau and replaces the Z-row with the original objective function, Z = 5x1 - 4x2 + 3x3. He then calculates the new Z-row by subtracting the appropriate multiples of the basic variable rows from the objective function row. The new Z-row is calculated as Z - 5x1 + 4x2 - 3x3 = 0. He then checks the Z-row for negative coefficients to determine the entering variable. The coefficient for x1 is -5, which is the most negative, so x1 is the entering variable. He then performs the minimum ratio test to find the leaving variable. The pivot column is the x1 column, and the minimum ratio is 10/1 = 10, which corresponds to the S2 row. The pivot element is 1. He performs the row operations to make the pivot element 1 and to eliminate the other entries in the x1 column. The new S2 row is the old S2 row. The new x1 row is calculated as the old x1 row minus 1 times the new S2 row. The new Z row is calculated as the old Z row minus 5 times the new S2 row.

  5. 15:00 – 15:58 15:00-15:58

    The instructor completes the second iteration of Phase 2. He calculates the new Z-row, which is now Z - 11x2 + 12x3 + 5S2 = 50. He checks the Z-row for negative coefficients and finds that the coefficient for x2 is -11, which is the most negative, so x2 is the entering variable. He performs the minimum ratio test to find the leaving variable. The pivot column is the x2 column, and the minimum ratio is 10/1 = 10, which corresponds to the S2 row. The pivot element is 1. He performs the row operations to make the pivot element 1 and to eliminate the other entries in the x2 column. The new S2 row is the old S2 row. The new x2 row is calculated as the old x2 row minus 1 times the new S2 row. The new Z row is calculated as the old Z row minus 11 times the new S2 row. The final tableau is shown, with the optimal solution. The instructor states that the optimal value of Z is 155/3, and the values of the variables are x1 = 30, x2 = 0, x3 = 55/3, S1 = 0, S2 = 0.

The video provides a comprehensive, step-by-step walkthrough of the Two-Phase Method for solving linear programming problems. It begins by setting up the problem with artificial variables to handle equality constraints, then systematically applies the Simplex method in two distinct phases. Phase 1 focuses on minimizing the sum of artificial variables to find a feasible solution, while Phase 2 uses the original objective function to find the optimal solution. The instructor meticulously demonstrates each step of the Simplex algorithm, including identifying entering and leaving variables, performing pivot operations, and updating the tableau. The progression from the initial problem to the final optimal solution is clearly illustrated, making it an excellent resource for understanding this fundamental optimization technique.