## How Do You Minimize Brewery Costs Under Some Constraints?

Let’s look at another example of writing out a standard minimization problem. This is a question about minimizing the costs at a brewery that produces regular and light beer. It goes something like this…

A brewery produces two types of beer. One beer is a regular beer with a typical number of calories. The other beer is a light beer containing a lower number of calories per serving. Steady customers of the brewery buy 10 units of regular beer and 15 units of light beer per month. The brewery wishes to produce extra beer beyond that which steady customers demand. The cost per unit of regular beer is 32,000 dollars and the cost per unit of light beer is 50,000 dollars. Every unit of regular beer brings in 120,000 dollars in revenue and every unit of light beer brings in 300,000 dollars in revenue. The brewery wants at least 9,000,000 dollars in revenue. At least 20 additional units of beer can be sold.

How much beer of each type must be sold to minimize production costs?

To begin a problem like this, define the independent variables:

R: units of regular beer

L: units of light beer

Once the variables are established, let’s write out the objective function that must be minimized. We are minimizing production costs and the pertinent info in the problem is

The cost per unit of regular beer is 32,000 dollars and the cost per unit of light beer is 50,000 dollars.

It is easiest to work in thousands of dollars and to write the objective function as

C = 32R + 50L

There are two constraints on production. First of all, the brewery needs at least 9,000,000 dollars (9000 thousand dollars). The corresponding revenue data in the problem is

Every unit of regular beer brings in 120,000 dollars in revenue and every unit of light beer brings in 300,000 dollars in revenue.

