第5章线性规划与计算复杂性简介

1线性规划与计算复杂性简介张文博北京邮电大学上一页 下一页28.1 线性规划问题一 、 线性规划的实例与定义二、线性规划的标准形式三、线性规划的图解法四、基本可行解与极点的等价定理五、求解线性规划的单纯形法六、初始可行解的求法 两段单纯形法8.2 运输问题一 、 运输问题的数学模型三、最优性判别二、初始可行解的选取8.3 指派问题一、指派问题的数学模型二、求解指派问题的匈牙利算法8.4 计算复杂性问题的提出一、 P类与 NP类， NP完全性二、有关离散问题模型及其算法的几点附加说明上一页 下一页38.1 线性规划问题在人们的生产实践中，经常会遇到如何利用现有资源来安排生产以取得最大经济效益的问题，此类问题构成了运筹学的一个重要分支 数学规划，而线性规划（ Linear Programming, 简记 LP）则是数学规划的一个重要部分。自从 1947年 GBDantzig提出求解线性规划的单纯形方法以来，线性规划在理论上日趋成熟 ，在应用上日趋广泛，已成为现代管理中经常采用的基本方法之一。上一页 下一页4一 .线性规划的实例与定义例 8.1 某机床厂生产甲、乙两种机床，每台销售后的利润分别为 4000元与 3000元。生产甲机床需用 A、 B机器加工，加工时间分别为每台 2小时和 1小时；生产乙机床需用 A、 B、 C三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为 A机器 10小时、 B机器 8小时和 C机器 7小时，问该厂应生产甲、乙机床各多少台，才能使总利润最大？上一页 下一页5例 1的数学模型：设该厂生产 x1台甲机床和 x2台乙机床时总利润最大，则 x1 、 x2应满足 max 4x1 + 3x2 s.t 2x1 + x2 10x1 + x2 8 (8.1)x2 7x1 , x2 0（ 8.1）式中 4x1 + 3x2表示生产 x1台甲机床和 x2台乙机床的总利润，被称为问题的目标函数，当希望使目标函数最大时，记为 max；反之，当希望使目标函数最小时，记为 min。（8.1）中的几个不等式是问题的约束条件，记为 S.t（即Subject to）。由于（ 8.1）式中的目标函数及约束条件均为线性函数，故被称为线性规划问题。总之，线性规划问题是在一组线性约束条件的限止下，求一线性目标函数最大或最小的问题。上一页 下一页6二、线性规划的标准形式例 8.2minS.t i=1, m xj0, j=1, n线性规划的目标函数可以是求最大值，也可以是求最小值，约束条件可以是不等式也可以是等式，变量可以有非负要求也可以没有非负要求（称这样的变量为自由变量）。为了避免这种由于形式多样性而带来的不便，规定线性规划的标准形式为利用矩阵与向量记为min z = CT x S.t Ax = bx0 （ 8.3）其中 C 和 x 为 n 维列向量， b为 m 维列向量， b0 ， A为 m n矩阵 ,m0 ，则称 x=（ B-1b ， 0）为（ 8.3）的一个非退化的基本可行解，并称 B为非退化的可行基。由于基矩阵最多只有 种不同的取法，即使 A的任意 m解均线性无关，且对应的基本解均可行，（ 8.3）最多也只能有个不同的基本可行解。上一页 下一页12四、基本可行解与极点的等价定理在线性规划的求解中，下列定理起了关键性的作用。在这里，我们不加证明地引入这些定理。定理 8.1 （基本可行解与极点的等价定理）设 A为一个秩为 m的 m n矩阵（ nm） b为 m维列向量，记 R为（ 8.3）的可行域。则 x为 R的极点的充分必要条件为x 是 的基本可行解。定理 8.1既提供了求可行域 R的极点的代数方法，又指明了线性规划可行域 R的极点至多只有有限个 .对定理证明有兴趣的读者可以参阅 D.G.鲁恩伯杰著的 “线性与非线性规划引论 ”一书第二章上一页 下一页13（线性规划基本定理） 线性规划（ 8.3）具有以下性质：（ 1）若可行域 R ，则必存在一个基本可行解。（ 2）若问题存在一个最优解 ，则必存在一个最优的基本可行解。定理 8.2并非说最优解只能在基本可行解（极点）上达到，而是说只要（ 8.3）有有限最优解，就必定可在基本可行解（极点）中找到。定理 8.2从模型本身讲，线性规划显然应属连续模型。但定理 2表明，如果线性规划有有限最优解，我们只需比较各基本可行解上的目标函数值即可找到一个最优解，而问题的基本可行解至多只有有限个，从而问题化为一个从有限多个点选取一个最优点 的问题。正是基于这样一种思路， Dantzig提出了求解线性规划的单纯形法。也正因为如此，我们把线性规划列入了离散模型，因为求解它的单纯形法更具有离散模型问题的算法特征。上一页 下一页14五、求解线性规划的单纯形法（步 1）取一初始可行基 B（一般取法见后面的两段单纯形法），再用高斯 约当消去法求出初始基本可行解 x0，编制成所谓的初始单纯形表；（步 2）判断 x0是否最优解，如果 x0是最优解，输出 x0，停，否则到步 3；（步 3）按一改进准则，将一个非基变量转变为基变量，而将一个基变量转变为非基变量。这相当于交换 B与 N的一个列，同样可用高斯 约当消去法，运算可以通过单纯形表上的 “转轴运算 ”实现。Dantzig单纯形法的基本步骤如下：上一页 下一页15设 B为一非退化的可行基， x=（ B-1b， 0）为其对应的基本可行解。现在，我们先来讨论如何判别 x0是否为最优解。为此，考察任一可行解 。由 Ax=b可得（ 8.5）代入目标函数，得到定理 8.3 （最优性判别定理） 令 。（ 1）若 rN0，则 x0必为（ 8.3）的一个最优解。（ 2）记 。若 ， rj0 ，根据（ 7.15）式知，当且充分小时，仍有 xB0 。此时对应的 x仍 为可行解，但由（ 8.6），其目标函数值：故 x0必非最优解。定理 8.3不仅给出了判别一个基本可行解是否为最优解的准则，而且在 x0非最优解时还指出了一条改进它的途径。由于 rN在判别现行基本可行解是否为最优解时起了重要作用，所以 rN被称为 x0处的检验向量，而 rj (j N)被称为非基变量 xj的检验数。上一页 下一页17有趣的是上述过程完全可以在以下的单纯形表上进行。先将CT、 A、 b及数 0写在一个矩阵中，在表上用高斯 约当消去法解方程组 Ax=b高斯 -约当消去法（第一行不变）利用单位矩阵 I消第一行的为零向量，则 被消成，而 0则被消成 。将消去后的行向量写到最后一行，删去原来的第一行，得到一张被称为单纯表的表格：xB xNI B 1N B 1b0 rN Z0(8.7)表格（ 8.7）以极为简洁明了的方式表达了我们需要的全部信息。从其前 m行可看出哪些变量是基变量并可直接读出对应的基本可行解 x0=（ B 1b， 0）。其最后一行又给出了非基变量的检验数及 x0处目标函数值的相反数。上一页 下一页18例 8.1的标准形式为（ 8.4），容易看出它的一个初始基B=I（以 x3、 x4、 x5为基变量），且 CB已经为零，故我们已有了一张初始的单纯形表表 8.1： 表 8.1x1 x2 x3 x4 x5基变量x3 1 1 0 0 10x4 1 1 0 1 0 8x5 0 1 0 0 1 7rj 4 3 0 0 0 0x0=(0,0,10,8,7)Tz0=CTx0=0rN=(r1,r2)=( 4， 3)现在，我们以例 8.1为例，来看一下单纯形法是如何工作的。上一页 下一页19由于存在着负的检验数且 x0非退化， x0非最优解。 r1， r2均为负， x1， x2增大（进基）均能改进目标函数值。 例如，取 x1进基仍令 x2=0（ x2仍为非基变量），此时由（ 8.5）式及（ 8.6）式有且 z = CTx = 4x1x1增加得越多，目标函数值下降得越多，但当 x1 =5时 x3=0， x1再增大则x3将变负。为保证可行性， x1最多只能增加到 5，此时 x3成为非基变量（退基）。 不难看出，上述改进可以在单纯形表上进行。对于 一般形式 的单纯形表，记最后一列的前 m个分量为（ yi0）， i=1, ,m。若取 进基，记 j0列前 m个分量为（ ）， i=1, ,m。易见，阻碍 增大的只可能在0的那些约束中。若 0对一切 i=1, ,m成立（ j0列前 m个分量中不存在正值），则 可任意增大，得到的均为可行解，但其目标值随之可任意减小，故问题无有限最优解。 上一页 下一页20否则，令则随着 的增大，将 最先降为零（退出基变量），故只需以 为主元作一次消去法运算（称此运算为一次转轴运算），即可得到改进后的基本可行解处的单纯形表。在本例中，因取 x1进基（ j=1） 而，以 y11为主元作第一次转轴，得到 x1=(5,0,0,3,7)T z1= 20 rN=(r2,r3)=( 1， 2)20002 10rj710010x5301 -0x45001x3基变量x5x4x3x2x1表 8.2上一页 下一页21表 8.2中 r20） 最小选定以下y22 = 为主元转轴，得到下一基本可行解 x2处的单纯形表表 8.3。表 8.3x1 x2 x3 x4 x5基变量x3 1 0 1 0 2x4 0 1 0 6x5 0 0 1 1rj 0 0 0 26x2=(2,6,0,0,1)Tz2= 26rN=(r3,r4)=(1， 2)对 于 x2， rN= (1， 2)为 非 负 向量，故 x2为 最 优 解，最 优 目 标值为 26。于是，原 问题 例 1的最 优 解 x*=(2,6)T，最 优 目 标值为 26。 上一页 下一页22六、初始可行解的求法 两段单纯形法阶段 2 若辅助规划的最优目标值不等于零，原规划无可行解。否则我们已求得原问题的一个基本可行解 x0。删去阶段 1最终单纯表中最后一行及对应人工变量的列，作出原规划对应x0的初始单纯形表。此时又可利用上述单纯形法求解原规划了。阶段 1 对第 i个约束引入人工变量 yi， yi0 ，将其改写为ai1x1+ + ainxn+yi=bi， i=1, ,m。作辅助线性规划 LP（ 1），其目标函数为 。容易看出，原规划有可行解（从而有基本可行解）的充分必要条件为辅助规划的最优目标值为零。由于辅助规划具有明显的初始可行基（人工变量对应的列构成单位矩阵 I），可利用上述单纯形法逐次改进而求出辅助规划最优解。上一页 下一页23例 8.2 min 4x1+ x2+ x3S.t 2x1+ x2+2x3 = 43x1+ 3x2+x3 = 3x1、 x2、 x30?解 ： 因为初始可行基不能直接看出，我们采用两段单纯形法求解。阶段 1 先求解辅助规划：min x4+ x5S.t 2x1+ x2+2x3 + x4= 43x1+ 3x2+x3+ x5 = 3x1， ， x30上一页 下一页24表 8.4x1 x2 x3 x4 x5基变量x4 2 1 2 1 0 4x5 3 1 0 1 3rj 5 4 3 0 0 7选取 x1进基，以 y21=3为主元转轴（ x5出基），得表 8.5。表 8.5x1 x2 x3 x4 x5基变量x4 0 1 4/3 1 2/3 2x1 1 1 1/3 0 1/3 1rj 0 1 4/3 0 5/3 2上一页 下一页25因 r3 0 。当 B 1b也存在零分量时，我们遇到了一个退化的基本可行解。此时 rN存在负分量不一定说明现行基本可行解不是最优解，单纯形法也可能会遇到循环迭代。存在着几种避免循环的技巧，例如，只要每次在 rj0的非基变量中选取具有最小足标者进基即可。 在求解线性规划时，首先应将问题化为标准形式。若从标准形式已可看出一个初始基，则可直接用单纯法求解：（ 1）写出初始单纯形表；（ 2）若检验向量 rN 0 ，则已得以最优解；（ 3）任选一负分量 rj。以 进基，考察 所在列。若对 i=1, ,m均有 0，则问题无有限最优解，停；否则令，以 为主元转轴，返回（ 2），直至 rN0 求出最优解。若从标准形式无法看出初始可行基，则需采用两段单纯形法求解。变量同时具有上、下界限止的线性规划问题也可化为标准形式求解，有兴趣的读者可以参阅 D.G.鲁恩伯杰的 “线性与非线性规划引论 ”一书的第三章。 上一页 下一页288.2 运 输问题一 .运输问题的数学模型 例 8.3 某商品有 m个产地、 n个销地，各产地的产量分别为a1, ,am各销地的需求量分别为 b1, ,bn。若该商品由 i产地运到 j销地的单位运价为 Cij，问应该如何调运才能使总运费最省 ? 解 ： 引入变量 xij，其取值为由 i产地运往 j销地的该商品数量。例 8.3的数学模型为min S.t ， i=1, m (8.9)， j=1, nxij 0（ 8.9）显然是一个线性规划问题，当然可以用单纯形方法求解，但由于其约束条件的系数矩阵相当特殊，求解它可以采用其他简便办法。本节将介绍由康脱洛维奇和希奇柯克两人独立地提出的表上作业法（简称康 希表上作业法），其实质仍然是先作出一个初始基本可行解，然后用最优性准则检验是否为最优并逐次改进直至