实训六__商品配送运输成本最小化

46 商品配送商品配送 实训六实训六 软件求解配送运输成本最小化问题 指派问题 软件求解配送运输成本最小化问题 指派问题 一 实验目的 熟悉 WinQSB 软件 LP ILP 子系统界面内容 掌握操作命令 能够用 WinQSB 软件求 解配送运输与相似问题 二 实验平台和环境 Windows9X ME NT 2000 XP 平台 三 实验内容和要求 建立运输与指派新问题 使用 WinQSB 软件输入模型 求解模型 并对问题的结果进 行简单分析 四 实验操作步骤 实例操作 例例 6 1 某公司经销甲产品 它下设三个加工厂 每日的产量分别是 A1为 7 吨 A2 为 4 吨 A3为 9 吨 该公司把这些产品从配送中心分别运往四个销售点 各销售点每日销 量为 B1为 3 吨 B2为 6 吨 B3为 5 吨 B4为 6 吨 已知从各工厂到各销售点的单位产 品的运价为表 5 3 所示 问该公司应如何调运产品 在满足各销售点的需要量的前提下 使总运费为最少 销售点 加工厂 B1B2B3B4产 量 A13113107 A219284 A3741059 销 量3656 表 6 3 单位运价表 1 启动程序 点击开始程序WinQSB Network Modeling 屏幕显示如图 5 11 所示的网络模型工作界面 图 6 11 网络模型的工作界面 2 建立新问题或打开磁盘中已有的文件 按点击 FileNew Problem 或直接点击工具 栏的按钮建立新问题 屏幕上出现如图 6 12 所示的问题选项输入界面 47 图 6 12 建立新运输问题 此处问题类型 Problem Type 共有 7 种 Network Flow 网络流问题 Transportation Problem 运输问题 Assignment Problem 指派问题 Shortest Path Problem 最短路问题 Maximal Flow Problem 最大流问题 Minimal Spanning Tree 最小支撑树问题 Travel Salesman Problem 旅行销售员问题 中国邮递员问题 输入运输问题在此处应当选 Transportation Problem 本例中有三个生产点 Number of Sources 和四个销售点 Number of Destinations 也在此处输入 本例为求最小运费 所以在 Objective Criterion 目标函数标准 中选择 Minimization 此外 数据输入格式 Data Entry Format 可以选择电子表格模式 Spreadsheet Matrix Form 与图形模式 Graphic Model Form 3 输入数据 在选择数据输入格式时 选择 Spreadsheet Matrix Form 则以电子表格矩 阵形式输入单位运价系数矩阵和各地产量与销量 是固定格式 如表 6 4 所示 表 6 4 电子表格矩阵形式输入数据 数据输入方法与其它规划问题输入数据时相同 请参看实验二的相应内容 另外 数 据输入后 如果需要修改 增减等处理 也可以实现 同样请参看实验二中的相关内容 4 求解模型 点击菜单栏 Solve and Analyze 下拉菜单有四个选项 48 直接求解 Solve the Problem 用网络图形式求解并显示求解步骤 Solve and Display Steps Network 用表上作业法求解并显示求解步骤 Solve and Display Steps Tableau 选择求初始解的方法 Select Initial Solution Method 本例可以先选择求初始解的方法 具体过程参看 5 4 2 相关内容 可以选择伏格尔法 Vogel s Approximation Method 来求解初始解 点击 OK 后 即可进入下面的计算过程 以下可以选择 三种方法来求解这个运输问题的最优解 1 直接求最优解 选择 Solve the Problem 或直接点击工具栏上的 系统直接显 示求解的综合报告如表 5 5 所示 表中的各项含义见常见术语表 5 9 表 6 5 最优解综合报告表 本例得到最小运费支出为 85 运输方案见表 6 5 2 用网络图形式求解并显示求解步骤 用网络图形式分步求解可以明确每一步的优 化结果 选择 Solve and AnalyzeSolve and Display Steps Network 系统显示网络图形解 题第一步的求解结果 如图 5 13 所示 图 6 13 Graphic Solution Iteration 1 49 继续选择 IterationNext Iteration 或点击工具栏 得到第二步的求解结果 如 图 6 14 所示 图 6 14 Graphic Solution Iteration 2 虽然只进行了两步运算 但由于选择了伏格尔法寻找初始解 第二步显示的结果已是 最终结果 Final 了 再次选择 IterationNext Iteration 或点击工具栏 即可得到表 格式的求解结果 如表 6 3 所示 3 并显示求解步骤 点击 Solve and AnalyzeSolve and Display Steps Tableau 软件将用表上作业法求解问题 第一步得到如图 6 15 的结果 50 图 6 15 Transportation Tableau Iteration 1 这里得到了一个目标函数值 86 即运费 但它还不是最小运费 图 5 15 中显示了对 运量的调整 即将 Source 2 运到 Destination 3 的运量 1 转运到 Destination 1 其周边运量也 相应调整 运费还能下降 继续选择 IterationNext Iteration 或点击工具栏 得到第 二步的求解结果 如图 6 16 所示 图 5 16 Transportation Tableau Iteration 2 51 第二步显示的结果已是最终结果 Final 了 再次选择 IterationNext Iteration 或点 击工具栏 即可得到表格式的求解结果 如表 5 5 所示 至此 本运输问题求解完毕 最小运费为 85 5 保存结果 求解后可以保存结果 点击 FileSave As 系统以文本格式存储计算 结果 还可以打印结果 6 将计算表格转换成 Excel 表格 先清空剪贴板 在计算结果界面中点击 FileCopy to Clipboard 系统将计算结果复制到剪贴板 再粘贴到 Excel 表格中保存即可 例例 6 2 有一份中文说明书 需译成英 日 德 俄四种文字 分别记作 E J G R 现有甲 乙 丙 丁四人 他们将中文说明书翻译成不同语种的说明书所需 时间如表 5 6 所示 问应指派何人去完成何工作 使所需总时间为最少 任务 人员 EJGR 甲215134 乙1041415 丙9141613 丁78119 表 6 6 1 启动程序 点击开始程序WinQSB Network Modeling 屏幕显示如图 5 11 所示的网络模型工作界面 2 建立新问题或打开磁盘中已有的文件 按点击 FileNew Problem 或直接点击工具 栏的按钮建立新问题 屏幕上出现如图 6 17 所示的问题选项输入界面 52 图 6 17 建立新指派问题 输入指派问题在此处应当选 Assignment Problem 本例中有四项任务 Number of Objects 和四个翻译 Number of Assignments 也在此处输入 本例为求最少翻译时间 所以在 Objective Criterion 目标函数标准 中选择 Minimization 此外 数据输入格式 Data Entry Format 可以选择电子表格模式 Spreadsheet Matrix Form 与图形模式 Graphic Model Form 3 输入数据 在选择数据输入格式时 选择 Spreadsheet Matrix Form 则以电子表格矩 阵形式输入各人翻译成不同语种的说明书所需的时间 如表 5 7 所示 表 6 7 电子表格形式输入指派问题数据 4 求解模型 点击菜单栏 Solve and Analyze 下拉菜单有四个选项 直接求解 Solve the Problem 用网络图形式求解并显示求解步骤 Solve and Display Steps Network 用表上作业法求解并显示求解步骤 Solve and Display Steps Tableau 选择求初始解的方法 Select Initial Solution Method 以下可以选择 三种方法来求解这个运输问题的最优解 1 直接求最优解 选择 Solve the Problem 或直接点击工具栏上的 系统直接显 示求解的综合报告如表 5 8 所示 表中的各项含义见常见术语表 5 9 表 6 8 指派问题最优解综合报告表 本例得到最少花费时间为 28 具体指派方案见表 6 8 2 用网络图形式求解并显示求解步骤 用网络图形式分步求解可以明确每一步的优 化结果 选择 Solve and AnalyzeSolve and Display Steps Network 系统显示网络图形解 题第一步的求解结果 如图 5 18 所示 53 图 6 18 Graphic Solution Iteration 1 继续选择 IterationNext Iteration 或点击工具栏 得到第二步的求解结果 如图 5 19 所示 图 6 19 Graphic Solution Iteration 2 54 此时 第二步显示的结果已是最终结果 Final 了 再次选择 IterationNext Iteration 或点击工具栏 即可得到表格式的求解结果 如表 6 8 所示 3 用表上作业法求解并显示求解步骤 具体方法与例 6 1 基本一致 此处略 5 保存结果 结果保存方法与例 6 1 一致 请参看相关内容 五 数据处理和分析 在计算结束后 可以对数据及结果进行分析 读入例 6 2 FileLoad Problem 执 行解题 Solve and AnalyzeSolve the Problem 点击菜单栏 result 或点击工具栏 下拉 菜单有以下选项 1 只显示非零的解 Solution Table Nonzero Only 2 显示所有解 Solution Table All 3 网络图形式的解 Graphic Solution 直观地显示的指派的最优方案 55 4 最优性范围 Range of Optimality 表示了每一个人去做每一项任务在时间上的 花费 56 六 分析讨论题 1 用 WinQSB 软件求解下列运输问题的最优解 销售点 加工厂 B1B2B3B4产 量 A137645 A224322 A343853 销 量3322 销售点 加工厂 B1B2B3B4B5产 量 A1102059105 A221083064 A312071042 A4863759 销 量44624 2 用 WinQSB 软件求解下列指派问题 四个工人指派四项工作 下表为每人做各项工作所消耗的时间 问应如何分配 才能使总的消耗时间为最少 工种 工人 ABCD 甲15182124 乙19232218 丙26171619 丁19212317 有 5 人去做 5 项工作 每人做各项工作的能力评分见下表 应如何分派 才能 使总的得分为最大