第五章线性规划与计算复杂性简介ppt课件

1、线性规划与计算复杂性简介浙江大学数学建模实践基地浙江大学数学建模实践基地上一页上一页下一页下一页5.1 5.1 线性规划问题线性规划问题一、线性规划的实例与定义一、线性规划的实例与定义二、线性规划的标准形式二、线性规划的标准形式三、线性规划的图解法三、线性规划的图解法四、基本可行解与极点的等价定理四、基本可行解与极点的等价定理五、求解线性规划的单纯形法五、求解线性规划的单纯形法六、初始可行解的求法六、初始可行解的求法两段单纯形法两段单纯形法5.2 5.2 运输问题运输问题一、运输问题的数学模型一、运输问题的数学模型三、最优性判别三、最优性判别二、初始可行解的选取二、初始可行解的选取5.3 5.

2、3 指派问题指派问题一、指派问题的数学模型一、指派问题的数学模型二、求解指派问题的匈牙利算法二、求解指派问题的匈牙利算法5.4 5.4 计算复杂性问题的提出计算复杂性问题的提出一、一、P P类与类与NPNP类，类，NPNP完全性完全性二、有关离散问题模型及其算法的几点附加说明二、有关离散问题模型及其算法的几点附加说明上一页上一页下一页下一页5.1 线性规划问题在人们的生产实践中，经常会遇到如何利用现有资源来安排生产以取得最大经济效益的问题，此类问题构成了运筹学的一个重要分支数学规划，而线性规划Linear Programming, 简记LP则是数学规划的一个重要部分。自从1947年GBDant

3、zig提出求解线性规划的单纯形方法以来，线性规划在理论上日趋成熟 ，在应用上日趋广泛，已成为现代管理中经常采用的基本方法之一。上一页上一页下一页下一页一.线性规划的实例与定义例例5.1 5.1 某机床厂生产甲、乙两种机床，每台销售后的利某机床厂生产甲、乙两种机床，每台销售后的利润分别为润分别为40004000元与元与30003000元。生产甲机床需用元。生产甲机床需用A A、B B机器加工，机器加工，加工时间分别为每台加工时间分别为每台 2 2小时和小时和1 1小时；生产乙机床需用小时；生产乙机床需用A A、B B、C C三种机器加工，加工时间为每台各一小时。若每天可三种机器加工，加工时间为每

4、台各一小时。若每天可用于加工的机器时数分别为用于加工的机器时数分别为A A机器机器1010小时、小时、B B机器机器8 8小时和小时和C C机器机器7 7小时，问该厂应生产甲、乙机床各多少台，才能使小时，问该厂应生产甲、乙机床各多少台，才能使总利润最大？总利润最大？上一页上一页下一页下一页例1的数学模型：设该厂生产x1台甲机床和x2台乙机床时总利润最大，那么 x1 、x2应满足 max 4x1 + 3x2 s.t 2x1 + x2 10 x1 + x2 8 (5.1) x2 7 x1 , x2 0（5.1式中4x1 + 3x2表示生产x1台甲机床和x2台乙机床的总利润，被称为问题的目标函数，当

5、希望使目标函数最大时，记为max；反之，当希望使目标函数最小时，记为min。（5.1中的几个不等式是问题的约束条件，记为S.t即Subject to）。由于5.1式中的目标函数及约束条件均为线性函数，故被称为线性规划问题。总之，线性规划问题是在一组线性约束条件的限止下，求一线性目标函数最大或最小的问题。上一页上一页下一页下一页二、线性规划的标准形式例例5.25.2 min min S.t S.t i=1,m i=1,m xj0,j=1,nxj0,j=1,njnjjxc1injjijbxa1线性规划的目标函数可以是求最大值，也可以是求最小值，约束条件线性规划的目标函数可以是求最大值，也可以是求最

6、小值，约束条件可以是不等式也可以是等式，变量可以有非负要求也可以没有非负要可以是不等式也可以是等式，变量可以有非负要求也可以没有非负要求称这样的变量为自由变量）。为了避免这种由于形式多样性而带求称这样的变量为自由变量）。为了避免这种由于形式多样性而带来的不便，规定线性规划的标准形式为来的不便，规定线性规划的标准形式为利用矩阵与向量记为利用矩阵与向量记为min z = CT x min z = CT x S.t Ax = bS.t Ax = bx0 x0 （5.35.3）其中其中C C 和和x x 为为n n 维列向量，维列向量，b b为为m m 维列维列向量，向量，b0b0，A A为为m mn

7、 n矩阵矩阵,mn,mn且且rank(A)=mrank(A)=m。或更简洁地或更简洁地上一页上一页下一页下一页如果根据实际问题建立起来的线性规划问题并非标准形式，可以将它如下化为标准形式：（1 1若目标函数为若目标函数为max z =CT xmax z =CT x，可将它化为，可将它化为minminz =z =CT CT x x（2 2若第若第i i个约束为个约束为ai1x1+ainxnbiai1x1+ainxnbi，可增加一个松驰，可增加一个松驰变变量量yiyi，将不等式化为，将不等式化为ai1x1+ainxn+yi = biai1x1+ainxn+yi = bi，且，且yi0yi0。若第若

8、第i i个约束为个约束为ai1x1+ainxnbiai1x1+ainxnbi，可引入剩余量，可引入剩余量yiyi，将将不等式化为不等式化为ai1x1+ainxnai1x1+ainxn yi = biyi = bi，且，且yi0yi0。（3 3若若xixi为自变量，则可令为自变量，则可令 , ,其中其中 、 00iiixxx ixix 例如例如例例5.15.1并非标准形式，其标准形式为并非标准形式，其标准形式为min 4x13x2min 4x13x2s.t 2x1 + x2 + x3 = 10s.t 2x1 + x2 + x3 = 10 x1 + x2 + x4 = 8x1 + x2 + x4

