第五章线性规划与计算复杂性简介整理ppt.ppt

线性规划与计算复杂性简介 数学建模基地 §5.1 线性规划问题 在人们的生产实践中，经常会遇到如何利用现有资源来安排生产以取得最大经济效益的问题，此类问题构成了运筹学的一个重要分支——数学规划，而线性规划（Linear Programming, 简记LP）则是数学规划的一个重要部分。自从1947年G·B·Dantzig提出求解线性规划的单纯形方法以来，线性规划在理论上日趋成熟 ，在应用上日趋广泛，已成为现代管理中经常采用的基本方法之一。 一.线性规划的实例与定义 例1的数学模型：设该厂生产x1台甲机床和x2台乙机床时总利润最大，则 x1 、x2应满足 二、线性规划的标准形式 如果根据实际问题建立起来的线性规划问题并非标准形 式，可以将它如下化为标准形式： 三、线性规划的图解法 三、基本解与基本可行解 四、基本可行解与极点的等价定理 （线性规划基本定理） 线性规划（5.3）具有以下性质： （1）若可行域R≠Φ，则必存在一个基本可行解。 （2）若问题存在一个最优解 ，则必存在一个最优的基本可行解。 定理5.2并非说最优解只能在基本可行解（极点）上达到，而是说只要（5.3）有有限最优解，就必定可在基本可行解（极点）中找到。 五、求解线性规划的单纯形法 （步1）取一初始可行基B（一般取法见后面的两段单纯形法），再用高斯—约当消去法求出初始基本可行解x0，编制成所谓的初始单纯形表； （步2）判断x0是否最优解，如果x0是最优解，输出x0，停，否则到步3； （步3）按一改进准则，将一个非基变量转变为基变量，而将一个基变量转变为非基变量。这相当于交换B与N的一个列，同样可用高斯—约当消去法，运算可以通过单纯形表上的“转轴运算”实现。 六、初始可行解的求法——两段单纯形法 §5.2 运输问题 二、初始可行解的选取 三、最优性判别 §5.3 指派问题 二、求解指派问题的匈牙利算法 §5.4 计算复杂性问题的提出 一、P类与NP类，NP完全性 二、有关离散问题模型及其算法的几点附加说明 例5.12 （SAT问题） 给定布尔变量x1,…,xn的一个布尔表达式c1·c2·…·cm，其中ci为用x1,…,xn构成的句子，问此表达式是可满足的吗？ SAT问题是数理逻辑中的中心问题之一，这一点可从计算机的运算方式看出，故设计一个较好的求解SAT问题的算法具有重要意义。 1972年，R.M.Karp 以多项式转化的方式证明并列出21个NP完全问题。此后，大量NP完全问题一一被证明。短短十几年时间，已知的NP完全问题就达到了 4000多个，其中包括前面提到过的HC和TSP。总之，NP完全类是一个极为庞大的问题类，其中包含着无穷多个问题。按照目前普遍的看法，这些问题中的任意一个都不应当有多项式算法，即求解它的任一算法在遇到最“坏”的实例时都需要化指数时间。 P类、NP完全类及NP类的关系如图8.3所示，即，NP完全类。还有很多离散问题目前尚未搞清它们的计算复杂性。有些将被证明是P问题，有些将被证明是 NP完全的。此外，确实存在着NP以外的问题，其求解更为困难。 最近几十年来，有成千上万离散问题的模型得到了广泛而又较为深入的研究。因而，当我们研究一个离散型的问题时，首先要搞清遇到的实际课题是否为某一别人已研究过的问题的一个实例。搞清这一点十分重要，否则你的努力完全可能是一种徒劳。 例5.13 某工厂在生产一种产品或部件时，需要在一些指桑骂槐定位置上钻孔。问应按怎样的顺序钻孔，才能使加工速度最快。 由于生产是连续进行的，钻头将从一钻孔位置出发到各指定点钻孔，最后返回原位置，以便加工下一个产品或部件。显然，这是一个旅行商问题。 然而，是否为某一问题的实例有时并不是一目了然的。 例5.14 在轧钢等生产中，为了保持工件的温度，工件在一台机器上加工以后必需立即转送下台机器加工，中间不允许出现工件等待现象。现设共有n个工件Ji(i=1,…,n)需要进行加工，且加工有以下特点： （i）加工不同工件时，使用机器的顺序可以不同。 （ii）每一工件在每台机器上至少加工一次。 （iii）每台机器加工各工件的顺序相同。 （iv）工件加工中不允许有中间等待。 要求确定{1,…,n}（工件编号）的一个排序{i1,…,in}，使得总加工时间最少。 例5.13是排序（Scheduling）问题的一个子问题，这个子问题的计算复杂性如何呢？下面的分析表明，这一子问题实质上就是旅行商问题，从而是NP—完全的。 图5.4给出了一个三台机器二个工件的实例。工作Ji需加工5次，依次使用机器2→1→2→5→2。工作Ji需加工4次，依次使用机器1→2→3→1。该图是设先加工Ji作出的，图中的点表示加工活动，旁边的数字为加工时间，箭线反映加工顺序。 由图5.