Using SIMPLEX

338 ACTIVITY 15: Using SIMPLEX 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 PIVOT procedure in Maple, it requires no interaction with the user except the specification of the coefficients of variables in the objective function and constraints. We will use this program to solve the second project linear programming problem for both Phase I and Phase II.

LEARNING OBJECTIVES:

Discover how to prepare the data for, run, and read the results of the Simplex program under Jade.
Observe and think about the sensitivity analysis section of the Simplex program output.
Discover how to maximize the learning done in groups.

PERFORMANCE CRITERIA:

Quality of the answers to the Critical Thinking Questions.
- Completeness
- Clarity
- Depth
Degree to which learning was improved through focused group effort.

RESOURCES:

Appendix A, Strategic Mathematics
30 minutes

PLAN:

Choose roles if you have not already done so.
Look over the model and answer the Critical Thinking Questions.
Set up problem 1.16 on page 48 as a linear programming problem in standard form.
Solve this problem using the Simplex program on Jade. Be sure to request that all tableaus and the sensitivity analysis be printed. To get to the $ UNIX prompt from the first E-mail Jade menu, choose the X option (instead of "m" for MAIL). The pico editor does not accept the delete key. You have to backspace to erase.

MODEL:

          minimize  -3x1 - 2x2
          subject to
                     2x1 + x2  <=  80         
                      x1 + x2  <=  50         
                         x1 >= 0,  x2 >= 0     

          Standard Form:
         minimize   -3x1 - 2x2                    
         subject to  2x1 + x2 + x3      = 80      
                      x1 + x2      + x4 = 50
          x1 >= 0,  x2 >= 0, x3 >= 0, x4 >= 0

Basic Variables x3, x4, Nonbasic Variables x1, x2

Once a problem is in standard form, we get onto Jade and open a pico editing session to prepare the input file. The following entries would be typed. The comments are not entered.

$pico filename    // You can replace filename by any name of your choosing
1,1               // This means that we are on the first problem of a total 
		  //	of 1 problem.
2,4,1,1           // This means we have 2 constraints and 4 variables, 
			and that we want all tableaus printed as well as the
                  //    sensitivity analysis.
3,4,1,2           // The basic variables are 3 and 4 and the nonbasic 
		  //	variables are 1 and 2.
0,0,-3,-2         // The coefficients of the objective function in the 
		  //	variable order from the previous line.
80,2,1            // Right hand side and nonbasic coefficients for 1st 
		  //	constraint.
50,1,1            //  "     "     "      "      "      "      "    2nd    ".

After hitting Ctrl X and agreeing to save the file, we type the following at the $ prompt:

$ /home/faculty/psmith/simplex < filename

// the computer prints the following four lines:

Completed reading the data
Finished printing tableau 1
Finished printing tableau 2
Finished printing tableau 3
$

We can then type pico ftn01 to see the results as follows:

                     PROBLEM NUMBER     1
                       ITERATION     1
 VARIABLE COSTS
     0.0000     0.0000    -3.0000    -2.0000

       SOLUTION          TABLEAU

                      3        4        1        2

 3       80.00     1.00     0.00     2.00     1.00

 4       50.00     0.00     1.00     1.00     1.00

         0.0        0.0      0.0      0.0      0.0

                    0.0      0.0      3.0      2.0


                       ITERATION     2

       SOLUTION          TABLEAU

                      3        4        1        2

 1       40.00     0.50     0.00     1.00     0.50

 4       10.00    -0.50     1.00     0.00     0.50

      -120.0       -1.5      0.0     -3.0     -1.5

                   -1.5      0.0      0.0      0.5


                       ITERATION     3

       SOLUTION          TABLEAU

                      3        4        1        2

 1       30.00     1.00    -1.00     1.00     0.00

 2       20.00    -1.00     2.00     0.00     1.00

      -130.0       -1.0     -1.0     -3.0     -2.0

                   -1.0     -1.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
              3                  1.000
              4                  1.000


             ROW               SHADOW
            NUMBER             PRICES
              1                 -1.000
              2                 -1.000


   RANGES ON NON-BASIC C(J)
          VARIABLE           LOWER LIMIT
              3                   -1.000
              4                   -1.000


   RANGES ON BASIC C(J)
          VARIABLE           LOWER LIMIT           UPPER LIMIT
              1                   -4.000                -2.000
              2                   -3.000                -1.500


   RANGES ON B(I)
              I              LOWER LIMIT           UPPER LIMIT
              1                   50.000               100.000
              2                   40.000                80.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:

These will be provided in class.

Math 338 Activity 15 -- Revised 10/13/98