Learning Outcomes

You will learn

• How to derive a bound on the optimal objective value

• How to reformulate the problem into a dual with a different interpretation

• Correspondence between the primal (original) and dual problems

Try it out visually!

Imagine you run a small bakery that makes two products: cakes ($x_1$) and cookies ($x_2$). Your goal is to maximize your daily profit. Cakes yield a profit of $3 each, and cookies yield $2 each. You are limited by the ingredients you have on hand: you have at most 4 units of flour and 5 units of sugar available each day. Each cake requires 1 unit of flour and 2 units of sugar, while each cookie requires 1 unit of flour and 1 unit of sugar. We can write this scenario as a linear program:

Here, $x_1$ is the number of cakes you bake, and $x_2$ is the number of cookies. The constraints limit how many of each product you can produce given your resources.

Now, suppose a friend is not sure that you are telling the truth about the maximum profit you can make. They ask, “Can you prove an upper bound on how much money you could possibly earn with these ingredient constraints, without actually solving the problem?”

Consider the constraints in the problem. Each one puts a cap on how large the combination of $x_1$ and $x_2$ can be. If we think of them separately:

• The flour constraint: $x_1+x_2\le 4$.

• The sugar constraint: $2x_1+x_2\le 5$.

Now, what if we take some nonnegative multipliers $y_1$ and $y_2$ and combine these inequalities into one single inequality? For instance, multiply the flour constraint by $y_1\ge 0$ and the sugar constraint by $y_2\ge 0$ and add them up:

Grouping the terms by $x_1$ and $x_2$ gives:

If we choose $y_1$ and $y_2$ cleverly, we can force the left-hand side to be an expression that is always at least as large as our profit function $3x_1+2x_2$. Specifically, we want

Why? Because if the coefficients on $x_1$ and $x_2$ in our combined inequality dominate those in our profit function, then the upper bound on the combined inequality’s right-hand side ($4y_1+5y_2$) will also serve as an upper bound on the profit $3x_1+2x_2$. This ensures:

Thus, by choosing $y_1$ and $y_2$, we obtain a valid upper bound on the maximum profit. If we try to minimize $4y_1+5y_2$ over all $y_1,y_2\ge 0$ that satisfy these inequalities, we find the best (smallest) upper bound on our original problem.

Learning Checkpoint 11.1.1

In the bakery problem, take multipliers $y_1=3$ and $y_2=0$. Verify that this choice satisfies both dominance conditions, and compute the resulting upper bound on profit. Then compare it with the bound from $y_1=1,y_2=1$. Which certificate is better? Can you find one better still?

We started with the primal problem in a general form:

Each constraint $a^i\cdot x\le b_i$ (where $a^i$ is the $i$-th row of $A$) is valid for all feasible $x$. If we take a nonnegative combination of these constraints, say with multipliers $y_i\ge 0$, we get:

This can be written as:

If we choose $y$ such that ${\sum }_{i=1}^m{y}_i{a}^i\ge c$, then for all feasible $x$ (since $x\ge 0$):

So, $b^{\top }y={\sum }_{i=1}^m{y}_i{b}_i$ is an upper bound on the maximum primal objective value. By minimizing over all such $y$, we seek the tightest upper bound:

This is the dual problem. In our bakery scenario, this dual formulation corresponds to adjusting the prices (the $y$ values can be thought of as “shadow prices”) you would assign to each ingredient such that if you charge yourself for using these ingredients at these shadow prices, you end up with the smallest possible “bill” that still always surpasses or equals your maximum possible profit. The Strong Duality Theorem ensures that the optimal primal value equals the optimal dual value. This is precisely the rival baker’s problem from the start of the chapter: the constraints $A^{\top }y\ge c$ say the offer must beat baking, product by product, and the objective $\min b^{\top }y$ is the rival shopping for the cheapest offer that still convinces you.

From the above reasoning, we have shown that if $x$ is feasible for the primal and $y$ is feasible for the dual, then $c^{\top }x\le b^{\top }y$. In other words, the value of any feasible primal solution is always bounded above by the value of any feasible dual solution. This inequality is called weak duality; we state it as a theorem in the next section.

Weak duality is not specific to linear programming; the same kind of bound appears in many other classes of optimization problems. In the special case of linear programs (and certain other problem classes), we can say even more: there exist optimal solutions for both problems whose objective values match. This result is known as the Strong Duality Theorem.

Learning Outcomes

• Learn the two most important theorems in Linear Programming!!!

