《运筹学》-课程实践S2

课程实践S2实验与案例分析学习目标通过本课程实践S2的学习，进一步了解运筹学相关方向的意义、认识运筹学应用的特点、性质和关键，体会运筹学应用的重要意义和发展前景。运筹学是一门实践性很强的基础性应用学科，它主要是将实践中经济、军事、生产、管理、组织等事件中出现的一些带有普遍性的运筹问题加以提炼，然后利用科学方法进行分析、求解等。为了更好地引导读者认识运筹学事件，提高应用水平和能力，下面对本教材第6~11章内容的实验与实践提出系统的建议。上一页返回下一页S2.1整数规划问题S2.1.1实验与实践

(1)学习并掌握一种用于求解整数规划的计算机应用软件。

(2)体会并掌握整数规划建模的特点，特别是灵活掌握0一1变量的使用，分析在第2章习题2.8中用线性规划建模时的困惑，并讨论如何用整数规划来建模。

(3)分组制订实践调研计划，收集数据，分析、讨论整数规划的实践应用领域和模式特征。

(4)对S2.1.2的案例分组进行讨论、分析，计算结果，并组织在班内介绍思路和计算情况。

(5)每一小组在(3)的基础上，结合实际编写一个案例并进行分析、求解，讨论解的过程及实践意义。下一页返回上一页S2.1整数规划问题S2.1.2案例建模与分析例S2.1京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置Aj(j=1,2,3,…,10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定:

在东区，由A1，A2，A3三个点中至多选择两个。在西区，由A4,A5两个点中至少选一个。在南区，由A6,A7两个点中至少选一个。在北区，由A8,A9,A10三个点中至少选两个。

A各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况如表S2-1所示。但投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最大?上一页下一页返回S2.1整数规划问题解设0-1变量xi=1(Ai点被选用)或0(Ai点被选用)。这样可建立如下的数学模型:上一页下一页返回S2.1整数规划问题

例S2.2高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表S2-2所示。不考虑固定费用，每种容器售出一只所得的利润分别为4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300人月，机器有100台月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用:小号是100万元，中号为150万元，大号为200万元。现在要制订一个生产计划，使获得的利润为最大。解设x1,x2,x3分别为小号容器、中号容器和大号容器的生产数量。各种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种性质，设yi=1(当生产第i种容器，即xi>0时)或0(当不生产第i种容器，即xi=0时)，引入约束xi≤Myi

，i=1,2,3,M充分大，以保证当yi=0时，xi=0。上一页下一页返回S2.1整数规划问题数学模型:上一页下一页返回S2.1整数规划问题例S2.3某企业在A1,地已有一个工厂，其产品的生产能力为3万箱，为了扩大生产，打算在A2,A3，A4,A5地中再选择几个地方建厂。已知在A2,A3，A4,A5地建厂的固定成本分别为17.5万元、30万元、37.5万元、50万元，另外，A1

产量及A2,A3，A4,A5建成厂后的产量、销地的销量，以及产地到销地B1，B2，B3的单位运价(每万箱运费)如表S2-3所示。问:在哪几个地方建厂才能在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小？解设xij为从Ai运往Bj的运输量(单位:万箱)，yi=1(当Ai被选中时)或0(当Ai没被选中时)。上一页下一页返回S2.1整数规划问题上一页下一页返回S2.1整数规划问题

例S2.4某公司现有资金1000万元，准备在今后5年内考虑对以下4个项目进行投资，已知:

项目A:每年年初均可投资，于次年年末可回收本利115%，但要求第1年投资最低金额为400万元，第2、第3、第4年不限。项目B:可在第3年年初投资，到第5年年末能回收本利128%，但规定如果投资，则最低投资金额为300万元，最高金额为500万元。项目C:可在第2年年初投资，到第5年年末能回收本利140%，但规定若投资，其投资额或为200万元或为400万元或为600万元或为800万元。项目D:每年年初均可购买公债，于当年年末归还，并加利息6%，此项投资金额不限。考虑该公司应如何确定对这些项目的每年投资额，使到第5年年末拥有的资金本利总额最大?上一页下一页返回S2.1整数规划问题

解设xij表示第i年年初给项目j(j=1,2,3,4分别代表项目A,B,C,D)的投资额。再设y11为0-1变量，规定取1时代表第1年投资A项目，否则取0;设yi2为0-1变量，规定取1时表示第i年(i=1,2,3,4,5)给B项目投资，否则取0。设y23是非负整数变量，并规定:第2年投资C项目为800万元、600万元、400万元、200万元，不投资C项目时，分别取值为4,3,2,1,0，即x23=200y23。由此，我们可以得到变量表如表S2-4所示。对约束条件的分析:

第1年:年初有1000万元，由于D项目在当年年末即可收回投资，故第一年年初应把全部资金投出去，于是x11+x14=100;

第2年:项目A次年年末才可收回投资，故第2年年初的资金为1.06x14,于是上一页下一页返回S2.1整数规划问题第3年:年初的资金为1.15x11+1.06x24，于是第4年:年初的资金为1.15x21+1.06x34，于是第5年:年初的资金为1.15x31+1.06x44，于是关于项目A的投资额规定，可采用两个约束:x11≥400y11,x11≤1000y11,其中1000是足够大的数。可以保证当y11=0时，x11=0;当y11=1时，x11≥40000。上一页下一页返回S2.1整数规划问题

关于项目B的投资额规定，可以采用两个约束:x32≥300y32和x32≤500y32,以保证当y32=0时，x32=0;当y32=1时，500≥x32≥300。关于项目C的投资额规定，按照前面已讨论的:x23=200y23，y23=0,1,2,3,4。关于目标函数:

问题要求考虑第5年年末的本利回收额，即可以得到混合整数规划模型:上一页下一页返回S2.1整数规划问题上一页返回S2.2动态规划问题S2.2.1实验与实践

(1)学习并掌握求解动态规划的基本思路和主要步骤。

(2)体会并掌握动态规划建模的特点，求解基本方程的步骤(以逆序求解为重点)。

(3)分组制订实践调研计划，收集数据，分析、讨论动态规划的实践应用领域和模式特征。

(4)选择S2.2.2的案例进行分组讨论、分析，计算结果，并组织在班内介绍思路和计算情况。

(5)每一小组在(3)的基础上，结合实际编写一个案例并对其进行分析、求解，讨论解的过程及实践意义。下一页返回S2.2动态规划问题S2.2.2案例建模与分析例S2.5某企业准备资金600万元，计划对A,B,C三个项目进行投资，每个项目至少投资100万元。投资以100万元为单位，各项目的投资效益与投入该项目的资金有关。三个项目A,B,C的投资效益和投入资金的关系如表S2-5所示。问:如何对三个项目进行投资分配，使总投资效益最大?解第一步:建立动态规划模型。阶段k:每投资一个项目就作为一个阶段。状态变量xk:考虑投资第k个项目前的资金数。决策变量dk:第k个项目的投资资金数。上一页下一页返回S2.2动态规划问题决策允许集合Dk: 。状态转移方程: 。阶段指标:vk(xk,dk)如表中所示。递推方程: ，终端条件:.f4(x4)=0。第二步:递推求解动态规划基本方程。上一页下一页返回S2.2动态规划问题上一页下一页返回S2.2动态规划问题上一页下一页返回S2.2动态规划问题上一页下一页返回S2.2动态规划问题

得到最优值为f1(x1)=990

第三步:回溯求最优策略。最优解为x1=600,d1*=400，x2-=x1-d1=200,d2*=100，x3=x2-d2*=100,d3=100，x34=x3-d3=0，即项目A投资400万元，项目B投资100万元，项目C投资100万元，最大效益为99万元。例S2.6某公司有资金10万元，若投资于项目i(i=1,2,3)的投资额为xi时，其收益分别为g1(x1)=4x1，g2(x2)=9x2，g3(x3)=2x32，问:应如何分配投资数额才能使总收益最大?

解这是一个与时间无明显关系的静态最优化问题，容易建立非线性静态规划模型:上一页下一页返回S2.2动态规划问题

为了应用动态规划方法求解，我们可以人为地赋予它“时段”的概念:给投资项目排序，首先考虑对项目1投资，然后考虑对项目2投资，……，即把问题划分为3个阶段，每个阶段只决定对一个项目应投资的金额。这样把一个含有3个变量的问题转化为一个3阶段决策过程。下面的关键问题是如何正确选择状态变量，使各后部子过程之间具有递推关系。通常可以把决策变量。、定为原静态问题中的变量xk，即设状态变量和决策变量有密切关系，状态变量一般为累计量或随递推过程变化的量。这里可以把每阶段可供使用的资金定为状态变量sk，初始状态s1=10。u1为分配于第一种项目的资金数，则当第1阶段(k=1)时，有上一页下一页返回S2.2动态规划问题第2阶段(k=2)时，状态变量s2为余下可投资于其余两个项目的资金数，即一般地，第k段时于是有:

第一步:动态规划建模。阶段k:本例中取1,2,3。状态变量sk:第k段可以投资于第k项到第3个(最后一个)项目的资金数。决策变量xk:决定给第k个项目投资的资金数。上一页下一页返回S2.2动态规划问题状态转移方程:阶段指标函数:最优指标函数fk(sk)当可投资金数为sk时，投资第k项到第3项所得的最大收益数。基本方程:上一页下一页返回S2.2动态规划问题

第二步:递推求解动态规划基本方程。k=3时，这是一个简单的函数求极值问题，易知当x3*=s3时，取得极大值2s32，即k=2时,上一页下一页返回S2.2动态规划问题这是一个非线性规划问题。令用经典解析方法求其极值点。由解得而上一页下一页返回S2.2动态规划问题所以 x2=s2=-9/4是极小点,极大值只可能在[0,s2]端点取得:当f2(0)=f2(s2)时，解得s2=9/2。当s2>9/2时，f2(0)>f2(s2),此时x2*=0;当s2<9/2时，f2(0)<f2(s2),此时x2*=s2;k=1时,考虑上述的两种可能当f2(s2)=9s2时，上一页下一页返回S2.2动态规划问题但此时 与s2<9/2矛盾，所以舍去。当 时，令由解得而 上一页下一页返回S2.2动态规划问题所以 是极小点。极大值只可能在[0,10]端点取得。比较[0,10]两个端点，x1=0时，f1(10)=200;x1=10时，f1(10)=40。所以f1(10)=200就是所求的最大利益。于是，x1*=0。第三步:回溯求最优策略。再由状态转移方程回溯(顺推),因为s2>9/2，所以最优投资方案为全部资金投于第3个项目，可得最大收益200万元。上一页下一页返回S2.2动态规划问题例S2.7有某种机床，可以在高低两种不同的负荷下进行生产，在高负荷下生产时，产品的年产量为g，与年初投入生产的机床数量u1，的关系为g=g(u1)=8u1，这时，年终机床完好台数将为au1,(a为机床完好率，0<a<1，设a=0.7)。在低负荷下生产时，产品的年产量为h，和投入生产的机床数量u2的关系为h=h(u2)-5u2，相应的机床完好率为b(0<b<1，设b=0.9}，一般情况下a<b。假设某厂开始有x1=1000台完好的机床，现要制订一个5年生产计划，问:每年开始时应如何重新分配完好的机床在两种不同的负荷下生产的数量，使在5年内产品的总产量最高?上一页下一页返回S2.2动态规划问题解根据题意，本题的决策允许集合应该是一个整数集合，但由于决策允许集合中可取的决策数量很大，一一列举计算量很大，不妨认为状态变量和决策变量都是连续的，得到最优解后，再作取整处理。第一步:动态规划建模。阶段:设阶段变量k表示年度，因此，阶段总数n=5。状态变量sk:表示第k年度初拥有的完好机床台数，同时也是第k-1年度末时的完好机床数量。决策变量uk:表示第k年度中分配于高负荷下生产的机床台数。于是sk-uk便为该年度中分配于低负荷下生产的机床台数。在第k阶段的允许决策集合为 。上一页下一页返回S2.2动态规划问题

这里sk与uk

均取连续变量，当它们有非整数数值时，可以这样理解:sk=0.6时，表示一台机器在第k年度中正常工作的时间只占6/10;uk=0.4时，表示一台机床在第k年度只有4/10的时间在高负荷下工作。状态转移方程:阶段指标函数:设 为第k年度的产量，则动态规划基本方程:

令fk(sk)表示由第k年的状态sk出发采取最优分配方案到第5年度结束这段时间的产品产量，根据最优化原理有以下递推关系:上一页下一页返回S2.2动态规划问题第二步:递推求解动态规划基本方程。当k=5时，有显然，当u5*=s5时,f5(s5)有最大值，相应的有f5(s5)=8s5。当k=4时,有上一页下一页返回S2.2动态规划问题当u4*=s4时,f4(s4)有最大值，相应的有f4(s4)=13.6s4。当k=3时,有当u3*=s3时,f3(s3)有最大值，相应的有f3(s3)=17.55s3。当k=2时,有上一页下一页返回S2.2动态规划问题此时，当取u2*=0时有最大值，即f2(s2)=20.8s2

，其中

当k=1时，有此时，当取u1*=0时有最大值，即f1(s1)=23.7s1

，因为s1=1000，故f1(s1)=23700。第三步:回溯求最优策略。按照上述计算顺序寻踪得到下述计算结果:上一页下一页返回S2.2动态规划问题上面所讨论的最优决策过程是始端状态s1固定，终端状态s6自由，如果终端也附加上一定的约束条件，那么计算结果将会与之有所差别。上一页下一页返回S2.2动态规划问题

例S2.8进一步考虑例S2.7，若规定在第5个年度结束时，完好的机床数量为500台(上面只有278台)，问应该如何安排5年的生产，使之在满足这一终端要求的情况下产量最高？解在上例分析的基础上，注意由状态转移方程有于是可以得到显而易见，由于固定了终端的状态s6，第五年的决策变量u5的允许决策集合u5(s5)也有了约束，上式说明u5(s5)已退化为一个点，即第五年投入高负荷下生产的机床数只能根据上一页下一页返回S2.2动态规划问题作出一种决策，故当k=5时有当k=4时有上一页下一页返回S2.2动态规划问题可知，当u3*=0时,f3(s3)有最大值，相应的有f3(s3)=24.5s3-7500。当k=2时,有此时，当u2*=0时,f2(s2)有最大值，相应的有f2(s2)=27.1s2-7500。当k=1时,有上一页下一页返回S2.2动态规划问题此时，当u1*=0时,f1(s1)有最大值，相应的有f1(s1)=29.4s1-7500。由此可见，为了使下一个五年计划在开始的一年有完好的机床500台，其最优策略应该为:在前4年中，都应该把全部机床投入到低负荷下生产，在第5年，只能把部分完好机床投入到高负荷下生产。根据最优策略，从始端向终端递推计算出各年的状态，即算出每年年初的完好机床台数，因为s1=1000(台)，于是有上一页下一页返回S2.2动态规划问题说明第5年里有452台投入到高负荷下生产，还有656一452=204(台)投入到低负荷下生产，否则不能保证s6=0.7u5+0.9(s5-u5)=500(台)。在上述最优决策下，5年里所得最高产量为可见，附加了终端约束条件以后，其最高产量f1(s1)比终端自由时要低一些。例S2.9有一辆最大货运量为10吨的卡车，用以装载3种货物，每种货物的单位重量及相应单位价值(万元)如表S2-6所示。问:应如何装载可使总价值最大?上一页下一页返回S2.2动态规划问题解设第i种货物装载的件数为xi(i=1,2,3)，则问题可表示为此问题可按前述方式建立动态规划模型，由于决策变量取离散值，所以可以用列表法求解(过程略，读者可以作为练习完成)。下面用解析方法求解，由于已经给出模型，下面可从第二步开始。第二步:递推求解动态规划基本方程。边界条件:f1(s1)=0。当k=3时，上一页下一页返回S2.2动态规划问题由于0≤s3≤10，x3的取值有3种可能:当k=2时，上一页下一页返回S2.2动态规划问题由于0≤s2≤10，x2的取值有3种可能:当k=1时，注意s1=10，s1有4种可能的取值，分别为上一页下一页返回S2.2动态规划问题由于s1=10，则x1*=2，f1(s1)=13。第三步:回溯求最优策略。按照k=1,2,3的顺序求得最优策略:s1=10，x1=2；s2=4，x2=1；s3=0，x3=0；于是，最优解为第一种货物装2件，第二种货物装1件，第三种货物不装，总价值为13万元。例S2.10某企业生产某种产品，每月月初按订货单发货，生产的产品随时入库，由于空间的限制，仓库最多能够贮存产品90000件。在上半年(1~6月)其生产成本(万元/千件)和产品订单的需求数量情况如表S2-7所示。上一页下一页返回S2.2动态规划问题已知上一年年底库存量为40千件，要求6月底库存量仍能够保持40千件。问:如何安排这6个月的生产量，才既能满足各月的订单需求，同时又能使生产成本最低?解第一步:动态规划建模。阶段k:月份(k=1,2，…，7)。状态变量xk:第k个月初(发货以前)的库存量。决策变量dk:第k个月的生产量。决策允许集合:上一页下一页返回S2.2动态规划问题状态转移方程:阶段指标:动态规划基本方程:第二步:递推求解动态规划基本方程。对于k=6，根据状态转移方程因此有上一页下一页返回S2.2动态规划问题是唯一的决策。递推方程为对于k=5，允许决策集合与递推方程为上一页下一页返回S2.2动态规划问题对于k=4，允许决策集合与递推方程为由于 ，故 ，所以上一页下一页返回S2.2动态规划问题对于k=3，允许决策集合与递推方程为上一页下一页返回S2.2动态规划问题对于k=2，允许决策集合与递推方程为上一页下一页返回S2.2动态规划问题对于k=1，允许决策集合与递推方程为由于x1=40，故上一页下一页返回S2.2动态规划问题第三步:回溯求最优策略。将以上结果如表S2-8所示。例S2.11某部门欲采购一批原料，原料价格在5周内可能有所变动，已预测得该种原料今后五周内取不同单价的概率如表S2-9所示。试确定该部门在五周内购进这批原料的最优策略，使采购价格的期望值最小。解本例与前面所讨论的确定型问题不同，状态的转移不能完全确定，而按某种已知的概率分布取值，即属于随机型动态规划问题。第一步:动态规划建模。阶段k:可按采购期限(周)分为5段，k=1,2,3,4,5。上一页下一页返回S2.2动态规划问题

状态变量sk:第k周的原料实际价格。决策变量uk:第k周若采购则uk=1，若不采购则uk=0。另外用SKE:表示:当第k周决定等待，而在以后采购时的采购价格期望值。最优指标函数fk(sk):第k周实际价格为sk时，从第k周至第5周采取最优策略所花费的最低期望价格。动态规划逆序递推关系式为:

为状态集合。上一页下一页返回S2.2动态规划问题第二步:递推求解动态规划基本方程。当k=5时，因为若前4周尚未购买，则无论本周价格如何，该部门都必须购买，所以当k=4时，由于上一页下一页返回S2.2动态规划问题所以当k=3时，由于所以上一页下一页返回S2.2动态规划问题当k=2时，同理所以当k=1时上一页下一页返回S2.2动态规划问题所以最优值即5周的采购最小期望价格为第三步:回溯求最优策略。按照顺序可得到最优采购策略为:若第1、第2、第3周原料价格为500，则立即采购，否则在以后的几周内再采购;若第4周价格为500或600，则立即采购，否则等第五周再采购;而第五周时无论当时价格为多少都必须采购。按照以上策略进行采购，最优期望价格为:525.382元。上一页返回S2.3排队论问题S2.3.1实验与实践

(1)学习并掌握一种用于求解规范性排队论问题的计算机应用软件。由于有些排队问题不能建立规范性模型，需要学习并掌握求解排队论问题的思路和关键步骤。

(2)体会并掌握随机服务系统的特点，特别是灵活掌握通过状态转移速度图及建立状态概率之间关系的方法。

(3)分组制定实践调研计划，收集数据，分析、讨论排队论的实践应用领域和模式特征。

(4)选择S2.3.2的案例进行分组讨论、分析，计算结果，并组织在班内介绍思路和计算情况。

(5)每一小组在(3)的基础上，结合实际编写一个案例并进行分析、求解，讨论解的过程及实践意义。下一页返回S2.3排队论问题S2.3.2案例建模与分析例S2.12某计算中心可带若干个终端，每天工作16小时，用户按泊松流到达，每天平均28人，用户使用终端时间为服从负指数分布的随机变量，平均每人30分钟。计算机中心负责人想设置合适的终端数量。解本题的模型为M/M/c/∞/∞。其中，本题的求解思路:分别讨论c=1,2,3,…,比较各参数，在分析的基础上确定合适的终端数量。上一页下一页返回S2.3排队论问题(1)设置1台终端(c=1)，这时上一页下一页返回S2.3排队论问题(2)设置2台终端(c=2)，这时上一页下一页返回S2.3排队论问题(3)若设置3台终端(c)=3，这时上一页下一页返回S2.3排队论问题结果如表S2-10所示。综合以上对比、分析，从实际出发可知，配置2台终端是合适的。例S2.13对于M/M/1/N/∞模型，试证:并对上式给予直观的解释。解设 ，由M/M/1/N/∞模型的数字特征有上一页下一页返回S2.3排队论问题故当ρ=1时显然当ρ≠1时，上一页下一页返回S2.3排队论问题即则即故上一页下一页返回S2.3排队论问题直观解释:由于系统的容量为N，则有效到达率为有效服务率(有效离去率)为当系统平衡时，有效到达率和有效服务率(有效离去率)应当相等，即例S2.14到某健康检测中心来查体的人平均到达率为λ=48(人次/天)，每次来检查由于请假等原因带来的损失为6元，检查时间服从负指数分布，平均服务率μ为25人次/天，每安排一位医生的服务成本为每天4元，问应安排几位医生(设备)才能使总费用最小？上一页下一页返回S2.3排队论问题解本题的模型为M/M/c/∞/∞。由题意知λ=48,μ=25,bc=4,cw=6。首先须满足又因为而令c=2,3,4将已知数据代入上面两个式子，算得结果如下表所示。上一页下一页返回S2.3排队论问题上一页下一页返回S2.3排队论问题又因为 ，故由及上面的计算结果知0.5817<0.6667<19.9252所以 ，落在区间(0.5817,19.9252)，故c*=3，即安排3位医生可使总费用最小。例S2.15某小城市的火车站有一候车室，经过调查、分析得知，在某段时间里旅客到达服从泊松分布，平均到达速率为260人/小时，每位旅客在候车室内停留的时间服从负指数分布，平均停留时间为0.5小时，问此候车室内平均候车的人数为多少?上一页下一页返回S2.3排队论问题

解分析可以把旅客在候车室的停留看做服务。本问题隐含了候车室能够允许到达的顾客均可在候车室内停留，即不需等待就直接接受服务，表明服务台可充分满足需要。这意味着有无穷多个服务台，于是系统为M/M/∞/∞/∞。参数:λ=260，μ=1/0.5=2首先绘制状态转移速度图:上一页下一页返回S2.3排队论问题其中， ，于是，我们可以得到下列稳态概率关系记 ，代入 ，于是有下面计算平均队长，上一页下一页返回S2.3排队论问题

例S2.16分组制订实践调研计划，选定一个排队系统，如邮局、超市、银行或高速路收费站等。通过收集数据，分析、讨论等完成此项课程实践，并写出研究、分析报告。

(1)记录该排队系统中1个单位时间内(可以是1个小时、半个小时，10分钟等)顾客到达的数量，分多次记录，每次记录1个单位时间，然后计算平均到达率。

(2)记录该排队系统中1个单位时间内(可以是1个小时、半个小时，10分钟等)接受服务的顾客数量，分多次记录，每次记录1个单位时间，然后计算平均服务率。

(3)计算有关参数，并进一步计算排队系统的数量指标。

(4)依据计算结果对排队系统进行分析和评价。

(5)提出积极的建议，并论证其可行性，讨论其实践意义。上一页返回下一页S2.4存贮论问题S2.4.1实验与实践

(1)学习并掌握一种用于求解存贮论问题的计算机应用软件。

(2)体会并掌握存贮问题建模的特点，特别是灵活掌握确定性存贮问题的理论结果，在随机型存贮问题求解过程中的作用和意义，并讨论如何在实践中应用计算的理论结果。

(3)分组制订实践调研计划，收集数据，分析、讨论存贮论的实践应用领域和模式特征。

(4)选择S2.4.2的案例进行分组讨论、分析，计算结果，并组织在班内介绍思路和计算情况。

(5)每一小组在(3)的基础上，结合实际编写一个案例并进行分析、求解，讨论解的过程及实践意义。下一页返回上一页S2.4存贮论问题S2.4.2案例建模与分析例S2.17益民食品批发部为附近200多家食品零售店提供某品牌方便面的货源。为了满足顾客的需求，批发部目前采取的进货方案为:每月进一次货并存入仓库，当发现货物快售完时，及时调整进货。如此每年需花费在存贮和订货上面的费用约37000元。批发部负责人考虑降低这笔费用，并达到最好的运营效果。为此，益民食品批发部对这种方便面的需求进行调查，得到以下12周的数据:3000箱、3080箱、2960箱、2950箱、2990箱、3000箱、3020箱、3000箱、2980箱、3030箱、3000箱、2990箱。上一页下一页返回S2.4存贮论问题

另外，已知单位存储费以存贮率(占成本的百分比)来定，是20%(包含占用资金利息12%，仓库、保险、损耗等管理费用8%，这种方便面的成本为每箱30元。又知每次订货费(包含手续费、电话费、交通费、采购人员劳务费等)25元。依据这些数据，制订订货方案，使存贮、订货的总费用尽可能少。解根据上述数据分析可知，需求量近似常数3000(箱/周)，可以近似看做需求确定型的经济订购问题。按照已知条件，可以得到方便面的单位年存储费:存贮率20%，每箱成本30元，故上一页下一页返回S2.4存贮论问题每次订货费:c3=25元/次。年需求量:D=3000x52=156000(箱)。利用有关公式，可求得最优存贮量货间隔时间急费用上一页下一页返回S2.4存贮论问题

实用分析:我们注意到，上述理论数据在操作上存在困难。一般来说，不能够简单地通过近似来操作，当结果的稳定性较差时，往往会造成超出人们预料的损失。实践中，要想用近似方法来解决问题，应该进行灵敏性分析。本例的灵敏度分析:当我们不能得到灵敏性的理论结果(线性规划的灵敏性分析是有理论结果的)时，可以通过讨论参数扰动的影响来取代。我们下面讨论单位存贮费c1和每次订购费c3发生变化时对最优存贮策略的影响，通过上述计算得到表S2-11。表中数据显示，最优方案比较稳定。我们有把握对其进行实际操作方面的修改:例题结论的实际操作:上一页下一页返回S2.4存贮论问题(1)进货间隔时间2.67天(无法操作)延长为3天，于是每次订货量变为

(2)为保证供应，决定多存贮200箱，于是第1次进货为1282+200=1482(箱)，以后每次进货为1282箱。(3)若需提前1或2天订货(从订货到货物到位需要1或2天)，则应在剩下货物量为D/365=3000·52/365=427(箱)(1天)或854箱(2天)时就订货，这称为再订货点。实际操作方式修改后，实际总费用为我们可以看到，即使做了使用上的操作修改，总费用仍比原来下降很多，为上一页下一页返回S2.4存贮论问题例S2.18某公司经营一种专用，靠订货供应需求。已知，年需求D=4900个/年，存储费c1=1000元/个·年，订货费c3=500元/次。(1)不允许缺货时，求:最优存储量Q*、订货周期T及总费用TC。

(2)允许缺货时，缺货费c2=2000元/个·年，求:最优存储量Q*，最优缺货量S*，订货周期T及总费用TC。

(3)如果公司改订货为自己生产，年生产能力p=9800个/年，生产准备费与订货费相同c3=500元/次。不允许缺货时，求:最优存储量Q*、订货周期T及总费用TC。

(4)在(3)的假设下，允许缺货时，缺货费c2=2000元/个年，求:最优存储量Q*，最优缺货量S*，订货周期T及总费用TC。(5)比较上述结果，你可得到什么结论?为什么?有什么实践意义?解利用有关公式，可求得(1)~(4)的结果，列表如表S2-12所示。上一页下一页返回S2.4存贮论问题从表中可以看出:同样是订购问题或生产问题，允许缺货的最小总费用比不允许缺货的少;生产问题比订购问题的总费用少。关于为什么的问题和实践中的意义，请读者思考。例S2.19已知单位存储费C1=0.5元，单位货价K=0.5元，单位缺货费C2=4.5元，订购费用C3=9元，需求量密度函数为试确定最优存储策略(s,S)

解上一页下一页返回S2.4存贮论问题故由方程 得上一页下一页返回S2.4存贮论问题解得x1=2或x=14>S(舍去)，故s=20。最优解为:当初始库存I<2时，应订货。订货量为Q*=8-I，当I>2时，不订货。例S2.20某公司在生产过程中需用一种紧缺化学原料K，该原料K每千克价格为500元，若在生产过程中该原料K变质，而公司又无备用原料K，则将产生20000元的损失，因此，需要考虑购买备用原料K的问题，每千克原料K在生产期内的存储费不论存储时间长短均为100元，已知在生产期内所需该备用材料K的数量服从如表S2-13所示的概率分布。问:公司应订购多少千克该备用原料K，才能使总费用最低?上一页下一页返回S2.4存贮论问题解记α=500+100=600=6(百元)，β=20000=200(百元)设Q为订购量，x为需求量。①由于订购过少，Q<x，应支付的费用为期望值为②由于订购过多，Q>x，应支付的费用为期望值为总费用期望为上一页下一页返回S2.4存贮论问题结果如表S2-14所示。故应订购1千克备用原料K，才能使总费用期望值最低为8.6(百元)，即860元。例S2.21某超市每年销售5000只玩具汽车。最近该商品的供应商为超市提供数量拆扣的价格优惠策略(数量拆扣表见表S2-15)，即玩具汽车的原价格为50元/只;若订货量在1000~1999只，单位价格为48元;若订货量为2000只或者2000只以上，单位价格为47.5元。已知订货费用为490元/次，每只玩具汽车的存贮费用为其单位成本的20%o试求最优的订货策略。上一页下一页返回S2.4存贮论问题解根据题意可知其中，首先计算每一个价格对应的最优订货批量Eop确定a1*，a2*，a3*，因为0≤EOQ1=700<999，所以a1*=700；因为EOQ2=714<1000，所以a2*=1000；因为EOQ3=718<2000，所以a3*=2000；上一页下一页返回S2.4存贮论问题通过计算订货量为a1*，a2*，a3*时的总费用，确定最优订货策略a*。由相关公式可以计算出结果，如表S2-16所示。由此可知，最优的订货策略为每次以48元/只的价格订购1000只玩具汽车。上一页返回下一页S2.5图与网络分析问题S2.5.1实验与实践

(1)学习并掌握求解图与网络分析问题的求解思路和方法。

(2)体会并掌握图与网络分析问题的特点，重点掌握最小生成树、最短路、最大流问题的特征与求解思路、求解方法。

(3)分组制订实践调研计划，收集数据，分析、讨论整数规划的实践应用领域和模式特征。

(4)选择S2.5.2的案例进行分组讨论、分析，计算结果，并组织在班内介绍思路和计算情况。

(5)每一小组在(3)的基础上，结合实际编写一个案例并进行分析、求解，讨论解的过程及实践意义。下一页返回上一页S2.5图与网络分析问题S2.5.2案例建模与分析例S2.22求图S2-1所示的网络中v0，到各节点的最短路。解令u0=v0,步骤1:设步骤2:对与u0，相邻的节点:v1，v2，v3，v4，v5，v6，进行l(vi)值置换(更改临时标号)，可得上一页下一页返回S2.5图与网络分析问题选其中最小值，l(v1)=1，令u1=v1

，并将其标号改为永久标号上一页下一页返回S2.5图与网络分析问题步骤3:令故u0到u1(即v0到v1)的最短路为P1=(u0，u1)=(v0，v1)，检查是否全部节点已进入S，若已进入，则算法结束;否则，返回步骤2。步骤2:再对与u1相邻的节点(u0除外)，v2，v6，v7进行l(vi)值的置换，可得上一页下一页返回S2.5图与网络分析问题对所有未获永久标号的节点，找出具有最小临时标号的点，得l(v2)=2，令u2=v2，并将其标号改为永久标号步骤3:令 ，通过对u2标号过程的回溯可知，u0到u2的最短路上，u2的前一个节点(即先驱点)为u0(注意不是u1)，故u0到u2(即v0到v2)的最短路为P1=(u0，u1)=(v0，v1)。此时，节点尚未全部进入S，继续步骤2。步骤2:再对与u2相邻的节点(u0,u1除外)v5，v7进行l(vi)值的置换，可得上一页下一页返回S2.5图与网络分析问题到目前为止，未获得永久标号的各节点临时标号值分别为选其中最小值得， ，并将其标号改为永久标号步骤3:令 ，通过对u3标号过程的回溯可知，u3的先驱点为u2，故u0到u3(即v0到v3)的最短路为 。此时，节点尚未全部进入S，继续步骤2。步骤2:再对与u3相邻的节点(u0,u1，u2除外)v3，v5，v7进行l(vi)值的置换，可得上一页下一页返回S2.5图与网络分析问题对所有未获永久标号的节点，找出最小临时标号值，得l(v4)=4，令u4=v4，并将其标号改为永久标号步骤3:令 ，由于u4的先驱点为u3，故u0到u4(即v0到v4)的最短路为 。此时，继续步骤2。步骤2:再对与u4相邻的节点(u0,u1，u2，u3除外)v3，v5，v6进行l(vi)值的置换，可得上一页下一页返回S2.5图与网络分析问题最小临时标号为l(v5)=l(v6)=6，任选其一(如v5),令u5=v5

，并将其标号改为永久标号步骤3:令由于u5的先驱点为u4，故u0到u5(即v0到v5)的最短路为 。此时，继续步骤2。步骤2:再对与u5相邻的节点(永久标号点除外)v3进行l(vi)值的置换，可得上一页下一页返回S2.5图与网络分析问题最小临时标号值，得l(v6)=6，令u6=v6，并将其标号改为永久标号步骤3:令由于u6的先驱点为u4，故u0到u6(即v0到v6)的最短路为 。此时，继续步骤2。步骤2:再对与u6相邻的节点(永久标号点除外)v3进行l(vi)值的置换，可得上一页下一页返回S2.5图与网络分析问题最小临时标号值，得l(v7)=9，令u7=v3，并将其标号改为永久标号步骤3:令

u7的先驱点为u3，故u0到u7(即v0到v3)的最短路为 。所有节点均已进入Si，计算终止。最后得到v0到各节点的最短路，各节点最后所标的d(ui)值即为d(u0，ui)(i=1，2，…，7)。需要注意的是，为得出最短路的路径，需要在树的生长过程中保留先驱点的轨迹。在标号过程中每当进行l(v)标号转换时(即由l(v)标为d(u)时)，由式上一页下一页返回S2.5图与网络分析问题在选定l(v)时，使上式成立的ui即为v的先驱点，顺先驱点逐点反推即可列出从始点到该点的最短路径。试讨论并比较这里的最短路径问题求解思路、方法与动态规划中求解最短路径问题有哪些相同点和不同点?如果用动态规划的思路考虑，这里的求解方法应怎样描述。例S2.23用“破圈法”求图S2-2所示赋权图的一个最小支撑树)解在图S2-2中，每次考虑的圈均以粗线示出，丢掉的最大权的边在图中不再示出，如图S2-3(a)~(f)所示。在图S2-3(e)中，由粗线形成的圈有两条权为6的最长边，这时可任意丢掉其一，这里丢掉了边(V2，V5)。上一页下一页返回S2.5图与网络分析问题例S2.24求图S2-4中从V1到各个顶点的最短路的长度。解首先给V1以标号(0,0)，然后进行第二轮计算，在第一步中， 包含两条弧(V1,V2)，(V1,V4)，对应的K为最小的是K12=2，按第三步应给V2以标号(2,1)，然后进人第三轮计算，这时已标号顶点有Vl，和V2

，故 包含下述三条弧由于K14=8上面已算过，不必再算(可以把K14记在弧旁边，并在外面画一个方框)，而上一页下一页返回S2.5图与网络分析问题于是最小的是K25=3，故应给V5以标号(3,2)，然后进人第四轮计算，这时已标号的顶点为V1

，V2

，V5

，故 包含下述四条弧:Kij中最小的是K59=3+1=4，故应给矶以标号(4,5)，继续做下去，最后可得到图S2-5。从图S2-5中可以看出从Vl到各个顶点Vj都存在有向路(因为所有顶点都得到了标号)，而且很容易具体地把V1到每个Vj的最短路及它的长度求出来。例如，看V8，从V8的标号(11,9)立即可知，V1到V8的最短路长度是11，而最短路则可由“逆向追踪”的办法求得:对于有向图中存在有负权弧时最短路的求法与上面的标号法相类似，这里就不再叙述了。上一页下一页返回S2.5图与网络分析问题例S2.25求图S2-6中网路的最大流。解从图S2-6中的值为7的可行流开始，通过标号过程来寻求可扩充路。给V1，标号(0,+)，然后取V1

，用第四步对V1进行检查，发现V2与V3分别可以得到标号(1,+)，(1,+)，V1成为已检查的点，再取已标号而未检查的点砚，由第四步可使顶点竹得到标号(2,+)，V5得到标号(2，-)。现在V3，V4，V5都是已标号而未检查的点，可以任取一个，如V5

，用第四步可使V6得到标号(5,+)，应用第五步的“逆向追踪”方法，找出可扩充路。由于V6的标号是(5,+)，故可扩充路的最后段是:{V5，(V5，V6)，V6}，又V5的标号是(2，-)，故往前追踪是{V2，(V5，V2)，V5，(V5，V6)，V6}，又因V2的标号是(1+)，所以可扩充路是上一页下一页返回S2.5图与网络分析问题通过调整过程，求出改进后的可行流。令取因此改进后的可行流如图S2-7所示。对新的可行流再用标号过程来寻求可扩充路，经过几次标号可得扩充路为易见调整量ε=1，改进后的可行流如图S2-8所示。对于图S2-8中的可行流再用标号过程，在V1得到标号后，按第四步对V1进行检查，经过两步，没有使其他任何顶点得到标号，即标号过程进行不下去，故算法结束。因此，图中的可行流已是最大流。上一页下一页返回S2.5图与网络分析问题例S2.26设有图S2-9所示的赋权图，构造通过每个节点一次，总权数最小的链。解因顶点V1和V3是奇次顶点，为使各顶点均为偶次顶点，可有多种加重复边的方式。若在图(a)的基础上加成图(b)，它虽满足条件①，但不满足条件②的要求，故不可能是总权数为最小的闭欧拉链，图(c)也满足条件①，但在闭合链 ，故不满足条件②。欲使它同时满足条件①和②，应改加边e1和e5，如图S2-10所示，容易看出，在加的边所涉及的闭链 和 中都满足条件①和②。因此图(d)是总权最小的闭的欧拉链。上一页返回下一页S2.6决策分析问题S2.6.1实验与实践

(1)学习并掌握求解不确定型决策问题的5种思路和方法。

(2)学习并掌握求解风险型决策问题的期望值准则、决策树的绘制与计算;理解、认识转拆概率概念，了解效用函数的实践意义及其测试方法。

(3)分组制定实践调研计划，收集数据，分析、讨论决策分析的实践应用领域和模式特征。

(4)分组选择S2.6.2的案例进行讨论、分析，计算结果，并组织在班内介绍思路和计算情况。

(5)每一小组在(3)的基础上，结合实际编写一个案例并进行分析、求解，讨论解的过程及实践意义。下一页返回上一页S2.6决策分析问题S2.6.2案例建模与分析例S2.27Q公司考虑从1800千米外的B地采购一批西瓜，共40万千克。购进价为0.12元/千克。运往Q公司的方案有两个:a1为铁路普通车运输，平均每1000千克每千米运价为0.04元，损耗率为20%，而且售出平均价为0.20元/千米;a2为空调车运输，运费、损耗率、售出平均价分别为0.06元/(吨·千米)、2%、0.24元/千米。公司规定总利润超过2000元才可以采购。在销售不成问题的情况下，问Q公司是否应采购这批西瓜?若采购，应采用哪种运输方式?

解由题意可以知道，销售情况是不必顾虑的。未来状况，如价格、损耗率等都是确定的，故本决策问题属于确定型。策略空间A含有三个方案:a1为用普通运输购进，a2为用空调车运输购进，a3为不采购。我们不难计算出它们的收益分别为上一页下一页返回S2.6决策分析问题对于方案a1:对于方案a2:对于方案a3:所以，最优方案a*=a2，即最好的决策方案为用空调车运输采购的这批40万千克西瓜。上一页下一页返回S2.6决策分析问题例S2.28某企业要投产一种新产品，投资方案有三个:S1,S2,S3，不同经济形势下的利润如表S2-17所示。(1)用乐观准则进行决策。(2)用悲观准则进行决策。(3)用乐观系数准则(拆中准则)，取α=0.6，进行决策。(4)用后悔值准则进行决策。(5)用等可能准则进行决策。解对于(3)，设CVi为拆中值，于是当α=0.6时，上一页下一页返回S2.6决策分析问题对于(5)，得到各方案的均值为把(1)，(2)，(3)，(5)做成决策表如表S2-18所示。首先构造后悔值矩阵，然后求各方案最大后悔值的最小值，确定决策结果，后悔值决策表如表S2-19所示。故对应的决策方案为S2。上一页下一页返回S2.6决策分析问题例S2.29某公司有10万元多余资金。如用于开发某个项目估计成功率为95%，成功时一年可获利15%，但一旦失败，有全部丧失资金的危险。如把资金存放到银行中，则可稳得年利4%。为获得更多的信息，该公司求助于咨询公司，咨询费为800元，但咨询意见只是提供参考。咨询公司过去的类似200例咨询意见实施结果如表S2-20所示，试用决策树法分析:(1)该公司是否值得求助于咨询公司?(2)该公司多余资金该如何使用?

解分析收益:

若不求助咨询公司:多余资金用于开发某个项目成功时可获利100000×15%(元)=15000，存入银行可获利100000×4%=4000(元);若失败，则损失100000元，即收益为-100000元。上一页下一页返回S2.6决策分析问题

若求助咨询公司:各项资金均需减少咨询费800元，于是成功时可获利14200元，存入银行可获利3200元;若失败，则损失100800元，即收益为-100800元。概率状况:

设:S1:咨询公司意见可以投资;S2:咨询公司意见不可以投资;E1:投资成功;E2:投资不成功。由题义知:上一页下一页返回S2.6决策分析问题根据概率乘法公式又因为故得决策树如下:上一页下一页返回S2.6决策分析问题上一页下一页返回S2.6决策分析问题由上图可得结论: