第九章 最优化方法要点

A=[3,2,-1,4,2; 2,4, -2,-1,-2]; b=[5;5] ;

[x,fval,exit,output]=bintprog(f,A,b) 输出结果：

Optimization terminated. x = 1 1 1 0 0 fval = -5 exit = 1 output =

iterations: 4 nodes: 1 time: 0.0781

algorithm: 'LP-based branch-and-bound' branchStrategy: 'maximum integer infeasibility' nodeSrchStrategy: 'best node search' message: 'Optimization terminated.

这表明，当x1?1,x2?1,x3?1,x4?0,x5?0时，目标函数取最大值5。 例4 资金分配问题，某企业在今后3年内有5个工程考虑开工，每项工程的期望收入和年度费用如表所示。假定每一项已经批准的工程要在整3年内完成。企业应如何选择工程，使企业总收入最大？

工程 1 费用（千元） 第一年 5 第二年 1 第三年 8 收入（千元） 20 2 3 4 5 最大可用资金数 4 3 7 8 25 7 9 4 6 25 10 2 1 10 25 40 20 15 30 解 设决策变量为x1,x2,x3,x4,x5：其中xi?0或1，xi?0表示放弃第i项工程，

xi?1表示选择第i项工程。

该问题的数学模型为：

max z?20x1?40x2?20x3?15x4?30x5?5x1?4x2?3x3?7x4?8x5?25?x?7x?9x?4x?6x?25?12345s.. t??8x1?10x2?2x3?x4?10x5?25??xi?1或0(i=1,2,3,4,5)

利用bintprog函数求解如下： f=-[20;40;20;15;30];

A=[5,4,3,7,8;1,7,9,4,6;8,10,2,1,10]; b=[25;25;25];

[x,fv,exit]=bintprog(f,A,b) 输出结果如下： Optimization terminated. x = 1 1 1 1 0 fv = -95 exit = 1

上述结果表明，该企业选择第1，第2，第3，第4项工程，可以获得最大

利润95千元。

指派问题：设有n项工作分配给n个人去做，每人做一项，由于个人的工作效率不同，因而完成同一工作所需时间也不同，设人员i完成工作j所需时间为，问如何分配工作，使得完成所有工作所用的总时间最少？Cij（称为效率矩阵）

这类问题称为指派问题（Assignment Problem），也称最优匹配问题，它是一类典型的0-1规划问题。

例5 有4个工人被分派做4项工作，每项工作只能一人做，每人只能做一项工作。现设每个工人做每项工作的耗时如表所示，求总耗时最少的分配方案。

表1时间表 时间单位：小时

工作 耗时 工人 1 2 3 4 1 2 3 4 15 19 26 19 18 23 17 21 21 22 16 23 24 18 19 17 解 设决策变量为xij(i,j?1,2,3,4)，只取0或1。xij?1表示工人i完成工作

j；xij?0表示工人i不做工作j。

于是，上述问题的数学模型如下：

min z?15x11?18x12?21x13?24x14?19x21?23x22?22x23?18x24?26x31?17x32?16x33?19x34?19x41?21x42?23x43?17x44

?n??xij?1,i?1,2,3,4?j?1 s.. t?n?x?1,j?1,2,3,4?ij??i?1下面给出Matlab计算程序。

>> f=[15;18;21;24;19;23;22;18;26;17;16;19;19;21;23;17]; o4=ones(1,4);z4=zeros(1,4); z8=zeros(1,8);z12=zeros(1,12);

Aeq1=[o4,z12;z4,o4,z8;z8,o4,z4;z12,o4];

e4=eye(4); Aeq2=[e4,e4,e4,e4]; Aeq = [Aeq1;Aeq2]; beq=ones(8,1);

[x,fv,exit]=bintprog(f,[],[],Aeq,beq); x=transpose(reshape(x,4,4)) 计算接可以得出： fv = 70 exit = 1 指派方阵 x =

1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0

它表示的最优指派方案为：工人1做工作1；工人2做工作4；工人3做工作3；工人4做工作2。该指派方案耗时最少，为70小时。

9.3 非线性规划

9.3.1 有约束的一元函数的极（最）小值

在MATLAB中使用fminbnd函数求一元函数y?f(x)在区间(x1,x2)上的极（最）小值。其调用格式有：

[x,fval,exitflag,output] = fminbnd(fun,x1,x2,options)

其中输入参数fun为目标函数的表达式字符串或MATLAB定义的M函数，x1和x2为自变量x的取值范围，options为指定优化参数选项；输出参数x为函数fun在区间x1

若参数exitflag>0，表示函数收敛于x，若exitflag=0，表示超过函数估计值