Consider the following pair of linear programs, known as a primal-dual pair. The primal problem (P) has $n$ decision variables and $m$ constraints, while the dual problem (D) has $m$ decision variables and $n$ constraints.

From weak duality, we know that for any feasible $x$ in (P) and any feasible $y$ in (D), it holds that:

Theorem 11.1: Weak Duality

For any feasible solution $x$ of the primal problem (P) and any feasible solution $y$ of the dual problem (D),

Theorem 11.2: Strong Duality

For a primal-dual pair of linear programs:

the following cases hold:

1.

If (P) is unbounded, then (D) must be infeasible.

2.

If (D) is unbounded, then (P) must be infeasible.

3.

If both (P) and (D) have feasible solutions and are bounded, then both have optimal solutions $x^{\ast }$ and $y^{\ast }$ respectively, and

$$c^{\top }{x}^{\ast }=b^{\top }{y}^{\ast }.$$

Example 11.3: Dual Infeasibility from Primal Unboundedness

Consider the following linear program:

Definition 11.4: Shadow Price

The shadow price of a constraint in a linear program tells us how much the optimal objective value would change if we slightly increased the right-hand side of that constraint by one unit, while keeping everything else fixed.

In a maximization problem, a shadow price represents the increase in value per additional unit of a scarce resource. In a minimization problem, it represents the decrease in cost.

Interpretation: If a constraint represents the availability of a resource (e.g., time, material), then its shadow price reflects the marginal value of that resource: how much the objective would improve if you had one more unit of it.

Mathematically: If the constraint $a_i^{\top }x\le b_i$ has corresponding dual variable $y_i^{\ast }$, then:

where $z^{\ast }$ is the optimal value of the objective function.

Example 11.5: The Bakery Revisited

Consider the primal problem:

The dual problem is:

If the optimal dual solution is $y_1^{\ast }=1,y_2^{\ast }=1$, then:

• The shadow price of flour is 1: each extra unit of flour increases profit by $1.

• The shadow price of sugar is 1: each extra unit of sugar increases profit by $1.

Example 11.6: A Larger Example: Bakery 2.0

The primal problem describes a bakery optimizing the production of cakes, cookies, and muffins to maximize profit. The constraints represent limited resources: flour, sugar, and baking time. The dual problem attaches a shadow price to each of these resources, reflecting their marginal value.

Primal Problem:

Optimal Primal Solution:

Dual Problem:

Optimal Dual Solution:

• $y_1=0$: The shadow price of flour is $0. This implies the flour constraint is non-binding: the bakery is not using all 40 kg of flour. Increasing flour supply would not increase profit.

• $y_2=50$: The shadow price of sugar is $50. Each additional kilogram of sugar allows the bakery to increase profit by $50. The sugar constraint is binding.

• $y_3=40$: The shadow price of baking time is $40 per hour. Baking time is fully used and limits production. Gaining one more hour would allow an increase in profit by $40.

From the primal solution:

• The flour constraint is not tight  $\Rightarrow$  $y_1=0$

• The sugar constraint is tight  $\Rightarrow$  $y_2>0$

• The baking time constraint is tight  $\Rightarrow$  $y_3>0$

These relationships satisfy the complementary slackness conditions:

Sensitivity Analysis: Marginal Value of Resources Assuming the current basis remains optimal, the increase in maximum profit from one additional unit of:

• Flour = $0

• Sugar = $50

• Baking Time = $40

The dual solution not only validates the primal objective value (via strong duality), but also assigns economic meaning to each constraint. Shadow prices tell you how much you would be willing to pay for more of each resource, a foundational concept in operations, pricing, and planning.

• The constraint is binding (i.e., tight) at the optimal solution.

• The problem satisfies strong duality (which always holds for feasible and bounded linear programs).

• The right-hand side is perturbed slightly (local sensitivity).

If a constraint is not tight, then its shadow price is 0: the resource is not limiting the optimal solution.

• The objective function is the total value of resources, priced at shadow prices.

• The constraints ensure that no activity in the primal makes more profit than it costs, when inputs are valued at shadow prices.

This ensures equilibrium: no profitable arbitrage is possible, and every unit of constrained resource is priced at its true marginal value.

Summary of Shadow Price Properties:

• A shadow price represents how much you would pay for an extra unit of a constrained resource.

• It is equal to the dual variable corresponding to the constraint.

• It reflects the marginal value of relaxing that constraint.

• Shadow prices are only nonzero for binding constraints.

• If a resource is fully used and limits optimality, its shadow price is positive.

