• Table of Contents

A Refreshing Example

Linear programming (LP) is a technique used in optimization to find the best solution to a problem given a set of constraints. The Brewer’s problem is a classic optimization problem in LP that deals with the allocation of limited resources to produce a range of products with different demands.

• The brewery has limited amount of resources — corn, hops, and barley malt.

  

• The recipes for ale and beer require different proportions of resources.

  

The goal is choose a mix of products to maximize profits. The problem can be formulated as a linear program with the following components:

1. Decision variables: We can define the number of barrels of ale and beer as $A$ and $B$, respectively.
2. Objective function: The goal is to maximize $13A + 23B$, which represents the profit from the sale of barrels.
3. Constraints: The production of ale and beer requires different resource ratios for their recipes.

   • The available amount of corn for the brewery is limited to $480$ lbs. Ale requires $5$ lbs of corn and beer requires $15$ lbs of corn:

     $$ 5A + 15B \leq 480 $$

   • The available amount of hops for the brewery is limited to $160$ lbs. Ale requires $4$ lbs of corn and beer requires $4$ lbs of corn:

     $$ 4A + 4B \leq 160 $$

   • The available amount of malt for the brewery is limited to $1190$ lbs. Ale requires $35$ lbs of corn and beer requires $20$ lbs of corn:

     $$ 35A + 20B \leq 1190 $$

   • And obviously, the number of barrels of ale and beer cannot be negative:

     $$ A, B \geq 0 $$

With these constraints and objective function, we can then solve it to find the optimal solution to the Brewer's problem.

Geometrical Interpretation

Plotting the constraint, we achieve the following graph. The shaded region is defined as the feasible region, which represents all possible combinations to the problem,

Figure 10.1a Feasible region.

However, we are interested in the most optimal, not just any solution. In LP, the optimal solution to a problem occurs at one of the extreme points — intersection of two constraint in 2D.

Figure 10.1b Extreme points.

To determine the optimal solution from the extreme points, we evaluate the objective function at each of the extreme points and select the one that gives the highest objective function value as the optimal solution.

Figure 10.1c Maximum profits.

As you can see, $A = 12$ and $B = 28$ provides the highest profits among extreme points.

Convexity