9、= 8x2 + x5 = 7x2 + x5 = 7x1 , x2 , x3 , x4, x50 x1 , x2 , x3 , x4, x50上一页上一页下一页下一页图5.1对于例5.1，显然等位线越趋于右上方，其上的点具有越大的目标函数值。不难看出，本例的最优解为x*=(2,6)T ，最优目标值z*=26 。三、线性规划的图解法为了了解线性规划问题的特征并导出求解它的单纯形法，我们先应用图解法来求解例5.1。满足线性规划所有约束条件的点称为问题的可行点或可行解），所有可行点构成的集合称为问题的可行域，记为R。对于每一固定的值z，使目标函数值等于z的点构成的直线称为目标函数等位线，当z变动时，我

10、们得到一族平行直线图5.1）。上一页上一页下一页下一页上述论断可以推广到一般的线性规划问题，区别只在于空间的维数。在一般的n维空间中，满足一线性等式aix=bi的点集被称为一个超平面，而满足一线性不等式aixbi （或aixbi ）的点集被称为一个半空间其中ai为一n维行向量，bi为一实数）。若干个半空间的交集被称为多胞形，有界的多胞形又被称为多面体。易见，线性规划的可行域R必为多胞形为统一起见，空集也被视为多胞形）。（1可行域R可能会出现多种情况。R可能是空集也可能是非空集合，当R非空时，它必定是若干个半平面的交集（ 除非遇到空间维数的退化）。R既可能是有界区域，也可能是无界区域。（2在R非

11、空时，线性规划既可以存在有限最优解，也可以不存在有限最优解其目标函数值无界）。（3若线性规划存在有限最优解，则必可找到具有最优目标函数值的可行域R的“顶点”。从上面的图解过程可以看出并不难证明以下断言：上一页上一页下一页下一页在一般n维空间中，要直接得出多胞形“顶点概念还有一些困难。在图5.1中顶点可以看成为边界直线的交点，但这一几何概念的推广在一般n维空间中的几何意义并不十分直观。定义定义5.1 5.1 称称n n 维空间中的区域维空间中的区域R R为一凸集，若为一凸集，若x1 , x2 Rx1 , x2 R及及 (0, 1)(0, 1)，有，有 x1 + x1 +（1 1x2 Rx2 R。

12、定义定义5.2 5.2 设设R R为为n n维空间中的一个凸集，维空间中的一个凸集，R R中的点中的点x x被称为被称为R R的的一个极点，若不存在一个极点，若不存在x1 x1 、x2 Rx2 R及及(0, 1)(0, 1)，使得，使得x = x1 +x = x1 +（1 1x2 x2 。定义5.1说明凸集中任意两点的连线必在此凸集中；而定义5.2说明，若x是凸集R的一个极点，则x不能位于R中任意两点的连线上。不难证明，多胞形必为凸集。同样也不难证明，图5.1中R的顶点均为R的极点R 也没有其他的极点）为此，我们将采用另一途径来定义它。上一页上一页下一页下一页三、基本解与基本可行解给定一个标准

13、形式的线性规划问题5.3），其中A=(aij)mxn ，m 0 ，则称x=（B-1b ，0为5.3的一个非退化的基本可行解，并称B为非退化的可行基。由于基矩阵最多只有 种不同的取法，即使A的任意m解均线性无关，且对应的基本解均可行，（5.3最多也只能有个不同的基本可行解。mnC上一页上一页下一页下一页四、基本可行解与极点的等价定理在线性规划的求解中，下列定理起了关键性的作用。在这里，我们不加证明地引入这些定理。0 xbAx定理定理5.1 5.1 （基本可行解与极点的等价定理）（基本可行解与极点的等价定理）设设A A为一个秩为为一个秩为m m的的m mn n矩阵矩阵nmnmb b为为m m维列向

14、量，维列向量，记记R R为为5.35.3的可行域。则的可行域。则x x为为R R的极点的充分必要条件为的极点的充分必要条件为 x x 是是 的基本可行解。的基本可行解。定理定理5.15.1既提供了求可行域既提供了求可行域R R的极点的代数方法，又指的极点的代数方法，又指明了线性规划可行域明了线性规划可行域R R的极点至多只有有限个的极点至多只有有限个. .对定理证明有兴趣的读者可以参阅 D.G.鲁恩伯杰著的“线性与非线性规划引论一书第二章上一页上一页下一页下一页（线性规划基本定理） 线性规划5.3具有以下性质：（1若可行域R，则必存在一个基本可行解。（2若问题存在一个最优解 ，则必存在一个最优

15、的基本可行解。定理5.2并非说最优解只能在基本可行解极点上达到，而是说只要5.3有有限最优解，就必定可在基本可行解极点中找到。定理定理5.25.2从模型本身讲，线性规划显然应属连续模型。但定理 2表明，如果线性规划有有限最优解，我们只需比较各基本可行解上的目标函数值即可找到一个最优解，而问题的基本可行解至多只有有限个，从而问题化为一个从有限多个点选取一个最优点 的问题。正是基于这样一种思路，Dantzig提出了求解线性规划的单纯形法。也正因为如此，我们把线性规划列入了离散模型，因为求解它的单纯形法更具有离散模型问题的算法特征。上一页上一页下一页下一页五、求解线性规划的单纯形法（步1取一初始可行

