例 4
7 x1 3x 2 9 x 3 1, 8x 5x 4 x 1, 1 2 3 s.t. 6 x1 9 x 2 5x 3 1, x1 , x 2 , x 3 0
>> c=[-1 -1 -1]; >> A=[7 3 9;8 5 4;6 9 5]; >> b=[1;1;1]; >> Ae=[];be=[];vlb=[0 0 0];ulb=[]; >> [x,fval,exitflag,output,lambda]=linprog(c,A,b,Ae,be,vlb,ulb)
>> [x,fval,exitflag,output]=fminunc(@zuisu1,x,options) x = 1.2671 1.6062 fval = 0.0714 exitflag = 0 output = iterations: 23 funcCount: 252 stepsize: 1.0000e-003 firstorderopt: 0.2239 algorithm: 'medium-scale: Quasi-Newton line search' message: 'Solver stopped prematurely.fminunc stopped because it exceeded the function evaluation limit,options. MaxFunEvals = 250 (the selected value).
>> f=[100,30,40,45]; >> A=[-50 -30 -25 -10;-7 -2 -1 例5 -1 -1 -10;0 1 1 -1]; -4;-2 >> b=[-20;-4;-2;1]; >> [x,fval,exitflag,output]=bintprog(f,A,b,[],[],[]) Optimization terminated. x= 0 1 0 1 fval = 75 exitflag = 1 output = iterations: 15 nodes: 11 time: 1.1388 algorithm: 'LP-based branch-and-bound' branchStrategy: 'maximum integer infeasibility' nodeSrchStrategy: 'best node search' message: 'Optimization terminated.'
>> [x,fval]=bintprog(c,A,b) Optimization terminated.
X12,x23,x34,x41,x55取1，其余取0。
x=
(2,1)
1
(8,1)
(14,1) (16,1)
1
1 1
三、无约束优化
1、无约束最优性判别条件（略） 2、语法：
[x,fval,exitflag,output,grad,hessian]=fminunc(fun,x0,options)
3. 求解格式3
min z cx Ax b, s.t .Qx p , vlb x vub
x=linprog(c,A,b,Q,p,vlb,vub,x0)
例3Βιβλιοθήκη X0表示初始解，默认不写。vlb 表示决策变量x的 下界，vub 表示变量x的上界。 例3 求解例2，增加下界(0 0 0 0 0 0)。
Optimization terminated. x=
0.0870
0.0356
0.0316
fval = -0.1542 exitflag = 1
output = iterations: 7 algorithm: ‘large-scale: interior point’ cgiterations: 0 (共轭迭代0次) message: 'Optimization terminated.' constrviolation: 0 firstorderopt: 3.2143e-014 lambda = ineqlin: [3x1 double] eqlin: [0x1 double] upper: [3x1 double] lower: [3x1 double]
二、0-1整数规划 1、bintprog函数
[x,fval,exitflag,output]=bintprog(f,A,b,Aeq,beq,x0,options)
所有变量说明如前。 例5 求解0-1线性规划问题
min f 100 y1 30 y 2 40 y 3 45 y 4 50 y1 30 y 2 25 y 3 10 y 4 20, 7 y 2 y y 4 y 4, 1 2 3 4 s.t. 2 y1 y 2 y 3 10 y 4 2, y y y 1 3 4 2 y1 , y 2 , y 3 , y 4 {0,1}
g为导数解析式
f=100*(x(2)-x(1)^2)^2+(1-x(1))^2;
[1] 不含解析的计算 g=[200*(x(2)-x(1)^2)*(-2)*x(1)-2*(1-x(1)),200*(x(2)-x(1)^2)];
>> x=[2;2]; >> options=optimset('LargeScale','off','HessUpdate', 'steepdesc','gradobj','off','MaxFunEvals',250,'display','iter');
‘MaxFunEvals’ ,250 最大函数计算次数 250
‘display’,’iter’ 显示迭代过程
例7 利用最速下降法计算无约束优化问题
min
f 100 ( x 2 x ) (1 x1 )
2 2 1
2
function f=zuisu1(x)
不含导数解析式
f=100*(x(2)-x(1)^2)^2+(1-x(1))^2; function [f,g]=zuisu2(x)
例6 某装修公司有甲、乙、丙、丁、戊5个装修队，现 在公司接到5项装修任务A、B、C、D、E。各个装修 例6 0-1指派问题 队对5项任务的装修时间估计如下表 A B C D E
甲
乙 丙
32
21 24
17
31 29
34
21 40
36
22 28
25
19 39
丁
戊
26
33
35
27
41
31
33
42
29
22
Grad：最优点的导数（梯度）
Hessian：最优点的二阶导数，海赛矩阵。
3、无约束优化的几种算法选择
3.1
最速下降法
在语法中，将输入参数options设置为
Options=optimset(‘LargeScale’,’off’,’HessUpdate’,’steepdesc’,’gr adobj’,’on’,’maxFunEvals’,250,’display’,’iter’); ‘LargeScale’,’off’ 大规模计算模式 关闭 ‘HessUpdate’,’steepdesc’ Hess矩阵修正，采用最速下降法 （不需要修正） ‘gradobj’,’on’ 目标函数导数解析式，on使用，off不使用(差分)
Output：优化结果的约束信息
Lambda,exitfla：算法停止原因 1 算法收敛于x； 0 算法达到最大迭代次数停止迭代，x不一定是最优 解；
-2 算法没有找到可行解，无可行解；
-3 原问题为无界解；
…（其它信息可以查阅相关的help信息）
例4 求解线性规问题 min f x1 x 2 x 3
>> clear
>> c=[-2,-1]; A=[0,2;6,2;1,1]; b=[15;25;5]; >> x=linprog(c,A,b)
注意：matlab规 划模块不会自动 认为决策向量x非 负，如果要求x非 负，需要给出下 界Lb。
2、求解格式2 terminated. cx min z Optimization
参数输入： Fun： x0： 目标函数，一般用M文件给出 优化的初始点
Options: 参数设置（后面说明）
函数输出：
X：最优点（或最后迭代值） Fval：最后迭代值的目标函数值 Exitflag：函数结束的信息 Oupput：函数基本信息，包括迭代次数，目标函数最 大计算次数，使用的算法名称，计算规模
>> c=[13 9 10 11 12 8]; >> A=[0.4 1.1 1 0 0 0;
0 0 0 0.5 1.2 1.3];
>> b=[800;900];
>> Q=[1 0 0 1 0 0;
因为x没有下界， 计算中断
exiting:0One 0; more of the residuals, duality gap, or total 0 1 0 1 or relative error has grown 100000 times greater than its minimum0value so far: the dual appears to be infeasible 0 0 1 0 1]; (and the primal unbounded). (The primal residual >> p=[400;600;500]; < TolFun=1.00e-008.) x = 1.0e+042 * ( -1.6376 0.1424 0.4984 1.6376 0.1424 -0.4984) >> x=linprog(c,A,b,Q,p)