运筹学

陈建华

目录

  • 1 第一章    绪论
    • 1.1 第一节 运筹学的定义与发展简史
    • 1.2 第二节 运筹学的基本特点和工作步骤
    • 1.3 第三节 运筹学的主要分支
    • 1.4 第四节 运筹学的应用
  • 2 第二章  线性规划
    • 2.1 第一节 线性规划概述
    • 2.2 第二节 线性规划问题及其数学模型
    • 2.3 第三节 线性规划图解法及其几何意义
    • 2.4 第四节 线性规划单纯形法与单纯形表
    • 2.5 第五节 单纯形法的矩阵描述
    • 2.6 第六节 人造基下的单纯形法
    • 2.7 第七节 线性规划典型例题及应用
  • 3 第三章 运输问题
    • 3.1 第一节 运输问题的数学模型及其特征
    • 3.2 第二节 运输模型的求解---表上作业法
    • 3.3 第三节 运输问题的推广
  • 4 第四章 整数规划
    • 4.1 第一节 整数规划概念与特点
    • 4.2 第二节 分枝定界法
    • 4.3 第三节 割平面法
    • 4.4 第四节 0—1规划与隐枚举法
    • 4.5 第五节 指派问题与匈牙利法
    • 4.6 第六节 典型例题及应用
  • 5 第五章 图与网络
    • 5.1 第一节 图的基本概念
    • 5.2 第二节 树
    • 5.3 第三节 最短路问题
    • 5.4 第四节 网络最大流问题
    • 5.5 第五节 Euler图
    • 5.6 第六节 中国邮递员问题
  • 6 第六章 网络计划
    • 6.1 第一节 网络计划图
    • 6.2 第二节 网络计划图的时间参数
    • 6.3 第三节 网络计划的优化
  • 7 第七章 排队论
    • 7.1 第一节 排队论的基本概念
    • 7.2 第二节 排队系统常用分布
    • 7.3 第三节 单服务台模型
  • 8 第八章 存储论
    • 8.1 第一节 存储论基础
    • 8.2 第二节 确定性库存模型
    • 8.3 第三节 确定性库存模型的参数分析
    • 8.4 第四节 随机型存储模型
  • 9 第九章 决策论
    • 9.1 第一节 决策论基本问题
    • 9.2 第二节 完全不确定型决策
    • 9.3 第三节 风险型决策
    • 9.4 第四节 效用理论在决策中的应用
第三节 风险型决策

第三节风险型决策

根据自然条件,某农场可以选择种植的农作物有四种:水稻、小麦、大豆、燕麦。该农场所在地区每一年可能发生的天气类型有五种:极旱年、旱年、平年、湿润年、极湿年。在不同的天气条件下,种植每一种农作物所获得的收益各不相同。表9-3给出了每一种天气类型发生的概率,以及在每一种天气类型条件下种植各种农作物所获得的收益(千元/)。试问,该农场究竟应该种植哪一种农作物?

该例所描述的就是一个决策问题。在这一个决策问题中,各种天气类型就是自然状态,共有5种状态,即极旱年旱年平年湿润年极湿年,各状态发生的概率,即状态概率分别为0.10.20.40.20.1各农作物种类就是行动方案,共有四种方案,即水稻小麦大豆燕麦;在每一种状态下,各方案的益损值就是在每一种天气类型下各种农作物的收益值。

9-3 每一种天气类型发生的概率及各种农作物的收益

                                                     

 

天气类型

 
 

极旱年

 
 

旱年

 
 

干年

 
 

湿年

 
 

极湿年

 
 

发生概率

 
 

0.1

 
 

0.2

 
 

0.4

 
 

0.2

 
 

0.1

 
 

农作物的收益(单位:千元/m2)

 
 

水稻

 

小麦

 

大豆

 

燕麦

 
 

100

 

250

 

120

 

118

 
 

120

 

210

 

170

 

150

 
 

180

 

170

 

200

 

170

 
 

200

 

120

 

170

 

190

 
 

220

 

80

 

110

 

210

 







风险型决策是指决策者在目标明确的前提下,对客观情况并不完全了解,存在着决策者无法控制的两种或两种以上的自然状态,但根据过去经验可以估计出现每一种自然状态的可能性有多大,即发生的概率有多大,因此依据概率算出不同状态下的效益值,然后做出决策。风险型决策主要应用于战略决策或非程序化决策,如投资方案决策、产品研发决策等。

常用的方法有:期望值准则决策方法、决策树法等

9.3.1期望值准则

以期望值为标准的决策方法:以收益和损失矩阵为依据,分别计算各可行方案的期望值,选择其中期望收益值最大(或期望损失值最小)的方案作为最优方案。具体为:

表示第个方案的期望值;表示采取第个方案,出现第种状态时的损益值;表示第种状态发生的概率,总共可能出现种状态,则期望损益的计算公式为:

