We found in the previous section that the graphical method of solving linear programming problems, while time-consuming, enables us to see solution regions and identify corner points. This, however, is not possible when there are multiple variables. We can visualize in up to three dimensions, but even this can be difficult when there are numerous constraints. To handle linear programming problems that contain upwards of two variables, mathematicians developed what is now known as the simplex method. It is an efficient algorithm (set of mechanical steps) that "toggles" through corner points until it has located the one that maximizes the objective function. Although tempting, there are a few things we need to lookout for prior to using it. Prior to providing the mathematical details, let's see an example of a linear programming problem that would qualify for the simplex method:

Example 1

The following system can be solved by using the simplex method: Objective Function: P = 2x + 3y + z Subject to Constraints: 3 x + 2y le 5 2 x + y – z le 13 z le 4

Standard Maximization Problem

Mathematically speaking, in order to use the simplex method to solve a linear programming problem, we need the standard maximization problem:

• an objective function, and
• one or more constraints of the form a₁x₁ + a₂x₂ + ... a_nx_n le V
  • All of the a_number represent real-numbered coefficients and
  • the x_number represent the corresponding variables.
  • V is a non-negative (0 or larger) real number

Having constraints that have upper limits should make sense, since when maximizing a quantity, we probably have caps on what we can do. If we had no caps, then we could continue to increase, say profit, infinitely! This contradicts what we know about the real world. In order to use the simplex method, either by technology or by hand, we must set up an initial simplex tableau, which is a matrix containing information about the linear programming problem we wish to solve.

Setting Up the Initial Simplex Tableau

First off, matrices don't do well with inequalities. For one, a matrix does not have a simple way of keeping track of the direction of an inequality. This alone discourages the use of inequalities in matrices. How, then, do we avoid this? Consider the following linear programming problem Maximize: P = 7x + 12y Subject to: 2x + 3y le 6 3 x + 7y le 12 Because we know that the left sides of both inequalities will be quantities that are smaller than the corresponding values on the right, we can be sure that adding "something" to the left-hand side will make them exactly equal. That is: 2x + 3y + s₁ = 6 3 x + 7y + s₂ = 12 For instance, suppose that x = 1, y = 1, Then [latex-display]\displaystyle{\left[\matrix{{stackrel{{{x}}}{{{2}{({1})}}}}+{stackrel{{{y}}}{{{3}{({1})}}}}+{stackrel{{{s}_{{1}}}}{{{1}}}}={6}\{stackrel{{{x}}}{{{3}{({1})}}}}+{stackrel{{{y}}}{{{7}{({1})}}}}+{stackrel{{{s}_{{2}}}}{{{2}}}}={12}}.}[/latex-display] It is important to note that these two variables, s₁ and s₂, are not necessarily the same. They simply act on the inequality by picking up the "slack" that keeps the left side from looking like the right side. Hence, we call them slack variables. This takes care of the inequalities for us. Since augmented matrices contain all variables on the left and constants on the right, we will rewrite the objective function to match this format: –7x – 12y + P =0 This will require us to have a matrix that can handle x,y,s₁,s₂, and P. We will put it in this order. Finally, the simplex method requires that the objective function be listed as the bottom line in the matrix so that we have: We have established the initial simplex tableau. Note that he horizontal and vertical lines are used simply to separate constraint coefficients from constants and objective function coefficients. Also notice that the slack variable columns, along with the objective function output, form the identity matrix.

Solving the Linear Programming Problem by Using the Initial Tableau

We will present the algorithm for solving, however, note that it is not entirely intuitive. We will focus on this method for one example, and will then proceed to use technology to run through the process for us.

1. Select a Pivot Column

We first select a pivot column, which will be the column that contains the largest negative coefficient in the row containing the objective function. Note that the largest negative number belongs to the term that contributes most to the objective function. This is intentional since we want to focus on values that make the output as large as possible. Our pivot is thus the y column.

