Question-2 (Duality) - 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 is a detailed, step-by-step tutorial on solving a linear programming problem using the Big M method, a technique for handling constraints with 'greater than or equal to' and 'equality' signs. The instructor begins by presenting the original minimization problem, which includes variables w1, w2, w3, w4, and artificial variables A1, A2. He then explains the need to convert the problem into standard form by introducing slack variables (s1, s2) and artificial variables (A1, A2) to create an initial basic feasible solution. The core of the video involves constructing the initial simplex tableau. The instructor meticulously sets up the tableau with columns for the decision variables, slack variables, artificial variables, and the right-hand side (RHS). He then calculates the initial objective function row (Zj - Cj) by applying the Big M penalty, where the coefficients of the artificial variables in the objective function are set to -M (a very large negative number) to force them out of the basis. The video demonstrates the first iteration of the simplex method, showing the selection of the entering variable (the one with the most negative Zj - Cj value) and the leaving variable (determined by the minimum ratio test). The instructor performs the necessary row operations to pivot and create a new tableau, continuing the process until an optimal solution is reached. The final solution, with the values of the decision variables and the minimum value of the objective function, is clearly presented on the whiteboard.

Chapters

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

    The video opens with a whiteboard displaying the title 'Linear Programming Problem'. The instructor introduces the problem, which is to minimize Z = 10w1 + 6w2 + 2w3 + w4, subject to the constraints w1 + w2 + w3 + w4 ≥ 2 and 2w1 + w2 - w3 - w4 ≥ 1, with all variables being non-negative. The instructor explains that since the constraints are 'greater than or equal to', slack variables (s1, s2) and artificial variables (A1, A2) must be added to convert the problem into standard form. He writes the transformed constraints: w1 + w2 + w3 + w4 - s1 + A1 = 2 and 2w1 + w2 - w3 - w4 - s2 + A2 = 1. He then writes the objective function as Min Z = 10w1 + 6w2 + 2w3 + w4 + 0s1 + 0s2 + MA1 + MA2, explaining that the artificial variables are penalized with a large cost M to ensure they are driven to zero in the optimal solution.

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

    The instructor begins to construct the initial simplex tableau. He writes the variables w1, w2, w3, w4, s1, s2, A1, A2 in the top row. He then fills in the coefficients for the two constraints: the first row is [1, 1, 1, 1, -1, 0, 1, 0, 2] and the second is [2, 1, -1, -1, 0, -1, 0, 1, 1]. He then calculates the initial Zj - Cj row. For the artificial variables A1 and A2, the cost is M, so the Zj values are M and M respectively. The Cj values for A1 and A2 are M, so Zj - Cj is 0. For the slack variables s1 and s2, the cost is 0, so Zj is 0 and Zj - Cj is 0. For the decision variables, the Zj values are calculated as the sum of the product of the basic variable's cost and the column coefficient. For w1, Zj = 0*1 + 0*2 = 0, so Zj - Cj = 0 - 10 = -10. He repeats this for all variables, resulting in the Zj - Cj row: [-10, -6, -2, -1, 0, 0, 0, 0, 0]. He identifies the most negative value, -10, which corresponds to w1, as the entering variable.

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

    The instructor performs the minimum ratio test to determine the leaving variable. He divides the RHS by the coefficients of the entering variable w1. For the first row, 2 / 1 = 2. For the second row, 1 / 2 = 0.5. The minimum ratio is 0.5, so the second row is the pivot row, and A2 is the leaving variable. He then performs the pivot operation. The pivot element is 2. He divides the second row by 2 to make the pivot element 1, resulting in [1, 0.5, -0.5, -0.5, 0, -0.5, 0, 0.5, 0.5]. He then uses this new row to eliminate w1 from the other rows. For the first row, he subtracts the new row from it: [1, 1, 1, 1, -1, 0, 1, 0, 2] - [1, 0.5, -0.5, -0.5, 0, -0.5, 0, 0.5, 0.5] = [0, 0.5, 1.5, 1.5, -1, 0.5, 1, -0.5, 1.5]. For the Zj - Cj row, he adds 10 times the new row to it: [-10, -6, -2, -1, 0, 0, 0, 0, 0] + 10*[1, 0.5, -0.5, -0.5, 0, -0.5, 0, 0.5, 0.5] = [0, -1, -7, -6, 0, -5, 0, 5, 5]. The new Zj - Cj row is [0, -1, -7, -6, 0, -5, 0, 5, 5]. He identifies the most negative value, -7, which corresponds to w3, as the new entering variable.

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

    The instructor performs the minimum ratio test for the new entering variable w3. He divides the RHS by the coefficients of w3. For the first row, 1.5 / 1.5 = 1. For the second row, 0.5 / (-0.5) = -1. Since the ratio must be positive, only the first row is considered. The minimum ratio is 1, so the first row is the pivot row, and A1 is the leaving variable. He performs the pivot operation. The pivot element is 1.5. He divides the first row by 1.5 to make the pivot element 1, resulting in [0, 1/3, 1, 1, -2/3, 1/3, 2/3, -1/3, 1]. He then uses this new row to eliminate w3 from the other rows. For the second row, he adds 0.5 times the new row to it: [1, 0.5, -0.5, -0.5, 0, -0.5, 0, 0.5, 0.5] + 0.5*[0, 1/3, 1, 1, -2/3, 1/3, 2/3, -1/3, 1] = [1, 2/3, 0, 0, -1/3, -1/3, 1/3, 1/3, 1]. For the Zj - Cj row, he adds 7 times the new row to it: [0, -1, -7, -6, 0, -5, 0, 5, 5] + 7*[0, 1/3, 1, 1, -2/3, 1/3, 2/3, -1/3, 1] = [0, 4/3, 0, 1, -14/3, -8/3, 14/3, -2/3, 12]. The new Zj - Cj row is [0, 4/3, 0, 1, -14/3, -8/3, 14/3, -2/3, 12]. He identifies the most negative value, -14/3, which corresponds to s1, as the new entering variable.

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

    The instructor performs the minimum ratio test for the new entering variable s1. He divides the RHS by the coefficients of s1. For the first row, 1 / (-2/3) = -1.5. For the second row, 1 / (-1/3) = -3. Since both ratios are negative, there is no positive ratio, which indicates that the problem is unbounded. However, the instructor continues the process. He identifies the pivot element as -2/3 in the first row. He divides the first row by -2/3 to make the pivot element 1, resulting in [0, -1/2, -3/2, -3/2, 1, -1/2, -1, 1/2, -3/2]. He then uses this new row to eliminate s1 from the other rows. For the second row, he adds 1/3 times the new row to it: [1, 2/3, 0, 0, -1/3, -1/3, 1/3, 1/3, 1] + (1/3)*[0, -1/2, -3/2, -3/2, 1, -1/2, -1, 1/2, -3/2] = [1, 1/2, -1/2, -1/2, 0, -1/2, 2/3, 1/2, 1/2]. For the Zj - Cj row, he adds 14/3 times the new row to it: [0, 4/3, 0, 1, -14/3, -8/3, 14/3, -2/3, 12] + (14/3)*[0, -1/2, -3/2, -3/2, 1, -1/2, -1, 1/2, -3/2] = [0, -1/3, -7, -6, 0, -5, 0, 5, 5]. The new Zj - Cj row is [0, -1/3, -7, -6, 0, -5, 0, 5, 5]. The instructor then identifies the most negative value, -7, which corresponds to w3, as the entering variable. He performs the minimum ratio test again, and the process continues. The final solution is not reached in the video, but the instructor shows the final tableau with the optimal solution. The optimal solution is w1 = 0, w2 = 0, w3 = 1, w4 = 0, s1 = 0, s2 = 0, A1 = 0, A2 = 0, and the minimum value of Z is 2.

The video provides a comprehensive, step-by-step walkthrough of the Big M method for solving a linear programming problem. It begins with the formulation of the problem, highlighting the need for artificial variables to handle 'greater than or equal to' constraints. The instructor then systematically constructs the initial simplex tableau, carefully calculating the Zj - Cj row with the large penalty M. The core of the lesson is the iterative simplex process, where the instructor demonstrates the selection of entering and leaving variables using the minimum ratio test and performs the necessary row operations to pivot. The video illustrates the entire process of transforming the initial tableau into a final optimal tableau, showcasing the power of the simplex method to find the optimal solution to a complex optimization problem.