运筹学课程设计.doc

内蒙古科技大学课程设计运筹学课程设计目录第一章 自编题-1一、运输规划问题-1二、指派问题-4三、最小数问题-5第二章 上机题-8 一、线性规划问题-8 1-82-93-104-115-126-147-15 二、运输问题-168-159-1710-1711-18 三、最短路问题-1812-1813-1914-19 四、最大流问题-2015-2016-2117-2118-22 五、最小支撑树问题-2319-2320-24参考文献-24第一章自编题一、运输规划问题包头市某冰箱工厂有三个分厂，生产同一种冰箱，供应该厂在市内的四个门市部销售。已知三个分厂的日生产能力分别是50、60、50台。四个门市部的日销售量分别是40、40、60、20台。从各个分厂运往各门市部的运费如表1-11所示。试安排一个运费最低的运输计划。表1-11门市部工厂123 4供应量总计19129650273776036591150需求量总计40406020解,（1）运用最小元素法求解，得初始基本可行解，如下表1-12表1-12销地产地1234产量19 12 9 30 6 20502 7 3 40 7 20 7603 6 40 4 9 10 1150销量40406020（2）用位势法计算所有非基变量检验数，求得如下表1-13表1-13销地产地1234产量19 （3） 12 （8） 9 30 6 20502 7 （3） 3 40 7 20 7 （3）603 6 40 4 （-1） 9 10 11 （5）50销量40406020（3）利用闭回路法进一步求解：表1-14销地产地1234产量19 （3） 12 （8） 9 30 6 20502- 7 （3） 3 40 7 + 20 7 （3）603 6 40 4 + （-1）- 9 10 11 （5）50销量40406020（4）得出新方案，如表1-15表1-15销地产地1234产量19 12 9 30 6 20502 7 3 30 7 30 7603 6 40 4 10 9 1150销量40406020（5）经检验所有空格的检验数均大于等于零，故此方案为最优解。最优解为：X13=30，X14=20，X22=30，X23=30，X31=40，X32=10最优方案运费Z=309+206+303+307+406+104=970元（6）运用软件进行检验：最优解如下* 起 至 销点 发点 1 2 3 4 - - - - - 1 0 0 30 20 2 0 30 30 0 3 40 10 0 0此运输问题的成本或收益为: 970二、指派问题现有四项不同的任务，分别由四个人去完成。因四个人的专长不同，所以每个人完成的任务所需的时间也不同(如 表1-21),试问如何安排他们的工作才能使总的工作时间最少？ 表1-21 （单位：小时）工作人1234甲10978乙5877丙5465丁2345解：（1）变换效率系数矩阵，使其每行没列都出现0元素 10 9 7 8 （-7） 3 2 0 1Cij = 5 8 7 7 （-5） 0 3 2 2 5 4 6 5 （-4） 1 0 2 5 2 3 4 5 （-2） 0 1 2 3 （2）进行试指派3 2 0 10 3 2 21 0 2 50 1 2 3（3）作最少的直线覆盖所有的0元素，以确定该系数矩阵中能找到最多0元素3 2 0 10 3 2 2 1 0 2 50 1 2 3 （4）对矩阵进行变换，以增加0元素3 2 0 1 4 2 0 00 3 2 2 0 2 1 01 0 2 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个居民点，并使总的输电线长度最短。54图1-31223 1 2 634 725623 57 4 8解：（1）利用破圈法求解：54图1-32223 1 2 634 725623 57 4 854图1-33223 1 2 634 725623 5 4 854图1-34223 1 2 634 72523 5 4 84图1-35223 1 2 634 72523 5 4 84图1-36223 1 2 634 7223 5 4 8图1-37223 1 2 634 7223 5 4 8至此，无圈，图1-37为最小树，各边权之和为18,或如下1-38图：各边权之和也为184图1-3823 1 2 623 7223 5 4 8（2）运用软件进行检验：此问题的最小生成树如下：* 起点 终点 距离 - - - 1 3 2 3 4 2 1 2 4 2 5 2 5 7 3 7 8 2 7 6 3此问题的解为:18第二章 上机题 一、线性规划1. max z = s. t. 运算检验：目标函数最优值为 : 21 变量 最优解 相差值 - - - 5 0 3 0 约束 松弛/剩余变量 对偶价格 - - - 1 0 .7 2 3 0 3 0 .8 4 5 0 目标函数系数范围 : 变量 下限 当前值 上限 - - - - X1 1 3 无上限 X2 -1.5 2 6 常数项数范围 : 约束 下限 当前值 上限 - - - - 1 12 22 26.286 2 7 10 无上限 3 4.5 7 12 4 -4 1 无上限2. max z= s.t. 运算检验：目标函数最优值为 : 31 变量 最优解 相差值 - - - 13 0 5 0 约束 松弛/剩余变量 对偶价格 - - - 1 5 0 2 9 0 3 0 .5 4 0 .5 目标函数系数范围 : 变量 下限 当前值 上限 - - - - 1 2 3 .667 1 2 常数项数范围 : 约束 下限 当前值 上限 - - - - 1 5 10 无上限 2 51 60 无上限 3 14.667 18 19.385 4 38 44 543. min z= s.t. 运算检验：目标函数最优值为 : 55 变量 最优解 相差值 - - - 2 0 1 0 约束 松弛/剩余变量 对偶价格 - - - 1 0 -5 2 7 0 3 0 -10 目标函数系数范围 : 变量 下限 当前值 上限 - - - - 15 20 30 10 15 20 常数项数范围 : 约束 下限 当前值 上限 - - - - 1 3.6 5 6 2 -4 3 无上限 3 2.5 3 44 max z= s.t. 运算检验：目标函数最优值为 : 18 变量 最优解 相差值 - - - 21 0 24 0 0 2 约束 松弛/剩余变量 对偶价格 - - - 1 0 1 2 0 1 3 7 0 目标函数系数范围 : 变量 下限 当前值 上限 - - - - x1 1.5 2 无上限 x2 -1.333 -1 无上限 x3 无下限 1 3 常数项数范围 : 约束 下限 当前值 上限 - - - - 1 -6 15 无上限 2 无下限 -3 4 3 -3 4 无上限5. min z= s.t. ,无约束，运算检验：目标函数最优值为 : 6 变量 最优解 相差值 - - - 2 0 0 0 0 3.286 约束 松弛/剩余变量 对偶价格 - - - 1 8 0 2 0 -0.857 3 0 0.143 目标函数系数范围 : 变量 下限 当前值 上限 - - - - -1.6 3 无上限 无下限 1 1 无下限 -2 1.286 常数项数范围 : 约束 下限 当前值 上限 - - - - 1 4 12 无上限 2 -6 8 8 3 6 6 无上限6.minz=-3x1+x2+x3-x4 s.t. 运算检验：目标函数最优值为 : 7 变量 最优解 相差值 - - - 1 0 1 0 3 0 0 32.333 约束 松弛/剩余变量 对偶价格 - - - 1 0 .667 2 0 7 3 0 -11.667 目标函数系数范围 : 变量 下限 当前值 上限 - - - - 无下限 -3 3.929 -6.462 1 无上限 -3.467 3 无上限 -33.333 -1 无上限 常数项数范围 : 约束 下限 当前值 上限 - - - - 1 -3 0 无上限 2 8 9 10 3 5.4 6 6.757. min z= s.t. (j=1,4)运算检验：目标函数最优值为 : 5 变量 最优解 相差值 - - - 0 9 0 0 1 0 1 0 约束 松弛/剩余变量 对偶价格 - - - 1 0 -2 2 0 3 目标函数系数范围 : 变量 下限 当前值 上限 - - - - -4 5 无上限 -2 -2 无上限 3 3 无上限 无下限 2 2 常数项数范围 : 约束 下限 当前值 上限 - - - - 1 6 7 9 2 2.333 3 3.5 二、运输问题8.下列表中的数据是某公司的甲、乙、丙三个分厂向公司所属四个门市部运送单位产品的运费。请给出总运费最低的运费值。表2-7销地产地1234供应量甲82975乙523820丙15181515需求5101015运算检验：最优解如下* 起 至 销点 发点 1 2 3 4 - - - - - 1 0 0 0 5 2 5 0 5 10 3 0 10 5 0此运输问题的成本或收益为: 2059.运输问题销地产地B1B2B3B4供应量A1211446A2103595A378128需求量5347运算检验：最优解如下* 起 至 销点 发点 1 2 3 4 - - - - - 1 5 0 0 1 2 0 3 2 0 3 0 0 2 6此运输问题的成本或收益为: 4710.运输问题销地产地B1B2B3B4供应量A13113107A219264A3741059需求量3656运算检验：最优解如下* 起 至 销点 发点 1 2 3 4 - - - - - 1 2 0 5 0 2 1 0 0 3 3 0 6 0 3此运输问题的成本或收益为: 7911.运输问题销地产地B1B2B3B4供应量A184127A2694725A3534326需求量10102015运算检验：最优解如下* 起 至 销点 发点 1 2 3 4 - - - - - 1 0 0 7 0 2 12 0 13 0 3 0 10 0 15此运输问题的成本或收益为: 206三、最短路问题12.最短路问题7 A65164 D145 S B T82 E5 C 从节点S到节点T的最短路* 起点 终点 距离 - - - S A 4 A B 1 B D 5 D T 6此问题的解为:1613.最短路问题3475219 1 3510388 V1