  # 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 built-in 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' built-in 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 m-file (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

x = [1 10]';

% We can perform the optimization with different number of
% iterations or tolerances
options = optimset('MaxFunEvals', 2000, 'TolX', 1e-2);
[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
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
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'  