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.
Many standard maximization problems may be solved graphically or with the Simplex Method. If your problem has two independent variables (like x and y or x1 and x2), you have a choice of which technique to utilize. However you do it, the solutions should be the same. Let’s look into this.
Maximize z = 5x1 + 2x2 subject to
2x1 + 4x2< 15
3x1 + x2< 10
x1> 0, x2> 0
Let’s look at the two solutions.
First off, here is the solution using a graphical approach.
In this solution, the feasible region is graphed using the inequalities. The corner points of the region are then tested in the objective function to find the maximum.
Now let’s look at the same problem solved with the Simplex Method.
First the problem needs to be written with slack variables and put into a matrix. Then the pivot is identified and row operations are used to change the pivot to a 1.
Once the pivot is a 1, the rest of the pivot column is filled with 0’s using row operations. Since the bottom row has negatives in it, another pivot is selected.
As before, the pivot is changed to a 1. Then the rest of the pivot column is changed to 0’s.
After these operations, there are no longer any negative numbers in the bottom row so we can read the solution off of the matrix. The solution, x1 = 2.5, x2 = 2.5 and z = 17.5, is the same as the graphical solution.
For problems with two independent variables, the linear programming problem can be found graphically and with the Simplex Method. For problems with more independent variables, the graphical method may not be applied so the Simplex Method becomes the best choice.
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.