7.10. Dual Problem in Linear Programming

It turns out that fortunately this is not a coincidence, it turns out you can always construct such a combination. So, if I have my constraints C 1, C 2, so these are my constraint equations, I can always find some combination. So, I can take some lambda 1 C 1, lambda 2 C 2, I can add these up and then I can get from that some upper bound and that upper bound will actually tell me, whether not the solution I found is correct.

In linear programming, we can discover a dual problem associated with any linear programming problem. This dual problem is constructed using the original constraints of the problem. For each constraint in the original problem, there is a corresponding variable in the dual problem. We can combine these constraints using specific multipliers (denoted as lambda) to derive an upper bound. Understanding this relationship helps us verify whether the solution we obtained for the original problem is correct.

Think of a company minimizing costs while maximizing profits. If they have a budget (constraint), they can explore different combinations of marketing strategies (dual variables) to maximize their outreach. By examining how these strategies affect their budget, the company can ensure they are making optimal decisions.

This is called the dual of the LP and again we are not going to look into the theory of this, but this is useful to know that we can take the formulation that we start with for LP and then we can ask another question which is what is the minimum value that we can get by combining the constraints with some linear multipliers.

The dual problem seeks to minimize the value obtained from a combination of the original constraints using the lambdas mentioned earlier. These lambda variables serve as multipliers that adjust how much weight each constraint contributes to the overall evaluation. The formulation of duality provides a different angle to understand the same problem, revealing the minimum limits imposed by constraints, thus allowing us to check the validity of the original maximization scenario.

Consider a school planning to minimize costs through various fundraising options. Each option has a different potential to generate funds (constraints). By evaluating how each fundraising option affects their overall funds, they essentially establish a dual plan that ensures they do not overspend.

So, we get new variables which are exactly this multiplier. What are the values of lambda 1 to lambda k which minimize the combination lambda 1 C 1 plus lambda 2 C 2 plus lambda k C k? So, this is my new question, I want to minimize this and then this becomes another LP problem and I solve that in terms of that the dual and the original have a solution if and only if that solution is the optimum for both.

The variables in the dual problem, which are derived from the original constraints, allow us to formulate a new linear programming problem focused on minimization. The key aspect here is that if we find a solution to both the dual and original problems, they will confirm each other's optimality, establishing a powerful connection between the two. This means that solving one effectively helps us solve the other, reinforcing the validity of our results.

Imagine a bakery that wants to optimize production amounts of different goods (original problem). Meanwhile, they're also examining costs associated with ingredients, which can be viewed as a dual problem. An optimal production schedule will not only give the best output but will also directly influence how they manage costs effectively, demonstrating the interconnectedness of their decision variables.

--