16、基B一般取法见后面的两段单纯形法），再用高斯约当消去法求出初始基本可行解x0，编制成所谓的初始单纯形表；（步2判断x0是否最优解，如果x0是最优解，输出x0，停，否则到步3；（步3按一改进准则，将一个非基变量转变为基变量，而将一个基变量转变为非基变量。这相当于交换B与N的一个列，同样可用高斯约当消去法，运算可以通过单纯形表上的“转轴运算实现。Dantzig单纯形法的基本步骤如下：上一页上一页下一页下一页设B为一非退化的可行基，x=（B-1b，0为其对应的基本可行解。如今，我们先来讨论如何判别x0是否为最优解。为此，考察任一可行解 。由Ax=b可得 （5.5）代入目标函数，得到NBxxxNBNx

17、BbBx11NTBTNTBNTNBTBxNBCCbBCxCxCZ)(11NTBTNTxNBCCxC)(10NBCCrTBTNN1NjjNrr)(Nj定理定理5.3 （最优性判别定理）（最优性判别定理） 令令 。（1若若rN0，则，则x0必为必为5.3的一个最优解。的一个最优解。（2记记 。假设。假设 ，rj0 ， 根据上式知，当且充分小时，仍有xB0 。此时对应的x仍 为可行解，但由5.6），其目标函数值：故x0必非最优解。Njrj , 00Rx0 xCxCzTT01100 xCbBCxrbBCxCzTTBjjTBT 定理5.3不仅给出了判别一个基本可行解是否为最优解的准则，而且在x0非最优解

18、时还指出了一条改进它的途径。由于rN在判别现行基本可行解是否为最优解时起了重要作用，所以rN被称为x0处的检验向量，而rj (jN)被称为非基变量xj的检验数。上一页上一页下一页下一页有趣的是上述过程完全可以在以下的单纯形表上进行。先将CT、A、b及数0写在一个矩阵中，在表上用高斯约当消去法解方程组Ax=b 高斯-约当消去法 （第一行不变） bACT0bBNBICCTNTB110利用单位矩阵I消第一行的为零向量，那么 被消成 ，而0则被消成 。将消去后的行向量写到最后一行，删去原来的第一行，得到一张被称为单纯表的表格：TBCTNCNTBTNrNBCC101ZbBCTBxBxNIB1NB1b0r

19、NZ0(5.7)表格5.7以极为简洁明了的方式表达了我们需要的全部信息。从其前m行可看出哪些变量是基变量并可直接读出对应的基本可行解x0=（B1b，0）。其最后一行又给出了非基变量的检验数及x0处目标函数值的相反数。 上一页上一页下一页下一页例5.1的标准形式为5.4），容易看出它的一个初始基B=I以x3、x4、x5为基变量），且CB已经为零，故我们已有了一张初始的单纯形表表5.1： 表表5.15.1x1x2x3x4x5基变量x3110010 x4110108x5010017rj430000 x0=(0,0,10,8,7)Tz0=CTx0=0rN=(r1,r2)=(4，3)如今，我们以例如今，

20、我们以例8.18.1为例，来看一下单为例，来看一下单纯形法是如何工作纯形法是如何工作的。的。上一页上一页下一页下一页由于存在着负的检验数且由于存在着负的检验数且x0 x0非退化，非退化，x0 x0非最优解。非最优解。r1r1，r2r2均为负，均为负，x1x1，x2x2增大进基均能改进目标函数值。增大进基均能改进目标函数值。 例如，取例如，取x1x1进基仍令进基仍令x2=0 x2=0 x2x2仍为非基变量），此时由仍为非基变量），此时由5.55.5式及式及5.65.6式有式有 且且z = CTx = z = CTx = 4x14x1x1x1增加得越多，目标函数值下降得越多，但当增加得越多，目标函

21、数值下降得越多，但当x1 =5x1 =5时时x3=0 x3=0，x1x1再增大再增大则则x3x3将变负。为保证可行性，将变负。为保证可行性，x1x1最多只能增加到最多只能增加到5 5，此时，此时x3x3成为非基变成为非基变量退基）。量退基）。 7821051413xxxxx不难看出，上述改进可以在单纯形表上进行。对于一般形式的单纯形表，不难看出，上述改进可以在单纯形表上进行。对于一般形式的单纯形表，记最后一列的前记最后一列的前m m个分量为个分量为yi0yi0），），i=1,mi=1,m。若取。若取 进基，记进基，记j0j0列前列前m m个分量为（个分量为（ ），），i=1,mi=1,m。易见

22、，阻碍。易见，阻碍 增大的只可能在增大的只可能在 00的那些约束中。假设的那些约束中。假设 00对一切对一切i=1,mi=1,m成立成立j0j0列前列前m m个分个分量中不存在正值），那么量中不存在正值），那么 可任意增大，得到的均为可行解，但其目可任意增大，得到的均为可行解，但其目标值随之可任意减小，故问题无有限最优解。标值随之可任意减小，故问题无有限最优解。 0jx0ijy0jx0ijy0ijy0jx上一页上一页下一页下一页否则，令则随着 的增大，将 最先降为零退出基变量），故只需以 为主元作一次消去法运算称此运算为一次转轴运算），即可得到改进后的基本可行解处的单纯形表。在本例中，因取x1

23、进基j=1） 而 ，以y11为主元作第一次转轴，得到 0000000min0ijiijjiiyyyyy0jx0ix00jiy51110yy82120yyx1=(5,0,0,3,7)T z1=20 rN=(r2,r3)=(1，2)2000210rj710010 x5301 -0 x45001x3基变量x5x4x3x2x121212121表5.2上一页上一页下一页下一页表表5.25.2中中r20r20yi20最小选定以下最小选定以下 y22 = y22 = 为主元转轴，得到下一基本可行解为主元转轴，得到下一基本可行解x2x2处的单纯形表表处的单纯形表表8.38.3。21表5.3x1x2x3x4x5

24、基基变变量量x310102x40106x50011rj00026x2=(2,6,0,0,1)Tz2=26rN=(r3,r4)=(1，2)对于对于x2，rN= (1，2)为非负向量，故为非负向量，故x2为最优解，最优目标值为为最优解，最优目标值为26。于是，原问题例于是，原问题例1的最优解的最优解x*=(2,6)T，最优目标值为，最优目标值为26。 上一页上一页下一页下一页六、初始可行解的求法两段单纯形法 阶段2 若辅助规划的最优目标值不等于零，原规划无可行解。否则我们已求得原问题的一个基本可行解x0。删去阶段1最终单纯表中最后一行及对应人工变量的列，作出原规划对应x0的初始单纯形表。此时又可利

25、用上述单纯形法求解原规划了。阶段1 对第i个约束引入人工变量 yi，yi0，将其改写为ai1x1+ ainxn+yi=bi，i=1,m。作辅助线性规划LP1），其目标函数为 。容易看出，原规划有可行解从而有基本可行解的充分必要条件为辅助规划的最优目标值为零。由于辅助规划具有明显的初始可行基人工变量对应的列构成单位矩阵I），可利用上述单纯形法逐次改进而求出辅助规划最优解。miiy1上一页上一页下一页下一页例例5.2 min 4x1+ x2+ x35.2 min 4x1+ x2+ x3 S.t 2x1+ x2+2x3 = S.t 2x1+ x2+2x3 = 4 4 3x1+ 3x2+x3 = 3x

26、1+ 3x2+x3 = 3 3 x1 x1、x2x2、x30 x30?解：因为初始可行基不能直接看出，我们采用两段单纯形法解：因为初始可行基不能直接看出，我们采用两段单纯形法求解。求解。阶段阶段1 1 先求解辅助规划：先求解辅助规划：min x4+ x5min x4+ x5S.t 2x1+ x2+2x3 + x4= 4S.t 2x1+ x2+2x3 + x4= 4 3x1+ 3x2+x3+ x5 = 3 3x1+ 3x2+x3+ x5 = 3 x1 x1，x30 x30上一页上一页下一页下一页表表5.45.4x1x2x3x4x5基基变变量量x4212104x531013rj543007选取选取

27、x1x1进基，以进基，以y21=3y21=3为主元转轴为主元转轴x5x5出基），得表出基），得表5.55.5。表表5.55.5x1x2x3x4x5基基变变量量x4014/312/32x1111/301/31rj014/305/32上一页上一页下一页下一页因因r3 0r3 0 1b0 。当。当B B1b1b也存在零分量也存在零分量时，我们遇到了一个退化的基本可行解。此时时，我们遇到了一个退化的基本可行解。此时rNrN存在负分量不一定说明现存在负分量不一定说明现行基本可行解不是最优解，单纯形法也可能会遇到循环迭代。存在着几种行基本可行解不是最优解，单纯形法也可能会遇到循环迭代。存在着几种避免循环的

28、技巧，例如，只要每次在避免循环的技巧，例如，只要每次在rj0rj0的非基变量中选取具有最小足标的非基变量中选取具有最小足标者进基即可。者进基即可。 在求解线性规划时，首先应将问题化为标准形式。若从标准形式已可看出在求解线性规划时，首先应将问题化为标准形式。若从标准形式已可看出一个初始基，则可直接用单纯法求解：（一个初始基，则可直接用单纯法求解：（1 1写出初始单纯形表；（写出初始单纯形表；（2 2若若检验向量检验向量 rN 0rN 0，则已得以最优解；（，则已得以最优解；（3 3任选一负分量任选一负分量rjrj。以。以 进基，进基，考察考察 所在列。若对所在列。若对i=1,mi=1,m均有均有

29、 00，则问题无有限最优解，停；，则问题无有限最优解，停；否则令否则令 ，以以 为主元转轴，返回为主元转轴，返回2 2），直至），直至rN0rN0求出最优解。若从标准形式无求出最优解。若从标准形式无法看出初始可行基，则需采用两段单纯形法求解。法看出初始可行基，则需采用两段单纯形法求解。0jx0jx0ijy0000000min0ijiijjiiyyyyy00jiy变量同时具有上、下界限止的线性规划问变量同时具有上、下界限止的线性规划问题也可化为标准形式求解，有兴趣的读者题也可化为标准形式求解，有兴趣的读者可以参阅可以参阅D.G.D.G.鲁恩伯杰的鲁恩伯杰的“线性与非线性线性与非线性规划引论一书的

30、第三章。规划引论一书的第三章。 上一页上一页下一页下一页5.2 运输问题一.运输问题的数学模型 例例5.3 5.3 某商品有某商品有m m个产地、个产地、n n个销地，各产地的产量分别为个销地，各产地的产量分别为a1,ama1,am各销地的需求量分别为各销地的需求量分别为b1,bnb1,bn。若该商品由。若该商品由i i产产地运到地运到j j销地的单位运价为销地的单位运价为CijCij，问应该如何调运才能使总运，问应该如何调运才能使总运费最省费最省? ? 解：引入变量解：引入变量xij，其取值为由，其取值为由i产地运往产地运往j销地的该商品数量。例销地的该商品数量。例8.3的数的数学模型为学模

31、型为min S.t ，i=1,m (8.9) ，j=1,n xij 0njijijmixC11injijax 1jmiijbx 1（8.98.9显然是一个线性规划问题，当然可以用单纯形方法求解，但由于显然是一个线性规划问题，当然可以用单纯形方法求解，但由于其约束条件的系数矩阵相当特殊，求解它可以采用其他简便办法。本节其约束条件的系数矩阵相当特殊，求解它可以采用其他简便办法。本节将介绍由康脱洛维奇和希奇柯克两人独立地提出的表上作业法简称将介绍由康脱洛维奇和希奇柯克两人独立地提出的表上作业法简称康康希表上作业法），其实质仍然是先作出一个初始基本可行解，然后希表上作业法），其实质仍然是先作出一个初始

32、基本可行解，然后用最优性准则检验是否为最优并逐次改进直至最优性准则成立。用最优性准则检验是否为最优并逐次改进直至最优性准则成立。 上一页上一页下一页下一页二、初始可行解的选取不难发现，（5.9的约束条件中存在着多余方程。容易证明，只要从中除去一个约束，例如最后一个方程，约束条件就彼此独立了。因而，（5.9是一个具有mn个变量的线性规划，其每一基本可行解应含有m+n1个基变量。记5.9约束条件中前m+n1个方程的系数矩阵为A，A为m+n1）mn矩阵，它的每一列最多只有两个非零元素且非零元素均为1。利用线性代数知识能够判定A中怎样的m+n1个列可以取为基即怎样的m+n1个变量可以取为基变量），为了

33、判明哪些变量对应的列是线性无关的，先引入下面的定义： 上一页上一页下一页下一页定义定义5.3 5.3 （闭回路）（闭回路） xij xij （i=1,m; j=1,ni=1,m; j=1,n的一个子集被称的一个子集被称为一个闭回路，若它可以被排成为一个闭回路，若它可以被排成其中其中 互异，互异， 也互异。也互异。211132222111,jijijijijijixxxxxxtii ,.,1tjj ,.,1用下面的方法可以较方便直观地看出用下面的方法可以较方便直观地看出 xij xij 的一个子集是否为一闭回路：的一个子集是否为一闭回路：作一个作一个m m行行n n列的表格，令格列的表格，令格i

34、,ji,j对应对应 xij xij 。将子集中的变量填于相。将子集中的变量填于相应格中，并将相邻变量或同行或同列用边相连，则此子集为闭回路应格中，并将相邻变量或同行或同列用边相连，则此子集为闭回路当且仅当其点按上述连法作出的折线可构成一个闭回路。当且仅当其点按上述连法作出的折线可构成一个闭回路。例如，当例如，当m=3,n=4m=3,n=4时，时，X1=x12,x13,x23,x24,x34,x32X1=x12,x13,x23,x24,x34,x32和和X2=x12,x14,x24,x21,x31,x32 X2=x12,x14,x24,x21,x31,x32 均为闭回路，见表均为闭回路，见表5.

35、95.9和表和表5.105.10。表(5.9)表(5.10)上一页上一页下一页下一页定理定理5.4 X5.4 X为为 xij xij （i=1,i=1,，m m；j=1j=1，n n的一个子集，的一个子集，X X中的中的变量对应的变量对应的A A中的列向量集线性无关的充要条件为中的列向量集线性无关的充要条件为X X中不包含闭回路。中不包含闭回路。定量定量5.45.4不难用线性代数知识证明，详细证明从略。根据定理不难用线性代数知识证明，详细证明从略。根据定理5.45.4，要选，要选取取5.95.9的一组基变量并进而得到一个基本可行解，只需选取的一组基变量并进而得到一个基本可行解，只需选取xijx

36、ij的的一个子集一个子集X X，X=m+n-1X=m+n-1且且X X中不含闭回路，其中中不含闭回路，其中XX表示表示X X中的变量个中的变量个数。数。 我们从下面的例子来说明如何选取一个基本可行解。我们从下面的例子来说明如何选取一个基本可行解。 例5.3 给定运输问题如表5.11所示，表中左上角的数字为单位运价Cij 。易见，本例是产销平衡的即 。jiba表表5.115.116432销量销量72 31 48 7 359 25 3 310 234 13 11 2 21产量产量4321jiba销地产地上一页上一页下一页下一页现采用现采用“最小元素法求一基本可行解。单位运价最小的为最小元素法求一基

37、本可行解。单位运价最小的为C33=1C33=1，令，令x33=mina3,b3=4,x33=mina3,b3=4,并令并令x13= x23=0 x13= x23=0销地销地3 3已满足），相应格打已满足），相应格打“”。产地产地3 3已运出已运出4 4单位，将产量改为剩余产量单位，将产量改为剩余产量3 3。剩余表中单位运价最小的为。剩余表中单位运价最小的为C11=2C11=2或或C34=2C34=2），令），令x11= min a1,b1=2,x11= min a1,b1=2,并令并令x21= x31=0 x21= x31=0，相应格打，相应格打“”，a1a1改为剩余产量改为剩余产量1 1，直

38、至全部产品分配完毕。注意到除最后，直至全部产品分配完毕。注意到除最后一次分配外每次只能对一行或一列找一次分配外每次只能对一行或一列找“”，表示某销地已满足或某产，表示某销地已满足或某产地产品已分配完当两者同时成立时只能打地产品已分配完当两者同时成立时只能打“”行或列之一，将剩余行或列之一，将剩余需求量或产量记为需求量或产量记为0 0，此时基本可行基是退化的）。容易证明：这样分配，此时基本可行基是退化的）。容易证明：这样分配共选出了共选出了m+n-1m+n-1个变量，且这些变量的集合不含闭回路，从而构成一个基个变量，且这些变量的集合不含闭回路，从而构成一个基本可行解。当每一基变量本可行解。当每一

39、基变量xijxij选取时选取时i i产地的剩余商品量与产地的剩余商品量与j j销地的剩余需销地的剩余需求量总不相等，选出的基本可行解是非退化的。求量总不相等，选出的基本可行解是非退化的。初始基本可行解也初始基本可行解也可按其他方式选取，可按其他方式选取，如如“左上角法等，左上角法等，其方法与原理是类其方法与原理是类似的，左上角法每似的，左上角法每次选取剩余表格中次选取剩余表格中位于最左上角的变位于最左上角的变量，其余均相同。量，其余均相同。上一页上一页下一页下一页三、最优性判别类似单纯形法，可计算非基变量的检验数，存在多种求检验数的方法类似单纯形法，可计算非基变量的检验数，存在多种求检验数的方

40、法求得的结果是相同的），下面介绍计算简便且计算量也较小的求得的结果是相同的），下面介绍计算简便且计算量也较小的“位势位势法法”。引入。引入m+nm+n个量被称为位势个量被称为位势u1u1，umum；u1u1，unun。对每一变。对每一变量量xijxij，引入，引入rij,rij,令令xij=xij=ij- ui-vj(ij- ui-vj(事实上，这一公式与单纯形法求检事实上，这一公式与单纯形法求检验数的公式是相同的验数的公式是相同的) )。对基变量。对基变量xijxij，令，令rij=0rij=0，得到，得到CijCijuiuivj=0 (xijvj=0 (xij为基变量为基变量) ) （5.

41、10) 5.10) 齐次线性方程组齐次线性方程组5.10共有共有m+n个独立方程，但含有个独立方程，但含有m+n个变量。个变量。任取一变量，例如任取一变量，例如u1作为自由变量，便可解出方程组。容易看出，作为自由变量，便可解出方程组。容易看出，u1的的取值不同虽会改变位势的取值但不会改变非基变量的检验数。为方便起取值不同虽会改变位势的取值但不会改变非基变量的检验数。为方便起见，只要令见，只要令u1即可。事实上，我们甚至不必去解方程组即可。事实上，我们甚至不必去解方程组5.10），），而只需令而只需令u1，对所有基变量令，对所有基变量令uivjcij，即，即=ij- ui-vj，在表，在表上逐次

