Reading: Solving Standard Maximization Problems using the Simplex Method
Example 1
The following system can be solved by using the simplex method: Objective Function: P = 2x + 3y + zStandard 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 a1x1 + a2x2 + ... anxn le V
- All of the anumber represent real-numbered coefficients and
- the xnumber represent the corresponding variables.
- V is a non-negative (0 or larger) real number
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 + s1 = 6 3 x + 7y + s2 = 12 For instance, suppose that x = 1, y = 1, Then \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}}.} It is important to note that these two variables, s1 and s2, 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,s1,s2, 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: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: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.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 + s1 – .43s2 = .86 7 y – 4.23s1 + 2.81s2 = 8.38 2.62 s1 + .59s2 + 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
Calculator Clinic—Using the Simplex Program
We will work through the above example to verify the solution triplet (1.21, 1.20, 22.82).- Enter the initial simplex tableau into matrix A (it is important that it goes into A and nowhere else!)
- Pull matrix A into your home screen and press ENTER. Without this step, the program will not function properly.
- 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
- 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 \displaystyle{\left[\matrix{{1}{x}=\frac{{6}}{{5}}={1.2}\{1}{y}=\frac{{6}}{{5}}={1.2}\{z}={22.8}}.} With some minor rounding error, we confirm the solution triplet (1.2,1.2,22.8)
Example 2
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
- Add prices and divide by 3
- 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
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 + s3 = 150 This adds one column and one row to our tableau:Example 4
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 + s1 = 400 2 x + 2y + 2z + s2 = 252 x + 2y + 3z + s3 = 200 x + y + 2z + s4 = 900 – x – y – z + S = 0 The initial simplex tableau is:Practice Problems
- Solve each of the following linear programming problems by using the simplex method.
- Maximize: P = x + y + 2z, subject to x + 2y – z le 100 – x – y + 10z le 30 3x + 4y + 5z le 200
- 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
- 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?
- 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.
- How much time should be allotted to each politician in order to get the maximum number of viewers?
- Under these circumstances, what will be the maximum number of viewers?
- 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.
- What is the maximum revenue the company can generate, and how many of each breakfast will they need to sell?
- What is the maximum number of each breakfast the café can produce each day?
- 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.