Tutorials › Calculus III › Production Planning Under An Emissions Cap

Home  /  Tutorials  /  Applied Multivariable Optimization

Applied Multivariable Optimization · Tutorial 488 of 999

Production Planning Under An Emissions Cap

Learn how resource and emissions caps jointly shape a two-product profit-maximizing production plan, including how to check whether one or both limits bind.

Advanced 11 min read

What You'll Learn

  • Formulate production quantities, profit, resource use, and emissions as an optimization model.
  • Distinguish binding constraints from slack constraints and check feasibility.
  • Find stationary candidates along individual caps and at their intersection.
  • Compare plans when only a resource cap or only an emissions cap binds.
  • Verify a global maximum using concavity and nonnegative constraint multipliers.

Planning Production Under Two Limits

A manufacturer may be able to sell more than it can responsibly or practically produce. Production uses limited resources, such as machine time or raw material, and may also generate emissions subject to a regulatory cap. The best plan must therefore balance profit against both limits.

The important point is that a limit is an inequality, not an instruction to use the entire allowance. A cap may be binding, meaning that the best plan uses all of it, or slack, meaning that the best plan leaves some allowance unused. Which situation occurs depends on the profit function and on how each product uses resources and produces emissions.

We will model two nonnegative production quantities and compare candidate plans. The examples use concave quadratic profit functions, for which a first-order certificate can verify that a feasible candidate is globally optimal.

Model and Key Terms

Let \(x\) and \(y\) denote the quantities produced of products \(X\) and \(Y\). Let \(\pi(x,y)\) be the profit. Suppose each unit of product \(X\) uses \(a_1\) units of a shared resource and produces \(e_1\) units of emissions; product \(Y\) has corresponding coefficients \(a_2\) and \(e_2\). If the available resource is \(R\) and the emissions cap is \(E\), the model is

$$ \begin{aligned} \text{maximize}\quad & \pi(x,y)\\ \text{subject to}\quad & a_1x+a_2y\le R,\\ & e_1x+e_2y\le E,\\ & x\ge 0,\qquad y\ge 0. \end{aligned} $$
Definition: A production plan is feasible if it satisfies every resource, emissions, and nonnegativity constraint. A constraint is binding at a plan if equality holds; it is slack if the inequality is strict.

For example, the resource constraint is binding when \(a_1x+a_2y=R\), and slack when \(a_1x+a_2y<R\). A plan that violates even one cap is not a candidate for the constrained maximum, no matter how large its profit would be without that cap.

When the feasible region is closed and bounded and profit is continuous, a maximum exists. With two products and linear caps, the feasible region is a polygon in the \(xy\)-plane. Possible locations for a maximum include an unconstrained stationary point inside the region, a stationary point along a single boundary, an intersection of boundaries, or an endpoint such as an axis intercept. Each candidate must be checked against all the constraints.

A Certificate for a Candidate Maximum

A useful way to verify a proposed plan is to use concavity. A differentiable function is concave if its graph lies below each of its tangent planes. For a concave profit function \(\pi\), this gives, for any candidate \(q=(x_*,y_*)\) and any plan \(z=(x,y)\),

$$ \pi(z)\le \pi(q)+\nabla\pi(q)\mathbin{\cdot}(z-q). $$

Suppose the resource and emissions constraints have coefficient vectors \(\mathbf{a}=(a_1,a_2)\) and \(\mathbf{e}=(e_1,e_2)\). If \(q\) is feasible and its gradient can be written as a nonnegative combination of the normals of its binding caps, then every feasible displacement from \(q\) has nonpositive directional contribution to the tangent plane. This proves that no feasible plan has higher profit.

Theorem: Suppose \(\pi\) is differentiable and concave, \(q\) is feasible, and \[ \nabla\pi(q)=\lambda\mathbf{a}+\mu\mathbf{e} \] for \(\lambda,\mu\ge 0\), where any positive multiplier is attached to a constraint binding at \(q\). Then \(q\) maximizes profit over the feasible region. If \(\pi\) is strictly concave, that maximum is unique.