42、求出所有位势，进而再对非基变量上逐次求出所有位势，进而再对非基变量xij计算其检验数计算其检验数rij=ij- ui-vj上一页上一页下一页下一页例如，对表例如，对表5.115.11中取定的基，我们求出位势及非基变量的检验中取定的基，我们求出位势及非基变量的检验数，列于表数，列于表5.125.12中，表中不带圈的数为基变量取值，带圈的数中，表中不带圈的数为基变量取值，带圈的数为非基变量检验数，右上角的数为单位运价为非基变量检验数，右上角的数为单位运价ijij。u1=02 211 133 04 1u1=510 3 35 39 2u3=-210 8 121 42 31 1 = 2= 2 = =2

43、23 3 = 3= 34 4 = 4= 4利用线性代数知识可以证明下列各定理利用线性代数知识可以证明下列各定理( (证明从略证明从略) )：定理定理5.5 5.5 任取一非基变量任取一非基变量 ，将其加入基变量集合中，则在所得，将其加入基变量集合中，则在所得变量集合中存在唯一的闭回路变量集合中存在唯一的闭回路 。易见闭回路中含有偶数个变量，假设易见闭回路中含有偶数个变量，假设 令进基，令令进基，令 =，为保持，为保持平衡条件，位于偶数位置的变量平衡条件，位于偶数位置的变量 必须减少必须减少，而位，而位于奇数位置的变量于奇数位置的变量 则必须增加则必须增加注：注： ）。）。1 1i jx1 11

