解:首先设每百公里所用费用相同,求v1到v6的费用最少,既求v1到v6的最短路线。为了方便计算,先作出该网络的距离矩阵,如下:
??v?1?v2?L??v3?v4??v5?v?6v1v20552??0159v3210810?v4???v6????59???810?? 025??202?520???v5?(0)设W?v1??0,T?v???,vj?s??v2,v3,v4,v5,v6?, (1)第一次迭代
①计算Tvj,j?2,3,4,5,6如下
??T?v2??min?T?v2?,W?v1??w12??min??,0?5??5 T?v3??min?T?v3?,W?v1??w13??min??,0?2??2 T?v4??min?T?v4?,W?v1??w14??min??,0????? T?v5???,T?v6???
②取
min?T?v???2?T?v?,令W?v??T?v??2
j3vj?s33③由于k?3??n?6?,令s??v2,v4,v5,v6?,i?3转(1) 第二次迭代:
①算Tvj,j?2,4,5,6如下
???T?v2??min?T?v2?,W?v3??w23??min?5,2?1??3
26
T?v4??min?T?v4?,W?v3??w34??min?8,2?8??8 T?v5??min?T?v5?,W?v3??w35??min?10,2?10??10 T?v6??min?T?v6?,W?v3??w36??min??,2?????
②取minTvj?vj?s?????3?T?v?令W?v??T?v??3
222③由于k?2??n?6?,令s??v4,v5,v6?i?2转(1) 第三次迭代:
①算Tvj,j?4,5,6如下
???T?v4??min?T?v4?,W?v2??w24??min?8,3?5??8 T?v5??min?T?v5?,W?v2??w25??min?10,3?9??10 T?v6???
Tvj②取min?vj?s?????8?T?v?,W?v??T?v??8
444③由于k?4??n?6?,令s??v5,v6?i?4转(1) 第四次迭代:
①算Tvj,j?5,6如下
???T?v5??min?T?v5?,W?v4??w45??min?10,2?8??10 T?v6??min?T?v6?,W?v4??w46??min??,8?5??13
Tvj②取min?vj?s?????10?T?v?,W?v??T?v??10
555③由于k?5??n?6?,令s??v6?转(1) 第五次迭代:
①算Tvj,j?6如下
???T?v6??min?T?v6?,W?v5??w56??min?13,10?2??12
②由于k?6?n。因此已找到v1到v6的最短距离为12。计算结束。 找最短路线:逆向追踪得v1?v3?v2?v4?v5?v6
27
最短距离为12,即从城市v1到城市v6的距离最短,即费用最省。
练习题：
9.5 用Dijkstra标号法求下图中始点到各顶点的最短路，弧上数字为距离：
v3 3 v5
1 5 4 v1 2 4
v2 2 v4
9.9 已知有6个村子，相互间道路的距离如下图所示，拟合建一所小学。已知A处有小学生50人，B处40人，C处60人，D处20人，E处70人，F处90人，问小学应建在哪一个村子，使学生上学最方便（走的总路程最短）。
B· 6 ·D 2 8 6 A· 4 1 ·F 7 1 3
C · 3 ·E 9.6 最短路问题：某公司使用一种设备，此设备在一定年限内随着时间的推移逐渐损坏。每年购买价格和不同年限的维修使用费如下表所示。假定公司在第一年开始时必须购买一台此设备，请建立此问题的网络图，确定设备更新方案，使维修费和新设备购置费的总数最小。说明解决思路和方法，不必求解。
年份 1 2 3 4 5 价格 20 21 23 24 26
使用年限 0－1 1－2 2－3 3－4 4－5 费用 8 13 19 23 30
9.4. 请用标号法求下图所示的最短路问题，弧上数字为距离：
2 1 4 1 7 1 2 3 6 4 6 3 5 3 1 5 六、最小支撑树问题
最小支撑树的生成方法
避圈法：在图中取一条最小权的边，以后每一步中，总从未被选取的边中选一条权最小的边，并使之与已选取的边不构成圈（每一步中，如果有两条或两条以上的边都是最小权的边，则从中任选一条）。
破圈法：任取一个圈，从圈中去掉一条权最大的边（如果有两条或两条以上的边都是权最大的边，则任意去掉其中一条）。在余下的图中，重复这个步骤，直到得到一个不含圈的图为止，这时的图便是最小树。
28
七、不9.2 求下图的最小生成树和最大生成树：
V1 6 V2 6 6 2 2
V6 7 V7 3 V3
8 3 4 3
V5 1 V4
七、确定型决策问题
1、某工厂为增加生产，有两方案可选：引进生产线和现有设备更新改造。据预测，引进生产线需一次投资150万元，更新改造需一次投资50万元。又对未来市场进行预测，在未来3年内，产品畅销的概率为0.6；产品销路不好的概率为0.4。若引进生产线，产品畅销时，每年可获利100万元；产品销路不好时，每年可获利10万元。若对现有设备进行更新改造，产品畅销时，每年可获利80万元；产品销路不好时，每年可获利30万元，问该企业应选择哪个方案。
2、根据下表资料，用乐观法、悲观法、后悔值法进行决策。 X Y V 高需求Y1 20 9 4 状态变量 中需求Y2 1 8 4 低需求Y3 -6 0 4 第一方案X1 第二方案X2 第三方案X3 3、某企业生产一种产品，市场预测结果表明有三种可能：销路好，销路一般，销路差。备选取方案三个，一是扩建，二是技术改造，三是维持现状。各方案在不同自然状态下的损益值如下表。
1．选用乐观决策法、悲观决策法、最小后悔值法、等概率法进行决策。
2．若已知销路好的概率为0.5，销路一般为0.3，销路差为0.2，试用期望值法、决策树法决策。
方案 销路好 A：扩 建 B：技术改造 C：维持现状
损益值 销路一般 90 80 40 29 销路差 -70 -50 -20 200 150 90
3、 某决策问题，其决策信息如下表 效益（万元） 状 态 N1 50 30 10 N2 20 25 10 N3 -20 -10 10 方 案 S1 S2 S3 （1）用悲观主义决策标准求最佳方案； （2）用乐观主义决策准则求最佳方案； （3）用等可能性决策准则求最佳方案；
（4）令乐观系数α＝0.4，用折衷主义决策准则求最佳方案； （5）用后悔值准则求最佳方案。
4、某厂自产自销一种产品，每箱成本30元，售价80元，但当天卖不掉的产品要报废。该厂去年90天中的日销售量记录表明，有18天售出100箱，有36天售出110箱，有27天售出120箱，有9天售出130箱。问该厂今年每天应当生产多少箱可获利最大。
5、某地方书店希望订购最新出版的好的图书。根据以往经验，新书的销售量可能为50，100，150或200本。假定每本新书的订购价为4元，销售价为6元，剩书的处理价为每本2元。要求：
(a)建立损益矩阵；
(b)分别用悲观法、乐观法及等可能法决定该书店应订购的新书数字； (c)建立后悔矩阵，并用后悔值法决定书店应订购的新书数。
八、风险性决策问题（决策树）
例题：设某厂进行生产能力决策。根据市场预测可能有好、中、坏三种自然状态，市场形势好，年销售量可达１０万件，市场形势中等时，年销售量可达８万件，市场形势差时，年销售量只有５万件，其概率分别为0.3，0.5，0.2 ，与之相对应，生产能力可有年产１０万，８万，５万件三种方案。年产１０万件时，单件成本为６元，但如果卖不出去，则未卖出的产品就积压报废，其成本由已销产品承担。年产８万件时，单件成本为７元，年产５万件时，因规模更小，成本增大，每件为８元，单价预计为１０元。
试问：应当选择何种方案？
解：第一步：计算各种生产方案在不同自然状态下的条件损益值
方案１，年产１０万件，其条件损益值： 好：10×10-10×6=40万元 中：8×10-10×6=20万元 差：5×10-10×6=-10万元 方案２，年产８万件，其条件损益值： 好和中：8×10-8×7=24万元 差：5×10-8×7=-6万元
30