• If a resource is unused or abundant, its shadow price is zero.

The form of a dual problem depends on the primal’s objective (maximize or minimize), inequality directions, and sign constraints on variables. Rather than memorizing a separate rule for every combination, it helps to see a few representative primal–dual pairs side by side and notice the pattern: constraint types in one problem control variable signs in the other, and vice versa. We walk through four common cases below.

• If a primal variable $x_j$ is unrestricted (free), the corresponding dual constraint is an equality.

• If $x_j\le 0$, the dual constraint becomes $\le$ instead of $\ge$.

• If a primal constraint $a_i^{\top }x\le b_i$ is changed to $\ge b_i$, then the sign constraint on the corresponding dual variable $y_i$ flips.

This shows how each component in the primal affects the dual, in particular how inequality direction and sign restrictions control the dual variable domain and constraint form.

Learning Checkpoint 11.3.1

Without writing out a full derivation, predict the form of the dual of

Is the dual a maximization or minimization? Are the dual variables sign-restricted or free? Are the dual constraints inequalities or equalities?

Let us now consider a variation of our previous derivation of the dual problem. This time, our primal problem (P) will have equality constraints rather than inequalities, and all variables will remain nonnegative. For example, consider the following linear program with $m=2$ equality constraints and $n=4$ variables:

In matrix form, if we let

our primal problem is:

Previously, when we had inequalities, we formed upper bounds on the objective by taking nonnegative linear combinations of the constraints. Now, since we have equalities, we are free to choose any real multipliers for these constraints (positive, negative, or zero), and the resulting combination will still hold as an equality. This is because any scalar multiple of an equation remains a valid equation.

Let $y_1$ and $y_2$ be arbitrary real numbers, and form the linear combination:

Adding these together gives:

Collecting terms by variable:

Since $x\ge 0$, if we want the left-hand side to serve as an upper bound on our objective function $2x_1+3x_2-x_3+x_4$ for all feasible $x$, we need the coefficients of each $x_j$ in the combined inequality to dominate those in the objective. Specifically, we want:

If these inequalities hold, then for every feasible $x$:

Thus, $10y_1+5y_2$ is an upper bound on the maximal value of $2x_1+3x_2-x_3+x_4$. Since $y_1$ and $y_2$ are unrestricted in sign, we can try to minimize $10y_1+5y_2$ subject to ensuring these dominance conditions.

In the general setting with equality constraints and nonnegative primal variables, the dual variables associated with these equality constraints are free (they can be positive, negative, or zero). The process we followed above leads us to the dual problem:

subject to the condition that $A^{\top }y\ge c$, i.e.:

In our numeric example, minimizing $10y_1+5y_2$ subject to these four inequalities gives the optimal dual solution $y^{\ast }=(2,1)$ with value $25$; the constraints coming from $x_2$ and $x_3$ are tight there, while the other two hold with strict inequality. More generally, the dual problem corresponding to

is

Example 11.7: Example with Inequalities and Free Variables

Now consider a primal problem with three inequality constraints and two free variables. Suppose:

Here, $x_1$ and $x_2$ can be positive or negative.

We can write this in a compact matrix form. Let:

Then (P) is:

To create a bound on $3x_1-2x_2$, we take nonnegative combinations of the constraints. Let $y_1,y_2,y_3\ge 0$ be the multipliers for the three constraints:

Combining like terms in $x_1$ and $x_2$:

We want this inequality to hold for all $x_1,x_2$ free. If $y_1+2y_2-y_3>3$, then by choosing $x_1$ large and positive, we could make the left side arbitrarily large, violating the bound. If $y_1+2y_2-y_3<3$, by choosing $x_1$ large and negative, we break the bound. The only way to always hold the inequality is to have exact equality:

Similarly, for $x_2$:

If $y_1-y_2+3y_3>-2$, we could send $x_2$ to $-\infty$ to break the bound. If $y_1-y_2+3y_3<-2$, we could send $x_2$ to $\infty$. Again, the only safe choice is equality:

Thus, the dual constraints must be equalities. The dual problem is:

From our derivation, the dual problem (D) becomes:

subject to:

and

Summarizing, we have

Here we see the pattern: having $x$ free in the primal forces the dual constraints to be equalities. In summary:

• Primal inequalities with $x$ free $\Rightarrow$ Dual equality constraints.

• Primal equalities with $x\ge 0$ $\Rightarrow$ Dual inequalities and $y$ free.

These relationships ensure that by choosing appropriate dual multipliers, we can always create a valid bound on the primal objective.

