Procedures and a Maplet for Analyzing Linear Programming Problems
by P.H. Stikker (version: 07 May 2002)
Warning, the protected names maximize and minimize have been redefined and unprotected
Warning, the names changecoords and display have been redefined
What's new in this version (updated May 7, 2002)?
In this latest version a lot of additions are made, and mathematical enhancements. In below all of the changes in summary:
- Corner walk
There is now an extra button that allows the user to 'walk' around all corners of the feasible area
- Mark corners
In the 'plot options' screen is a new option 'Mark corners'. This option (when selected) shows the corners of the feasible area and marks them with a circle (also the size and color of the circle can be changed). - Range plot
For the range of the plot (xMin,xMax, yMin and yMax) is now a help window. In this window you can let the Maplet/Maple calculate all corners of the feasible area and use these coordinates to set the range.
- Saving The problem of saving the constraints (and other options) as variables is solved. All possible interesting calculations/inputs can be saved now as variables.
- Starting the maplet Since I solved the saving problem, it is now possible to 're-run' the maplet by one single line ( LinEquations(): )
- The slider
The slider now has a range of -10000..10000 (instead of -10..10). This means the objective function can now be moved more fluent.
- Calculations
Although rounding is sometimes not preferred, I think most Maple users still prefer to see the decimal value than the fraction. Therefor there is now an option to select the amount of digits to be used at the starting screen.
- Small changes Some other changes have been made to improve the lay-out of the Maplet. All buttons now have a so called 'tooltip', there are a few more borders and the 'z-value' is now always shown on the right-top of the plot and doesn't show the comma anymore (i.e. [z=, 0.3] now is z=0.3) . Also the info-screen is not a seperate Maplet anymore, but has been 'integrated' in 'the main maplet'.
The new version has as a drawback that the plot in the first window becomes very small. If you are using a high-resolution screen or a big screen this shouldn't be a problem, since you can always adjust the size of the Maplet. In other cases I suggest to use the 'plot in new window' option.
Introduction
Gregory A. Moore wrote a worksheet to solve linear inequalities in 2 dimensions and solve linear programming problems of optimizing a function over these planar regions ( http://www.mapleapps.com/powertools/postsecondary/html/0301.html). In this worksheet I will show a couple of procedures that can solve these type of problems, along with a maplet . The Maplet is written by using Dutch names for the variables, but the maplet shows everything in English. If you have any suggestions please contact me at p.stikker@hsholland.nl
Procedures
In the following procedures in below, we will create a complete procedure showing all information possible from linear inequalities
Procedure 1
The region that we are interested in can also be shown each time by use of the following procedure: a, b, c and d are the desired x- and y-ranges over which to show the region.
Procedure 2
In the previous worksheet ( http://www.mapleapps.com/powertools/postsecondary/html/0301.html) the simplex method was used to calculate the answer. There are other ways to come to the answer. The first one is called the "Corner walk method". The idea is to substitute the coordinates of each corner of the region into the objective function. The highest value is then the answer. The problem with this approach is that the number of corners of the region grows exponentially with the number of inequality constraints. A graphical approach is also possible. You draw a line along which the objective function is constant. Then translate this line parallel until it is just about to leave the feasible region. At this point, the line will intersect a corner. This corner will be either a max or a min of the objective function over the region.
The following procedure uses the graphical approach with an animation. Click on the graph below and press the "Play" button in the animation tool bar above.
Procedure 3
What if we don't want to optimise but minimise the whole situation. A small change makes this possible:
Two extra's
Often a system of constraints represents the capacity of machines or departments. If someone outside the company would then like to rent this capacity he/she will have to offer a reasonable price. He/she wouldn't like to pay too much, but for the person who rents the capacity the price should still be good enough. This problem is called the dual problem and can be represented by Maple:
A second thing is the way we enter the constraints. Often the constraints look like: ax + by <= c, this is often called the standard form. Not always the constraints are written down in this way (i.e. ax + c <= -y or ax + by = c). Maple can show the standard form:
These two points we can easily add to our procedure:
Final procedure
The last procedure already looks pretty good, but there is small catch. If there is no maximum or minimum, the procedure won't work:
For this linear program, there is no minimum solution because the feasible region is unbounded in the direction , which has negative dot-product with the objective vector . See the region below.
Error, (in animate) Third argument must be a range in this case
By using some if-statements, we can get around this problem.
Now let's see if this does work:
The Maplet
I initialy wrote this Maplet using Dutch words. I only changed the names in the Maplet itself not the variables. It will therefore be hard to understand the programing but the Maplet itself shouldn't be any problem cause I changed everything into English.
Help procedures
GraphicSolMaplet
maximum
minimum
objfuncvalue
objfuncvalue2
dualproc
output
helpPlotRange
LinEquations
The Maplet itself
The main Maplet:
Let's go...
Before you can use the Maplet, we need to enter some initial values.
Let's go:
Initializing Java runtime environment.
If you have chosen the 'save' option you can recall all your variables by typing in the given names (the list is in the 'More info' screen):
Some final info
Use the procedures
The final procedure was: GraphicSol(a,b,c,d) . Hereby is 'a' the minimum x-value of the plot, 'b' the maximum y-value of the plot, 'c' the minimum y-value of the plot and 'd' the maximum y-value of the plot. The procedure can only work if you enter the restrictions first by putting them into a list called ' Constraints ' and the objective function as a variable called: ' Objective '. In below a final example:
Use the Maplet
The Maplet can be run by activating the line in below:
If you would like to use this Maplet more often you could try to create a package from it, or copy paste all the procedures into one big maple line. As it said on the saving-screen, if you clicked on the option save , you can re-run the Maplet and it will start with your previous entered conditions and objective function. Also the conditions and objective function are saved (as a string) and can be reviewed by using:
Comments/Future ideas
After writing all procedures I started working on the Maplet. I came across some problems during the programming, and solved most of them. Of course some programming could have been done in a simpler way looking at it afterwards, but it does works. Since I started with the procedures, the plot of the conditions is different in the Maplet. Problems/Future Ideas Problem 1 By email I was given a small problem I was unable to solve. The problem was to make the following text appear on the info screen: Point 1 You can only use x and y as variables Point 2 The objective function should have a*x+b*y+c as structure etc... Problem 2 I would like to solve is the label of the constraints in the plot. At this moment these are sometimes hard to read. Although the axes option helps often... Problem 3 I couldn't find a way to show an animation in the Maplet. Only by use of the slider I tried to get the closest to this. Unfortunately this means that sometimes the objective function cannot be shown exactly on the maximum or minimum point. Problem 4
Sometimes you have to click twice now, I don't know why this is and would like to solve the problem. Also the corner walk method sometimes skips a corner. Idea 1 At this moment the Maplet only shows planar problems. Perhaps an option to calculate optimal points with more variables can be nice. Idea 2 Creating a package that can run everything in one time..
At this time I think the Maplet and the procedures are useable enough. If you have any comment or usefull information for the problems and ideas please email me ( p.stikker@hsholland.nl). Hope you enjoyed the show, Your sincerely, P.H. Stikker