9.2某电信公司决定开发新产品,需要对产品做出决策,有三种产品可供开发。未来市场对产品需求情况有三种,即较大、中等、较小,经估计各种方案在各种自然状态下的效益值及发生的概率如下表9-4所示,工厂生产何种产品,才能使收益最大。

9-4 效益值表(单位:万元)

               

 

自然状态及概率

 

方案

 
 

需求量大

 

1=0.3

 
 

需求量中等

 

2=0.4

 
 

需求量小

 

3=0.3

 
 

 

 

 
 

50

 

30

 

10

 
 

20

 

25

 

10

 
 

-20

 

-10

 

10

 

解:求出各决策方案的效益期望值

=50×0.3+20×0.4+(-20)×0.3=17

=30×0.3+25×0.4+(-10)×0.3=16

=10×0.3+10×0.4+10×0.3=10

由此可知,最大值是,所以,选择开发产品

期望值决策准则适用于一次决策多次重复进行生产的情况,所以它是平均意义下的最优损益。

9.3.2决策树

决策树是对决策局面的一种图解。它是把各种备选方案、可能出现的自然状态及各种损益值简明地绘制在一张图表上。用决策树可以使决策问题形象化。决策树由决策点、事件点及结果构成的树形图,一般应用于序列决策中,以最优损益值作为决策准则。

决策树基本模型如图9-2所示。

:表示决策点,也称树根,由它发出的分支称为方案分支,也称为树枝,条树枝表示有种选择方案。

:表示策略点,其上方数字表示该方案的最优损益值,由其引出的条线称为概率枝,表示有种自然状态,其发生的概率标明在分枝上。

:表示每个方案在相应自然状态的效益值。

:表示经过比较,此选择方案被否决,称之为剪枝。

决策方法:

(1)根据条件,画出决策树图;

(2)从右向左计算各方案期望值,其中,并进行标注;

(3)对期望值进行比较,选出最大期望值,写在上方,表明其所对应方案为决策方案,同时在其他方案枝上打‖删除。

9.3某厂投入不同数额的资金对机器进行改造,改造有三种方法,分别为购买新机器、大修与维护。根据经验,相关投入额及不同路情况的效益值如表9-5所示,请选择最佳方案。

9-5效益值表

               

 

供选方案

 
 

投资额Ti

 
 

销路好i=0.6

 
 

销路不好i=0.4

 
 

:购新

 

:大修

 

:维护

 
 

12

 

8

 

5

 
 

25

 

20

 

15

 
 

-20

 

-12

 

-8

 

(1)根据题意,做出决策树,如图9-2

9-2

93 决策树图

(2)计算各方案期望值

(3)最大值为,选对应方案,即维护机器,并将剪枝。

9.3这种类型称为单级决策问题。在序列决策中,常常需要根据阶段的不同作出不同的多次决策,包括两级或两级以上的决策称为多级决策问题。决策树法特别适合多级决策问题。

9.4某公司由于市场需求增加,使得公司决定要扩大公司规模,供选方案有三种:第一种方案,新建一个大工厂,需投资250万元;第二种方案,新建一个小工厂,需投资150万元;第三种方案,新建一个小工厂,2年后若产品销路好再考虑扩建,扩建需追加120万元,后3年收益与新建大工厂间,如表9-6所示,根据预测该产品前三年畅销和滞销的概率分别为0.60.4。若前2年畅销,则后3年畅销后滞销概率为0.80.2;若前2年滞销,则后3年一定滞销。请对方案做出选择。

 

 

9-6效益值表

                                                         

 

自然状态

 
 

概率

 
 

供选方案与效益

 
 

2

 
 

3

 
 

大工厂

 
 

小工厂

 
 

先小后大

 
 

2

 
 

3

 
 

畅销

 
 

0.6

 
 

畅销0.8

 

滞销0.2

 
 

150

 
 

80

 
 

80

 
 

150

 
 

滞销

 
 

0.4

 
 

畅销0

 

滞销1

 
 

50

 
 

20

 
 

20

 
 

50

 
 

成本

 
 

250

 
 

150

 
 

150

 
 

120

 

 

9-4

解:(1)画决策树如图9-4

(2)计算节点567810的期望值

 

    

由于存在二级决策,即在9决测点,则应该首先计算出节点1112的效益期望值,决定是否扩建。

由于,因此取最大值对应的方案,即在决策点1上,删去不扩建方案,选择扩建方案。

求节点234的效益期望值,分别为:

(3)比较方案,最大,则取最大值112,对应的方案是先小后大作为选定方案,即先建小厂,后扩建大工厂的方案为最终方案。

9.3.3贝叶斯决策

风险决策时,决策者要估计各事件出现的概率,但决策者常常碰到的问题是没有掌握充分的信息,于是决策者通过调查及做实验等途径去获得更多的更确切的信息,以便掌握各事件发生的概率,这可以利用贝叶斯公式来实现,它体现了最大限度地利用现有信息,并加以连续观察和重新估计。

