练习题习题课答案.pdfVIP

1.一个硬币正面为币值，为国徽图案。将这个硬币随机掷10次，如果用树

图表示所有可能出现的结果，试问这个树图有多少个节点，多少条边。

正反

...……...……...……...……

2101111

解：有1+2+2++2=2−1个节点，2−2条边

2.如下图所示，要铺设一条从S到T的管道，各箭线旁边的数字为相应的两点间

的距离。

甲，乙，丙三个人讨论用什么样的运筹学方法求解。甲提出用dijkstra算法求从

S到T的最短路。乙提出这个问题可以通过建立整数规划的模型求解，但丙和甲

对此持怀疑态度;丙设想先找出图中的最小支撑树，由树图中任意两点间存在唯

一的链，故最小支撑树中的从S到T的链即为从S到T的铺设管道的最短路，对

此甲和乙不同意。试你对甲，乙，丙三个人所提方法的评论意见，并说明

同意或的理由。如果同意，试分析如何建立模型并求解。

12

c

2

5

g

5

sbt

h2

1

af

10

11

1234

解：甲的建议是一致同意的，乙的建议也是可行的，可以用整数规划求解，

丙的建议不可行

答案：最短路线是s→b→d→g→t，相应的最短距离是19.

3.有八种化学药品A，B，C，D，P，R，S，T要放进贮藏室保管。出于安全，

下列各组药品不能贮在同一室内：A-R，A-C，A-T，R-P，P-S，S-T，T-B，B-D，

D-C，R-S，R-B，P-D，S-C，S-D，问贮藏这八种药品至少需要多少间贮藏室。

解：用八个点分别代表八种药品，哪两种药品不能贮于同一室内，就在代表它

们的两个点间连一条边。其中S，P，R两两相邻，必须占用3间贮藏室。与S

不相邻，彼此也不相邻的有A，B点，可与S贮于一室。类似可推出此题最少需

要3间贮藏室。(不与黑线重合)

A

TB

SC

R

D

P

4.已知问题的单位运价表及最优方案表分别如表所示，试分析：

（1）从A2到B2的单位运价C22在什么范围内变化时，最优调运方案可保持不

变？

（2）从A2到B4的单位运价C24变为何值时，将有无限多调运方案。除表所示

之外，再写出另外两个最优调运方案。

单位运价表

销地

产地