2022年《运筹学》复习参考资料知识点及习题 .pdf

《2022年《运筹学》复习参考资料知识点及习题 .pdf》由会员分享，可在线阅读，更多相关《2022年《运筹学》复习参考资料知识点及习题 .pdf（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一部分线性规划问题的求解一、两个变量的线性规划问题的图解法：概念准备： 定义：满足所有约束条件的解为可行解；可行解的全体称为可行（解）域。定义：达到目标的可行解为最优解。图解法：图解法采用直角坐标求解：x1横轴； x2竖轴。 1、将约束条件（取等号）用直线绘出；2、确定可行解域；3、绘出目标函数的图形（等值线） ，确定它向最优解的移动方向；注：求极大值沿价值系数向量的正向移动；求极小值沿价值系数向量的反向移动。4、确定最优解及目标函数值。参考例题：（只要求下面这些有唯一最优解的类型）例 1：某厂生产甲、乙两种产品，这两种产品均需在A、B、C 三种不同的设备上加工，每种产品在不同设备上加工所需

2、的工时不同，这些产品销售后所能获得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示：A B C 利润（万元）甲乙3 5 9 9 5 3 70 30 有效总工时540 450 720 问：该厂应如何组织生产， 即生产多少甲、 乙产品使得该厂的总利润为最大？（此题也可用“ 单纯形法 ”或化“ 对偶问题 ”用大 M 法求解）设备消耗产品名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 1 页，共 27 页 - - - - - - - - - 解：设 x

3、1、x2为生产甲、乙产品的数量。max z = 70 x1+30 x2s.t. 072039450555409321212121xxxxxxxx，可行解域为 oabcd0，最优解为 b 点。由方程组72039450552121xxxx解出 x1=75，x2=15 X*=21xx=（75，15）T max z =Z*= 70 75+30 15=5700 、名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 2 页，共 27 页 - - - - - - - - - 例 2：

4、用图解法求解max z = 6x1+4x2s.t. 0781022122121xxxxxxx，解：可行解域为 oabcd0 ，最优解为 b 点。由方程组81022121xxxx解出 x1=2，x2=6 X*=21xx=（2，6）Tmax z = 6 2+4 6=36 、名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 3 页，共 27 页 - - - - - - - - - 例 3：用图解法求解min z =3x1+x2s.t. 08212523421212121xx

5、xxxxxx，解：可行解域为 bcdefb，最优解为 b 点。由方程组12524211xxx解出 x1=4，x2=54X*=21xx=（4，54）Tmin z =3 4+54=1151、名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 4 页，共 27 页 - - - - - - - - - 二、标准型线性规划问题的单纯形解法：一般思路：1、用简单易行的方法获得初始基本可行解；2、对上述解进行检验，检验其是否为最优解，若是，停止迭代，否则转入3；3、根据 L规则确定改

6、进解的方向；4、根据可能改进的方向进行迭代得到新的解；5、根据检验规则对新解进行检验，若是最优解，则停止迭代，否则转入3，直至最优解。具体做法（可化归 标准型 的情况） ：设已知max z = c1x1+ c2x2+ cnxns.t. njxbxaxaxabxaxaxabxaxaxajmnmnmmnnnn，.210.22112222212111212111对第 i 个方程加入松弛变量xn+i，i =1，2，m，得到njxbxxaxaxabxxaxaxabxxaxaxajmmnnmnmmnnnnnn，.210.2211222222121111212111列表计算，格式、算法如下：名师归纳总结 精

7、品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 5 页，共 27 页 - - - - - - - - - CBXBb c1c2cn+mLx1x2xn+mcn+1xn+1b1a11a12a1 n+mc n+2xn+2b2a21a22a2 n+m. . . . . . . . cn+mxn+mbnam1am2am n+mz1z2zn+m12n+m注：zj =cn+1a1j+ cn+2a2j+ cn+mamj=miijinac1， （j=1，2，n+m）j =cjzj ,当j 0 时，当

