运输问题 运输问题及其数学模型 运输问题的表上作业法 运输问题的进一步讨论 指派问题 数学试验

⑴ 运输问题是特殊的线性规划问题。 ⑵ 普通运输问题是追求运费最少问题。 ⑶ 目前研究问题：瓶颈运输问题；特殊运输问题等。

第一节 运输问题及其数学模型 一. 问题的提出 例1 某部门有3个同类型的工厂（产地），生产的产品由4个 销售点出售，各工厂的生产量、各销售点的销售量（假定单 位为t）以及各工厂到销售点的单位运价（元/t）示于表3-2 中，问如何调运才能使总运费最小？

表 3-2 销地 产地 产 量 4 12 11 16 2 10 3 9 8 5 6 22 销 量 14 48

一. 运输问题的数学模型 运输问题的一般提法是：设某种物资有 个产地 各产地的产量是 有 个销地 各销地的销量是 假定从产地 到销地 运输单位物品的运价是 ，问 怎样调运这些物品才能使总运费最小？

销地 产地 产 量 销 量

则称该运输问题为产销平衡问题；反之，称产销不平衡问题。 如果运输问题的总产量等于总销量，即有 （3.1） 则称该运输问题为产销平衡问题；反之，称产销不平衡问题。 产销平衡问题 的数学模型为： （3.2）

§2 运输问题的表上作业法 例1 某部门有3个同类型的工厂（产地），生产的产品由4个 销售点出售，各工厂的生产量、各销售点的销售量（假定单 位为t）以及各工厂到销售点的单位运价（元/t）示于表3-2 中，问如何调运才能使总运费最小？

表 3-2 销地 产地 产 量 4 12 11 16 2 10 3 9 8 5 6 22 销 量 14 48

该运输问题的数学模型为：

可以证明：约束矩阵的秩 为r (A) = 6. 从而基变量的个数为 6.

对于m个产地、n个销地产销平衡的运输问题， 可以证明：约束矩阵的秩 r (A) = m +n -1. 基变量的个数为 m+n-1.

表 3-2 销地 产地 产 量 4 12 11 16 2 10 3 9 8 5 6 22 销 量 14 48

表 3-2 销地 产地 产 量 4 12 11 16 2 10 3 9 8 5 6 22 销 量 14 48

一. 给出运输问题的初始可行解（初始调运方案） 下面介绍三种常用的方法。 1. 最小元素法 思想：优先满足运价（或运距）最小的供销业务。

表 3-2 销地 产地 产 量 4 12 11 16 10 3 9 8 5 6 22 销 量 14 48 ①

表 3-2 销地 产地 产 量 4 12 11 16 2 10 9 8 5 6 22 销 量 14 48 ② ①

表 3-2 销地 产地 产 量 4 12 11 2 10 9 8 5 6 22 销 量 14 48 ② ① ③

表 3-2 销地 产地 产 量 4 12 11 8 2 10 9 6 销 量 14 48 ② ① ④ ③

表 3-2 销地 产地 产 量 4 12 11 8 2 10 9 销 量 48 ② ⑤ ① ④ ③

表 3-2 销地 产地 产 量 4 12 8 2 10 9 11 销 量 48 ⑥ ② ⑤ ④ ① ③ ⑥

此时得到一个初始调运方案（初始可行解）： 其余变量全等于零。 此解满足所有约束条件，且基变量（非零变量）的个数为6 （等于m+n-1=3+4-1=6). 总运费为（目标函数值） 第7次课将到此。

⒉ 西北角法 西北角法是优先满足运输表中西北角（左上角）上空格的供 销需求。

表 3-2 销地 产地 产 量 4 12 11 2 10 3 9 8 5 6 22 销 量 14 48

表 3-2 销地 产地 产 量 4 12 11 2 10 3 9 8 5 6 22 销 量 14 48 ①

表 3-2 销地 产地 产 量 4 12 11 2 10 3 9 8 5 6 22 销 量 14 48 ①

表 3-2 销地 产地 产 量 4 12 11 2 10 3 9 8 5 6 22 销 量 14 48 ② ①

表 3-2 销地 产地 产 量 4 12 11 2 10 3 9 8 5 6 22 销 量 14 48 ② ①

表 3-2 销地 产地 产 量 4 12 11 2 10 3 9 8 5 6 22 销 量 14 48 ② ① ③

表 3-2 销地 产地 产 量 4 12 11 2 10 3 9 8 5 6 22 销 量 14 48 ② ③ ①

