第六章 贝叶斯博弈
在这一章主要内容有：
一、豪尔绍尼转换，
二、贝叶斯博弈及贝叶斯纳什均衡，
最后为显示原理。
其中贝叶斯纳什均衡的概念是需要掌握的核心概念。
第一节豪尔绍尼转换
豪尔绍尼转换的想法非常简单，并不复杂，其实质就是将非完全信息造成的不确定性通过概率的方式来加以处理。为了较为形象的理解豪尔绍尼转换，我们还是通过案例加以说明。
例6.1 贝叶斯信用困境
商人2（良商） 商人2（奸商）
H C H C
H 2，2 0，‐1H 2，2 0，3
商人1
C ‐1，0 1，1 C ‐1，0 1，1
图6-1 贝叶斯信用困境
在贝叶斯信用困境这个博弈中，相当于存在着两个博弈。如果商人1
相信商人2是一个讲诚信的人，他们的纳什均衡为(H, H)和(C, C)。如果商人1相信商人2是一个奸商，那么纳什均衡为(C, C)，但到底哪一个策略组合是整个博弈的纳什均衡显然无法回答。原因在于商人1对商人2不同的信念(Belief)导致了即使是相同的策略，也会出现不同的收益，即在相同的策略组合下，收益具有不确定性。例如(H, C)这个策略组合，对参与者而言就有不同的收益，在商人2诚信的情况下，收益为(0, -1)；在商人2为奸商的情况下，收益则为(0, 3)。收益具有不确定性是所有非完全信息博弈与完全信息博弈相比最重要的差异，非完全信息也正是根据这一点来定义的。其次，图6-2实际上清楚地表明了贝叶斯信用困境所面临的困难，该博弈有两个开始点，在商人1行动的时候，商人1分不清他到底处于那种情况，是处于（商人2）诚信，还是处于（商人2）欺骗。由于该博弈有两个开始点，可以理解
为两个不同的博弈，但关键是，这两个博弈被一条虚线连接了起来，因而它又是一个博弈。两个开始点还意味着我们从博弈的结束点往回推，我们不知道会回到哪一个开始点。这意味着如果参与者要达到某个结束点，那么不知道采取什么样的策略才能达到这个结束点，也就是说没有人能保证一定走到这个结束点，因而均衡会不会出现只有上帝才知道了，当然最优策略也就无从谈起。
奸商2
良商2
图6-2 贝叶斯信用困境
最后，在石头、剪刀、布的博弈（完全信息博弈）中，混合策略形成
的纳什均衡实际上也包含着一点点的收益不确定性，这似乎意味着在非完全信息博弈和完全信息博弈之间（均衡概念上）存在着某种联系。这种联系就是期望值。
要知道期望值首先得知道概率分布。在贝叶斯信用困境中，把商人2是什么样的人看作一种概率分布，显然是一个非常妙的想法，它既克服了贝叶斯博弈中存在的矛盾，又能利用v-N-M偏好理论来分析参与者的偏好（期望值），从而最优策略，乃至纳什均衡都有了意义。最早把这一想法变成规范性的学术语言是由经济学家豪尔绍尼在1967完成的，被称为豪尔绍尼转换。也正因为这个贡献，豪尔绍尼与纳什和塞尔腾(Selten)分享了1994的诺贝尔经济学奖。
定义6.1豪尔绍尼转换——不同状态的出现服从一定的概率分布，并且这个概率分布是公共信息。
通过转换，图6-2可以重新转换为图6-3。
Nature
‐1 0
2 2 1
1 ‐10
1
3
0 2 0
2 ‐1 1
图6-3 转换后的贝叶斯信用困境
所有可能策略组合下商人1的期望值就列在了图6-4中。
其中(H，H)表示商人2为良商选择H，为奸商时选择H，其他类推。
商 人 2
商人2 (H, H) (H, C) (C, H) (C, C)
商人1
H 2 1 1 0 C ‐1 0 0 1
图6-4 贝叶斯信用困境中商人1的期望值
这里我们可以看到，对于商人1而言，其策略为H和C，而对于商人2而言，其策略则为4个：(H, H)，(H, C)，(C, H)和(C, C)。读者可能会问，商人2不是知道自己是什么样的人吗？为什么商人2的策略不是H或C，却是(H, H)，(H, C)，(C, H)和(C, C)呢？我们可以从三个方面来理解这点：一是在博弈开始之前，商人2也不知道到底会出现什么状态，即不知道自己是否是诚信还是欺诈，所以他必须事先有所计划，规定好在什么样的状态下选择什么样的行动。例如商人2以为自己是奸商，但结果发现自己是良商，如果策略只是C，那么商人2将不知道在状态为良商的情况下如何行动。二是商人1到市场上交易，
那么有可能遇到良商，也可能遇到奸商，其概率各为1/2。给定商人1选择H，那么良商和奸商的策略显然不同，而(H, C)就表示良商选择H，而奸商选择C。三是虽然商人2知道自己是什么样的人，但商人1并不知道，因而商人2不得不把自己想象成商人1，以便获得有关商人1的信念的一种正确猜测，以便选择最优行动。因而，商人2的策略必然由H和C所组成。
例6.2 罗密欧与朱丽叶
罗密欧和朱丽叶相约去听音乐会，罗密欧向朱丽叶提出邀请，但罗密欧不知道朱丽叶是否喜欢自己。如果喜欢，那么两人一起听音乐一定要好过彼此分开；相反，如果不喜欢，那么朱丽叶就会主动回避，以免一起听音乐会遭遇尴尬。对于朱丽叶而言，也可能遇到相同的情况，如果罗密欧喜欢她，那么两人一起听音乐会要好过彼此分开；相
反，如果不喜欢，那么罗密欧就会主动回避，以免尴尬。而因，该博弈就可能会出现4种状态：xx，xb，bx和bb。x代表喜欢，b代表不喜欢。例如，xb表示罗密欧喜欢朱丽叶，但朱丽叶不喜欢他。
图6‐5 罗密欧与朱丽叶
第二节 贝叶斯博弈与纳什均衡
一、贝叶斯博弈
要给出贝叶斯博弈的表达式需引进若干新的概念。
所谓状态就是对参与者特性集合的一个完整描述，包含着参与者的偏好和相关信息。不同的状态意味着不同的特性集合，所有可能的状态就构成了状态集合。我们用z 来表示某个状态，Z ={z 1, z 2, …}就表示状态集合。
在博弈开始时某个状态成为现实，但（有些）参与者并不能直接观察到状态（否则就是完全信息了），而是观察到某种信号，这个信号可能反映出有关状态的某些信息。我们用()i z τ来表示参与者i 在状态z 发生时观察到的信号，函数i τ就称为参与者i 的信号函数。显然，如果
对于每一个参与者而言，任意z y ≠意味着()i ()i z y ττ≠，那么就不存在不
确定性，因而如果信息是不完全的，就一定存在着某些状态发出的信号一样（这样参与者才分不清到底是哪种状态）。凡是给出信号t i 的状态的集合就称为与信号t i 相一致的状态类，简称状态类t i ，数学上可表示为{z : ()i z t τ=1()i z i }。如果每一个参与者的每一个状态类只包含一个状态，就说明这个博弈是一个完全信息博弈，另一个极端情况则是只存在一个状态类（即所有状态发出的信号都一样），因而参与者i 状态类的大小实际上反映了参与者i 拥有信息的充分性。例如，存在三个状态z 1，z 2和z 3，1t τ=，23()()i i z z 2t ττ==，因而当参与者i 观察到信号为t 1时，参与者i 知道发生的是状态z 1，但如果观察到t 2，参与者i 只知道发生了状态z 2或z 3，但不能确定到底是哪一个状态。参与者i 的信念就是定义在状态类上的概率分布。例如，状态类t 1只包含一个状态，因而其概率就是1，而状态类t 2包含两个状态，因而有关状态z 2和z 3的信
念就是一个概率分布(p, 1–p )。在非完全信息静态博弈中，参与者的偏好是定义在行动和状态之上的，即收益函数为u(a; z)，其中a为行动组合。由于参与者对状态不确定，因而参与者的偏好必须考虑与向量(a; z)相应的概率分布，因而参与者的收益函数实质上为伯努利收益函数，即满足v-M-N理性偏好的要求。
实际上，对于参与者的信念，准确的定义应该考虑条件概率，而不是简单概率。我们用Pr(z|t i)来表示参与者i在观察到信号t i的条件下，对状态z可能发生概率的一个猜测（信念），并且参与者会根据贝叶斯法则不断对这种猜测进行修正。通常为了分析简单，我们假设各状态之间彼此独立。
有了上面这些说明，现在就可以给出贝叶斯博弈的正式定义。
定义6.2 贝叶斯博弈的基本式表示为G B={N, Z, A, T, P, u}，其中
N 为参与者集合；Z 为状态集合；A 为行动集合；T 为信号集合；P 则为概率分布集合，它实际上代表着参与者的信念，对于参与者i 而言，状态z 的后验概率为Pr(z |t i )；u =(u 1,…, u n )，u i 是参与者i 定义在(a ; z )上的伯努利收益函数，因而参与者i 的期望收益v i =Pr(z 1| t )u i (a , z 1) + … + Pr(z k | t )u i (a , z k )，其中状态类t ={z 1, z 2, …, z k }。
参与者的策略实际上是由状态到行动的一个函数，因而可以根据状态与行动构造出参与者的策略。另，参与者的信念P 是理性的，既符合贝叶斯法则。如果z 是离散的，参与者i 观察到信号t ，那么
{}Pr()Pr(|)Pr()t
z z z z t z ∈=∑ (6-1) 其中{z }t 表示状态类t ，即{z : ()i z t τ=}。
例6.1贝叶斯信用困境的基本式G B ={N , Z , A , T , P , u }，其中
（1）参与者集合：N={商人1，商人2}。
（2）状态集合：Z={良商，奸商}。
（3）行动集合：A i={H, C}，i N
∈。
（4）信号集合：T={{t1}, {t21, t22}}，对于商人1，
τ(良商)=1τ(奸
1
商)=t1，但对于商人2，
τ(良商)=t21，2τ(奸商)=t22。
2
（5）信念：对于商人1，Pr(良商| t1) = Pr(奸商| t1)= 1/2，而对于商人2，Pr(良商| t21) = 1，Pr(奸商| t21)=0，或者Pr(奸商| t22)= 1，Pr(良商|t22)=0。
（6）偏好：对于商人1而言，存在两个u1(a；良商)和u1(a；奸商)，期望收益就为v1 =1/2×u1(a；良商)+1/2×u1(a；奸商)，而对于商人2，其期望收益为v2 = 1×u2(a；良商)+0×u2(a；奸商)或v2 = 0×u2(a；良商)+1×u2(a；奸商)。
例6.2罗密欧与朱丽叶的基本式G B={N, Z, A, T, P, u}，其中
（1）参与者集合：N={罗密欧，朱丽叶}。
（2）状态集合：Z={xx, xb, bx, bb}。
（3）行动集合：A i={C, Pop}，i N
∈。（为了防止与概率分布P相混，用Pop来表示流行乐）
（4）信号集合：T={{x1, b1}, {x2, b2}}，即
τ(xx)=1τ(xb)=x1，1τ(bx)=
1
τ(bb)=b1，2τ(xx)=2τ(bx)=x2，2τ(xb)=2τ(bb)=b2。
1
（5）信念：对于罗密欧，Pr(xx| x1)=Pr(xb| x1) =1/2，Pr(bx| b1)=Pr(bb| b1)=1/2；对于朱丽叶，Pr(xx| x2)=Pr(bx| x2)=1/2，Pr(xb| b2)=Pr(bb| b2)=1/2。
（6）偏好：在喜欢的状态下，罗密欧的期望收益为v1=1/2×u1(a, xx)+1/2×u i(a, xb)；在不喜欢的状态下，v1=1/2×u1(a, bx)+1/2×u i(a, bb)。朱丽叶的期望收益类似，不再赘述。
二、贝叶斯纳什均衡
要定义纳什均衡首先得定义策略。
定义6.3 贝叶斯博弈G B = {N , Z , A , T , P , u }，参与者i 的一个纯策略s i 是一个由T i 映射到A i 的函数。对于T i 中的每一个t i ，s i (t i )表明当参与者i 观察到信号t i 时，参与者i 将从行动空间A i 中选择一个行动。
有了策略的定义，就可以定义相应的贝叶斯纳什均衡。
定义 6.4 贝叶斯博弈G B = {N , Z , A , T , P , u }，策略组合s *=(s 1*,…,s n *)是一个纯策略贝叶斯纳什均衡，如果对每一个．．．参与者i ，及对i 的信号空间T i 中的每一个．．．
信号t i ，s i *(t i )满足
11{:()}Pr(|)[*(()),,*(),*(())]i i i i i i n n z z z t z t u s z s t s z τ
ττ∈=∑L L > (6-2) 11{:()}
Pr(|)[*(()),,(),*(())]i i i i i i n n z z z t z t u s z s t s z ττ∈=∑L L τ其中，s i *(t i )≠s i (t i )。需要注意的是()z t τ=，s (t )=a ，所以u (a ; z )可
以紧凑地写作u(s(t))。
我们可以换一个角度来理解贝叶斯博弈中的参与者，即我们不是根据i N，来定义参与者，而是根据i和类型t，来定义参与者，即参与者为(i, t) N T。
命题6.1 贝叶斯博弈G B的贝叶斯纳什均衡与如下定义的策略式博弈G的纳什均衡完全等价。对于策略式博弈G={N, A, u}，其中（1）N为向量(i, t i)的集合，每一个(i, t i)都代表一个参与者。
（2）A为行动空间，A(i, t i)就是每一个参与者(i, t i)的行动集合。
（3）偏好：每一个参与者(i, t i)的伯努利收益函数为Pr(z|t i)u i[(a i,
Σ
a-i(z)); t i]，其中a-i(z)表示其他参与者在状态为z的情况下采取的行动。
例如，贝叶斯信用困境的策略式博弈G={N, A, u}：
（1）参与者集合：N={(1, H), (2, H), (2, C)}。(1, H)为诚信商人1，
(2, H)为诚信商人2，(2, C)代表欺诈商人2。
（2）行动空间：A 1, H ={H, C}，A 2, H ={H, C}，A 2, C ={H, C}。
（3）伯努利收益函数：对于商人1，期望收益函数为
112,H 1112,C 111(,;)(,;)22
u a a t u a a t +对于商人（2, H ），其收益函数为
u 2, H (a 1, a 2, H ; t 21) (因为Pr(H|t 21) =1)。
对于商人（2, C ），其收益函数为
u 2, C (a 1, a 2, C ; t 22) (因为Pr(C|t 22)=1)。
其中，t 1=H ，表示商人1收到的信号，t 21=H 和t 22=C ，表示商人2收到的信号。根据纳什均衡的定义，很容易得到(H, (H, C))为贝叶斯信用困境的纳什均衡（即商人1与商人(2, H)的纳什均衡为(H, H)，商人1与商人(2, C)的纳什均衡为(H, C)，记住商人1的收益是期望收益），。
它也是该博弈的贝叶斯纳什均衡。
混合策略的贝叶斯纳什均衡定义实际上也是一样的，只不过混合策略为从类型映射到一个概率分布而已。
定义6.5在贝叶斯博弈G B = {N , Z, A, T, P, u}中，参与者i的一个混合策略s i是一个由T i映射到ΔA i的函数。ΔA i为定义在行动空间A i上的概率分布空间。对于任意一个行动a i∈A i，s i(t i)(a i)表示在混合策略s i(t i)下，a i被使用的概率。s=(s1, s2,…, s n)为一个混合策略组合，ΔS i 为参与者i所有可能混合策略的集合，而ΔS =(ΔS1 ,…, ΔS n)是所有可能策略组合的集合。
定理6.1贝叶斯纳什均衡存在性定理对于有限的贝叶斯静态博弈G B = {N, Z, A , T, P, u}，即参与者是有限的，A是有限的，Z是有限的，那么一定存在（混合）贝叶斯纳什均衡。
第三节 举 例
一、贝叶斯3人古诺模型
贝叶斯古诺模型的基本式G B={N, Z, A, T, P, u}，其中
（1）参与者集合：N={1, 2, 3}。
（2）状态集合：Z={{c1L c2L c3L, c1L c2L c3H, c1L c2H c3L, c1L c2H c3H, c1H c2L c3L, c1H c2L c3H, c1H c2H c3L, c1H c2H c3H}。
（3）行动集合：产量q i就是企业i的行动，行动空间A i = [0, a]。
（4）信号集合：T={c1L, c1H, c2L, c2H, c3L, c3H}，对于企业1而言，τ1(c1L c2L c3L) =τ1(c1L c2L c3H) =τ1(c1L c2H c3L) =τ1(c1L c2H c3H) =c1L，τ
(c1H c2L c3L) =τ1(c1H c2L c3H) =τ1(c1H c2H c3L) =τ1(c1H c2H c3H) = c1H，即企业1 1
知道自己的成本，但不知道其他企业的成本。其他类推。
第六章博弈论 主要内容：本章共分四节：第一节，简单博弈与博弈均衡；第二节，重复博弈与序列博弈；第三节，威胁与承诺；第四节，几种相关的策略。在第一、二节中将介绍博弈论的一些基本概念，在第三、四节中运用博弈论来分析寡占市场中厂商的一些竞争策略，包括厂商的定价策略、产品选择策略、阻止进入策略等。 教学重点：了解关于博弈论的基本概念，掌握上策均衡与纳什均衡的区别；学会运用重复博弈和序列博弈分析案例，并能够运用博弈论的基本知识分析厂商的基本竞争策略。 关键概念：博弈均衡上策上策均衡纳什均衡重复博弈序列博弈威胁承诺 第三节威胁与承诺 一、阻止市场进入的威胁 威胁与承诺是博弈论中的一个重要论题，它可以用来分析竞争中的一种重要现象。“小镇上的折扣店”是市场进入中的一种较为特殊的现象，在更一般的情况中，一个市场不一定只能容纳一家厂商。此时市场进入的博弈也有所不同。 例证 7 ：阻止市场进入的威胁博弈 已有一个垄断经营者，现在有另一家厂商作为潜在的竞争者试图进入这个市场。对垄断者来说，如果要想保住自己的垄断地位，就会设法阻止潜在竞争者的进入。在这个博弈中，潜在竞争者有两种策略可以选择，即进入或不进入；垄断者也有两种策略，或者与进入者打一场商战，或者默许他的进入。这个博弈的报酬矩阵如表 6.6 所示。 表 6.6 阻止市场进入的博弈 垄断者 商战默许 潜在进入者进入－ 200 ， 600 900 ， 1 100 不进入0 ， 3 000 0 ， 3 000 在这个博弈中，策略选择是有着确定的顺序的：潜在进入者做出选择（进入或不进入）→垄断者决定（默许进入或进行商战）。当然，潜在进入者在做出决策的时候必须要考虑垄断者的反应。 假定潜在进入者进入市场需要花费进入成本 200 万元。对于进入者来说，如果其选择了进入市场的策略，当垄断者默许的时候，他可获利 900 万元；但如果垄断者决定与他进行一场商战时，垄断者依然可以获利 600 万元，而进入者将亏损 200 万元。市场进入的扩展形式见图6.2 。
《管理运筹学》第四版课后习题解析（上） 第2章 线性规划的图解法 1．解： （1）可行域为OABC 。 （2）等值线为图中虚线部分。 （3）由图2-1可知，最优解为B 点，最优解1x = 127，2157x =；最优目标函数值697 。 图2-1 2．解： （1）如图2-2所示，由图解法可知有唯一解12 0.2 0.6x x =??=?，函数值为3.6。 图2-2 （2）无可行解。 （3）无界解。 （4）无可行解。 （5）无穷多解。
（6）有唯一解 12203 8 3x x ?=????=?? ，函数值为923。 3．解： （1）标准形式 12123max 32000f x x s s s =++++ 1211221231212392303213229,,,,0 x x s x x s x x s x x s s s ++=++=++=≥ （2）标准形式 1212min 4600f x x s s =+++ 12112212121236210764,,,0 x x s x x s x x x x s s --=++=-=≥ （3）标准形式 1 2212min 2200f x x x s s ''''=-+++ 12 211 2212221 2212355702555032230,,,,0x x x s x x x x x x s x x x s s '''-+-+=''''-+=''''+--=''''≥ 4．解： 标准形式 1212max 10500z x x s s =+++ 1211221212349528,,,0 x x s x x s x x s s ++=++=≥ 松弛变量（0，0） 最优解为 1x =1，x 2=3/2。 5．解：
习题解答 1. 已知矩阵博弈局中人I 的赢得矩阵如下，求最优纯策略及博弈值。 （1） ?? ??????? ???83 54 66756544 3494 （2） ????? ? ??? ???------------21221405126331222 210 解: (1) () 8 695 354 38354667565443494? ???????? ??? 所以),(13βα,V=5 (2) 2 - 3 2- 2 2 2562)2(1)2(214051263312)2(2)2(10----??? ?????????------------ 所以 ),(31βα,),(51βα,),(33βα,),(53βα,V=-2 2． 甲乙两国进行乒乓球团体赛，每国由三个人组成一个队参加比赛。甲国的人员根据不同的组合可组成4个队，乙国的人员可组成3个队，根据以往的比赛记 解: 6 282 8276128184)2(3715---??? ?????????------ 所以),(22βα,V=2 答: 双方应均派第2队出场 3. 对任意一个m 行n 列的实数矩阵A=（a ij ）,试证有下式成立
ij m i n j ij n j m i a a ≤≤≤≤≤≤≤≤≤1111max min min max 证: ij m i n j ij n j m i ij m i ij n j m i ij ij n j a a a a j a a n j m i j i ≤≤≤≤≤≤≤≤≤≤≤≤≤≤≤≤≤∴≤?∴≤≤≤≤≤?11111111max min min max max min max ,min : 1,1,,有有 4. 某城区有A 、B 、C 三个居民小区，分别居住着40％，30%，30%的居民，有两个公司甲和乙都计划在区内建造超市，公司甲计划建两个，公司乙计划建一个，每个公司都知道，如果在某个小区内设有两个超市，那么这两个超市将平分该区的消费，如果在某个小区只有一个超市，则该超市将独揽这个小区的消费。如果在一个小区没有超市，则该小区的消费将平分给三个超市。每个公司都想使自己的营业额尽可能地多．试把这个问题表示成一个矩阵博弈，写出公司甲的赢得矩阵，井求两个公司的最优策略以及各占有多大的市场份额。 解: 甲公司的策略集为{(A,B), (A,C), (B,C)} 乙公司的策略集为{A,B,C} 甲的赢得矩阵为: 75 .075.07.06 .07.07 .0717.0717.06.075.07.0)7.0(7.075.0)7.0(),(),(),(?? ????????C B C A B A C B A 所以甲选(A,B)或(A,C),占70%份额。乙选A,占30%份额. 5． 一个病人的症状说明他可能患a ，b ，c 三种病中的一种，有两种药C ，D 可 解: 8.04.07.01.04 .08.01.07.06.0)4.0(5.0?????? 最优策略为),(21βα 答:应开C 药较为稳妥. 6．设矩阵博弈局中人I 的赢得为 A=?? ?? ? ?????--203233
第六章习题 一、判断下列表述是否正确，并作简单分析 （1）完全但不完美信息动态博弈中各博弈方都不清楚博弈的进程，但清楚博弈的得益。 答：不一定，不是所有博弈方都不清楚博弈的进程，只要有一个博弈方都不完全清楚博弈的进程。 （2）不完美信息动态博弈中的信息不完美性都是客观因素造成的，而非主观因素造成。 答：错。信息不完美很多是人为因素所造成的，因为出于各自的动机和目的，人们在市场竞争或合作中常常会故意隐瞒自己的行为。 （3）在完全但不完美信息动态博弈中，若不存在混合策略，并且各博弈方都是主动选择且行为理性的，则不完美信息从本质上说是“假的”。 答：正确。因为只包含理性博弈方的主动选择行为，利益结构明确，而且不同路径有严格优劣之分，从不需要用混合策略的动态博弈来说，所有博弈方选择的路径都可以通过分析加以确定和预测，根本无须观察。从这个意义上说，这种博弈的不完美信息实际上都是假的。 （4）子博弈可以从一个多节点信息集开始。 答：不能从多节点信息集开始，因为多节点必然分割信息集。 （5）不完美信息是指至少某个博弈方在一个阶段完全没有博弈进程的信息。 答：不是完全没有博弈进程的信息，而是没有完美的信息，只有以概率判断形式给出的信息。 二、用柠檬原理和逆向选择的思想解释老年人投保困难的原因。
答：“柠檬原理”是在信息不完美且消费者缺乏识别能力的市场中，劣质品赶走优质品，最后搞垮整个市场机制。“逆向选择”是在同样不完美市场和消费者缺乏识别能力的市场中，当价格可变时，价格和质量循环下降，市场不断向低端发展的机制。 老年人投保的分析：大致思路是由于信息不对称，费用越来越高，投保人的健康状况好的比例越来越小，最终发展成为只有身体不好的人才参加投保。如果允许调整费率，保险公司为了避免亏损降低风险，上调保费率，健康状况相对好一些的退出市场，整个市场状况恶化。…… 这就是逆向选择机制在老年保险市场上作用的结果。 三、用完全但不完美信息动态博弈的思想，讨论我国治理假冒伪劣现象很困难的原因。 答：商品交易中的质量问题可以用完全但不完美信息动态博弈来描述。商品交易中的假冒伪劣现象正是这种市场低效率均衡的表现形式。主要因素包括：（1）信息不完美程度比较严重。信誉的建立有差距，信息不对称现象严重等； （2）消费者识别能力低下而且麻木。不法商贩的造假成本低，消费者识别能力低下，而且容忍麻木，知假买假，很难治理（如盗版等）； （3）暴力空间的存在。价格水平不合理，定价过高，垄断暴利，造价者利润空间大。 （4）对造价者打击不力。执法部门、政府管理部门打击力度不够，而且保护甚至纵容（“激励的悖论”）； （5）我国社会经济环境的变化太大，稳定性比较差。
运筹学部分课后习题解答P47 1.1 用图解法求解线性规划问题 a） 12 12 12 12 min z=23 466 ..424 ,0 x x x x s t x x x x + +≥ ? ? +≥ ? ?≥ ? 解：由图1可知，该问题的可行域为凸集MABCN，且可知线段BA上的点都为 最优解，即该问题有无穷多最优解，这时的最优值为 min 3 z=2303 2 ?+?= P47 1.3 用图解法和单纯形法求解线性规划问题 a） 12 12 12 12 max z=10x5x 349 ..528 ,0 x x s t x x x x + +≤ ? ? +≤ ? ?≥ ? 解：由图1可知，该问题的可行域为凸集OABCO，且可知B点为最优值点， 即 1 12 122 1 349 3 528 2 x x x x x x = ? += ?? ? ?? +== ?? ? ，即最优解为* 3 1, 2 T x ?? = ? ?? 这时的最优值为 max 335 z=1015 22 ?+?=
单纯形法： 原问题化成标准型为 121231241234 max z=10x 5x 349 ..528,,,0x x x s t x x x x x x x +++=?? ++=??≥? j c → 10 5 B C B X b 1x 2x 3x 4x 0 3x 9 3 4 1 0 0 4x 8 [5] 2 0 1 j j C Z - 10 5 0 0 0 3x 21/5 0 [14/5] 1 -3/5 10 1x 8/5 1 2/5 0 1/5 j j C Z - 1 0 - 2 5 2x 3/2 0 1 5/14 -3/14 10 1x 1 1 0 -1/7 2/7 j j C Z - -5/14 -25/14
《运筹学》第六章排队论习题 1. 思考题 （1）排队论主要研究的问题是什么； （2）试述排队模型的种类及各部分的特征； （3）Kendall 符号C B A Z Y X /////中各字母的分别代表什么意义； （4）理解平均到达率、平均服务率、平均服务时间和顾客到达间隔时间等概念； （5）分别写出普阿松分布、负指数分布、爱尔朗分布的密度函数，说明这些分 布的主要性质； （6）试述队长和排队长；等待时间和逗留时间；忙期和闲期等概念及他们之间的联系 与区别。 2．判断下列说法是否正确 （1）若到达排队系统的顾客为普阿松流，则依次到达的两名顾客之间的间隔时间 服从负指数分布； （2）假如到达排队系统的顾客来自两个方面，分别服从普阿松分布，则这两部分 顾客合起来的顾客流仍为普阿松分布； （3）若两两顾客依次到达的间隔时间服从负指数分布，又将顾客按到达先后排序， 则第1、3、5、7，┉名顾客到达的间隔时间也服从负指数分布； （4）对1//M M 或C M M //的排队系统，服务完毕离开系统的顾客流也为普阿松流； （5）在排队系统中，一般假定对顾客服务时间的分布为负指数分布，这是因为通过对大 量实际系统的统计研究，这样的假定比较合理； （6）一个排队系统中，不管顾客到达和服务时间的情况如何，只要运行足够长的时间后， 系统将进入稳定状态； （7）排队系统中，顾客等待时间的分布不受排队服务规则的影响； （8）在顾客到达及机构服务时间的分布相同的情况下，对容量有限的排队系统，顾客的 平均等待时间少于允许队长无限的系统； （9）在顾客到达分布相同的情况下，顾客的平均等待时间同服务时间分布的方差大小有 关，当服务时间分布的方差越大时，顾客的平均等待时间就越长； （10）在机器发生故障的概率及工人修复一台机器的时间分布不变的条件下，由1名工人 看管5台机器，或由3名工人联合看管15台机器时，机器因故障等待工人维修的平均时间不变。 3．某店有一个修理工人，顾客到达过程为Poisson 流，平均每小时3人，修理时间服从负 指数分布，平均需19分钟，求： （1）店内空闲的时间； （2）有4个顾客的概率； （3）至少有一个顾客的概率； （4）店内顾客的平均数； （5）等待服务的顾客数； （6）平均等待修理的时间； （7）一个顾客在店内逗留时间超过15分钟的概率。 4．设有一个医院门诊，只有一个值班医生。病人的到达过程为Poisson 流，平均到达时间间隔为20分钟，诊断时间服从负指数分布，平均需12分钟，求： （1）病人到来不用等待的概率； （2）门诊部内顾客的平均数； （3）病人在门诊部的平均逗留时间； （4）若病人在门诊部内的平均逗留时间超过1小时，则医院方将考虑增加值班医生。问 病人平均到达率为多少时，医院才会增加医生？ 5．某排队系统只有1名服务员，平均每小时有4名顾客到达，到达过程为Poisson 流，，服务时间服从负指数分布，平均需6分钟，由于场地限制，系统内最多不超过3名顾客，求： （1）系统内没有顾客的概率； （2）系统内顾客的平均数；
《运筹学》第六章排队论习题 转载请注明 1. 思考题 （1）排队论主要研究的问题是什么； （2）试述排队模型的种类及各部分的特征； （3）Kendall 符号C B A Z Y X /////中各字母的分别代表什么意义； （4）理解平均到达率、平均服务率、平均服务时间和顾客到达间隔时间等概念； （5）分别写出普阿松分布、负指数分布、爱尔朗分布的密度函数，说明这些分 布的主要性质； （6）试述队长和排队长；等待时间和逗留时间；忙期和闲期等概念及他们之间的联系 与区别。 2．判断下列说法是否正确 （1）若到达排队系统的顾客为普阿松流，则依次到达的两名顾客之间的间隔时间 服从负指数分布； （2）假如到达排队系统的顾客来自两个方面，分别服从普阿松分布，则这两部分 顾客合起来的顾客流仍为普阿松分布； （3）若两两顾客依次到达的间隔时间服从负指数分布，又将顾客按到达先后排序， 则第1、3、5、7，┉名顾客到达的间隔时间也服从负指数分布； （4）对1//M M 或C M M //的排队系统，服务完毕离开系统的顾客流也为普阿松流； （5）在排队系统中，一般假定对顾客服务时间的分布为负指数分布，这是因为通过对大 量实际系统的统计研究，这样的假定比较合理； （6）一个排队系统中，不管顾客到达和服务时间的情况如何，只要运行足够长的时间后， 系统将进入稳定状态； （7）排队系统中，顾客等待时间的分布不受排队服务规则的影响； （8）在顾客到达及机构服务时间的分布相同的情况下，对容量有限的排队系统，顾客的 平均等待时间少于允许队长无限的系统； （9）在顾客到达分布相同的情况下，顾客的平均等待时间同服务时间分布的方差大小有 关，当服务时间分布的方差越大时，顾客的平均等待时间就越长； （10）在机器发生故障的概率及工人修复一台机器的时间分布不变的条件下，由1名工人 看管5台机器，或由3名工人联合看管15台机器时，机器因故障等待工人维修的平均时间不变。 3．某店有一个修理工人，顾客到达过程为Poisson 流，平均每小时3人，修理时间服从负 指数分布，平均需19分钟，求： （1）店内空闲的时间； （2）有4个顾客的概率； （3）至少有一个顾客的概率； （4）店内顾客的平均数； （5）等待服务的顾客数； （6）平均等待修理的时间； （7）一个顾客在店内逗留时间超过15分钟的概率。 4．设有一个医院门诊，只有一个值班医生。病人的到达过程为Poisson 流，平均到达时间间隔为20分钟，诊断时间服从负指数分布，平均需12分钟，求： （1）病人到来不用等待的概率； （2）门诊部内顾客的平均数； （3）病人在门诊部的平均逗留时间； （4）若病人在门诊部内的平均逗留时间超过1小时，则医院方将考虑增加值班医生。问 病人平均到达率为多少时，医院才会增加医生？ 5．某排队系统只有1名服务员，平均每小时有4名顾客到达，到达过程为Poisson 流，，服务时间服从负指数分布，平均需6分钟，由于场地限制，系统内最多不超过3名顾客，求：
第六章决策分析 决策就是人们在从事各种活动过程中所采取的决定或者选择。经济生活中，一项成功的决策可以带来巨大的财富，一项错误的决策会造成巨大的损失。许多决策问题受到不确定性因素的影响，因而需要进行科学的分析，以利于作出正确的决策。决策分析就是分析在各种条件下不同的决策行动的合理性以及在多种可能方案中选择最佳方案的过程。 决策问题通常分为：确定性决策、风险性决策和不确定性决策。 所谓确定性决策就是在决策环境完全确定的情况下进行的决策，因而所作的决策应是合理的。如线性规划问题、需求确定的库存问题等。而风险决策和不确定性决策是在决策环境不完全确定的情况下进行的决策，其中，风险决策对于其面临的自然状态发生的概率，决策者可以预先计算或估计出来；而不确定性决策对于其所面临的自然状态发生的概率，决策者完全不知，只能靠决策者的主观倾向进行决策。 第一节决策分析问题及其一般性描述 一、决策分析问题举例 例6.1 某食品店牛奶的月需求量为25至28箱，每箱牛奶的进价为16元，售价为22元。若牛奶当月为售完，则因过期而每箱损失16元。试制定食品店每月牛奶的订购箱数。 该问题的基本分析可用如下两个表格来描述。 （1）收益（利润） 此处的收益表示利润。食品店在各种决策（订货25～28箱）下的收益如下表。 第六章——1 （2）损失 食品店的损失分两种情况。第一种情况是订货大于需求时，牛奶因过期而损失，损失价值为损失的箱数乘以每箱进价；第二种情况是当需求大于订货量时，因失去获取利润机会的机会损失，其损失值为需求超过订货的箱数乘以每箱利润。食品店在各种决策下的损失如下表。
有了上述表格，就有了关于决策问题的描述。在此基础上，决策者可以根据某种准则来作出自己满意的决策。 值得注意的是，上述两个表格是从不同的角度来描述同一个决策问题。如果是用收益描述决策问题，决策的准则就是收益最大；相反如果是用损失描述决策问题，则决策达到准则为损失最小。 例6.2 某公司需要对某种新产品的批量作出决策。市场对该种产品的需求有三种可能，即需求量大、需求一般和需求量小。现有三种决策方案，即大批量生产、中批量生产和小批量生产。经估算，各行动方案在各种需求的情况下的收益值情况如下表，问哪种行动方案为最好？ 二、决策问题的一般性描述 （一）决策问题的基本要素 从以上两个例子可以总结出，决策问题一般包括三个基本要素：行动方案、自 第六章——2 然状态和损益函数。 首先，任何决策问题都必须具有两个或两个以上的行动方案。显然，只有一个方案就无须决策。行动方案也称方案或决策，通常用Ai（i=1，…，m）表示某一具体的可行方案，用A=｛A1，A2，…，Am｝表示方案集。 其次，任何决策问题，无论采取何种方案，都面临着一种或几种自然状态。自然状态简称状态，也称事件。决策问题中的自然状态是不可控制因素，因而是随机事件。通常用Si（j=1，…，n）表示某一具体的状态，用S=｛S1，S2，…，Sn｝表示状态集。决策问题中，某一确定的时间条件下，各种可能的自然状态只可能出现其中的一种，由概率论的知识可知，各Sj是互斥事件，而所有的Sj构成的集合S是一个必然事件。
运筹学部分课后习题解答P47 用图解法求解线性规划问题 a） 12 12 12 12 min z=23 466 ..424 ,0 x x x x s t x x x x + +≥ ? ? +≥ ? ?≥ ? 解：由图1可知，该问题的可行域为凸集MABCN，且可知线段BA上的点都 为最优解，即该问题有无穷多最优解，这时的最优值为 min 3 z=2303 2 ?+?= P47 用图解法和单纯形法求解线性规划问题 a） 12 12 12 12 max z=10x5x 349 ..528 ,0 x x s t x x x x + +≤ ? ? +≤ ? ?≥ ? < 解：由图1可知，该问题的可行域为凸集OABCO，且可知B点为最优值点， 即 1 12 122 1 349 3 528 2 x x x x x x = ? += ?? ? ?? +== ?? ? ，即最优解为* 3 1, 2 T x ?? = ? ?? 这时的最优值为 max 335 z=1015 22 ?+?=
单纯形法： 原问题化成标准型为 121231241234 max z=10x 5x 349 ..528,,,0x x x s t x x x x x x x +++=?? ++=??≥? j c → 10 5 、 B C B X b 1x 2x 3x 4x 0 3x \ 9 3 4 1 0 0 4x 8 [5] 2 . 0 1 j j C Z - 10 5 0 0 0 3x 21/5 . 0 [14/5] 1 -3/5 10 1x 8/5 1 2/5 0 （ 1/5 j j C Z - 1 0 -2 5 2x 3/2 0 ； 1 5/14 -3/14 10 1x 1 1 0 -1/7 2/7 （ j j C Z - -5/14 -25/14
《管理运筹学》第四版课后习题解析 第6章单纯形法的灵敏度分析与对偶 1．解： （1）c 1≤24 （2）c 2≥6 （3）c s 2≤8 2．解： （1）c 1≥?0.5 （2）?2≤c 3≤0 （3）c s 2≤0.5 3．解： （1）b 1≥250 （2）0≤b 2≤50 （3）0≤b 3≤150 4．解： （1）b 1≥?4 （2）0≤b 2≤10 （3）b 3≥4 5. 解： 最优基矩阵和其逆矩阵分别为：???? ??=1401B ，??? ? ??-=-14011 B ； 最优解变为130321 ===x x x ，，最小值变为-78； 最优解没有变化； 最优解变为2140321 ===x x x ，，，最小值变为-96； 6．解： （1）利润变动范围c 1≤3，故当c 1=2时最优解不变。 （2）根据材料的对偶价格为1判断，此做法有利。 （3）0≤b 2≤45。 （4）最优解不变，故不需要修改生产计划。 （5）此时生产计划不需要修改，因为新的产品计算的检验数为?3小于零，对原生产计划没有影响。 7. 解：
(1)设321,,x x x 为三种食品的实际产量，则该问题的线性规划模型为 ,, 4005132 4505510 35010168 325.2max 321321321321321≥≤++≤++≤++++=x x x x x x x x x x x x x x x z 约束条件： 解得三种食品产量分别为0,75.43321===x x x ，这时厂家获利最大为109.375万元。 (2)如表中所示，工序1对于的对偶价格为0.313万元，由题意每增加10工时可以多获利3.13万元，但是消耗成本为10万元，所以厂家这样做不合算。
第六章 贝叶斯博弈 在这一章主要内容有： 一、豪尔绍尼转换， 二、贝叶斯博弈及贝叶斯纳什均衡， 最后为显示原理。 其中贝叶斯纳什均衡的概念是需要掌握的核心概念。
第一节豪尔绍尼转换 豪尔绍尼转换的想法非常简单，并不复杂，其实质就是将非完全信息造成的不确定性通过概率的方式来加以处理。为了较为形象的理解豪尔绍尼转换，我们还是通过案例加以说明。 例6.1 贝叶斯信用困境 商人2（良商） 商人2（奸商） H C H C H 2，2 0，‐1H 2，2 0，3 商人1 C ‐1，0 1，1 C ‐1，0 1，1 图6-1 贝叶斯信用困境 在贝叶斯信用困境这个博弈中，相当于存在着两个博弈。如果商人1
相信商人2是一个讲诚信的人，他们的纳什均衡为(H, H)和(C, C)。如果商人1相信商人2是一个奸商，那么纳什均衡为(C, C)，但到底哪一个策略组合是整个博弈的纳什均衡显然无法回答。原因在于商人1对商人2不同的信念(Belief)导致了即使是相同的策略，也会出现不同的收益，即在相同的策略组合下，收益具有不确定性。例如(H, C)这个策略组合，对参与者而言就有不同的收益，在商人2诚信的情况下，收益为(0, -1)；在商人2为奸商的情况下，收益则为(0, 3)。收益具有不确定性是所有非完全信息博弈与完全信息博弈相比最重要的差异，非完全信息也正是根据这一点来定义的。其次，图6-2实际上清楚地表明了贝叶斯信用困境所面临的困难，该博弈有两个开始点，在商人1行动的时候，商人1分不清他到底处于那种情况，是处于（商人2）诚信，还是处于（商人2）欺骗。由于该博弈有两个开始点，可以理解
如何走出囚徒困境 目前博弈论的发展正越来越受到各个领域的重视，因为在现实生活中矛盾和冲突总是无所不在，而利用博弈论可以帮助我们很好地解决这些现实生活中的矛盾和冲突问题。由此可见，如何在矛盾和冲突中成功的选择和运用策略是一个很有意义的问题。 一、“囚徒困境“现象描述 囚徒困境是由数学家Tucker提出的，描述的是警方抓住两个合伙犯罪的嫌犯，但却缺乏足够的证据指证他们的罪行，如果其中至少有一人供认犯罪，就能确认罪名成立。为了得到所需的口供，警察将两个嫌疑犯A和B关在两个单独的房间里单独审讯，并告诉他们：如果有一人坦白，坦白者将被无罪释放，不坦白者则将被判刑10年徒刑；如果两人同时认罪，则他们将被各判5年徒.由此得 出囚徒困境得意矩阵： 在“囚徒困境”博奕中，纳什均衡是（坦白，坦白），尽管从总体上看（抵赖，抵赖）是对两个人都有益的结果，但由于不构成纳什均衡，所以不是该博奕的解。给定B坦白的情况下，A的最优战略选择是坦白，AB最优战略的组合（纳什均衡）却不是总体最优的选择。有没有可能其中一个人选择抵赖呢？按照人是理性的假设，没有人会积极地这么做，因为如果对方坦白的话，自己就可能被判刑
10年，理性的人是不会冒这种风险的。事实上如果两人都不坦白，则警方只能将他们都无罪释放，当然这一点警方不会告诉他们。这样看来A和B毫无疑问应该相互合作共同保持沉默，但是并非如此，以A为例，他认为如果自己不坦白而B坦白的话B将会无罪释放，却留下A自己独守牢狱。当然此时如果B也不坦白那情况是最佳的，但A无法确信B在这样的诱惑下能不动心。而在A坦白的情况下，无论B是否坦白，A收到的惩罚都小于前者。因此A最终会选择坦白。同理B也会做出同样的决定，结果就是A、B两人一起坐牢。 囚徒困境说明的是每个人都应该理性地考虑自身利益最大化做出对各自有利的抉择，其结果却会适得其反。即使他们建立同盟，在缺少足够的沟通和信任的情况下这种同盟只会不攻自破。 二、解决“囚徒困境”的方法： 现实生活中的博弈现象很多，只要有竞争的地方就会有博弈就会出现囚徒困境现象。囚徒困境一旦从一次性博弈转变为重复博弈，情况会发生非常大的变化，博弈的结局也就是纳什均衡点可能会完全不同。我们怎样才能走出这种困境这是值得我们深思的问题。 （一）重复多次博弈 该博弈为一个完全信息的静态重复博弈，因为单次的囚徒困境只会导致双方选择纳什均衡，即均不合作。在重复博弈中囚徒们只是有时会走出困境，在每个囚徒贴现值充分大时，以下两种情况可能使得两个囚徒走出困境：其一是博弈重复无限次；其二是引入非对称信息，博弈重复的次数充分大。一次性的博弈最终会因个人利益最大化而陷入囚徒困境；但如果是多次博弈，人们就有了合作的可能性，囚徒困境就可能破解。
第6章训练题 一．基本技能训练 1．已知网络图各段路线所需费用如下图所示，试选择从A 到B 线的最小费用路线，并计算其总的费用。图中A 线和B 线上的数字分别代表相应点的有关费用。 1．3的点止。其总费用为17。 用动态规划方法求解2题至13题。 2．33221max x x x z = 3．2 22211295m ax x x x x z -+-= 3 ,2,1,06321=≥≤++i x x x x i 2 ,1,0521=≥≤+i x x x i 4．2 3 222143min x x x z ++= 5．432163105max x x x x z +++= 3 ,2,1,09321=≥≥i x x x x i 4 ,3,2,1,01110544321=≥≤+++i x x x x x i 且为整数 6．)2(2)-(23m ax 2211x x x x z -+= 7．24232221max x x x x z +++= 2,1,03 21=≥≤+i x x i 且为整数 4 ,3,2,1,010 4321=≥≥+++i x x x x x i 且为整数 8．321854m ax x x x z ++= 9．2 2121567m ax x x x z ++= 3,2,1,011 4136310 31321321=≥≤+≤++≤++i x x x x x x x x x i 且为整数 2 ,1,09310 22121=≥≤-≤+i x x x x x i 10．33222148max x x x z ++= 11．42322 1max x x x x ax z ++= 为整数b i x b x x x i 3 ,2,1,0102321=≥=++ 为实数 ＝a i x x x x x i 4 ,3,2,1,00 14321=≥+++ 2．最优解为：108;3,1,2max 321====z x x x 。
第六章博弈论初步 教学目的和要求：在寡头垄断的市场上，厂商之间的决策是相互影响的，可以用博弈论的有关理论来分析具有相互影响的厂商之间的决策行为。通过本章的学习，学生应该了解博弈论的基本概念，能够运用博弈论的有关理论分析厂商的行为，并且重点掌握古诺模型、斯塔克博格模型、伯特兰模型、价格领导模型等几个有关厂商价格和产量决策的模型。 教学重点与难点：纳什均衡、古诺模型、伯特兰模型、价格领导模型 教学时数：8课时 第一节博弈论和博弈简介 博弈论是研究产业组织的有效方法，著名经济学家泰勒尔说：“正如理性预期使宏观经济学发生革命一样，博弈论广泛而深远地改变了经济学家的思维方式”。 博弈论与传统经济学有关决策理论的区别在于：后者涉及的个人决策，个人效用只依赖于自己的选择，而外在于他人的选择；然而博弈论看来，个人效用不仅依赖于自己的选择，而且依赖于他人的选择。 一、博弈论的基本知识 1.博弈 个人，团体或组织在面对一定的环境条件，在一定的规则下，同时或先后，一次或多次，从各自允许选择的行为或策略中进行选择并加以实施，各自从中取得相应结果的过程。 2.博弈论 英文为Game theory，是研究相互依赖、相互影响的决策主体的理性决策行为以及这些决策的均衡结果的理论。 3.描述博弈的要素 参与人(player)，参与人指的是博弈中选择行动以最大化自己效用的决策主体(可以是个人，也可以是团体)； 行动（actions），行动是指参与人在博弈进程中轮到自己选择时所作的某个具体决策； 信息(information) 信息指的是参与人在博弈中所知道的关于自己以及其他参与人的行动、策略及其得益函数等知识； 策略(strategy) 策略是指参与人选择行动的规则，即在博弈进程中，什么情况下选择什么行动的预先安排； 支付(payoff)函数支付函数是参与人在博弈结束后从博弈中获得的效用，一般是所有参与人的策略或行动的函数，这是每个参与人最关心的东西； 结果(outcome)，结果是指博弈分析者感兴趣的要素的集合，常用支付矩阵或收益矩阵来表示。 均衡(equilibrium) ，均衡是指所有参与人的最优策略或行动的组合 4.博弈的分类
6.4解：设X j = 1 ,设置i 类商品j 状态 ，不设置i 类商品j 状态 i=食品、珠宝、服装、鞋帽、文具；j=商店数量为1,2,3 obj : maxz=20x i +36x 12+45x 13+10x 21+18x 22+21x 23+15x 31 + 26X 32+30X 33+17X 41+28X 42+33X 43+16X 51+18X 52+18X 53 Xu 2x 12 3x 13 乞 3 X 21 2X 22 3X 23 - 3 X 31 2 X 32 3X 33 — 1 X 41 ' 2X 42 ' 3X 43 — 1 x 41 2X 42 3X 43 辽 3 X 51 ' 2X 52 ' 3X 53 一 1 X 51 2 X 52 3X 53 - 3 1000 (x 11 2X 12 3X 13) +500 (x 21 2X 22 3X 23 ) +900 (x 31 2x 32 3x 33) + 700 (X 41 2X 42 3X 43) +600(X 51 2 X 52 3 x 53 工 10000, X 21 ' X 22 ' X 23 =1 X 31 X 32 X 33 =1 X 41 X 42 X 43 = 1 X 51 ' X 52 ' X 53 = 1 X j =0 或 1 s.t. x 11 - 2x 12 3x 13 -1 X 21 2x 22 3x 23 亠 1 '2X 32 ' 3X 33 - 3 X 11 X 12 X 13 =1
利用QM软件求解，可得下图: 6.7解：设X j = 1,表示第i个电站j年建设 0 ，表示第i个电站j年不建设 i=1,2,3,4;j=1,2,3,4,5 minZ =200(X ll+X l2+X l3+X l4+X l5)+160(X 2l+X22+X23+X24+X25)+180(X 31+X32+X33+X 34+X35) + 140(X 41 +X42+X43+X44+X45)+15(5X 11+4X12+3X13+2X14+X15)+ 8(5X 21+4X22+3X23+2 X24 + X25)+13(5X 31 +4X32 + 3X33 +2X34+X35) +6(5X 41 +4X42 + 3X43 +2X44+X45) s.t 50+70X 11+50X21+60X31+40X41 > 100 50+70 (X11+X12) +50( X21+X22) +60( X31+X32) +40( X41+X42)》120 50+70 (X11+X12+X13)+50(X21+X22+X23) +60(x31 +X32+X33)+40(X 41+X42+X43) > 140 50+ 70(X11+X12+X13+X14) + 50(X 21 +X22+X23+X24) +60(X 31 +X32+X33+X34)+40(X 41 +X42 +X43+X44)》160
第六章作业的参考答案 233P 6. 证明：若树T 的最大次k ≥，则T 至少有k 个次为1的点。 证：任给树)E ,N (T =，因为 T 连通，所以 T 中每个点的次至少为1，即任给N i ∈，都有1)i (d ≥。 （反证）设T 中次为1的点有m 个，k m <。则 )1|(|2)1|(|2)1|(|2)(->-+-=+--+≥∑∈N m k N k m N m i d N i 另一方面， ),1|(|2||2)(-==∑∈N E i d N i 矛盾。所以，k m ≥。即，T 至少有k 个次为1的点。 233P 7、用Kruskal 算法求下图所示网络中的最小树。 解：
上图中粗线部分为所求的最小树，其权为1+2+3+5=11. 233P 9、用Dijkstra 算法求下图所示有向网络中自点①到其它各点的最短有向路.
解：
上图中粗线部分为点①到其它各点的最短有向路. 233P 10、用Ford-Fulkerson 算法求下图所示有向网络中从①到⑥的最大流。 解： ② 1 ④ 3 2 4 3 ① 2 ⑥ 3 3 ③ 4 ⑤ ② 1,0 ④ 3,0 2,0 4,0 3,0 ① 2,0 ⑥ 3,0 3,0 ③ 4,0 ⑤
(+1,3) ② 1,0 ④ 3,0 2,0 4,0 3,0 (+5,3) ① 2,0 ⑥ 3,0 3,0 ③ 4,0 ⑤ (+1,3) (+3,3) (+1,3) (+2,1) ② 1,0 ④ 3,0 2,0 4,0 3,0 (+4,1) ① 2,0 ⑥ 3,3 3,3 ③ 4,3 ⑤ (+1,2) ② 1,1 ④ 3,1 2,0 4,0 3,1 ① 2,0 ⑥ 3,3 3,3 ③ 4,3 ⑤ ),(∞- ),(∞- ),(∞- 所以，最大流的值为4.
6.4解：设x ij = 1，设置i 类商品j 状态 0，不设置i 类商品j 状态 i=食品、珠宝、服装、鞋帽、文具；j=商店数量为1,2,3 obj ：maxz=20x 11+36x 12+45x 13+10x 21+18x 22+21x 23+15x 31+ 26x 32+30x 33+17x 41+28x 42+33x 43+16x 51+18x 52+18x 53 s.t. 13121132x x x ++1≥ , 13121132x x x ++3≤ , 23222132x x x ++1≥ , 23222132x x x ++3≤ , 33323132x x x ++1≥ , 33323132x x x ++3≤ , 43424132x x x ++1≥ , 43424132x x x ++3≤ , 53525132x x x ++1≥ , 53525132x x x ++3≤ , 1000?(13121132x x x ++) +500?(23222132x x x ++) +900?(33323132x x x ++) + 700?(43424132x x x ++) +600?(53525132x x x ++)10000≤, 1131211=++x x x , 1232221=++x x x , 1333231=++x x x , 1434241=++x x x , 1535251=++x x x ,
x=0或1 ij 利用QM软件求解，可得下图： 6.7解：设x ij= 1, 表示第i个电站j年建设 0，表示第i个电站j年不建设 i=1,2,3,4;j=1,2,3,4,5 minz=200(x11+x12+x13+x14+x15)+160(x21+x22+x23+x24+x25)+180(x31+x32+x33+x ) 34+x35 +140(x41+x42+x43+x44+x45)+15(5x11+4x12+3x13+2x14+x15)+8(5x21+4x22+3x23+2 x24+ x25)+13(5x31+4x32+3x33+2x34+x35)+6(5x41+4x42+3x43+2x44+x45) s.t 50+70x11+50x21+60x31+40x41≥100 50+70（x11+x12）+50（x21+x22）+60（x31+x32）+40（x41+x42）≥120 50+70（x11+x12+x13）+50（x21+x22+x23）+60(x31+x32+x33)+40(x41+x42+x43)≥140 50+70(x11+x12+x13+x14)+50(x21+x22+x23+x24)+60(x31+x32+x33+x34)+40(x41+x42 +x43+x44)≥160
管理运筹学第四版第六章习题答案
6.4解：设x ij = 1，设置i 类商品j 状态 0，不设置i 类商品j 状态 i=食品、珠宝、服装、鞋帽、文具；j=商店数量为1,2,3 obj ：maxz=20x 11+36x 12+45x 13+10x 21+18x 22+21x 23+15x 31+ 26x 32+30x 33+17x 41+28x 42+33x 43+16x 51+18x 52+18x 53 s.t. 13121132x x x ++1≥ , 13121132x x x ++3≤ , 23222132x x x ++1≥ , 23222132x x x ++3≤ , 33323132x x x ++1≥ , 33323132x x x ++3≤ , 43424132x x x ++1≥ , 43424132x x x ++3≤ , 53525132x x x ++1≥ , 53525132x x x ++3≤ , 1000?(13121132x x x ++) +500?(23222132x x x ++) +900?(33323132x x x ++) + 700?(43424132x x x ++) +600?(53525132x x x ++)10000≤, 1131211=++x x x , 1232221=++x x x , 1333231=++x x x , 1434241=++x x x ,
1535251=++x x x , ij x =0或1 利用QM 软件求解，可得下图： 6.7解：设x ij = 1, 表示第i 个电站j 年建设 0，表示第i 个电站j 年不建设 i=1,2,3,4;j=1,2,3,4,5 minz=200(x 11+x 12+x 13+x 14+x 15)+160(x 21+x 22+x 23+x 24+x 25)+180(x 31+x 32+x 33+x 34+x 35) +140(x 41+x 42+x 43+x 44+x 45)+15(5x 11+4x 12+3x 13+2x 14+x 15)+8(5x 21+4x 22+3x 23+2x 24+ x 25)+13(5x 31+4x 32+3x 33+2x 34+x 35)+6(5x 41+4x 42+3x 43+2x 44+x 45) s.t 50+70x 11+50x 21+60x 31+40x 41≥100 50+70（x 11+x 12）+50（x 21+x 22）+60（x 31+x 32）+40（x 41+x 42）≥120 50+70（x 11+x 12+x 13）+50（x 21+x 22+x 23） +60(x 31+x 32+x 33)+40(x 41+x 42+x 43)≥140