• 因为x1,x2当前均为非整数，故不满足整数要求，
任选一个进行分枝。设选x1进行分枝，把可行
集分成2个子集：
x1 [4.8] 4 x1 [4.8] 1 5
• ，因为4与5之间无整数，故这两个子集内的整
数解s.t. 必与原可行集合整数解一致。这一步称为
分枝。这两个子集的规划及求解如下：问题B1：
Max z 40x1 90x2
• 最优解为：
9 7
x1 x1
7x2 56 20x2 70
0 x1 4, x2 0
x1 4.0, x2 2.1, z1 349
• 问题B2
Max z 40x1 90x2
s.t.
9x1 7x2 56 7x1 20x2 70
x1 5, x2 0
由于xi只取值0或1
xi (1 xi ) 0, i 1,L , n.
最佳投资方案应是投资额最小而总收益最 大的方案，所以这个最佳投资决策问题归 结为总资金以及决策变量（取0或1）的限 制条件下，极大化总收益和总投资之比。 因此，其数学模型为
n
bi xi
max Q
i 1 n
ai xi
i 1
非线性规划的Matlab解法 Matlab中非线性规划的数学模型形式
minf(x)
Ax B Aeq x Beq C(x) 0 Ceq(x) 0
其中是标量函数，是相应维数的矩阵和向量， 是非线性向量函数。Matlab中的命令是
X=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB, NONLCON,OPTIONS)
• x j [bj ] xj [bj ] 1 进行迭代。
• 第一步：分枝，在B的最优解中任选一个不符 合整数条件的变量xj，其值为bj，以[bj]表示小 于bj的最大整数。构造两个约束条件
• 将这两个约束条件，分别加入问题B，求两个 后继规划问题B1和B2。不考虑整数条件求解这 两个后继问题。
5.2.6 求解下列指派问题，已知指派矩阵为
其整数规划解出现下述情况： • ①原线性规划最优解全是整数，则整数规划最优解与
线性规划最优解一致。②整数规划无可行解 • （ii） 整数规划最优解不能按照实数最优解简单取整
而获得。
理学院
例5.2.3 求解下述整数规划
Max z 40x1 90x2 9x1 7x2 56
s.t. 7x1 20x2 70 x1, x2 0 且为整数
数学建模
（Mathematical Modeling)
• 1. 整数规划的分类 • 如不加特殊说明，一般指整数线性规划。对于整数线
性规划模型大致可分为两类： • （i）变量全限制为整数时，称纯（完全）整数规划。 • （ii）变量部分限制为整数的，称混合整数规划。 • （iii）变量只能取0或1时，称之为0-1整数规划。 • 2.整数规划特点 • （i）原线性规划有最优解，当自变量限制为整数后，
例5.3.1 （投资决策问题）某企业有个项目可 供选择投资，并且至少要对其中一个项目投 资。已知该企业拥有总资金元，投资于第个 项目需花资金元，并预计可收益元。试选择 最佳投资方案。
解 设投资决策变量为
1, 决定投资第i个项目 xi 0， 决定不投资第i个项目
限制条件
n
0 ai xi A i 1
• （a）B没有可行解，这时A也没有可行解， 则停止．
• （b）B有最优解，并符合问题A的整数条件， B的最优解即为A的最优解，则停止。
• （c）B有最优解Z，但不符合问题A的整数条 件，记它的目标函数值为 。
• （ii）用观察法找问题A的一个整数可行解， 一般可取xj=0，j=1,…,n试探，求得其目标函数 值，并记作Z。以Z*表示问题A的最优目标函数 值；这时有 z z* z
• 最优解为：x1 5.0, x2 1.57, z1 341.4
0 z* 349
以此类推找出最优解。
• 从以上解题过程可得用分枝定界法求解整数规 划（最大化）问题的步骤为：
• 开始，将要求解的整数规划问题称为问题A， 将与它相应的线性规划问题称为问题B。
• （i）解问题B可能得到以下情况之一：
n
s.t.0 ai xi A i 1
xi (1 xi ) 0, i 1,L , n.
非线性规划问题一般形式：
min f (x)
其中
s.t. h j ( x) 0, j 1, , q gi (x) 0, i 1, , p
x [x1 xn ]T称为模型的决策变量，
f称为目标函数，gi(x)和 hi(x)称为约束函数。 另外， gi(x)=0 称为等式约束， hi(x)<0 称为不等式约束
• 解 编写Matlab程序如下： c=[3 8 2 10 3;8 7 2 9 7;6 4 2
8 4 2 3 5;9 10 6 9 10];
783
5
8 7
2 10 29
3
7
6 4 2 7 5
c=c(:);a=zeros(10,25); for i=1:5 a(i,(i-1)*5+1:5*i)=1;
8
42
3
5
Hale Waihona Puke 9 10 6 9 10a(5+i,i:5:25)=1;end b=ones(10,1);
[x,y]=linprog(c,[],[],a,b,zeros(25,1),ones(25,1))
求得最优指派方案为 x15 x23 x32 x44 x51 1
§5.3 非线性规划
如果目标函数或约束条件中包含非 线性函数，就称这种规划问题为非 线性规划问题。一般说来，解非线 性规划要比解线性规划问题困难得 多。而且，也不象线性规划有单纯 形法这一通用方法，非线性规划目 前还没有适于各种问题的一般算法， 各个方法都有自己特定的适用范围。
解 （i）先不考虑整数限制，即解相应的线性规 划，得最优解为：x1 4.8092, x2 1.8168, z 355.8779
可见它不符合整数条Z件。这时Z是问题A的最优 目标函数值Z*的上界，记作 。而x1=0,x2=0显 然是问题A的一个整数可行解，这时Z=0，是 Z*的一个下界，记作，即0<Z*<356。