目录目录 1第一章管理运筹学课程设计 2第一节线性规划之生产计划问题 2第二节物资的最小费用运输问题 5第三节管理中的随机性决策问题 10第二章运筹学软件练习题 14第一节线性规划 14第二节运输问题 16第三节整数规划 19第三节决策分析 21第三节最短路问题 23第三节最小支撑树 25第三节网络最大流 26第三节最小费用最大流28参考文献 30第一章管理运筹学设计第一节线性规划之生产计划问题一、问题的提出：某大型公司在安徽合肥地区的工厂仅生产扳手和钳子，扳 手和钳子是由钢铁制造的，并且制造过程先在浇铸机上浇铸，然后在装配机上装 配。用于生产一个扳手和一个钳子的钢铁数量和每天可以得到的钢铁数量见表1 1的第一行，下两行是生产一个扳手和一个钳子所需要的机器使用时间以及这 些机器的生产总时间，表的最后一行是每天这些变量（扳手和钳子）对本公司分 厂的盈利贡献。表11某大型公司在安徽亳州地区的工厂生产扳手和钳子的有关数据扳手钳子可获得的资源数量钢铁（kg）1.51.0每天 27000kg浇铸机工时（h）1.01.0每天21000h装配机工时（h）0.30.5每天9000h盈利贡献（百元/千件）130150该公司想作出安徽合肥地区的工厂有关扳手和钳子每天的生产量的计划，使 得对公司分厂的盈利贡献得到最大化。该公司要解决问题是：（1）为使这个大型公司在安徽合肥地区的工厂的盈利贡献得到最大化，应该计划每天生产多少件扳手和钳子？（2）根据这个计划该公司分厂的最大盈利是多少？（3）在这个计划中，哪些资源是最关键的因素？二、建立数学模型：对于这个问题，主要目标是使经营对公司分厂的盈利贡 献得到最大化。该公司必须对每天生产的扳手和钳子的数量作出决策，但由于资 源数值比较大，可以定义如下：X为每天生产的扳手数量，以千件为单位x2为每天生产的钳子数量，以千件为单位在这个问题中，目标是确定生产计划中的X和X2的数值，使对公司分厂的 盈利贡献最大化。为了求出这两个数值，有一些必须满足的约束条件，这些约束 条件是可供利用的钢铁数量限制、浇铸机工时限制和装配机工时限制，即：钢铁约束：1.5 x + x2 W27浇铸机约束：X + x2 W21装配机约束：0.3X + 0.5x2 W9因此该大型公司在安徽合肥地区的工厂生产计划问题的数学模型即线性规 划问题模型为：max z = 130X + 100x21.5 X + x2 W27s. t. 丿 x. + x2 W21 10.3X + 0.5x2 W9 j X1，X20化为标准型：max z = 130X + 100x2 +0 x3 + 0x4 + 0x5厂 1.5 X + x2 + x3 W27s. t.X + x2 + x4 W210.3X + 0.5x2+ x5 W9.X1，X2，X3，X4，X5 三 0三、模型的解答：本线性规划问题模型可以利用单纯形法得出最优解和最优值。表12c130100000eC3XbzXXcXXX0x271.521310501803x42111010210xE90.30.500130X130100000130Jx1812/32/300270x301/3 -2/31090x18/503/10-1/50112X040/3-260/300130x112102-20100x2900-2300x9/10002/5-9/101Xj100-60-400由于所有的检验数入j均已大于等于零，由此可知该线性规划问题的最优解为：X* = (12 , 9 , 0 , 0 , 9/10) t所以该公司分厂的盈利贡献最大化的生产计划为：x1= 12 , x2= 9对公司分厂的盈利贡献的最大值为2460百元/天。因此该大型公司在安徽合肥地区的分厂要解决的问题的答案为：(1) 该大型公司分厂应该计划每天生产12000件扳手和9000件钳子(2) 对该大型分厂盈利的总贡献将是：max = 130 X + 100 x2 = 2460 (百元/天)(3) 资源的使用率：钢铁数量=1.5 X 12000 + 1 X 9000 = 27000 (kg)这个结果正好等于每天可以得到的钢铁数量，所以钢铁数量是该大型公司分厂生 产扳手和钳子的关键资源浇铸机工时=1 X 12000 + 1 X 9000 = 21000 (h)这个结果正好等于每天浇铸机的生产能力，所以浇铸机的生产能力是该大型公司 分厂生产扳手和钳子的关键资源装配机工时=0.3 X 12000 + 0.5 X 9000 = 8100 (h)这个结果小于每天9000h的装配机的生产能力，所以装配机的生产能力不是该大型公司分厂生产扳手和钳子的关键资源四、运筹学软件检验最优解如下目标函数最优值为：2460变量最优解相差值x1120x290约束松弛/剩余变量对偶价格1060204035.40目标函数系数范围:变量下限当前值上限x1100130150x286.667100130常数项数范围：约束下限当前值上限1212731.5218212733.69无上限第二节 物资的最小费用运输问题一、问题的提出：包头市某食品生产公司在青山区有三个食品生产基地（可以认为是A、A、A ）和四个食品存储仓库分别在昆都仑区、东河区、青山区123和固阳县（可以认为是B、B、B、B ）这三个生产基地生产的食品需要及时运1234送到仓库区存储起来以防变质。各生产基地的生产能力（吨）和各村储仓库的存 储量（吨）以及从生产基地到存储仓库的单位运价（百元/吨）见下表，问如何 存储可以使总运费达到最小？表21 单位运价表（单位：百元/吨）单、仓位库产B1B2B3B4产量A1327650A2752360A3254525存储量60402015二、建立数学模型：设x.表示从产地A. （i=1, 2, 3）到存储仓库B. （j=1,IJIj2, 3, 4）的运输量，c.表示表中所示的单位运价。经分析可建立线性规划数学IJ模型表示如下：min z = 丫 c x.j .ji=1 j=1rt x = 135（j=1, 2, 3, 4）.ji=Ls. t .x = 135（i=1, 2, 3）错误！未找到引用源。.jx A 0（i=1, 2, 3； j=1, 2, 3, 4）ij三、模型的解答：此线性规划数学模型可知此问题相当于产销平衡问题，可以根据表上作业法求得最优解。单、仓位、库运、产B1B2B3B4产量A13102407650A2725522031560A322554525存储量60402015表2一2 最小元素法确定初始调运量方案（单位：百元/吨）表23位势法检验初始调运量方案（单位：百元/吨）单、仓位库运、产B1B2B3B4行A131024076（7）U=01A27255(-1)220315U=42A32255(4)4（7）5(7)U=-13列v =31V=22V=-23V=-14由于检验数久22 =-1，所以上述方案不是最优方案，所以用闭回路法进行方案调整见表24,并由此得到新方案见表25。表24闭回路法进行调整方案（单位：百元/吨）单仓位库运、产B1B2B3B4行A13+27(9)6（7）u=o11040A275+(-1)220315U=4225A32255(4)4（7）5(7)u=-13列v =3iV=22V=-23v=-i4表25闭回路法得到的新方案（单位：百元/吨）单、仓位库运、 产飞一价、B1B2B3B4产量A13352157650A2752522031560A322554525存储量60402015新方案仍然需要用位势法进行检验是否为最优方案，见表26。表26位势法检验新方案（单位：百元/吨）单仓位库运、产B1B2B3B4行A13352157(8)6(7)U=01A27(1)525220315U=32A32255(4)4(6)5(6)U=-13列v =31V=22V=13V=04由于所有的检验数久三0,故此方案为原始问题的最优方案，即该食品生IJ产公司最终的最优方案，将各基变量的取值列于表27中。表27 食品公司的食品最优调运量方案（单位：百元/吨）单仓位库产匚介、B1B2B3B4产量A13352157650A2752522031560A322554525存储量60402015苴中 x = 35 ， x = 15 ， x = 25 ， x = 20 ， x = 15 ， x = 2111222232431其余的xij = 0最小运输费用