1 整数规划的MATLAB 求解方法
（一） 用MATLAB 求解一般混合整数规划问题
由于MATLAB 优化工具箱中并未提供求解纯整数规划和混合整数规划的函数，因而需要自行根据需要和设定相关的算法来实现。现在有许多用户发布的工具箱可以解决该类问题。这里我们给出开罗大学的Sherif 和Tawfik 在MATLAB Central 上发布的一个用于求解一般混合整数规划的程序，在此命名为intprog ，在原程序的基础上做了简单的修改，将其选择分枝变量的算法由自然序改造成分枝变量选择原则中的一种，即：选择与整数值相差最大的非整数变量首先进行分枝。intprog 函数的调用格式如下：
[x,fval,exitflag]=intprog(c,A,b,Aeq,beq,lb,ub,M,TolXInteger) 该函数解决的整数规划问题为：
?????
??????∈=≥≤≤=≤=）
取整数（M j x n i x ub x lb b x A b
Ax t s x c f j i eq eq T )
,,2,1(0
..min
在上述标准问题中，假设x 为n 维设计变量，且问题具有不等式约束1m 个，等式约束2m 个，那么：c 、x 均为n 维列向量，b 为1m 维列向量，eq b 为2m 维列向量，A 为n m ?1维矩阵，eq A 为n m ?2维矩阵。
在该函数中，输入参数有c,A,b,A eq ,b eq ,lb,ub,M 和TolXInteger 。其中c 为目标函数所对应设计变量的系数，A 为不等式约束条件方程组构成的系数矩阵，b 为不等式约束条件方程组右边的值构成的向量。Aeq 为等式约束方程组构成的系数矩阵，b eq 为等式约束条件方程组右边的值构成的向量。lb 和ub 为设计变量对应的上界和下界。M 为具有整数约束条件限制的设计变量的序号，例如问题中设计变量为621,,,x x x ，要求32,x x 和6x 为整数，则M=[2;3;6]；若要求全为整数，则M=1:6，或者M=[1;2;3;4;5;6]。TolXInteger 为判定整数的误差限，即若某数x 和最邻近整数相差小于该误差限，则认为x 即为该整数。
在该函数中，输出参数有x, fval 和exitflag 。其中x 为整数规划问题的最优解向量，fval 为整数规划问题的目标函数在最优解向量x 处的函数值，exitflag 为函数计算终止时的状态指示变量。 例1 求解整数规划问题：
?????
??
??≥≥≤+≥-+= 0,
12 1124 124 ..max
212212121，且取整数值x x x x x x x t s x x f
算法：
c=[-1;-1]; A=[-4 2;4 2;0 -2]; b=[-1;11;-1]; lb=[0;0]; M=[1;2]; %均要求为整数变量 Tol=1e-8;
%判断是否整数的误差限
[x,fval]=linprog(c,A,b,[],[],lb,[])
%求解原问题松弛线性规划
[x1,fval1]=intprog(c,A,b,[],[],lb,[],M,Tol) %求最优解整数解 结果：
x =
%松弛线性规划问题的最优解
1.5000
2.5000 fval = -4.0000 x1 =
%整数规划的最优解
2 1 fval2 = -3.0000
（二） 用MATLAB 求解0-1规划问题
在MATLAB 优化工具箱中，提供了专门用于求解0-1规划问题的函数bintprog ，其算法基础即为分枝界定法，在MATLAB 中调用bintprog 函数求解0-1规划时，需要遵循MATLAB 中对0-1规划标准性的要求。 0-1规划问题的MATLAB 标准型
???
????==≤=1
,0..min x b x A b
Ax t s x c f eq eq T
在上述模型中，目标函数f 需要极小化，以及需要满足的约束条件，不等式约束一定要化为形式为“≤”。
假设x 为n 维设计变量，且问题具有不等式约束1m 个，等式约束2m 个，那么：
c 、x 均为n 维列向量，b 为1m 维列向量，eq b 为2m 维列向量，A 为n m ?1维矩阵，eq A 为n m ?2维矩阵。
如果不满足标准型的要求，则需要对原问题进行转化，化为标准型之后才能使用相关函数，标准化的方法和线性规划中的类似。 0-1规划问题的MATLAB 求解函数
MATLAB 优化工具箱中求解0-1规划问题的命令为bintprog bintprog 的调用格式
x = bintprog(f) x = bintprog(f,A,b) x = bintprog(f,A,b,Aeq,beq) x = bintprog(f,A,b,Aeq,beq,x0) x = bintprog(f,A,b,Aeq,Beq,x0,options) [x,fval] = bintprog(...) [x,fval,exitflag] = bintprog(...) [x,fval,exitflag,output] = bintprog(...)
命令详解
1）x = bintprog(f)
该函数调用格式求解如下形式的0-1规划问题
???==1
,0.
.min x t s x
c f T
2）x = bintprog(c,A,b)
该函数调用格式求解如下形式的0-1规划问题
??
???=≤=1
,0..min x b Ax t s x c f T
3）x = bintprog (c,A,b,Aeq,beq)
该函数调用格式求解如下形式的0-1规划问题：
???
????==≤=1
,0..min x b x A b
Ax t s x c f eq eq T
4）x = bintprog (c,A,b,Aeq,beq,x0)
该函数调用格式求解如下形式的0-1规划问题
???
????==≤=1
,0..min x b x A b
Ax t s x c f eq eq T
在前一个调用格式的基础上同时设置求解算法的初始解为x0，如果初始解x0不在0-1规划问题的可行域中，算法将采用默认的初始解 5）x = bintprog (c,A,b,Aeq,beq,x0,options)
用options 指定的优化参数进行最小化。可以使用optimset 来设置这些参数
上面的函数调用格式仅设置了最优解这一输出参数，如果需要更多的输出参数，则可以参照下面的调用格式：
[x,fval] = bintprog(...)
在优化计算结束之时返回整数规划问题在解x 处的目标函数值fval
[x,fval,exitflag] = bintprog(...)
在优化计算结束之时返回exitflag 值，描述函数计算的退出条件。
[x,fval,exitflag,output] = bintprog(...) 在优化计算结束之时返回结构变量output 例2：求解0-1规划问题
()()()?????
?????
?
========∑∑∑∑==== 21;21 4,3,21 10 21 1 21 1 ..max
1111
,n ,,j ,n ,,i x ,n ,,j x ,n ,,i x t s x E f ij n
i ij n j ij n i n
j ij
ij ），（或?????
???????=2332
16
2224311321232915222633
1220E 为了程序的可读性，我们用一维下标来表示设计变量，即用41~x x 表示1411~x x ，用85~x x 表示2421~x x ，用129~x x 表示3431~x x ，用1613~x x 表示4441~x x ，于是约束条件和目标函数分别为：
???
?????
??
?????===+++=+++=+++=+++=+++=+++=+++=+++)
16,,2,1( 1,0111
1111
1
16128415117314
1062
139511615141312111098765
4321 i x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x i 1644622521414313212111x E x E x E x E x E x E x E f +++++++=
算法：
c=[20;12;33;26;22;15;29;23;21;13;31;24;22;16;32;23]; Aeq=[1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1; 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0;
0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0;
0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0;
0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1;
];
beq=ones(1,8);
[x,fval]=bintprog(c,[],[],Aeq,beq);
B=reshape(x,4,4); %由于x是一列元素，为了使结果更加直观，故排成与效率矩阵E相
对应的形式
B'
fval
结果：
Optimization terminated.
ans =
0 1 0 0
0 0 1 0
1 0 0 0
0 0 0 1
fval =
85
整数规划的应用——组件配套问题
某机械产品需要由三个工厂开工一起生产后组装完成。每件机械需要4个组件1和3个组件2。生产这两种组件需要消耗两种原材料A和B。已知这两种原材料的供应量分别为400kg和600kg。
由于三个工厂的生产条件和拥有设备工艺条件不同，每个工厂生产组件的能力和原材料的消耗也不尽相同，且每个工厂开工一次都是配套生产一定数量的组件1和组件2，其具体的数据如表所示。
表11-2 各工厂生产能力和消耗原材料的数据表
现在的最优化问题是，这三个工厂应当如何安排生产，才能使该产品的配套数达到最大？
（Ⅰ）组件配套问题的建模
设21x x 、和3x 是三个工厂分别开工的次数，将其作为该问题的设计变量。由于每个工厂开工一次都是配套生产，故每次开工消耗的原材料一定，且生产的组件数也是一定的。在这个假设的前提之下，我们可以得出该问题的目标函数和约束条件。
因为原材料的总量是有限的，根据工厂的开工次数，可得工厂１将消耗A 材料19x ，工厂２将消耗A 材料26x ，工厂３将消耗A 材料34x ，故有约束条件：
400469321≤++x x x
同理，对于材料B 的总量约束条件可以表达为：6009107321≤++x x x 然后再来分析三个工厂零件生产的情况，三个工厂生产的组件1的数量分别为2178x x 、和39x ，故组件1的总数为：3211978x x x Q ++=
同理，组件2的总数为：3212596x x x Q ++=
下一步是分析目标函数，该问题要求的不是生产的各种组件总数最多，而是要求产品的配套数量最大，即能组成的机械数目最多。问题中已经给出了该种机械中两种组件的配比为4:3，故组件1所能成套的数目1T 满足约束条件：
4
97843
2111x x x Q T ++=≤
同理，组件2所能成套的数目2T 满足约束条件：3
59633
2122x x x Q T ++=≤
因而，所能组成的成品机械的数目f 应该为1T 和2T 中的较小值，即：
),min(21T T f =
那么，我们求解的目标即是使得f 能够尽可能大，可以看出，这种形式并不是有关设计变量的线性函数，我们需要对其进行转化，此时我们可以令一个人工设计变量等于目标函数值，则有：),min(214T T x =
在该假设下，一定满足关系式：41x T ≥且42x T ≥ 结合约束关系，对1T 的约束可以表示为：4
97843
21114x x x Q T x ++=≤
≤ 同理，对2T 的约束可以表示为：3
59633
21224x x x Q T x ++=≤
≤ 对1T 的上述关系进行整理，可以得到关系：049784321≤+---x x x x 同理对2T 也可以得到不等式关系为：035964321≤+---x x x x
上面两个式子即为由组件的配比数得到的关于组件数目的约束条件，此时问题的目标就是如何使得4x 取到最大值，由于开工的次数一定是一个非负整数，故也是一个约束条件，决定了该问题是一个纯整数规划问题。结合前面给出的原材料约束，可以得到如下的数学模型：
()
????????
??
?=≥≤+---≤+---≤++≤++=4,3,2,10 03596 04978 6009107
400
469 max i 432143213213214
i x x x x x x x x x x x x x x x s.t.x f 且取整数值 （Ⅱ）组件配套问题的求解
利用§8.１节中给出的ＭＡＴＬＡＢ函数对此问题求解，代码和运行结果如下：
算法：
%目标函数所对应的设计变量的系数，为转化为极小，故取原目标函数的相反数 f=[0;0;0;-1]; %不等式约束 A=[ 9 6 4 0;
7 10 9 0;
-8 -7 -9 4;
-6 -9 -5 3];
b=[400;600;0;0];
%边界约束，由于无上界，故设置ub=[Inf;Inf;Inf;Inf];
lb=[0;0;0;0];
ub=[Inf;Inf;Inf;Inf];
%所有变量均为整数变量，故将所有序号组成向量M
M=[1;2;3;4];
%判定为整数的误差限
Tol=1e-8;
%求最优解x和目标函数值fval，并返回状态指示
[x,fval,exitflag]=intprog(f,A,b,[],[],lb,ub,M,Tol)
结果：
x =％最优解向量x
18
15
36
141
fval = ％在最优解向量x处，原目标函数值的相反数
-141.000
exitflag= ％算法终止指示变量，说明问题收敛到了最优解x 1
由运行结果可知，工厂１、２和３需要分别开工18、15和36次，这样所能生产出来的成套的机械为141件。
2 多目标规划的MATLAB求解方法
（一）多目标规划的MATLAB求解
由于多目标规划中的求解涉及到的方法非常多，故在MATLAB中可以利用
不同的函数进行求解，例如在评价函数法中我们所得最后的评价函数为一线性函数，且约束条件也为线性函数，则我们可以利用MATLAB 优化工具箱中提供的linprog 函数进行求解，如果我们得到的评价函数为非线性函数，则可以利用MATLAB 优化工具箱中提供的fmincon 函数进行求解，如果我们采用最大最小法进行求解，则可以利用MATLAB 优化工具箱中提供的fminimax 函数进行求解。下面我们就结合理论求解的几种方法，讲解一下典型多目标规划问题的MATLAB 求解方法。 例1 利用理想点法求解
?????
????≥≤+≤+--=-=0
, 8
1223 35)( min 32)( min 212
121212211x x x x x x s.t.x
x x f x x x f 我们首先根据评价函数法中的理想点法的理论基础，按照理想点法的求解思路分别对两个单目标规划问题()()21,P P 进行求解：
()()???????≥≤+≤+--=???????≥≤+≤+-=0,
8 1223 35)( min ,0, 8 1223 32)( min 2121212
1222121212111x x x x x x s.t.x x x f P x x x x x x s.t.x x x f P
求解()1P 的MATLAB 的代码和相应的运行结果为：
算法：
c=[2;-3]; A=[3 2;1 1]; b=[12;8] lb=[0;0]
[x,fval]=linprog(c,A,b,[],[],lb,[]) 结果：
x = 0.0000 6.0000
-18.0000
于是可知。当()T
x 6,01=时，单目标线性规划()1P 的最优函数值为18*1-=f 。
求解()2P 的MATLAB 的代码和相应的运行结果为：
算法：
c=[-5;-3]; A=[3 2;1 1]; b=[12;8] lb=[0;0]
[x,fval]=linprog(c,A,b,[],[],lb,[]) 结果：
Optimization terminated. x = 4.0000 0.0000 fval = -20.0000
于是可知，当()T
x 0,42=时，单目标线性规划()2P 的最优函数值为20*2-=f 。
由上述两个单目标线性规划的求解结果可知22x x ≠，因而
()
()20,18,*2*1
--=f f
是一个不可能达到的理想点，因而我们构造如下评价函数：
()()()()()212212
2212035183220)(18)()(min -+++-=
+++=
∈x x x x x f x f x f h R
x
构造描述该评价函数的M-函数文件objfun.m 如下： function f=objfun(x)
f=sqrt((2*x(1)-3*x(2)+18)^2+(5*x(1)+3*x(2)-20)^2); 然后用非线性规划的方式求解上述问题：
算法：
A=[3 2;1 1]; b=[12;8];
x0=[0;0];
[x,fval,exitflag]=fmincon(@objfun,x0,A,b,[],[],lb,[]) 结果：
Active inequalities (to within options.TolCon = 1e-006): lower upper ineqlin ineqnonlin 1
x = 0.0235 5.9647
fval = 1.9941
exitflag = 5
由运行结果可知在该评价函数标准之下，问题的最优解为：
()T
x 9647.5,0235.0*=此时，
各目标函数的取值为：0118.18,8471.17*2*1-=-=f f 。它与理想点()
()20,18,*2*1--=f f 在评价函数标准下的最小距离为1.9941。 例2 利用评价函数中的线性加权和法求解如下多目标规划问题：
???
???
?≥=++++=++=0,, 3 32)( min )( min 3213212
322
2122322211x x x x x x s.t.x x x x f x x x x f 其中权系数为2.0,8.021==λλ。 建立线性加权和法的评价函数为：
()()()
2
322212232221132)(min x x x x x x x f h +++++=λλ
将相应的权系数代入上式即整理出目标函数)(x f 为：
2
3
22214.12.1)(x x x x f ++=
于是建立目标函数的M-函数文件objfun.m ：
function f=objfun(x)
f=x(1)^2+1.2*x(2)^2+1.4*x(3)^2;
由于目标函数非线性函数且具有线性等式约束和边界约束，因而我们调用MATLAB 中求解非线性规划的fmincon 函数对此问题进行求解，同时注意如果只考虑第一个目标函数，由这种特殊形式，即在设计变量的和为一定值，需要求其平方和的最小值时，最优解必然是当这几个设计变量的值相等时取得，于是我们可以将这个解设为问题的初始点，开始迭代。
算法：
Aeq=[1 1 1]; beq=[3]; lb=[0;0;0]; x0=[1;1;1];
[x,fval]=fmincon(@objfun,x0,[],[],Aeq,beq,lb,[]) 结果：
No active inequalities. x = 1.1776 0.9812 0.8412 fval = 3.5327
结果说明，问题的最优解为：5327.3)(,8412.09812.01776.1**3*2
*1*=?
?????????=??????????=x f x x x x 我们在求解多目标规划问题时，可以采用评价函数法中的最大最小法，而MATLAB 也为这种方法提供了专门的求解函数fminimax ，在讲解这方面的例题之前，我们首先介绍一下MATLAB 优化工具箱中所提供的最大最小法的求解函数fminimax 。
最大最小法问题的MATLAB 标准形式为：
??????
????
?≤≤=≤=≤ub
x lb b
x A b Ax (x)c c(x)s.t.x f eq
eq eq i i
x
0 0 )
( max min 函数fminimax 的调用方式和其他的最优化函数类似，其中所涉及的输入参数和输出参数的含义与非线性规划的求解函数fmincon 类似，使用方法也基本相同，细节问题读者可以参考MATLAB 的帮助文件。 例3 求解最大最小问题：
??
????????
?-+=--=-+=--=+--+=8
)( )( 183)( 3)( 30440482)( )( max min 21521421322
212212
2211x x x f x
x x f x x x f x x x f x x x x x f s.t.x f i i
x
首先建立描述目标函数的M-函数文件objfun.m ，注意到一共有五个目标函数，所求目标为这五个函数最大值中的最小值，代码如下：
function f = objfun(x)
f(1)= 2*x(1)^2+x(2)^2-48*x(1)-40*x(2)+304; f(2)= -x(1)^2 - 3*x(2)^2; f(3)= x(1) + 3*x(2) -18; f(4)= -x(1)- x(2); f(5)= x(1) + x(2) - 8;
然后设置求解的初始点为x0=[0;0]，调用fminimax 求解该问题。
算法：
x0 = [0; 0];
[x,fval,maxfval] = fminimax(@objfun,x0) 结果：
Local minimum possible. Constraints satisfied.
fminimax stopped because the predicted change in the objective function
is less than the default value of the function tolerance and constraints were satisfied to within the default value of the constraint tolerance.
Active inequalities (to within options.TolCon = 1e-006): lower upper ineqlin ineqnonlin 1 5 x = 4.0000 4.0000 fval =
0.0000 -64.0006 -1.9999 -8.0000 -0.0000 maxfval = 2.6897e-008
上述结果说明当4,421==x x 时，目标函数5,,2,1 )( =i x f i 的最大值达到最小，这一组的函数值为0.0000，-64.0006，-1.9999，-8.0000，-0.0000，于是最大值为0。
多目标规划的应用——投资问题（全国大学生数学建模竞赛试题）
假设市场上有n 种资产，比如股票、债券等可以供投资者选择，某公司有数额为M 的一笔相当大的资金可用作一个时间的投资。通过财务人员对i S 种资产进行评估，大概可以估算出在这一时期内购买资产i S 的平均收益率为i r ，并预测出购买i S 的损失率为i q 。考虑到投资越分散，总的风险越小，公司决定当用这笔资金购买若干种资产时，总体风险可用所投资的i S 中的最大一个风险来度量。
购买i S 要付交易费，费率为i p ，并且当购买额不超过给定值i u 时，交易费按购买i u 计算（不买当然无须付费）。另外，假定同期银行存款利率是0r ，且既无交易费又无风险(0r ＝5％)。已知4=n 时的相关数据如下表所示：
表1 投资各种资产的参数值
试给该公司设计一种投资组合方案，即用给定的资金M ，有选择地购买若干种资产或存银行生息，使净收益尽可能大，而总体风险尽可能小。 （Ⅰ）投资问题的建模
为了建立数学模型，首先对模型进行一些必要的假设及符号说明： (1) 模型的假设
① 在一个时期内所给出的i r ，i q ，i p 保持不变。
②在一个时间内所购买的各种资产(如股票、证券等)不进行买卖交易，即在买入后不再卖出。
③ 每种投资是否收益是相互独立的。
④ 在投资过程中，无论盈利与否必须先付交易费。 (2)符号说明
M (元)：公司现有投资总金额；
()n i S i ,,1,0, =：欲购买的第i 种资产种类（其中0=i 表示存入银行）
： ()n i x i ,,1,0, =：公司购买i S 的金额； ()n i r i ,,1,0, =：公司购买i S 的平均收益率； ()n i q i ,,1,0, =：公司购买i S 的平均损失率；
()n i p i ,,1,0, =：公司购买i S 超过i u 时所付交易费率。 下面来建立模型。设购买i S 的金额为i x ，所付的交易费)(i i x c ，则
???????=≥=<<==0
)( ),,2,1(0 0
0)(00x c u x x p n i u x u p x x c i
i i i i i i
i i i i
由于投资额M 相当大，所以总可以假定对每个i S 的投资i i u x ≥。这时上面的大括号公式可简化为：),,2,1( )(n i x p x c i i i i ==
对i S 投资的净收益为：() )()(i i i i i i i i i x p r x c x r x R -=-= 对i S 的风险为：i i i i x q x Q =)(
对i S 投资所需资金为投资金额i x 与所需的手续费)(i i x c 之和，即：
()i i i i i i i x p x c x x f +=+=1)()(
当购买i S 的金额为),,2,1,0( n i x i =，投资组合),,,(10n x x x x =的净收益总额为：
∑==n
i i i x R x R 0)()(
整体风险为：)(max )(max )(11i i n
i i i n
i x q x Q x Q ≤≤≤≤==
资金约束为：M x f n
i i i =∑=0
)(
根据题目要求，以净收益总额)(x R 最大，而整体风险)(x Q 最小为目标建立模型如下：
()()()????
?
?
??
???=≥=+???
??--∑∑==n i x M
x p s.t. x q x p r i n i i i i i n i i i i ,,2,1,0 1 max min 00 很显然，这是一个多目标规划问题。 （Ⅱ）投资问题的求解
在此我们采用主要目标法对该问题进行求解，即根据问题的实际情况，确
定一个目标为主要目标，而把其余目标作为次要目标，并且根据经验，选取一定的界限值。这样就可以把次要目标作为约束来处理，于是就将原来的多目标问题转化为一个在新的约束下的单目标最优化问题。
在上述例子中如果以收益为主要目标，则可以固定风险水平，给定风险一个界限a ，讲问题转化称为求最大风险不超过a 时的最大收益，即下面的线性规划模型：
()()
()?
?????
???
=≥=+=≤-∑∑==n i x M x p n i Ma x q s.t. x p r i n
i i i i i n
i i
i i ,,2,1,0
1 ,,2,1 max 00
（1）
若投资者希望总盈利至少达到水平K 以上，则可以在风险最小的情况下寻找相应的投资组合，从而将原模型转化成为下列的线性规划模型进行求解：
()()
()()????
????
???=≥=+≥-∑∑==n i x M x p K x p r s.t. x q i n
i i i n
i i i i i i i
,,2,1,0
1 max min 0
x
（2）
根据上面的分析，我们利用主要目标法建立了该问题的多目标规划模型，进而转化成为了线性规划模型，下面我们利用MATLAB 对此问题进行求解并进行投资分析。将4=n 时的数据代入模型(1)中，我们可以得到MATLAB 的标准型为：
?
??
???
??
???=≥≤≤≤≤=++++-----=4,3,2,1,0
0.026 0.055 0.015 0.025 1
065.1045.102.101.1 ..185.0185.019.027.005.0 min 4321432104
3210i x a x a x a x a x x x x x x t s x x x x x f i
由于a是任意给定的风险度，因而实际上没有一个选择的准则，不同的投资者可能有自身不同的判断，因而使得a的取值不同。我们在求解的过程中不妨用试探的方法，从0
=
.0
?a进行搜索，通过实验来分析和总a开始，以步长001
=
结风险度a和收益Q之间的数量关系。利用MATLAB编程求解。
算法：
clear
i=1;
a(i)=0;
x=cell(1,101);
while(1.1-a(i))>1
i=i+1;
a(i)=a(i-1)+0.001;
f=[-0.05 -0.27 -0.19 -0.185 -0.185];
Aeq=[1 1.01 1.02 1.045 1.065];
beq=[1];
A=[0 0.025 0 0 0;
0 0 0.015 0 0;
0 0 0 0.055 0;
0 0 0 0 0.026];
b=[a(i);a(i);a(i);a(i)];
lb=[0;0;0;0;0];
[y,fval(i)]=linprog(f,A,b,Aeq,beq,lb,[]);
x{i}=y;
Q(i)=-fval(i);
end
plot(a,Q,'.');
xlabel('a');
ylabel('Q');
结果：
a
Q
风险度与收益关系图
模型(1)的结果图分析：
(1) 由上图可知，收益随风险增大而增大，就是说，风险越大，收益也越大。 (2) 由数据表可以看出，投资越分散，投资者承担的风险越小。这与实际情况相符，就是说，冒险的投资者会出现集中投资的情况，保守的投资者则尽量分散投资。
(3) 曲线上的任一点都表示该风险水平的最大可能收益和该收益要求的最小风险。投资者应根据对不同风险的承受能力，选择该风险水平下的最优投资组合。
(4) 由局部放大上图可以看出，在0060.0)7(=a 附近有一个转折点。在这一点左边，风险增加很少时，利润增长很快；在这一点右边，风险增加很大时，利润增长很缓慢。所以对于风险和收益没有特殊偏好的投资者来说，应该选择曲线的该转折点作为最优投资组合，大约是2019.0)7(,0060.0)7(*===Q Q a ，所对应投资方案为：
T x ]2212.0,1091.0,4000.0,2400.0,0[=
1 整数规划的MATLAB 求解方法 （一） 用MATLAB 求解一般混合整数规划问题 由于MATLAB 优化工具箱中并未提供求解纯整数规划和混合整数规划的函数，因而需要自行根据需要和设定相关的算法来实现。现在有许多用户发布的工具箱可以解决该类问题。这里我们给出开罗大学的Sherif 和Tawfik 在MATLAB Central 上发布的一个用于求解一般混合整数规划的程序，在此命名为intprog ，在原程序的基础上做了简单的修改，将其选择分枝变量的算法由自然序改造成分枝变量选择原则中的一种，即：选择与整数值相差最大的非整数变量首先进行分枝。intprog 函数的调用格式如下： [x,fval,exitflag]=intprog(c,A,b,Aeq,beq,lb,ub,M,TolXInteger) 该函数解决的整数规划问题为： ????? ??????∈=≥≤≤=≤=） 取整数（M j x n i x ub x lb b x A b Ax t s x c f j i eq eq T ),,2,1(0..min Λ 在上述标准问题中，假设x 为n 维设计变量，且问题具有不等式约束1m 个，等式约束2m 个，那么：c 、x 均为n 维列向量，b 为1m 维列向量，eq b 为2m 维列向量，A 为n m ?1维矩阵，eq A 为n m ?2维矩阵。 在该函数中，输入参数有c,A,b,A eq ,b eq ,lb,ub,M 和TolXInteger 。其中c 为目标函数所对应设计变量的系数，A 为不等式约束条件方程组构成的系数矩阵，b 为不等式约束条件方程组右边的值构成的向量。Aeq 为等式约束方程组构成的系数矩阵，b eq 为等式约束条件方程组右边的值构成的向量。lb 和ub 为设计变量对应的上界和下界。M 为具有整数约束条件限制的设计变量的序号，例如问题中设计变量为621,,,x x x Λ，要求32,x x 和6x 为整数，则M=[2;3;6]；若要求全为整数，则M=1:6，或者M=[1;2;3;4;5;6]。TolXInteger 为判定整数的误差限，即若某数x 和最邻近整数相差小于该误差限，则认为x 即为该整数。
数学建模8-动态规划和目标规划 一、动态规划 1.动态规划是求解决策过程最优化的数学方法，主要用于求解以时间划分阶段的动态过程的 优化问题。但是一些与时间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。 2.基本概念、基本方程： （1）阶段 （2）状态 （3）决策 （4）策略 （5）状态转移方程： （6）指标函数和最优值函数： （7）最优策略和最优轨线 （8）递归方程： 3．计算方法和逆序解法（此处较为抽象，理解较为困难，建议结合例子去看）
4．动态规划与静态规划的关系：一些静态规划只需要引入阶段变量、状态、决策等就可以用动态规划方法求解（详见书中例4） 5．若干典型问题的动态规划模型： （1）最短路线问题： （2）生产计划问题:状态定义为每阶段开始时的储存量x k，决策为每个阶段的产量，记每个阶段的需求量（已知量）为d k，则状态转移方程为 （3）资源分配问题：详见例5
状态转移方程： 最优值函数： 自有终端条件： （4）具体应用实例：详见例6、例7。 二、目标规划 1．实际问题中，衡量方案优劣要考虑多个目标，有主要的，有主要的，也有次要的；有最大值的，也有最小值的；有定量的，也有定性的；有相互补充的，也有相互对立的，这时可用目标规划解决。其求解思路有加权系数法、优先等级法、有效解法等。 2．基本概念： （1）正负偏差变量： （2）绝对（刚性）约束和目标约束 ，次位赋（3）优先因子（优先等级）与权系数：凡要求第一位达到的目标赋予优先因子P 1……以此类推。 予P 2 （4）目标规划的目标函数： （5）一般数学模型：
工厂资源规划问题 冉光明 2010070102019 信息与计算科学 指导老师：赵姣珍
目录 摘要 (1) 关键词 (1) 问题的提出 (2) 问题重述与分析 (3) 符号说明 (4) 模型假设 (4) 模型建立与求解 (5) 模型检验 (9) 模型推广 (10) 参考文献 (11) 附录 (12)
摘要：本问题是个优化问题。问题首先选择合适的决策变量即各种产品数，然后通过决策变量来表达约束条件和目标函数，再利用matlab或lingo编写程序，求得最优产品品种计划；最后通过优化模型对问题作以解释，得出当技术服务消耗33小时、劳动力消耗67小时、不消耗行政管理时，得到的是最优品种规划。 问题一回答：当技术服务消耗33小时、劳动力消耗67小时、不消耗行政管理时， 时，若使产品品产品III不值得生产。用matlab运算分析，当产品III的利润增加至25 3 种计划最优，此时需要消耗技术服务29h，劳动力消耗46h，行政管理消耗25h。 问题二回答：利用lingo得到当技术服务增加1h时，利润增加2.5元;劳动力增加1h，利润增加1元；行政管理的增减不会影响利润。 问题三回答：增加的决策变量，调整目标函数。当技术服务消耗33h，劳动力消耗17h，不消耗行政管理，新增量50h时，管理部门采取这样的决策得到最优的产品品种规划。 问题四回答：增加新的约束条件，此时当技术服务消耗32h，劳动力消耗58h，行政管理消耗10h时，得到最优产品品种规划。 本文对模型的求解给出在线性约束条件下的获利最多的产品品种规划。 关键词：线性规划；优化模型；最优品种规划
问题的提出 某工厂制造三种产品，生产这三种产品需要三种资源：技术服务、劳动力和行政管理。下表列出了三种单位产品对每种资源的需要量： 资源利润 技术服务劳动力行政管理 产品I 1 10 2 10 II 1 4 2 6 III 1 5 6 4 现有100h的技术服务、600h劳动力和300h的行政管理时间可使用，求最优产品品种规划。且回答下列问题： ⑴若产品III值得生产的话，它的利润是多少？假使将产品III的利润增加至25/3元，求获利最多的产品品种规划。 ⑵确定全部资源的影子价格。 ⑶制造部门提出建议，要生产一种新产品，该种产品需要技术服务1h、劳动力4h 和行政管理4h。销售部门预测这种产品售出时有8元的单位利润。管理部门应有怎样的决策？ ⑷假定该工厂至少生产10件产品III，试确定最优产品品种规划。
MATLAB 中文论坛讲义 多目标规划优化问题 Matlab 中常用于求解多目标达到问题的函数为fgoalattain.假设多目标函数问题的数学模型为： ub x lb beq x Aeq b x A x ceq x c goal weight x F t s y x ≤≤=≤=≤≤-**0 )(0 )(*)(..min ,γγ weight 为权值系数向量，用于控制对应的目标函数与用户定义的目标函数值的接近程度； goal 为用户设计的与目标函数相应的目标函数值向量； γ为一个松弛因子标量； F(x)为多目标规划中的目标函数向量。 综上，fgoalattain 的优化过程就是使得F 逼近goal; 工程应用中fgoalattain 函数调用格式如下： [x,fval]=fgoalattain (fun,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon) x0表示初值； fun 表示要优化的目标函数； goal 表示函数fun 要逼近的目标值，是一个向量，它的维数大小等于目标函数fun 返回向量F 的维数大小； weight 表示给定的权值向量，用于控制目标逼近过程的步长； 例1. 程序（利用fgoalattain 函数求解） 23222 12 3222132min )3()2()1(min x x x x x x ++-+-+- 0,,6 ..321321≥=++x x x x x x t s ①建立M 文件. function f=myfun(x) f(1)= x(1)-1)^2+(x(2)-2)^2+(x(3)-3)^2; f(2)= x(1)^2+2*x(2)^2+3*x(3)^2; ②在命令窗口中输入. goal=[1,1]; weight=[1,1];
§5.3 目标规划模型 1. 目标规划模型概述 1)引例 目标规划模型是有别于线性规划模型的一类多目标决策问题模型，通过下面的例子，我们可看出这两者的区别。 例1 某工厂的日生产能力为每天500小时，该厂生产A 、B 两种产品，每生产一件A 产品或B 产品均需一小时，由于市场需求有限，每天只有300件A 产品或400件B 产品可卖出去，每出售一件A 产品可获利10元，每出售一件B 产品可获利5元，厂长按重要性大小的顺序列出了下列目标，并要求按这样的目标进行相应的生产。 （1）尽量避免生产能力闲置； （2）尽可能多地卖出产品，但对于能否多卖出A 产品更感兴趣； （3）尽量减少加班时间。 显然，这样的多目标决策问题，是单目标决策的线性规划模型所难胜任的，对这类问题，须采用新的方法和手段来建立对应的模型。 2）相关的几个概念 （1）正、负偏差变量+ d 、- d 正偏差变量+ d 表示决策值 ) ,,2,1(n i x i =超过目标值的部分；负偏差变量 - d 表示决策值 ) ,,2,1(n i x i =未达到目标值的部分；一般而言，正负偏差变量 + d 、- d 的相互关系如下： 当决策值 ) ,,2,1(n i x i =超过规定的目标值时， ,0=>- + d d ；当决策值 ),,2,1(n i x i =未超过规定的目标值时，0 ,0>=- + d d ；当决策值 ) ,,2,1(n i x i =正好等于规定的目标值时， ,0==- + d d 。 （2）绝对约束和目标约束 绝对约束是必须严格满足的等式约束或不等式约束，前述线性规划中的约束
条件一般都是绝对约束；而目标约束是目标规划所特有的，在约束条件中允许目标值发生一定的正偏差或负偏差的一类约束，它通过在约束条件中引入正、负偏差变量+ d 、- d 来实现。 （3）优先因子（优先级）与权系数 目标规划问题常要求许多目标，在这些诸多目标中，凡决策者要求第一位达到的目标赋予优先因子1P ，要求第二位达到的目标赋予优先因子2P ，……，并规定1+>>k k P P ，即1+k P 级目标的讨论是在k P 级目标得以实现后才进行的（这里 n k ,,2,1 =）。若要考虑两个优先因子相同的目标的区别，则可通过赋予它们 不同的权系数 j w 来完成。 3）目标规划模型的目标函数 目标规划的目标函数是根据各目标约束的正、负偏差变量+ d 、- d 和其优先因子来构造的，一般而言，当每一目标值确定后，我们总要求尽可能地缩小与目标值的偏差，故目标规划的目标函数只能是 ) ,( min - +=d d f z 的形式。我们 可将其分为以下三种情形： （1）当决策值) ,,2,1(n i x i =要求恰好等于规定的目标值时，这时正、负 偏差变量+ d 、- d 都要尽可能小，即对应的目标函数为： ) ( min - + +=d d f z ； （2）当决策值) ,,2,1(n i x i =要求不超过规定的目标值时，这时正偏差变 量+ d 要尽可能小，即对应的目标函数为： ) ( min + =d f z ； （3）当决策值 ) ,,2,1(n i x i =要求超过规定的目标值时，这时负偏差变量 - d 要尽可能小，即对应的目标函数为： ) ( min - =d f z 。 目标规划数学模型的一般形式为： ∑∑=+ +-- =+= K k k lk k lk L l l d w d w P z 1 1 ) ( min
优化与决策 ——多目标线性规划的若干解法及MATLAB 实现 摘要：求解多目标线性规划的基本思想大都是将多目标问题转化为单目标规划，本文介绍 了理想点法、线性加权和法、最大最小法、目标规划法，然后给出多目标线性规划的模糊数学解法，最后举例进行说明，并用Matlab 软件加以实现。 关键词：多目标线性规划 Matlab 模糊数学。 注：本文仅供参考，如有疑问，还望指正。 一．引言 多目标线性规划是多目标最优化理论的重要组成部分，由于多个目标之间的矛盾性和不可公度性,要求使所有目标均达到最优解是不可能的,因此多目标规划问题往往只是求其有效解(非劣解)。目前求解多目标线性规划问题有效解的方法,有理想点法、线性加权和法、最大最小法、目标规划法。本文也给出多目标线性规划的模糊数学解法。 二．多目标线性规划模型 多目标线性规划有着两个和两个以上的目标函数,且目标函数和约束条件全是线性函数,其数学模型表示为： 11111221221122221122max n n n n r r r rn n z c x c x c x z c x c x c x z c x c x c x =+++??=+++?? ??=+++? （1） 约束条件为： 1111221121122222112212,,,0 n n n n m m mn n m n a x a x a x b a x a x a x b a x a x a x b x x x +++≤??+++≤?? ??+++≤?≥?? （2） 若（1）式中只有一个1122i i i in n z c x c x c x =+++ ，则该问题为典型的单目标线性规划。我们记:()ij m n A a ?=,()ij r n C c ?=,12(,,,)T m b b b b = ,12(,,,)T n x x x x = ，
四类基本模型 1 优化模型 1.1 数学规划模型 线性规划、整数线性规划、非线性规划、多目标规划、动态规划。 1.2 微分方程组模型 阻滞增长模型、SARS 传播模型。 1.3 图论与网络优化问题 最短路径问题、网络最大流问题、最小费用最大流问题、最小生成树问题(MST)、旅行商问题(TSP)、图的着色问题。 1.4 概率模型 决策模型、随机存储模型、随机人口模型、报童问题、Markov 链模型。 1.5 组合优化经典问题 ● 多维背包问题(MKP) 背包问题：n 个物品，对物品i ，体积为i w ，背包容量为W 。如何将尽可能多的物品装入背包。 多维背包问题：n 个物品，对物品i ，价值为i p ，体积为i w ，背包容量为W 。如何选取物品装入背包，是背包中物品的总价值最大。 多维背包问题在实际中的应用有：资源分配、货物装载和存储分配等问题。该问题属于NP 难问题。 ● 二维指派问题(QAP) 工作指派问题：n 个工作可以由n 个工人分别完成。工人i 完成工作j 的时间为ij d 。如何安排使总工作时间最小。 二维指派问题（常以机器布局问题为例）：n 台机器要布置在n 个地方，机器i 与k 之间的物流量为ik f ，位置j 与l 之间的距离为jl d ，如何布置使费用最小。 二维指派问题在实际中的应用有：校园建筑物的布局、医院科室的安排、成组技术中加工中心的组成问题等。 ● 旅行商问题(TSP) 旅行商问题：有n 个城市，城市i 与j 之间的距离为ij d ，找一条经过n 个城市的巡回（每个城市经过且只经过一次，最后回到出发点），使得总路程最小。 ● 车辆路径问题(VRP) 车辆路径问题（也称车辆计划）：已知n 个客户的位置坐标和货物需求，在
多目标规划训练例题 某音像商店有5名全职熟练货员和4名兼职售货员，全职售货员每月工作160h,兼职售货员每月工作80h ，根据过去的工作纪录，全职售货员每小时销售CD25张，平均每小时工资15元，加班工资每小时22.5元，兼职售货员每小时销售CD10张，平均工资每小时10元，加班工资每小时10元，现在预测下个月CD 销售量为27500张，商店每周开门营业6天，所以可能要加班，每出售一张CD 盈利1.5元， 商店经理认为，保持稳定的就业水平加上必要的加班，比不加班但就业水平不稳定要好，但全职售货员如果加班过多，就会因为疲劳过度而造成效益下降，因此，不允许每月加班超过100h,建立相应的目标规划模型，并应用Lingo 软件求解。 解：首先建立目标约束的优先级 1P ：下月的CD 销售量达到27500张 2P ：限制全职售货员加班时间不超过100h 3P ：保持全体售货员充分就业，因为充分工作是良好劳资关系的重要因素，但对全职售货 员要比兼职售货员加倍优先考虑 4P ：尽量减少加班时间，但对两种售货员区别对待，优先权因子由他们对利润的贡献而定。 第二，建立目标约束 （1）销售目标约束，设 1x ：全体售货员下月的工作时间； 2x ：全体兼职售货员下月的工作时间； - 1d ：达不到销售目标的偏差； +1d ：超过销售目标的偏差； 希望下月的销售超过27500张CD 片，因此销售目标为 ???=-+++ -- 27500 1025} min{11211d d x x d （2）正常工作时间约束，设 - 2d ：全体全职售货员下月的停工时间； + 2d ：全体全职售货员下月的加班时间； - 3d ：全体兼职售货员下月的停工时间； +3d ：全体兼职售货员下月的加班时间；
27. 多目标规划 一、线性规划的局限性 1. 线性规划要求所求解问题必须满足全部的约束，而实际问题中并非所有约束都需要严格的满足； 2. 线性规划只能处理单目标的优化问题，从而对一些次目标只能转化为约束处理，而实际问题中，目标和约束是可以相互转化的，处理时不一定要严格区分； 3. 线性规划在处理问题时，将各个约束（也可看成目标）的地位看成同等重要，实际问题中，各个目标的重要性有层次上的差别，在同一层次也可能有不同权重； 4. 线性规划寻找最优解，而许多实际问题只要找到满意解就可以了。 例1 (线性规划——生产安排问题) 某企业生产甲、乙两种产品，需要用到A,B,C三种设备，每天产品盈利与设备使用工时及限制如下表： 问：该企业应如何安排生产，能使总利润最大？
解：设甲乙产品的产量分别为x 1, x 2，建立线性规划模型： 12 121212max 200300 s. t. 2212 416 515 ,0z x x x x x x x x =++≤≤≤≥ 用Lingo 可求得最优解：x 1=3, x 2=3, z *=1500. 但实际上，企业的经营目标不仅仅是利润，还需要考虑多个方面，比如：增加下列因素（目标） （1） 力求使利润不低于1500元； （2） 考虑市场需求，甲乙两种产品的产量比应尽量保持1:2； （3） 设备A 位贵重设备，严格禁止超时使用； （4）设备C 可以适当加班，但要控制，设备B 既要求充分利用，又尽可能不加班，在重要性上，设备B 是设备C 的3倍。 这就需要用目标规划。 二、目标规划的基本概念 1. 设置偏差变量 偏差变量——表示实际值与目标值之间的差异； d +——表示超出目标的差值，称为正偏差变量；当实际值超过目标值时，有d - = 0，d +> 0; d -——表示未达到目标的差值，称为负偏差变量；当实际值未达到目标值时，有d + = 0，d ->0. 注：若实际值与目标值一致，有d - = d += 0.