The following table can help remember the above.

Consider the following primal linear program:

To derive the dual, we introduce a dual variable for each constraint:

• Let $y_1$ be the dual variable for the equality constraint $x_1+x_2=2$

• Let $y_2$ be the dual variable for the $\ge$ constraint $2x_1-x_2\ge 3$

• Let $y_3$ be the dual variable for the $\le$ constraint $x_1-x_2\le 1$

Explanation of Dual Structure:

• The primal has one equality constraint. Therefore, the corresponding dual variable $y_1$ is unrestricted in sign.

• The second primal constraint is a $\ge$ inequality in a maximization problem, so its corresponding dual variable $y_2$ must be $\le 0$: only a nonpositive multiplier turns a $\ge$ constraint into a valid $\le$ ingredient of an upper bound.

• The third primal constraint is a $\le$ inequality, so its corresponding dual variable $y_3$ must be $\ge 0$.

• The dual constraints come from the coefficients of the primal variables. Since the primal is a maximization, the dual constraints are $\ge$.

• The dual objective coefficients come from the right-hand sides of the primal constraints: $2,3,1$.

Summary: This example demonstrates how mixed constraint types in the primal ($=,\ge ,\le$) lead to a dual with mixed variable sign restrictions. The primal variable bounds also affect whether dual constraints are inequalities or equalities. You need these mappings to construct dual problems correctly.

Consider the following primal linear program:

We now derive the dual using the aggregation method.

Step 1: Multiply constraints by dual variables.

We introduce dual variables $y_1,y_2,y_3$ corresponding to constraints 1, 2, and 3, respectively.

We aggregate the constraints by forming a linear combination:

Before combining, we must ensure every term contributes a valid $\le$ inequality, because we’re maximizing in the primal and want an upper bound. So:

- Equality constraint: any multiplier is fine, so $y_1\in ℝ$ - $\ge$ constraint: multiply by $y_2\le 0$ (a nonpositive multiplier flips $\ge$ to $\le$) - $\le$ constraint: multiply by $y_3\ge 0$ (a nonnegative multiplier preserves $\le$)

Now aggregate:

And the aggregated right-hand side is:

So the aggregated constraint is:

Step 2: Ensure this constraint dominates the primal objective.

To upper-bound the primal objective $2x_1+x_2$, we want:

Since $x_1\ge 0$, domination in the $x_1$ coordinate means the aggregated coefficient must be at least $2$. Since $x_2$ is free, its aggregated coefficient must match the objective coefficient exactly (otherwise a large positive or negative $x_2$ breaks the bound):

Step 3: Formulate the dual.

The dual objective is the right-hand side of the aggregated constraint:

With constraints:

Conclusion:

This derivation shows how:

• Constraint direction in the primal determines the sign of the corresponding dual variable.

• Sign of a primal variable (e.g., $x_1\ge 0$) determines the direction of the dual constraint: to ensure domination for non-negative variables, we require the dual combination to be $\ge$ the primal coefficients.

• The dual objective comes from aggregating the right-hand sides, weighted by the dual variables.

This example illustrates how careful sign and inequality management gives rise to a valid dual that bounds the primal objective from above.

Question: What happens if variable $x_1$ instead was constrained as $x_1\le 0$?

Exercise 11.8: The Dual of a Small Bakery

$\star$  A bakery sells loaves ($x_1$, profit $5 each) and rolls ($x_2$, profit $4 each), using at most 12 units of flour and 5 units of sugar:

1.

Write the dual linear program, introducing one dual variable per resource.

2.

Interpret each dual variable as a price per unit of its resource, as in the rival baker story: what do the two dual constraints say about loaves and rolls?

3.

Which primal data become the dual objective coefficients, and which become the dual right-hand sides?

Exercise 11.9: Formulate the Dual

$\star$  Write the dual of the following linear program:

Exercise 11.10: Verifying Weak Duality

Exercise 11.11: Weak Duality Bound

$\star \star$  Consider the primal LP:

1.

Write the dual problem.

2.

Verify that $y=(1,1)$ is feasible for the dual. Compute the dual objective value $b^{\top }y$.

3.

Verify that $x=(2,2)$ is feasible for the primal. Compute the primal objective value $c^{\top }x$.

4.

Use weak duality to explain why the optimal value of the primal must lie between these two values.

Exercise 11.12: Dual with Mixed Constraints

$\star \star$  Formulate the dual of the following LP:

Identify the sign restrictions on each dual variable and whether each dual constraint is an inequality or an equality.