Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
Data,Model and Decisions
数据、模型与决策第 10章
Nonlinear Programming
非线性规划
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
本章内容
10.1 非线性规划的挑战
10.2 边际收益递减的非线性规划
10.3 可分离规划
10.4 复杂非线性规划问题
10.5 Evolutionary Solver 软件和遗传算法 （了解即可）
10.6 小结案例 10.3 跨国投资要求掌握：
1、边际收益递减的二次规划
2、可分离规划
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
Nonlinear Programming
非线性规划 P394
线性规划的目标函数和约束条件都是其自变量（决策变量 X）的线性函数，如果目标函数或约束条件中包含有自变量（决策变量 X）的非线性函数，则这样的规划问题就属于 非线性规划 。
例 1：给定一根长度为 400米的绳子，用来围成一块矩形菜地，问长和宽各为多少，使菜地的面积最大？
假设长为 x1米，宽为 x2米,Max 面积 S=x1*x2
绳子长度（周长）约束,2（ x1+x2）＝ 400 且 x1,x2?0
例 2：对于一般的产品来说，提高价格将会导致需求的减少，反之，会使需求增加。
假设 d＝产品的年需求量,p＝单价，并且公司认为需求价格的关系如下,d＝ 800－ 10p，这里 20?p? 70。
则总收益 Profit＝年需求量 × 单价＝ d× p＝（ 800－ 10p） p
求 p＝？，总收益 P最大，此时的年需求量 d是多少？（ 40，
16000,400）
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
Nonlinear Programming
非线性规划（ 补充 ）
非线性规划的 解 经常是 局部 极大点或极小点（局部最优解
），它使得目标函数在一部分可行域上达到极大值或极小值（ 局部极值 ），具体的解与给定的 决策变量初值 有关（
例子请见 P403图 10.7），我们只能从这些局部最优解中挑选出一个最优解作为最后的答案（我们无法判断一个具体的非线性规划问题到底有几个局部最优解）。
有一些理论来判别局部最优解就是全局最优解（如判断
Min 目标函数 f(X)是否是凸函数，如果是，则该非线性规划就是 凸规划（目标 Min），其局部最优解就是全局最优解,容易想到，线性规划也是一种凸规划（ 目标 Min时 ）
。 反之，对于 Max 目标函数 f(X)要判断是否是 凹函数（利润函数图形上任意两点的连线都在这个图形的下方）,凹规划，我们这章节讲的是目标函数是 Max 利润 P的凹函数
－－边际利润递减的情况：分为连续和分段直线 P398）
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
二次规划（ 补充 ）
若某非线性规划的目标函数为自变量 X的二次函数，约束条件全是线性函数，称这种规划为二次规划 。
二次规划是非线性规划中比较简单的一类，它比较容易求解。很多方面的问题都可以抽象成二次规划的模型（ 10.2节书上举的 2个例子全是二次凹规划 ）。
二次规划是凸规划（目标为 Min时）或凹规划
（目标为 Max时），其局部最优解就是全局最优解。
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
10.1 非线性规划的挑战 P396
非比例关系的挑战 P396
1,线性规划的比例性假设,各种活动对目标函数值的贡献与活动水平成比例，也就是目标函数中各和项是系数与决策变量的乘积。
2,违背比例性假设,每增加一个单位的活动与前面第一个单位创造的收益不同，也就是线性规划活动的收益与活动的水平不成比例（ 目标函数非线性 ）
3,P398四种活动水平 X和其利润 P的关系曲线（
边际收益不同，斜率不同 ），边际收益递减的利润曲线称为 凹函数（函数图形上的任意两点的连线都在这个图形的下方 ）。
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
建立非线性公式的挑战 P399
利润曲线（或成本曲线）的二次形式使用很广泛 。
利润曲线 (公式 ):运用 Excel曲线拟合方法，步骤如下（
P400－ 402）：
1,作 XY散点图（取消图例，省略标题）；
2,用鼠标激活散点图：把鼠标放在任一数据点上，单击鼠标右键
，打开菜单，在菜单栏里选择,添加趋势线,选项，打开,添加趋势线,对话框；
3,在,类型 Type”页面，选择相应的回归分析类型，如多项式（阶数,2）,Excel将显示一条拟合数据点的二次曲线
4,在,选项 Options”页面的下部，选择,显示公式,和,显示 R平方值,选项，单击,确定 OK”按钮，便得到趋势回归图、公式以及 R平方值（ R平方值：用来说明用自变量解释因变量变差的程度，以测量同因变量 y的拟合效果,R2越接近 1越好。本例中：
R2 = 0.9862，表明用自变量 X可解释因变量变差的 98.62%）。
5,最后的拟合曲线为
y = -0.3002x2 + 5.661x + 6.1477
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
非线性规划模型求解的挑战 P402
非线性规划的 解 经常是 局部 极大点或极小点（
局部最优解），它使得目标函数在一部分可行域上达到极大值或极小值（ 局部极值 ），具体的解与给定的 决策变量初值 有关（ 例子请见
P403图 10.7），我们只能从这些局部最优解中挑选出一个最优解作为最后的答案（我们无法判断一个具体的非线性规划问题到底有几个局部最优解）。
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
10.2 边际收益递减的非线性规划 P405
本节中，集中讨论有以下特征的非线性规划问题
1,与线性规划模型的约束条件相同 (线性 )
2,目标函数为 非线性 函数 （二次）
3,违背线性规划比例性假设的每一活动表现为边际收益递减（要求的最大化的目标函数是凹的，而要求的最小化的目标函数是凸的）
这是非线性规划问题中比较简单的类型，使用
Excel的规划求解 Solver就可以求解，因为它获得的解能保证是该类问题的最优解。
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
伟恩德玻璃公司案例研究的续篇：
非线性营销成本的伟恩德问题 P405
门的 营销成本＝ $25D2，每扇门的毛利润为 $375（原来每扇门的净利润为 $300 ）
，因此，每周门的净利润大致为：
门的净利润＝ 375D－ 25D2
同样,窗的 营销成本＝ $66.67W2，窗的毛利润为 $700W（原来窗的净利润为
$500W ），因此：
窗的净利润＝ 700W － 66.67W2
P407 图 10.10显示了两种产品的利润曲线，两者都是具有递减的边际利润。
目标函数（非线性）,Max 利润＝ 375D－ 25D2 ＋ 700W－ 66.67W2
用 Excel的“规划求解”，只需在选项中，不选中“采用线性模型”即可。
W y n d o r P r o b l e m W i t h N o n l i n e a r M a r k e t i n g C o s t s
P 4 0 9 非线性营销成本的伟恩德问题门 D o o r s 窗 W i n d o w s
单位毛利 $375 $700
使用时数 每周可得时数工厂 1 1 0 3,2 1 4 <= 4
工厂 2 0 2 8,3 5 7 <= 12
工厂 3 3 2 1 8,0 0 0 <= 18
门 D o o r s 窗 W i n d o w s
每周生产量 3,2 1 4 4,1 7 9 销售毛利润 $ 4,1 3 0
营销成本 $258 $ 1,1 6 4 总营销成本 $ 1,4 2 2
总利润 $ 2,7 0 8
每个产品所需生产时数
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
伟恩德玻璃公司案例研究的续篇：
非线性营销成本的伟恩德问题（ 数学模型 ）
决策变量,D,W为门和窗的生产数量
目标（非线性）,Max 利润 ＝ 375D-25D2 +700W-66.67W2
约束条件：
工厂 1,D? 4
工厂 2,2W? 12
工厂 3,3D+2W? 18
且非负,D? 0,W? 0
二次规划问题具有线性的约束条件和一个二次的边际收益递减的目标函数
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
运用非线性规划进行有价证券投资组合
Portfolio Selection P410
管理大量证券投资组合的职业经理，现在都习惯于用部分基于非线性规划的计算机模型来指导他们的工作
。因为投资者不仅关心预期回报，还关注着投资带来的相应风险，所以非线性规划被经常用来确定投资的组合，该投资组合在一定的假设下可以获得收益和风险之间的最优平衡。这种方法主要来自于 哈里,马克维茨（ Harry Markowitz）威廉,夏普（ William
Sharpe）开创性的研究，他们因为该项研究而获得了
1990年的诺贝尔经济学奖。
模型的一般表达形式：
Minimize 风险约束条件预期回报?最低可接受水平风险 在这里是以概率论中定义的 回报的方差 来衡量的。利用概率论中的标准公式，目标函数就可以表示为一个决策变量的非线性函数。
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
Portfolio Selection
非线性投资组合例子 P411
三种证券的投资比例（决策变量）－－投资组合
S1— 股票 1占总投资的比例
S2— 股票 2占总投资的比例
S3— 股票 3占总投资的比例
约束条件：这些比例相加必须等于 1,S1+S2+S3=1
根据每种股票的预期回报率，计算整个投资组合的预期回报：
总预期回报＝（ 21S1+30S2+8S3）％
投资者当前选择的最低可接受水平为：
最低可接受预期回报＝ 18％
总风险 (方差 )：每种股票的独立风险 (系数为方差 =标准差的平方 )＋两种股票交叉风险（ 系数为交叉风险＝协方差的 2倍 ），公式为：
Min 总风险（方差）＝
(0.25 2 ) S12+ (0.45 2 ) S22+ (0.052) S32 +2(0.04)S1S2 +2(-0.005)S1S3+2(-0.01)S2S3
注意,P411表 10.2给的风险系数为 标准差和协方差
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
非线性规划模型的代数形式 412
决策变量,三种证券的投资比例（投资组合）
S1— 股票 1占总投资的比例
S2— 股票 2占总投资的比例
S3— 股票 3占总投资的比例
目标,Min 总风险（方差）＝
(0.25 2 ) S12+ (0.45 2 ) S22+ (0.052) S32 +2(0.04)S1S2+2(-0.005)S1S3+2(-0.01)S2S3
约束条件：
预期回报,21S1+30S2+8S3?18
总比例,S1 + S2+ S3＝ 1
且非负,S1,S2,S3? 0
这个模型的目标函数是边际收益递减的，且是二次的，所以是一个二次规划问题。是一个比较简单的非线性规划问题。
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
投资组合的非线性规划电子表格模型 P413
目标函数,Min 总风险（方差） -------非线性，公式复杂
结果,总风险 (方差?2 )=0.0238，总风险 (标准差?)=15.4%<预期回报 (?) ＝ 18％
（说明投资组合最终获得的实际收益不大可能为负）
P o r t f o l i o S e l e c t i o n P r o b l e m ( N o n l i n e a r P r o g r a m m i n g )
P 4 1 3 投资组合问题 ( 非线性规划 )
股票 1 股票 2 股票 3
预期回报 21% 30% 8%
风险 ( 标准差 ) 25% 45% 5%
交叉风险 ( 协方差 ) 股票 1 股票 2 股票 3
股票 1 0,0 4 0 - 0,0 0 5
股票 2 - 0,0 1 0
股票 3
股票 1 股票 2 股票 3 合计投资比例 4 0,2 % 2 1,7 % 3 8,1 % 100% = 100%
最低可接受预期回报总预期回报 1 8,0 % >= 1 8,0 %
总风险 ( 方差 ) 0,0 2 3 8
总风险 ( 标准差 ) 1 5,4 %
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
求总风险（方差）的一种简便方法（ 补充 ）
由于目标函数,总风险（方差）,的公式是非线性的，也复杂，希望找到一种不容易出错且简便的办法
构造协方差矩阵（方差、协方差）
总风险（方差） =
SUMPRODUCT（ MMULT（投资组合,协方差矩阵）,投资组合）
注意,在输入此公式时,要在,投资组合,中先输入数据，如 0协方差矩阵 股票 1 股票 2 股票 3
股票 1 0,0 6 2 5 0,0 4 0 - 0,0 0 5
股票 2 0,0 4 0 0,2 0 3 - 0,0 1 0
股票 3 - 0,0 0 5 - 0,0 1 0 0,0 0 2 5
总风险 ( 方差 ) 0,0 2 3 7 9 2 2 3
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
寻找成本（风险）和收益（预期回报）之间的最佳平衡 P413
利用 Solver Table生成一个表格，表格中给出了当预期回报最低可接受水平在某个范围（ 8％－ 30％，每隔 2％）变动时，分别获得模型最优解时的预期回报与风险（表中还包括三种股票的投资比例）
画风险（标准差）和总预期回报的 XY折线散点图（曲线）
投资者需要在表格和曲线中决定哪个投资组合在预期回报和风险之间提供了最佳平衡。
总风险 总预期最小回报 股票 1 股票 2 股票 3 ( 标准差 ) 回报
4 0,2 % 2 1,7 % 3 8,1 % 1 5,4 % 1 8,0 %
8% 7,1 % 3,7 % 8 9,1 % 3,9 % 9,7 %
10% 8,1 % 4,3 % 8 7,6 % 3,9 % 1 0,0 %
12% 1 6,2 % 8,6 % 7 5,2 % 5,6 % 1 2,0 %
14% 2 4,2 % 1 3,0 % 6 2,8 % 8,6 % 1 4,0 %
16% 3 2,2 % 1 7,3 % 5 0,5 % 1 2,0 % 1 6,0 %
18% 4 0,2 % 2 1,7 % 3 8,1 % 1 5,4 % 1 8,0 %
20% 4 8,2 % 2 6,1 % 2 5,7 % 1 8,9 % 2 0,0 %
22% 5 6,2 % 3 0,4 % 1 3,4 % 2 2,5 % 2 2,0 %
24% 6 4,2 % 3 4,8 % 1,0 % 2 6,1 % 2 4,0 %
26% 4 4,4 % 5 5,6 % 0,0 % 3 0,8 % 2 6,0 %
28% 2 2,2 % 7 7,8 % 0,0 % 3 7,3 % 2 8,0 %
30% 0,0 % 1 0 0,0 % 0,0 % 4 5,0 % 3 0,0 %
0%
5%
10%
15%
20%
25%
30%
35%
0% 10% 20% 30% 40% 50%
总风险( 标准差)
预期回报
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
投资组合优化问题（ 补充 ）
丁以中主编的,管理科学－运用 Spreadsheet建模和求解,P188
投资组合优化，就是确定一组投资项目的最优投资比例。这里所说的,最优,,可以是指在一定风险水平下使得投资回报最大，也可以是指在一定的投资回报水平下使得风险最小。
在 20世纪 50年代,Harry Markowitz研究了一定期望投资回报水平下使得方差最小的最优投资比例问题,Harry Markowitz在该问题上的研究成果以及关于投资的其他研究成果，使他荣获 1990年诺贝尔经济学奖。
先介绍均值、方差、标准差、相关系数、协方差的基本概念，然后用一个例子说明投资组合优化问题的建模与求解方法。
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
投资组合优化问题（ 补充续 ）
单项投资的期望回报率与风险
如果投资对象只有一个，则该投资的回报可以用期望回报率来描述，该投资的风险可以用方差或标准差来描述。下面介绍 期望值,方差 与 标准差 的概念。
用前 n年的回报率（ x1,x2,…,xn ）的期望值来估计本年的 期望回报率?（可用 AVERAGE函数求）
用前 n年的回报率（ x1,x2,…,xn ）的 方差?2（总体方差，可用 VARP函数求）或标准差?（总体标准差，可用 STDEVP函数求） 来估计本年的风险。
即一个投资项目的投资效果可以用投资回报率的期望值和方差（或标准差）描述，前者反映了该项投资的回报水平；后者反映了该项投资的风险状况。
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
投资组合优化问题（ 补充续 ）
一组投资（即多项投资）的期望回报与风险
如果投资对象不止一个，则该组投资的总回报率不仅与各投资项目的单项期望回报率有关，而且与各项目的投资比例有关。设一组投资由
m个投资项目组成，它们的单项期望回报率为（?1,?2,…,?m ）
，对该 m个项目的投资比例为（ S1,S2,…,Sm ），则该组投资的总回报率 R的期望值为单项回报率与相应的投资比例的乘积之和。其估算公式如下：
R的期望值 ＝ S1?1 ＋ S2?2 ＋ … ＋ Sm?m
总回报率 R的 方差 估算公式如下：
R的方差 ＝
其中 rij为投资 i和 j的相关系数（可用 CORREL函数求）
COVij为投资 i和 j的协方差（可用 COVAR函数求）
即一组投资项目的投资效果可以用投资组合的总回报率的期望值和方差（或标准差）描述，前者反映了该组投资的总体回报水平；后者反映了该组投资的总体风险状况。
2 2 2 2 2 2
1 1 2 2
1 1 1 1
m m i j ij i j
ij
m m m m
i j ij i j i j ij
i j i j
S S S S S
S S S S C O V
r
r
说明：题目有的给相关系数
、有的给协方差
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
投资组合优化问题（ 补充续 ）
用 Excel计算期望值、方差、协方差
期望值用 AVERAGE函数、方差用 VARP函数（总体方差
）、标准差用 STDEVP函数（总体标准差）、相关系数用
CORREL函数、协方差用 COVAR函数。
例子：现有三个可投资的项目：股票 1，股票 2和债券。它们自 1985年至 2004年 20年的投资回报率（见 Excel文件）
。分别计算这三个项目的单项投资回报率的期望值、方差
、以及三个项目之间的协方差矩阵。
方法,
1,期望值用 AVERAGE函数求；
2,方差用 VARP函数求（总体方差）；
3,协方差用 COVAR函数求；
4,还可以用,工具 ->数据分析 ->协方差,计算协方差矩阵（包括方差和协方差），只需输入三个项目的历史数据所在地址区域
（包括标题和数据）以及输出区域，就可得到三个项目的协方差矩阵。
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
投资组合优化问题（ 补充续 ）
投资组合优化模型
计算上面例子中对三个投资项目（股票 1，股票 2和债券）的最优投资比例 S1,S2,S3，要求在总投资回报率不低于 13％的前提下，使得投资的总风险最小（见 Excel文件）。
方法,
1,决策变量：各投资项目的投资比例 S1,S2,S3
2,目标函数,构造协方差矩阵，总风险（方差） =
SUMPRODUCT（ MMULT（投资比例,协方差矩阵）,投资比例）
3,约束条件投资组合总回报率的期望值约束投资比例之和应等于 1
非负
结果,股票 1、股票 2、债券的投资比例为 50.63%:32.43%:16.93%。
总风险 (方差?2 )=0.0143，总风险 (标准差?)=12%<预期回报 (?)=13％
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
10.3 Separable Programming
可分离规划 P414
对利润或成本曲线是分段直线并且边际收益递减的非线性规划问题,可分离规划技术 将问题转换成相应的线性规划问题。
总利润（或总成本）仅是从单个活动的分段直线利润（或成本）曲线上直接获得的利润（或成本）相加得到的 总和 。
由于每条利润（或成本）曲线都存在直线段，
所以这个技术将模型描述转换为线性规划模型
。这有助于非常有效地求解模型，并且可以对线性规划运用 What-If分析的强大工具。
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
每周最大产量 产品的单位利润产品 正常工作时间加班时间总计 正常工作时间加班时间门 3 1 4
(D?4)
$300 $200
窗 3 3 6
(2W?12)
$500 $100
（ 3D＋ 2W?18）－－工厂 3的约束需要加班时伟恩德玻璃公司问题 P415
产品（门和窗），在正常时间和加班时间，单位利润不同（递减），表中给出了工厂 1和工厂 2每周在正常工作时间和加班工作时间生产门和窗的最大数量。
每周产品利润与每周产量间的关系图（折线）,P416
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
P416 可分离规划技术
The Separable Programming Technique
对于违背比例性假设的任一活动，将其利润线划分成多段，使得每一段为直线线段
,为利润线上的每一直线段引入新的可分决策变量，以代替原来的单一决策变量 。
因为每一直线段的新决策变量仍然遵循比例性假设，因此可以为这些决策变量建立线性规划 模型
非线性规划－ >线性规划
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
需要加班时的伟恩德可分离规划问题的 代数模型 （补充）
利用可分离规划技术，将每周门和窗生产量（ 2个决策变量）分为正常工作时间和加班工作时间的每周生产量（ 2× 2＝ 4个决策变量）
决策变量：
DR,DO为正常工作时间和加班工作时间每周门的生产量
WR,WO为正常工作时间和加班工作时间每周窗的生产量目标,最大化 净利润 P=300DR ＋ 200DO ＋ 500WR ＋ 100WO
约束条件：
工厂 1,DR ＋ DO? 4
工厂 2,2 (WR ＋ WO )? 12
工厂 3,3 (DR ＋ DO)+2 (WR ＋ WO)? 18
每周最大产量,DR? 3,DO? 1,WR?3,WO?3
且 非负,DR,DO,WR,WO?0
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
需要加班时的伟恩德可分离规划问题的 代数模型 2 （补充）
利用可分离规划技术，将每周门和窗生产量（ 2个决策变量）分为正常工作时间和加班工作时间的每周生产量（ 2× 2＝ 4个决策变量），
这样共 2＋ 4＝ 6个决策变量决策变量：
D为 每周门的生产量,W为每周窗的生产量
DR,DO为正常工作时间和加班工作时间每周门的生产量
WR,WO为正常工作时间和加班工作时间每周窗的生产量目标,最大化 净利润 P=300DR＋ 200DO ＋ 500WR ＋ 100WO
约束条件：
总的生产量：
门,D = DR ＋ DO
窗,W = WR ＋ WO
工厂 1,D? 4
工厂 2,2W? 12
工厂 3,3D+2W? 18
每周最大产量,DR? 3,DO? 1,WR? 3,WO? 3
且 非负,D,W,DR,DO,WR,WO? 0
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
需要加班时的伟恩德可分离规划问题的电子表格模型 P417
由于边际收益递减，为了使总利润最大化，最优解肯定会先自动地用完正常的工作时间，才开始采取加班的措施。
W y n d o r P r o b l e m w i t h O v e r t i m e ( S e p a r a b l e P r o g r a m m i n g )
P 4 1 7 有加班的伟恩德公司问题（可分离规划）
单位利润 门 D o o r s 窗户 W i n d o w s
正常时间 $300 $500
加班时间 $200 $100
使用时数 每周可得时数工厂 1 1 0 4 <= 4
工厂 2 0 2 6 <= 12
工厂 3 3 2 18 <= 18
门 D o o r s 窗户 W i n d o w s 门 D o o r s 窗户 W i n d o w s
正常时间 3 3 <= 3 3
加班时间 1 0 <= 1 3
总生产量 4 3
总利润 $ 2,6 0 0
每个产品所需生产时数每周最大产量 M a x i m u m每周生产量
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
P418 对光华利润曲线应用可分离规划
在可分离规划的一些应用中，利润线是一条曲线而非一系列的直线段。
P419图 10.17中的实线显示了这样的一条利润曲线,为了能够应用可分离规划,这条曲线可以近似为一系列的直线段。
非线性规划－ >线性规划
还是要求边际收益递减
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
存在加班成本和非线性营销成本的伟恩德问题 P419
门的 营销成本 =$25D2,窗的 营销成本 =$66.67W2
单位毛利润：单位利润 (P415表 10.3)+营销成本
(每扇门 75美元，每扇窗 200美元 )。
产品每周最大产量 单位毛利润（美元）
正常工作时间加班时间 总计正常工作时间加班时间营销成本门 3 1 4(D?4) 375(300+75) 275(200+75) 25D2
窗 3 3 6(2W?12) 700(500+200) 300(100+200) 66.67W2
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
存在 加班成本和 非线性营销成本的伟恩德 问题 P419
计算每周生产 D扇门时，伟恩德公司周利润表
(P419),然后再绘制门的利润曲线（ P421）
计算每周生产 W扇窗时，伟恩德公司周利润表
(P420),然后再绘制窗的利润曲线（ P421）
两条利润曲线都是边际收益递减的
当分段直线与实际利润曲线非常近似时，使用 可分离规划是相当好的。
方法 1：用可分离规划（ 我感觉麻烦些 ）
方法 2：用非线性规划（ 感觉简单些，我推荐这种方法 ）
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
存在 加班成本和 非线性营销成本的伟恩德 问题 P419-422
方法 1：用可分离规划（ 了解即可 ）
W y n d o r w i t h O v e r t i m e a n d M a r k e t i n g C o s t s ( S e p a r a b l e )
P 4 2 2 有加班成本和非线性营销成本的伟恩德问题( 可分离规划)
单位利润 门 D o o r s 窗 W i n d o w s
正常时间 ( 0 - 1 ) $ 3 5 0,0 0 $ 6 3 3,3 3
正常时间 ( 1 - 2 ) $ 3 0 0,0 0 $ 5 0 0,0 0
正常时间 ( 2 - 3 ) $ 2 5 0,0 0 $ 3 6 7,6 7
加班时间 $ 1 0 0,0 0 - $ 3 0 0,0 0
使用时数 每周可得时数工厂 1 1 0 4 <= 4
工厂 2 0 2 6 <= 12
工厂 3 3 2 18 <= 18
门 D o o r s 窗 W i n d o w s 门 D o o r s 窗 W i n d o w s
正常时间 ( 0 - 1 ) 1 1 <= 1 1
正常时间 ( 1 - 2 ) 1 1 <= 1 1
正常时间 ( 2 - 3 ) 1 1 <= 1 1
加班时间 1 0 <= 1 3
总生产量 4 3
总利润 $ 2,5 0 1
每周最大产量每个产品所需生产时数每周生产量将两条利润曲线各近似成四段利润直线（ 2个－
>2*4个决策变量
）
单位利润：直线线段的斜率（表中最后一列增加的利润）
结果：每周生产
4扇门（ 1个加班生产）,3扇窗
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
存在 加班成本和 非线性营销成本的伟恩德 问题 P421
方法 2：用非线性规划（ 我推荐此方法 ）
非线性规划（
营销成本）
区分正常工作时间和加班时间
结果：每周生产 4扇门（ 1个加班生产）,3
扇窗
请自己写代数模型
W y n d o r W i t h O v e r t i m e a n d M a r k e t i n g C o s t s ( N o n l i n e a r P r o g r a m m i n g )
P 4 2 3 有加班成本和非线性营销成本的伟恩德问题( 非线性规划)
单位毛利润 门 D o o r s 窗 W i n d o w s
正常时间 $375 $700
加班时间 $275 $300
使用时数 每周可得时数工厂 1 1 0 4 <= 4
工厂 2 0 2 6 <= 12
工厂 3 3 2 18 <= 18
每周生产量 门 D o o r s 窗 W i n d o w s 门 D o o r s 窗 W i n d o w s
正常时间 3 3 <= 3 3
加班时间 1 0 <= 1 3
总生产量 4 3
销售毛利润 $ 3,5 0 0
营销成本 $400 $600 总营销成本 $ 1,0 0 0
总利润 $ 2,5 0 0
每个产品所需生产时数每周最大产量
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
补充：非线性规划问题的思考题
（ 请写数学模型 ）
某公司 有资金 10万元,若投资于项目 i（ i=1,2,3） 的投资额为 xi时
,其 收 益 分 别 为 g1(x1)=4x1,
g2(x2)=9x2,g3(x3)=2x32,问应如何分配投资额才能使总收益最大？ （ 结果,x3＝ 10）
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
10.4 复杂非线性规划问题 P424
前面讨论的两个例子都是简单的二次规划问题,要求 边际收益递减,此时 Solver就可以很容易地找到最优解 。 有时还可以用可分离规划来模拟 （ 或近似 ） 一个非线性规划问题
,以此来 利用线性规划 迅速找到最优解 。
但对 边际收益递增,标准的 Solver通常很难求解
如果存在多个局部最优解,从不同的初始点开始多次运行
Solver找到全局最优解－－－可以用 Solver Table来实现小规模的非线性规划问题 （ P425） 。
存在多个局部最优解的大规模的非线性规划问题或多个变量的非线性规划问题,或使用了 IF,ABS,MAX,ROUND的例子,有时 Solver连局部最优解也找不到 。
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
复杂非线性规划问题（ 补充例子 ）
合理安排值班表
合理安排值班表往往是每一个值班组长苦恼的问题,因为每个职工都有自己的私事,要合理解决两者之间的冲突,又不能经常改动值班表,以防大家记不住 。 要求：
1,职工 A要求比职工 C晚一天值班 （ A＝ C＋ 1）
2,职工 D要求在职工 E的前一天的后三天值班
（ D＝ E－ 1＋ 3）
3,职工 B要求比职工 G的早三天值班 （ B＝ G－ 3
,即 G＝ B＋ 3）
4,B,C两职工必须安排在 F职工值班的前后若干天之间 （ B＝ F－ X,C＝ F＋ X）
5,F职工要求安排在星期四值班 （ F＝ 4）
根据这些要求,找出值班关系表 （ 见右 ）,
求解：
设计目标值：将七天的乘积作为目标值,即
P＝ A*B*… *G（ 用 PRODUCT连乘函数实现
） ＝ 5040＝ 1*2*3*4*5*6*7
决策变量,E,X
约束,E,X为整数,非负具体见 Excel文件职工 值班关系表
A C+1=(4+X)+1=X+5
B F-X=4-X
C F+X=4+X
D E-1+3=E+2 若干天
E E X
F 4
G B+3=(4-X)+3=7-X
结果，一份可以让每个人满意的值班表已经完成，可见
，只要合理巧妙地设置参数
，规划求解就可以帮我们解决许多实际问题。
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
10.5 Evolutionary Solver 软件和遗传算法 P426 （了解即可）
Premium Solver,Frontline System,Excel中标准 Solver的开发商开发的 Premium版本,增加了新的搜索程序称之为
Evolutionary Solver,它的基本原理是根据遗传学,进化论和适者生存原理建立的 （ 遗传算法 ）
例子：选择高于市场收益的有价证券投资组合 。
5个股票：美国在线 (AOL),波音 (BA),福特 (F),宝洁 (PG),麦当劳 (MCD)
股票数据：显示了这些股票 6年 （ 1995－ 2001年 ） 的季度业绩
纽约证券交易所综合指数计算的市场整体的业绩
目标：选择在这个阶段中高于市场收益的季度数量最多的投资组合
直接利用标准 Solver求解,得 14次 （ 在 6年 × 4＝ 24季度 ）
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
应用 Evolutionary Solver来选择高于市场收益的投资组合 P427 （了解即可）
安装 Premium Solver：在光盘 Premium Solver文件夹下
,运行 PremSolv文件安装即可 。 安装完毕后,Premium
Solver 将代替 Excel原来的 Solver（ 规划求解 ）,界面也变成英文的,具体 P428。 有三种算法可供选择 （ 1,标准
GRG非线性－－等同于使用没有选择,假设线性模型,
的选项的标准 Solver,2,标准 Simplex LP－－相当于使用选择了,假设线性模型,的选项的标准 Solver,3,标准 Evolutionary－－新的 ） 。
利用 Premium Solver的,标准 Evolutionary”求解,我运行的结果得 18次 （ 在 6年 × 4＝ 24季度 ） －－都采用默认选项
Evolutionary Solver的优点和缺点：
优点：可以处理复杂的目标函数和有多个局部最优解的问题
缺点：不是万能的,1,时间长 2,最佳解有可能不是最优解 。
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
10.6 Summary 小结 P432
非线性规划：至少有一个目标函数或约束函数是非线性的 （ 通常只有目标函数 ）
建立和求解非线性规划模型通常比建立和求解线性规划模型更困难 （ 因为可能有许多局部最优解 ）
然而,当非线性规划模型是边际收益递减时,比较容易求解
当利润曲线是分段直线 （ 近似 ） 时,可以使用可分离规划将问题转化为线性规划问题 。
对于更复杂的非线性规划模型,如有许多局部最优解
,可以多次运行 Solver,每次输入不同的初始解－－
可以用 Solver Table实现
更复杂的非线性规划模型,可以使用有遗传算法的
Evolutionary Solver
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
P441 案例 10.3 跨国投资债券投资、利息税问题
4年前购买了 30000德国马克 （ DM） 的七年期的 B债券
,债券回报率 （ 本金和利息 ） 较高,如 P441的表 2
现在 （ 第 5年初 ）,如果没有利息税的话,最后一年卖比较合适,但从现在开始,要交利息税 （ 利息中获得的前 6100DM是不用缴税的,超过 6100DM的部分税率为 30%,所以卖出的决策要改变,以合理避税 。
售出债券后,得到的资金还可以购买利息为 4%的存款单 （ 一年期 ）
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
P441 案例 10.3 跨国投资数学模型（ b）
查尔斯的投资策略是第 5,6,7年年末卖掉的 B债券 。 直观上看,此问题的决策变量应该是这三年年末卖掉的 B债券量 。 但由于资本利息税的存在,利息在 6100马克以上和以下待遇是不同的,因此在计算净得利息时,需要用到 IF函数,将得到一个非线性模型 。 但试想,如果视每一年卖掉的债券为两部分,6100以下不缴税部分和 6100以上缴税部分
,则可以避开 IF函数,总利息是 3× 2＝ 6个决策变量的线性函数 。
先由表 2计算第 5,6,7年卖出债券时的回报率,例如第 5年卖出的回报率为 （ 第 5年 100马克的总回报 -100） /100,即 0.5001
约束情况,a) 不缴税部分债券利息不超过 6100
b) 三年卖出的总债券为初始投资 30000德国马克
c) 决策变量非负
由此得如下数学模型：
51 52 61 62 71 72
51 52
61 62
71 72
51
,,,,,
Ma x P 0.5 00 1 0.5 00 1 ( 1 30 % )
0.6 35 1 0.6 3 51 ( 1 30 % )
0.7 82 3 0.7 8 23 ( 1 30 % )
0,50 01 61 0
s.t,
x x x x x x
xx
xx
xx
x
决策变量：
目标函数：
61 71
51 52 61 62 71 72
51 52 61 62 71 72
0,0.6 35 1 61 00,0.7 82 3 61 00
30000
,,,,,0
xx
x x x x x x
x x x x x x
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
P441 案例 10.3 跨国投资数学模型（ d）
在考虑存款单 （ 一年期 ） 的情况下,由于存款单也要考虑资本利息税,故同样把购买的存款单分为卖出时不缴利息税和缴利息税两部分 。 不缴税部分回报率为 4%,缴税部分回报率为 4%*（ 1-30%） =2.8%。
约束情况,1） 不缴税部分总利息不超过 6100
2） 三年卖出的总债券为初始投资 30000马克
3） 第 5,6年年末购买的存款单不超过当年年末可用资金 。 第 5年年末可用资金为卖掉 B债券后的收入,第 6年年末为卖掉 B债券和前一年购买的存款单后的收入 。
4） 决策变量非负
5 1 5 2 6 1 6 2 7 1 7 2 5 1 5 2 6 1 6 2
5 1 5 2
6 1 6 2 5 1 5 2
7 1 7 2 6 1 6 2
,,,,,,,,,
M a x P 0,50 01 0,50 01 ( 1 30 %)
0.6351 0.6351 ( 1 30% ) 0.04 ( 1 30% )
0.7823 0.7823 ( 1 30% ) 0.04 ( 1 30% )
x x x x x x y y y y
xx
x x y y
x x y y
决策变量：
目标函数：
5 1 6 1 5 1
7 1 6 1
5 1 5 2 6 1 6 2 7 1 7 2
5 1 5 2 5 1 5 2
6 1 6 2 6 1 6 2
0,5 00 1 61 00,0,63 51 0,04 61 00
0,78 23 0,04 61 00
30000
s,t,( 1 0,50 01 ) ( 1 0,50 01 70 %)
( 1 0,63 51 ) ( 1 0,63 51 70 %)
( 1 0,04)
x x y
xy
x x x x x x
y y x x
y y x x
y
5 1 5 2
5 1 5 2 6 1 6 2 7 1 7 2 5 1 5 2 6 1 6 2
( 1 0,0 4 70 %)
,,,,,,,,,0
y
x x x x x x y y y y
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
P441 案例 10.3 跨国投资答案
b,总利息收入为 19099德国马克
d,总利息收入为 20070德国马克
f,在 d基础上,总利息收入为 22183德国马克,22183－ 20070＝ 2113
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
补充：非线性规划问题的思考题
（ 请写数学模型并实现 ）
1,一个饮食店卖包子和馒头两种早点,每卖出 10茏包子或馒头饮食店分别可以获利 6元或 4元；每做 10茏包子或 10茏馒头分别需要花费 2小时或 1小时人工,而饮食店工人每天可以用来加工包子或馒头的总时间不能超过 9小时；摆放 10茏包子或 10茏馒头分别需要 2层或 3层货架,而饮食店的货架总数为 16层；此外,由于销售能力的限制饮食店每天销售的包子与馒头的总数不能超过 60茏 。 试问在上述条件的限制下,饮食店应该如何安排每天生产的包子与馒头的数量才能获得最大的利润 。 （ 注意：以 10茏为单位
） 结果,（ 3,3）,P=30元
2,非线性规划：假定饮食店使用的人工费用是每小时 5元,加工 10茏包子或 10茏馒头的原料费用分别为 28
元或 22元,而销售 10茏包子或 10茏馒头的单价 （ 不是常数而是依赖于包子或馒头的销售数量 q1,q2）
分别为 p1=47-q1,p2=34-q2。 试确定此时利润达到最大的生产销售安排,即包子与馒头各应生产与销售多少数量 。 结果,（ 3.1,2.8）,P=30.05元
3,在 2问题中取消包子与馒头售价与销售数量有关的假设,但假设在该饮食店所在地区很多居民清晨上班时很喜欢吃包子,因此饮食店每天总可以将前 10茏包子以较高的价格卖出 。 具体地说,前 10茏包子的售价可以达到每 10茏 46元 （ 高价包子 ）,而这 10茏包子卖出之后其余包子的售价则为每 10茏 44元 （ 平价包子 ） 。 馒头的售价却是固定的：每 10茏 31元 。 试确定在此情况下每天包子与馒头的最优销售数量和饮食店所能达到的最大利润 。 结果,（ 3,3）,P=32元
4,在 2问题中,其包子原料 （ 例如猪肉 ） 供应商提出一个优惠条件：只要饮食店购买超过 50茏包子所需的原料就将每做 10茏包子所需原料的价格由 28元减至 24元 。 还有,总人工时间和货架总数为原来的 2倍,
每天销售的包子与馒头的总数不能超过 120茏,为试确定在饮食店接受这一优惠条件下的最优销售安排
。 结果,(1)初值为 （ 4,6） 结果为 （ 4.5,3.5）,P=32.5元
(2)初值为 （ 2,1） 结果为 （ 6.5,3.5）,P=54.5元
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
Exercise
作业（上机）
P433 习题：
10.4,10.6(股票 2的标准差改为 30000),
10.9 （可分离规划）
10.11 （可分离规划） 注意：从本章开始的后面 3章的作业，请交电子报告：
1、数学模型（公式编辑器）
2、电子表格模型
3、结果
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
案例分析作业
P440案例 10.2 了解投资组合注意,给的是方差,协方差 （ 可以直接构造协方差矩阵 ）
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
Data,Model and Decisions
数据、模型与决策第 10章
Nonlinear Programming
非线性规划
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
本章内容
10.1 非线性规划的挑战
10.2 边际收益递减的非线性规划
10.3 可分离规划
10.4 复杂非线性规划问题
10.5 Evolutionary Solver 软件和遗传算法 （了解即可）
10.6 小结案例 10.3 跨国投资要求掌握：
1、边际收益递减的二次规划
2、可分离规划
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
Nonlinear Programming
非线性规划 P394
线性规划的目标函数和约束条件都是其自变量（决策变量 X）的线性函数，如果目标函数或约束条件中包含有自变量（决策变量 X）的非线性函数，则这样的规划问题就属于 非线性规划 。
例 1：给定一根长度为 400米的绳子，用来围成一块矩形菜地，问长和宽各为多少，使菜地的面积最大？
假设长为 x1米，宽为 x2米,Max 面积 S=x1*x2
绳子长度（周长）约束,2（ x1+x2）＝ 400 且 x1,x2?0
例 2：对于一般的产品来说，提高价格将会导致需求的减少，反之，会使需求增加。
假设 d＝产品的年需求量,p＝单价，并且公司认为需求价格的关系如下,d＝ 800－ 10p，这里 20?p? 70。
则总收益 Profit＝年需求量 × 单价＝ d× p＝（ 800－ 10p） p
求 p＝？，总收益 P最大，此时的年需求量 d是多少？（ 40，
16000,400）
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
Nonlinear Programming
非线性规划（ 补充 ）
非线性规划的 解 经常是 局部 极大点或极小点（局部最优解
），它使得目标函数在一部分可行域上达到极大值或极小值（ 局部极值 ），具体的解与给定的 决策变量初值 有关（
例子请见 P403图 10.7），我们只能从这些局部最优解中挑选出一个最优解作为最后的答案（我们无法判断一个具体的非线性规划问题到底有几个局部最优解）。
有一些理论来判别局部最优解就是全局最优解（如判断
Min 目标函数 f(X)是否是凸函数，如果是，则该非线性规划就是 凸规划（目标 Min），其局部最优解就是全局最优解,容易想到，线性规划也是一种凸规划（ 目标 Min时 ）
。 反之，对于 Max 目标函数 f(X)要判断是否是 凹函数（利润函数图形上任意两点的连线都在这个图形的下方）,凹规划，我们这章节讲的是目标函数是 Max 利润 P的凹函数
－－边际利润递减的情况：分为连续和分段直线 P398）
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
二次规划（ 补充 ）
若某非线性规划的目标函数为自变量 X的二次函数，约束条件全是线性函数，称这种规划为二次规划 。
二次规划是非线性规划中比较简单的一类，它比较容易求解。很多方面的问题都可以抽象成二次规划的模型（ 10.2节书上举的 2个例子全是二次凹规划 ）。
二次规划是凸规划（目标为 Min时）或凹规划
（目标为 Max时），其局部最优解就是全局最优解。
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
10.1 非线性规划的挑战 P396
非比例关系的挑战 P396
1,线性规划的比例性假设,各种活动对目标函数值的贡献与活动水平成比例，也就是目标函数中各和项是系数与决策变量的乘积。
2,违背比例性假设,每增加一个单位的活动与前面第一个单位创造的收益不同，也就是线性规划活动的收益与活动的水平不成比例（ 目标函数非线性 ）
3,P398四种活动水平 X和其利润 P的关系曲线（
边际收益不同，斜率不同 ），边际收益递减的利润曲线称为 凹函数（函数图形上的任意两点的连线都在这个图形的下方 ）。
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
建立非线性公式的挑战 P399
利润曲线（或成本曲线）的二次形式使用很广泛 。
利润曲线 (公式 ):运用 Excel曲线拟合方法，步骤如下（
P400－ 402）：
1,作 XY散点图（取消图例，省略标题）；
2,用鼠标激活散点图：把鼠标放在任一数据点上，单击鼠标右键
，打开菜单，在菜单栏里选择,添加趋势线,选项，打开,添加趋势线,对话框；
3,在,类型 Type”页面，选择相应的回归分析类型，如多项式（阶数,2）,Excel将显示一条拟合数据点的二次曲线
4,在,选项 Options”页面的下部，选择,显示公式,和,显示 R平方值,选项，单击,确定 OK”按钮，便得到趋势回归图、公式以及 R平方值（ R平方值：用来说明用自变量解释因变量变差的程度，以测量同因变量 y的拟合效果,R2越接近 1越好。本例中：
R2 = 0.9862，表明用自变量 X可解释因变量变差的 98.62%）。
5,最后的拟合曲线为
y = -0.3002x2 + 5.661x + 6.1477
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
非线性规划模型求解的挑战 P402
非线性规划的 解 经常是 局部 极大点或极小点（
局部最优解），它使得目标函数在一部分可行域上达到极大值或极小值（ 局部极值 ），具体的解与给定的 决策变量初值 有关（ 例子请见
P403图 10.7），我们只能从这些局部最优解中挑选出一个最优解作为最后的答案（我们无法判断一个具体的非线性规划问题到底有几个局部最优解）。
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
10.2 边际收益递减的非线性规划 P405
本节中，集中讨论有以下特征的非线性规划问题
1,与线性规划模型的约束条件相同 (线性 )
2,目标函数为 非线性 函数 （二次）
3,违背线性规划比例性假设的每一活动表现为边际收益递减（要求的最大化的目标函数是凹的，而要求的最小化的目标函数是凸的）
这是非线性规划问题中比较简单的类型，使用
Excel的规划求解 Solver就可以求解，因为它获得的解能保证是该类问题的最优解。
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
伟恩德玻璃公司案例研究的续篇：
非线性营销成本的伟恩德问题 P405
门的 营销成本＝ $25D2，每扇门的毛利润为 $375（原来每扇门的净利润为 $300 ）
，因此，每周门的净利润大致为：
门的净利润＝ 375D－ 25D2
同样,窗的 营销成本＝ $66.67W2，窗的毛利润为 $700W（原来窗的净利润为
$500W ），因此：
窗的净利润＝ 700W － 66.67W2
P407 图 10.10显示了两种产品的利润曲线，两者都是具有递减的边际利润。
目标函数（非线性）,Max 利润＝ 375D－ 25D2 ＋ 700W－ 66.67W2
用 Excel的“规划求解”，只需在选项中，不选中“采用线性模型”即可。
W y n d o r P r o b l e m W i t h N o n l i n e a r M a r k e t i n g C o s t s
P 4 0 9 非线性营销成本的伟恩德问题门 D o o r s 窗 W i n d o w s
单位毛利 $375 $700
使用时数 每周可得时数工厂 1 1 0 3,2 1 4 <= 4
工厂 2 0 2 8,3 5 7 <= 12
工厂 3 3 2 1 8,0 0 0 <= 18
门 D o o r s 窗 W i n d o w s
每周生产量 3,2 1 4 4,1 7 9 销售毛利润 $ 4,1 3 0
营销成本 $258 $ 1,1 6 4 总营销成本 $ 1,4 2 2
总利润 $ 2,7 0 8
每个产品所需生产时数
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
伟恩德玻璃公司案例研究的续篇：
非线性营销成本的伟恩德问题（ 数学模型 ）
决策变量,D,W为门和窗的生产数量
目标（非线性）,Max 利润 ＝ 375D-25D2 +700W-66.67W2
约束条件：
工厂 1,D? 4
工厂 2,2W? 12
工厂 3,3D+2W? 18
且非负,D? 0,W? 0
二次规划问题具有线性的约束条件和一个二次的边际收益递减的目标函数
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
运用非线性规划进行有价证券投资组合
Portfolio Selection P410
管理大量证券投资组合的职业经理，现在都习惯于用部分基于非线性规划的计算机模型来指导他们的工作
。因为投资者不仅关心预期回报，还关注着投资带来的相应风险，所以非线性规划被经常用来确定投资的组合，该投资组合在一定的假设下可以获得收益和风险之间的最优平衡。这种方法主要来自于 哈里,马克维茨（ Harry Markowitz）威廉,夏普（ William
Sharpe）开创性的研究，他们因为该项研究而获得了
1990年的诺贝尔经济学奖。
模型的一般表达形式：
Minimize 风险约束条件预期回报?最低可接受水平风险 在这里是以概率论中定义的 回报的方差 来衡量的。利用概率论中的标准公式，目标函数就可以表示为一个决策变量的非线性函数。
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
Portfolio Selection
非线性投资组合例子 P411
三种证券的投资比例（决策变量）－－投资组合
S1— 股票 1占总投资的比例
S2— 股票 2占总投资的比例
S3— 股票 3占总投资的比例
约束条件：这些比例相加必须等于 1,S1+S2+S3=1
根据每种股票的预期回报率，计算整个投资组合的预期回报：
总预期回报＝（ 21S1+30S2+8S3）％
投资者当前选择的最低可接受水平为：
最低可接受预期回报＝ 18％
总风险 (方差 )：每种股票的独立风险 (系数为方差 =标准差的平方 )＋两种股票交叉风险（ 系数为交叉风险＝协方差的 2倍 ），公式为：
Min 总风险（方差）＝
(0.25 2 ) S12+ (0.45 2 ) S22+ (0.052) S32 +2(0.04)S1S2 +2(-0.005)S1S3+2(-0.01)S2S3
注意,P411表 10.2给的风险系数为 标准差和协方差
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
非线性规划模型的代数形式 412
决策变量,三种证券的投资比例（投资组合）
S1— 股票 1占总投资的比例
S2— 股票 2占总投资的比例
S3— 股票 3占总投资的比例
目标,Min 总风险（方差）＝
(0.25 2 ) S12+ (0.45 2 ) S22+ (0.052) S32 +2(0.04)S1S2+2(-0.005)S1S3+2(-0.01)S2S3
约束条件：
预期回报,21S1+30S2+8S3?18
总比例,S1 + S2+ S3＝ 1
且非负,S1,S2,S3? 0
这个模型的目标函数是边际收益递减的，且是二次的，所以是一个二次规划问题。是一个比较简单的非线性规划问题。
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
投资组合的非线性规划电子表格模型 P413
目标函数,Min 总风险（方差） -------非线性，公式复杂
结果,总风险 (方差?2 )=0.0238，总风险 (标准差?)=15.4%<预期回报 (?) ＝ 18％
（说明投资组合最终获得的实际收益不大可能为负）
P o r t f o l i o S e l e c t i o n P r o b l e m ( N o n l i n e a r P r o g r a m m i n g )
P 4 1 3 投资组合问题 ( 非线性规划 )
股票 1 股票 2 股票 3
预期回报 21% 30% 8%
风险 ( 标准差 ) 25% 45% 5%
交叉风险 ( 协方差 ) 股票 1 股票 2 股票 3
股票 1 0,0 4 0 - 0,0 0 5
股票 2 - 0,0 1 0
股票 3
股票 1 股票 2 股票 3 合计投资比例 4 0,2 % 2 1,7 % 3 8,1 % 100% = 100%
最低可接受预期回报总预期回报 1 8,0 % >= 1 8,0 %
总风险 ( 方差 ) 0,0 2 3 8
总风险 ( 标准差 ) 1 5,4 %
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
求总风险（方差）的一种简便方法（ 补充 ）
由于目标函数,总风险（方差）,的公式是非线性的，也复杂，希望找到一种不容易出错且简便的办法
构造协方差矩阵（方差、协方差）
总风险（方差） =
SUMPRODUCT（ MMULT（投资组合,协方差矩阵）,投资组合）
注意,在输入此公式时,要在,投资组合,中先输入数据，如 0协方差矩阵 股票 1 股票 2 股票 3
股票 1 0,0 6 2 5 0,0 4 0 - 0,0 0 5
股票 2 0,0 4 0 0,2 0 3 - 0,0 1 0
股票 3 - 0,0 0 5 - 0,0 1 0 0,0 0 2 5
总风险 ( 方差 ) 0,0 2 3 7 9 2 2 3
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
寻找成本（风险）和收益（预期回报）之间的最佳平衡 P413
利用 Solver Table生成一个表格，表格中给出了当预期回报最低可接受水平在某个范围（ 8％－ 30％，每隔 2％）变动时，分别获得模型最优解时的预期回报与风险（表中还包括三种股票的投资比例）
画风险（标准差）和总预期回报的 XY折线散点图（曲线）
投资者需要在表格和曲线中决定哪个投资组合在预期回报和风险之间提供了最佳平衡。
总风险 总预期最小回报 股票 1 股票 2 股票 3 ( 标准差 ) 回报
4 0,2 % 2 1,7 % 3 8,1 % 1 5,4 % 1 8,0 %
8% 7,1 % 3,7 % 8 9,1 % 3,9 % 9,7 %
10% 8,1 % 4,3 % 8 7,6 % 3,9 % 1 0,0 %
12% 1 6,2 % 8,6 % 7 5,2 % 5,6 % 1 2,0 %
14% 2 4,2 % 1 3,0 % 6 2,8 % 8,6 % 1 4,0 %
16% 3 2,2 % 1 7,3 % 5 0,5 % 1 2,0 % 1 6,0 %
18% 4 0,2 % 2 1,7 % 3 8,1 % 1 5,4 % 1 8,0 %
20% 4 8,2 % 2 6,1 % 2 5,7 % 1 8,9 % 2 0,0 %
22% 5 6,2 % 3 0,4 % 1 3,4 % 2 2,5 % 2 2,0 %
24% 6 4,2 % 3 4,8 % 1,0 % 2 6,1 % 2 4,0 %
26% 4 4,4 % 5 5,6 % 0,0 % 3 0,8 % 2 6,0 %
28% 2 2,2 % 7 7,8 % 0,0 % 3 7,3 % 2 8,0 %
30% 0,0 % 1 0 0,0 % 0,0 % 4 5,0 % 3 0,0 %
0%
5%
10%
15%
20%
25%
30%
35%
0% 10% 20% 30% 40% 50%
总风险( 标准差)
预期回报
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
投资组合优化问题（ 补充 ）
丁以中主编的,管理科学－运用 Spreadsheet建模和求解,P188
投资组合优化，就是确定一组投资项目的最优投资比例。这里所说的,最优,,可以是指在一定风险水平下使得投资回报最大，也可以是指在一定的投资回报水平下使得风险最小。
在 20世纪 50年代,Harry Markowitz研究了一定期望投资回报水平下使得方差最小的最优投资比例问题,Harry Markowitz在该问题上的研究成果以及关于投资的其他研究成果，使他荣获 1990年诺贝尔经济学奖。
先介绍均值、方差、标准差、相关系数、协方差的基本概念，然后用一个例子说明投资组合优化问题的建模与求解方法。
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
投资组合优化问题（ 补充续 ）
单项投资的期望回报率与风险
如果投资对象只有一个，则该投资的回报可以用期望回报率来描述，该投资的风险可以用方差或标准差来描述。下面介绍 期望值,方差 与 标准差 的概念。
用前 n年的回报率（ x1,x2,…,xn ）的期望值来估计本年的 期望回报率?（可用 AVERAGE函数求）
用前 n年的回报率（ x1,x2,…,xn ）的 方差?2（总体方差，可用 VARP函数求）或标准差?（总体标准差，可用 STDEVP函数求） 来估计本年的风险。
即一个投资项目的投资效果可以用投资回报率的期望值和方差（或标准差）描述，前者反映了该项投资的回报水平；后者反映了该项投资的风险状况。
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
投资组合优化问题（ 补充续 ）
一组投资（即多项投资）的期望回报与风险
如果投资对象不止一个，则该组投资的总回报率不仅与各投资项目的单项期望回报率有关，而且与各项目的投资比例有关。设一组投资由
m个投资项目组成，它们的单项期望回报率为（?1,?2,…,?m ）
，对该 m个项目的投资比例为（ S1,S2,…,Sm ），则该组投资的总回报率 R的期望值为单项回报率与相应的投资比例的乘积之和。其估算公式如下：
R的期望值 ＝ S1?1 ＋ S2?2 ＋ … ＋ Sm?m
总回报率 R的 方差 估算公式如下：
R的方差 ＝
其中 rij为投资 i和 j的相关系数（可用 CORREL函数求）
COVij为投资 i和 j的协方差（可用 COVAR函数求）
即一组投资项目的投资效果可以用投资组合的总回报率的期望值和方差（或标准差）描述，前者反映了该组投资的总体回报水平；后者反映了该组投资的总体风险状况。
2 2 2 2 2 2
1 1 2 2
1 1 1 1
m m i j ij i j
ij
m m m m
i j ij i j i j ij
i j i j
S S S S S
S S S S C O V
r
r
说明：题目有的给相关系数
、有的给协方差
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
投资组合优化问题（ 补充续 ）
用 Excel计算期望值、方差、协方差
期望值用 AVERAGE函数、方差用 VARP函数（总体方差
）、标准差用 STDEVP函数（总体标准差）、相关系数用
CORREL函数、协方差用 COVAR函数。
例子：现有三个可投资的项目：股票 1，股票 2和债券。它们自 1985年至 2004年 20年的投资回报率（见 Excel文件）
。分别计算这三个项目的单项投资回报率的期望值、方差
、以及三个项目之间的协方差矩阵。
方法,
1,期望值用 AVERAGE函数求；
2,方差用 VARP函数求（总体方差）；
3,协方差用 COVAR函数求；
4,还可以用,工具 ->数据分析 ->协方差,计算协方差矩阵（包括方差和协方差），只需输入三个项目的历史数据所在地址区域
（包括标题和数据）以及输出区域，就可得到三个项目的协方差矩阵。
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
投资组合优化问题（ 补充续 ）
投资组合优化模型
计算上面例子中对三个投资项目（股票 1，股票 2和债券）的最优投资比例 S1,S2,S3，要求在总投资回报率不低于 13％的前提下，使得投资的总风险最小（见 Excel文件）。
方法,
1,决策变量：各投资项目的投资比例 S1,S2,S3
2,目标函数,构造协方差矩阵，总风险（方差） =
SUMPRODUCT（ MMULT（投资比例,协方差矩阵）,投资比例）
3,约束条件投资组合总回报率的期望值约束投资比例之和应等于 1
非负
结果,股票 1、股票 2、债券的投资比例为 50.63%:32.43%:16.93%。
总风险 (方差?2 )=0.0143，总风险 (标准差?)=12%<预期回报 (?)=13％
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
10.3 Separable Programming
可分离规划 P414
对利润或成本曲线是分段直线并且边际收益递减的非线性规划问题,可分离规划技术 将问题转换成相应的线性规划问题。
总利润（或总成本）仅是从单个活动的分段直线利润（或成本）曲线上直接获得的利润（或成本）相加得到的 总和 。
由于每条利润（或成本）曲线都存在直线段，
所以这个技术将模型描述转换为线性规划模型
。这有助于非常有效地求解模型，并且可以对线性规划运用 What-If分析的强大工具。
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
每周最大产量 产品的单位利润产品 正常工作时间加班时间总计 正常工作时间加班时间门 3 1 4
(D?4)
$300 $200
窗 3 3 6
(2W?12)
$500 $100
（ 3D＋ 2W?18）－－工厂 3的约束需要加班时伟恩德玻璃公司问题 P415
产品（门和窗），在正常时间和加班时间，单位利润不同（递减），表中给出了工厂 1和工厂 2每周在正常工作时间和加班工作时间生产门和窗的最大数量。
每周产品利润与每周产量间的关系图（折线）,P416
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
P416 可分离规划技术
The Separable Programming Technique
对于违背比例性假设的任一活动，将其利润线划分成多段，使得每一段为直线线段
,为利润线上的每一直线段引入新的可分决策变量，以代替原来的单一决策变量 。
因为每一直线段的新决策变量仍然遵循比例性假设，因此可以为这些决策变量建立线性规划 模型
非线性规划－ >线性规划
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
需要加班时的伟恩德可分离规划问题的 代数模型 （补充）
利用可分离规划技术，将每周门和窗生产量（ 2个决策变量）分为正常工作时间和加班工作时间的每周生产量（ 2× 2＝ 4个决策变量）
决策变量：
DR,DO为正常工作时间和加班工作时间每周门的生产量
WR,WO为正常工作时间和加班工作时间每周窗的生产量目标,最大化 净利润 P=300DR ＋ 200DO ＋ 500WR ＋ 100WO
约束条件：
工厂 1,DR ＋ DO? 4
工厂 2,2 (WR ＋ WO )? 12
工厂 3,3 (DR ＋ DO)+2 (WR ＋ WO)? 18
每周最大产量,DR? 3,DO? 1,WR?3,WO?3
且 非负,DR,DO,WR,WO?0
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
需要加班时的伟恩德可分离规划问题的 代数模型 2 （补充）
利用可分离规划技术，将每周门和窗生产量（ 2个决策变量）分为正常工作时间和加班工作时间的每周生产量（ 2× 2＝ 4个决策变量），
这样共 2＋ 4＝ 6个决策变量决策变量：
D为 每周门的生产量,W为每周窗的生产量
DR,DO为正常工作时间和加班工作时间每周门的生产量
WR,WO为正常工作时间和加班工作时间每周窗的生产量目标,最大化 净利润 P=300DR＋ 200DO ＋ 500WR ＋ 100WO
约束条件：
总的生产量：
门,D = DR ＋ DO
窗,W = WR ＋ WO
工厂 1,D? 4
工厂 2,2W? 12
工厂 3,3D+2W? 18
每周最大产量,DR? 3,DO? 1,WR? 3,WO? 3
且 非负,D,W,DR,DO,WR,WO? 0
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
需要加班时的伟恩德可分离规划问题的电子表格模型 P417
由于边际收益递减，为了使总利润最大化，最优解肯定会先自动地用完正常的工作时间，才开始采取加班的措施。
W y n d o r P r o b l e m w i t h O v e r t i m e ( S e p a r a b l e P r o g r a m m i n g )
P 4 1 7 有加班的伟恩德公司问题（可分离规划）
单位利润 门 D o o r s 窗户 W i n d o w s
正常时间 $300 $500
加班时间 $200 $100
使用时数 每周可得时数工厂 1 1 0 4 <= 4
工厂 2 0 2 6 <= 12
工厂 3 3 2 18 <= 18
门 D o o r s 窗户 W i n d o w s 门 D o o r s 窗户 W i n d o w s
正常时间 3 3 <= 3 3
加班时间 1 0 <= 1 3
总生产量 4 3
总利润 $ 2,6 0 0
每个产品所需生产时数每周最大产量 M a x i m u m每周生产量
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
P418 对光华利润曲线应用可分离规划
在可分离规划的一些应用中，利润线是一条曲线而非一系列的直线段。
P419图 10.17中的实线显示了这样的一条利润曲线,为了能够应用可分离规划,这条曲线可以近似为一系列的直线段。
非线性规划－ >线性规划
还是要求边际收益递减
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
存在加班成本和非线性营销成本的伟恩德问题 P419
门的 营销成本 =$25D2,窗的 营销成本 =$66.67W2
单位毛利润：单位利润 (P415表 10.3)+营销成本
(每扇门 75美元，每扇窗 200美元 )。
产品每周最大产量 单位毛利润（美元）
正常工作时间加班时间 总计正常工作时间加班时间营销成本门 3 1 4(D?4) 375(300+75) 275(200+75) 25D2
窗 3 3 6(2W?12) 700(500+200) 300(100+200) 66.67W2
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
存在 加班成本和 非线性营销成本的伟恩德 问题 P419
计算每周生产 D扇门时，伟恩德公司周利润表
(P419),然后再绘制门的利润曲线（ P421）
计算每周生产 W扇窗时，伟恩德公司周利润表
(P420),然后再绘制窗的利润曲线（ P421）
两条利润曲线都是边际收益递减的
当分段直线与实际利润曲线非常近似时，使用 可分离规划是相当好的。
方法 1：用可分离规划（ 我感觉麻烦些 ）
方法 2：用非线性规划（ 感觉简单些，我推荐这种方法 ）
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
存在 加班成本和 非线性营销成本的伟恩德 问题 P419-422
方法 1：用可分离规划（ 了解即可 ）
W y n d o r w i t h O v e r t i m e a n d M a r k e t i n g C o s t s ( S e p a r a b l e )
P 4 2 2 有加班成本和非线性营销成本的伟恩德问题( 可分离规划)
单位利润 门 D o o r s 窗 W i n d o w s
正常时间 ( 0 - 1 ) $ 3 5 0,0 0 $ 6 3 3,3 3
正常时间 ( 1 - 2 ) $ 3 0 0,0 0 $ 5 0 0,0 0
正常时间 ( 2 - 3 ) $ 2 5 0,0 0 $ 3 6 7,6 7
加班时间 $ 1 0 0,0 0 - $ 3 0 0,0 0
使用时数 每周可得时数工厂 1 1 0 4 <= 4
工厂 2 0 2 6 <= 12
工厂 3 3 2 18 <= 18
门 D o o r s 窗 W i n d o w s 门 D o o r s 窗 W i n d o w s
正常时间 ( 0 - 1 ) 1 1 <= 1 1
正常时间 ( 1 - 2 ) 1 1 <= 1 1
正常时间 ( 2 - 3 ) 1 1 <= 1 1
加班时间 1 0 <= 1 3
总生产量 4 3
总利润 $ 2,5 0 1
每周最大产量每个产品所需生产时数每周生产量将两条利润曲线各近似成四段利润直线（ 2个－
>2*4个决策变量
）
单位利润：直线线段的斜率（表中最后一列增加的利润）
结果：每周生产
4扇门（ 1个加班生产）,3扇窗
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
存在 加班成本和 非线性营销成本的伟恩德 问题 P421
方法 2：用非线性规划（ 我推荐此方法 ）
非线性规划（
营销成本）
区分正常工作时间和加班时间
结果：每周生产 4扇门（ 1个加班生产）,3
扇窗
请自己写代数模型
W y n d o r W i t h O v e r t i m e a n d M a r k e t i n g C o s t s ( N o n l i n e a r P r o g r a m m i n g )
P 4 2 3 有加班成本和非线性营销成本的伟恩德问题( 非线性规划)
单位毛利润 门 D o o r s 窗 W i n d o w s
正常时间 $375 $700
加班时间 $275 $300
使用时数 每周可得时数工厂 1 1 0 4 <= 4
工厂 2 0 2 6 <= 12
工厂 3 3 2 18 <= 18
每周生产量 门 D o o r s 窗 W i n d o w s 门 D o o r s 窗 W i n d o w s
正常时间 3 3 <= 3 3
加班时间 1 0 <= 1 3
总生产量 4 3
销售毛利润 $ 3,5 0 0
营销成本 $400 $600 总营销成本 $ 1,0 0 0
总利润 $ 2,5 0 0
每个产品所需生产时数每周最大产量
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
补充：非线性规划问题的思考题
（ 请写数学模型 ）
某公司 有资金 10万元,若投资于项目 i（ i=1,2,3） 的投资额为 xi时
,其 收 益 分 别 为 g1(x1)=4x1,
g2(x2)=9x2,g3(x3)=2x32,问应如何分配投资额才能使总收益最大？ （ 结果,x3＝ 10）
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
10.4 复杂非线性规划问题 P424
前面讨论的两个例子都是简单的二次规划问题,要求 边际收益递减,此时 Solver就可以很容易地找到最优解 。 有时还可以用可分离规划来模拟 （ 或近似 ） 一个非线性规划问题
,以此来 利用线性规划 迅速找到最优解 。
但对 边际收益递增,标准的 Solver通常很难求解
如果存在多个局部最优解,从不同的初始点开始多次运行
Solver找到全局最优解－－－可以用 Solver Table来实现小规模的非线性规划问题 （ P425） 。
存在多个局部最优解的大规模的非线性规划问题或多个变量的非线性规划问题,或使用了 IF,ABS,MAX,ROUND的例子,有时 Solver连局部最优解也找不到 。
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
复杂非线性规划问题（ 补充例子 ）
合理安排值班表
合理安排值班表往往是每一个值班组长苦恼的问题,因为每个职工都有自己的私事,要合理解决两者之间的冲突,又不能经常改动值班表,以防大家记不住 。 要求：
1,职工 A要求比职工 C晚一天值班 （ A＝ C＋ 1）
2,职工 D要求在职工 E的前一天的后三天值班
（ D＝ E－ 1＋ 3）
3,职工 B要求比职工 G的早三天值班 （ B＝ G－ 3
,即 G＝ B＋ 3）
4,B,C两职工必须安排在 F职工值班的前后若干天之间 （ B＝ F－ X,C＝ F＋ X）
5,F职工要求安排在星期四值班 （ F＝ 4）
根据这些要求,找出值班关系表 （ 见右 ）,
求解：
设计目标值：将七天的乘积作为目标值,即
P＝ A*B*… *G（ 用 PRODUCT连乘函数实现
） ＝ 5040＝ 1*2*3*4*5*6*7
决策变量,E,X
约束,E,X为整数,非负具体见 Excel文件职工 值班关系表
A C+1=(4+X)+1=X+5
B F-X=4-X
C F+X=4+X
D E-1+3=E+2 若干天
E E X
F 4
G B+3=(4-X)+3=7-X
结果，一份可以让每个人满意的值班表已经完成，可见
，只要合理巧妙地设置参数
，规划求解就可以帮我们解决许多实际问题。
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
10.5 Evolutionary Solver 软件和遗传算法 P426 （了解即可）
Premium Solver,Frontline System,Excel中标准 Solver的开发商开发的 Premium版本,增加了新的搜索程序称之为
Evolutionary Solver,它的基本原理是根据遗传学,进化论和适者生存原理建立的 （ 遗传算法 ）
例子：选择高于市场收益的有价证券投资组合 。
5个股票：美国在线 (AOL),波音 (BA),福特 (F),宝洁 (PG),麦当劳 (MCD)
股票数据：显示了这些股票 6年 （ 1995－ 2001年 ） 的季度业绩
纽约证券交易所综合指数计算的市场整体的业绩
目标：选择在这个阶段中高于市场收益的季度数量最多的投资组合
直接利用标准 Solver求解,得 14次 （ 在 6年 × 4＝ 24季度 ）
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
应用 Evolutionary Solver来选择高于市场收益的投资组合 P427 （了解即可）
安装 Premium Solver：在光盘 Premium Solver文件夹下
,运行 PremSolv文件安装即可 。 安装完毕后,Premium
Solver 将代替 Excel原来的 Solver（ 规划求解 ）,界面也变成英文的,具体 P428。 有三种算法可供选择 （ 1,标准
GRG非线性－－等同于使用没有选择,假设线性模型,
的选项的标准 Solver,2,标准 Simplex LP－－相当于使用选择了,假设线性模型,的选项的标准 Solver,3,标准 Evolutionary－－新的 ） 。
利用 Premium Solver的,标准 Evolutionary”求解,我运行的结果得 18次 （ 在 6年 × 4＝ 24季度 ） －－都采用默认选项
Evolutionary Solver的优点和缺点：
优点：可以处理复杂的目标函数和有多个局部最优解的问题
缺点：不是万能的,1,时间长 2,最佳解有可能不是最优解 。
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
10.6 Summary 小结 P432
非线性规划：至少有一个目标函数或约束函数是非线性的 （ 通常只有目标函数 ）
建立和求解非线性规划模型通常比建立和求解线性规划模型更困难 （ 因为可能有许多局部最优解 ）
然而,当非线性规划模型是边际收益递减时,比较容易求解
当利润曲线是分段直线 （ 近似 ） 时,可以使用可分离规划将问题转化为线性规划问题 。
对于更复杂的非线性规划模型,如有许多局部最优解
,可以多次运行 Solver,每次输入不同的初始解－－
可以用 Solver Table实现
更复杂的非线性规划模型,可以使用有遗传算法的
Evolutionary Solver
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
P441 案例 10.3 跨国投资债券投资、利息税问题
4年前购买了 30000德国马克 （ DM） 的七年期的 B债券
,债券回报率 （ 本金和利息 ） 较高,如 P441的表 2
现在 （ 第 5年初 ）,如果没有利息税的话,最后一年卖比较合适,但从现在开始,要交利息税 （ 利息中获得的前 6100DM是不用缴税的,超过 6100DM的部分税率为 30%,所以卖出的决策要改变,以合理避税 。
售出债券后,得到的资金还可以购买利息为 4%的存款单 （ 一年期 ）
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
P441 案例 10.3 跨国投资数学模型（ b）
查尔斯的投资策略是第 5,6,7年年末卖掉的 B债券 。 直观上看,此问题的决策变量应该是这三年年末卖掉的 B债券量 。 但由于资本利息税的存在,利息在 6100马克以上和以下待遇是不同的,因此在计算净得利息时,需要用到 IF函数,将得到一个非线性模型 。 但试想,如果视每一年卖掉的债券为两部分,6100以下不缴税部分和 6100以上缴税部分
,则可以避开 IF函数,总利息是 3× 2＝ 6个决策变量的线性函数 。
先由表 2计算第 5,6,7年卖出债券时的回报率,例如第 5年卖出的回报率为 （ 第 5年 100马克的总回报 -100） /100,即 0.5001
约束情况,a) 不缴税部分债券利息不超过 6100
b) 三年卖出的总债券为初始投资 30000德国马克
c) 决策变量非负
由此得如下数学模型：
51 52 61 62 71 72
51 52
61 62
71 72
51
,,,,,
Ma x P 0.5 00 1 0.5 00 1 ( 1 30 % )
0.6 35 1 0.6 3 51 ( 1 30 % )
0.7 82 3 0.7 8 23 ( 1 30 % )
0,50 01 61 0
s.t,
x x x x x x
xx
xx
xx
x
决策变量：
目标函数：
61 71
51 52 61 62 71 72
51 52 61 62 71 72
0,0.6 35 1 61 00,0.7 82 3 61 00
30000
,,,,,0
xx
x x x x x x
x x x x x x
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
P441 案例 10.3 跨国投资数学模型（ d）
在考虑存款单 （ 一年期 ） 的情况下,由于存款单也要考虑资本利息税,故同样把购买的存款单分为卖出时不缴利息税和缴利息税两部分 。 不缴税部分回报率为 4%,缴税部分回报率为 4%*（ 1-30%） =2.8%。
约束情况,1） 不缴税部分总利息不超过 6100
2） 三年卖出的总债券为初始投资 30000马克
3） 第 5,6年年末购买的存款单不超过当年年末可用资金 。 第 5年年末可用资金为卖掉 B债券后的收入,第 6年年末为卖掉 B债券和前一年购买的存款单后的收入 。
4） 决策变量非负
5 1 5 2 6 1 6 2 7 1 7 2 5 1 5 2 6 1 6 2
5 1 5 2
6 1 6 2 5 1 5 2
7 1 7 2 6 1 6 2
,,,,,,,,,
M a x P 0,50 01 0,50 01 ( 1 30 %)
0.6351 0.6351 ( 1 30% ) 0.04 ( 1 30% )
0.7823 0.7823 ( 1 30% ) 0.04 ( 1 30% )
x x x x x x y y y y
xx
x x y y
x x y y
决策变量：
目标函数：
5 1 6 1 5 1
7 1 6 1
5 1 5 2 6 1 6 2 7 1 7 2
5 1 5 2 5 1 5 2
6 1 6 2 6 1 6 2
0,5 00 1 61 00,0,63 51 0,04 61 00
0,78 23 0,04 61 00
30000
s,t,( 1 0,50 01 ) ( 1 0,50 01 70 %)
( 1 0,63 51 ) ( 1 0,63 51 70 %)
( 1 0,04)
x x y
xy
x x x x x x
y y x x
y y x x
y
5 1 5 2
5 1 5 2 6 1 6 2 7 1 7 2 5 1 5 2 6 1 6 2
( 1 0,0 4 70 %)
,,,,,,,,,0
y
x x x x x x y y y y
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
P441 案例 10.3 跨国投资答案
b,总利息收入为 19099德国马克
d,总利息收入为 20070德国马克
f,在 d基础上,总利息收入为 22183德国马克,22183－ 20070＝ 2113
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
补充：非线性规划问题的思考题
（ 请写数学模型并实现 ）
1,一个饮食店卖包子和馒头两种早点,每卖出 10茏包子或馒头饮食店分别可以获利 6元或 4元；每做 10茏包子或 10茏馒头分别需要花费 2小时或 1小时人工,而饮食店工人每天可以用来加工包子或馒头的总时间不能超过 9小时；摆放 10茏包子或 10茏馒头分别需要 2层或 3层货架,而饮食店的货架总数为 16层；此外,由于销售能力的限制饮食店每天销售的包子与馒头的总数不能超过 60茏 。 试问在上述条件的限制下,饮食店应该如何安排每天生产的包子与馒头的数量才能获得最大的利润 。 （ 注意：以 10茏为单位
） 结果,（ 3,3）,P=30元
2,非线性规划：假定饮食店使用的人工费用是每小时 5元,加工 10茏包子或 10茏馒头的原料费用分别为 28
元或 22元,而销售 10茏包子或 10茏馒头的单价 （ 不是常数而是依赖于包子或馒头的销售数量 q1,q2）
分别为 p1=47-q1,p2=34-q2。 试确定此时利润达到最大的生产销售安排,即包子与馒头各应生产与销售多少数量 。 结果,（ 3.1,2.8）,P=30.05元
3,在 2问题中取消包子与馒头售价与销售数量有关的假设,但假设在该饮食店所在地区很多居民清晨上班时很喜欢吃包子,因此饮食店每天总可以将前 10茏包子以较高的价格卖出 。 具体地说,前 10茏包子的售价可以达到每 10茏 46元 （ 高价包子 ）,而这 10茏包子卖出之后其余包子的售价则为每 10茏 44元 （ 平价包子 ） 。 馒头的售价却是固定的：每 10茏 31元 。 试确定在此情况下每天包子与馒头的最优销售数量和饮食店所能达到的最大利润 。 结果,（ 3,3）,P=32元
4,在 2问题中,其包子原料 （ 例如猪肉 ） 供应商提出一个优惠条件：只要饮食店购买超过 50茏包子所需的原料就将每做 10茏包子所需原料的价格由 28元减至 24元 。 还有,总人工时间和货架总数为原来的 2倍,
每天销售的包子与馒头的总数不能超过 120茏,为试确定在饮食店接受这一优惠条件下的最优销售安排
。 结果,(1)初值为 （ 4,6） 结果为 （ 4.5,3.5）,P=32.5元
(2)初值为 （ 2,1） 结果为 （ 6.5,3.5）,P=54.5元
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
Exercise
作业（上机）
P433 习题：
10.4,10.6(股票 2的标准差改为 30000),
10.9 （可分离规划）
10.11 （可分离规划） 注意：从本章开始的后面 3章的作业，请交电子报告：
1、数学模型（公式编辑器）
2、电子表格模型
3、结果
Chapter 10
Nonlinear Programming
非线性规划
RUC Information School,Ye Xiang,2007
案例分析作业
P440案例 10.2 了解投资组合注意,给的是方差,协方差 （ 可以直接构造协方差矩阵 ）
