Linear Programming 
| 1. Introduction | 2. Example | 3. Main Menu | 4. Printing | 5. Graphs | 6. Modules |
Linear Programming Any linear program is defined by the number of variables and the number of constraints. Do not count the non-negativity restrictions as constraints. Almost any linear programming package, including this one, assumes that unless told otherwise the variables must be non-negative.
Consider the following example with 2 constraints and 2 variables.
maximize 3x + 3y
subject to 3x + 4y <= 14 (labor hours)
6x + 4y <= 15 (lbs material)
x, y >= 0
The data screen for this appears below. We show the entire screen so that we can point out that a [STEP] button now appears on the command bar between [PRINT SCREEN] and [SOLVE]. Also STEP is enabled in the FILE menu.
Objective function. The choice of minimization or maximization is made in the usual way at the time of problem creation but it can be changed on the data screen using the objective box above the data.
Objective function coefficients. The cost/profit coefficients (typically referred to as cj) are entered as numerical values. These coefficients may be positive or negative.
Constraint coefficients. The main body of information are the constraint coefficients which typically are called the aijs. These coefficients may be positive or negative.
Right hand side coefficients. The values on the right hand side of the constraints are entered here. These are also termed the bis. These must be non-negative.
The constraint sign. This can be entered in one of two ways. It is permissible to press the [<] key, the [>] key or the [=] key. Alternatively, when you go to a cell with the constraint sign then a drop down arrow appears in the cell as shown below in constraint 2 in the column with the constraint signs.
You can click on the arrow bringing in a drop down box as shown below.
Given below is the solution to our example. Please note that the display varies somewhat according to the textbook option selected.
Optimal values for the variables. Underneath each column the optimal values for the variable are given. In this example x should be .33 and y should be 3.25.
Optimal cost/profit. In the lower right hand corner of the table the maximum profit or the minimum cost is given. In this example the maximum profit is $10.75.
Shadow prices. The shadow (or dual) prices appear on the right of each constraint. In this example we would pay .5 more for one more unit of resource 1 and .25 more for one more unit of resource 2.
One of the other output displays is a graph as shown below. The feasible region is shaded in. On the right is a table of all of the feasible corner points and the value of the objective function (Z) at those points. In addition the constraints and objective function can be highlighted in red by clicking on the option buttons on the right under 'Constraint Display'.
In addition to listing the values we have provided additional information about the variables. The interpretation of the additional information is left for your textbook. In the example, you can see the reduced cost, original objective value coefficient and the lower and upper limit (the range) over which the solution will be the same. That is, the variables will take on the same values of .333 and 3.25 and only the objective value will change.
Note: Some texts and other programs give the allowable decrease and increase (from the original value) rather than the upper and lower limits on the ranges.
The iterations can also be displayed. The tableau style varies according to the textbook selected.
It is also possible to display the solution in a list as shown below.
If you look at the first screen at the top of this section notice that between the PRINT SCREEN button and the SOLVE button a STEP button appears.
While the iterations are available in the iteration output screen it also is possible to step through and see the iterations one at a time. The major advantage of stepping is that you can select the entering variable. We have pressed [STEP] and the screen appears as below.
The software has created a simplex tableau adding two slack variables. The first column is highlighted since it has the highest profit contribution. If you want this column then press the [STEP] button. If you want to change the pivot column then simply click on a different column and then press [STEP].
When the optimal solution is found a message to that effect will appear in the instruction bar.
Since the software allows you to iterate even after finding the optimal solution when you are done
you must press the [FINISH] button to see the usual results.
| 1. Introduction | 2. Example | 3. Main Menu | 4. Printing | 5. Graphs | 6. Modules |
 |
©
Prentice-Hall, Inc. A Simon & Schuster Company Upper Saddle River, New Jersey 07458 |