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.
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.
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.
Let’s look at another example of writing out a standard minimization problem. This is a question about minimizing the costs at a brewery that produces regular and light beer. It goes something like this…
A brewery produces two types of beer. One beer is a regular beer with a typical number of calories. The other beer is a light beer containing a lower number of calories per serving. Steady customers of the brewery buy 10 units of regular beer and 15 units of light beer per month. The brewery wishes to produce extra beer beyond that which steady customers demand. The cost per unit of regular beer is 32,000 dollars and the cost per unit of light beer is 50,000 dollars. Every unit of regular beer brings in 120,000 dollars in revenue and every unit of light beer brings in 300,000 dollars in revenue. The brewery wants at least 9,000,000 dollars in revenue. At least 20 additional units of beer can be sold.
How much beer of each type must be sold to minimize production costs?
To begin a problem like this, define the independent variables:
R: units of regular beer
L: units of light beer
Once the variables are established, let’s write out the objective function that must be minimized. We are minimizing production costs and the pertinent info in the problem is
The cost per unit of regular beer is 32,000 dollars and the cost per unit of light beer is 50,000 dollars.
It is easiest to work in thousands of dollars and to write the objective function as
C = 32R + 50L
There are two constraints on production. First of all, the brewery needs at least 9,000,000 dollars (9000 thousand dollars). The corresponding revenue data in the problem is
Every unit of regular beer brings in 120,000 dollars in revenue and every unit of light beer brings in 300,000 dollars in revenue.
The revenue (in thousands of dollars from R units of regular beer is 120R and from L units of light beer is 300L. This means
120R + 300L ≥ 9000
The second constraint has to do with the fact that “at least 20 additional units of beer can be sold.” If steady customers require 10 units of regular beer and the brewery produces R units total, the additional amount produced is R – 10. Similarly, the additional amount of light beer produced is L – 15. So the constraint for additional units is
R – 10 + L – 15 ≥ 20
Isolating R and L on the left side gives
R + L ≥ 45
Let’s put all of this together in a standard minimization problem:
Minimize C = 32R + 50L subject to
120R + 300L ≥ 9000
R + L ≥ 45
R ≥ 0, L ≥ 0
The last constraints are need since the amounts of beer produced can’t be negative.
With this standard minimization problem in hand, we can now apply the simplex method to find the solution. Using this technique, we find that the minimum cost is 1800 thousand dollars (1,800,000 dollars) and occurs when 25 units of regular beer and 20 units of light beer are produced.
In an earlier FAQ, we 
