设有某物资要从调往,平衡表及运价表如下.问应怎样调运,才能使总运费最少?
平衡表(单位:吨) 运价表(单位:元/吨)
销地产地
产 量
4
3
7
3
11
3
12
-⑤
3
1
4
1
9
2
8
- ②
6
3
9
7
4
10
5
- ⑥
销 量
3
6
5
6
20
①
④
③
(答案; 初始基本可行解为
相应运价为
总运费 (元) )
32.对上题,用最小元素法已编制出初始调运方案,
① 再用左上角法编制一个初始调运方案.
② 用闭回路法或位势法,对其中任一方案,判别是否为最优?并对方案进行调整.
（答案,对空格是非基变量的分别作闭回路,求出其检验数,若检验数中有正数,则对方案进行调整,方法见教材P.127,129,得3个调整量,最终调整方案为:有数字格的基变量是分别乘相应运价得 (元)为最优调运方案.）
33.(运输问题的图上作业法) 某物资25吨,由发点发货,,发货量分别是7,
2,4,10,2吨,运往收点收货,收货量分别是6,6,10,3吨,交通图如下:
② ⑩
④
⑦ ②
问应如何调运才能使吨公里最小?
(答案:采用丢边破圈法,见教材P.136,最后得最优调运方案,总运输量为
(吨公里) )
下篇 非线性规划 (Nonlinear Programming)
第一章 基本概念
1.用图解法求下面两个变量的非线性规划的最优解:
s.t, (答案:等高线与可行域的切点 为此问题的最优解)
复习思考题:
2.试述非线性规划数学模型的一般形式及其与线性规划模型的主要区别.
3.分别说明在什么条件下,称为在上的局部最小点,严格局部最小点,全局极小点,严格全局极小点.
4.分别写出下述概念的数学表达式:
(a) 函数在处的梯度;
(b) 在处的矩阵;
(c) 二次型;
(d) 正定、半正定、负定、半负定二次型的充要条件.
5.
试计算以下各函数的梯度和矩阵:
(1) (答案:▽,
▽= )
(2)
解
(3)
解
6.求下列各函数的驻点,并判定它们是极小点或是鞍点:
(1)
(答案,驻点为严格极小点.)
(2)
(答案;驻点是鞍点.)
(3)
(答案;驻点为极大点.)
第二章 最优化方法
复习思考题:
7.试述凸函数,严格凸函数,凹函数,严格凹函数的定义.
8.判别一个函数是否为凸函数的一阶、二阶条件.(教材P.172定理1.4,1.5)
9.试判定以下函数的凹凸性:
(1) (答案:由的矩阵为正定,知为严格凸函数.)
(2) (答案:由的矩阵为不定,故为非凸也非凹函数.)
10.判定下述非线性规划是否为凸规划?
(1)
s.t,
(2)
s.t,
(答案,(1) 为正定,故为凸函数,的
海赛矩阵 为负定,为凹函数,故此线性规划为凸规划,)
(2) 为正定,为凸函数,负定,为凹函数,故原非线性规划为凸规划,)
复习思考题:
11.分述一维搜索中斐波那契(法及黄金分割法的主要思想,主要步骤及适用范围.
下面简介Fibonacci数.
十三世纪初,意大利比萨的一位叫伦纳地,绰号叫斐波那契(Fibonacci,1170-1250是filius Bonacci意思是“波那契之子”)的数学家在一本题为《算盘书》的数学著作中,提出下面一个有趣订的问题:
兔子出生以后两个月就能生小兔,若每次不多不少恰好生一对(一雌一雄),假如养了初生的小兔一对,试问一年后可有多少对兔子(如果生下的小兔子都不死的话)?
推算如下:
第一个月:只有一对小兔;
第二个月:小兔子没有长成不会生殖,仍然是一对兔子;
第三个月:这对兔子生了一对小兔子,这是共有二对兔子;
第四个月:老兔子又生了一对小兔,而上月生的小兔还未成熟,这时共对兔子;
第五个月:这时已有两对兔子可以生殖(原老兔和第三月初生的小兔),于是生了两对,共5对兔子:
……………………………………………………………………………
如此推算下去,得结果,1,1,2,3,5,8,13,21,34,55,…,233
一年后(第13个月)共有兔子233对.
我们把数列,1,1,2,3,5,8,13,21,34,…叫Fibonacci数列.
1634年(斐氏死后400年)数学家奇拉特发现,Fibonacci数列的通项公式:
设
通项公式(内比公式)为:
(这公式是18世纪初,棣美佛在其所著《分析集锦》(Miscellanea Analytica)中给出的)
由此数列引出许多重要的发现:
1753年,希姆松发现斐氏数列中前后两项之比是连分数的第n个渐近分数.
1884年,拉姆斯证明了(利用了斐氏数列):应用辗转相除(欧几里德除法)法的步数(辗转除的次数)不大于较小的那个数的位数的5倍.
1876年,鲁卡斯发现:
方程 的两个根 的任何次幂的线性组合都满足关系式 .
卡鲁斯还利用斐氏数列的性质证明了 是一个质数(有39位,验证非轻而易举),“斐波那契数列”名称正是出自卡鲁斯之口.
本世纪50年代数学家华罗庚教授在推广运筹学的优选法工作中也找到了斐氏数列的巧妙应用,这就是黄金分割数:.
由于这个数列越来越多的性质被人们所发现(例如:植物的叶序,菠萝的鳞片,树枝的生长,蜂进蜂房,上楼方式,雄蜂家族,钢琴键盘以及几何、代数、概率、…的问题都与斐氏数列有关.)和应用,因而引起了数学家的关注,一本专门研究它的杂志-《斐波那契季刊》(Fibonacci Quarterly于1963年开始发行.
12.用Fibonacci法求函数
在区间上的极大点,要求缩短后的区间长度不大于原区间长度的.
(答案:为近似最优点,)
13.用 Fibonacci数求
〡,设最终区间长度不超过0.08,(答案:为近似极小点,,缩短后的区间长度为0.545-0.231=0.314, )
14.用黄金分割法求解下述函数的极小值
,
要求
(答案:经过7次迭代,因为,精度满足要求,迭代终止,包含最优解的区间是 )
第三章 无约束极值问题
15.用最速下降法(梯度法)求下述函数的极大点,给定初始点,要求迭代4步,
要求梯度精度
(答案:函数的极大点为 且 )
16.试用Newton法求解
取初始点,并将采用最佳步长和固定步长时的情形做比较.
(答案:取步长时,不收敛,取最佳步长时收敛,极小点为
17.试用牛顿法求解第15题.
由戴维顿于1959年提出,佛莱彻-鲍威尔于1963年改进的变尺度法,有更快的收敛速度,且避免了二阶导数矩阵及其求逆过程,特别适于求解高维最优化问题.
18.用法(变尺度法)求解
(答案,X为极小点,)
第四章 约束极值问题
复习思考题:
19.什么是库恩-塔克条件和库恩-塔克点,为什么满足库恩-塔克条件是点成为最优点的必要条件?
答:假定是非线性规划
s.t, (4.1)
的极小点,该点可能位于可行域的内部,这是无约束问题,必满足.若位于可行域的边界上,不失一般性,设位于第一个约束形成的可行域边界上,即第易个约束是点的起作用的约束()是极小点,则必与在一条直线上且方向相反,这说明在上述条件下存在实数使
若有m个起作用约束,线性无关,即存在,使
为了把不起作用的约束也包括在上式中,增加条件
我们用 代替约束条件
这样可得如下条件
这样,设是(4.1)式极小点,而且点的所有起作用约束的梯度和
线性无关,则存在及,使下述条件成立
(4.3)
条件(4.3)叫库恩-塔克条件(最优性条件),满足条件的点叫库恩-塔克点,
条件中的称为广义Lagrange乘子.
根据定理4.2,满足库恩-塔克条件是点成为最优点的必要条件,这比无条件极值问题中使目标函数的偏导数为零的点不一定是目标函数的极值点一样,单如假定了凸性,则可保证最优点了(定理4.3).
20.用库恩-塔克条件解非线性规划
(答案:由于该非线性规划为凸规划,故为点,是全局极小点,是可行域的内点,其目标函数值.此题比书例4.2少约束条件解点及判断最优化较简单.)
复习思考题:
21.叙述用线性规划逼近非线性规划的基本思想,及为了克服可行域无阶或近似解不可行时,应加进对变量变化范围的限制,即法.(此法适于求解变量及约束条件比较多的问题,单只有少量的约束是非线性的规划问题.)
22.将教材例4.4用法重做一遍.求解下述非线性规划问题
s.t,g(x)=1-x 设初始点
解 先将约束函数在点线性化.
=0+
得线性规划问题
s.t,
此可行域无阶.给定上问题的一个可行点步长界限 精度要求
经单纯行法第一次迭代,得下线性规划问题为
s.t, (附加条件)
解得 ,
是原问题的可行解,则令
用单纯行法经第二次迭代,得线性规划问题为
s.t,
得
对原问题不可行,缩小步长1/100,及令
用单纯行法解下列线性规划问题:
s.t,
得,是原问题的近似可行解,故令
经检验
故此问题的近似最优解是
23.用法解求解教材例4.5
s.t,
解 设初始点 ,则 f(,取
在处将上非线性规划问题线性化
令
=
=
=
=
=
=
(
故 )
这样得
s.t,
用单纯形法,得上问题最优解
对应原问题最优解为
由于 不满足非线性约束,须将缩小,例如令
上述约束条件改为
解得新问题最优解
故 ,它是原问题的一个可行解,故令
,这是第一次迭代,
第二次迭代是原问题在处线性化并保持不变,同学们接下去做完…….
24.用简约梯度法解教材例4.9
s.t,
解 见教材P.289-293.
对策论 (Theory of gamrs)
复习思考题:
1.试述组成对策模型的三个基本要素的涵义.
2.试述二人零和有限对策在研究对策模型中的地位、意义,为什么它又被称为矩阵对策?
3.两人各有1角、5分和1分的硬币各一枚,在双方互不知道情况下各出一枚,并规定和数为奇数时,赢得所出硬币;当和为偶数时,赢得所出硬币,试据此列出二人零和对策的模型,并说明该项游戏对双方是否公平合理?
(答案;解得A的最优策略为 ,B的最优策略为
对策值 V=0 即该项游戏公平合理.)
4.两人在互不知道的情况下,各在纸上写三个数字中的任意一个,设A所写数字为s,B所写数字为t,答案公布后,B付给A 元.试列出此问题对A的支付矩阵,并说明该游戏对双方是否公平合理?
5.任放一张红牌或黑牌,让A看但不让A知道.如为红牌,A可掷一枚硬币让B猜,掷硬币出现正反面的概率各为1/2,如出现正面,A赢得p元,出现反面,A赢得q元;若让B猜,B猜红,A输r元,猜黑A赢s元.如为黑牌,A只能让B猜,如猜红,A赢t元,如猜黑,A输u元.试列出A的赢得矩阵.
答案; 猜 红 猜 黑
掷硬币让B猜.,
6.(复习思考题)解释下列概念,并说明同组概念之间的联系和区别.
(1) 策略、纯策略.
(2) 鞍点、平衡局势、纯局势、纯策略意义下的解.
7.已知、两人对策时,的赢得矩阵如下,求双方各自的最优策略及对策值.
① (答案:, )
② (答案:,)
③ (答案:)
8.若和是矩阵的两个鞍点,求证有,
9.下列矩阵中确定p,q,使得该矩阵在交叉处存在鞍点.
答案,
10.(复习思考题) 解释下列概念:混合扩充、混合局势、混合策略意义下的解,优超,某纯策略被另一纯策略优超.
11.利用优超原则解下列混合策略的对策
矩阵 为A,B对策时,A的赢得矩阵.(尽可能按优超原则简化)
(答案:原矩阵对策的一个解是 , )
12.试用图解法求解下述对策问题
A B
b 1 b 2 b 3
a 1
a 2
1 -1 3
3 5 -3
(答案:由图解得
13.已知A,BD的各自纯策略及赢得(支付)矩阵如下表
A B
b 1 b 2 b 3
a 1
a 2
a 3
8 4 12
12 6 2
4 16 8
试求局中人B的最优混合策略及对策值.
(答案:设B以的概率混合使用策略.根据用线性规划方法求解对策问题的过程计算得 )
决策分析 (Decicion Analysis)
14.(复习思考题)简述决策的分类,决策的过程和程序.
15.某地方新华书店希望定购最新出版的好书,根据以往经验,新书的销售量可能为50,100,150或200本.假设每本新书的定购价为4元,销售价为6元,剩书的定购价为每本2元.要求:建立损益矩阵(收益矩阵).
16.某钟表公司计划通过它的销售网推销一种低价钟表,计划零售价每块10元.对这种钟表有三种设计方案:方案Ⅰ需一次投资10万元,投资后每块成本5元;方案Ⅱ需一次投资16万元,投资后每块成本4元;方案Ⅲ需一次投资25万元,投资后每块成本3元,该种钟表需求量不确且,但估计有三种可能:
① 试建立这个问题的收益矩阵.
② 分别用悲观法,乐观法及等可能法决定公司应采用哪一个设计方案.
(答案:策略Ⅰ为悲观方案,方案Ⅲ为乐观方案
故第Ⅲ方案为等可能法.)
17.设A工厂以批发方式销售它所生产的产品,每件产品的成本为0.03元,批发价为每件0.05元,若每天生产的产品当天销售不完,每天要损失0.01元.A工厂每天的产量可以是0,1000,2000,3000,4000件.则A厂的决策者应如何考虑每天生产的生产量,使它的收入最高?
提示:①设销售量从0-4000的概率分别为0.1,0.2,0.4,0.2,0.1,工厂决策者采用最大收益期望值进行决策(MEV),计算结果列表…… ②利用最小机会损失准则(Savage准则):
最大收益值-每个策略对应j发生的收益值=机会损失值.即
得机会损失矩阵……根据这个矩阵,用最小机会损失期望值决策准则(EOL准则)计算出结果…..
18.在使用修正概率法时应复习概率论中的全概率公式和逆概率公式即贝叶斯(Bayes)公式.
19.在一台机器上加工制造一批零件10000个,如加工完后逐个进行修整,则全部可以合格,但需修整费300元,如不进行修整据以往资料,次品率见下表次品率(E)
0.02
0.04
0.06
0.08
0.10
概率P(E)
0.20
0.40
0.25
0.10
0.05
一旦装配中发现次品时,需返工修理费每个零件0.50元,要求:
(1) 分别用期望值法(等可能准则)和后悔值法(最小机会损失准则)决定这批零件要不要整修;
(2) 为了获得这批零件中次品率的正确资料,在刚加工完的10000件中,随机抽取130个样品,发现其中有9件次品,试修整先验概率,并重新按期望值法和后悔值法决定这批零件要不要整修?
(答案,(1) 零件不需要修正.(2) 均应采用修正零件的方案.)
20.计算下列人员的效用值:
(1) 某甲失去500元时的效用值为1,得到1000元时效用值为10元;又肯定能得到5元与发生下列情况对他无差别:以概率0.3失去500元和以概率0.7得到1000元,问某甲得到5元时的效用值有多大? (答案:U(5)=7.3)
(2) 某乙 -10元的效用值为0.1;200元的效用值为0.5,他自己解释肯定得到200元和以下情况无差别;以0.7的概率失去10元和以0.3的概率得到2000问对某乙2000元的效用值为多大? (答案:U(2000)=1.433)
(3) 某丙1000元的效用值0;500元的效用值为-150,并且对以下事件上效用值无差别:肯定得到500元或益0.8的机会得到1000元和以0.2的机会失去1000元,则某丙失去1000元的效用值为多大? (答案,U(-1000)=-750)
21.某丁2000元的效用值为0;500元的效用值6;-100元的效用值为0,试找出概率p使以下情况对他来讲无差别:肯定得到500元或以概率p得到2000元和以概率(1-p)失去100元.
(答案,p=0.6)
22.某公司经理的决策效用函数U(M)如下表所示,他需要决定是否为公司的财产保火险.据大量社会资料,一年内该公司发生火灾的概率为0.0015,问他是否愿意每年付100元保10000元财产的潜在火灾损失?
U(M)
M
-800
-2
-1
0
250
-1000
-200
-100
0
10000
(答案:画出这个问题的决策树……
投保火险的期望值为,0.0015
不投火险的期望值为:0.0015
结论:按效用值决策时应投保火险.
选编于2004年春节前夕.
平衡表(单位:吨) 运价表(单位:元/吨)
销地产地
产 量
4
3
7
3
11
3
12
-⑤
3
1
4
1
9
2
8
- ②
6
3
9
7
4
10
5
- ⑥
销 量
3
6
5
6
20
①
④
③
(答案; 初始基本可行解为
相应运价为
总运费 (元) )
32.对上题,用最小元素法已编制出初始调运方案,
① 再用左上角法编制一个初始调运方案.
② 用闭回路法或位势法,对其中任一方案,判别是否为最优?并对方案进行调整.
（答案,对空格是非基变量的分别作闭回路,求出其检验数,若检验数中有正数,则对方案进行调整,方法见教材P.127,129,得3个调整量,最终调整方案为:有数字格的基变量是分别乘相应运价得 (元)为最优调运方案.）
33.(运输问题的图上作业法) 某物资25吨,由发点发货,,发货量分别是7,
2,4,10,2吨,运往收点收货,收货量分别是6,6,10,3吨,交通图如下:
② ⑩
④
⑦ ②
问应如何调运才能使吨公里最小?
(答案:采用丢边破圈法,见教材P.136,最后得最优调运方案,总运输量为
(吨公里) )
下篇 非线性规划 (Nonlinear Programming)
第一章 基本概念
1.用图解法求下面两个变量的非线性规划的最优解:
s.t, (答案:等高线与可行域的切点 为此问题的最优解)
复习思考题:
2.试述非线性规划数学模型的一般形式及其与线性规划模型的主要区别.
3.分别说明在什么条件下,称为在上的局部最小点,严格局部最小点,全局极小点,严格全局极小点.
4.分别写出下述概念的数学表达式:
(a) 函数在处的梯度;
(b) 在处的矩阵;
(c) 二次型;
(d) 正定、半正定、负定、半负定二次型的充要条件.
5.
试计算以下各函数的梯度和矩阵:
(1) (答案:▽,
▽= )
(2)
解
(3)
解
6.求下列各函数的驻点,并判定它们是极小点或是鞍点:
(1)
(答案,驻点为严格极小点.)
(2)
(答案;驻点是鞍点.)
(3)
(答案;驻点为极大点.)
第二章 最优化方法
复习思考题:
7.试述凸函数,严格凸函数,凹函数,严格凹函数的定义.
8.判别一个函数是否为凸函数的一阶、二阶条件.(教材P.172定理1.4,1.5)
9.试判定以下函数的凹凸性:
(1) (答案:由的矩阵为正定,知为严格凸函数.)
(2) (答案:由的矩阵为不定,故为非凸也非凹函数.)
10.判定下述非线性规划是否为凸规划?
(1)
s.t,
(2)
s.t,
(答案,(1) 为正定,故为凸函数,的
海赛矩阵 为负定,为凹函数,故此线性规划为凸规划,)
(2) 为正定,为凸函数,负定,为凹函数,故原非线性规划为凸规划,)
复习思考题:
11.分述一维搜索中斐波那契(法及黄金分割法的主要思想,主要步骤及适用范围.
下面简介Fibonacci数.
十三世纪初,意大利比萨的一位叫伦纳地,绰号叫斐波那契(Fibonacci,1170-1250是filius Bonacci意思是“波那契之子”)的数学家在一本题为《算盘书》的数学著作中,提出下面一个有趣订的问题:
兔子出生以后两个月就能生小兔,若每次不多不少恰好生一对(一雌一雄),假如养了初生的小兔一对,试问一年后可有多少对兔子(如果生下的小兔子都不死的话)?
推算如下:
第一个月:只有一对小兔;
第二个月:小兔子没有长成不会生殖,仍然是一对兔子;
第三个月:这对兔子生了一对小兔子,这是共有二对兔子;
第四个月:老兔子又生了一对小兔,而上月生的小兔还未成熟,这时共对兔子;
第五个月:这时已有两对兔子可以生殖(原老兔和第三月初生的小兔),于是生了两对,共5对兔子:
……………………………………………………………………………
如此推算下去,得结果,1,1,2,3,5,8,13,21,34,55,…,233
一年后(第13个月)共有兔子233对.
我们把数列,1,1,2,3,5,8,13,21,34,…叫Fibonacci数列.
1634年(斐氏死后400年)数学家奇拉特发现,Fibonacci数列的通项公式:
设
通项公式(内比公式)为:
(这公式是18世纪初,棣美佛在其所著《分析集锦》(Miscellanea Analytica)中给出的)
由此数列引出许多重要的发现:
1753年,希姆松发现斐氏数列中前后两项之比是连分数的第n个渐近分数.
1884年,拉姆斯证明了(利用了斐氏数列):应用辗转相除(欧几里德除法)法的步数(辗转除的次数)不大于较小的那个数的位数的5倍.
1876年,鲁卡斯发现:
方程 的两个根 的任何次幂的线性组合都满足关系式 .
卡鲁斯还利用斐氏数列的性质证明了 是一个质数(有39位,验证非轻而易举),“斐波那契数列”名称正是出自卡鲁斯之口.
本世纪50年代数学家华罗庚教授在推广运筹学的优选法工作中也找到了斐氏数列的巧妙应用,这就是黄金分割数:.
由于这个数列越来越多的性质被人们所发现(例如:植物的叶序,菠萝的鳞片,树枝的生长,蜂进蜂房,上楼方式,雄蜂家族,钢琴键盘以及几何、代数、概率、…的问题都与斐氏数列有关.)和应用,因而引起了数学家的关注,一本专门研究它的杂志-《斐波那契季刊》(Fibonacci Quarterly于1963年开始发行.
12.用Fibonacci法求函数
在区间上的极大点,要求缩短后的区间长度不大于原区间长度的.
(答案:为近似最优点,)
13.用 Fibonacci数求
〡,设最终区间长度不超过0.08,(答案:为近似极小点,,缩短后的区间长度为0.545-0.231=0.314, )
14.用黄金分割法求解下述函数的极小值
,
要求
(答案:经过7次迭代,因为,精度满足要求,迭代终止,包含最优解的区间是 )
第三章 无约束极值问题
15.用最速下降法(梯度法)求下述函数的极大点,给定初始点,要求迭代4步,
要求梯度精度
(答案:函数的极大点为 且 )
16.试用Newton法求解
取初始点,并将采用最佳步长和固定步长时的情形做比较.
(答案:取步长时,不收敛,取最佳步长时收敛,极小点为
17.试用牛顿法求解第15题.
由戴维顿于1959年提出,佛莱彻-鲍威尔于1963年改进的变尺度法,有更快的收敛速度,且避免了二阶导数矩阵及其求逆过程,特别适于求解高维最优化问题.
18.用法(变尺度法)求解
(答案,X为极小点,)
第四章 约束极值问题
复习思考题:
19.什么是库恩-塔克条件和库恩-塔克点,为什么满足库恩-塔克条件是点成为最优点的必要条件?
答:假定是非线性规划
s.t, (4.1)
的极小点,该点可能位于可行域的内部,这是无约束问题,必满足.若位于可行域的边界上,不失一般性,设位于第一个约束形成的可行域边界上,即第易个约束是点的起作用的约束()是极小点,则必与在一条直线上且方向相反,这说明在上述条件下存在实数使
若有m个起作用约束,线性无关,即存在,使
为了把不起作用的约束也包括在上式中,增加条件
我们用 代替约束条件
这样可得如下条件
这样,设是(4.1)式极小点,而且点的所有起作用约束的梯度和
线性无关,则存在及,使下述条件成立
(4.3)
条件(4.3)叫库恩-塔克条件(最优性条件),满足条件的点叫库恩-塔克点,
条件中的称为广义Lagrange乘子.
根据定理4.2,满足库恩-塔克条件是点成为最优点的必要条件,这比无条件极值问题中使目标函数的偏导数为零的点不一定是目标函数的极值点一样,单如假定了凸性,则可保证最优点了(定理4.3).
20.用库恩-塔克条件解非线性规划
(答案:由于该非线性规划为凸规划,故为点,是全局极小点,是可行域的内点,其目标函数值.此题比书例4.2少约束条件解点及判断最优化较简单.)
复习思考题:
21.叙述用线性规划逼近非线性规划的基本思想,及为了克服可行域无阶或近似解不可行时,应加进对变量变化范围的限制,即法.(此法适于求解变量及约束条件比较多的问题,单只有少量的约束是非线性的规划问题.)
22.将教材例4.4用法重做一遍.求解下述非线性规划问题
s.t,g(x)=1-x 设初始点
解 先将约束函数在点线性化.
=0+
得线性规划问题
s.t,
此可行域无阶.给定上问题的一个可行点步长界限 精度要求
经单纯行法第一次迭代,得下线性规划问题为
s.t, (附加条件)
解得 ,
是原问题的可行解,则令
用单纯行法经第二次迭代,得线性规划问题为
s.t,
得
对原问题不可行,缩小步长1/100,及令
用单纯行法解下列线性规划问题:
s.t,
得,是原问题的近似可行解,故令
经检验
故此问题的近似最优解是
23.用法解求解教材例4.5
s.t,
解 设初始点 ,则 f(,取
在处将上非线性规划问题线性化
令
=
=
=
=
=
=
(
故 )
这样得
s.t,
用单纯形法,得上问题最优解
对应原问题最优解为
由于 不满足非线性约束,须将缩小,例如令
上述约束条件改为
解得新问题最优解
故 ,它是原问题的一个可行解,故令
,这是第一次迭代,
第二次迭代是原问题在处线性化并保持不变,同学们接下去做完…….
24.用简约梯度法解教材例4.9
s.t,
解 见教材P.289-293.
对策论 (Theory of gamrs)
复习思考题:
1.试述组成对策模型的三个基本要素的涵义.
2.试述二人零和有限对策在研究对策模型中的地位、意义,为什么它又被称为矩阵对策?
3.两人各有1角、5分和1分的硬币各一枚,在双方互不知道情况下各出一枚,并规定和数为奇数时,赢得所出硬币;当和为偶数时,赢得所出硬币,试据此列出二人零和对策的模型,并说明该项游戏对双方是否公平合理?
(答案;解得A的最优策略为 ,B的最优策略为
对策值 V=0 即该项游戏公平合理.)
4.两人在互不知道的情况下,各在纸上写三个数字中的任意一个,设A所写数字为s,B所写数字为t,答案公布后,B付给A 元.试列出此问题对A的支付矩阵,并说明该游戏对双方是否公平合理?
5.任放一张红牌或黑牌,让A看但不让A知道.如为红牌,A可掷一枚硬币让B猜,掷硬币出现正反面的概率各为1/2,如出现正面,A赢得p元,出现反面,A赢得q元;若让B猜,B猜红,A输r元,猜黑A赢s元.如为黑牌,A只能让B猜,如猜红,A赢t元,如猜黑,A输u元.试列出A的赢得矩阵.
答案; 猜 红 猜 黑
掷硬币让B猜.,
6.(复习思考题)解释下列概念,并说明同组概念之间的联系和区别.
(1) 策略、纯策略.
(2) 鞍点、平衡局势、纯局势、纯策略意义下的解.
7.已知、两人对策时,的赢得矩阵如下,求双方各自的最优策略及对策值.
① (答案:, )
② (答案:,)
③ (答案:)
8.若和是矩阵的两个鞍点,求证有,
9.下列矩阵中确定p,q,使得该矩阵在交叉处存在鞍点.
答案,
10.(复习思考题) 解释下列概念:混合扩充、混合局势、混合策略意义下的解,优超,某纯策略被另一纯策略优超.
11.利用优超原则解下列混合策略的对策
矩阵 为A,B对策时,A的赢得矩阵.(尽可能按优超原则简化)
(答案:原矩阵对策的一个解是 , )
12.试用图解法求解下述对策问题
A B
b 1 b 2 b 3
a 1
a 2
1 -1 3
3 5 -3
(答案:由图解得
13.已知A,BD的各自纯策略及赢得(支付)矩阵如下表
A B
b 1 b 2 b 3
a 1
a 2
a 3
8 4 12
12 6 2
4 16 8
试求局中人B的最优混合策略及对策值.
(答案:设B以的概率混合使用策略.根据用线性规划方法求解对策问题的过程计算得 )
决策分析 (Decicion Analysis)
14.(复习思考题)简述决策的分类,决策的过程和程序.
15.某地方新华书店希望定购最新出版的好书,根据以往经验,新书的销售量可能为50,100,150或200本.假设每本新书的定购价为4元,销售价为6元,剩书的定购价为每本2元.要求:建立损益矩阵(收益矩阵).
16.某钟表公司计划通过它的销售网推销一种低价钟表,计划零售价每块10元.对这种钟表有三种设计方案:方案Ⅰ需一次投资10万元,投资后每块成本5元;方案Ⅱ需一次投资16万元,投资后每块成本4元;方案Ⅲ需一次投资25万元,投资后每块成本3元,该种钟表需求量不确且,但估计有三种可能:
① 试建立这个问题的收益矩阵.
② 分别用悲观法,乐观法及等可能法决定公司应采用哪一个设计方案.
(答案:策略Ⅰ为悲观方案,方案Ⅲ为乐观方案
故第Ⅲ方案为等可能法.)
17.设A工厂以批发方式销售它所生产的产品,每件产品的成本为0.03元,批发价为每件0.05元,若每天生产的产品当天销售不完,每天要损失0.01元.A工厂每天的产量可以是0,1000,2000,3000,4000件.则A厂的决策者应如何考虑每天生产的生产量,使它的收入最高?
提示:①设销售量从0-4000的概率分别为0.1,0.2,0.4,0.2,0.1,工厂决策者采用最大收益期望值进行决策(MEV),计算结果列表…… ②利用最小机会损失准则(Savage准则):
最大收益值-每个策略对应j发生的收益值=机会损失值.即
得机会损失矩阵……根据这个矩阵,用最小机会损失期望值决策准则(EOL准则)计算出结果…..
18.在使用修正概率法时应复习概率论中的全概率公式和逆概率公式即贝叶斯(Bayes)公式.
19.在一台机器上加工制造一批零件10000个,如加工完后逐个进行修整,则全部可以合格,但需修整费300元,如不进行修整据以往资料,次品率见下表次品率(E)
0.02
0.04
0.06
0.08
0.10
概率P(E)
0.20
0.40
0.25
0.10
0.05
一旦装配中发现次品时,需返工修理费每个零件0.50元,要求:
(1) 分别用期望值法(等可能准则)和后悔值法(最小机会损失准则)决定这批零件要不要整修;
(2) 为了获得这批零件中次品率的正确资料,在刚加工完的10000件中,随机抽取130个样品,发现其中有9件次品,试修整先验概率,并重新按期望值法和后悔值法决定这批零件要不要整修?
(答案,(1) 零件不需要修正.(2) 均应采用修正零件的方案.)
20.计算下列人员的效用值:
(1) 某甲失去500元时的效用值为1,得到1000元时效用值为10元;又肯定能得到5元与发生下列情况对他无差别:以概率0.3失去500元和以概率0.7得到1000元,问某甲得到5元时的效用值有多大? (答案:U(5)=7.3)
(2) 某乙 -10元的效用值为0.1;200元的效用值为0.5,他自己解释肯定得到200元和以下情况无差别;以0.7的概率失去10元和以0.3的概率得到2000问对某乙2000元的效用值为多大? (答案:U(2000)=1.433)
(3) 某丙1000元的效用值0;500元的效用值为-150,并且对以下事件上效用值无差别:肯定得到500元或益0.8的机会得到1000元和以0.2的机会失去1000元,则某丙失去1000元的效用值为多大? (答案,U(-1000)=-750)
21.某丁2000元的效用值为0;500元的效用值6;-100元的效用值为0,试找出概率p使以下情况对他来讲无差别:肯定得到500元或以概率p得到2000元和以概率(1-p)失去100元.
(答案,p=0.6)
22.某公司经理的决策效用函数U(M)如下表所示,他需要决定是否为公司的财产保火险.据大量社会资料,一年内该公司发生火灾的概率为0.0015,问他是否愿意每年付100元保10000元财产的潜在火灾损失?
U(M)
M
-800
-2
-1
0
250
-1000
-200
-100
0
10000
(答案:画出这个问题的决策树……
投保火险的期望值为,0.0015
不投火险的期望值为:0.0015
结论:按效用值决策时应投保火险.
选编于2004年春节前夕.
