This Matlab code illustrates the solution of a multivariable constraint optimization using linear programming. Executing the code REQUIRES access to the Optimization Toolbox!
First identify the variables:
Objective function to be maximized (total yield)
z = 400*x1+200*x2+250*x3;
Define the constraint coefficient matrix A and the vectors representing the constraint inequalities/equalities [See help document for the linprog MATLAB command.]
clear all, close all, clc f = [400;200;250]; % coeffients of linear objective function A = [3 1 1.5; 0.8 0.2 0.3; 1 1 1]; b = [1000;300;625]; % RHS of inequality constraints
This is one (efficient) method for the linear programming task. Note that linprog minimizes the objective function, which means that for maximization one needs to replace f with -f.
format bank
[x,fval,exitflag,output,lambda] = linprog(-f,A,b);
x, fmax=-fval
Optimization terminated. x = 128.86 261.57 234.58 fmax = 162500.00
Slack variables (Large Scale Method)
b-A*x
ans = 0.00 74.23 0
Shadow Prices
shadowprices = lambda.ineqlin
shadowprices = 100.00 0.00 100.00
Alternately, one can employ the simplex method explicitly [Expect 'different' optimal values for x.]
options = optimset('LargeScale','off','Simplex','on'); lb=[0;0;0]; [x,fval,exitflag,output,lambda] = ... linprog(-f,A,b,[],[],lb,[],[],options); x, fmax=-fval
Optimization terminated. x = 187.50 437.50 0 fmax = 162500.00
Slack variables (Simplex Metod)
Slack = b-A*x
Slack = 0 62.50 0
Shadow prices
shadowprices=lambda.ineqlin
shadowprices = 100.00 0 100.00
Notice that the two different methods yield the same maximum for the objective function, BUT different 'optimal' choice for the decision variables x1,x2,x3. The Large Scale method gives a 'better' value for the optimal slack value than the Simplex Method.
b = [1001;300;625]; lb=[0;0;0]; [x,fval] = linprog(-f,A,b,[],[],lb,[],[],options); x, fmax_new=-fval Gain = fmax_new-fmax Slack = b-A*x
Optimization terminated. x = 188.00 437.00 0 fmax_new = 162600.00 Gain = 100.00 Slack = -0.00 62.20 0
Conclusion: Relaxing the constraint on the water resource (by 1 unit) will cause an increase in total yield of $100 (exacly the shadow price computed earlier).
f = [450;200;250]; b = [1000;300;625]; lb=[0;0;0]; [x,fval] = linprog(-f,A,b,[],[],lb,[],[],options); x, fmax_new=-fval Gain = fmax_new-fmax Slack = b-A*x shadowprice_new = lambda.ineqlin
Optimization terminated. x = 187.50 437.50 0 fmax_new = 171875.00 Gain = 9375.00 Slack = 0 62.50 0 shadowprice_new = 100.00 0 100.00
Conclusion: In case of a higher yield for corn ($450 instead of $400), the increase in total yield is 50*x1=9375. Yhere is no change in the slack variables. Note the change in the shadow prices.
f = [400;200;260]; b = [1000;300;625]; lb=[0;0;0]; [x,fval] = linprog(-f,A,b,[],[],lb,[],[],options); x, fmax_new=-fval Gain = fmax_new-fmax Slack = b-A*x
Optimization terminated. x = 41.67 0.00 583.33 fmax_new = 168333.33 Gain = 5833.33 Slack = 0 91.67 0
Conclusion: In case of a higher yield for oats ($260 instead of $250), there is a significant change in the 'optimal' decision variables. More oats and less corn should be planted.
f = [400;200;250]; A = [2.5 1 1.5; 0.8 0.2 0.3; 1 1 1]; b = [1000;300;625]; lb=[0;0;0]; [x,fval] = linprog(-f,A,b,[],[],lb,[],[],options); x, fmax_new=-fval Gain = fmax_new-fmax Slack = b-A*x
Optimization terminated. x = 250.00 375.00 0 fmax_new = 175000.00 Gain = 12500.00 Slack = 0 25.00 0
Adjust the constraints to accomodate a new crop
f = [400;200;250;200]; A = [3 1 1.5 1.5; 0.8 0.2 0.3 0.25; 1 1 1 1]; b = [1000;300;625]; lb=[0;0;0;0]; [x,fval] = linprog(-f,A,b,[],[],lb,[],[],options); x, fmax_new=-fval Slack = b-A*x
Optimization terminated. x = 187.50 437.50 0 0 fmax_new = 162500.00 Slack = 0 62.50 0