44、 21,t tti ji ji ji jxxxx1 1i jx1 1i jx1(1, )kki jxkt(1, )k ki jxkt11tjj表表5.125.12上一页上一页下一页下一页定理定理5.6 5.6 设设 是非基变量是非基变量 与基变量集合与基变量集合的并集中唯一的闭回路，若令的并集中唯一的闭回路，若令 =并在闭回路上调整基变量取值并在闭回路上调整基变量取值使之平衡，得一可行解使之平衡，得一可行解x x，则，则x x处的目标值与原基本可行解上的目标值处的目标值与原基本可行解上的目标值之差为之差为 。1 11 21,t tti ji ji ji jxxxx1 1i jx1 1i jx1

45、 1i jr根据定理根据定理5.65.6，若存在检验数，若存在检验数 的非基变量的非基变量 ，取进基，取进基 （取（取正值并令正值并令 （5.125.12）则原取值为则原取值为的位于偶数位置的基变量退基，得到一新的基本可行解，的位于偶数位置的基变量退基，得到一新的基本可行解，其目标值减少其目标值减少 。 1 10i jr1 1i jx1 111mink ki ji jk txx 1 1i jr1 1i jx定理定理5.7 5.7 设设 为为5.95.9的一个基本可行解，若的一个基本可行解，若x0 x0所有非基所有非基变量的检验数均非负，则变量的检验数均非负，则x0 x0必为必为5.95.9的一

