How do you find the optimal solution for an application?
The Simplex Method can be applied to the brewery application developed earlier in the chapter.
Example 4 Find the Optimal Production Level
The linear programming problem for the craft brewery is
where x1 is the number of barrels of pale ale, and x2 is the number of barrels of porter. Use the Simplex Method to find the production level that maximizes profit.
Solution In Example 1, we added slack variables and found the initial simplex tableau for this standard maximization problem.
The initial simplex tableau is a 4 x 7 matrix,
The most negative entry in the indicator row is -100. This entry means the pivot column is the first column in the tableau. The quotients formed from the last column and the pivot column,
indicate that the third row is the pivot row.
The third row must be multiplied by 1/23.8 to change the pivot to a 1.
The entries in the first six columns are shown rounded to three decimal places when necessary, and the entries in the last column are rounded to the nearest tenth.
Now we need to use three row operations to place zeros in the rest of the pivot column.
The negative number in the indicator row tells us that the second column will be the new pivot column.
To locate the new pivot, form the quotients with the last column and second column. The quotients for the individual rows are
The numbers shown in the quotient are rounded numbers, and the amount calculated is rounded to the nearest integer. This does not affect our choice of the pivot row. If the quotients are close to each other, carry more decimals so you do not choose the wrong pivot row due to rounding. The new pivot is 0.544 in the first row, second column.
The new pivot is changed to a 1 by multiplying the first row of the tableau by 1/0.544:
We use three row operations to put zeros in the rest of the pivot column:
Since there are no negative numbers in the indicator row, we can read the solution from this tableau. If we cover the nonbasic variables s1 and s2,we see that the solution corresponding to this tableau is (x1, x2) = (35,328.2, 14,671.8) and P = 4,706,563.7 or approximately 35,328 barrels of pale ale and 14,672 barrels of porter for a maximum profit of about $4,706,564.
Example 3 and Example 4 both have two decision variables and were also done graphically in Section 4.2. In the next example, we apply the Simplex Method to a problem with three decision variables. Problems with more than two decision variables are impossible to do with the graphical methods introduced in Section 4.2.
Example 5 Find the Optimal Investment Portfolio
Investing in stocks and mutual funds are a trade off. We want to maximize the money we make from investments, but manage the risk of losing money in poor investments. Typically, investments with higher returns are riskier, and investments with lower returns are less risky.
Investors use several statistics to quantify the returns on their investments. For instance, websites such as Yahoo Financial calculate measures like average rate of return. This number indicates the investor’s total returns on an investment annualized over some time period. The higher the average rate of return, the more gains you achieve from dividends or the sale of the stock or mutual fund.
There are also several measures of risk available to investors. One commonly used indicator is called beta. The beta of a stock or mutual fund is calculated using regression analysis. The details of the analysis are not important for our purposes. However, understanding what the beta tells you is an important investing tool.
A stock or mutual fund’s beta measures the volatility of the investment’s price with respect to some benchmark like the S & P 500 or the Dow Jones Industrial Average. A beta of 1 indicates that the investment’s price will change with the benchmark’s changes. A beta less than 1 indicates that the investment’s price is less volatile than the benchmark. In other words, changes in the benchmark will be larger than changes in the investment’s price. A beta greater than 1 indicates that the investment’s price is more volatile than the benchmark. In this case, changes in the benchmark will be smaller than changes in the investment’s price.
Suppose an investor is interested in investing in three different mutual funds. The funds, their five year average annual return, and beta values are shown (as of July 31, 2010) in the table below:
The fund TIIRX has the highest rate of return and the lowest beta. The fund TCMVX has the lowest rate of return and the highest beta. On the surface, it would appear that the investor should put all of their money in TIIRX since that would yield the highest return and the lowest risk.
Each investor has their own requirements for their investments and in this case, the investor wants to diversify their holdings. This means the investor wants to lower their overall risk by investing in several broad categories of stocks. TIIRX seeks to invest 80% of its funds in securities which offer long term returns. It invests approximately 20% in smaller companies that offer an opportunity at growth. While this may seem like a good mix, the investor wishes the sum of what is invested in TCMVX and TIERX to be at least 25% of what is invested in TIINX.
If the investor has $100,000 to invest and wishes the average weighted beta to be no larger than 1, how much should the investor put in each of the three funds so that their returns are maximized?
Solution A good starting point for linear programming problems is the variables. In this problem, we want to find the amount of money to invest in each fund. It makes sense to define the variables as follows:
M: amount of money invested in Mid Cap Value Fund.
G: amount of money invested in Growth & Income Fund.
E: amount of money invested in International Equity Fund
We wish to maximize the return on the investment. The return on an investment is found by multiplying the amount invested by the average annual return. Since M, G, and E represent the amounts of money invested, 0.0172M, 0.0288G, and 0.0267E represent the return on these amounts. The objective function is the sum of these amounts or
where R is the total return.
Three pieces of information can help us to write out constraints. First, the investor has $100,000 to invest. This means the sum of the amounts invested in each fund must be less than or equal to 100,000 or
Second, the investor wishes the sum of what is invested in the Mid Cap Value Fund and International Equity Fund to be at least 25% of what is invested in Growth & Income Fund. Focusing on the word “sum” and the phrase “25% of”, we write
The word “sum” indicates that we must add the two quantities and the phrase “25% of” indicates that we must multiply the quantity by 0.25.
The final piece of information dictates that the investor “wishes the average weighted beta to be no larger than 1”. A weighted average tells us that we need to add up some terms and then divide by a total amount. The weighted sum of the risk is written as 1.16M + 0.93G + 1.04E. The term “weighted” indicates the presence of the variable in each term. If we had simply added up the beta values, they would have each contributed “equally” to the sum since each one appears in their own term. By multiplying the beta value by the amount invested in the corresponding fund, we are weighting the beta by the amount invested. If we do this, then a fund with a large amount in it will contribute more to the sum than a fund with very little invested in it. To average the weighted sum, we divide by the total amount invested or M + G + E. The constraint
reflects the investor’s wish that the average weighted beta be no more than 1.
If we add non-negativity constraints, the linear programming problem becomes
This linear programming problem is not in standard maximum form since the second and third constraints do not have the form
b1 x1 + b2 x2 + … + bn xn ≤ c
where b1, b2, … and c are real numbers and c ≥ 0. A little algebra changes these constraints to the proper form.
If we start with the second constraint and subtract M and E from both sides, we get the inequality
0 ≥ 0.25G – M – E
Flip the inequality and rearrange the order of the terms to yield
–M + 0.25G – E ≤ 0
This inequality has the proper form.
If we start with the third inequality and multiply both sides by M + G + E we are left with
1.16M + 0.93G + 1.04E ≤ M + G + E
Collect all of the terms on the left side to yield
0.16M – 0.07G + 0.04E ≤ 0
With these modifications, we can write out a standard maximization problem:
Now that the problem is in standard form, we can add slack variables to the constraints and write out the initial simplex tableau.
The objective function must be rewritten with all terms on the left side of the equal sign or
-0.0172M – 0.0288G – 0.0267E + R = 0
Notice that the variables are written in a particular order. Since the terms will match with columns in the tableau, we need to use this order for each equation we write.
Add the slack variables s1, s2, and s3 to the inequalities
to give the equations
Combine these equations with the equation from the objective function to give
From this initial simplex tableau we need to pick a pivot column and row. To find the pivot column, locate the most negative entry in the indicator row at the bottom. The entry -0.0288 is the most negative entry so the second column is the pivot column.
The quotients for picking the pivot row are found by dividing the entries in the last column by the corresponding entries in the pivot column,
Remember that quotients with a negative numerator or denominator are ignored so the quotient for the third row isn’t even computed. The second row contains the smallest quotient, so the pivot is 0.25 in the second row, second column.
To change the pivot to a 1, multiply the second row by 1/0.25 or 4:
With the pivot changed, row operations are needed to change the other numbers in the pivot column to zeros.
After the first Simplex Method iteration, there is still a negative number in the indicator row. This tableau does not correspond to an optimal solution so we must select the first column as the pivot column and determine the new pivot row. Only the first row has an admissible quotient. The 5 in the first row, third column will be the new pivot.
To change the pivot to a 1, multiply the first row by 1/5:
Row operations are required to change the rest of the column into zeros.
After the row operations, there are no negative numbers in the indicator row. Covering the first, fourth and fifth columns, we can read off the solution (M, G, E) = (0, 80,000, 20,000) and R = 2838. Remember, by covering the first column we are assuming that M = 0.
The optimal solution is to invest no money in the Mid Cap Value Fund, $80,000 in the Growth & Income Fund, and $20,000 in the International Equity Fund. This combination of investments results in the largest return of $2838.
Even with more variables, the Simplex Method allows the standard maximization problem to be solved. Adding more decision variables or constraints simply adds more columns or rows to the initial simplex tableau. Although this makes for more writing, it does not change how the Simplex Method is applied.