表 3-2 销地 产地 产 量 4 12 11 2 10 3 9 8 5 6 22 销 量 14 48 ② ④ ① ③

表 3-2 销地 产地 产 量 4 12 11 2 10 3 9 8 5 6 销 量 14 48 ② ④ ① ③

表 3-2 销地 产地 产 量 4 12 11 2 10 3 9 8 5 6 销 量 14 48 ② ④ ③ ① ⑤

表 3-2 销地 产地 产 量 4 12 11 2 10 3 9 8 5 6 销 量 14 48 ② ④ ③ ① ⑤

表 3-2 销地 产地 产 量 4 12 11 2 10 3 9 8 5 6 销 量 14 48 ② ④ ⑥ ③ ① ⑤ ⑥

此时得到一个初始调运方案（初始可行解）： 其余变量全等于零。 此解满足所有约束条件，且基变量（非零变量）的个数为6 （等于m+n-1=3+4-1=6). 总运费为（目标函数值）

从上面两例看，最小元素法比较合理。但从下表供应看 ⒊ 沃格尔（Vogel ) 法 从上面两例看，最小元素法比较合理。但从下表供应看 销地 产地 产 量 4 12 8 2 10 9 11 销 量 48 ② ⑤ ① ④ ③

沃格尔法的基本思想：运输表中各行各列的最小运价与次小 运价之差值（罚数）应尽可能地小。 或者说：若某行运价罚数最大，优先供应罚数最大行（或 列）中最小运费的方格，以避免将运量分配到该行（或该 列）次小的方格中。

表 3-2 销地 产地 产 量 4 12 11 16 2 10 3 9 8 5 6 22 销 量 14 48

销 地 产地 产 量 行罚数 1 2 3 4 12 11 16 10 9 8 6 销 量 14 48 列 罚 数 5

销 地 产地 产 量 行罚数 1 2 3 4 12 11 16 10 9 8 5 22 销 量 14 48 列 罚 数

销 地 产地 产 量 行罚数 1 2 3 4 12 11 16 10 9 8 5 22 销 量 14 48 列 罚 数

销 地 产地 产 量 行罚数 4 5 6 12 11 7 10 3 9 8 22 销 量 14 48 列 罚 数 1 2

销 地 产地 产 量 行罚数 4 5 6 12 11 7 10 3 8 22 销 量 14 48 列 罚 数 1 2

此时得到一个初始调运方案（初始可行解）： 其余变量全等于零。 此解满足所有约束条件，且基变量（非零变量）的个数为6 （等于m+n-1=3+4-1=6). 总运费为（目标函数值）

二. 解的最优性检验 前面得到了初始基可行解，一般来说此解并非最优。下面介绍 最优性检验的两种方法。 ⒈ 闭回路法（cycle method) 下面用最小元素法所确定的初始基本可行解来说明。 与单纯性原理相同，现目标是运费最少，故检验每一个非 基变量的检验数是否

三. 解的改进（用闭回路法调整） 选择进基变量的原则： 即选择非基变量中检验数最小的一个进基。 在进基格点所对应的闭回路上，定义顶点的序号：自进基 格点起选定一个方向（比如顺时针方向），依次为第一 格、第二格、… 在奇数格点上减少调整量 ，在偶数格点上增加调整量 。 其中调整量为 为闭回路中偶数格点}

表 3-2 销地 产地 产 量 4 12 10 6 11 16 8 2 3 9 14 5 22 销 量 48

表 3-2 销地 产地 产 量 4 12 10 6 11 16 8 2 3 9 14 5 22 销 量 48

表 3-2 销地 产地 产 量 4 12 10 6 11 16 8 2 3 9 14 5 22 销 量 48

表 3-2 销地 产地 产 量 4 12 10 6 11 16 8 2 3 9 14 5 22 销 量 48

表 3-2 销地 产地 产 量 4 12 10 6 11 16 8 2 3 9 14 5 22 销 量 48

表 3-2 销地 产地 产 量 4 12 10 6 11 16 8 2 3 9 14 5 22 销 量 48

表 3-2 销地 产地 产 量 4 12 10 6 11 16 8 2 3 9 14 5 22 销 量 48

表 3-2 销地 产地 产 量 4 12 10 6 11 16 8 2 3 9 14 5 22 销 量 48

表 3-2 销地 产地 产 量 4 12 11 16 8 2 10 3 9 14 5 6 22 销 量 48

表 3-2 销地 产地 产 量 4 12 11 16 8 2 10 3 9 14 5 6 22 销 量 48 到此

闭回路寻找麻烦，且用于两方面：一是计算非基变量检验 数，而是用于检验数为负数的非基变量的基变换。问题是： 有没有所有变量统一的检验数公式？下面的对偶变量法（位 势法）就解决这个问题。

⒉ 对偶变量法（位势法）(dual variable method) 用LP的对偶理论可以证明，检验数的公式为： （2.1） 其中 分别称为行位势、列位势。 有基变量所对应的检验数为零，可从m+n-1个等式 （2.2） 解出所有的行位势、列位势。 可以证明，不论令 为何值， 始终不变。

即 将不会随 的取值而改变。 为此，在求解方程组（2.2）时，为计算简便，可指定一个位 势等于一个较小的整数或零。

行位势 表 3-2 销地 产地 产 量 4 12 10 6 16 8 2 9 14 11 22 销 量 48 列位势

表 3-2 销地 产地 产 量 4 12 10 6 11 16 8 2 3 9 14 5 22 销 量 48

表 3-2 销地 产地 产 量 4 12 10 6 11 16 8 2 3 9 14 5 22 销 量 48

表 3-2 销地 产地 产 量 4 12 10 6 11 16 8 2 3 9 14 5 22 销 量 48

表 3-2 销地 产地 产 量 4 12 10 6 11 16 8 2 3 9 14 5 22 销 量 48

表 3-2 销地 产地 产 量 4 12 10 6 11 16 8 2 3 9 14 5 22 销 量 48

表 3-2 销地 产地 产 量 4 12 10 6 11 16 8 2 3 9 14 5 22 销 量 48

表 3-2 销地 产地 产 量 4 12 10 6 11 16 8 2 3 9 14 5 22 销 量 48

表 3-2 销地 产地 产 量 4 12 11 16 8 2 10 3 9 14 5 6 22 销 量 48

表 3-2 销地 产地 产 量 4 12 16 8 10 3 2 14 11 22 销 量 48

表 3-2 销地 产地 产 量 4 12 11 16 8 2 10 3 9 14 5 6 22 销 量 48

表 3-2 销地 产地 产 量 4 12 11 16 8 2 10 3 9 14 5 6 22 销 量 48

表 3-2 销地 产地 产 量 4 12 11 16 8 2 10 3 9 14 5 6 22 销 量 48

表 3-2 销地 产地 产 量 4 12 11 16 8 2 10 3 9 14 5 6 22 销 量 48

表 3-2 销地 产地 产 量 4 12 11 16 8 2 10 3 9 14 5 6 22 销 量 48

表 3-2 销地 产地 产 量 4 12 11 16 8 2 10 3 9 14 5 6 22 销 量 48

表 3-2 销地 产地 产 量 4 12 11 16 8 2 10 3 9 14 5 6 22 销 量 48

此时得到一个最优解： 其余变量全等于零。 总运费为（目标函数值） 四. 表上作业法计算中的两个问题 ⒈ 无穷多个最优解 若在最优解中，某个非基变量的检验数为零，则该问题有 无穷多个最优解（相当于当 无整数要求而言）

表 3-2 销地 产地 产 量 4 12 11 16 8 2 10 3 9 14 5 6 22 销 量 48

表 3-2 销地 产地 产 量 4 12 11 16 2 10 3 9 8 14 5 6 22 销 量 48

表 3-2 销地 产地 产 量 4 12 11 16 2 10 3 6 9 8 14 5 22 销 量 48

此时得另一个最优解： 其余变量全等于零。 总运费为（目标函数值） ⒉ 退化情况 与一般LP问题类似，运输问题也可能出现退化了的基本可 行解。有以下两种情况：

（1）在确定初始基本可行解时，若已确定在空格 处 要添上调运量 ，而此时发点的当前可发送量与收点的当 前需求量恰好相等。即发点的当前发送量已全部用完，而收 点的需求量已全部满足。因此应同时划掉发送的行及接受的 列。为了使调运表上确保有(m+n-1)个基变量的值，就需要在 所划掉的行（或列）的任一空格添上调运量0。这样就得到有 一个基变量取值为0的基本可行解——退化解。 例如：下表给出一个3×4运输的运价及发送量与需求量。 试用最小元素法求该问题的一个初始基本可行解。

表 4-2 销地 产地 产 量 3 11 4 5 7 8 1 2 10 6 9 销 量 48

