试求出表3-34给出的产销不平衡运输问题的最优解（请给出详细计算步骤） 最小元素法 为您推荐： 其他类似问题 扫描下载二维码产销不平衡的运输问题_中华文本库 第1页/共30页 第1页/共30页 寻找更多 ""第三章运输问题前面讨论了一般线性规划问题的数学模型的建立和求解的方法, 但在实际工作中，往往碰到有些线性规划问题, 它们的约束条件的 系数矩阵具有特殊的结构，这就使我们有可能找到比单纯形法更为 简单的求解方法, 从而节约大量的计算时间和费用。本章所讨论的 运输问题就是属于这样一类特殊的线性规划问题，它在实践中具有 重用的作用，具有广泛的应用。运输问题一般是研究把某种商品从若干个产地运至若干个销地 而使总运费最小的一类问题。在经济建设中，经常会遇到大宗物资调拨中的运输问题。
第一节运输问题的数学模型在给出一般化模型之前，先看下面例子。 例1、某公司经营某种产品，其下A,B,C三个生产厂，甲乙丙丁四个 销售点，公司每天把三个工厂生产的产品分别运往四个销售点，由 于各工厂距离各销售点的路程不同，所以单位产品的运费也就不同 ，各工厂每天的产量，各销售点每天的销量以及从各工厂到销售点 单位产品的运价如下表，问该公司如何调运产品，在满足各销售点 需要的前提下，使总运费最小？ 销地 甲 乙 丙 丁 产量ai 产地A B C 销量bj3 1 7 311 9 4 63 2 10 510 8 5 67 4 9对于运输问题，关键要素有三：产量、销量和运费。 解：设xij代表从第I个产地到第j个销地的运输量（I＝1，2，3； J＝1，2，3，4），用cij代表从第I个产地到第j个销地的运价，于是 可构造数学模型Min Z ? ?? cij xiji ?1 j ?134?4 ?? xij ? b j ? i ?1 ?3 ?? xij ? ai ? j ?1 ? x ?0 ij ? ?j ? 1,2,3运出的商品总量等于其产量 i ? 1,2,34运来的商品总量等于其销量由例子扩展到更一般的情况，即有m个产地，n个销地 的情况。这时运输问题可用以下数学语言来描述： 运输问题 ：假设有 m 个生产地点,可以供应某种物资( 以后称为产地)，用 Ai 表示（i = 1,2,???,m）；有 n 个销 售地，用 Bj 表示（j = 1,2, ???,n）；产地的产量和销售 地的销售量分别为 ai , i = 1,2,???,m 和 bj j = 1,2, ???,n，从 Ai 到 Bj 运输单位物资的运价为 cij ，这些数据可汇总 于如下表2―1。我们首先研究产销平衡的情况，因此 假设产销平衡的条件下，即?ai ?1mi? ?bjj ?1n的情况下，求使得总运费最小的调运方案。表2―1销地 产地产销平衡表与单位运价表 B1 B2 Bn ?????? c11 c21? cm1 b1产量A1 A2? Am 销量c12 c22? cm2 b2?????? ??????? ?????? ??????c1n c2n? cmn bna1 a2? am其数学模型:可以通过建模获得，而实际上就是将例1中的3（产地个数）用m代替，4（销地个数）用n代替，即可。其模型如下：Min Z ???ci ?1 j ?1mnijxij? m j ? 1,2, ? , n ?? xij ? b j ? i ?1 ? n i ? 1,2, ? , m ?? xij ? ai ? j ?1 ? xij ? 0 i ? 1,2, ? , j ? 1,2, ? , n ? ?对于产销不平衡的情况，我们将在以后讲到。模型特性：1、运输问题的数学模型，变量从x11到 xmn，共包含 m?个 变量, 约束条件为m + n 个； n 2、它的约束方程组的系数矩阵具有如下形 式，在该矩阵中，每列只有两个元素为1，其余都是0。 （表上作业法既是以此为基础得出）；x11 , ? , x1n , x21 , ? , x2 n , ?? , xm1 , ? , xmn ?1 ?0 ? 行 ?? ? A ? ?0 ?1 ? ?? 行 ?0 ? ? 1 ? 0 ? ? ? 0 ? 0 ? ? ? 1 0 ? 0 ?? 0 ? 0? 1 ? 1 ?? 0 ? 0? ? ? ? ? ?? ? ? ? ? ? 0 ? 0 ?? 1 ? 1? 1 ? 0 ?? 1 ? 0? ? ? ? ? ?? ? ? ? ? 0 ? 1 ?? 0 ? 1? ?M N另外要注意（记忆）： 1、对于运输问题模型，在m＋n个约束条 件中，因为隐含着一个总产量等于总销量的等式，所以相 互独立的约束条件个数为m＋n－1个，因此秩≤m＋n－1 2、区别于一般的线性规划问题，产销平衡 的运输问题一定具有可行解，同时也一定存在最优解。这种模型用单纯形法完全可以求解。 但是如果用单纯形法求 解，先得在每个约束条件上加入一个人工变量(以便求出初始基可 行解)。因此，即使是 m = 3， n = 4 这样的简单问题, 变量数就有 （3×4）＋（3＋4）＝19个之多，计算起来非常复杂。因此，我们有必要针对运输问题的某些特点，来寻求更为简单 方便的求解方法。前辈们给我们提供了简易方法，我们称之为表上 作业法。第二节表上作业法（本章重点）表上作业法是单纯形法在求解运输问题时的一种简化方法， 其实质是单纯形算法。只是具体计算和术语有所不同，可归纳 为：（1）找出初始基可行解。即在 (m?n) 产销平衡表上（共m×n）个 格）给出m+n-1个有数字的格（基变量），这些有数字的格不能构 成闭回路，且行和等于产量，列和等于销售量；（2）求各非基变量（空格或非数字格）的检验数。即在表上求空 格的检验数，判别是否达到最优解。如果达到最优解，则停止计算， 否则转入下一步； （3）迭代。确定换入变量和换出变量，找出新的基可行解，在表 上用闭回路法进行调整。 （4）重复（2）、（3）步，直到求得最优解为止。表上作业法的难点是 1、找出初始基可行解2、求检验数以下我们就具体给出求解运输问题表上作业法的 计算步骤。2.1 确定初始基可行解确定初始基可行解即首先确定初始的调运方案，这一方 案可行但不一定是最优。对于确定初始基可行解共有两种方法： 方法一：最小元素法 方法二：伏格尔法1. 方法一、最小元素法： 最小元素法的基本思想就是就近供应。即首先从 单位运价表中运费最小的开始确定产销关系，确定运 输方法,依次类 推,直到给出初始方案为止。我们通过 例子来掌握这一方法： 例2：某公司经销甲产品，它下设三个加工厂，每 日的产量分别为：A1―7吨、 A2―4吨、 A3―9吨。该 公司把这些产品分别运往四个销售点. 各销售点每日销 售量为：B1―3吨、 B2―6吨、 B3―5吨、B4―6吨。已 知从各工厂到各销售点的单位产品的运价如表2―5所 示。问该公司应如何调运产品，在满足各销售点的需 要量的前提下,使总的运费为最小。表2―5销地单位：元/吨B1产地B211 9 4 6B33 2 10 5B410 8 5 6产量A1 A2 A3销量3 1 7 37 4 9解：先画出这个问题的产销平衡表简表2―6。表2―6销地单位：吨B1产地B2B3B4产量 7 4 9A1 A2 A3销量3656第一步：从单位运价表中找出最小运价为1，这表示先将A2 的产品供应 B1 。由于A2 每天生产4吨，B1 每天只需要3吨，即 A2 除每日能满足B1 的需要外还余1吨。因此在产销平衡表 (A2 , B1) 交叉处填上3，表示 A2 调运3吨给B1 ，再在单位运价表中将B1 这一列运价划去，表示 B1 的需求已满足，不需要继续调运 (即x21 =3=min(a2,b1)=min(4 , 3).第二步: 从上述未划去的单位运价表的元素中找出最小的 运价2 ，即A2 把剩余的产品供应给B3 ；B3 每天需要5 吨 ，A2 只剩余 1 吨，因此在上述产销平衡表的 (A2 , B3) 交 叉处填上 1，划去上述运价表中A2 这一行运价，表示 A2的产品已分配完毕。 第三步: 从上述第二步所得的单位运价表未划去的元素中 找出最小元素为 3。这表示将 A1 的产品供应 B3 ， A1 每 天生产7 吨，B3 尚缺 4 吨，因此在产销平衡表的(A1 , B3) 交叉处填上 4，由于B3 的需求已满足，将第二步的单位运价表中的 B3 这一列运价划去。如此，一步步进行下去，直到单位运价表中所有元素都划去为止，最终在产销平衡表上就可以得到一个初始调运方案。这个方案的总运费为 86 元，如表2―7所示。B1B2B3B4A1A2 A3 表2―7 销地 产地 A1 A231 7119 432 10108 5B1B2B3 4B4 3 3产量 736 3 615 649A3销量应当注意，在用最小元素法确定初始基可行解的时候， 有可能出现以下的两种特殊情况： 1、当在中间步骤的未划去的单位运价表中寻找最小 元素时，发现该元素所在行的剩余产量等于该元素所在列 的剩余销售量。这时在产销平衡表相应的位置填上一个 数，而在单位运价表中就要同时划去一行和一列。为了 使调运方案中有数字的格仍为（m + n C1）个，需要在同 时划去的行或列的任一空格位置添上一个“0”，这个 “0” 表示该变量是基变量，只不过它取值为0，即此时的调运方案是一个退化的基可行解。见如下例 4：B1B2B3B4A1A2 A3 销地 产地513610946201057产量B1B2 5B3 0 1B4 4A1 A2A3 销量 3 39 4775 8 4在这个例子中，当在填入第三数字的格 ( A1, B4 ) 时, 在填入 4 之后，恰好产销平衡，就必须在单位运价表中 同时划去第一行和第四列。为了使有数字的格不减少， ( 有数字的格的总数应为m + n C1个 )可以在空格( A1, B1 ) 、 ( A1, B3 ) 、 ( A2, B4 ) 、( A3, B4 )中任选一个格添加一个“0”；同样，这个添加的“0”格当 作基变量，取值为0。 我们这里是在 ( A1, B3 ) 处填0（即初始调运方案是一个退化 的基可行解）。? ?最小元素法应用练习： 用最小元素法确定下题中初始基可行解。B1 3 1 7 3 B2 11 9 4 6 B3 3 2 10 5 B4 10 8 5 6 产量 7 4 产量 7 4 9销地 产地 A1 A2 A3 销量 销地 产地 A1 A2B1B20B34 1B43A3销量 366 56692. 方法二、伏格尔法：最小元素法有其缺点，在应用最小元素法时为了节省一处的费 用，有时会造成在其它地方要花多几倍的运费。伏格尔法考虑到， 一产地的产品，假如不能按最小运费就近供应，就考虑次小运费。 这就有一个差额，差额越大，说明不能按最小运费调运时，运费增 加就越多。因此，对于差额最大处，就优先采用最小运费调运。 我们还是用例 1 来说明伏格尔法的具体实施过程，以使两种方 法的区别更为明显， 步骤如下：第一步：计算行差额、列差额。在单位运价表中增加一行和一列，列的格位置 相应填入该行 的次小运费与最小运费之差，我们称之为行差额。行的格位置相应 填入该列的次小运费与最小运费之差，我们称之为列差额。如此可 得表2―8：表2―8销地 产地 A1 A2 A3 列差额 B1 B2 B3 B4 行差额31 7 2119 4 532 10 1108 5 301 1第二步：填表划线。从行差额和列差额中选出最大者，选择它所在 的行或列中的 最小元素。比较该元素所在的行和列的产量，取它们最小者填入产 销平衡表相应的位置。同时在单位运价表中划去一行或一列。由表 2―8可知 B2 的列差额最大。B2 列中最小元素为 4（即 A3 行），可确定 A3 产品优先 供应 B2 。比较它们的产量和销量，可知在单位运价表中划去 B2 列。 在产销平衡表的( A3 , B2 ) 空格处填入 6。第三步：循环反复，直至最优。对上述未划去的元素再分别计算出各行、各列的差额。重复 第一、二步的工作，直到给出初始解为止。本问题利用伏格尔方法 给出的初始调运方案如下表2―9所示。 销地 产地 A1 A2 A3 销量 3 B1 B2 B3 B4 产量53 6 6 521 3 674 9由以上可见：伏格尔方法同最小元素法除在确定供 求关系的原则上不同外，其余步骤相同，因而给出的初始 调运方案也是基可行解。且一般来说，比用最小元素法所 求出的初始解更接近于最优解。本例用伏格尔方法给出的 初始解就是最优解。??伏格尔法应用练习： 请用伏格尔法确定下题中初始基可行解。B1 3 1 7 3 B1 B2 11 9 4 6 B2 B3 3 2 10 5 B3 5 3 6 3 6 5 B4 10 8 5 6 B4 2 1 3 6 产量 7 4 9 产量 7 4 9销地 产地 A1 A2 A3 销量 销地 产地 A1 A2 A3 销量2 .2 计算检验数，进行最优解的判别 判别的方法是计算非基变量即空格的检验数。这与应 用单纯形法计算时要计算非基变量的检验数的检验数并无 不同，因运输问题的目标函数是要求实现最小化，所以当 所有的非基变量检验数全都 ? 0 时（与max情况相反）为 最优解。下面介绍两种求空格检验数的方法。1.方法一：闭回路法2. 方法二：位势法1. 闭回路法在给出调运方案的计算表上，如表2―9，从每一空格出发，找 一条闭回路。它是以空格为起点，用水平线或 垂直线向前划，碰 到一数字格后，可根据实际情况转 （或不转） 90 度，然后继续前 进。直到回到起始空格处为止。(A1 , B1) 空格与(A1 , B4) 、(A2 , B4) 和 (A2 , B1) 三个有数字的格构成一闭回路，如此等等。闭回路计算检验数的经济解释为：在已给出初始解的表2―7中， 可以从任一空格出发，如从 (A1 , B1) 出发，若让 A1 的产品调 1 吨给 B1 ，为了保持产销平衡，就要依次作调整：在 (A1 , B3) 处减少 1 吨， (A2 , B3) 处增加 1 吨， (A2 , B1) 处减少 1 吨，即构成了以(A1 , B1) 空 格为起点，其它为有数字的格的闭回路。如表2―10中的直线所示， 在这表闭回路中，各顶点所在格的右上角的数字是单位运价。表2―10销地 B1 B2 B3 4 3 （-1） 1 2 （+1） 6 3 6 5 3 6 B4 产量产地A1 A2 A3 销量 3 （+1） 3 1 （-1） 3 7 4 9可见这一调整方案使运费增加了： (+1)?3 + (-1) ?3 + (+1)?2 + (-1) ?1 = 1 (元) 这表明若这样调整运输方式将增加运费。将“1”这个数 填 入(A1 , B1) 格，这就是检验数。按以上所述，就可以找出所有空格的检验数，见如下表2―11。这时检验数还存在负数，因为(A2 , B4) 空格的检验数 改进方法见后面的2. 3小节。为 C1，这说明原方案还不是最优解，还需要进一步改进，表2―11 空格 (A1 , B1) (A1 , B2) 闭 回 路 检验数 1 2 1 -1 10(1,1)? (1,3)? (2,3)? (2,1)?(1,1) (1,2)? (1,4)? (3,4)? (3,2)?(1,2)(2,2)? (2,3)? (1,3)? (1,4)? (3,4)? (A2 , B2) (3,2)? (2,2) (A2 , B4) (2,4)? (2,3)? (3,3)? (1,4)?(2,4)(3,1)? (3,4)? (1,4)? (1,3)? (2,3)? (A3 , B1) (2,1)? (3,1) (A3 , B3) (3,3)? (3,4)? (1,4)? (1,3)? (3,3)12闭回路法应用练习： 写出下列问题的闭回路销地 产地 A1 A2 A3 销量 3 3 6 6 5 B1 B2 0 B3 4 1 6 6 B4 产量 7 4 92. 方法二：位势法用闭回路法求检验数时，需要给每一空格找一条闭回路。当产销点很多时，这种计算很费时。下面介绍一种较为简便的方法――位势法。 现在引进 m+n 个未知量 u1 , ?, um , v1 , ?, vn ，由上述基 ? ? ? ?可行解可构造如下一个方程组（2.1)：设 xi1 j1 ,?, xis js , ( s ? m ? n ? 1)是一组基可行解，?ui1 ? v j1 ? ci1 j1 ? ?ui2 ? v j2 ? ci2 j2 ? ? ? ?u ? v ? c js is j s ? is(2.1)其中cij 为单位运价。方程组（2.1）共有m+n 未知数和m+n-1个方程。(2.1)的解存在且恰有一个自由变量。称u1 , ?, um 为行位势， v1 , ?, vn 为列位势。 ? ? ? ? 定理：设已给了一组基可行解，且 u1=c1 , ?, um=cm ? ? v1 =d1, ?, vn =dn ? ? 是这组基可行解对应的行位势和列位势，则对每一个非 基变量xij 来说，它所对应的检验数为：?ij = cij C ( ui + vj )(2.2)下面,我们就以例子来说明这种方法的具体实施过程仍以例2所给出的初始基可行解表2―7为例： 第一步：由表2―7作表2―12，在对应表2―7的数字格 处填入单位运价如表2―12所示： 第二步：在表2―12上增加一行和一列，列中填入行 位势 ui ，行中填入列位势 vj 的表2―13。先令u1= 0 ，然后按 ui + vj = cij ( i , j )?基变量指标集，相继确定 ui 、 vj 。由表2―13可见，u1= 0 时，由u1 + v3 = c13 = 3 可得v3 = 3 ，由u1 + v4 = c14 = 10 可得v4 = 10；在v4 = 10时，由u3 + v4 = c34 = 5 可得 u3 = -5 。以此类推可确定所有的 ui 、vj 的值。表2―12B1A1 A2 A3 表2―13 销地 产地 B1 B2 1B2B33 2B41045B3B4行位势 uiA1 A2A3 列位势 vj 23 14 9 3105 100 -1-52第三步：按?ij = cij C (ui + vj ) ,( i , j )?非基变量指标集， 计 算所有的空格检验数。如：?11 = c11 C (u1 + v1 ) =3 C ( 0 + 2 ) = 1 ?12 = c12 C (u1 + v2 ) = 11 - ( 0 + 9 ) = 2这些计算可直接在表2―13上进行。为了方便，特设计计 算表，如表2―14。右上角框内的数为单位运价。在表2―14中还有负的检验数，说明还未得到最优解， 还得进一步进行改进。表2――14 销地 B1 B2 3 1 1 0 7 10 11 2 9 1 4 0 B3 3 0 2 0 10 12 -1 5 0 0 8 B4 10 行位势 ui产地A1 A2 A3 0 -1 -5列位势 vj29310位势法应用练习：写出下列问题的位势销地 产地 A1 A2 3B1B20B34 1B4产量 7 4A3销量 366 56692. 3 解改进的方法――闭回路调整法 当计算所有的空格检验数时，出现了负检验数，这表 明还未得到最优解。若有两个或两个以上的检验数为负 时，一般选择其中最小的负检验数，以它对应的空格为 调入格。即以它对应的非基变量为换入变量。由表2―14可知 (A2 , B4)为调入格（即以它对应的变量 x24 为换入变量）。以此格为出发点，作一闭回路，如表2―15所示。(A2 , B4) 格的调入量 ? 是选择闭回路上具有（-1）的数字格中的最小者。即 ? = min{1 , 3}=1 (其原理与单纯形法中按? 规则来确定的换出变量是相同)，然后按闭回路上的正、负好，加入和减去此值，得到调整方案如表2―16所示。对表2―16给出的解，再用闭回路法或位势法求各空格的检验数，见表2―17，这时表中的所有检验数全都 ? 0 ，所以表2―16所给出的解为最优解。这时得到的总运费的最小值是 85 元。 表2―15销地 产地A1B1B2B34(+1)B43(-1)产量7A2A3361(-1) 3 6 51(+1)349销量6表2―16 销地 B1 产地 A1 A2 3 A3 3 销量 表2―17 B1 A1 A2 0B2B3 5B4 2 1 3 6 B4产量 7 4 96 6 B2 2 25B3 1A3912应当指出的是，产销平衡的运输问题必定存在最优 解。那么有唯一最优解还是无穷多个最优解？依据仍然 是要检验是否有存在非基变量（即空格处）的检验数为 0。若有，则存在无穷多个最优解；否则，只有唯一最优 解。由于表2―17可知，空格 (A1 , B1)处的检验数为0，表名例2有无穷多个最优解。可在表2―16中以(A1 , B1)为调入格, 作闭回路 (A1 , B1)+?(A1 , B4)-?(A2 , B4)+?(A2 , B1)-?(A1 , B1)+ 。确定? = min{2 , 3}=2，经调整后得到另一个最优解，见表2―18。当然，我们的调入量可以是：0 & ? & 2 中的任一实数，这时的解仍为最优解，但不是基可行解（因为线性规划问题可以在顶点取到最优解， 也可以是在非顶点即是边界点上取到最优解，本题如表 2―19所示。 表2―18 销地 B1 产地 A1 A2 2 1B2B3 5B4产量 734A3 销量 36 6 53 69表2―19销地 B1 B2 B3 B4 产量产地 A1A2 A3 销量 3?3- ? 6 652- ?1+ ? 374 956第三节产销不平衡的运输问题及其求解方法（了解）前面讲的表上作业法，都是以产销平衡为前提的。但实际问题往往是不平衡的。这就需要把产销不平衡的问题转化为产销平衡的问题。当产大于销，即?ai ?1mi? ? b j 时，运输问题的j ?1n m i ?1 j ?1n的数学模型可以写成：Min Z ? ?? cij xij ? n ?? xij , ? ai (i ? 1, ? , m) ? j ?1 ?m ? ?? xij ? b j ( j ? 1, ? , n) ? i ?1 ? xij ? 0 (i ? 1, ? , m j ? 1, ? , n) ?由于总的产量大于销售量，就要考虑多余的物资在那 一个产地贮存的问题。设 xin+1 是产地 Ai 贮存量，故有：?xj ?1 mnij? xin?1 ? ? xij ? aij ?1n ?1(i ? 1, ? , m)?xi ?1 mij? bjm( j ? 1, ? , n)n?xi ?1in ?1? ? ai ? ? b j ? bn ?1i ?1 j ?1? 令 : cij ? cij , 当 : i ? 1, ? , m, j ? 1, ? , n 时; ? cij ? 0, 当 : i ? 1, ? , m, j ? n ? 1时.将其分别代入，得到：? Min Z ? ? ? ? cij xij ? ? ? cij xiji ?1 j ?1 i ?1 j ?1mn ?1mn? n ?1 ?? xij ? ai (i ? 1, ? , m) ? j ?1 ?m ? ?? xij ? b j ( j ? 1, ? , n, n ? 1) ? i ?1 m n ? ? xij ? 0 bn ?1 ? ? ai ? ? b j ? i ?1 j ?1 ?这是一个产销平衡的运输问题。类似地，当销大于产时，可以在产销平衡表中增加一bj ? ai 个假想的产地 i = m + 1 ，该产地的产量为 j ?1 i ?1 在单位运价表中令从该产地到各个销售地的单位运价为：cm+1 j = 0，同样可以转化为产销平衡的运输问题。?n?mMin Z ? ?? ? c? xi ?1 j ?1 ijm ?1nij???ci ?1 j ?1mnijxij? n ?? xij ? ai (i ? 1, ? , m, m ? 1) ? j ?1 ? m ?1 ? ?? xij ? b j ( j ? 1, ? , n) ? i ?1 n m ? ? xij ? 0 am ?1 ? ? b j ? ? ai ? j ?1 i ?1 ?第四节应用举例例3 设有三个化肥厂供应四个地区的农用化肥。假定等 量的化肥在这些地区使用的效果相同。各化肥厂年产量、 各地区年需要量及从各化肥厂到各地区运送单位化肥的 运价表如表2―20所示。试求出总的运费最省的化肥调拨方案。解：这是一个产销不平衡的运输问题，总产量为160万吨，四个地区的最低需求为110万吨，最高需求为无限。根据现有产量，第?个地区每年最多能分配得到60万吨，这样最高需求就为210万吨，大于产量。为了求得平衡，表2―20 需求 产地 A B ? 16 14 ? 13 13 ? 22 19单位运价：万元/万吨 ? 17 15 产量(万吨) 50 60C最低需求 最高需求1930 502070 70230 30―10 不限50在产销平衡表中增加一个假想的化肥厂 D ，其年产量为50 万吨。由于各地区的需求量包含两部分，如地区1，其中 30 万吨是最低需求，故不能由假想化肥厂 D 供给，令相应的单位运价为 M （任意大的正数）；而另一部分 20万吨满足或不满足均可以，因此可以由假想化肥厂 D 供给，按前述，可令相应的单位运价为0。对凡是需求分两种情况的地区，实际上可按照两个地区看待。这样可以 写出这个问题的产销平衡表（表2―21）和单位运价表（ 表2―22）。并根据表上作业法，可以求得这个问题的最 优解如表2―23所示。表2―21 产地 销地 A ?产销平衡表 ?? ? ? ? ?? 产量 50BC D6050 50销 量302070301050表2―22 产地 销地 A B C D单位运价表?16 14 19 M??16 14 19 0?13 13 20 M?22 19 23 0?17 15 M M??17 15 M 0表2―23 产地 销地 A B ? ??最优调运方案 ? 50 20 10 30 ? ? ?? 产量 50 60C D 销 量30200 30 20 10 5050 5030207030由于在变量个数相等的情况下，表上作业法的计算 远比单纯形法的计算简单得多，所以在解决实际问题时， 人们常常尽可能把某些线性规划问题化为运输问题的数 学模型。下面介绍例4作为一个典型的实例。 例4 某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如表2―24所示。又如果生产出来的柴油机当季不交货，每台每季度需存储费、维护费等共0.15万元。要求在完成合同的情况下，做出使该厂全年生产（包括储存、维护等）费用最小的决策。表2―24季 ? ? 度 生产能力(台) 25 35 单位成本(万元) 10.8 11.1??301011.011.3解： 由于每个季度生产出来的柴油机不一定当季交货， 所以设 xij 表示为第 i 季度生产的用于第 j 季度交货的 柴油机数。根据合同要求，必须满足： x11 x12 + x22 = 10 = 15x13 + x23 + x33= 25x14 + x24 + x34 + x44 = 20又每季度生产的用于当季和以后各季交货的柴油机数不可能超过该季度的生产能力，故又有：x11 + x12 + x13 + x14 ? 25x22 + x23 + x24 ? 35x33 + x34 ? 30 x44 ? 10 第 i 季度生产的用于第 j 季度交货的每台柴油机的实际成本 cij 应该是该季度单位成本加上储存、维护等费用。cij 的具体数值见表2―25。表2―25 交货 生产 ? ? ? ?? ? ??10.810.95 11.1011.10 11.25 11.0011.25 11.40 11.1511.30设用 ai 表示该厂第 i 季度生产能力，bj 表示第 j 季度的合同供应量，则问题可写成：Min Z ???ci ?1 j ?144ijxij? 4 (i ? 1 , 2 , 3 , 4) ?? xij ? ai ? j ?1 ? 4 ? ( j ? 1 , 2 , 3 , 4) ?? xij ? b j ? i ?1 ? xij ? 0 ? ? ? 显然这是一个产大于销的运输问题模型。注意到这个问题中当 i & j 时，xij = 0，所以应该令对应的 cij = M，M 是充分大的正数，再加上一个假想的需求月份 ?，就可以把这个问题变成产销平衡的运输模型，并写出产销 平衡表和单位运价表（合二为一，见表2―26）。 经用表上作业法求解，可得多个最优方案，表2―27 中列出最优方案之一。即第 ?季度生产 25台，其中 10台 当季交货，15台第 ?季度交货；第 ?季度生产 5台用于第? 季度交货；第 ? 季度生产 30台，其中 20台当季交货，10台用于第 ?季度交货；第 ? 季度生产 10台用于当季度交货。按此方案安排生产，可使该厂总的生产（包括储存、维护等）费用最省，即为 773万元。表2―26 销售 生产 ?产销平衡表与单位运价表 ? ? ? ? 产量?? ? ? 销量10.8M M M 1010.95 11.1011.10 M M 15 11.25 11.00 M 2511.2511.40 11.15 11.30 2000 0 0 302535 30 10表2―27最优调运方案 ? 15 ? 0 ? ? 产量 25销售 生产?? 10?? ?520 10 10303530 10销量1015252030第四章目标规划目标规划是在线性规划的基础上，为适应企业经营管理中多目标决策的需要而逐步发展起来的。目标规划是一种数学方法。它是在企业决策者所规定的若干指标值及要求实现这些指标值的先后顺序，并在给定有限资源条件下，求得总的偏离指标值最小的方案。。称这种方案为满意方案。目标规划的有关概念和数学模型是在1961年由美国学者查恩斯(A.Charnes)和库伯(W.W.Cooper)首次在《管理模型及线性规划的工业应用》一书中提出。当时是作为解一个没有可行解的线性规划而引入的一种方法。这种方法把规划问题表达为尽可能地接近预期的目标。1965年，尤吉? 艾吉里(Yuji ? Ijiri)在处理多目标问题，分析各类目标的重要性时，引入了赋予各目标一个优先因子及加权系数的概念；并进一步完善了目标规划的数学模型。表达和求解目标规划问题的方法是由杰斯基莱恩(Jashekilaineu)和桑?李(Sang?Li)给出并加以改进的。目标规划与线性规划相比有以下优点：1.线性规划只能处理一个目标，而现实问题往往要处理多个目标。目标规划就能统筹兼顾地处理多个目标的关系，求得更切合实际要求的解。2. 线性规划立足于求满足所有约束条件的最优解而在实际问题中，可能存在相互矛盾的约束条件。目标规划可以在相互矛盾的约束条件下找到满意解。3. 目标规划的最优解指的是尽可能地达到或接近一个或若干个已给定的指标值。4. 线性规划的约束条件是不分主次地同等对待，而目标规划可根据实际的需要给予轻重缓急的考虑。因此，可以认为目标规划更能确切地描述和解决经营管理中的许多实际问题。目前，目标规划已在经济计划、生产管理、市场管理、财务分析、技术参数的选择等方面得到广泛的应用。第一节目标规划的数学模型目标规划相应的基本概念有；正负偏差变量、目标约束条件、系统约束条件、优先因子等等。为了具体说明这些概念、目标规划与线性规划在处理问题方法上的区别，先通过例子来介绍目标规划的有关概念和数学模型。例1：某工厂生产I、II两种产品，有关数据见表3―1。试求获利最大的生产方案。 表3―1 I 原材料（kg） 设备（hr） 利润（元/件） 2 1 8 II 1 2 10 拥有量 11 10解：设 x1 、 x2 分别为生产产品I、II的件数，则这是一个单目标线性规划问题，其数学模型可表述为如下一张幻灯片所表示的形式，我们用图解法可求得最优决策方案为：x1*= 4，x2*= 3，Z *= 62 元。但实际上，工厂在作决策时，要考虑市场等一系列其它因素，如：（1）根据市场信息，产品I的销售量有下降的趋势，故考虑产品I的产量不大于产品II的产量；（2）超过计划供应的原材料，需用高价采购，这就使成本增加；（3）应尽可能充分利用设备台时，但不希望加班；（4）应尽可能达到并超过计划利润指标56元。这样在考虑产品决策时，便成为多目标决策问题。目标规划的方法是解这类决策问题的方法之一。下面引入与建立目标规划数学模型的有关概念。1. 设 x1 、 x2 为决策变量，此外，引进正、负偏差变量 d +、 d - 。正偏差变量d +表示决策值超过目标值的部分；负偏差变量 d - 表示决策值未达到目标值的部分。因决策值不可能既超过目标值同时又未达到目标值，即恒有：d +?d - = 0 (3.1)2. 系统（绝对）约束和目标约束：系统约束是指必须严格满足的等式或不等式；如线性规划问题的所有约束条件，不能满足这些约束条件的解称为非可行解，所以它们是硬约束。目标约束是目标规划特有的，可把约束右端项看作是要追求的目标值。在达到此目标值的过程中允许发生正或负偏差，因此在这些约束中加入正、负偏差变量，它们是软约束。线性规划问题的目标函数，在给定目标值和加入正、负偏差变量之后，可转变为目标约束。同时也可根据问题的需要将系统约束转变为目标约束。3. 优先因子（优先等级）与权系数：一个规划问题常常有若干个目标。但决策者在要求达到这些目标时是有主次或轻重缓急的考虑。凡要求第一位达到的目标，就赋予优先因子 P1 ；次位的目标赋予优先因子 P2 ，??，并规定 Pk ? Pk+1 ，k =1 ?? ??，2， ??，K ，表示 Pk 比 Pk+1 有更大的优先权。即 ?? ??首先保证 P1 级目标的实现，这时可以不考虑次级目标；而 P2 级目标是在实现 P1 级目标的前提下考虑的；以此类推，若要区别具有相同优先因子的两个目标的差别，这时可分别赋予它们不同的权系数 wj ，这些都由决策者按具体情况而定。4. 目标规划的目标函数:目标规划的目标函数（又称准则函数）是按各目标约束的正、负偏差变量和赋予相应的优先因子而构造的。当每一目标值确定后，决策者的要求是尽可能缩小与目标值的偏离。因此，目标规划的目标函数只能是 Min f (d +、 d - )。其基本形式有以下三种：（1）要求恰好达到目标值，即正、负偏差变量都要尽可能地小，这时：Min Z = f (d +、 d - ) (3.2)（2）要求不超过目标值，即允许达不到目标值，但尽量不超过目标值，也就是正偏差尽量小。这时：Min Z = f (d +)(3.2)（3）要求超过目标值，即超过量不限，大坝必须是负偏差变量要尽可能地小。这时：Min Z = f (d -) (3.2)对每一个具体目标规划问题，可根据决策者的要求和赋予各目标的优先因子来构造目标函数，以下用例子说明。例2：例1的决策者在原材料供应受严格限制的基础上考虑；首先是产品II的产量不低于产品I的产量；其次是充分利用设备的有效台时，不加班；在则是利润不小于 56元。求决策方案。解：按决策者所要求的，分别赋予这三个目标 P1 、 P2 、 P3 优先因子。于是这个问题的数学模型就是：Min Z ? P d ? P2 ( d ? d ) ? P d 1 3? 1? 2? 2? 3?2 x1 ? x2 ? 11 ? ? ? ? x1 ? x2 ? d1 ? d1 ? 0 ? ? ? ? x1 ? 2 x2 ? d 2 ? d 2 ? 10 ? ? ? 8 x1 ? 10 x2 ? d 3 ? d 3 ? 56 ? ?x , x , d ? , d ? ? 0 i ? 1 , 2 , 3 i ? 1 2 i目标规划数学模型的一般形式如下：? K ? ? ? ? ? Min Z ? ? P ?? ( wlk d k ? wlk d k ) ? l l ?1 ? k ?1 ?L? n ? ? ckj x j ? d k ? d k ? g k k ? 1, ? , K ?? ? j ?1 ? n ?? aij x j ? ( ?, ?)bi i ? 1, ? , m ? j ?1 ? ? x j ? 0 j ? 1, ? , n ? ? ? ?d k , d k ? 0 k ? 1, ? , K ? L ? K ( L : 优先因子数, K :目标数) ? ? ? ?建立目标规划的数学模型时，需要确定目标值、优先等级、权系数等，它都具有一定的主观性和模糊性，可用专家评定法等给予量化。第二节目标规划的图解法对具有两个决策变量的目标规划数学模型，可用图解法进行求解。我们对例2用图解法进行求解。从图中可知，该目标规划问题的最优解是线段GD上的所有点。 这时，线段GD 上的点能够满足目标规划问题的所有约束条件，即能满足所有的系统约束和目 标约束条件。但大多数目标规划问题并非如此，x2 B d 1-?d1+ FE G JDC d3I A d 3+ ? d2+ ? d2x10还可能出现非可行解，所以将目标规划问题的最优解称之为满意解。例 3：某电视机厂装配黑白和彩色两种电视机，每装配一台电视机需占用装配线1小时，装配线每周计划开动40小时，预计市场每周彩色电视机的销售量是24台，每台获利80元；黑白电视机的销售量是30台，每台获利40元。该厂确定的目标是：第一优先级：充分利用装配线每周计划开动40小时；第二优先级：允许装配线加班，但每周加班时间尽量不超过10小时；第三优先级：装配电视机的数量尽量满足市场的需要。又因彩色电视机的利润高，我们取其权系数为2。 试建立该问题的目标规划模型，并求解黑白和彩 色两种电视机的产量。 解：设 x1 、 x2 分别表示彩色和黑白电视机的产量。 这个问题的目标规划问题的数学模型为：Min Z ? P d ? P2 d ? P3 (2d ? d ) ? x1 ? x2 ? d ? d ? 40 ? ? ? ? ? ? ? x1 ? x2 ? d 2 ? d 2 ? 50 (或 : d1 ? d 2 ? d 2 ? 10) ? ? ? ? d 3 ? d 3 ? 24 ? x1 ? ? ? x2 ? d 4 ? d 4 ? 30 ? ? x , x , d ? , d ? ? 0, i ? 1 , 2 , 3 , 4 ? 1 2 i i? 1 ? 1? 1 1? 2? 3? 4我们用图解法求解该问题如下图所示：x2C D H?d 3+d3-d 4-GE(24,26) F d4+ d2-?d1A B ?0d1+d2+ ?x1第三节解目标规划的单纯形法目标规划的数学模型结构与线性规划的数学模型没有本质的区别，所以可用单纯形法求解。但要考虑目标规划数学模型的一些特点，作如下规定：（1）因目标规划问题的目标函数都是求最小化，所以检验数 ?j ? 0，j = 1，?，n 为最优准则；（2）因非基变量检验数中含有不同等级的优先因子，? 即： j ???k ?1KkjPk , j ? 1 ?, n , 而 P ?? P2 ?? ??? Pk 1从每个检验数的整体来看；检验数的正、负首先取决 于 P1 的系数 ?1j 的正、负。若 ?1j = 0，这时此检验数的正、负就取决于 P2 的系数 ?2j 的正、负，以下可依此类推。解目标规划问题的单纯形法的计算步骤：（1）建立初始单纯形表，在表中将检验数行按优先因子个数分别列成 K 行，令 k = 1；（2）检验该行中是否存在负数，且对应的前 k-1行系数是0，若有，取其中最小者对应的变量为换入变量，转下一步，若无负数，则转到（5）；（3）按最小比值规则确定换出变量，当存在两个和两个以上相同的最小比值时，选取具有较高优先级的变量为换出变量；（4）按单纯形法进行基变变换运算，建立新的计算表，返回（2）；（5）当 k = K 时，计算结束，表中的解即为满意解，否则令 k = k + 1 返回到（2）。例 4：试用单纯形法来求解例 2 。解：首先将例2的数学模型标准化；(1)取 xs , d1-, d2-, d3- 为初始基变量，列出初始单纯形表，见表3―2 。(2)取 k =1 , 检查检验数的 P1 行，因该行无负检验数，所以转下一步；(3) 因 k (= 1) & K (=3)，令k = k + 1 =2返回第(2)步；(4)查出检验数的 P2 行中有 -1, -2 ，取Min（ -1, -2 ）= -2 ，它对应的变量为 x2 是换入变量，转第（5）步；Min Z ? P d 1? 1? P2 ( d? 2?d )? Pd 3? 2? 3?2 x1 ? x2 ? xs ? 11 ? ? ? ? x1 ? x2 ? d1 ? d1 ? 0 ? ? ? x1 ? 2 x2 ? d 2 ? d 2 ? 10 ? ? ? ? 8 x1 ? 10 x2 ? d 3 ? d 3 ? 56 ? ?x , x , x , d ? , d ? ? 0 , i ? 1 , 2 , 3 i ? 1 2 s i表3―2cj P1 P2 P2 P3CB xBxs d1-b*11 0x12 1 1x21 -1 [2]xs1d1- d1+ d2- d2+ d3- d3+?1-1 1 -1P2 d2- 10P3 d3- 56P181011-1?jP2 P3-1-22 1-8 -10(5) 在表3―2上计算最小比值? = Min{ 11/1 , ―, 10/2 , 56/10 } = 10/2 = 5它所对应的变量 d2- 为换出变量，转第(6)步;(6) 进行基变换运算,得表3―3，返回第(2)步，以此类推，直至得到最终表为止，见表3―5。表3―4所示的解 x1*= 2 , x2*= 4 为例2的满意解。我们检查表3―4的检验数行，发现非基变量 d3+ 的检验数为0，这表明存在多重最优解。在表3―4中以非基变量 d3+ 为换入变量，d1- 为换出变量，经迭代得到表3―5，这时： x1*= 10/3 , x2*= 10/3 也是例2满意解。表3―3 cj CB xB xs b* 6 x1 3/2 x2 xs 1 P1 P2 P2 P3d1- d1+ d2-d2+ d3- d3+?-1/2 1/2d1x2553/21/2 11-1 1/2 -1/21/2 -1/2P3 d3P16[3]1-551-1?jP2 P3 -31 51 -5 1表3―4 cj CB xB b* x1 x2 xs P1 P2 P2 d2+ P3 d 3d3+d1- d1+ d2-?xsd1x232 4 111 -123-2 -1/2 1/2-3 -1/2 1/24/3 -4/3 -1/6 1/6x1P1211-5/3 5/3 1/3 -1/3?jP2 P311 1表3―5 cj CB xB b* x1 x2 xs d1-P1 d1+P2 d2-P2 d2+P3 d 3d3+xsd3+14 11-121-2-161-6 -1 1x2 10/3 x1 10/3 1 P1-1/3 1/31/3 1/32/3 -2/3 1/3 -1/3 1 1 1?jP2P31第四节目标优先次序的确定在目标规划中，要求按各目标的重要性程度赋予相应的优先因子及加权系数。简单情况下，决策者可按自己对各目标的重要性程度的认识给出排队顺序，当目标多而又不易判断时，可采用两两比较法，对那些关系重大的目标，优先次序的排队问题可听取多方面专家的意见，用加权平均法来确定。以下我们分别介绍这两种方法。1. 两两比较法假设有 n 个目标，决策者从这些目标中取出两个进行比较，并确定这两个目标的重要性程度的差别。用 Gi & Gj 表示目标Gi 比Gj 重要。这就有 n(n-1)/2 种 出现得越多表示该目标越重要，以出现的多少给出排队顺序。举例说明如下：比较结果。然后统计“ & ”左边的某目标出现的数目。例 5：假设某个人要买一辆新的小轿车，要考虑的目标有价格 G1、耗油量 G2、可维修性 G3、舒适性 G4四个目标。他对这四个目标依据自己的判断，利用两两比较的方法得出这四个目标之间的比较结果：G1 & G2G1 & G3G 1 & G4G2 & G3G2 & G4G 3 & G4问这四个目标重要性的排列顺序如何?解：我们可统计出在 “ & ”左边次数中：可维修性 G3 ：3次，价格 G1：2次，耗油量 G2：1次，舒适性 G4：0 次。所以赋予优先因子如下：G 3 ? P1 ； G 1 ? P2 ； G 2 ? P3 ； G 4 ? P4 。当各目标在“ & ”左边出现次数统计出来以后，可 按需要赋予相应的优先因子，或某些目标赋予同一优 先因子及不同的加权系数。这种方法的基本前提是决同一目标，不同的决策者的兴趣、偏好、感受往往有差异，为了尽量避免由于这些差异而引起错误安排优先因子，我们有以下确定优先因子的方法。这相当于决策者由个人转变到多人，由少数到多数。综合他们的意见给出汇总，也即是决策过程的民主化。2. 加权平均法对于那些重大目标的排序问题。可以听取多方面的意见，然后加予综合，现在我们举例如下：例 6：若需要对 5个目标 G1、G2、G3、G4、G5的重要性进行排队，现请 10 位有关专家参与评定。各自的评定工作均独立地进行，给每位专家一个编号 i , i =1，2，?，10，根据各方面评定的可信程度赋予每一 ? ? 个专家一个评定权系数 vi ， vi 取值范围是 0 ? 1 之间 。比如某位专家评出的结果是： G2 & G5 & G1 & G3 & G4 这表明 G2 最重要， G5 次之， ?，G4 最不重要。其 ? ? 它的专家也都做出类似的评定。10 位 专家评定的结 果汇总于表3―6。请给出这 5 个目标的重要性排列顺 序。表3―6 专家 编号 目标的重要性程度 1 2 3 4 5 评定权 系数vi12 3 4 5G2G3 G5 G1 G5G5G1 G3 G2 G2G1G5 G2 G5 G1G3G4 G1 G4 G3G4G2 G4 G3 G40.70.8 0.6 0.7 0.967G2G5G5G1G3G3G1G2G4G40.80.789G5G2G2G1G4G5G1G4G3G30.90.710G5G2G3G1G4100.8?vi ?1i? 7. 6解：为了便于计算，规定第一重要的目标给 5 分，次要的分别给予 4、3、2、1分。根据表3―6给出的 10个排队次序，统计出各目标分别被排在各位置的次数及对应的评定权系数，计算各目标的综合得分：目标 G1 的综合得分为：b1 ?5 ? v4 ? 4 ? (v2 ? v7 ? v9 ) ? 3 ? (v1 ? v5 ) ? 2 ? (v3 ? v6 ? v8 ? v10 )?vi ?110i? 3.17按同样的方法可计算出目标 G2、G3、G4、G5 的综合得分，分别为：b2 = 3.75、 b3 = 2.47、 b4 = 1.53、 b5= 4.22 。将这些综合得分数按递减顺序排队得到：b5 & b2 & b1 & b3 & b4由此得到对应的目标排队顺序为:G 5 & G2 & G1 & G3 & G 4目标重要性程度的排队顺序还可以用其它的方法 来确定，如可用层次分析法（AHP）等，这里就不在一一列举。第五章整数规划在线性规划问题中，所有的解都假设为具有连续型的数值，即解可以是整数、分数或带有小数点的实数。但对于某些具体的问题，常要求最优解是整数的情形。例如，所求的解是机器台数，完成工作的人数或装货的车数等，这时，分数或小数的解答就不符合要求。为了满足整数解的要求，初看起来，似乎只要把已求得的解经过“舍入化整”就可以，但这常常是 不 可行的。因为化整后不见得是可行解。或虽然是可行题，有必要另行研究。我们称这样的问题为整数规划(Integer Programming)，简称为 I P 。整数规划中，如果所有的变量都要求是（非负）整数，就称为纯整数规划(Pure Integer Programming)或全整数规划(All Integer Programming)；如果仅是其中一部分变量取值为整数，则称为混合整数规划(Mixed Integer Programming )。整数规划问题的求解要比一般的线性规划困难得多，这里我们将着重讨论一类特殊的整数规划――指派问题，它的数学模型和其求解。一、指派问题的数学模型在生活中经常会遇到这样的问题，某单位需要指派 n 个人去完成 n 项任务，每个人只做一项工作，同时，每项工作只由一个人完成。由于各人的专长不同，每个人完成各项任务的效率也不同。于是产生了应指派哪一个人去完成哪一项任务，使完成 n 项任务的总效率最高（如所用的时间为最少）。我们把这类问题称之为指派问题或分派问题(Assignment Problem)。例 7 :有一份中文说明书,需要译成英、日、德、俄四种文字，分别记作 E、J、G、R 。现有 甲、乙、丙丁四人，他们将中文说明书翻译成不同文字说明书所需要的时间如表4―1所示。问应指派何人去完成哪一项工作，使所需的总时间最少？表4―1任务 人员EJGR甲乙 丙210 9154 141314 16415 13丁78119类似的有：n 项加工任务，怎样指派到 n 台机床上分别完成的问题；n 条航线，怎样指定 n 艘船去航行的问题??等等。对应每个指派问题, 都有类似表 ?? ?? 4― 1那样的表格，我们称之为效率矩阵或系数矩阵，某元素 cij ( i , j = 1,2, ??, n ) 表示指派第 i 个人去完成 ?? ??第 j 项任务时的效率(或时间、成本等)。解题时需要?1 当指派第 i 个人去完成第 j 项任务 xij ? ? ?0 当不指派第 i 个人去完成第 j 项任务引入变量 xij ；其取值只能是 1 或 0，并令 ：当问题是要求极小化时的数学模型是：Min Z ???ci ?1 j ?1nnijxij? n ?? xij ? 1 i ? 1, ? , n ? j ?1 ? n ? j ? 1, ? , n ?? xij ? 1 ? i ?1 ? xij ? 0 或 1 ? ? ?指派问题的解矩阵应当是每行或每列只能有一个元素为1，其余均为 0 的 n 阶方阵。如下就是例 7 的 一个 解矩阵：指派问题是 0―1规划的特例，也是运输问题的特 例；即 m = n ，ai = bj = 1。我们利用指派问题的特点?0 ?0 ( xij ) ? ? ?1 ? ?01 0 0? ? 0 1 0? 0 0 0? ? 0 0 1?可以有更为简便的求解方法。定理：设 (cij)是指派问题的系数矩阵， cij ? 0，i , j = 1 , 2, ??, n 。若从(cij)的某一行（列）各元素中分别减 ?? ??去该行（列）的最小元素而得到的新矩阵 (bij) ，那么以新矩阵 (bij) 为系数矩阵的指派问题与原问题具有相同的最优解。库恩（W.W.Kuhn）于1955年提出了指派问题的解法，他引用了匈牙利数学家康尼（D.K? nig) 一个关于矩阵中 0 元素的定理：系数矩阵中独立 0 元素的最多个数等于能覆盖所有 0 元素的最少直线数。这个解以下用例 7 来说明指派问题的解法。第一步：使指派问题的系数矩阵，经变换，在各行各列中都出现 0 元素。为此分如下两步进行：（1）将系数矩阵的每行元素减去该行的最小元素；（2）再从所得的系数矩阵中，将每列减去该列的最小元素。（若该行或列已有 0 元素，则就不必计算）第二步：进行试指派以寻求最优解。为此按如下 5 个分步骤进行：（1）从只有一个 0 元素的行（列）开始，给这个0 元素加圈，记为 ? 。然后划去 ? 所在的列（行）的其它 0 元素，记为 ? 。这表示该列所代表的任务已指派完，不必再考虑别人。（2）给只有一个 0 元素的列的 0 元素加圈，记为?；然后划去? 所在行的 0 元素，记为 ? 。（3）重复进行（1）、（2）两步，直到所有 0 元素都被圈出和划掉为止。（4）若仍然有没有被划圈的 0 元素，且同行（列）的 0 元素至少有两个（表示对这个人可以从两项任务中指派其一），则可用不同的方案去试探。从所剩 0元素最少的行或列开始，比较该行或列各 0 元素所在列或行中 0 元素的数目，选择 0 元素少的那一列或行的这个 0 元素加圈（表示选择性多的要“礼让”选择 性 少的）。然后划掉同行或列的其它 0 元素。反复进行直到所有 0 元素都已被圈出和划掉为止。（5）若 ? 元素的数目 m 等于矩阵的阶数 n ，那么这个指派问题的最优解已得到。若 m & n ，则转入下一步：?2 ?10 (cij ) ? ? ?9 ? ?7 ?0 ?6 ?? ?0 ? ?015 13 4 14 14 16 8 11 13 7 0 5 1 6 3 04 ? ?0 13 11 2 ? ? ?6 0 10 11? 15? ? ? ? 13? ?0 5 7 4 ? ? ? ? 9 ? ?0 1 4 2 ? 0? ?0 13 7 0? ? ? ?6 0 6 9 ? 9? ? ? ? 2 ? ?0 5 3 2 ? ? ? ? 0 ? ?0 1 0 0 ? ? ?例7， 这时我们已经找到了4个不同行不同列的 0 元素，所以，该问题的最优解矩阵是：?0 ?0 ( xij ) ? ? ?1 ? ?00 1 0 00 0 0 11? ? 0? 0? ? 0?这表示：指定甲翻译俄文，乙翻译日文，丙翻译英文，丁翻译文。所需总时间最少为：Min Z ? c31 ? c22 ? c43 ? c14 ? 28 (小时)例8：求如下系数矩阵所对应的指派问题： ?12 7 9 7 9 ? ?8 9 6 6 6? ? ? (cij ) ? ? 7 17 12 14 9 ? ? ? ?15 14 6 6 10? ? 4 10 7 10 9 ? ? ? 解：按第一、二步将系数矩阵进行变换和试指派：?12 7 9 7 9 ? ?5 0 ?8 9 6 6 6? ?2 3 ? ? ? (cij ) ? ? 7 17 12 14 9 ? ? ?0 10 ? ? ? ?15 14 6 6 10? ?9 8 ? 4 10 7 10 9 ? ?0 6 ? ? ?2 0 5 0 30 0 7 0 62? ? 0? 2? ? 4? 5? ??5 ?2 ? ?0 ? ?9 ?0 ??0 3 10 8 62 0 ? 5 0 30 ? 0 7 0 ? 62? ? 0? ? 2? ? 4? 5? ?这里独立 0 元素的个数 m = 4 & 5 ；所以解题没有完 成，这时，应按以下步骤进行： 第三步：作最少的直线覆盖所有的 0 元素，以确定该 系数矩阵中能找到最多的独立 0 元素。为此按以下步 骤进行：（1）对没有? 的行打 ? ；（2）对已打 ? 的行中包含有 0 元素的列打 ? ；（3）再对有打 ? 的列中含有的? 的行打 ? ；（4）重复（2）、（3）直到得不出新的打 ? 的行、列为止；（5）对没有打 ? 的行画一横线，对打 ? 的列画一纵线，这就得到了能够覆盖所有 0 元素的最少直线数。令这直线数为 l 。若 l & n ，则说明必须再变换当前的系数矩阵，才能找到 n 个独立的 0 元素，为此转第四步；若 l = n ，应回到第二步，另行试探。在例8中，对由第一、二步所求得的矩阵进行第 三步的工作：?5 ?2 ? ?0 ? 9 ? ?0 ???0 3 10 8 62 0 ? 5 0 30 ? 0 7 0 ? 62? ? 0? ? 2? ? ? 4? 5? ? ?l = 4 & 5 ，所以应继续对上述矩阵进行变换，转第四步；第四步：对于上述矩阵进行行变换的目的是增加 0 元素。为此，在没有被直线覆盖的部分中找出最小元素， 然后在打? 行各元素中都减去该最小元素，而在打? 列的各元素中都加上该最小元素，以保证原来的 0 元 素的位置在经过变换之后仍然还是 0 元素。这样得到 的新系数矩阵与原问题具有相同最优解。由此若能得 到 n 个独立的 0 元素，则已得到最优解；否则返回到 第三步重复进行。 对于例8，我们继续进行计算如下：0 ?5 ?2 3 ? ?0 10 ? 8 ?9 ?0 6 ?? 0 ?7 ?4 3 ? ? ?0 ? 8 ? ?11 8 ?0 4 ??2 0 ? 5 0 3 2 0 ? 3 0 10 ? 0 7 0 ? 6 0 ? 0 5 0 ? 42? 0? ?? 2? ? ? 4? 5 ?? ? 2? ? 0? ? 0? ? 4? 3? ?这时我们已经找到了 n 个不同行不同列的 0 元素，也就得到了例8问题的最优解，具体如下：?0 ?0 ? ( xij ) ? ?0 ? 0 ? ?1 ?1 0 0 0? ? 0 0 1 0? 0 0 0 1? ? 0 1 0 0? 0 0 0 0? ?目?A由解矩阵可得最优指派方案是：甲?B 乙?D 丙?E 丁?C本例还可得出另一个最优解：?0 ?0 ? ( xij ) ? ?0 ? ?0 ?1 ?最优指派方案是：甲?B1 0 0 0? ? 0 1 0 0? 0 0 0 1? ? 0 0 1 0? 0 0 0 0? ?丁?D 目?A乙?C 丙?E所需总时间为 32。以上讨论仅限于求极小化目标的指派问题。对于求极大化的问题，只要经如下变换，仍可利用匈牙利 算法进行求解。对于 : Max Z ? ?? cij xij 型的指派问题, 可令 :i ?1 j ?1nnbij ? M ? cijM ? Max {cij } 则由(bij )作为1?i , j ? n系数矩阵的指派问题(目标为Min 型)与原问题 具有相同的最优解. 更多相关文档