Primal to Dual Example

Duration: 8 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 lecture on Linear Programming, focusing on the concept of duality. The instructor begins by writing a standard minimization problem, Min z = x1 + 7x2, subject to constraints 5x1 + x2 ≥ 10 and x1 + x2 = 4. He then explains the process of finding the dual of this problem. The dual is formulated as a maximization problem, Max z = 10w1 + 4w2, with the objective function derived from the right-hand side of the primal constraints. The constraints of the dual are formed from the coefficients of the primal variables, resulting in -5w1 - w2 ≤ 1 and -w1 - w2 ≤ 7. The lecture also covers the transformation of the primal's equality constraint into two inequality constraints, which leads to the dual variables w1 and w2 being unrestricted in sign. The instructor uses the standard form of a linear program to demonstrate the general rules for constructing the dual, showing how the primal's matrix A, vector c, and vector b are used to define the dual's matrix A^T, vector b, and vector c. The video concludes with the final formulation of the dual problem, including the non-negativity and unrestricted conditions for the dual variables.

Chapters

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

    The video opens with a man writing on a whiteboard. The title 'Linear Programming Problem' is written at the top. He begins by writing the primal problem: 'Prob : Min z = x1 + 7x2' and 'Subject to the constraints: 5x1 + x2 ≥ 10'. He then writes the second constraint, 'x1 + x2 = 4', and labels it as the 'Solution'. The on-screen text clearly shows the initial formulation of the minimization problem.

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

    The instructor transitions to the dual problem. He writes 'Dual' and then 'Max z = c^T x' and 'Ax ≤ b' to represent the standard form of a maximization problem. He then writes the dual objective function as 'Max z = 10w1 + 4w2', where 10 and 4 are the right-hand side values from the primal constraints. He explains that the dual constraints are formed from the coefficients of the primal variables, writing '-5w1 - w2 ≤ 1' and '-w1 - w2 ≤ 7'. He also notes that the equality constraint in the primal leads to unrestricted dual variables, writing 'w1, w2 unrestricted'.

  3. 5:00 – 8:29 05:00-08:29

    The instructor continues to formalize the dual problem. He writes the dual objective function as 'Min z = -Max z' and then 'Min z = -10w1 - 4w2'. He then writes the dual constraints in a boxed format: '-5w1 - w2 ≤ 1' and '-w1 - w2 ≤ 7'. He also writes the non-negativity condition for the dual variables as 'w1, w2 ≥ 0'. Finally, he writes the matrix A from the primal problem and its transpose A^T, showing the relationship between the primal and dual matrices. The final dual problem is presented as 'Min z = -10w1 - 4w2' subject to the constraints and w1, w2 ≥ 0.

The video provides a step-by-step derivation of the dual of a linear programming problem. It starts with a specific minimization problem and systematically applies the rules of duality. The instructor demonstrates how to convert the primal's objective function and constraints into the dual's objective function and constraints, using the coefficients and right-hand side values from the primal. The key insight is that the dual of a minimization problem is a maximization problem, and the constraints are derived from the primal's variables. The lecture also highlights the importance of the primal's constraint types (≥, =) in determining the sign of the dual variables, which is a crucial aspect of the duality theory.