Question 4: How do you get the optimal solution to a standard maximization problem with the Simplex Method? - PDF

Please download to get full document.

View again

of 26
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report
Category:

Law

Published:

Views: 16 | Pages: 26

Extension: PDF | Download: 0

Share
Related documents
Description
Question : How do you get the optimal solution to a standard maximization problem with the Simplex Method? In the previous question, we learned how to make different variables into basic and nonbasic variables.
Transcript
Question : How do you get the optimal solution to a standard maximization problem with the Simplex Method? In the previous question, we learned how to make different variables into basic and nonbasic variables. This allowed us to calculate the locations of corner points on the feasible region and other points of intersection. For simple linear programming problems, there can be many such points. If we naively make different variables into basic variables, it may take a very long time to find the corner point that optimizes the objective function. The Simplex Method is an algorithm for solving standard maximization problems. By following the steps below, you ensure that the points you find by changing basic variables are corner points of the feasible region. In addition, the algorithm is iterative. In other words, it is carried out several times with the result of each iteration providing the starting point to the next iteration. The beauty of the Simplex Method is that each iteration yields a larger value for the objective function and eventually leads to the largest possible value for the objective function. To get a feel for how the Simplex Method works, let s solve the standard maximization problem Maximize z 5x 6 y subject to x y xy x0, y0 We ll start by converting this problem to an appropriate system of linear equations. Add a different slack variable to each constraint to yield x ys x y s 7 To convert the objective function to an appropriate form, move all of the terms with variables to the left side of the equation. This is done by subtracting 5x and 6y from both sides. This yields the equation 5x6yz 0. These equations form the system of linear equations x ys x y s. 5x6y z 0 The augmented matrix for this system, x y s s z 0 0, is the initial simplex tableau. It is the starting point for carrying out the Simplex Method algorithm. The bottom row of the tableau is called the indicator row. The algorithm starts by determining which variable will become a basic variable in the first iteration of the algorithm. The variable that corresponds to the most negative entry in the indicator row will become a basic variable. For this matrix, the most negative entry is -6 in the second column. The variable y that corresponds to the column will become the basic variable. This column is the pivot column. If we pick the column with the most negative entry in the indicator row to be the pivot column, the objective function will increase by the largest amount. emember, those negative entries correspond to positive coefficients in the original objective function. For the objective function z 5x 6y, the most negative entry in the indicator row, -6, corresponds to the largest positive coefficient, 6, in the objective function. Increasing the value of y in the potential solution from 0 to some positive value leads to a larger increase in the objective function value z than increasing the value of x from 0 to the 8 same positive value. This is due to the fact that the coefficient on y is larger than the coefficient of x. In effect, it is more efficient to change y values than x values in the solution. We know that we ll need to make all of the entries but one in that column equal to zero via row operations. The other entry will be a one. The row where we will put the one is called the pivot row, and the entry that a one is called the pivot. To find which row will become the pivot row, we form quotients from the entries in the pivot column and the last column: x y s s z pivot column The row whose quotient is positive and smallest is the pivot row. In this case, the second row is the pivot row so the pivot is the number in this row. As we saw earlier, picking the pivot row carefully guarantees that the potential solution stays in the feasible region and all variables are non-negative. The variables must remain non-negative for a standard linear programming problem. Let s look at this idea more closely. Look at the initial tableau from the standard linear programming problem: x y s s z We already know that y will become a basic variable based on the numbers in the indicator row. By making y a basic variable, either s or s will join x as a nonbasic variable. The question is, which will it be? 9 Suppose that s and x will be the nonbasic variables in the next tableau, and will be set equal to zero. In this case, we can use the first row of the tableau to determine the corresponding value of y: xys 0 0y y Write the first row of the tableau as an equation Set x 0 and s 0 Solve for y y The value of s is found from the second row of the tableau by setting the nonbasic variables equal to zero and y : xys 0s s Write the second row of the tableau as an equation Set x 0 and y Solve for s This is not a reasonable solution since the slack variable s is negative. Let s look at making s and x the nonbasic variables. In this case, we can use the second row of the tableau to determine the corresponding value of y: x ys 0 0y y Write the second row of the tableau as an equation Set x 0 and s 0 Solve for y The value of s is found from the first row of the tableau, xys 0s s Write the first row of the tableau as an equation Set x 0 and y Solve for s 0 All variables in this case are non-negative. Note that the values for y in each case are precisely the quotients we use to choose which row the pivot row. By choosing a value for y that is smaller (the smaller quotient), we get a situation in which all variables are non-negative. Now that we know that the pivot is the in the second row, second column of x y s s z we ll use row operations to change it to a one. The rest of the pivot column will be changed to zeros using row operations. This change in basic variables will lead to the largest increase in the value of the objective function and keep all variables nonnegative. As shown in Question, change the pivot to a one by multiplying the second row by : x y s s z Once the pivot is in place, use row operations to place zeros in the rest of the column: : : : : x y s s z In the Simplex Method, the optimal solution is obtained when there are no negative numbers in the indicator row. Since the transformed matrix has a negative number in the indicator row, the solution, 0, xy is not optimal. The value of the objective function, z, can be made greater by picking the first column to be the pivot column. To find the pivot row, examine the quotients formed from dividing entries in the last column by corresponding entries in the pivot column: x y s s z pivot column The smallest quotient is in the first row. The pivot,, is in the first row, first column. As in the first iteration, we must use row operations to change the pivot to a one and change the rest of the pivot column to zeros. To change the pivot to a one, multiply the first row by : x y s s z To complete the transformation of the pivot column, we must use row operations to put zeros in the rest of the pivot column: : : : 0 0 : x y s s z For this tableau, the basic variables are x, y, and z. The nonbasic variables are s and s. The indicator row has no negative entries so this tableau is the final tableau. The optimal solution is read from this tableau by setting the nonbasic variables equal to zero. If we cover the nonbasic variables, x y s s z we see that this tableau corresponds to,, This is the same value we found graphically in Section., xy and an optimal value of z. The process outlined here is summarized in the steps shown here. The Simplex Method. Make sure the linear programming problem is a standard maximization problem.. Convert each inequality to an equality by adding a slack variable. Each inequality must have a different slack variable. Each constraint will now be an equality of the form bx bx bx sc n n where s is the slack variable for the constraint. If more than one slack variable is needed, use subscripts like s, s,. ewrite the objective function z axax anxn by moving all of the variables to the left side. After rewriting the equation, the function will have the form ax ax ax z. n n 0. Convert the equations from steps and to an initial simplex tableau. Put the equation from step in the bottom row of the tableau and all other equations above it. The bottom row is called the indicator row. 5. Find the entry in the indicator row that is most negative. If two of the entries are most negative and equal, pick the entry that is farthest to the left. The column with this entry is called the pivot column. 6. For each row except the last row, divide the entry in the last column by the entry in the pivot column. The row with the smallest positive quotient is the pivot row. If more than one row has the same smallest quotient, the higher of the rows is the pivot row. 7. The pivot is the entry where the pivot row and pivot column intersect. Multiply the pivot row by the reciprocal of the pivot to change it to a one. 8. To change the rest of the pivot column to zeros, multiply the pivot row by constants and add them to the other rows in the tableau. eplace those rows with the appropriate sums. When complete, the pivot should be a one, and the rest of the pivot column should be zeros. 9. If the indicator does not contain any negative entries, this tableau corresponds to the optimum solution. In this case, cover the nonbasic variables (set the nonbasic variables equal to zero), and read off the solution for the basic variables. Otherwise, repeat steps 5 through 9 until the indicator row contains no negative numbers. The Simplex Method will reach an optimal solution for a standard maximization problem with any number of variables and any number of inequalities. However, problems with large numbers of variables and inequalities may require many iterations of steps 5 through 9 to reach the optimal solution. Take special care to avoid arithmetic errors when carrying out the row operations. A graphing calculator can make the task of carrying out the row operations fairly painless. 5 Example Find the Optimal Solution Find the optimal solution to the linear programming problem Maximize z x 5 x subject to x x 5 7x 6x 6 x 5x x 0, x 0 Solution Although this example has three constraints (in addition to the non-negativity constraints), it still has two decision variables. Each constraint needs a slack variable to convert it to an equation. Using the slack variables s, s, and s, the constraints become x x s 5 7x 6x s 6 x 5x s Move all of the variable terms in the objective function to the left side of the equation to yield x 5x z 0 These equations become the initial simplex tableau x x s s s z The bottom row of the initial simplex tableau is the indicator row. The most negative entry of the indicator row is -5. This means the pivot column is the second column in the tableau. To determine the pivot row, compute the quotients formed by dividing entries in the last column by entries in the pivot column, x x s s s z Any negative quotients, such as 5 in the third row, are discarded. The quotient formed in the first row, 5, is the smallest quotient so the pivot is the in the first row, second column. In the first iteration of the simplex method, we must use row operations to change the pivot to a one and all other entries in the pivot column to zero. The pivot is changed to a one by multiplying the first row by. Carrying out the row operation yields x x s s s z Three row operations are necessary to put the zeros in the rest of the pivot column: 7 6 : : : : : : x x s s s z The new tableau corresponds to the solution, 0,5 x x and is not optimal since there is a negative entry in the indicator row. The new pivot column is the first column due to the negative number in the indicator row. To find the new pivot row, compute the quotient formed from dividing the entries in the last column by the entries in the new pivot column: x x s s s z The second row is the only row with a valid quotient so it is the pivot row. The pivot is the in the second row, first column of the tableau. 8 Multiply the pivot row by to change the pivot to a one: x x s s s z To complete this Simplex Method iteration, we must place zero above and below the pivot using row operations. Three row operations are required to place the zeros above and below the pivot. : : : : 7 5 : 7 8 : x x s s s z The indicator row does not contain any negative numbers so the optimal solution has been reached. The solution to the linear programming problem is easily observed by covering the columns corresponding to the nonbasic variables s and s : 9 x x s s s z The optimal solution to the linear programming problem is z 9 and occurs at,,7 x x. Example Find the Optimal Production Level The linear programming problem for the craft brewery is Maximize P 00x 80x subject to x x 50, x 85.5x, 000, 000.8x 0.85x, 000, 000 x 0, x 0 where x is the number of barrels of pale ale, and x is the number of barrels of porter. Use the Simplex Method to find the production level that maximizes profit. Solution In Example, we added slack variables and found the initial simplex tableau for this standard maximization problem. 0 The initial simplex tableau is a x 7 matrix, x x s s s P , , 000, , 000, The most negative entry in the indictor row is -00. This entry means the pivot column is the first column in the tableau. The quotients formed from the last column and the pivot column, x x s s s P 50, ,000 50, ,000,000,000, , ,000,000,000,000. 8, indicate that the third row is the pivot row. The third row must be multiplied by.8 to change the pivot to a one ,000, , x x s s s P , , 000, , 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. : , 06.8 : , : , 90, 67. : , 000, ,069, x x s s s P , 069, , , 0, : ,0, : ,0, 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 x x s s s P , 675,069, , 069, , 005, , , , 0, 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.5 in the first row, second column. The new pivot is changed to a one by multiplying the first row of the tableau by 0.5 : , x x s s s P , ,069, , , 0,680.7 We use three row operations to put zeros in the rest of the pivot column: 5.5 : , 0.8 : , 069, , : : , , x x s s s P , , , , 706,56.7. : ,88.0 : , 0, , 706, Since there are no negative numbers in the indicator row, we can read the solution from this tableau. If we cover the nonbasic variables s and s,we see that the solution corresponding to this tableau is, 5,8.,, 67.8 x x and P,706,56.7 or approximately 5,8 barrels of pale ale and,67 barrels of porter for a maximum profit of about $,706,56. Example and Example both have two decision variables and were also done graphically in Section.. 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.. Example 5 Find the Optimal Investment Portfolio Investing in stocks and mutual funds are a tradeoff. 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 indicates that the investment s price will change with the benchmark s changes. A beta less than 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 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, 00) in the table below: Fund 5 Year Average Annual eturn Beta TIAA-CEF Mid Cap Value Fund (TCMVX).7%.6 TIAA-CEF Growth & Income Fund (TIIX).88% 0.9 TIAA-CEF International Equity Fund (TIEX).67%.0 The fund TIIX 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 TIIX 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. TIIX seeks to invest 80% of its funds in securities which offer long term returns. It invests approximately 0% 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 TIEX to be at least 5% of what is invested in TIINX. If the investor has $00,000 to invest and wishes the average weighted beta to be no larger than, how much should the investor put in each of the three funds so that their returns are maximized? 5 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.07M, 0.088G, and 0.067E represent the return on these amounts. The objective function is the sum of these amounts or 0.07M 0.088G 0.067E, where is the total return. Three pieces of information can help us to write out constraints. First, the investor has $00,000 to invest. This means the sum of the amounts invested in each fund must be less than or equal to 00,000 or M GE 00,000. sum of the amounts invested Second, the investor wishes the sum of what is invested in the Mid Cap Value Fund and International Equity Fund to be at least 5% of what is invested in Growth & Income Fund. Focusing on the word sum and the phrase 5% of, we write M E 0.5 G sum of Mid Cap and International Equity Funds 5% of Growth & Value Fund 6 The word sum indicates that we must add the two quantities and the phrase 5% of indicates that we must multiply the quantity by 0.5. The final piece of information dictates that the
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks