As of October, 2016, Embarcadero is offering a free release
of Delphi (Delphi
10.1 Berlin Starter Edition ). There
are a few restrictions, but it is a welcome step toward making
more programmers aware of the joys of Delphi. They do say
"Offer may be withdrawn at any time", so don't delay if you want
to check it out. Please use the
link to let me know if the link stops working.
Support DFF - Shop
If you shop at Amazon anyway, consider
using this link.
We receive a few cents from each
Support DFF - Donate
If you benefit from the website, in terms of
knowledge, entertainment value, or something otherwise useful,
consider making a donation via PayPal to help defray the
costs. (No PayPal account necessary to donate via credit
card.) Transaction is secure.
For over 15 years
Mensa Page-A-Day calendars have provided several puzzles a year
for my programming pleasure. Coding "solvers" is most fun,
but many programs also allow user solving, convenient for "fill
in the blanks" type. Below are Amazon links to the
two most recent years.
365 Puzzlers Calendar 2017
365 Puzzlers Calendar 2018
(Hint: If you can
wait, current year calendars are usually on sale in January.)
e-mail with your comments about this program (or anything else).
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
http://tech.groups.yahoo.com/group/lp_solve/. The Yahoo site requires
group membership to access files but the site has more of the files needed than
does the SourceForge site which seems only to include an executable version of
the solver.. I have downloaded and included all of the necessary files for this
demo in the downloads below. For programmers, the documentation for using LP-Solve
features is available at
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:
|Amount of clay used cannot exceed 250 pounds: 0.75*Cups + Plates <=250|
|Amount of time used cannot exceed 20 hours:
0.1*Cups+.05*Plates <= 20|
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.
Optimum variable values are:
Cups = 120.000
Plates = 160.000
2.000 * Cups + 1.500 * Plates = ???
2.000 * 120.000 + 1.500 * 160.000 = 480.000
0.750 * Cups + 1.000 * Plates <= 250.000
0.750 * 120.000 + 1.000 * 160.000 = 250.000
0.100 * Cups + 0.050 * Plates <= 20.000
0.100 * 120.000 + 0.050 * 160.000 = 20.000
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
information form the table to the record format required by LP_Solve and calls
its "Solve" function to attempt a solution. Results appear
below the problem description in that display.
The "Load" button will load text and detailed information for several sample
cases included. The "Save" button saves the text and problem
detail to a file. If you want to modify the sample problems or define your own,
here are some details:
Only the basic options available in LP_Solve are implemented here. You can
specify the number of variables and the number of
constraints to change the size of the table. You can also specify whether to
look for the maximum or minimum for the objective function.
The objection function is the expression describing the quantity to be
optimized. The top row of the table is reserved for names of the
variables. The row below that defines the objective. Each following row defines
a constraint. The first column is reserved for names of
the constraints. Columns to the right define coefficients for each of the
variables in the objective function and each of the constraint
equations. The next to last column contains the relation of the constraint to
the constant contained in the rightmost column. Allowed
relation operators are ">=", "<=", or "=". For the objective row, the final 2
columns should remain as "= ???".
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.
Running/Exploring the Program
Suggestions for Further Explorations
||Add additional LP_Solve options to assign other
variable types (Integer, Semi-continuous, Special order), additional search
|Original: January 30, 2011
July 29, 2017