Maple Tutor
Part 12: The Simplex
Package
Here we introduce the main features
of Maple's simplex package, which solves linear programming problems like those
in Part 11. We will illustrate this, first step-by-step, then all-at-once, using
Problem A:
Find values of x
and y that maximize z = 120x + 100y
subject to the restrictions
| 2x + 2y <
8 |
| 5x + 3y < 15 |
| x > 0,
y > 0. |
- To avoid conflicts with variables and commands already entered, use the
command
restart;
to tell Maple to forget everything. Then enter
with(simplex);
to load the simplex package. Using a semicolon rather than a colon displays
the names of the new commands being defined. In particular, note that one
of those commands is display, which means
something very different now from what it meant in the plots package.
- Next enter
constraintsA:=[2*x+2*y<=8, 5*x+3*y<=15];
Note two differences from the way we entered constraints in Part
11: We are not including the nonnegativity constraints, and we are using a
list rather than a set. Neither of these changes is necessary for using simplex
commands, but this format will make it easier to keep track of what is going
on. Now enter
display(%);
The function of display is to show the constraints in matrix-vector form.
By using a list, we have forced Maple to respect the order of our inequalities,
but we can't force it to keep the variables in the same order -- so the first
column belongs to y and the second to x.
- Our next three commands are
C1:=setup(constraintsA);
basis(%);
display(C1);
The first of these converts the constraints to a list of equations
by inserting slack variables, _SL1
and _SL2. The second identifies the slack
variables as the basic variables at this stage. And the third displays
the new list of equations in matrix form -- without the vector of variables.
Look closely at the matrix -- which columns belong to each
of the variables x, y,
_SL1, and
_SL2 ?
- Now we define the objective
function:
objA:=(x,y)->120*x+100*y;
and we ask Maple to decide which variable determines the first pivot column:
pivotvar(objA(x,y));
The pivot operation is going to exchange one basic and one nonbasic variable
-- that is, y will become basic and one of the slack variables
will become nonbasic. The choice of which slack variable is determined
by picking a pivot equation:
pivoteqn(C1,y);
You will learn the criteria for making these decisions when you study the
simplex algorithm. Carry out the pivot operation:
C2:=pivot(C1,y,%);
If you wish, you can check the basis in
C2 and/or display the new list of equations
in matrix form.
- We have completed one step of the simplex algorithm now -- to see what it
means, we need to express the objective function in terms of the current nonbasic
variables. That is, we need to substitute for
y its
expression in terms of x
and
_SL1 -- which you can
do by copying and pasting from C2:
objA(x,-1/2*_SL1+4-x);
The important part of the result is the constant term -- this is the value of
the objective function when the nonbasic variables are set to zero. Have we
reached the maximum yet? No, because x
still has a positive coefficient, which means the objective function will grow
if x
becomes basic (and therefore nonzero).
- You can carry out the next simplex
step by copying, pasting, and
editing commands from the preceding step:
pivotvar(%);
pivoteqn(C2,x);
pivot(C2,x,%);
objA(fill in for x, fill in for y);
At this point, the constant term should be the solution you know already from
Part 11, the coefficients in the objective function should be negative (meaning
the maximum occurs when both slack variables are zero), and the corresponding
values of x
and y
should be the constant terms in the final equations (why?).
- Finally, we see that Maple can
carry out the simplex algorithm all at once:
maximize(objA(x,y),constraintsA);
objA(3/2,5/2);
The step-by-step procedure is useful for learning the simplex algorithm.
The maximize and minimize functions are useful once you understand how the
algorithm works.