8、前解最优。注：由 maxj 确定所对应的行的变量为“入基变量”；由L=0minikikiiaab确定所对应的行的变量为“出基变量”，行、列交叉处为主元素，迭代时要求将主元素变为1，此列其余元素变为0。例 1：用单纯形法求解（本题即是本资料P2“图解法 ”例 1 的单纯形解法 ；也可化“ 对偶问题 ”求解）max z =70 x1+30 x2s.t. 072039450555409321212121xxxxxxxx，解：加入松弛变量x3，x4，x5，得到等效的标准模型：max z =70 x1+30 x2+0 x3+0 x4+0 x5名师归纳总结 精品学习资料 - - - - - - - - -

9、 - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 6 页，共 27 页 - - - - - - - - - s.t. 5,.,2, 1,0720394505554093521421321jxxxxxxxxxxj列表计算如下：CBXBb 70 30 0 0 0 Lx1x2x3x4x50 x3540 3 9 1 0 0 540/3 =180 0 x4450 5 5 0 1 0 450/5 =90 0 x5720 （9）3 0 0 1 720/9 =80 0 0 0 0 0 7030 0 0 0 0 x3300 0 8 1 0 - 1

10、/3 300/8 =37.5 0 x450 0 （10/3 ）0 1 - 5/9 50/10/3 =15 70 x180 1 1/3 0 0 1/9 80/1/3 =240 70 70/3 0 0 70/9 0 20/30 0 70/90 x3180 0 0 1 12/51 30 x215 0 1 0 3/10 - 1/6 70 x175 1 0 0 - 1/10 1/6 5700 70 30 0 2 20/3 0 0 0 -2 20/3X*=（75，15，180，0，0）Tmax z =7075+3015=5700名师归纳总结 精品学习资料 - - - - - - - - - - - - -

11、 - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 7 页，共 27 页 - - - - - - - - - 例 2：用单纯形法求解max z =7x1+12x2s.t. 0300103200543604921212121xxxxxxxx，解：加入松弛变量x3，x4，x5，得到等效的标准模型：max z =7x1+12x2+0 x3+0 x4+0 x5s.t. 5,.,2 , 1, 03001032005436049521421321jxxxxxxxxxxj列表计算如下：名师归纳总结 精品学习资料 - - - - - - - - - - - -

12、- - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 8 页，共 27 页 - - - - - - - - - CBXBb 7 12 0 0 0 Lx1x2x3x4x50 x3360 9 4 1 0 0 360/4 =90 0 x4200 4 5 0 1 0 200/5 =40 0 x5300 3 （10）0 0 1 300/10 =30 0 0 0 0 0 7 120 0 0 0 x3240 78/10 0 1 0 - 2/5 240/78/10 =2400/78 0 x450 （5/2 ）00 1 - 1/2 50/5/2 =20 12 x2

13、30 3/1010 0 1/10 30/3/10 =100 18/5 12 0 0 6/5 17/500 0 6/50 x384 0 0 1 78/2529/25 7 x120 1 00 2/5 - 1/5 12 x224 0 1 0 3/25 4/28 428 7 12 0 34/25 11/35 0 0 0 34/25 11/35X*=（20，24，84，0，0）T max z =720+1224=428三、非标准型线性规划问题的解法：1、一般地，对于约束条件组：若为“”，则加松弛变量，使方程成为“” ；若为“”，则减松弛变量，使方程成为“” 。我们在前面标准型中是规定目标函数求极大值。如

