Math 438 ACTIVITY 16: Using the SIMPLEX Program to Solve LP problems
WHY: This activity is designed to help you learn to use the SIMPLEX program on the Saint Mary's central computer, Jade. This program will handle the solution of linear programming problems with up to 60 variables and 40 constraints. Unlike the Maple procedure, it requires no interaction with the user except the specification of the problem (in a standard form). It also gives added information for post-optimality analysis (our next topic).
LEARNING OBJECTIVES:
1. Discover how to prepare the data for, run, and read the results of the Simplex program
2. Observe and think about the sensitivity analysis section of the Simplex program output.
3. Discover how to maximize the learning done in groups.
CRITERIA:
1. Quality of the answers to the Critical Thinking Questions.
2. Degree to which learning was improved through focused group effort.
RESOURCES:
1. Appendix A: Strategic Mathematics
2. The SIMPLEX program, running on the Saint Mary's network
3. A text editor or word processor [MS Word on a networked computer serves well]
4. The handout “To use SIMPLEX to solve an LP problem in standard form (with identity present).” Attached here
5. 30 minutes
PLAN:
1. Look over the model and answer the Critical Thinking Questions.
2. Complete the exercise [exercise 1.16 p. 43 in the text]
MODEL: [Examples 3.3.4-3.3.6 from pp.103 - 106]
minimize x1 - 2x2 - x3
subject to x1 + x2 + x3 ≤ 5
4x1 - x2 + x3 ≤ 6
x1 + x2 ≤ 4
x1 ≥ 0, x2 ≥ 0
Standard Form:
minimize x1 - 2x2 - x3
subject to x1 + x2 + x3 + x4 = 5
4x1 - x2 + x3 + x5 = 6
x1 + x2 + x6 = 4
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, x6 ≥ 0
Initial Basic Variables x4, x5, x6 Initial Nonbasic Variables x1, x2, x3
To use SIMPLEX to solve an LP problem in standard form (with identity present):
1. Create the input file
Easiest – use Microsoft Word or (or WordPad) to create a text file with the problem data, store the file in your filespace (h: drive)
You can also use any Unix line editor after you have logged in to jade.
The data file for this problem is shown below, with comments [which you should not enter] on each line typed after the // symbol
The program is very sensitive to spacing and to order.
Note that the tableau is in a special form: The b vector (of constants) comes first, then the initial identity matrix in order, then the initial non-basic variables. The constraint coefficients for the initial basic variables are not entered by the user but are filled in by the program.
There are two lines of command parameters and one line of setup that begin the file before the actual data are entered:
To creat the input file for this example, type:
1,1 // Indicates you want to solve problems number 1 to 1 (only one - you could do several in one run)
3,6,1,1 // This means we have 3 constraints and 6 variables, and that we want all tableaus printed (0 would indicate only the first and last) as well as the sensitivity analysis (1 for “yes” 0 for “no”) .
4,5,6,1,2,3 // The basic variables are x4, x5, x6 (order matters - identity must be in correct order) and the nonbasic variables are x1, x2, x3.
0,0,0,1,-2,-1 // The coefficients [actual coefficients - signs not changed] of the objective function in the variable order from the previous line [basic variables first].
5,1,1,1 // Right hand side and nonbasic coefficients for 1st constraint.
6,4,-1,1 // Right hand side and nonbasic coefficients for 2nd constraint..
4,1,1,0 // Right hand side and nonbasic coefficients for 3rd constraint..
2. Save the data file in your filespace (not on the hard drive) as a plain text document:
Use Save As....
Select “Other Formats” and Save file as “Plain text (*,txt)”
The name must be compatible with Unix file naming: In Unix, spaces always end names/words and various symbols (/, <, > , |, !, etc.) are command symbols or link filenames together – so none of these can be used in filenames. It’s safest to restrict yourself to letters, numbers, hyphen(-) and underscore (_) Word will add “.txt” to the end of your filename - this becomes part of the name
3. Log in in to jade and run the simplex program on this file:
FROM a WINDOWS machine:
Select Start>Utilities>PuTTY or
Select Start>Run and enter (type) C:Program Files\Putty.exe
For hostname enter jade or jade.saintmarys.edu - connect via SSH, don’t change other settings
This runs the program PuTTY to establish a secure shell link to a remote computer (as an active machine, not just a file server)
Log in with your usual login and password. You should see the prompt
-bash-3.00$ All your Unix commands will be entered after this prompt.
[To log out of jade you will type Exit after the prompt]
FROM a MAC:
Run the program Terminal (it’s in Applications Folder>Utilities>Terminal) – this opens a Unix session on the Mac
At the prompt, type ssh –l yourlogin jade.saintmarys.edu
Type your password in response to the prompt
This opens a secure shell connection between the Unix system on the Mac and the Unix system on jade.
-bash-3.00$ All your Unix commands will be entered after this prompt.
[To log out of jade you will type Exit after the prompt]
4. Run the simplex program on this file:
To run the simplex program, enter (type)
/home/faculty1/cpeltier/simplex<filename using the filename (probably including .txt) of your data file [The program lives in my filespace. In Unix, typing the pathname of a file is an instruction to run that file as a program. The “<filename” includes the data file]
[It’s easiest to copy the first part of this string to the clipboard and paste it in each time you want to run the program.]
The computer prints the following lines (indicating the running of the program):
Completed reading the data
Finished printing tableau 1
Finished printing tableau 2
Finished printing tableau 3
$. To see/print the results.
Return to Word (or whatever text editor you used) and open the file ftn01 in your filespace [with Word you will need to use the “All files (*,*)” filetype since there is no extension on the filename] – this is the file that is always generated by the simplex program.
Save the file with a new name – the next time you run simplex the ftn01 file will be overwritten.
NOTES:
The program prints an additional row [except for the constant column – showing the value of the function] between the coefficient matrix and the usual bottom row of the tableau, so the usual bottom row is the very last row of the printout.
If the tableau is too wide to fit on one row (more than about seven variables) each row wraps individually – all of row 1 is printed before all of row 2, etc.
Here is the file generated by the commands shown above (you should obtain this result in working through the model)
[Font used is Monaco 9 - I had to put in the page breaks]
PROBLEM NUMBER 1
ITERATION 1
VARIABLE COSTS
0.0000 0.0000 0.0000 1.0000 -2.0000 -1.0000
SOLUTION TABLEAU
4 5 6 1 2 3
4 5.00 1.00 0.00 0.00 1.00 1.00 1.00
5 6.00 0.00 1.00 0.00 4.00 -1.00 1.00
6 4.00 0.00 0.00 1.00 1.00 1.00 0.00
0.0 0.0 0.0 0.0 0.0 0.0 0.0
0.0 0.0 0.0 -1.0 2.0 1.0
ITERATION 2
SOLUTION TABLEAU
4 5 6 1 2 3
4 1.00 1.00 0.00 -1.00 0.00 0.00 1.00
5 10.00 0.00 1.00 1.00 5.00 0.00 1.00
2 4.00 0.00 0.00 1.00 1.00 1.00 0.00
-8.0 0.0 0.0 -2.0 -2.0 -2.0 0.0
0.0 0.0 -2.0 -3.0 0.0 1.0
ITERATION 3
SOLUTION TABLEAU
4 5 6 1 2 3
3 1.00 1.00 0.00 -1.00 0.00 0.00 1.00
5 9.00 -1.00 1.00 2.00 5.00 0.00 0.00
2 4.00 0.00 0.00 1.00 1.00 1.00 0.00
-9.0 -1.0 0.0 -1.0 -2.0 -2.0 -1.0
-1.0 0.0 -1.0 -3.0 0.0 0.0
SENSITIVITY ANALYSIS
SHADOW PRICES ARE CHANGE IN OBJECTIVE FUNCTION VALUE PER UNIT CHANGE
IN THE RIGHT HAND SIDE CONSTANTS.
PENALTY COSTS ARE CHANGES IN THE OBJECTIVE FUNCTION VALUE PER UNIT INCREASE
IN THE NON-BASIC VARIABLES.
RANGES ON C(J) REPRESENTS LIMITING VALUES OF COST COEFFICIENTS THAT WILL NOT
CHANGE THE OPTIMUM SOLUTIONS.
RANGES ON B(I) REPRESENT LIMITING VALUES OF RIGHT HAND SIDE CONSTANTS THAT
WILL NOT CHANGE THE OPTIMUM BASIC VARIABLES.
NON-BASIC PENALTY
VARIABLES COST
4 1.000
6 1.000
1 3.000
ROW SHADOW
NUMBER PRICES
1 -1.000
2 0.000
3 -1.000
RANGES ON NON-BASIC C(J)
VARIABLE LOWER LIMIT
4 -1.000
6 -1.000
1 -2.000
RANGES ON BASIC C(J)
VARIABLE LOWER LIMIT UPPER LIMIT
5 -1.000 0.500
2 -999999.000 -1.000
3 -2.000 -0.000
RANGES ON B(I)
I LOWER LIMIT UPPER LIMIT
1 4.000 14.000
2 -3.000 999999.000
3 -0.000 5.000
PROGRAM PREPARED FOR THE SAINT MARY S TIME SHARING SERVICE (1981)
BY
D.E.MILLER & A.M.AGOSTINO
CONVERTED TO C (1994) BY P.D.SMITH
CRITICAL THINKING QUESTIONS:
1. Why can the simplex program fill in the coefficients (in the constraints – though not in the objective) of the initial basic variables? [Hint: Why must the variable columns appear in a specific order?]
2. There is a column of single digit numbers to the left of each solution tableau. What do these numbers represent and how are they helpful in reading the basic feasible solutions represented by each tableau?
3. Using information from the last (optimal solution) tableau and from the initial tableau, write B , D , CB , CD , B-1
[B-1 should be really easy], B-1D and CBTB-1D - CDT . [The very bottom row of the printout is the usual tableau bottom row]. What is the solution to this problem? What is the optimal value of the objective function?
4. There appear to be two bottom rows in each solution tableau. The lower of the two is the usual bottom row we obtain in using the simplex tableau (that is, CBTB-1A - CT). What does the extra row above it represent? (Hint: Compare the extra row to the standard last row and remember the bottom row in the initial tableau is - CT.)
5. Penalty costs and shadow prices [shown in the sensitivity analysis] will be covered in Section 3.7.
Penalty costs are associated with non-basic (in the optimal solution) variables and represent the unit cost – increase in the optimal value – if we forced the variable into the basis. This is closely related [but with opposite sign – cost instead of benefit] to the way we selected the entering variable for the next step in the simplex procedure]
Shadow prices go with constraints (rows of the tableau) – but teach constraint is matched with a slack/surplus variables. The shadow price represents the effect on the optimal value of easing the corresponding constraint by one unit (which would make the slack/surplus variable positive) [Note: the shadow price of a non-zero slack/surplus variable is always 0].
The values are given in the “Sensitivity Analysis” portion of the output. Can you find where these values [or, perhaps, their negatives] are shown in the optimal tableau (associated with the appropriate column, of course)?
EXERCISE:
1. Set up example 1.16 on p. 43 [The Furnco problem] as a linear programming problem in standard form [you need only to put it in standard form - tableau is not necessary].
2. Solve this problem using the Simplex program on Jade. Be sure to request that all tableaus and the sensitivity analysis be printed.
Save your solution - you will need it for next class.