Lesson 8

A similar effect exists in the maximum flow problem (which can be used to find matchings in a bipartite graph): when the maximum flow is found, a proof of its maximality can be quickly constructed. Finally, in the more general problem of linear programming, it is required to find the optimal value of a linear function under linear constraints on the variables. The duality theorem guarantees that coefficients can always be found with which the original constraints can be combined to prove that the found value is indeed optimal.