46、个最优解。当的一个最优解。当x0 x0非退化非退化时，此条件还是必要的。时，此条件还是必要的。00ijxx证明证明 由定理由定理5.65.6知，当知，当x0 x0所有非基变量的检验数均非负时，任一非基变所有非基变量的检验数均非负时，任一非基变量进基均不会使目标值减小，由于量进基均不会使目标值减小，由于5.95.9是一线性规划，此性质表明是一线性规划，此性质表明x0 x0已为最优基本可行解。反之，则只要令具有负检验数的非基变量进基即可。已为最优基本可行解。反之，则只要令具有负检验数的非基变量进基即可。 上一页上一页下一页下一页综上所述，康综上所述，康希表上作业法可如下操作：希表上作业法可如下操作

47、：（步（步1 1） 按最小元素法或右上角法等求一初始基本可行解。按最小元素法或右上角法等求一初始基本可行解。（步（步2 2） 按按5.105.10求出位势求出位势ui,jui,ji=1,m; j=1,ni=1,m; j=1,n）。进）。进而按而按5.115.11求出非变量的检验数求出非变量的检验数rijrij。若一切。若一切rij0rij0，则已求得一，则已求得一最优解。最优解。（步（步3 3） 任取一任取一00，找出进基后形成的唯一闭回路。在找出的闭回，找出进基后形成的唯一闭回路。在找出的闭回路上调整，按路上调整，按5.125.12取取，得出新的基本可行解，返回步，得出新的基本可行解，返回步