2. Select a Pivot Row

Do this by computing the ratio of each constraint constant to its respective coefficient in the pivot column—this is called the test ratio. Select the row with the smallest test ratio. We first calculate the test ratios: [latex-display]\displaystyle{\left[\matrix{\frac{{6}}{{2}}={2}\frac{{12}}{{7}}approx{1.7}}.}[/latex-display] Since the test ratio is smaller for row 2, we select it as the pivot row. The boxed value is now called our pivot. To justify why we do this, observe that 2 and 1.7 are simply the vertical intercepts of the two inequalities. We select the smaller one to ensure we have a corner point that is in our feasible region:

3. Using Gaussian Elimination, Eliminate Rows 1 and 3

We can do this by entering the entire initial tableau into our calculator and using the calculator's row operation features. We want to take –3/7 multiplied by row 2 and add it to row 1, so that we eliminate the 3 in the second column. To do this, we access the *row+() function in the TI-83. Go to , scroll over to MATH, and access F: *row+(). Press ENTER. This function takes the multiple of one row and adds it to another. We then want to make sure the change is made to matrix a, so we will store the result to matrix A. The format of this function is row + (multiple,matrix,row to multiply,row to add to) Since we want to take -3/7 times matrix A's 2 ^nd row and add it to row 1, we type: To store into matrix A, press , and then select matrix A from the matrix listing. If you do not do this, then the matrix will not track your results. We have zeroed out the 2nd column of the first row. We want next to eliminate the –12. To do this, we must multiply 7 by 12/7 and add it to row 3 (recall that placing the value you wish to cancel out in the denominator of a multiple and the value you wish to achieve in the numerator of the multiple, you obtain the new value): By moving to the right, we can see that we have effectively zeroed out the second column non-pivot values. We get the following matrix: What have we done? For one, we have maxed out the contribution of the 2-2 entry y-value coefficient to the objective function. Have we optimized the function? Not quite, as we still see that there is a negative value in the first column. This tells us that can still contribute to the objective function. To eliminate this, we first find the pivot row by obtaining test ratios: [latex-display]\displaystyle\frac{{.86}}{{.71}}approx{1.3}[/latex-display] [latex-display]\displaystyle\frac{{12}}{{3}}={4}[/latex-display] Interestingly, this test ratio corresponds to the input value of the intersection of the two lines! Similarly, we proceed to eliminate all non-pivot values. ( Note: The 2-1 entry is not quite 0; this is due to rounding error) There remain no additional negative entries in the objective function row. We thus have the following matrix: We are thus prepared to read the solutions.

4. Identify the Solution Set

To identify the solution set, focus we focus only on the columns with exactly one non-zero entry—these are called active variables (columns with more than one non-zero entry are thus called inactive variables). We notice that both the and columns are active variables. We really don't care about the slack variables, much like we ignore inequalities when we are finding intersections. We now see that, .71 x + s₁ – .43s₂ = .86 7 y – 4.23s₁ + 2.81s₂ = 8.38 2.62 s₁ + .59s₂ + P = 22.82 Setting the slack variables to 0, gives: .71x = .86 → x ≈ 1.21 7 y = 8.38 → y ≈ 1.20 P = 22.82 Thus, the triplet, (x,y,z) ~ (1.21,1.20,22.82) is the solution to the linear programming problem. That is, inputs of 1.21 and 1.20 will yield a maximum objective function value of 22.82 While somewhat intuitive, this process has more behind it than we are letting on. And, rather than going through these grueling steps ad nauseum, we will allow our technology to follow these steps. For this, we need a special program, which will be distributed in class, To perform the simplex method with a graphing calculator, the following programs are needed:

• Pivot,
• Pivot1, and
• Simplex

Pivot and Pivot1 are not used directly. Instead, the Simplex program reaches into these two applications to assist it with some rather long and tedious code. How does the code work? Using instructions, it finds pivot columns, pivot rows, performs Gaussian elimination, checks for negatives in the objective function row, and repeats this process, as necessary until all negatives have been removed.

Calculator Clinic—Using the Simplex Program

We will work through the above example to verify the solution triplet (1.21, 1.20, 22.82).

1. Enter the initial simplex tableau into matrix A (it is important that it goes into A and nowhere else!)
2. Pull matrix A into your home screen and press ENTER. Without this step, the program will not function properly.
3. Go to and run Simplex. Continue to press ENTER until you see FINAL TABLEAU appear. The program shows all pivot rows and columns. These correspond to the pivot rows and columns found by working the problem out long-hand
4. Read the solution by ignoring all inactive columns and using only those solutions that correspond to active columns. If a variable column is ever inactive, its value is set to 0. Reading from the matrix gives [latex-display]\displaystyle{\left[\matrix{{1}{x}=\frac{{6}}{{5}}={1.2}\{1}{y}=\frac{{6}}{{5}}={1.2}\{z}={22.8}}.}[/latex-display] With some minor rounding error, we confirm the solution triplet (1.2,1.2,22.8)

Now that we have illustrated that, in fact, the simplex method works for even two input variables, let's show a situation where this method is particularly useful.

Example 2

A new airline has decided to join the market. It is considering offering flights out of Phoenix, AZ, and would initially like to travel to three different locations: San Diego, San Francisco, and Las Vegas. The distances of each round-trip flight going out of Phoenix are (approximately): 720 miles, 1500 miles, and 1140 miles, respectively. The company would like to use the slogan, "the average price per flight is never more than $200." As for costs, it anticipates flights to San Diego will run about 10% of airfare. Similarly, San Francisco will run 12% and Las Vegas will run 14% of airfare. The company wants to ensure that the overall average cost is no more than 10% of earned airfare. Recent market research allows the company to conclude that it could probably sell about 1900 San Diego tickets, 700 San Francisco tickets, and 1000 Las Vegas ticket. Under these conditions and assuming that all tickets sold are round-trip flights, how much should the company charge per ticket in order to maximize its total revenue?

Solution

We want to know the price for airfare to each destination. Let, x = price per round-trip ticket to San Diego y = price per round-trip ticket to San Francisco z = price per round-trip ticket to Las Vegas The company wants to maximize total revenue. This is based on the sum of number of tickets sold multiplied by the price per ticket, which is: R = 1900x + 700y + 1000z Subject to the constraints:

• Average price per flight is less than or equal to $200
• Average cost from airfare is no more than 10% of total

Mathematically,

• Add prices and divide by 3 [latex]\displaystyle\frac{{{x}+{y}+{z}}}{{3}}le{200}[/latex]
• Revenue from San Diego tickets will total and 10% of this amount is estimated to be cost. That is Cost = .10(900x) = 90x. Similarly, we have .12(700y) = 84y and .14(1000z) = 140z. We want the sum of these costs to be less than or equal to 10% of total revenue, which is .10(900x + 700y + 1000z) = 90x + 70y + 100z. That is, 90 x + 84y + 140z le 90x + 70y + 100z 0x + 14y + 40z le 0

Since both constraints are of the correct form, we can proceed to set up the initial simplex tableau. As a note, be very cautious about when you use the simplex method, as unmet requirements invalidate the results obtained. The rewritten objective function is: –900 x – 700y – 1000z + R = 0 And simplified constraints are: x + y + z le 600 (Multiply both sides by 3) 14 y + 40z le 0 Each of the two constraints will require a slack variable, and so we rewrite them as follows: x + y + z + s₁ = 600 14 y + 40z + s₂ = 0 We will have the following variable columns: x,y,z,s₁,s₂,R, and the constant column, for a total of 7 columns. We have two constraints and one objective function for a total of three rows. We now write the initial simplex tableau: The tableau is now ready to be simplified using the Simplex program: Since only the z column is considered active, we can see that z = 600 is a solution. The fact that x and y are inactive variables, we set x = y = 0. That is, they do not contribute to maximizing revenue. Additionally, R is an active variable, and so we see that R = $600,000 is the maximum revenue the company can earn, given the constraints. They should sell tickets to Las Vegas for $600 and market no flights to San Diego or San Francisco. As you might guess, the company is probably a bit stunned. We will explore this in the next example. It is interesting that Las Vegas trips alone produce the highest revenue, based on the constraints given. Why is this? If we look at the constraints, we see that the company is fairly certain it can sell 1000 flights to Las Vegas, and the percentage of each ticket that constitutes cost is only 9%, the lowest of the three flights. The company is also somewhat puzzled that it is expected to sell tickets at $600 each. At this point, it might decide to add some additional constraints to the model.

Example 3

Supposed the airliner in Example 2 decides that it can charge no more than $150 per ticket to Las Vegas in order to be competitive with other airliners that fly to the same destination. Assuming all other constraints will still be used, how are ticket prices and maximum revenue affected?

Solution

We use the same initial tableau, but we must deal with the following new constraint: z le 150 Adding a third slack variable, we have z + s₃ = 150 This adds one column and one row to our tableau: We update this information in our calculator and produce the final tableau (note that you cannot insert columns and rows without information being shifted): We see that the x and z variables are both active, whereas y is inactive. We find that the price for each San Diego ticket should be $450, and the price for each Las Vegas ticket should be $150, the minimum value specified in our constraint. Still, however, no San Francisco trips should be offered, and now the total revenue has decreased to $555,000. Clearly, additional constraints must be added in order to reduce the price per ticket and ensure tickets should be sold for a San Francisco trip. Keep in mind that we're still experiencing the effects of high cost percentages and low potential sale opportunities. Some decisions by management are certainly in order.

Example 4

A catering company is to make lunch for a business meeting. It will serve ham sandwiches, light ham sandwiches, and vegetarian sandwiches. A ham sandwich has 1 serving of vegetables, 4 slices of ham, 1 slice of cheese, and 2 slices of bread. A light ham sandwich has 2 serving of vegetables, 2 slices of ham, 1 slice of cheese and 2 slices of bread. A vegetarian sandwich has 3 servings of vegetables, 2 slices of cheese, and 2 slices of bread. A total of 10 bags of ham are available, each of which has 40 slices; 18 loaves of bread are available, each with 14 slices; 200 servings of vegetables are available, and 15 bags of cheese, each with 60 slices, are available. Given the resources, how many of each sandwich can be produced if the goal is to maximize the number of sandwiches?

Solution

We wish to maximize the number of sandwiches, so let: x = # of ham sandwiches y = # of light ham sandwiches z = # of vegetarian sandwiches The total number of sandwiches is given by x S = x + y + z The constraints will be given by considering the total amount of ingredients available. That is, the company has a limited amount of ham, vegetables, cheese, and bread. In total, the company has 10(40) = 400 slices of ham, 18(14) = 252 slices of bread, 200 servings of vegetables, and 15(60) = 900 slices of cheese available. At most, the company can use the above amounts. There are two sandwiches that use ham—the first requires 4 slices of ham and the second requires only 2, per sandwich. That is, 4 x + 2y le 400 That is, the total number of slices of ham cannot exceed 400. Each sandwich requires 2 slices of bread so 2 x + 2y + 2z le 252 The ham sandwiches have 1 and 2 servings of vegetables, respectively, and the vegetarian sandwich has 3 servings of vegetables. So, 1 x + 2y + 3z le 200 Both ham sandwiches require one slice of cheese, and the vegetarian sandwich requires two slices of cheese, so, 1x + 1y + 2z le 900 These constraints satisfy the requirements for the simplex method, so we proceed. Incorporating slack variables, we get: 4x + 2y + 0z + s₁ = 400 2 x + 2y + 2z + s₂ = 252 x + 2y + 3z + s₃ = 200 x + y + 2z + s₄ = 900 – x – y – z + S = 0 The initial simplex tableau is: Using the simplex program gives: We find that 100 ham sandwiches, 26 vegetarian sandwiches, and 0 light ham sandwiches should be made to maximize the total number of sandwiches made. Notice that this will effectively use up all of the bread, which is the first to go.

Practice Problems

1. Solve each of the following linear programming problems by using the simplex method.
   1. Maximize: P = x + y + 2z, subject to x + 2y – z le 100 – x – y + 10z le 30 3x + 4y + 5z le 200
   2. Maximize: P = .5x + 1.2y + .9z, subject to 1.1 x + 2.1y + .4z le 9 0.7 x + .99y + z le 12 – x – 4y + 30z le 400
2. A gas station sells three types of energy drinks: High Power, Purple Elephant, and Creature. It earns $0.60, $0.76, and $0.99 in profit on each of the three drinks, respectively. It can stock no more than 400 cans in the store each week. Typically, at least twice as many Purple Elephants are sold as Creatures. Finally, the company never sells more than 100 High Powers in a week. If the company's goal is to maximize profit, how many of each energy drink should it stock?
3. A political party is planning a half-hour television show. The show will have 3-minutes of direct requests for money from viewers. Three of the party's politicians will be on the show: a senator, a congresswoman, and a governor. The senator, a party "elder statesman," demands that he be on screen at least twice as long as the governor. The total time taken by the senator and the governor must be at least twice the time taken by the congresswoman. On the basis of a preshow survey, it is believed that 40, 60, and 50 (in thousands) viewers will watch the program for each minute the senator, congresswoman, and governor, respectively, are on the air.
   1. How much time should be allotted to each politician in order to get the maximum number of viewers?
   2. Under these circumstances, what will be the maximum number of viewers?
4. Sugar-Coated Café has proposed starting a new line of granola-based breakfast cereals: Berry Bomb, Delicious Detox, and Marvelous Mango. The café generates $3.99, $4.49, and $2.99 for the three breakfasts, respectively. A Berry Bomb requires ¼ cup of strawberries, ¼ cup of blueberries, ¼ cup of raspberries, ½ cup of water, and 1 cup of its famous granola. The Delicious Detox contains ¾ cup of blueberries, ½ cup of green tea, and 1 cup of the granola. A Marvelous Mango contains 1 cup of chopped mango, ½ cup of water, and 1½ cups of granola. Each day, the café receives from its distributor 5 bags of strawberries, 6 bags of blueberries, 2 bags of raspberries, 10 boxes of granola, 20 mangos, and can produce 60 cups of green tea. Each bag of fruit contains about 8 cups of fruit. A single box of granola contains about 20 cups-worth of granola, and a mango can produce about 2 cups of fruit. The café does not need to use up all the ingredients it receives, but can use no more. Answer the following questions by solving separate linear programming problems.
   1. What is the maximum revenue the company can generate, and how many of each breakfast will they need to sell?
   2. What is the maximum number of each breakfast the café can produce each day?
   3. Gives a possible reason for why we observe the same number of breakfasts in each of the two above scenarios. Your reasons should take into account what it is that is being maximized in each of the two cases, in addition to the constraints.

---

Milos Podmanik, By the Numbers, "Solving Standard Maximization Problems using the Simplex Method," licensed under a CC BY-NC-SA 3.0 license. MathIsGreatFun, "MAT217 HW 2.2 #1," licensed under a Standard YouTube license. MathIsGreatFun, "MAT217 2.2 #2," licensed under a Standard YouTube license. MathIsGreatFun, "MAT217 2.2 #3," licensed under a Standard YouTube license. MathIsGreatFun, "MATH217 2.2 #4," licensed under a Standard YouTube license.