14、果在实际问题中遇到的是求极小值，则为 非标准型 。可作如下处理：名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 9 页，共 27 页 - - - - - - - - - 由目标函数 min z=njjjxc1变成等价的目标函数max（z）=njjjxc1)(令z=z/，min z=max z/2、等式约束大M 法：通过加人工变量的方法，构造人造基，从而产生初始可行基。人工变量的价值系数为 M，M 是很大的正数， 从原理上理解又称为 “惩罚系数”。 （课本 P29）类

15、型一：目标函数仍为 max z，约束条件组与。例 1：max z =3x1+5x2s.t. 018231224212121xxxxxx，解：加入松弛变量x3，x4，得到等效的标准模型：max z =3x1+5x2s.t. 4, 3 ,2, 1, 018231224214231jxxxxxxxj其中第三个约束条件虽然是等式，但因无初始解，所以增加一个人工变量x5，得到：max z =3x1+5x2Mx5s.t. 5, . . . ,2, 1,0182312245214231jxxxxxxxxj单纯形表求解过程如下：名师归纳总结 精品学习资料 - - - - - - - - - - - - - -

16、 -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 10 页，共 27 页 - - - - - - - - - CBXBb 3 5 0 0 MLx1x2x3x4x50 x34 （1）0 1 0 0 4/1 =4 0 x412 0 2 0 1 0 Mx518 3 2 0 0 1 18/3 =6 3M2M0 0 M3M352M0 0 0 3 x14 10 1 0 0 0 x412 020 1 0 12/2 =6 Mx56 0（2）3 0 1 6/2 =3 3 2M33M0 M0 533M0 0 3 x14 1 0 1 0 0 4/1 =4 0 x46 0

17、0（3）1 1 6/3 =2 5 x23 0 13/2 0 1/2 3/(2/3) =9/2 3 5 9/2 0 5/2 0 0 9/2 0 M5/2 3 0 5 x12 1 0 0 1/3 1/3x32 0 0 11/3 1/3 x26 0 1 0 1/2 0 36 3 5 0 3/2 1 0 0 0 3/2 M1X*=（2，6，2，0）T名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 11 页，共 27 页 - - - - - - - - - max z =32

18、+56=36类型二：目标函数 min z，约束条件组与。例 2：用单纯形法求解min z =4x1+3x2s.t. 012231642212121xxxxxx，解：减去松弛变量x3，x4，并化为等效的 标准模型：max z/ =4x13x2s.t. 4,3 ,2, 1,012231642421321jxxxxxxxj增加人工变量 x5、x6，得到：max z/ =4x13x2Mx5Mx6s.t 6,.,2, 1, 01223164264215321jxxxxxxxxxj单纯形表求解过程如下：名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选

19、学习资料 - - - - - - - - - - - - - - - 第 12 页，共 27 页 - - - - - - - - - CBXBb 4 0 0 MMLx1x2x3x4x5x6Mx516 2 （4）1 0 1 0 16/4=4 Mx612 32 0 1 0 1 12/2=6 5M6MMMMM5M4 6M3MM0 0 3 x24 1/2 1 1/4 0 1/4 0 4/1/2=8 Mx64 （2）0 1/2 1 1/2 1 4/2=2 2M3/23 3/4M/2MM/23/4M2M5/20 M/23/4M3/43M/20 3 x23 0 1 3/8 1/4 3/8 1/4 4 x12

20、 1 0 1/4 1/2 1/4 1/2 17 4 3 1/8 5/4 1/8 5/4 0 0 1/8 5/4 M1/8 M5/4 X*=（2，3，0，0）Tmin z =max z/ =（ 17）=17 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 13 页，共 27 页 - - - - - - - - - 四、对偶问题的解法：什么是对偶问题？1、在资源一定的条件下，作出最大的贡献；2、完成给定的工作，所消耗的资源最少。引例（与本资料 P2 例 1 “图解法”

21、、P7 例 1 “单纯形法 ”同）：某工厂生产甲、乙两种产品，这些产品均需在A、B、C 三种不同的设备上加工，每种产品在不同设备上加工时需要不同的工时，这些产品售后所能获得的利润值以及这三种加工设备因各种条件下所能使用的有效总工时数如下表：A B C 利润（万元）甲乙3 5 9 9 5 3 70 30 有效总工时540 450 720 问：该厂应如何组织生产， 即生产多少甲、 乙产品使得该厂的总利润为最大？解：原问题设 x1、x2为生产甲、乙产品的数量。max z = 70 x1+30 x2s.t. 072039450555409321212121xxxxxxxx，将这个原问题化为它的对偶问题

22、设备消耗产品名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 14 页，共 27 页 - - - - - - - - - 设 y1、y2、y2分别为设备 A、B、C 单位工时数的加工费。min w = 540y1+450y2+720y3s.t. 32103035970953321321，iyyyyyyyi用大 M 法，先化为等效的 标准模型：max w/ =540y1450y2720y3s.t. 5,.,2, 1,0303597095353214321jyyyyyyy

23、yyj增加人工变量 y6、y7，得到：max z/ =540y1450y2720y3My6My7s.t 5,.,2, 1,030359709537532164321jyyyyyyyyyyyj大 M 法单纯形表求解过程如下：名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 15 页，共 27 页 - - - - - - - - - CBXBb 540 450 720 0 0 MMLy1y2y3y4y5y6y7My670 3 5 9 1 0 1 0 70/3 My730

24、（9）5 3 0 1 0 1 30/9=10/3 12M10M12MMMMM12M54010M45012M720MM0 0 My660 0 10/3 （8）1 1/3 1 1/3 60/8=2.5 540 y110/3 1 5/9 1/3 0 1/9 0 1/9 10/3/1/3 =10 -300+10/3 M-8 M180MM/3+6 0MM/3600 -150+10/3 M 8M-540MM/3 600 M/3+6 0720 y315/2 0 5/12 1 1/8 1/24 1/8 1/24 15/2/5/12 =18 540 y15/6 1 （5/12 ）0 1/24 1/8 1/24

25、1/8 5/6/5/12 =2 540 572 720 135/2 475/12 135/2 75/20 1250 135/2 475/12 135/2 M75/2M720 450 y320/3 1 0 1 1/6 1/6 1/6 1/6y22 12/5 1 0 1/10 3/10 1/10 3/105700 360 450 720 75 15 75 15 180 0 0 75 15 75M15M该对偶问题的最优解是y*=（0，2，320，0，0）T最优目标函数值min w =（ 5700）=5700 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整

26、理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 16 页，共 27 页 - - - - - - - - - 五、运输规划问题：运输规划问题的特殊解法“表上作业法” 解题步骤：1、找出初始调运方案。即在(mn)产销平衡表上给出m+n-1 个数字格。 （最小元素法）2、 （对空格）求检验数。判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。 （闭回路法）3、对方案进行改善，找出新的调运方案。 （根据检验结果选择入基变量，用表上闭回路法 调整即迭代计算，得新的基本可行解）4、重复 2、3，再检验、再迭代，直到求得最优调运方案。类型一：供求平衡的运输规

27、划问题（又称“供需平衡”、 “产销平衡”）引例：某钢铁公司有三个铁矿和四个炼铁厂，铁矿的年产矿石量分别为100万吨、80 万吨和 50 万吨，炼铁厂年需矿石量分别为50 万吨、70 万吨、80 万吨和 30万吨，这三个铁矿与四个炼铁厂的距离如下：B1B2B3B4A1A2A315 20 3 30 70 8 14 20 12 3 20 15 问： 该公司应如何组织运输， 既满足各炼铁厂需要， 又使总的运输费用为最小 （按吨.公里计）？解：用“表上作业法”求解。先用最低费用法（最小元素法）求此问题的初始基础可行解：炼铁距离铁矿厂名师归纳总结 精品学习资料 - - - - - - - - - - -

28、- - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 17 页，共 27 页 - - - - - - - - - B1B2B3B4产量SiA1152067330 65 1002080A27081444 2080302030A31253 32033 25 10 5050销量dj50708030 230 230 初始方案：Z=1520+380+7030+820+2030+350=3550（吨.公里）对的初始可行解进行迭代（表上闭回路法），求最优解：销地费用产地20 80 B1B3A1B220 30 30 B1B3A2B250 A3名师归纳总结 精

29、品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 18 页，共 27 页 - - - - - - - - - B1B2B3B4产量SiA1152014 330 12 1002080A27053 8149 208050 30A312320 20 25 10 5030 20 销量dj50708030230 230 用表上闭回路法调整后，从上表可看出，所有检验数0，已得最优解。最优方案：Z=1520+380+850+2030+1230+320=1960（吨.公里）解法分析：如何求检验数并由

30、此确定入基变量？有数字的空格称为“基格”、打的空格称为“空格” ，标号为偶数的顶点称为偶点、 标号为奇数的顶点称为奇点， 出发点算 0 故为偶点。找出所有空格的闭回路后计算它们的检验数偶点奇点ijijijcc，必须ij0，才得到最优解。否则，应选所有中正的最大者对应的变量xj为入基变量进行迭代（调整） 。检验后调整运输方案的办法是：在空格的闭回路中所有的偶点均加上奇点中的最小运量，所有的奇点均减去奇点中的最小运量。重复以上两步，再检验、再调整，直到求得最优运输方案。类型二：供求不平衡的运输规划问题销地费用产地20 80 B1B3A150 30 B2B4A230 20 B1B2A3名师归纳总结

31、精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 19 页，共 27 页 - - - - - - - - - 若njjmiids11，则是供大于求（供过于求）问题，可设一虚销地Bn+1，令ci,n+1=0，dn+1=njjmiids11，转化为产销平衡问题。若njjmiids11，则是供小于求（供不应求）问题，可设一虚产地Am+1，令cm+1,j=0，sm+1=miinjjsd11，转化为产销平衡问题。（，2， m ； ，2， n）六、工作指派问题：工作指派问题的数学模型假定有 n

32、 项工作需要完成，恰好有n 个人每人可去完成其中一项工作，效果要好。工作指派问题的特殊解法“匈牙利法 ” （考！ ！ ）解题步骤：1、使系数矩阵（效率矩阵）各行、各列出现零元素。作法：行约简 系数矩阵各行元素减去所在行的最小元素，列约简再从所得矩阵的各列减去所在列最小元素。2、试求最优解。如能找出n 个位于不同行不同列的零元素，令对应的xij= 1，其余xij= 0，得最优解，结束；否则下一步。作法：由独立 0 元素的行（列）开始，独立0 元素处画 （）标记 ，在有（）的行列中划去（也可打 *）其它 0 元素；再在剩余的 0 元素中重复此做法， 直至不能标记 （）为止。3、作能覆盖所有0 元素

33、的最少数直线集合。作法：对没有 （）的行打号；对已打号的行中所有0 元素的所在列打号；再对打有号的列中0 元素的所在行打号； 重复、直到得不出新的打号的行(列)为止；对没有打号的行画一横线，对打号的列画一纵线，这就得到覆盖所有0 元素的最少直线数。未被直线覆盖的最小元素为cij,在未被直线覆盖处减去cij,在直线交叉处加上cij。4、重复 2、3，直到求得最优解。类型一：求极小值的匈牙利法： （重点掌握这种基本问题）名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 2

34、0 页，共 27 页 - - - - - - - - - 例 1：有甲、乙、丙、丁四个人，要派去完成A、B、C、D 四项工作，他们完成的工时如下表：A B C D 甲乙丙丁6 12 13 4 10 3 12 14 7 14 13 16 8 8 12 10 试问：应如何分配任务可使总工时为最少？解：用“匈牙利法”求解。已知条件可用系数矩阵（效率矩阵）表示为：（cij）=1012881613147141231041312624009670119070982200092701150705822)0(00927)0(115)0(7)0(582*使总工时为最少的分配任务方案为：甲D，乙B，丙A，丁 C

35、此时总工时数 W=4+3+7+12=26 例 2：求效率矩阵列约简任务工时人行约简标号甲乙丙丁A B C D 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 21 页，共 27 页 - - - - - - - - - 54325645778587910的最优解。解：5432564577858791032101201223010232210020112300023221002)0(1123)0(0)0(23*所画（） 0 元素少于 n，未得到最优解，需要继续变换矩阵（

36、求能覆盖所有 0 元素的最少数直线集合）：221002)0(1123)0(0)0(23*未被直线覆盖的最小元素为cij=1,在未被直线覆盖处减去1,在直线交叉处加上1。110002020120002411000202012)0(0)0(24*）（）（得最优解：0010100000010100类型二：求极大值的匈牙利法：min z=max（z）标号列约简行约简标号名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 22 页，共 27 页 - - - - - - - - -

37、 （cij）（Mcij）=（bij） ， （cij）中最大的元素为M max z=jijijixc=jijijixcM)(=jijijixcM)(jijijixc第一部分到此结束名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 23 页，共 27 页 - - - - - - - - - 第二部分动态规划只要求掌握动态规划的最短路问题用“ 图上标号法 ”解决：具体解题步骤请参看教材P103（这是本套资料少见的与教材完全相同的算法类型之一，务必看书掌握）学员们只有完全理解

38、了这种作法（思路：逆向追踪）才有可能做题，考试时数字无论如何变化都能作出正确求解！第二部分到此结束名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 24 页，共 27 页 - - - - - - - - - 第三部分网络分析一、求最小生成树（最小支撑树、最小树）问题：破圈法任取一个圈，从圈中去掉一条权最大的边（如果有两条或两条以上的边都是权最大的边，则任意去掉其中一条）。在余下的图中，重复这个步骤，直到得到一个不含圈的图为止，这时的图便是最小树。参考例题：例：求下图的

39、最小生成树：6 7 9 4 1 5 10 v2v1v3v5v4v63 2 8 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 25 页，共 27 页 - - - - - - - - - 解：用“破圈法”求得最小生成树为：已得最小树，此时权w=1+2+4+5+9=21 为最小。二、最短路问题：（有向图）TP 标号法（狄克斯托算法） 具体解题步骤请参看教材P125 （这是本套资料少见的与教材完全相同的算法类型之一，务必看书掌握）学员们只有完全理解了这种作法（思路：顺向追

40、踪）才有可能做题，考试时数字无论如何变化都能作出正确求解！参考例题：例：教材 P124图 48 的例子（略）三、网络最大流问题：寻求网络最大流的标号法（福特富克尔逊算法）具体解题步骤请参看教材 P130。（教材用有序数对（fij，cij）表示（流量，容量） ，但我们解题算法格式按南邮要求，用大多数 运筹学书籍中的标准格式，即用有序数对（cij，fij）表示（容量，流量） 。解法本质是相同的。 ）学员们只有完全理解了这种作法（思路：标号检查、迭代调整）才有可能做题，考试时数字无论如何变化都能作出正确求解！参考例题：运筹学参考综合习题 （我站搜集信息自编，非南邮综合练习题，仅供参考。另挂于网上）第

41、三部分到此结束9 4 1 5 v2v1v3v5v4v62 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 26 页，共 27 页 - - - - - - - - - 第四部分存储论（简介）随机存储模型参考例题：例：一食品店要决定每天牛奶的进货量，该店根据过去的销售经验，知道需求量的概率分布如下：需求 x（箱）25 26 27 28 p（x）0.1 0.3 0.5 0.1 若进货每箱 80 元，售价 100元，又若当天不能售出因牛奶变质而全部损失，试确定每天进货量。解

42、法一： 已知 C=80， p=100，g=0，需求 x（箱）25 26 27 28 概率 p（x）0.1 0.3 0.5 0.1 累计概率0.10.40.9 1 根据单周期随机型存储模型（ “报童模型”） 之离散型随机存储模型 公式，可得00100080100)(*sgpsCpQxp0.2即可以确定进货26 箱，获利的期望值最大。解法二： k=10080=20，h=80. khk=10020=0.2Px=25=0.1 0.2Px=25+Px=26=0.4 可以确定进货26 箱，获利的期望值最大。 。注：该问题即“报童问题” （关于报童进报纸问题的数学模型） ，即是相当于将上题的进 “牛奶”改为进“报纸”等等，解法思路是完全一致的，请注意！第四部分到此结束名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 27 页，共 27 页 - - - - - - - - -