48、2 2。直至。直至找到最优解。找到最优解。 上一页上一页下一页下一页对于例对于例5.35.3，表，表8.128.12已给出非基变量的检验数。因已给出非基变量的检验数。因r230r230，令，令x23x23进基，进基，得闭回路得闭回路x23, x24, x34, x33x23, x24, x34, x33取取=min x24, x33 =2=min x24, x33 =2，调整后得一新的基本可行解。求出新的基，调整后得一新的基本可行解。求出新的基本可行解、对应的位势及非基变量检验数，列成表本可行解、对应的位势及非基变量检验数，列成表5.135.13。表表5.135.13u1=02 211 113

49、 4 1u1=310 3 35 29 u3=17 8 1 23 51 1 = 2= 2 = 0= 03 3 = 3= 34 4 = 4= 4如今，非基变量检验数均已非负，故已求得最优解：如今，非基变量检验数均已非负，故已求得最优解：x11=2x11=2，x14=1x14=1，x22=3x22=3，x23=2x23=2，x33=2x33=2，x34=5x34=5，其余，其余 =0=0非基变量）。非基变量）。若运输问题是产销不平衡的，则应先将其转化为产销平衡的，然后再若运输问题是产销不平衡的，则应先将其转化为产销平衡的，然后再求解。例如，若产大于销，可虚设一销地剩余产量存贮），将单位求解。例如，若

50、产大于销，可虚设一销地剩余产量存贮），将单位运价取为零即可。运价取为零即可。ijx上一页上一页下一页下一页一、指派问题的数学模型5.3 指派问题 例例5.4 5.4 拟分配拟分配n n人去干人去干n n项工作，每人干且仅干一项工作，若分配第项工作，每人干且仅干一项工作，若分配第i i人人去干第去干第j j项工作，需化费项工作，需化费CijCij单位时间，问应如何分配工作才能使工人化单位时间，问应如何分配工作才能使工人化费的总时间最少？费的总时间最少？容易看出，要给出一个指派问题的实例，只需给出矩阵容易看出，要给出一个指派问题的实例，只需给出矩阵C=C=（CijCij）,C,C被被称为指派问题的

51、系数矩阵。称为指派问题的系数矩阵。引入变量引入变量xijxij，若分配，若分配i i干干j j工作，则取工作，则取xij =1xij =1，否则则取，否则则取xij =0 xij =0。上述。上述指派问题的数学模型为指派问题的数学模型为 S.t S.t （5.135.13） xij=0 xij=0或或1 111minnnijijijC x 11nijjx11nijix上一页上一页下一页下一页（5.135.13的可行解既可以用一个矩阵表示，其每行每列均有且只有的可行解既可以用一个矩阵表示，其每行每列均有且只有一个元素为一个元素为1 1，其余元素均为，其余元素均为0 0，也可以用，也可以用1,n1

52、,n中的一个置换表示。中的一个置换表示。 （5.135.13的变量只能取的变量只能取0 0或或1 1，从而是一个，从而是一个0101规划问题。下一章将规划问题。下一章将指出指出 ，一般的，一般的0101规划问题的求解极为困难。但指派问题规划问题的求解极为困难。但指派问题5.13 5.13 ）并不难解，其约束方程组的系数矩阵十分特殊被称为全单位模矩并不难解，其约束方程组的系数矩阵十分特殊被称为全单位模矩阵或全幺模矩阵，其各阶非零子式均为阵或全幺模矩阵，其各阶非零子式均为1 1），其非负可行解的分），其非负可行解的分量只能取量只能取0 0或或1 1，故约束，故约束“xij=0 xij=0或或1 1