此时得到一个退化了的初始基本可行解： 其余变量全等于零。 ⒉ 在用闭回路调整当前基本可行解时，有多个偶数格值相 等且都是极小值点 。此时只能取一个离基，其余的仍作为 基格。 例如：下表给出一个3×4运输问题的基本可行解及发送量 与需求量、基本可行解的检验数。试用闭回路法对其做出 调整。

表 4-5 销地 产地 产 量 3 1 7 9 销 量 6 4 48

表 4-5 销地 产地 产 量 3 4 7 6 9 销 量 48

§3 运输问题的进一步讨论 一. 产销不平衡运输问题 对产销不平衡问题，可转化为平衡问题，然后按表上作业 法求解。转换办法： ⒈ 若产大于销，增加一个假想的销地（可视为库存地）其销 量设定为余量，相应的运价设为0。 ⒉ 若销大于产，增加一个虚拟的产地，其产量设定为不足 量，相应的运价也设为0。

例4 某市有3个造纸厂 ， 和 ，有4个集中用户 和 ，各工厂的生产量、各用户的需用量以及各 工厂到用户的单位运价（元/t）示于表3-14中，问如何调运 才能使总运费最小？

表 3-14 销地 产地 产 量 3 12 4 8 11 2 5 9 6 7 1 销 量 18 可增加一个假想的销地 22

表 3-14 销地 产地 产 量 3 12 4 8 11 2 5 9 6 7 1 销 量

整 数 规 划 在许多线性规划问题中,要求最优解必须取整数.例如 所求的解是机器的台数、人数车辆船只数等.如果所得的解 中决策变量为分数或小数则不符合实际问题的要求. 对于一个规划问题,如果要求全部决策变量都取整数, 称为纯(或全)整数规划;如果仅要求部分决策变量取整数, 称为混合整数规划问题.有的问题要求决策变量仅取0或l两 个值,称为0-l规划问题. 整数规划(integer programming)简称为IP问题.这里主要 讨论的是整数线性规划问题,简称为ILP问题.

整数线性规划数学模型的一般形式为： 中部分或全部为整数，

整数线性规划类型 1.纯整数线性规划： 人员安排问题 2.混合整数线性规划： 物资运输问题 3.0－1型整数线性规划： 投资组合问题

人员安排问题 医院护士24小时值班，每次值班8小时。不同时段需要的护士人数不等。据统计： 最少需要多少护士？ 序号 时段 最少人数 安排人数 1 06—10 60 x1 2 10—14 70 x2 3 14—18 x3 4 18—22 50 x4 5 22—02 20 x5 6 02—06 30 x6 最少需要多少护士？

投资组合问题 证券投资：把一定的资金投入到合适的有价 证券上以规避风险并获得最大的利润。 项目投资：财团或银行把资金投入到若干项 目中以获得中长期的收益最大。

现有资金总额为B。可供选择的投资项目有n个，项目j所需投资额和预期收益分别为aj和cj（j=1,2, 现有资金总额为B。可供选择的投资项目有n个，项目j所需投资额和预期收益分别为aj和cj（j=1,2,...,n）。此外， 由于种种原因，有三个附加条件： 第一，若选择项目1，就必须同时选择项目2。反之，则不一定； 第二，项目3和4中至少选择一个； 第三，项目5，6和7中恰好选择两个。 应当怎样选择投资项目，才能使总预期收益最大？

模 型 变量—每个项目是否投资 约束—总金额不超过限制＋3个附加条件 目标—总收益最大

模 型

物资运输问题 B1 B2 B3 B4 生产能力 A1 2 9 3 4 400 A2 8 5 7 600 A3 6 1 200 A4 需求量 工厂A1和A2生产某种物资。由于该种物资供不应求，故需要再建一家工厂。相应的建厂方案有A3和A4两个。这种物资的需求地有B1，B2，B3，B4四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费cij(i,j=1,2,3,4). B1 B2 B3 B4 生产能力 A1 2 9 3 4 400 A2 8 5 7 600 A3 6 1 200 A4 需求量 350 300 150 1200 工厂A3或A4开工后，每年的生产费用估计分别为1200万元或1500万元。现要 决定应该建设工厂A3还是A4，才能使今后每年的总费用最少？

求解整数规划 IP（整数规划）问题的输入与LP类似，但在END标志后 需定义整型变量。 0-1型整数变量可用INTEGER（可简写为INT）命令来标 示；其它整数变量可用GIN（general integer variable)命令 来标示. 标示方法有两种：

