第2章 线性规划.doc

第2章 线性规划2.1 线性规划的基本定理2.1.1 线性规划发展简史 19世纪末，康特罗维奇和F. L. Hitchcock等研究运输问题，但其工作长期未被人们所知。由于战争的需要，T. C. Koopmans重新独立研究了运输问题。 1947年，G. B. Dantzig发表单纯形法，应用于与国防有关的问题。该法实用而有效。单纯形法被认为是20世纪10大算法之一（其中还有快速Fourier变换算法等）。 但1972年，V. Kell和G. Minty给出病态例子，用单纯形法求解可能要检查遍所有的顶点才能得到最优解，所用时间为. 故单纯形法为指数时间算法。 1979年，前苏联数学家提出了一种求解LP的椭球算法，计算复杂性为(为输入长度)。该算法在理论上很重要，但计算效率远不如单纯形法有效。 能否找到有效的多项式时间算法？在此背景下，1984年，在美国贝尔实验室工作的印度数学家Karmarkar给出了一个求解线性规划的新的多项式时间算法，计算复杂性为。通过例题试算，收敛到较好效果，人们希望借助这种算法解决一些领域中的大规模问题的计算。 对于现实生活中的大多数实际问题，单纯形法仍然有效. 基于单纯形法可以方便地讨论线性规划的对偶理论，而基于对偶理论可以设计求解LP的对偶单纯形法和原始对偶算法及其它算法，因此单纯形法是目前应用最广泛的算法之一。 LP之所以重要有以下方面的原因： 理论算法发展较完善 现实生活中许多问题可用LP近似建模 在非线性规划的求解中，将问题局部线性化处理2.1.2 标准形式与基本定理 LP标准形： s.t. LP向量形式： s.t. 其中.约定：为决策变量，为费用（价格）系数，为目标函数，为技术系数，为右端项. 各种形式的线性规划都可以化为标准形：(i) (ii) (引入松弛变量)(iii) (引入剩余变量) (iv) 无非负限制，令 (v) ，令(平移变换) 例 s.t. 令标准形： s.t. ，图解法例 s.t. 有唯一最优解。例 s.t. 有无穷个最优解。例 s.t. 此问题无上界，从而无有限最优解例 s.t. 问题无可行解，从而无最优解。由以上几个例子可以看出以下几个结论： (i) 可行域为空集，原问题无可行解；(不可行，无最优解) (ii) 目标函数可行域上无界；(可行，无有限最优解) (iii) 有唯一最优解；(有最优解，可在顶点达到) (iv) 有无穷多最优解；(有最优解，可在顶点达到) 猜想：求解一个LP问题可能有三种情况：不可行、无界和有最优解；线性规划若有最优解，则一定可以在可行域的某个“顶点”达到。线性规划的基本定理设可行域的极点为,极方向为.根据多面集的表示定理,任何可行点可表示为：将x代入LP标准型, 得到以为变量的等价LP:s.t. (i) 可任意大, 因此若对某个j有,则随的增大无限减小, 目标函数值趋向. 对于这种情形, 称该问题是无界的, 或不存在有限最优解.(ii) 如果对于所有的j有,这时为极小化目标函数,令, LP简化为s.t. , 令, 显然当及时, 目标函数取极小值. 此时必有因此极点是原LP问题的最优解.定理(基于标准型的线性规划基本定理): 设线性规划问题 s.t. , 的可行域非空,则有下列结论:(1) LP存在有限最优解的充要条件是所有.(2) 若LP存在有限最优解, 则目标函数的最优值可在某个极点上达到. 2.1.3 极点的代数特征设，其中为阶可逆矩阵.记，则，得.令，得称其为(LP)的基本解，对应的矩阵称为基矩阵，简称基。的各分量称为基变量，的各分量称为非基变量。注：基本解的个数最多为：个.例 引入松弛变量，得 则(最多有个基，而线性相关，故共有5个基)(i)令，则得 (ii)令，则；(iii) 令，则；(iv) 令，则；(v) 令，则； 若，称其为(LP)的基本可行解，对应的矩阵称为可行基矩阵，简称可行基。 5个基本解，除外，都是基本可行解。称为与基本可行解(与基)对应的单纯形乘子。对于LP，可行域的基本可行解与极点是等价的。 引理：设为的极点的充要条件是中与的所有正分量对应的列线性无关。 定理:在(LP)的标准形中，若，则的极点集与(LP)的基本可行解集相同。可行域的极点与基本可行解是一一对应的: (LP)的最优解可在某极点达到(LP)的最优解可在某基本可行解处达到 若，则有极点若，则有基本可行解2.2 单纯形算法2.2.1 基本原理定理: 若(LP)的可行域非空，即，且，则 (i) (LP)有基本可行解； (ii) (LP)存在有限最优解的充分必要条件是(LP)的价格系数与可行集的所有极方向的夹角小于90度，即对的所有极方向成立； (iii) 若(LP)有有限最优解，则其最优值可在某个基本可行解上达到。线性规划解的代数特征的一个重要应用就是单纯形算法的提出。 单纯形法的基本思路：用迭代法从一个基本可行解(极点)转换到另一个基本可行解(另一极点)，每一步转换只将一个非基变量(指一个分量)变为基变量，称为进基，同时将一个基变量变为非基变量，称为离基。 进基变量和出基变量的确定原则：应使新的基本解可行，同时目标函数值有一定的下降。 实现该思路的算法要解决以下问题： (1) 选取初始基本可行解(极点)； (2) 判断当前基本可行解是否是最优解，或判断问题无界； (3) 确定进基和离基变量。 定理(判定定理)：设为(LP)的一基本可行解，对应基为。(1) (最优判别)若，即则为(LP)的最优基本可行解； (2) (无界判别)若存在使，且，则(LP)无有限最优解，即极小化问题无下界。2.2.2 算法步骤与单纯形表极小化问题的计算步骤: 首先给定一个初始基本可行解,设初始基为B.(l)计算，令，计算目标函数值.(2)求单纯形乘子对于所有非基变量，计算判别数令若, 则对于所有非基变量，对应基变量的判别数总是零，停止计算，现行基本可行解是最优解否则，进行下一步(3)计算，若，则停止计算，问题不存在有限最优解否则，进行步骤(4). (4)确定下标r，使.为离基变址，为进基变量. 用替换，得到新的基矩阵B，返回步骤(1).用单纯形方法求解LP问题的过程，实际上就是解线性方程组只是在每次迭代中，要按一定规则选择自由未知量，以便能够得到改进的基本可行解这个求解过程可以通过变换单纯形表来实现线性规划标准型等价于如下形式(2)式两端左乘，得到即把基变量的系数矩阵化为单位矩阵.再用左乘（3）式两端，然后加到（1）式，得到等价问题：单纯形表:右端010上半部包含m个行，其中有个列,对应非基变量是m维列向量.令非基变量, 则基变量下半部只有1行, 各分量是对应非基变量的判别数.是在现行基本可行解处的目标函数值100010001000例: 求解LP问题s.t. 引入松弛变量, 转化为标准型:s.t. 选择初始的可行基指标集, 依次得到的可行基指标集为, .原问题的最优解为, 目标函数最大值为11.2.2.3 启动机制1.两阶段法标准形式的线性规划问题: (5)若A中含有m阶单位矩阵，则初始基本可行解立即得到若A中不包含m阶单位矩阵,就需要用某种方法求出一个基本可行解两阶段法的第一阶段提供了求初始基本可行解的方法 为使约束方程的系数矩阵中含有m阶单位矩阵，引入非负人工变量: (6)即 (7)显然，是（7）式的一个基本可行解.若从（7）式已知的基本可行解出发，能求出一个使的基本可行解，就可得到（5）式的一个基本可行解两阶段法的第一阶段，是用单纯形方法消去人工变量，即把人工变量都变换成非基变量，求出原来问题的一个基本可行解消去人工变量的一种方法是解下列第一阶段问题： (8)设线性规划（8)的最优基本可行解是，必有三种情形之一：(1) ，这时线性规划（5）无可行解因为如果（5）存在可行解，则是（8）的可行解在此点，问题（8）目标函数值而是目标函数的最优值，矛盾(2) 且的分量都是非基变量这时m个基变量都是原来的变量，又知是（8）的基本可行解，因此是（5）的一个基本可行解.(3) 且的某些分量是基变量这时，可用主元消去法，把原来变量中的某些非基变量引进基，替换出基变量中的人工变量，再开始两阶段法的第二阶段两阶段法的第二阶段，就是从得到的基本可行解出发，用单纯形方法求线性规划(5)的最优解例: 用两阶段法求下列问题的最优解： (9)先引进松弛变量把问题化成标准形式,为使标准形式中约束方程的系数矩阵包含3阶单位矩阵，还要引进人工变量先解一阶段问题：11-1001021-10-100111000100320-1-1000302-1101-111-10-10011010110-1202-1100-2101-1/21/201/2-1/21/210-1/2-1/201/21/23/2001/21/21-1/2-1/23/200000-1-10在一阶段问题的最优解中，人工变量都是非基变量，得到初始基本可行解：.修改最后的单纯形表去掉人工变量和下面的列，把最后的判别数行按原来问题进行修正开始第二阶段迭代，即极大化目标函数01-1/21/201/210-1/2-1/203/2001/21/213/200-1/2-3/205/202-110111-10020-1101103-20040101121000130-11011010026得到线性规划（9）的最优解:目标函数最优值 2. 大M法基本思想：在约束中增加人工变量，同时修改目标函数，加上罚项在极小化目标函数的过程中，由于大M的存在，将迫使人工变量离基线性规划问题(5)引入人工变量后构造新的线性规划问题： (10)用单纯形方法求解线性规划(10 )，结果必为下列几种情形之一：(l) 达到线性规划（10）的最优解，且此时，得到的x即为问题（5）的最优解(2）达到线性规划（10）的最优解，且. 这时，线性规划（5）无可行解如果（5）有可行解，比如说，则, 是（10）的可行解(10)在这一点的目标函数值设（10）的最优解是, 则最优值由于M是很大的正数，因此可以很大,从而可推知，这与为最优值矛盾 (3)规划（10）不存在有限最优值，在单纯形表中，这时，线性规划（5）无界 (4）规划（10）不存在有限最优值，在单纯形表中，有些人工变量不等于零，即这时，线性规划（5）无可行解例：用大M法求解下列问题：引进松弛变量和人工变量，用单纯形方法解下列问题：1-2110001121-40-110310-2000110000-23100-1100100-11-2110-20001101000031-22-5120100-11-2110-2000110010-120011/3-2/32/3-5/340100-11-211002/3-4/34/3-7/39000-1/3-1/3-2人工变量, 原来问题的最优解目标函数最优值 * 单纯形法的改进与推广（自学）-退化情形的处理-修正单纯形法2.3 线性规划的内点算法2.3.1 Karmarkar算法线性规划的可行域是多面体，在最优解存在时目标函数的最优值必能在某顶点（极点）取到给定初始可行解后，沿着什么样的路径到达最优解集是各种求解LP算法所关心的主要问题-单纯形算法沿着多面体的边移动，从一个顶点到达另一个对目标函数有改进的顶点；-椭球算法是一种外点法，从多面体的外部不断地逼近，最后找到它的一个内点-Karmarkar投影尺度算法是一种内点算法,由初始可行解出发穿越可行域的内部到达最优解1.Karmarkar投影尺度算法的基本思想Karmarkar注意到两个基本的事实：(l)如果一个内点居于多面体中心，那么目标函数的最速下降（投影）方向是比较好的可行方向；(2)在不改变问题基本特性条件下，存在一个适当的变换，能将可行域中给定内点置于变换后可行域的中心。根据这两个基本事实，Karmarkar构造了一个求解LP 问题的投影尺度算法Karmarkar投影尺度算法的基本思想：(1) 选定一个内点解作为迭代过程初始点，利用可行域投影尺度变换，将当前内点解置于变换后的可行域中心；(2) 在变换后的可行域中沿着目标函数最速下降方向的正交投影移动，获得新的可行内点.(3)通过投影尺度逆变换将新的可行内点映射到原来的可行域，作为新的迭代点重复这一过程直至求出满足一定精度的近优解2.Karmarkar标准形 （1）A是的满秩矩阵, 是分量均为1的向量称LP问题（1）为Karmarkar标准形如果问题（1）的可行解x的每个分量都大于零，那么称x为一个内点解Karmarkar两个基本假设:假设A：是一个内点解，即；假设B: Karmarkar标准形（1）的最优值为零3单纯形Karmarkar标准形（1）的后两个约束在n维空间中定义了一个多面体称为维单纯形S的内部记为，其顶点为单位向量中心点为单纯形S外接球半径:内切球半径：外接球与内切球半径之比：4单纯形S的投影尺度变换假设,即,矩阵考虑一种特殊的投影尺度变换: （2）变换（2）是一个线性分式变换，具有下列性质：(l)是单纯形S上的一一对应，其逆变换也是一个线性分式变换 （3）(2)不改变单纯形上点与点之间的拓扑关系，即该变换将单纯形S的顶点、棱、面等低维单纯形分别变换成相应的顶点、棱、面等低维单纯形；(3)约束在变换（3）下等价于；(4)点d的像是单纯形S的中心.5向量的正交投影设B是矩阵，,由m个行向量生成的空间记为，该空间的正交补空间就是B的零空间n维欧氏空间等于与的直和，对于，存在惟一的，使得，向量和分别称为在和上的正交投影记上正交投影算子矩阵为，则正交投影向量 （4）可以证明，在成立时，正交投影算子矩阵由下式确定 （5）6. Karmarhar投影尺度算法Karmarkar标准形（1）的可行域是一个多面体，即约束矩阵A的零空间和中的n-1维单纯形的交集给定一个可行点,若，则由式（3）定义的线性分式变换可以将Karmarkar标准形（1）等价地转化成如下形式的最优化问题： （6）单纯形S的中心点是最优化问题（6）的可行内点根据Karmarkar假设B，并且注意到分母，（6）等价于一个新的Karmarkar标准形： （7）新的Karmarkar标准形（7）仍然满足Karmarkar假设A和假设B.对于新的Karmarkar标准形（7)，可以从中心点 出发，沿着目标函数的下降方向移动为了保证移动后得到的新点仍是可行内点，移动方向应取为目标函数的最速下降方向在矩阵的零空间上的正交投影，即 （8）新的可行内点定义为 （9）是S的内切球半径，参数. Karmarkar投影尺度算法的基本原理：（1）通过投影尺度变换，可将新的可行内点映射到原来可行域，对应着；（2）然后，根据确定新的投影尺度变换，将可行内点重新映射到单纯形S的中心点，由此获得形如（7）的新问题重复以上过程直至求出满意的解 Karmarkar投影尺度算法步骤:步骤1：初始化置,；参数，L是充分大的正整数步骤2：最优性检验若，则算法停止，得到近优解；否则转步骤3. 步骤3：第次迭代令 ) 置，转步骤2. Karmarkar投影尺度算法的计算复杂性：定理：对于Karmarkar标准形问题（1），在Karmarkar假设成立时，若选取步长，则Karmarkar投影尺度算法经过次迭代后停止。7一般LP问题转化为Karmarkar标准形求解任意一个LP问题等价于求解某种形式的Karmarkar标准形任意一个LP问题都可以等价地转化为一个标准形式的LP问题 （10）Karmarkar标准形不过是（10）的一种特例对于标准形式（10），利用线性规划的最优性条件，可以将（10）等价地转化为求解某个线性系统: （11）分别是与A,b,c有关的矩阵和向量定理（标准形LP的最优性条件）：对于标准形式的LP问题，其中，则是该问题的最优解，当且仅当存在向量，使得最优性条件将求解LP问题转化为求解代数方程组问题，该代数方程组构成的线性系统有个变量，个方程，以及x和r非负性条件。令 ， ，就可构造出（11）式: 利用伪变量技巧，可将（11）转化为一个LP问题若记，则问题（11）等价于标准形式的线性规划 （12）问题（12）满足如下性质：(1) 是问题（12）的一个可行内点解；(2) 若该问题最优值为零，则得到线性系统（11）的一个可行解，由此可获得原来的线性规划问题的最优解；(3)若该问题最优值大于零，则线性系统（11）无解原线性规划问题(10）无可行解或者无下界.对于（12）中的变量y，考虑如下形式的投影变换：和y的维数均为k(）若记，则（12）等价于Karmarkar标准形： （13）对问题（13）有如下结论：(1) 是一个可行内点解；(2) 若最优值为零，则得到线性系统（11）的一个可行解，由此能获得原LP问题（10）的最优解；(3) 若最优值大于零，则原LP问题（10）无可行解或者无下界例：用Karmarkar投影尺度算法求解线性规划：引进松弛变量转化为(LP)标准形式，其中, , 生成Karmarkar标准形（13）:约束矩阵为=目标函数的梯度向量为, 记号的右下标表示向量维数.算法初始点，步长因子，精度参数L=25初始点Karmarkar标准形的目标函数值为0.0625. 经过97次迭代后，得到LP问题标准形式的近优解：此时Karmarkar标准形目标函数值为.原LP问题目标函数值为-5.2.3.2 内点法运用Karmarkar投影尺度算法，需要把一般LP问题的求解转化为解Karmarkar标准形，计算比较复杂。Karmarkar等人在此基础上，1989年又给出一个内点法，称为对偶仿射尺度算法。采用这种方法，不必把LP问题转化为Karmarkar标准问题，而是通过求解标准LP问题的对偶形式来求解原问题。虽然计算过程简明，并且具有收敛性，但还不知道此算法是否具有多项式时间复杂性。1计算公式的推导考虑线性规划问题 （14）A是矩阵，。先假设存在内点，并假设问题是有界的。算法的基本思想：从内点出发，沿可行方向求出使目标函数值上升的后继点，再从得到的内点出发，沿另一个可行方向求使目标函数值上升的内点。重复以上步骤，产生一个由内点组成的序列，使得当满足终止准则时，则停止迭代。该方法的关键是选择使目标函数值上升的可行方向。首先引进松弛变量，把线性规划（14）写成 （15）在第k次迭代，定义为非负松弛变量构成的m维向量，使得再定义对角矩阵作仿射变换，令把线性规划（15）改写成在变换的空间中，选择搜索方向d作为可行方向，它必是下列齐次方程的一个解 （16）对于（16）式的任一解，有由此得到 （17）每次迭代中，目标函数在方向的方向导数是 （18）把（17）式代入（18）式，则有选择，使得最大，则 （19）由（19）式确定后，可得出（16）式的一个解，其中同时，对作逆仿射变换，可得到搜索方向确定后，还需确定沿此方向移动的步长。设后继点步长的取值应保证为可行域的内点，即满足令 取，其中。这样即可从出发