Optimization Using Matlab
Mamata Jenamani
Associate Professor
Department of Industrial engineering and Management
IIT Kharagpur
General Structure of a Mathematical
Programming (Optimization) Problem
•Based on the description of the function f and the feasible
set M, the problem can be classified as linear, quadratic,
non-linear, non-linear, multiple-objective, discrete
optimization problem etc.
Linear Programming Problem
•If the objective function f and the defining functions of
M are linear, then the problem will be a linear
optimization problem.
•Example: Transportation problems, network flow
problems
A linear programming problem
Wyndor Glass Co. Product Mix Problem
Wyndor Glass Co. Product Mix Problem
• Wyndor has developed the following new products:
– An 8-foot glass door with aluminum framing.
– A 4-foot by 6-foot double-hung, wood-framed window.
• The company has three plants
– Plant 1 produces aluminum frames and hardware.
– Plant 2 produces wood frames.
– Plant 3 produces glass and assembles the windows and doors.
• The Problem
1. Should they go ahead with launching these two new products?
2. If so, what should be the product mix?
A linear programming problem
• Identification of the relevant data
Wyndor Glass Co. Product Mix Problem
– No. of hours available in each plant
– Production time (in hours) required for each batch
in each plant
– Profit per batch
Doors Windows
Unit Profit $300 $500
Hours
Hours Used Per Unit Produced Available
Plant 1 1 0 4
Plant 2 0 2 12
Plant 3 3 2 18
A linear programming problem
Formulate the problem
Let D = the number of doors to produce
W = the number of windows to produceDecision Variables
Maximize P = $300D + $500W
Objective
subject to
D≤4
2W ≤ 12 Constraints
3D + 2W ≤ 18
and
D ≥ 0, W ≥ 0.
The feasible region
Production rate for windows
W
10
3 D + 2 W = 18
8
D=4
6 2 W =12
Feasible
region
2
0 2 4 6 8 D
Production rate for doors
Finding the Optimal Solution
Production rate W
for windows
8
P = 3600 = 300D + 500W
Optimal solution
P = 3000 = 300D + 500W 6 (2, 6)
Feasible
4
region
P = 1500 = 300D + 500W
0 2 4 6 8 10 D
Production rate for doors
Linear Programming in Matlab
Input Arguments
Output Arguments
Algorithms
A simplex algorithm, Active-set algorithm (Medium scale problems, dense matrix
structure)
For
• Primal-dual interior details
point see:
method docscale
(Large linprog
problems, sparse matrix structure)
Linear Programming in Matlab
Setting Options
>>optimset(’linprog’) %To see the options for linprog
% General format to set the options
>>options=optimset(’ParameterName1’,value1,’ParameterName2’,val
ue2,..)
% Example
>>options=optimset(’LargeScale’,’off’,’Simplex’,’off’)
Find the default options for options for linprog
Linear Programming in Matlab
Run the solved problem
Find X that minimizes
f(x) = –5x1 – 4x2 –6x3,
subject to
x1 – x2 + x3 ≤ 20 Write a program
3x1 + 2x2 + 4x3 ≤ 42 yourself and solve
3x1 + 2x2 ≤ 30
0 ≤ x1, 0 ≤ x2, 0 ≤ x3
Non-linear Programming Problem
Application of such problems arise frequently in the
numerical solution of control problems, non-linear
approximation, engineering design, finance and economics,
signal processing, etc.
Unconstrained Optimization in Matlab
•fminunc.m - when the function f, to be minimized, has at
least a continuous gradient vector. The fminunc.m uses
descent direction methods which are known as quasi-
Newton methods alongwith line search strategies based
on quadratic or cubic interpolations.
[x,fval,exitflag,output,grad,hessian]=fminunc(fun,x0,optio
ns)
•fminsearch.m - when the function f has no derivative
information, or has discontinuities or if f is highly non-
linear
[x,fval,exitflag,output]=fminsearch(fun,x0,options)
Unconstrained Optimization in Matlab
Minimize the function f (x) = 3x12 + 2x1x2 + x22
Create a file containing the function
function f = myfunUNC(x)
f = 3*x(1)^2 + 2*x(1)*x(2) + x(2)^2; % Cost function
Then call fminunc/fminsearch to find a minimum near an
initial point:
x0 = [1,1];
[x,fval] = fminunc(@myfunUNC,x0);
Unconstrained Optimization in Matlab
Solve the following problems:
Constrained Optimization in Matlab
•fmincon.m :fmincon attempts to find a constrained
minimum of a scalar function of several variables starting
at an initial estimate.
•[x,fval,exitflag,output,lambda,grad,hessian]=
fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options)
min f ( x ) x1 3 x2 3
2 2
function
s.t .g1 2 x1 x22 1 0 y=examp_FUN_fmincon(
g 2 9 0.8 x12 2 x2 0 x)
y=(x(1)-3)^2+(x(2)-3)^2;
function [c,ceq]=examp_NONLCON_fmincon(x)
ceq=[];
c(1)=-2*x(1)+x(2)^2+1;
c(2)=0.8*x(1)^2+2*x(2)-9;
Constrained Optimization in
Matlab
Find values of x that minimize f(x) = –x1x2x3,
starting at the point x = [10;10;10], subject to the
constraints:
0 ≤ x1 + 2x2 + 2x3 ≤ 72
Binary Integer Programming in Matlab
bintprog uses a linear programming (LP)-based branch-
and-bound algorithm to solve binary integer programming
problems.
[x,fval,exitflag,output]
Minimize the function =f(x) = –9x1 – 5x2 – 6x3 – 4x4
bintprog(f,A,b,Aeq,Beq,x0,options)
subject to the constraints
where x1, x2, x3, and x4 are binary integers,
f = [-9; -5; -6; -4]; A = [6 3 5 2; 0 0 1 1; -1 0 1 0; 0 -1 0 1]; b = [9; 1;
0; 0];
x = bintprog(f,A,b)
Binary Integer Programming in Matlab
Four projects are available Project Investment Revenue
1 3 5
for investment by certain
2 5 8
company. Total amount 3 2 3
available for investment is 15 4 6 7
crores of rupees. The 5 2 5
investments required by the 6 6 8
projects and the revenues 7 2 5
8 4 6
generated from the projects
9 3 8
(in crores of rupees) are 10 5 10
shown below. Which of
these projects the company
must select?
Quadratic Programming
Matlab Function
Algorithms Used
1. Active-set strategy (Medium-Scale),
2. Interior reflective Newton method coupled with a trust region
method (Large scale problem)
Example: Least squares approximation problem
Matlab
General Formulation Specific Example
(Run solved problem)
Write a program yourself to solve the following problem
Mixed integer programming in Matlab
x=
ga(fitnessfcn,nvars,A,b,Aeq,Beq,LB,UB,nonlcon,IntCon,option
s) Winder glass product mix problem with integer constraints
A=[1 0;0 2; 3 2];
b=[4;10;19];
objfun=@(x)(-3*x(1)-5*x(2));
x = ga(objfun,2,A,b,[],[],[0;0],[inf;inf],[],[1
2])
References
Abebe Geletu. Solving Optimization Problems using
the Matlab Optimization Toolbox - a Tutorial. TU-
Ilmenau, Fakultt fr Mathematik und
Naturwissenschaften, 2007.