将依据过去的信息或经验由决策者估计的概率称之为主观概率。未收到新信息时根据已有信息和经验,估计出的概率分布称为先验概率;用随机试验确定出的概率称为客观概率。收到新信息,修正后的概率分布称为后验概率。在事件已经发生的条件下,事件发生的概率,称为事件在给定下的条件概率,记为

贝叶斯公式:若构成一个完备事件,,则对任何概率不为零的事件,有

利用贝叶斯公式可以修正对某件事情估计的概率,具体步骤为:

(1)先依据过去的信息或经验由决策者估计获得将发生事件的事前(先验)概率。

(2)根据调查或试验计算得到条件概率,利用贝叶斯公式:

计算出各事件的事后(后验)概率。

9.5某钻探大队在某地区进行石油勘探,主观估计该地区有油的概率为;无油的概率为,为了提高钻探的效果,先做地震试验。根据积累的资料得知:凡有油地区做实验结果亦好的概率为;做试验好结果不好的概率为。凡无油地区做试验结果好的概率为;做试验结果不好的概率为问该地区做试验后,有油与无油的概率各是多少?

解:先计算做地震试验好与不好的概率。

做地震试验好的概率

做地震试验不好的概率

利用贝叶斯公式计算各事件的事后概率(后验概率)

做地震试验好的条件下有油的概率

做地震试验好的条件下无油的概率

做地震试验不好的条件下有油的概率

做地震试验不好的条件下无油的概率

9.6盒子里有100枚均匀的硬币,有60枚是正常的,40枚两面都是徽。从盒子中任取一枚让你猜是哪一类硬币。猜中得10元,猜不中不得钱。你猜是哪一类?

9-7决策矩阵

                       


 

(正常)

 
 

(双徽)

 
 

先验概率

 
 

3/5

 
 

2/5

 
 

(猜正常)

 
 

10

 
 

0

 
 

(猜双徽)

 
 

0

 
 

10

 

获利的期望值:=10×3/5+0×2/5=6=0×3/5+10×2/5=4

正确决策是:猜正常。

如果现在抛掷3次,3次都出现徽,你又如何猜?该硬币是正常的概率为多少,是双徽的概率为多少。

H3次出现反面这一随机事件,为硬币是正常,为硬币是双徽,则(客观概率)

3次都出现双徽的概率为:

后验概率(贝叶斯公式)

用后验概率代替原来的概率,决策矩阵为:

9-8决策矩阵

                       


 

(正常)

 
 

(双徽)

 
 

后验概率

 
 

3/19

 
 

16/19

 
 

(猜正常)

 
 

10

 
 

0

 
 

(猜双徽)

 
 

0

 
 

10

 

获利的期望值:=10×3/19+0×2/5=30/19=0×3/5+10×16/19=160/19

正确的决策是:应该选择猜双徽。

与例9.6类似,借助于一些新收到的信息与已知信息和经验的结合,可以得出不同的决策结果,这可以提高决策质量。这种决策方法称为贝叶斯决策。

贝叶斯决策步骤:

(1)先验分析。根据先验概率按照期望值准则作出决策,得到效益期望值

(2)后验分析。经过试验调查计算所得结果对先验概率分布做修正,得出后验概率分布,再做新决策得到效益期望值

若对效益型指标而言有->调查费用,则认为调查是合算的。其差-称为全情报价值。

具体过程为:设调查后得到结果为种,即,效益函数为。根据过去经验可知当自然状态为Nj条件下调查结果为Zk的条件概率

再利用贝叶斯公式和全概率公式,求当结果为ZK的条件下自然状态为Nj的条件概率

  

在后验分析中用代替先验分析中的(Nj),利用期望值准则计算出Ek

 

 

再根据全概率公式,可知结果为Zk的概率。因此,后验分析的效益期望值为。

9.7某厂对一台机器的换代问题做决策,有三种方案:为买另一台新机器;为对老机器进行改建;是维护加强、输入不同质量的原料。三种方案的收益见表9-9。约有30%的原料是质量好的,还可以花600元对原料的质量进行测试,这种测试可靠性见表9-10。求最优方案。

9-9收益表(单位:万元)

                       

 

原料质量Ni

 
 

购新机器

 
 

改建老机器

 
 

维护老机器

 
 

N1(0.3)

 
 

3

 
 

1.0

 
 

0.8

 
 

N2(0.7)

 
 

-1.5

 
 

0.5

 
 

0.6

 

9-10测试可靠性

                     

 

 
 

原料的实际质量

 
 

N1

 
 

N2

 
 

测试结果

 
 

Z1

 
 

0.8

 
 

0.3

 
 

Z2

 
 

0.2

 
 

0.7

 

 

解:(1)若不做测试,各方案的先验收益

万元

应选方案3,维护老机器。

(2)计算后验概率

已知,联合概率为:

边际概率为

从而由贝叶斯公式有:

则有

即当测试结果为原料的质量好,则购买新机器;若测试结果为原材料的质量差,则维护老机器。

决策为:应花600元进行测试,测试后若质量好,购入新机器生产;若质量差,维护老机器生产。