To see why, take any feasible \(z=(x,y)\). For each binding resource constraint, \(\mathbf{a}\cdot(z-q)\le 0\), because \(z\) cannot use more resource than the cap. Similarly, for a binding emissions constraint, \(\mathbf{e}\cdot(z-q)\le 0\). Therefore,

$$ \begin{aligned} \pi(z) &\le \pi(q)+\nabla\pi(q)\cdot(z-q)\\ &= \pi(q)+\lambda\mathbf{a}\cdot(z-q)+\mu\mathbf{e}\cdot(z-q)\\ &\le \pi(q). \end{aligned} $$

Nonnegative multipliers matter: they ensure that tightening a constraint cannot make the final inequality point in the wrong direction. This is a sufficient global-optimality check; it does not replace checking feasibility, and it does not say that every candidate found by an equality calculation is feasible or optimal.

Worked Example: Both Caps Bind

Worked Example: Both Caps Bind

Suppose quantities \(x\) and \(y\) are measured in batches, and profit is measured in thousands of dollars. The profit function and caps are

$$ \pi(x,y)=30x+24y-x^2-y^2,\qquad 2x+y\le 16,\qquad x+2y\le 14,\qquad x,y\ge 0. $$

First find where the two caps intersect. Solve \(2x+y=16\) and \(x+2y=14\). From the first equation, \(y=16-2x\). Substitution into the second gives \(x+2(16-2x)=14\), so \(x+32-4x=14\), \(-3x=-18\), and \(x=6\). Then \(y=16-2(6)=4\). The intersection is \((6,4)\), which is feasible and makes both caps binding.

Its profit is \(30(6)+24(4)-6^2-4^2=180+96-36-16=224\) thousand dollars. To verify that this is the global maximum, differentiate: \(\nabla\pi(x,y)=(30-2x,24-2y)\). At \((6,4)\), the gradient is \((18,16)\). Write it as a combination of the cap normals \((2,1)\) and \((1,2)\): \(2\lambda+\mu=18\) and \(\lambda+2\mu=16\). Subtracting the equations after solving gives \(\lambda=20/3\) and \(\mu=14/3\); both are positive.

Thus the gradient is \((20/3)(2,1)+(14/3)(1,2)\). The profit function is strictly concave because its second-derivative matrix is \(\begin{pmatrix}-2&0\\0&-2\end{pmatrix}\), which is negative definite. The certificate above proves that \((6,4)\) is the unique global maximum.

As a feasibility check, resource use is \(2(6)+4=16\), and emissions are \(6+2(4)=14\): each equals its cap. The plan therefore uses exactly the available resource and exactly the permitted emissions.

Worked Example: Only the Resource Cap Binds

Worked Example: Only the Resource Cap Binds

Keep the same profit function and resource limit, but raise the emissions cap to \(30\):

$$ \pi(x,y)=30x+24y-x^2-y^2,\qquad 2x+y\le 16,\qquad x+2y\le 30,\qquad x,y\ge 0. $$

On the resource boundary, \(y=16-2x\). Substitute this into profit:

$$ \begin{aligned} \pi(x,16-2x) &=30x+24(16-2x)-x^2-(16-2x)^2\\ &=30x+384-48x-x^2-(256-64x+4x^2)\\ &=-5x^2+46x+128. \end{aligned} $$

The derivative along this boundary is \(-10x+46\). Setting it equal to zero gives \(x=46/10=23/5\), and hence \(y=16-2(23/5)=34/5\). The candidate is \((23/5,34/5)\), or \((4.6,6.8)\).

Check both caps: resource use is \(2(4.6)+6.8=16\), while emissions are \(4.6+2(6.8)=18.2\le 30\). The resource cap binds and the emissions cap is slack. Profit is \(30(4.6)+24(6.8)-(4.6)^2-(6.8)^2=138+163.2-21.16-46.24=233.8\) thousand dollars.

