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 + …+ an xn
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 + …+ an xn
subject to constraints of the form
b1 x1 + b2 x2 + …+ bn xn ≤ c or b1 x1 + b2 x2 + …+ bn xn ≥ 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
and the profit from x2 barrels of porter is
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:
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
and the cost to produce Q2 barrels at contract brewery 2 is
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,
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
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
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.