1）INTEGER Vname 或GIN Vname 2）INTEGER n 或GIN n 表示将当前模型中前n个变量标示为0-1型变量或为一般整数 变量。

例10/p147 求解0-1整数规划

§4 指派问题（Assignment problem ) 例12：某商业公司计划开办五家新商店。为了尽早建成 营业，商业公司决定由5家建筑公司分别承建。已知建筑 公司 对新商店 的建造 报价（万元）为 , 见矩阵C。商业公 司应当对5家建筑公司怎样分配建筑任务，才能使总的建 筑费用最少？

指派问题是整数规划的一类重要问题。也是在实际生活中经常 遇到的一种问题：由n项不同的工作或任务 ， 需要n个人 去完成（每人只能完成一项工 作）。由于每人的知识、能力、经验等不同，故各人完成不同 任务所需的时间（或其它资源）不同。问应指派哪个人完成何 项工作所消耗的总资源最少？

§4 指派问题 一. 指派问题的数学模型 引进0-1变量 表示按排第i个人完成第j项工作 表示不安排第i个人完成第j项工作 §4 指派问题 一. 指派问题的数学模型 引进0-1变量 表示按排第i个人完成第j项工作 表示不安排第i个人完成第j项工作 则决策变量矩阵可表示为：

用 表示第i个人完成第j项工作所需的资源数，称之为效率 系数（或价值系数）。表示为

则指派问题的数学模型为 或1

注：指派问题是一种特殊的LP问题，是一种特殊的运输问题。 下用目前认为最简洁的方法—匈牙利法求解 (The Hungarian Method of Assignment )。 例12：某商业公司计划开办五家新商店。为了尽早建成 营业，商业公司决定由5家建筑公司分别承建。已知建筑 公司 对新商店 的建造 报价（万元）为 ，见下矩阵。商业公 司应当对5家建筑公司怎样分配建筑任务，才能使总的建 筑费用最少？

这是一个标准的指派问题。若设0-1变量 当 承建 时 当 不承建 时

则问题的数学模型为 或1

若单说让谁建，不让谁建。

-4 -7 -6 -6 -7 从而导出匈牙利解法的思想：

