运筹学课程设计目录第一章自编题一、运输规划问题包头市某冰箱工厂有三个分厂，生产同一种冰箱，供应该厂在市内的四个门市部销售。
已知三个分厂的日生产能力分别是50、60、50台。
四个门市部的日销售量分别是40、40、60、20台。
从各个分厂运往各门市部的运费如表1-11所示。
试安排一个运费最低的运输计划。
表1-11解,（1）运用最小元素法求解，得初始基本可行解，如下表1-12表1-12（2）用位势法计算所有非基变量检验数，求得如下表1-13表1-13（3）利用闭回路法进一步求解：表1-14（4）得出新方案，如表1-15表1-15（5）经检验所有空格的检验数均大于等于零，故此方案为最优解。
最优解为：X13=30，X14=20，X22=30，X23=30，X31=40，X32=10最优方案运费Z=30×9+20×6+30×3+30×7+40×6+10×4=970元（6）运用软件进行检验：最优解如下********************************************起至销点发点 1 2 3 41 0 0 30 202 0 30 30 03 40 10 0 0此运输问题的成本或收益为: 970二、指派问题现有四项不同的任务，分别由四个人去完成。
因四个人的专长不同，所以每个人完成的任务所需的时间也不同(如表1-21),试问如何安排他们的工作才能使总的工作时间最少？表1-21 （单位：小时）解：（1）变换效率系数矩阵，使其每行没列都出现0元素10 9 7 8 （-7） 3 2 0 1C ij = 5 8 7 7 （-5） 0 3 2 25 46 5 （-4） 1 0 2 52 3 4 5（-2） 0 1 2 3（2）进行试指派3 2 0 10 3 2 21 02 50 1 2 3（3）作最少的直线覆盖所有的0元素，以确定该系数矩阵中能找到最多0元素3 2 0 10 3 2 21 02 50 1 2 3（4）对矩阵进行变换，以增加0元素3 2 0 14 2 0 00 3 2 2 0 2 1 01 02 5 2 0 2 00 1 2 3 0 0 1 1（5）重复第二步，找到最优解4 2 0 0 4 2 0 00 2 1 0 或 0 2 1 02 0 2 0 2 0 2 00 0 1 1 0 0 0 1最优方案1：乙→1，丁→2，甲→3，丙→4最少时间Z=7+5+5+3=20小时最优方案2：丁→1，丙→2，甲→3，乙→4最少时间Z=7+7+4+2=20小时因为软件原因，无法进行检验三、最小支撑树问题某网络公司为沿着友谊大街8个居民点架设网线，连接8个居民点的道路如图1-31所示，边表示可架设网络道路，边权为道路的长度，设计一网线网络连通这8个居民点，并使总的输电线长度最短。
图1-311 2 673 54 8解：（1）利用破圈法求解：图1-321 2 673 54 8图1-331 2 673 54 8图1-341 2 673 54 8图1-351 2 673 54 8图1-361 2 673 54 8图1-371 2 673 54 8至此，无圈，图1-37为最小树，各边权之和为18,或如下1-38图：各边权之和也为18图1-381 2 673 54 8（2）运用软件进行检验：此问题的最小生成树如下：*************************起点终点距离---- ---- ----1 3 23 4 21 2 42 5 25 7 37 8 27 6 3此问题的解为:18第二章上机题一、线性规划1. max z =s. t.运算检验：目标函数最优值为 : 21变量最优解相差值 5 03 0约束松弛剩余变量对偶价格 1 0 .73 0 .84 5 0目标函数系数范围 :变量下限当前值上限X1 1 3 无上限X2 -1.5 2 6常数项数范围 :约束下限当前值上限1 12 22 26.2862 7 10 无上限3 4.5 7 124 -4 1 无上限2. max z=s.t.运算检验：目标函数最优值为 : 31变量最优解相差值13 05 0约束松弛剩余变量对偶价格2 9 03 0 .54 0 .5目标函数系数范围 :变量下限当前值上限1 2 3.667 1 2常数项数范围 :约束下限当前值上限1 5 10 无上限2 51 60 无上限3 14.667 18 19.3854 38 44 543. min z=s.t.运算检验：目标函数最优值为 : 55变量最优解相差值2 01 0约束松弛剩余变量对偶价格1 0 -52 7 03 0 -10目标函数系数范围 :变量下限当前值上限15 20 3010 15 20常数项数范围 :约束下限当前值上限1 3.6 5 62 -43 无上限3 2.5 3 44． max z=s.t.运算检验：目标函数最优值为 : 18变量最优解相差值21 024 00 2约束松弛剩余变量对偶价格1 0 12 0 13 7 0目标函数系数范围 :变量下限当前值上限限x2 -1.333 -1 无上限x3 无下限 1 3 常数项数范围 :约束下限当前值上限 1 -6 15 无上限2 无下限 -3 43 -34 无上限5. min z=s.t.,无约束，运算检验：目标函数最优值为 : 6变量最优解相差值2 00 00 3.286约束松弛剩余变量对偶价格1 8 02 0 -0.8573 0 0.143目标函数系数范围 :变量下限当前值上限无下限 1 1无下限 -2 1.286 常数项数范围 :约束下限当前值上限 1 4 12 无上限2 -6 8 83 6 6 无上限6.minz=-3x1+x2+x3-x4s.t．.运算检验：目标函数最优值为 : 7变量最优解相差值1 01 03 00 32.333约束松弛剩余变量对偶价格1 0 .6672 0 73 0 -11.667目标函数系数范围 :变量下限当前值上限无下限 -3 3.929 -6.462 1 无上限 -3.467 3 无上限 -33.333 -1 无上限常数项数范围 :约束下限当前值上限1 -3 0 无上限2 8 9 103 5.4 6 6.757. min z=s.t.(j=1, (4)运算检验：目标函数最优值为 : 5变量最优解相差值0 90 01 01 0约束松弛剩余变量对偶价格1 0 -22 0 3目标函数系数范围 :变量下限当前值上限-4 5 无上限 -2 -2 无上限3 3 无上限无下限 2 2常数项数范围 :约束下限当前值上限1 6 7 92 2.333 3 3.5二、运输问题8.下列表中的数据是某公司的甲、乙、丙三个分厂向公司所属四个门市部运送单位产品的运费。
请给出总运费最低的运费值。
表2-7运算检验：最优解如下********************************************起至销点发点 1 2 3 41 0 0 0 52 5 0 5 103 0 10 5 0此运输问题的成本或收益为: 2059.运输问题运算检验：最优解如下********************************************起至销点发点 1 2 3 41 5 0 0 12 03 2 03 0 0 2 6此运输问题的成本或收益为: 4710.运输问题运算检验：最优解如下********************************************起至销点发点 1 2 3 41 2 0 5 02 1 0 0 33 0 6 0 3此运输问题的成本或收益为: 7911.运输问题运算检验：最优解如下********************************************起至销点发点 1 2 3 41 0 0 7 02 12 0 13 03 0 10 0 15此运输问题的成本或收益为: 206三、最短路问题12.最短路问题ADS B TEC从节点S到节点T的最短路*************************起点终点距离---- ---- ----S A 4A B 1B D 5D T 6此问题的解为:1613.最短路问题1 3V1 V2 2 4运算检验：从节点 v1到节点v2的最短路*************************起点终点距离---- ---- ----7 1 91 3 13 6 3此问题的解为:1314.最短路问题V1 V2VsV3 V4运算检验：从节点 Vs到节点Vt的最大流*************************起点终点距离---- ---- ----Vs V1 2V1 V3 1V1 V2 2V3 V1 0V3 V4 0V2 V4 0V2 V3 0V2 Vt 3V4 Vt 0此问题的解为:3四、最大流问题15.最大流问题251 3 764从节点1到节点7的最大流*************************起点终点距离---- ---- ----1 2 701 3 501 4 302 5 302 6 403 5 504 6 305 7 806 7 70此问题的解为:15016.最大流问题A DS TB C运算检验：从节点 1到节点6的最大流*************************起点终点距离---- ---- ----S A 3S B 2A C 0B D 3B C 2C A 0C D 0C T 2D T 3此问题的解为:517.最小费用最大流问题s t2 3运算检验：从节点 4到节点5的最大流*************************起点终点流量费用---- ---- ---- ----s 1 4 1s 2 8 41 2 2 21 32 32 3 3 12 t 7 63 t 5 2此问题的最大流为:12此问题的最小费用为:10118.最小费用最大流问题1 2s t3 4运算检验：从节点 s到节点t的最大流*************************起点终点流量费用---- ---- ---- ----s 1 7 2s 2 8 101 32 71 2 5 32 3 5 12 4 8 43 4 5 23 t 10 94 t5 3此问题的最大流为:15此问题的最小费用为:275五、最小支撑树问题19.最小支撑树问题1 43 5 72 6运算检验：此问题的最小生成树如下：*************************起点终点距离---- ---- ----1 3 13 2 23 5 25 4 25 6 34 7 3此问题的解为:1320.最小支撑树问题21 3 5 74 6运算检验：此问题的最小生成树如下：*************************起点终点距离---- ---- ----1 2 22 3 23 4 13 6 36 5 15 7 5此问题的解为:14参考文献：《运筹学》作者：宋学峰东南大学出版社 2011年一月出版《运筹学基础及应用》作者：胡运权高等教育出版社 2008年6月出版《运筹学实用教程》作者：宁宣熙科学出版社 2007年4月出版。