 Home
WelcomeBasicsPlots and GUIApplicationsOther

Linear
Programming  (as an optimization problem)

Matlab is well suited to handle the so
called linear programming
problems. These are problems in which you have a quantity, depending
linearly on several variables, that you want to maximize or minimize
subject to several constraints that are expressed as linear inequalities
with the same variables.
Sometimes the number of variables and the number of constraints are
high, or the 
constraints in the linear inequalities or the expression
for the quantity to be optimized may be numerically complicated.
We will illustrate the method of linear programming by means of a
simple example giving a numerical
solution. Matlab has some special functions such as 'simlp' or 'linprog' to tackle
down this type of problems, but these builtin functions are not always
available since they belong to special toolboxes (Simulink or Optimization
toolboxes). Therefore, we are going to formulate the problem as an
optimization issue, and we'll use the instruction 'fminsearch', which
is an always available instruction.
Let's suppose that a merry farmer has 75 roods (4 roods = 1 acre) on
which to plant two crops: wheat and corn. To produce these crops, it
costs the farmer (for seed, water, fertilizer, etc. ) $120 per rood for
the wheat, and $210 per rood for the corn. The farmer has $15,000
available for expenses, but after the harvest the farmer must store the
crops while awaiting favorable or good market conditions. The farmer
has storage space for 4,000 bushels. Each rood yields an average of 110
bushels of wheat or 30 bushels of corn. If the net profit per bushel of
wheat (after all the expenses) is $1.30 and for corn is $2.00, how
should the merry farmer plant the 75 roods to maximize profit?
We begin by formulating the linear programming problem mathematically.
We express the objective
(profit)
and the constraints.
Let x
denote the number of roods allotted to wheat and y the number of
roods allotted to corn. Then the expression to be maximized is clearly
P
= (110)(1.3)x
+ (30)(2)y
= 143x + 60y
There are some constraint inequalities, specified by the limits on
expenses, storage and roodage. They are:
and naturally:
As we mentioned before, we are going to formulate this as an optimization problem
using the 'fminsearch'
builtin function.
In Matlab, the instruction works as follows:
X = FMINSEARCH(FUN,X0,OPTIONS) minimizes with the default optimization
parameters replaced by values in the structure OPTIONS, created with
the OPTIMSET function. FMINSEARCH uses these options: Display,
TolX, TolFun, MaxFunEvals, MaxIter, FunValCheck, and OutputFcn.
This is one possible approach for our objective function, which is
saved as an mfile (in this case 'OF_P.m'):
function OFValue = OF_P(x)
% Here we
embed the constraints or inequalities.
% If the
constraints are not met, we penalize the optimization by
% giving an
arbitrary high value to the objective function.
if 120 * x(1) + 210 * x(2) > 15000 ...
110 * x(1) + 30 * x(2) > 4000 ...
x(1) + x(2) > 75  ...
x(1) < 0 ...
x(2) < 0
OFValue = 10;
return
end
% fminsearch
tries to minimize the function, so we invert its sign
P = 143 * x(1) + 60 * x(2);
OFValue = P;
Then, we can call it from another script, which includes the 'fminsearch'
function calling the objective function file (in 'OF_P'):
clear; clc;
format bank
% We have to
start with a 'seed' for the search
x = [1 10]';
% We can
perform the optimization with different number of
% iterations
or tolerances
options = optimset('MaxFunEvals', 2000, 'TolX', 1e2);
[x_opt, FunVal, EF, output] = fminsearch('OF_P', x, options)
% Finally, we
display the profit using the found solution
P = 143 * x_opt(1) + 60 * x_opt(2)
And the Matlab response is:
x_opt =
21.87
53.12
FunVal =
6315.62
EF =
1.00
output =
iterations: 121.00
funcCount: 243.00
algorithm: 'NelderMead simplex direct search'
message: [1x196 char]
P =
6315.62
This means that the farmer should consider 21.87 roods for wheat, 53.12
roods for corn, and his profit would be $6,315.62.
It is important to notice that this is a numerical approximation,
which means that if we start with another 'seed' or use other
parameters in the 'options'
set, we can get to another result. The number found is a possible
solution, but there's no guarantee that it is the best one, according
to tolerances
or to number of iterations
or evaluations desired.
For example, we can use the seed 'x = [10 10]' instead (without moving
any other instruction), and the Matlab answer now is:
x_opt =
32.31
14.88
FunVal =
5512.50
EF =
1.00
output =
iterations: 75.00
funcCount: 151.00
algorithm: 'NelderMead simplex direct search'
message: [1x196 char]
P =
5512.50
Now, the 'best' profit found is only $5,512.50. So, it is a good idea
to try with several 'seeds'
and different parameters in the 'options'
set to compare with and select the best solution. Most of the times the
solutions will be very close (at least for linear programming problems).
From
'Linear Programming'
to home
From
'Linear
Programming' to 'Linear Algebra'


