运筹学课程设计

内蒙古科技大学课程设计 第 1 页 共 30 页 运筹学课程设计 内蒙古科技大学课程设计 第 2 页 共 30 页 目录 第一章 自编题 、运输规划问题 、指派问题 、最小数问题 二章 上机题 、线性规划问题 、运输问题 01、最短路问题 234、最大流问题 567蒙古科技大学课程设计 第 3 页 共 30 页 18、最小支撑树问题 90考文献 一章 自编题 一、 运输规划问题 内蒙古科技大学课程设计 第 4 页 共 30 页 包头市某冰箱工厂有三个分厂，生产同一种冰箱， 供应该厂在市内的四个门市部销售。已知三个分厂的日生产能力分别是 50、 60、 50 台。四个门市部 的日销售量分别是 40、 40、 60、 20 台。从各个分厂运往各门市部的运费如表 1安排一个运费最低的运输计划。 表 1 2 3 4 供应量总计 1 9 12 9 6 50 2 7 3 7 7 60 3 6 5 9 11 50 需求量总计 40 40 60 20 解 ,（ 1） 运用最小元素法求解 ， 得初始基本可行解，如下 表 1 1 2 3 4 产量 1 9 12 9 30 6 20 50 2 7 3 40 7 20 7 60 3 6 40 4 9 10 11 50 销量 40 40 60 20 （ 2） 用位势法计算所有非基变量检验数 ，求得如下 表 1 1 市 部 工 厂 销 地 产 地 内蒙古科技大学课程设计 第 5 页 共 30 页 1 2 3 4 产量 1 9 （ 3） 12 （ 8） 9 30 6 20 50 2 7 （ 3） 3 40 7 20 7 （ 3） 60 3 6 40 4 （ 9 10 11 （ 5） 50 销量 40 40 60 20 （ 3） 利用闭回路法 进一步求解： 表 1 2 3 4 产量 1 9 （ 3） 12 （ 8） 9 30 6 20 50 2 7 （ 3） 3 40 7 + 20 7 （ 3） 60 3 6 40 4 + （ 9 10 11 （ 5） 50 销量 40 40 60 20 （ 4） 得出新方案，如 表 1 1 地 产 地 销 地 产 地 - - 内蒙古科技大学课程设计 第 6 页 共 30 页 1 2 3 4 产量 1 9 12 9 30 6 20 50 2 7 3 30 7 30 7 60 3 6 40 4 10 9 11 50 销量 40 40 60 20 （ 5） 经检验所有空格的检验数均大于等 于 零，故此方案为最优解。 最优解为： 0， 0， 0， 0， 0， 0 最优方案运费 Z=30 9+20 6+30 3+30 7+40 6+10 4=970元 （ 6）运用软件进行检验： 最优解如下 * 起 至 销点 发点 1 2 3 4 1 0 0 30 20 2 0 30 30 0 3 40 10 0 0 此运输问题的成本或收益为 : 970 二、指派问题 现有四项不同的任务，分别由四个人去完成。因四个人的专长不同，所以销 地 产 地 内蒙古科技大学课程设计 第 7 页 共 30 页 每个人完成的任务所需的时间 也不同 (如 表 1试问如何安排他们的工作才能使总的工作时间最少？ 表 1 （ 单位：小时） 1 2 3 4 甲 10 9 7 8 乙 5 8 7 7 丙 5 4 6 5 丁 2 3 4 5 解： （ 1）变换效率系数矩阵，使其每行没列都出现 0元素 10 9 7 8 （ 3 2 0 1 = 5 8 7 7 （ 0 3 2 2 5 4 6 5 （ 1 0 2 5 2 3 4 5 （ 0 1 2 3 （ 2）进行试指派 3 2 0 1 0 3 2 2 1 0 2 5 0 1 2 3 （ 3）作最少的直线覆盖所有 的 0 元素，以确定该系数矩阵中能找到最多 0元素 3 2 0 1 0 3 2 2 1 0 2 5 0 1 2 3 （ 4）对矩阵进行变换，以增加 0元素 工 作 人 内蒙古科技大学课程设计 第 8 页 共 30 页 3 2 0 1 4 2 0 0 0 3 2 2 0 2 1 0 1 0 2 5 2 0 2 0 0 1 2 3 0 0 1 1 （ 5）重复第二步，找到最优解 4 2 0 0 4 2 0 0 0 2 1 0 或 0 2 1 0 2 0 2 0 2 0 2 0 0 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示，边表示可架设网络道路，边权为道路的长度，设计一 网线网络连通这 8个居民点，并使总的输电线长度最短。 图 1 2 6 7 3 5 4 8 解：（ 1）利用破圈法求解： 4 5 3 2 2 4 7 6 5 2 3 2 内蒙古科技大学课程设计 第 9 页 共 30 页 图 1 2 6 7 3 5 4 8 图 1 2 6 7 3 5 4 8 图 1 2 6 7 3 5 4 8 图 1 2 6 7 3 5 4 8 4 5 3 2 2 4 7 6 5 2 3 2 4 5 3 2 2 4 6 5 2 3 2 4 5 3 2 2 4 5 2 3 2 4 3 2 2 4 5 2 3 2 内蒙古科技大学课程设计 第 10 页 共 30 页 图 1 2 6 7 3 5 4 8 图 1 2 6 7 3 5 4 8 至此，无圈，图 1边权之和为 18,或如下 1边权之和也为 18 图 1 2 6 7 3 5 4 8 （ 2）运用软件进行检验： 此问题的最小生成树如下： * 起点 终点 距离 3 2 2 4 2 3 2 3 2 2 4 2 3 2 4 3 2 2 2 3 2 内蒙古科技大学课程设计 第 11 页 共 30 页 1 3 2 3 4 2 1 2 4 2 5 2 5 7 3 7 8 2 7 6 3 此问题的解为 :18 第二章 上机题 一、线性规划 1. z = 21 23 2242 21 104 21 s. t. 721 13 21 0, 21 运算检验： 目标函数最优值为 : 21 变量 最优解 相差值 x 5 0 2x 3 0 约束 松弛 /剩余变量 对偶价格 0 3 0 内蒙古科技大学课程设计 第 12 页 共 30 页 3 0 5 0 目标函数系数范围 : 变量 下限 当前值 上限 1 1 3 无上限 2 6 常数项数范围 : 约束 下限 当前值 上限 12 22 7 10 无上限 3 7 12 4 1 无上限 2. z= 212 2x 10 6052 21 1x 182 x 443 21 0, 21 运算检验： 目标函数最优值为 : 31 变量 最优解 相差值 x 13 0 2x 5 0 约束 松弛 /剩余变量 对偶价格 内蒙古科技大学课程设计 第 13 页 共 30 页 5 0 2 9 0 3 0 0 标函数系数范围 : 变量 下限 当前值 上限 x 1 2 3 2x 1 2 常数项数范围 : 约束 下限 当前值 上限 5 10 无上限 2 51 60 无上限 3 18 38 44 54 3. z= 21 1520 52 21 322 21 321 0, 21 运算 检验： 目标函数最优值为 : 55 变量 最优解 相差值 x 2 0 内蒙古科技大学课程设计 第 14 页 共 30 页 2x 1 0 约束 松弛 /剩余变量 对偶价格 0 7 0 3 0 标函数系数范围 : 变量 下限 当前值 上限 x 15 20 30 2x 10 15 20 常数项数范围 : 约束 下限 当前值 上限 5 6 2 3 无上限 3 3 4 4 z=3212 15223321 3321 321 目标函数最优值为 : 18 变量 最优解 相差值 x 21 0 内蒙古科技大学课程设计 第 15 页 共 30 页 2x 24 0 3 2 约束 松弛 /剩余变量 对偶价格 0 1 2 0 1 3 7 0 目标函数系数范围 : 变量 下限 当前值 上限 2 无上限 无上限 无下限 1 3 常数项数范围 : 约束 下限 当前值 上限 15 无上限 2 无下限 4 3 4 无上限 5. z=31 23 12x 124332 82431 , 2x 无约束， 03 目标函数最优值为 : 6 内蒙古科技大学课程设计 第 16 页 共 30 页 变量 最优解 相差值 x 2 0 2x 0 0 3 束 松弛 /剩余变量 对偶价格 8 0 2 0 0 标函数系数范围 : 变量 下限 当前值 上限 x 3 无上限 2x 无下限 1 1 3 数项数范围 : 约束 下限 当前值 上限 4 12 无上限 2 8 8 3 6 6 无上限 3x1+x2+x 0432 933224321 第 17 页 共 30 页 . 62321 , 4321 运算检验： 目标函数最优值为 : 7 变量 最优解 相差值 x 1 0 2x 1 0 3 0 4x 0 束 松 弛 /剩余变量 对偶价格 0 0 7 3 0 标函数系数范围 : 变量 下限 当前值 上限 x 无下限 x 1 无上限 3 无上限 4x 无上限 常数项数范围 : 约束 下限 当前值 上限 0 无上限 2 8 9 10 3 6 . z=4321 2325 74324321 第 18 页 共 30 页 32224321 jx(j=1, ,4) 运算检验： 目标函数最优值为 : 5 变量 最优解 相差值 x 0 9 2x 0 0 3 0 4x 1 0 约束 松弛 /剩余变量 对偶价格 0 0 3 目标函数系数范围 : 变量 下限 当前值 上限 x 5 无上限 2x 无上限 3 3 无上限 4x 无下限 2 2 常数项数范围 : 约束 下限 当前值 上限 6 7 9 2 3 蒙古科技大学课程设计 第 19 页 共 30 页 二、运输问题 、丙三个分厂向公司所属四个门市 部运送单位产品的运费。请给出总运费最低的运费值。 表 2 2 3 4 供应量 甲 8 2 9 7 5 乙 5 2 3 8 20 丙 15 1 8 15 15 需求 5 10 10 15 运算检验： 最优解如下 * 起 至 销点 发点 1 2 3 4 1 0 0 0 5 2 5 0 5 10 3 0 10 5 0 此运输问题的成本或收益为 : 205 2 4 供应量 11 4 4 6 销 地 产 地 销 地 产 地 内蒙古科技大学课程设计 第 20 页 共 30 页 0 3 5 9 5 8 1 2 8 需求量 5 3 4 7 运算检验： 最优解如下 * 起 至 销点 发点 1 2 3 4 1 5 0 0 1 2 0 3 2 0 3 0 0 2 6 此运输问题的成本或收益为 : 47 2 4 供应量 11 3 10 7 9 2 6 4 4 10 5 9 需求量 3 6 5 6 运算检验： 最优解 如下 * 起 至 销点 发点 1 2 3 4 1 2 0 5 0 2 1 0 0 3 3 0 6 0 3 此运输问题的成本或收益为 : 79 销 地 产 地 内蒙古科技大学课程设计 第 21 页 共 30 页 2 4 供应量 4 1 2 7 9 4 7 25 3 4 3 26 需求量 10 10 20 15 运算检验： 最优解如下 * 起 至 销点 发点 1 2 3 4 1 0 0 7 0 2 12 0 13 0 3 0 10 0 15 此运输问题的成本或收益为 : 206 三、最短路问题 A D S B T E C 从节点 的最短路 * 起点 终点 距离 A 4 A B 1 4 6 5 1 2 7 5 4 1 6 8 5 销 地 产 地 内蒙古科技大学课程设计 第 22 页 共 30 页 B D 5 D T 6 此问题的解为 :16 1 3 4 运算检验： 从节点 * 起点 终点 距离 1 9 1 3 1 3 6 3 此问题的解为 :13 s 算检验： 从节点 * 起点 终点 距离 8 1 2 8 5 7 7 3 4 3 10 5 2 1 3 2 3 5 1 4 2 蒙古科技大学课程设计 第 23 页 共 30 页 2 1 2 0 0 0 0 3 0 此问题的解为 :3 四、最大流问题 2 5 1 3 7 6 4 从节点 1 到节点 7 的最大流 * 起点 终点 距离 2 70 1 3 50 1 4 30 2 5 30 2 6 40 3 5 50 4 6 30 5 7 80 6 7 70 此问题的解为 :150 50 50 40 40 30 60 70 70 80 内蒙古科技大学课程设计 第 24 页 共 30 页 题 A D S T B C 运算检验： 从节点 1到节点 6的最大流 * 起点 终点 距离 A 3 S B 2 A C 0 B D 3 B C 2 C A 0 C D 0 C T 2 D T 3 此问题的解为 :5 大流问题 s t 2 3 （ 0,4） （ 0,5） （0,1） （ 0,3） （ 0,2） (0,1) (0,2)(0,5) (0,2) (4,1) (7,6) (8,4) (3,2) (6,1) (2,3) (5,2) 1 内蒙古科技大学课程设计 第 25 页 共 30 页 运算检验： 从节点 4到节点 5的最大流 * 起点 终点 流量 费用 s 1 4 1 s 2 8 4 1 2 2 2 1 3 2 3 2 3 3 1 2 t 7 6 3 t 5 2 此问题的最大流为 :12 此问题的最小费用为 :101 1 2 s t 3 4 运算检验： 从节点 * 起点 终点 流量 费用 s 1 7 2 s 2 8 10 1 3 2 7 (10,10) (7,2) (7,7) (8,4) (5,3) (7,2) (5,1) （ 10,9） （ 5,3） 内蒙古科技大学课程设计