Section 4.2 Question 1

What is a linear programming problem?

Linear programming is a strategy for maximizing or minimizing a linear function of several variables. This function is called the objective function and takes the form

z = a1 x1 + a2 x2 + …+ axn

Although this equation may look imposing, we can break it down into a simple pattern. Each term on the right hand side consists of a constant called an multiplied by a decision variable xn. The names of the constants and variables are irrelevant, but the constant an always multiplies the decision variable xn raised to the first power. The decision variables are the variables that represent the quantities that may be varied. The variable z represents the quantity being maximized or minimized.

A linear programming problem consists of an objective function and a system of inequalities that defines acceptable values for the variables x1 through xn.

 Linear Programming Problem

A linear programming problem has the form

Maximize or Minimize z = a1 x1 + a2 x2 + …+ axn

subject to constraints of the form

b1 x1 + b2 x2 + …+ bxc or b1 x1 + b2 x2 + …+ bx≥ c

and x1 ≥ 0, x2 ≥ 0, …,  xn ≥ 0.

 

In a linear programming problem, the constants a1,…,an, b1,…,bn and c are real numbers.

The values of the decision variables that optimize (maximize or minimize) the value of the objective function are called the optimal solution of the linear programming problem.

Businesses typically try to either maximize profit or minimize cost by varying the values of the decision variables. With the addition of an objective function, the craft brewery problem can be written as a linear programming problem. Suppose that each barrel of pale ale yields $100 of profit and each barrel of porter yields $80 of profit. We can multiply the profit per barrel times the number of barrels for each type of beer to get the profit for each type of beer. The profit from barrels x1 of pale ale is

4_2_1_01

and the profit from x2 barrels of porter is

4_2_1_02

The total profit P is the sum of the profit from each type of beer,

P = 100 x1 + 80 x2

Although this equation does not utilize z as a variable, it is the objective function for a craft brewery. The names of the variables are not important. We could just as easily used z instead of P or Q1 and Q2 instead of x1 and x2. The key ingredient of a linear objective function is that the decision variables are raised to the first power, multiplied by a constant and then added together.

With this objective function in hand, we can write out the linear programming problem for the craft brewery:

4_2_1_03

In the next question, we’ll examine how this problem can be solved using a graph of the solution of the system of inequalities.

Example 1      Find the Linear Programming Problem

Some breweries contract with other breweries to brew a portion of their annual output. By doing this, they avoid the high fixed costs associated with setting up and operating a brewing facility. One brewery, Patrick Henry Brewing, contracts with two other breweries to produce an American ale. It costs the brewery $100 per barrel to produce the beer at the first contract brewery and $125 per barrel to produce the beer at the second contract brewery. To satisfy orders from distributors, Patrick Henry Brewing must contract for a total of at least 10,000 barrels per month. In addition, the amount that is contracted from the second brewery must be at least 25% of the amount contracted from the first brewery. However, labor agreements require that the amount contracted from the second brewery cannot exceed the amount contracted from the first brewery.

Write out the linear programming problem for determining how many barrels should be produced from each contract brewer to ensure that the total cost is minimized?

Solution To begin, identify what we are trying to find and define variables to reflect the unknowns. Since Patrick Henry Brewing needs to know how many barrels of American ale to produce at each of the contract brewers, define the variables as follows:

Q1: Number of barrels produced at contract brewery 1

Q2: Number of barrels produced at contract brewery 2

Producing these quantities costs Patrick Henry Brewing $100 per barrel at brewery 1 and $125 per barrel at brewery 2. The cost to produce Q1 barrels at contract brewery 1 is

4_2_1_04

and the cost to produce Q2 barrels at contract brewery 2 is

4_2_1_05

The total cost C is the sum of the individual costs from each contract brewery,

C = 100Q1 + 125Q2

We want to minimize the total cost subject to any constraints on production.

The inequalities are signaled by phrases like “at least” and “cannot exceed”. First we note that the brewery must contract for at least 10,000 barrels per month. This means that in any month,

4_2_1_06

The phrase “at least” means that the total amount contracted must be greater than or equal to 10,000. Substituting the sum of the variables for the total amount contracted yields

Q1 + Q2 ≥ 10,000

Similarly, the amount contracted from brewery 2 must be at least 25% of the amount contracted from brewery 1 or

4_2_1_07

Since the amount contracted from the second brewery cannot exceed the amount contracted from the first brewery, we can also write

Q2 ≤ Q1

Putting the objective function together with the inequalities (including non-negativity constraints) gives the linear programming problem

4_2_1_08

The non-negativity constraints are needed since the number of barrels of beer from each contract brewery cannot be negative. We’ll find the solution to this linear programming problem in the next question.