53、可改写为可改写为xij0 xij0而不改变其解。而不改变其解。此时，（此时，（5.135.13被转化为一个特殊的运输问题，其中被转化为一个特殊的运输问题，其中m=n, ai=bi=1m=n, ai=bi=1。上一页上一页下一页下一页二、求解指派问题的匈牙利算法由于指派问题的特殊性，又存在着由匈牙利数学家由于指派问题的特殊性，又存在着由匈牙利数学家KonigKonig提出的更为简提出的更为简便的解法便的解法匈牙利算法。算法主要依据以下事实：如果将系数矩阵匈牙利算法。算法主要依据以下事实：如果将系数矩阵C=C=（CijCij中一行或一列的每一元素都加上或减去同一个数，得到中一行或一列的每一元素都加

54、上或减去同一个数，得到一个新矩阵一个新矩阵B=B=（bijbij），则以），则以C C和和B B为系数矩阵的指派问题具有相同的最为系数矩阵的指派问题具有相同的最优指派。优指派。 例例5.5 5.5 求解指派问题，其系数矩阵为求解指派问题，其系数矩阵为 16151922172119182422181717192216C上一页上一页下一页下一页解解 将第一行元素减去此行中的最小元素将第一行元素减去此行中的最小元素1515，同样，第二行元素减，同样，第二行元素减去去1717，第三行元素减去，第三行元素减去1717，最后一行的元素减去，最后一行的元素减去1616，得，得1104704217510136

55、0B*2*1037041175001350B再将第再将第3 3列元素各减去列元素各减去1 1，得，得以以B2B2为系数矩阵的指派问题有最优指派为系数矩阵的指派问题有最优指派由等价性，它也是例由等价性，它也是例2 2的最优指派。的最优指派。有时问题会稍复杂一些，见下面的例有时问题会稍复杂一些，见下面的例5.65.612342134上一页上一页下一页下一页例例5.6 5.6 求解下面的系数矩阵为求解下面的系数矩阵为C C的指派问题的指派问题12797989666717121412151466104107106C解：先作等价变换如下解：先作等价变换如下*7 127979502026 89666230

56、007 7171214120105756 15146610980044 410710606362 容易看出，从变换后的矩阵中只能选出四个位于不同行不同列的零元素，容易看出，从变换后的矩阵中只能选出四个位于不同行不同列的零元素，但但n=5n=5，最优指派还无法看出。此时等价变换还可进行下去，最优指派还无法看出。此时等价变换还可进行下去 。 上一页上一页下一页下一页步骤如下：步骤如下：（1 1对未选出对未选出0 0元素的行打元素的行打；（2 2对对行中行中0 0元素所在列打元素所在列打；（3 3对对列中选中的列中选中的0 0元素所在行打元素所在行打；反复反复2 2）、（）、（3 3直到无法再打直到

57、无法再打为止。为止。可以证明，若用直线划没有打可以证明，若用直线划没有打的行与打的行与打的列，就得到了能够复盖住的列，就得到了能够复盖住矩阵中所有零元素的最少条数的直线集合。找出未复盖的元素中的最小矩阵中所有零元素的最少条数的直线集合。找出未复盖的元素中的最小者，令者，令行元素减去此数，行元素减去此数，列元素加上此数，则原先选中的列元素加上此数，则原先选中的0 0元素不元素不变，而未复盖元素中至少有一个已转变为变，而未复盖元素中至少有一个已转变为0 0，且新矩阵的指派问题与原，且新矩阵的指派问题与原问题也等价。上述过程可反复采用，直到能选出足够的问题也等价。上述过程可反复采用，直到能选出足够的

58、0 0元素为至。例元素为至。例如，对例如，对例8.68.6变换后的矩阵再变换，第三行、第五行元素减去变换后的矩阵再变换，第三行、第五行元素减去 2 2，第一，第一列元素加上列元素加上 2 2，得，得70202430000835311800404140现在已可看出，最优指派为现在已可看出，最优指派为1234524135（注：相应定理从略）（注：相应定理从略）上一页上一页下一页下一页5.4 计算复杂性问题的提出离散模型的实质是从有限多个候选值中选取一个最佳取值。例如离散模型的实质是从有限多个候选值中选取一个最佳取值。例如8.18.1中中的线性规划，虽然可行解一般有无穷多个，但线性规划基本定理指出，

59、的线性规划，虽然可行解一般有无穷多个，但线性规划基本定理指出，只要存在有限最优解，就必可在基本可行解中找到，而基本可行解总共只要存在有限最优解，就必可在基本可行解中找到，而基本可行解总共只有有限多个。只有有限多个。DantzigDantzig的单纯形法正是利用了这一性质，在基本可行解的单纯形法正是利用了这一性质，在基本可行解中选取最优解。中选取最优解。在有限多个候选者中选择其中之一，通常不存在连续模型中备受关注的在有限多个候选者中选择其中之一，通常不存在连续模型中备受关注的解的存在性问题，因为有限个值中选取最佳取值，解的存在性不成问题。解的存在性问题，因为有限个值中选取最佳取值，解的存在性不成

60、问题。解的唯一性问题也不再被人们重视。例如，在用单纯形法求得一最优基解的唯一性问题也不再被人们重视。例如，在用单纯形法求得一最优基本可行解后，我们认为问题已被解出，它是否还有其他的最优解，我们本可行解后，我们认为问题已被解出，它是否还有其他的最优解，我们一般不再感兴趣。一般不再感兴趣。上一页上一页下一页下一页也许有人会想，从有限种可能方案中挑选一种，这总是比较容易的。也许有人会想，从有限种可能方案中挑选一种，这总是比较容易的。如果一一比较下去，最后总可以得出满意的结果。然而，事实并非如果一一比较下去，最后总可以得出满意的结果。然而，事实并非如此简单，关键在于问题的规模和求解时的计算量。随着电子