For a global check, the gradient at the candidate is \((30-9.2,24-13.6)=(20.8,10.4)\). This equals \(10.4(2,1)\), a positive multiple of the resource normal. Since the resource cap binds and the profit function is strictly concave, the candidate is the unique global maximum over the feasible region. The emissions cap is not used up simply because it exists; it is slack at the best plan.

Worked Example: Only the Emissions Cap Binds

Worked Example: Only the Emissions Cap Binds

Now let the emissions cap be \(14\) and raise the resource limit to \(30\):

$$ \pi(x,y)=30x+24y-x^2-y^2,\qquad 2x+y\le 30,\qquad x+2y\le 14,\qquad x,y\ge 0. $$

On the emissions boundary, \(y=(14-x)/2=7-x/2\). Substitute:

$$ \begin{aligned} \pi(x,7-x/2) &=30x+24(7-x/2)-x^2-(7-x/2)^2\\ &=30x+168-12x-x^2-(49-7x+x^2/4)\\ &=119+25x-\frac54x^2. \end{aligned} $$

The derivative is \(25-\frac52x\), so the stationary point has \(x=10\), and \(y=7-10/2=2\). Resource use is \(2(10)+2=22\le 30\), while emissions are \(10+2(2)=14\). Thus only the emissions cap binds. Profit is \(30(10)+24(2)-10^2-2^2=300+48-100-4=244\) thousand dollars.

The gradient at \((10,2)\) is \((30-20,24-4)=(10,20)=10(1,2)\), a positive multiple of the emissions normal. Strict concavity and the global certificate show that this feasible plan is the unique maximum. This calculation also checks the boundary derivative: along the emissions boundary, the derivative of profit is zero at \(x=10\).

How to Compare Candidate Plans

The examples show why an equality calculation is only one part of constrained optimization. An optimizer found on a boundary must still satisfy every other inequality. If a resource-boundary candidate exceeds the emissions cap, it cannot be selected; the best feasible plan may instead lie at the intersection of the caps. Conversely, a candidate may use all of one allowance while leaving the other partly unused.

1
Identify the model.
Write profit, both caps, and nonnegativity constraints with consistent units.
2
Find plausible locations.
Check an interior stationary point, stationary points along individual boundaries, intersections, and relevant endpoints.
3
Test feasibility.
Substitute each candidate into every inequality. Discard any candidate that violates a cap or nonnegativity.
4
Compare or certify.
Compare profits among feasible candidates, or use concavity and nonnegative multipliers to establish a global maximum.

For a strictly concave profit function on a convex feasible region, there can be at most one maximizer. The multiplier certificate is particularly efficient when the candidate and its binding constraints are already known. If the certificate does not apply, that does not prove the candidate is wrong; it means the certificate has not verified it, so other candidates and boundary cases must be examined.

A Common Mistake: Treating Every Cap as an Equality

A frequent error is to impose both caps as equalities before checking whether both bind. In the resource-only example, solving \(2x+y=16\) together with \(x+2y=30\) would produce their intersection, even though the actual optimum has emissions \(18.2<30\). That intersection uses the entire emissions allowance without any reason to do so and is not the correct resource-boundary stationary point.

The reverse error is also possible: calculating a stationary point on one boundary and accepting it without testing the other cap. In the first example, the resource-only boundary candidate \((4.6,6.8)\) has emissions \(4.6+2(6.8)=18.2\), which exceeds the cap of \(14\). It is infeasible, so its boundary profit cannot be used as the constrained maximum. Always distinguish a candidate calculation from a feasibility check.

Check Your Understanding

Use the definitions and methods in this tutorial to answer the following questions.

  1. In the resource-only example, which cap is binding, and how can you verify the other cap is slack?
  2. Why must a stationary point found along one cap be checked against the other cap?
  3. For a concave profit function, what does a nonnegative combination of binding constraint normals tell you about feasible directions from a candidate?
  4. Suppose a proposed production plan exceeds the emissions cap but has greater profit than every feasible candidate checked so far. Can it be the constrained maximum? Explain.
  5. In the both-binding example, verify the cap intersection by substituting \((6,4)\) into each constraint.

Previous

Next

Back to Tutorials