二. 匈牙利解法 匈牙利法是1955年由库恩（W. W. Kuhn）根据匈牙利 数学家狄·考尼格（d. konig)关于矩阵中独立零元素的定理 发明的。 匈牙利法的基本原理： 定理1 将效率矩阵的某一行（或某一列）的各个元素都减去 同一个常数c (c可正可负），得到新的矩阵，则以新矩阵为 效率矩阵的指派问题与原指派问题的最优解相同。但其最 优值比原最优值减少c 。

推论 若将指派问题的效率矩阵每一行及每一列分别减去各 行各列的最小元素，则得到的新的指派问题与原指派问题有 相同的最优解。 注：当 时，从第i行看，它表示第i人去干第j项工作效 率（相对）最好，而从第j列来看，它表示第j项工作让第i人 来干效率（相对）最高。

问题是：能否找到位于不同行、不同列的n个0元素？ 定义 在效率矩阵C中，有一组处于不同行、不同列的零元素， 称为独立零元素组，此时其中每个元素称为独立零元素。 例 已知 则 是一个独立零元素组.

分别称为独立零元素。 也是一个独立零元素组。 不是一个独立零元素组。

但有的效率矩阵独立零元素的个数不到n, 很难找到最优 指派方案。 已知效率矩阵 怎么办？

定理 效率矩阵C中独立零元素的最多个数等于能覆盖所 有零元素的最少直线数。 本定理由匈牙利数学家狄·考尼格证明的。证明的内容已超出 所学的范围。 下面通过例子说明上述定理的内容 例 已知矩阵

至于如何找覆盖零元素的最少直线，通过例子来说明。 例1 现有一个4×4的指派问题，其效率矩阵为： 求解该指派问题。 步骤1：变换系数矩阵，使得每行及每列至少产生一个零元 素。

-2 -4 -9 -7 -4 -2 其余全为0。 步骤2：用圈0法确定 中的独立0元素。若独立零元素个 素有n个，则已得最优解。若 独立零元素的个数 < n, 则转 入步骤3。

在只有一个0元素的行（或列）加圈，表示此人只能做该事 （或此事只能由该人来做），每圈一个“0”，同时把位于同 列（或同行）的其他零元素划去。表示此时已不能再由他 人来做（或此人已不能做其它事）。如此反复，直到矩阵 中所有零元素都被圈去或划去为至。 在遇到所有行和列中，零元素都不止一个时，可任选其中 一个加圈，然后划去同行、同列其他未被标记的零元素。 例

步骤3： 若矩阵已不存在未被标记的零元素，但圈零的个 数m < n ，作最少直线覆盖当前零元素。 已知例12中的系数矩阵为 ⒈变换系数矩阵 -4 -7 -6 -6 -6 -1 -3

✓ ✓ ✓ ⒉ 确定独立零元素. 由于独立零元素个数4 < 5. ⒊ 作最少直线覆盖当前所有零元素。 ⑴ 对没有圈0的行打“✓”。 ⑵ 在已打“✓”的行中，对零元素所在的列打“✓”。 ⑶ 在已打“✓”的列中，对圈0元素所在的行打“✓”。

✓ ✓ ✓ ✓ ✓ ✓ ⑷ 重复⑵和⑶，直到再也找不到可以打“✓”的行或列为止 ⑸ 对没有打“✓”的行画一横线，对已打“✓”的列画一纵线， 即得覆盖当前0元素的最少直线数目的集合。 ⒋ 继续变换系数矩阵，以增加0元素。 在未被直线覆盖的元素中找出一个最小的元素。对未被直

✓ ✓ ✓ ✓ ✓ ✓ 线覆盖的元素所在的行（或列）中各元素都减去这一元素。这 样，在未被直线覆盖的元素中势必会出现0元素，但同时却又 使已覆盖的元素中出现负元素。为了消除负元素，只要对它们 所在的列（或行）中各元素都加上这一最小元素。返回⑵。

-1 -1 +1 中已有5个独立0元素，故可确 定指派问题的最优方案。 其余全为0。

也就是说，最优指派方案是：让 承建 ， 承建 承建 ， 承建 。这样安排能使总的建造费用最少， 总的建造费用为7+9+6+6+6=34（万元）。

三. 非标准形式的指派问题 在实际应用中，经常遇到非标准形式的指派问题。处理方法： 化标准，再按匈牙利访法求解。 ⒈ 最大化指派问题 例13 有4种机械要分别安装在4个工地，它们在4个工地工作 效率（见下表）不同。问应如何指派安排，才能使4台机械发 挥总的效率最大？

工地 机器 甲 乙 丙 丁 Ⅰ Ⅱ Ⅲ Ⅳ 30 25 40 32 32 35 30 36 35 40 34 27 28 43 32 38 解：设最大化的指派问题系数矩阵 ，其中最大元 素为m（本例种m=43），令矩阵

本例中 -3 -7 -3 -0 -4 打✓ 圈0 覆盖

✓ -1 ✓ -1 ✓ +1 圈0 此时m=n=4,因此决策变量矩阵为

即指派机械Ⅰ安装在工地丙，机械Ⅱ安装在工地丁，机械Ⅲ 安装在工地甲，机械Ⅳ安装在工地乙，才能使4台机器发挥总 的效率最大。其总效率为

⒉ 人数和事数不等的指派问题 若人少事多，则添上一些虚拟的“人”。这些虚拟的“人”做各事 的费用系数可取0，理解为这些费用实际上不会发生。若人多 事少，则添上一些虚拟的“事”。这些虚拟的“事”被各人做的费 用系数同样也取0。 ⒊ 一个人可做几件事的指派问题 若某个人可做几件事，则可将该人化作相同的几个 “人” 来接 受指派。这几个 “人” 做同一件时的费用系数当然都一样。 ⒋ 某事一定不能由某人做的指派问题

若某事一定不能由某个人做，则可将相应的费用系数取 作足够大的数M. 例13 对于例12的指派问题，为了保证工程质量，经研究决 定，舍弃建筑公司 和 ，而让技术力量较强的建筑公 司 、 和 来承建。根据实际情况，可以允许每家 建筑公司承建一家或两家商店。求使总费用最少的指派方 案。 反映投标费用的系数矩阵为

由于每家建筑公司最多可承建两家新商店，因此，把每家 建筑公司化作相同的两家建筑公司（ 和 这样，系数矩阵变为： 上面的系数矩阵有6行5列，为了使“人”和“事”的数目相同，

引入一件虚事 ，使之成为标准指派问题的系数矩阵： 再利用匈牙利法求解。

✓ 覆盖 ✓ 列变换 ✓ 圈0 打✓ 再变换 -1 -1 +1

圈0 最优解 承建 和 ， 承建 ， 承建 和 。总建筑费用为

最优解 承建 和 ， 承建 ， 承建 和 。总建筑费用为 （万元）