(2)当销大于产时，即，加入一个虚设的产地去生产不足的物资：它的产量为，构成新的平衡的运 输问题。 3.4运输问题的中转问题 在原运输问题上增加若干转运站。运输方式有：产地转运站、转运站销地、产地产地、产地销 地、销地转运站、销地产地等。 具体例子见PPT第56-60页。 3.5指派问题 (一）指派问题的标准形式及其数学模型 指派问题的标准形式（以人和事为例）是：有n个人和n件事，已知第i人做第j事的费用为Cj i.i=1.2. …,n),要求确定人和事之间的 一对应的指派方案，使完成这件事的总费用最 具体模型及例子见PPT第44-45页。 匈牙利解法 标准的指派问题是 类特殊的01整数规划问题，可以用多种相应的解法来求解。但是，这些方法 都没有充分利用指派问题的特殊性质来有效减少计算量。1955年，库恩(WW.Kuh)利用匈牙利数 学家康尼格(D.Koig)的关于矩阵中独立零元素的定理，提出了指派问题的一种解法，由此，习惯 上称之为匈牙利解法。 匈牙利解法的关键是利用了指派问题最优解的如下性质： 若从指派问题的系数矩阵C=(c)n×n的某行（或某列）各元素分别减去一个常数k,得到一个新 的系数矩阵C=（c叮)则以C和C为系数矩阵的两个指派问题有相同的最优解。 匈牙利解法的一般步骤 步骤一：变换系数矩阵。使其每行及每列至少有一个零元素，同时不出现负元素。 步骤二：进行试指派，即确定独立零元素。 步骤三：继续变换系数矩阵，然后返回步骤二。 (二)非标准形式的指派问题 在实际应用中，常会遇到各种非标准形式的制派问题。一般的处理方法是先将其转化为标准形式 然后再用匈牙利法求解。 最大化指派问题 一设品大化指派问颜系数矩连C=(c就) ,其中最大元素为m。令矩阵B= 相优），则以B为系数短陈的最小比指派狗和以c为系数矩陈的最大化指的题差 人数和事数不等的指派问题 -若人少事多，则添加一些虚拟的“人”，其费用系数取0，若人多事 少，则添加一些虚拟的事，其费用系数取0。 一个人可做几件事的指派问题一一若某个人可以做几件事，则将该人化作几个“人"来接受指派。这几 个“人做同一件事的费用系数当然都一样。 某事一定不能由某人做的指派问题一若某事一定不能由某人做，则可将相应的费用系数取为足够 大的数M。 第4章目标规划 4.1概述 1952年，美国学者Charnes等提出GP(Goal Programming)·GP在实践中的应用十分广泛， 它的重 要特点是对各个目标分级加权与逐级优化，这符合人们处理问题要分轻重缓急、保证重点的思考方 式 （一）目标规划问题举例 (1)企业生产（2）当销大于产时，即，加入一个虚设的产地去生产不足的物资；它的产量为，构成新的平衡的运 输问题。 3.4 运输问题的中转问题 在原运输问题上增加若干转运站。运输方式有：产地 转运站、转运站 销地、产地 产地、产地 销 地、销地 转运站、销地 产地等。 具体例子见PPT第56-60页。 3.5 指派问题 （一）指派问题的标准形式及其数学模型 指派问题的标准形式（以人和事为例）是：有 n 个人和 n 件事，已知第 i 人做第 j 事的费用为 Cij （i，j = 1，2，…，n），要求确定人和事之间的一一对应的指派方案，使完成这件事的总费用最 少。 具体模型及例子见PPT第44-45页。 匈牙利解法 标准的指派问题是一类特殊的 0-1 整数规划问题，可以用多种相应的解法来求解。但是，这些方法 都没有充分利用指派问题的特殊性质来有效减少计算量。1955年，库恩（W.W.Kuhn）利用匈牙利数 学家康尼格（D.König）的关于矩阵中独立零元素的定理，提出了指派问题的一种解法，由此，习惯 上称之为匈牙利解法。 匈牙利解法的关键是利用了指派问题最优解的如下性质： 若从指派问题的系数矩阵 C =（cij）n×n 的某行（或某列）各元素分别减去一个常数 k，得到一个新 的系数矩阵C‘= （ c’ij ）则以 C 和 C‘ 为系数矩阵的两个指派问题有相同的最优解。 匈牙利解法的一般步骤 步骤一： 变换系数矩阵。使其每行及每列至少有一个零元素，同时不出现负元素。 步骤二： 进行试指派，即确定独立零元素。 步骤三： 继续变换系数矩阵，然后返回步骤二。 （二）非标准形式的指派问题 在实际应用中，常会遇到各种非标准形式的制派问题。一般的处理方法是先将其转化为标准形式， 然后再用匈牙利法求解。 最大化指派问题——设最大化指派问题系数矩阵 C =（cij） ，其中最大元素为m 。令矩阵 B = （bij）=（m - cij ），则以 B 为系数矩阵的最小化指派问题和以 C 为系数矩阵的最大化指派问题有 相同最优解。 人数和事数不等的指派问题——若人少事多，则添加一些虚拟的“人”，其费用系数取 0 ，若人多事 少，则添加一些虚拟的“事”，其费用系数取 0 。 一个人可做几件事的指派问题——若某个人可以做几件事，则将该人化作几个“人”来接受指派。这几 个“人”做同一件事的费用系数当然都一样。 某事一定不能由某人做的指派问题——若某事一定不能由某人做，则可将相应的费用系数取为足够 大的数 M 。 第4章 目标规划 4.1 概述 1952年,美国学者Charnes等提出GP（Goal Programming）。GP在实践中的应用十分广泛，它的重 要特点是对各个目标分级加权与逐级优化，这符合人们处理问题要分轻重缓急、保证重点的思考方 式。 （一）目标规划问题举例 （1） 企业生产