[Home] [Puzzles & Projects] [Delphi Techniques] [Math Topics] [Library] [Utilities]
LP_Solve is a Mixed Integer Program solver which is callable from many languages. Here's a Delphi program which solves several sample LP problems and allows others to be entered and solved.
Background & Techniques
This program provides a Delphi user friendly interface to
LP-Solve, a free linear programming tool available from
Linear programming is a technique for solving a large class of optimization problems which can be described by a set of linear equations. For example,
A potter is making cups and plates. It takes her 6 minutes to make a cup and 3 minutes to make a plate. Each cup uses 3/4 lb. of clay and each plate uses one lb. of clay. She has 20 hours available for making the cups and plates and has 250 lbs. of clay on hand.She makes a profit of $2 on each cup and $1.50 on each plate. How many cups and how many plates should she make in order to maximize her profit?
Let variable names "Cups" and "Plates" signify then number of cups and plates produced. The problem is to maximize the profit, 1.5*Cups + 2*Plates, with the constraints:
To solve this problem with LP_Solve, we just need to pass it the variable coefficients for the profit equation and coefficients and the limit for each of the constraints. The table has a column for each variable and a row for the "objective function" followed by a row for each constraint. The LPDemo version looks like this:
LPDemo takes this table, passes the information to LP_Solve, and produces the following output from the LP_Solve results.
I used version 5.1 of the solver because the latest version (5.5) doesn't seem to have all the files available, specifically LPSolve51.pas a Delphi interface to the API functions available in LPSolve51.dll. Both files are included in the source distribution below. LPSolve51.dll is dynamically linked at execution time and is also included in the executable download.
The "Cases" page displays the initial sample program. The word description of
the problem occupies the top portion of the page. The table
describing the variables, the problem objective and the constraints appears at
the bottom of the page. The "Solve" button transfers the
Addendum Feb 1, 2011: A small change to the LoadString (in Loadcase) and SaveString (in SaveCase) procedures today makes the program compliable with both Delphi 7 and Delphi XE (Actually Delphi versions prior to Delphi 2009 and Delphi 2009 and later versions. Earlier versions generate "AnsiString" types by default using one byte per character, later versions create "Uniocde" strings by default which use 2 bytes per character. LPDemo uses TFileStream controls to save and reload cases. Streaming methods are not very smart about data types, they just require a count of the number of bytes to write and the starting address to save from or load into. You can see the problem if cases saved with ANSI strings are read back later as Unicode strings. All of the sample cases included with LPDemo were created with ANSIStrings so the change today forces strings to be written and read as ANSI strings regardless of the Delphi version. The ANSI strings are converted to or from the default string format regardless of whether the default string type is the long or short version. LPDemo was reposted as Version 2.1.
Suggestions for Further Explorations
Copyright © 2000-2013, Gary Darby
All rights reserved.