(1)若要总运费最少，该方案是否为最优方案? (2)若产地Z的供应量改为100，求最优方案。
4、某利润最大的运输问题，其单位利润如下表所示： A1 A2 A3 需要量 B1 （6） （4） （2） 8 B2 （7） （5） （9） 6 B3 （5） （10） （7） 5 B4 （8） （8） （3） 5 供应量 8 9 7 24 (1)求最优运输方案，该最优方案有何特征?
(2)当A1的供应量和B3的需求量各增加2时，结果又怎样?
5、某玩具公司分别生产三种新型玩具，每月可供量分别为1000、2000、2000件，它们分别被送到甲、乙、丙三个百货商店销售。已知每月百货商店各类玩具预期销售量均为1500件，由于经营方面原因，各商店销售不同玩具的盈利额不同,见下表。又知丙百货商店要求至少供应C玩具1000件，而拒绝进A玩具。求满足上述条件下使总盈利额最大的供销分配方案。
甲 乙 丙 可供量
A 5 4 － 1000 B 16 8 9 2000 C 12 10 11 2000
6、目前，城市大学能存贮200个文件在硬盘上，100个文件在计算机存贮器上，300个文件在磁带上。用户想存贮300个字处理文件，100个源程序文件，100个数据文件。每月，一个典型的字处理文件被访问8次，一个典型的源程序文件被访问4次，一个典型的数据文件被访问2次。当某文件被访问时，重新找到该文件所需的时间取决于文件类型和存贮介质，如下表。
时 间（分钟） 处理文件 源程序文件 数据文件
硬盘 5 4 4 存贮器 2 1 1 磁带 10 8 6
如果目标是极小化每月用户访问所需文件所花的时间，请构造一个运输问题的模型来决定文件应该怎么存放并求解。
7、已知下列五名运动员各种姿势的游泳成绩（各为50米）如表5-2：试用运输问题的方法来决定如何从中选拔一个参加200混合泳的接力队，使预期比赛成绩为最好。
仰 泳 蛙 泳 蝶 泳 自由泳 赵 37.7 43.4 33.3 29.2 钱 32.9 33.1 28.5 26.4 张 33.8 42.2 38.9 29.6 王 37.0 34.7 30.4 28.5 周 35.4 41.8 33.6 31.1
8、求总运费最小的运输问题，其中某一步的运输图如下表。 A1 A2 A3 需要量 B1 3（3） 2（4） （5） a B2 （5） 4（2） 1（6） b B3 （7） （4） 5（3） c 供应量 3 6 d e
16
（1）写出a,b,c,d,e的值，并求出最优运输方案；
（2）A3到B1的单位运费满足什么条件时，表中运输方案为最优方案。
9、 甲、乙两个煤矿分别生产煤500万吨，供应A、B、C三个电厂发电需要，各电厂用量分别为300、300、400万吨。已知煤矿之间、煤矿与电厂之间以及各电厂之间相互距离（单位：公里）如下列三个表所示。又煤可以直接运达，也可经转运抵达,试确定从煤矿到各电厂间煤的最优调运方案（最小总吨公里数）。
从 到 甲 乙 从 到 A B C 从 到 A B C 甲 0 120 甲 150 120 80 A 0 70 100 乙 100 0 乙 60 160 40 B 50 0 120
C 100 150 0
三、指派问题
例题 有一份中文说明书，需译成英、日、德、俄四种文字。分别记作E、J、G、R。现有甲、乙、丙、丁四人。他们将中文说明书翻译成不同语种的说明书所需时间如表5-6所示。问应指派何人去完成何工作，使所需总时间为最少？
任务 人员 甲 乙 丙 丁 E 2 10 9 7 J 15 4 14 8 表5-6
1. 启动程序，点击开始?程序?WinQSB? Network Modeling，屏幕显示如图5-11所示的网络模型工作界面。
2. 建立新问题或打开磁盘中已有的文件，按点击File?New Problem或直接点击工具栏的按钮
建立新问题，屏幕上出现如图5-17所示的问题选项输入界面。
G 13 14 16 11 R 4 15 13 9
17
图5-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所示。
表5-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。
，系统直接显示
表5-8 指派问题最优解综合报告表
本例得到最少花费时间为28，具体指派方案见表5-8。
（2）用网络图形式求解并显示求解步骤。用网络图形式分步求解可以明确每一步的优化结果。选择Solve and Analyze?Solve and Display Steps-Network，系统显示网络图形解题第一步的求解结果，如图5-18所示。
18
图5-18 Graphic Solution—Iteration 1
继续选择Iteration?Next Iteration或点击工具栏5-19所示。
，得到第二步的求解结果，如图
图5-19 Graphic Solution—Iteration 2
此时，第二步显示的结果已是最终结果（Final）了，再次选择Iteration?Next Iteration或点击工具栏
，即可得到表格式的求解结果，如表5-8所示。
（3）用表上作业法求解并显示求解步骤。具体方法与运输例题基本一致，此处略。
2.
用WinQSB软件求解下列指派问题：
① 四个工人指派四项工作，下表为每人做各项工作所消耗的时间，问应如何分配，
才能使总的消耗时间为最少。
工种 工人 甲 乙 丙 丁
19
A 15 19 26 19 B 18 23 17 21 C 21 22 16 23 D 24 18 19 17 ② 有5人去做5项工作，每人做各项工作的能力评分见下表。应如何分派，才能使总的得分为最大？ 业务 人员 A1 A2 A3 A4 A5 B1 1.3 0 1.0 0 1.0 B2 0.8 1.2 0 1.05 0.9 B3 0 1.3 0 0 0.6 B4 0 1.3 1.2 0.2 0 B5 1.0 0 0 1.4 1.1 ※ 指派问题的匈牙利解法
1、把各行元素分别减去本行元素的最小值；然后在此基础上再把每列元素减去本列中的最小值。
15 12??0 3 0 11 8??4 8 7 ?????7 9 17 14 10??0 1 7 7 3??6 9 12 8 7???0 2 3 2 1?????
10??0 0 5 0 4??6 7 14 6 ?6 9 12 10 6??0 2 3 4 0?????此时每行及每列中肯定都有0元素了。 2、 确定独立零元素，并作标记。
（1）、首先逐行判断是否有含有独立0元素的行，如果有，则按行继续处理；如没有，则要逐列判断是否有含有独立0元素的列，若有，则按列继续处理。若既没有含有独立0元素的行，也没有含有独立0元素的列，则仍然按行继续处理。
（2）在按行处理时，若某行有独立0元素，把该0元素标记为a，把该0所在的列中的其余0元素标记为b；否则，暂时越过本行，处理后面的行。把所有含有独立0元素的行处理完毕后，再回来处理含有2个以及2个以上的0元素的行：任选一个0做a标记，再把该0所在行中的其余0元素及所在列中的其余0元素都标记为b。
（3）在按列处理时，若某列有独立0元素，把该0元素标记为a，把该0所在的行中的其余0元素标记为b；否则，暂时越过本列，处理后面的列。把所有含有独立0元素的列处理完毕后，再回来处理含有2个以及2个以上的0元素的列：任选一个0做a标记，再把该0所在列中的其余0元素及所在行中的其余0元素都标记为b。 （4）、重复上述过程，即得到独立零元素（标记a的“0”）
?0b 3 0a 11 8???3??0a 1 7 7 ?0 2 3 2 ?1?b? ?0b 0a 5 0b 4????0b 2 3 4 0a?3、 若独立零元素等于矩阵阶数，则已经得到最优解，若小于矩阵阶数，则继续以下步骤：
（1）、对没有标记a的行作标记c
20