The basic algorithm for solving a standard maximization problem is covered in Section 4.3. This process, called the Simplex Method, uses matrices and row operations to gauge whether an objective function is maximized at corner points.
In the example below, I write out a standard maximization problem from an application and then solve it with the Simplex Method.
For basic problems, a good starting point for writing out a system of equations is to define the variables. If you don’t know what the variables represent, it is almost impossible to write out the equations. Once this is accomplished, locate the different totals in the problem…these are often where the equations come from.
Problem 1 A safe investment earns 4% per year. A risky investment earns 6% per year. An investor has 20,000 dollars to invest. How much should be invested in each investment to earn 1090 dollars annually?
Solution The two totals in the problem are the total amount invested, 20,000 dollars, and the total interest earned, 1090 dollars. The 20,000 dollars total is simply the sum of the variables. To calculate interest, multiply the percentage earned times the amount.
Once the equations are written, solve them by applying the Elimination Method.
Problem 2 Coffee is usually blended before being roasted. Suppose a roaster has Guatemalan beans worth 5.50 dollars per pound and Panamanian beans worth 8.00 dollars per pound. How many pounds of each should be mixed to obtain 100 pounds of beans worth 6.25 dollars per pound?
Solution The sum of the variables is related to the total amount of beans, 100 pounds. The other total is not so obvious. Using the numbers in the problem, we can calculate the total worth of the mixture,
$latex \displaystyle \left( 6.25\frac{\text{dollars}}{\text{pound}} \right)\left( 100\text{ pounds} \right)=625\text{ dollars}$
We can find the worth of the beans that make up the mixture by multiplying the cost per pound times the number of pounds of beans, 5.50g or 8p.
Notice that when we calculate how much 70 pounds of Guatemalan beans (385 dollars) and 30 pounds of Panamanian beans (240 dollars), the sum is 625 dollars.
Carrie Green is working to raise money for the homeless by sending information letters and making follow up calls to local labor organizations and church groups. She discovers that each church group requires 2 hours of letter writing and 1 hour of follow up while for each labor union she needs 2 hours of letter writing and 3 hours of follow up. Carrie can raise 100 dollars from each church group and 200 dollars from each union local, and she has a maximum of 16 hours of letter writing time and a maximum of 12 hours of follow up time available per month. Determine the most profitable mixture of groups she should contact and the most money she can raise.
Continue reading “How Do I Set Up and Solve a Maximization Problem with the Simplex Method?”
The row operations in the Simplex algorithm are not difficult to compute. To start, you should carry out the row operations in the process by hand. As you will quickly realize, the Simplex algorithm is tedious and prone to arithmetic errors. Once you get the idea behind how the Simplex method works, you can carry out the row operations in a spreadsheet.
In the video below, the steps in the Simplex Methods are carried out in Google Sheets. The same steps can also be carried out in other spreadsheets such as Microsoft Excel.
Please note that there is a typo in the original matrix in the process. The cell in D2 should be a 1 instead of a zero to account for the slack variable in the first constraint.
In an earlier FAQ, we wrote out a standard minimization problem from an application. Now we’ll solve that problem by finding the dual standard maximization problem and applying the Simplex Method.
This process is covered in Section 4.4 of the textbook. For complete details on the process, consult this section and the many examples contained in this section. I will assume that you have looked over this section and are familiar with carrying out row operations on a matrix.
The problem we will solve is
Minimize C = 16y1 + 14y2 + 12y3 subject to
y1 + y2 + y3 > 6000
2y2 – 3y3 > 0
3y1 – y2 – y3 > 0
y1 > 0, y2 > 0, y3 > 0
Solution Write out the dual problem and apply the Simplex Method. Start by entering the objective function and constraints into a matrix. The transpose of this matrix yields the form of the dual standard maximization problem.
The dual problem is
Maximize z = 6000x1 subject to
x1 + 3x3 < 16
x1 + 2x2 – x3 < 14
x1 – 3x2 – x3 < 12
x1 > 0, x2 > 0, x3 > 0
Now add the slack variables to each constraint and form the initial matrix for the Simplex Method.
The pivot column is the first column since that is where the indicator row is most negative. The pivot row is the third row. The entry in the pivot is already a zero so we simply need to put zeros in the rest of the column using row operations.
For this new matrix, the pivot is the 5 in the second row, second column. Change the pivot to a 1 and then use it to put zeros in the rest of the column. This results in
Since there is still a negative number in the indicator row, we continue applying the Simplex Method. In this step, the pivot is the 4 in the first row, third column. As before, this entry is changed to a 1 and used to make the rest of the column into zeros.
The indicator row does not contain any negatives numbers so this is the final matrix. The solution to the standard minimization problem is under the slack variables and indicate that
y1 = 1500, y2 = 2700, and y3 = 1800
with a corresponding minimum of C = 83400 cents or $834.
