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. Many linear programming packages, including this one, assumes that unless told otherwise the variables must be non-negative.

Consider the following example with two constraints and two 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 next. We show the entire screen so that we can point out that a STEP tool now appears on the toolbar before the SOLVE tool. 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 options 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 contains the constraint coefficients, which typically are called the aijs . These may be positive or negative.

Right hand side ( RHS ) 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, a drop- down arrow appears in the cell as shown in the following screen in constraint 2 in the column with the constraint signs.

You can click on the arrow bringing in a drop down box as shown next.

The solution

Following is the solution to our example. Please note that the display varies somewhat according to the textbook option selected in Help, User information.

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.

The graph

One of the other output displays is a graph as shown in the following screen. 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.'

Table of ranges

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; only the objective function value (profit or cost) 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.

Iterations

The iterations can also be displayed. The tableau style varies according to the textbook selected.

Solution list

It is also possible to display the solution in a list as shown next.

Stepping

If you look at the first screen at the top of this section notice that to the left of the SOLVE tool a STEP tool 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 follows. (The display varies according to the text set in Help, User information.)

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, press the STEP tool. If you want to change the pivot column, 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 as shown below. Since the software allows you to iterate even after finding the optimal solution, when you are done you must press the FINISH tool.