2017年南京师范大学F161运筹学复试实战预测五套卷
● 摘要
一、简答题
1． 简述求解最小费用最大流的赋权网络设置方法。
【答案】解:对网络G=（ V ，E ，C ，d ），有可行流f ，保持原网络各点， 每条边用两条方向相反的有向边代替，各边的权
②当边（vj 名）为原来G 中边（vi ，vj ）的反向边，令
2． 简述常用的不确定型决策准则。
【答案】不确定性决策是指决策者对将发生结果的概率一无所知，只能凭决策者的主观倾向进行决策，适用于对 概率判断缺乏信心，对事情做出简单的估计。。不确定性决策由决策者的主 观态度不同基本可分为四种准则:悲 观主义准则、乐观主义准则、等可能性准则、最小机会准则。
（l ）悲观主义决策准则:行中取min ，再取max 。 （2）乐观主义决策准则:行中取max ，再取max 。
（3）等可能性准则:先求各策略的收益期望值，再从中取max 。 （4）最小机会损失准则:
机会损失矩阵:每一列的值为列中最大的数分别减去其他的数（自己则变为0，其他的值全大于等于0），即
（5）折衷主义决策准则
其中a （最小收益值。
然后选择
）为乐观系数，
，
。分别表示第i 个策略可能得到的最大收益值与
。
按如下规则:
二、计算题
3． 企业A 是位于南京路的一家专供某类零部件的加工企业，生产产品DXF ，正常生产条件下可生产12百件/天，每百件定价8万元。根据供货合同，需按9百件/天供货。存贮费每百件0.16万元/天，允许缺货，缺货 费为每件0.65万元/天，每次生产准备费为80万元。要求:
（l ）绘出存储状态图，并说明存储过程;
（2）求最优存储策略。 【答案】由题意可知，
最优存贮策略各参数为: 最优存贮周期:经济生产批量:生产时间:最大存贮量:最大缺货量:平均总费用为:存贮状态图如图所示。
图
4． 有10个城市，它们在坐标系中的位置如表所示，试完成以下工作。
（l ）用C 一W 节约算法求出经过每个城市一次且仅一次的一条最短线路。
（2）用Norback 和Love 提出的几何法，求出经过上述每个城市一次且仅一次的最短线路。 （3）比较上述两种方法得出的结果，并设计一种启发式方法，对上述较差的结果进行改进。
表
【答案】（l ）计算各点对之间的欧氏距离c ij ，计算结果如表所示。
表
取城市1为基点，利用公式如表所示。
。计算将弧表
插入线路中的节约值，
按节约值由大到小的顺序，对每条弧加以考查，看能否将其插入到线路中。若能将其插入，就对线路做相应的改变，由此得到插入弧顺序为
（9，10）→（7，10）→（8，9）→（2，7）→（2，5）→（6，8）→（3，5）→（4，6） 其线路为 l →3→5→2→7→10→9→8→6→4→l
线路总长度为14.42+3.61+7.07+11.18+4.12+2.83+7+5+8+8.06=71.29
（2）几何法:开始时构成闭凸包1→2→7→10→8→6→1，如图中的实线所示。
图
然后运用几何运算步骤进行反复迭代，得到最终哈密尔顿回路（如图中加记号“‖”所示的线