The revenue (in thousands of dollars from R units of regular beer is 120R and from L units of light beer is 300L. This means

120R + 300L ≥ 9000

The second constraint has to do with the fact that “at least 20 additional units of beer can be sold.” If steady customers require 10 units of regular beer and the brewery produces R units total, the additional amount produced is R – 10. Similarly, the additional amount of light beer produced is L – 15. So the constraint for additional units is

R – 10 + L – 15 ≥ 20

Isolating R and L on the left side gives

R + L ≥ 45

Let’s put all of this together in a standard minimization problem:

Minimize C = 32R + 50L subject to

120R + 300L ≥ 9000

R + L ≥ 45

R ≥ 0, L ≥ 0

The last constraints are need since the amounts of beer produced can’t be negative.

With this standard minimization problem in hand, we can now apply the simplex method to find the solution. Using this technique, we find that the minimum cost is 1800 thousand dollars (1,800,000 dollars) and occurs when 25 units of regular beer and 20 units of light beer are produced.

## How Do You Solve A Standard Minimization Problem?

In an earlier FAQ, we wrote out a standard minimization problem from an application. Now we’ll solve that problem by finding the dual standard maximization problem and applying the Simplex Method.

This process is covered in Section 4.4 of the textbook. For complete details on the process, consult this section and the many examples contained in this section. I will assume that you have looked over this section and are familiar with carrying out row operations on a matrix.

The problem we will solve is

Minimize C = 16y1 + 14y2 + 12y3 subject to

y1 + y2 + y3 > 6000

2y2 – 3y3 > 0

3y1y2y3 > 0

y1 > 0, y2 > 0, y3 > 0

Solution Write out the dual problem and apply the Simplex Method. Start by entering the objective function and constraints into a matrix. The transpose of this matrix yields the form of the dual standard maximization problem.

The dual problem is

Maximize z = 6000x1 subject to

x1 + 3x3 < 16

x1 + 2x2x3 < 14

x1 – 3x2x3 < 12

x1  > 0, x2 > 0, x3 > 0

Now add the slack variables to each constraint and form the initial matrix for the Simplex Method.

The pivot column is the first column since that is where the indicator row is most negative. The pivot row is the third row. The entry in the pivot is already a zero so we simply need to put zeros in the rest of the column using row operations.

For this new matrix, the pivot is the 5 in the second row, second column. Change the pivot to a 1 and then use it to put zeros in the rest of the column. This results in

Since there is still a negative number in the indicator row, we continue applying the Simplex Method. In this step, the pivot is the 4 in the first row, third column. As before, this entry is changed to a 1 and used to make the rest of the column into zeros.

The indicator row does not contain any negatives numbers so this is the final matrix. The solution to the standard minimization problem is under the slack variables and indicate that

y1 = 1500, y2 = 2700, and y3 = 1800

with a corresponding minimum of C = 83400 cents or \$834.

## How Do You Write Out A Standard Minimization Problem?

Let’s take a look at a problem that requires a bit of ingenuity to put into standard minimization form.

Problem – Garton’s Seeds has a seed mixture containing three types of seeds: bluegrass, rye, and Bermuda. The cost per pound of the three seeds are 16 cents, 14 cents and 12 cents. Bluegrass seed must be at least 25% of the each batch. The amount of Bermuda must be no more than 2/3 the amount of rye in each batch. To fill current orders, Garton’s must make at least 6000 lbs of the mixture. How many pounds of each seed should be in the batch so that the cost of the batch is minimized?

Solution Start by defining the variables to represent the seeds.

y1 – lbs of bluegrass in the mixture

y2 – lbs of rye in the mixture

y3 – lbs of Bermuda in the mixture

Since cost is to be minimized, let C be the cost of the mixture. We know the cost per pound on each type of seed. By multiplying the cost per pound times the number of pounds, we can find the cost of each type of seed. Adding the cost for each type gives

C = 16y1 + 14y2 + 12y3

where C is in cents.

Now let’s look at the constraints. The easiest one to recognize relates to the requirement that at least 6000 lbs of the mixture must be made. This means that the sum of the variables representing the total amount of the mixture is greater than or equal to 6000,

y1 + y2 + y3 > 6000

In this format the inequality fits the form needed for a standard minimization. In this format the variables appear linearly on the left side of the inequality and are greater than or equal to a nonnegative number. Each of the inequalities must have this form to apply the Simplex Method.

Since the amount of Bermuda must be no more than 2/3 the amount of rye in each batch, we can write

y3 < 2/3 y2

To put this in the proper format, subtract y3 from both sides and flip-flop the inequality to yield

2/3 y2y3 > 0

This has the proper format, but will be easier to deal with in the Simplex Method if there is no fraction. Multiply each term by 3 to give

2y2 – 3y3 > 0

The statement “Bluegrass seed must be at least 25% of the each batch” is a bit more difficult to interpret. On the surface, you might write

y1 > 0.25(6000)

thinking that 25% of the 6000 lb mixture must be bluegrass. But this would be incorrect since the batch will be at least 6000 lbs. Instead of 6000 lbs, write the total amount of the batch as y1 + y2 + y3. Now we can interpret the information as

y1 > 0.25(y1 + y2 + y3)

Remove the parentheses and move all of the terms to the left side of the inequality. This yields

0.75y1 – 0.25y2 – 0.25y3 > 0

We can make this a bit more palatable by multiplying each term by 4,

3y1y2y3 > 0

Adding the nonnegativity constraints give the standard minimization problem:

Minimize C = 16y1 + 14y2 + 12y3 subject to

y1 + y2 + y3 > 6000

2y2 – 3y3 > 0

3y1y2y3 > 0

y1 > 0, y2 > 0, y3 > 0

With the standard minimization problem established, we can now write out the dual problem and apply the Simplex Method.

## How Can You Use a Spreadsheet To Carry Out The Simplex Method?

The row operations in the Simplex algorithm are not difficult to compute.  To start, you should carry out the row operations in the process by hand. As you will quickly realize, the Simplex algorithm is tedious and prone to arithmetic errors. Once you get the idea behind how the Simplex method works, you can carry out the row operations in a spreadsheet.

In the video below, the steps in the Simplex Methods are carried out in Google Sheets. The same steps can also be carried out in other spreadsheets such as Microsoft Excel.

Please note that there is a typo in the original matrix in the process. The cell in D2 should be a 1 instead of a zero to account for the slack variable in the first constraint.