ShowSimplexLinear Optimization |
and Documentation |
| 2x1+ 3x2+ 4x3+ 7x4 <=4600 | (Constraint C1: Type is <=inequality) |
| 3x1+ 4x2+ 5x3+ 6x4 <=5000 | (Constraint C2: Type is <=inequality) |
| 1x4 >=400 | (Constraint C3: Type is >=inequality) |
| 1x1+ 1x2+ 1x3+ 1x4 =950 | (Constraint C4: Type is =equality) |
| x1>=0,x2>=0,x3>=0,x4>=0 | (Default non-negativity constraints) |
All the expressions are linear: there are no products like x1*x2 or x3*x3 or forms like cosine(x1). So mathematically at least the functional forms are simple. The objective function coefficients c1, c2, c3, c4 are sometimes called costs. The 4 constants the b1, b2, b3, b4 -- the Right Hand Sides of the inequality-equality constraints are sometimes abbreviated RHS. So, in this sample problem, there are:
Solution: x1=0, x2= 400, x3=150, x4= 400 with z= 6650.
ShowSimplex also displays the classical Sensitivity Analysis Reports : these show how sensitive the solutions are with respect to changes in the objective function coefficients and the RHS constants. (This means that you do not have to run ShowSimplex again to see new values for the variables or objective function after making changes to a coefficient or a RHS. These sensitivity analysis reports were developed in early days when computing resources were very expensive.)
Some classical applications of linear programming are in the sample Excel ShowSimplex Workbook. The workbook contains linear programming problem formulations and ShowSimplex representations for
So if you need to find x* that minimizes f(x), then just find an x* that maximizes -f(x). To minimize an objective function, just maximize its negation and keep everything else the same.
An example of an optimization problem that is more naturally expressed in terms of "Minimizing and objective function" is the diet problem: we want to find the minimum amount of food components needed to meet certain dietary requirements (see the ShowSimplex Workbook).
| How many variables? |
Note: Maximum Number of Variables: 60 |
|
How many "<=" constraints? |
|
|
How many ">=" constraints? |
|
|
How many "=" constraints? |
Note: Maximum Number of All Constraints: 60 |
Here is a text file containing the above linear programming representation table in tab-delimited text.
Here is a Microsoft Excel file containing the table in tab-delimited text.
0 4 6 7 8represents the objective function z= 0 + 4x1 + 6x2 + 7x3. Note that the constant (in this case 0), is in the first column. The subsequent rows represent the constraints. Note that the ShowSimplex convention requires that all constraints be grouped according to type and order: first we put the <= constraints; second, the >= constraints; third, the = constraints. The second row
4600 -2 -3 -4 -7is the C1 constraint 2x1+ 3x2+ 4x3+ 7x4 <= 4600. It is the first <= constraint. Note that the RHS, 4600 is in the first column. Also note that in the ShowSimplex convention, the constraint coefficients are all negated. The third row
5000 -3 -4 -5 -6is the C2 constraint 3x1+ 4x2+ 5x3+ 6x4 <= 5000. It is the second <= constraint. Note that the RHS, 5000 is in the first column. Also note that in the ShowSimplex convention, the constraint coefficients are all negated. The fourth row
400 0 0 0 -1is the C3 constraint 1x4 >= 400. It is the first and only >= constraint. Note that the RHS, 5000 is in the first column. Also note that in the ShowSimplex convention, the constraint coefficients are all negated. The fifth row
950 -1 -1 -1 -1is the C4 constraint x1+ x2+ x3+ x4 = 950. It is the first and only = constraint. Note that the RHS, 950 is in the first column. Also note that in the ShowSimplex convention, the constraint coefficients are all negated.
If you want to try a sample run,
click here .
4 Variables; 2 <= Constraints; 1 > = Constraints; 1 = Constraints.
The table has 5 Rows and 5 Columns.
...and Outputs
The first ShowSimplex output is the web page that appears after you press
the Grab Constraints button. It is a confirmation page that verifies that the
input problem is the one you want to solve. In the above sample problem,
the page looks like this:
Step 2: Verify the specification you submitted:
| Const. | X1 | X2 | X3 | X4 |
| 0.00 | 4.00 | 6.00 | 7.00 | 8.00 |
| 4600.00 | -2.00 | -3.00 | -4.00 | -7.00 |
| 5000.00 | -3.00 | -4.00 | -5.00 | -6.00 |
| 400.00 | 0.00 | 0.00 | 0.00 | -1.00 |
| 950.00 | -1.00 | -1.00 | -1.00 | -1.00 |
Sample Problem
Press for Step 3: Find the Maximum z by running the Simplex Algorithm
You are allowed to use ShowSimplex 28 more times over a period of 30 more days.
| Var. | Optimal Value |
| x2 | 400.00000 |
| x3 | 150.00000 |
| x4 | 400.00000 |
| Var. | Reduced Cost |
| x1 | 1.00000 |
| Constraint | Slack Value |
| Cons 2 | 250.00000 |
| Constraint | Shadow Price |
| Cons 1 | 1.00000 |
| Cons 3 | -2.00000 |
| Cons 4 | 3.00000 |
| Constraint# | ALLOW inc | ALLOW dec | RHS (b) |
| Cons 1 | 250.00000 | 150.00000 | 4600.00000 |
| Cons 2 | INF | 250.00000 | 5000.00000 |
| Cons 3 | 37.50000 | 125.00000 | 400.00000 |
| Cons 4 | 50.00000 | 100.00000 | 950.00000 |
| Coefficient# | ALLOW inc | ALLOW dec | Coef.(c) |
| c1 | 1.00000 | INF | 4.00000 |
| c2 | 0.66667 | 0.50000 | 6.00000 |
| c3 | 1.00000 | 0.50000 | 7.00000 |
| c4 | 2.00000 | INF | 8.00000 |
| b | SL4 | x1 | SL3 | SL1 | |
| z | 6650.000 | 3.000 | -1.000 | -2.000 | -1.000 |
| x3 | 150.000 | -3.000 | 1.000 | -4.000 | -1.000 |
| SL2 | 250.000 | -1.000 | 0.000 | 2.000 | 1.000 |
| x4 | 400.000 | 0.000 | 0.000 | 1.000 | 0.000 |
| x2 | 400.000 | 4.000 | -2.000 | 3.000 | 1.000 |