最优化方法第二章(1)

2.1线性规划的各种形式1.标准形式和典范形式如下形式的线性规划11min..,1,2,,0,1,2,,.njjjnijjijjcxstaxbimxjn称为线性规划的标准形式。jcib其中各称为价格系数，各采用向量－矩阵表示法，标准形式可以简写为。（2.1）称为右端项。min;..0.TcxstAxbx（2.2）在进行理论分析时，有时需要把A表示成12[,,,],nAaaa这样，（2.2）中的Axb又可写成1njjjxabAm若中有个列向量可以合并成为单位矩阵，且0b例如，如下线性规划，此时（2.2）则称为线性规划的典范形式。12341341231234min3425;..265,438,,,,0,xxxxstxxxxxxxxxx4[1,0]Ta2[0,1]Ta就呈现为典范形式，因为和可合并成单位矩阵。不失一般性，假定单位矩阵位于前m列，即典范形式呈现为112211,111,122,112,2,11,min..0,nnmmnnmmnnmmmmmnnmjcxcxcxstxaxaxbxaxaxbxaxaxbxj1,2,,n（2.3）其中0(1,2,,)ibim。用向量－矩阵表示法，那么（2.3）可简写成min..,0.TTIINNININcxcxstIxNxbxx（2.4）2.一般形式线性规划1111min..,1,2,,,1,,,1,,0,1,2,,.tjjjtpjjpjtqjjqjtrjjrjjcxstaxbpuaxbquuvaxbruvmxjt（2.5）3.一般形式与标准形式的关系（1）松弛变量p考虑“”约束中的第个不等式1,tpjjpjaxb（2.6）引入非负变量tpx，迫使1.tpjjtppjaxxb使不等式约束（2.6）变为等式约束（2.7）的非负变量tpx称为松弛变量。（2）剩余变量q考虑“”约束中的第个不等式1,tqjjqjaxb（2.7）（2.8）引入非负变量tqx，迫使引入非负变量tqx，迫使使不等式约束（2.8）变为等约束（2.9）的非负变量1.tqjjtqqjaxxb（2.9）称为剩余变量。tqxuv在引入个松弛变量、个剩余变量后，线性规划（2.5）可化成标准形式：1111min..,1,2,,,1,,,1,,0,1,2,,.tjjjtpjjtppjtqjjtqqjtrjjrjjcxstaxxbpuaxxbquuvaxbruvmxjtuv（2.10）tuvnm它含有个变量、个等式约束。注意，新引入变量的价格系数全部设为零。因此，在（2.10）的目标函数中没有出现新变量。下面说明线性规划（2.5）与其标准形式（2.10）是等价的。首先，它们的容许点是一一对应的，且对应的容许点的函数值相等。因为若12[,,,]Ttxxx是（2.5）的一个容许点，那么按公式（2.7）和（2.9）引入非负的松弛变量和剩余变量1,,tnxx后，显然121[,,,,,,]Tttnxxxxx将是（2.10）的容许点。反之亦然。故（2.5）的容许点12[,,,]Ttxxx与（2.10）的容许点121[,,,,,,]Tttnxxxxx一一对应。又（2.5）与（2.10）的目标函数相同，且都只是1,,txx的函数，所以（2.5）与（2.10）所对应的容许点的函数值相等。其次，若*****121[,,,,,,]Tttnxxxxx是（2.10）的最优点，它所对应的最优值为**1tjjjzcx，那么，由前面的证明可知，其前t个分量组成的向量***12[,,,]Ttxxx也一定（2.5）的最优点。反之亦然。因此，线性规划（2.5）与其标准形式（2.10）是等价的。该结论表明，可以只讨论标准线性规划。例2.1将线性规划1212121212min34..2413,0.xxstxxxxxxxx化为标准形式，并用图解法求解原问题，给出标准形式的解。3x4x解对第1个约束引入松弛变量，对第2个约束引入。于是，该线性规划的标准形式为剩余变量12123124121234min34..2413,,,0.xxstxxxxxxxxxxxx图解法求解原线性规划如下：*x121xx123xx*1,2Tx*1,2,1,0Tx最优解在直线与的交汇处，即。相应的标准形式的最优解为。（3）自由变量以上讨论都考虑变量的取值是非负的（当变量的取值非正，那么它的负变量的取值即是非负的）。实际中，如果某些变量没有这种约束，也就是说，某些变量可以任意取值，那么这些变量称为自由变量。自由变量可以通过以下两种方法把它消除。例如，假若1x是自由变量。1x1x第一种方法：引入两个非负变量和，令111xxx（2.11）将其代入到线性规划的目标函数和约束函数中，自由变量1x就消除了。注意，求出新线性规划的最优点后，再利用（2.11）便可以定出1x。第二种方法：取一个包含1x的等式约束，例如1122iiinniaxaxaxb由此解出212111iiinniiibaaxxxaaa（2.12）将此式代入到线性规划的目标函数和其他约束函数中，自由变量1x也消除了。求出新线性规划的最优点后，1x。利用（2.12）再定出第一种方法将增加变量的数目，导致问题的维数增大。第二种方法正好相反。2.2基本定理考虑标准线性规划（2.2），即min;..0.TcxstAxbx记容许集{,0}DxAxbx。不妨假定()RAmn，0b。1.极点与基本容许解定义2.2有限个半空间的交称为凸多面体。半空间是凸集，故凸多面体是凸集。边界为直线或平面是多面体的几何特征。多面体凸多面体定义2.3有界的的凸多面体称为凸多胞形。凸多面体凸多胞形定理2.1线性规划（2.2）的容许集D是凸多面体。(2)凸集的极点与凸集相关的另一个重要概念是凸集的极点。Dx定义2.5若凸集中的某个点不能表示为这个集合中另外两个不同点的严格凸组合，即121212(1),,,;0,1xxxxxDxxxD则称为凸集的极点。(3)基本容许解当（2.2）的容许解又是“Axb的基本解”时，就称其为（2.2）的基本容许解。AxbAxb方程组满足“基本”条件的的解称为的基本解。Axb的基本解是如何定义的呢？将Axb表示成向量形式1122nnxaxaxab()RAmAmB因为，故中必含有阶的可逆矩阵，称为基。基B的每个列向量称为基向量，A的其余列向量称为非基向量。与基向量对应的变量称为基变量，与非基向量对应的变量称为非基变量。若基是单位矩阵，则称为标准基。非基变量取值皆为0的Axb解称为基本解。满足0x的基本解称为线性规划（2.2）关于基B的基本容许解。不失一般性，设11,,,,,,,,TTBmNmnABNxxxxxx则Axb11(,)BBNBNNxBNbBxNxbxBbBNxx0Nx1BxBb令。若，得基本解10Bb么该基本解是关于基B的基本容许解。，那例2.3P48定义2.10基变量取值皆不为0的基本解称为非退化的，否则称为退化的；若（2.2）的所有基本容许解都是非退化的，则线性规划（2.2）称为非退化的，否则称为退化的。例2.4P49(3)基本容许解与极点的关系{,0}DxAxbx引理2.2设12mn,,,nAaaa()RAm，，xD。则x是基本容许解x的正分量所对应的A的列向量线性无关。xDxxD定理2.3设,则是（2.2）的基本容许解是的极点。从几何角度讲，例2.3中的约束条件12312312362418,,0xxxxxxxxx表示空间一条直线在第一象限中的直线段部分。如图所示：红线部分为容许集D。D有两个极点(0,3,3)T和(2,0,4),T它们恰恰是两个基本容许解。例2.4如图所示：D有两个极点(0,6,0)T和(4,0,2)T推论2.4容许集D的极点个数有限。2.线性规划基本定理xD1,,,0,,00,1,Tlixxxxil引理2.5设.不妨设且12,,,laaa线性相关。那么一定存在最多有1l个正分量的容许解。定理2.7线性规划（2.2）若有容许解，则必有基本容许解。定理2.8线性规划（2.2）若有最优解，则必有最优基本容许解。从几何上看，解线性规划存在以下几种可能情形：唯一解无穷多解解无界无解2.3单纯形法由前述知，（2.2）的容许集D是凸多面体，D中的极点个数有限。（2.2）若有容许解，则必有基本容许解；若有最优解，则必有最优基本容许解。据此，对于线性规划，我们只关心基本容许解即可。因此，一个显而易见的求解方法是求出全部基本容许解（极点），比较目标函数值就能确定最优解。可是，当,nm数值较大时，这种法的计算量相当大，逆矩阵也不易求。Dantzig给出的单纯形法基本上解决了这个问题。单纯形法的基本思想是：首先找到（求出）一个极点（基本容许解）0x，并依据最优性准则判断其最优性，如非最优，则沿凸多面体D条棱找到（迭代到）的一使目标值降低（不找比0x的）的下一个极点（基本容许解）的目标值高1x数是有限的，所以在一定的条件下，总可以找到（迭代到），……。因为极点个最优极点（最优基本容许解）或者说明解无界。如图所示。Dantzig单纯形法的思想涉及以下三个具体问题：有最优点解无界一、初始基本容许解的产生；二、最优性准则；三、基本容许解的改进。1.最优性准则考虑标准线性规划min..0.TcxstAxbx（2.21）设B为容许基。并不妨设],[NBANBxxxNBccc,,。将（2.21）改写为min..,0.TTBBNNBNBNcxcxstBxNxbxx（2.22）0NxB令，得关于的基本容许解1,0Bbx目标函数值1TBzcBb设TTNTBxxx],[为任一容许解，则由（2.22）解出11BNxBbBNx代入目标函数中得111()().TTBNNNTTBNNzcBbBNxcxzcBNcx令TNTBTNcNBc1，于是TNNzzx（2.26）故TNNzzx.0Nx0N.zz因为，因此，只要，必有由此得到判断基本容许解是最优解的一个充分条件。定义2.11在标准线性规划（2.21）中，设B是一个基，则1,1,2,,TjBjjcBacjnjxB称为变量关于基的判别数。判别数的向量形式为1TBcBAc易知0B。定理2.9（线性规划最优性准则）在标准线性规划（2.21）中，设BBB是容许基。若所有变量关于基的判别数皆非正，则关于基的基本容许解是最优解。定义2.12在标准线性规划（2.21）中，若关于基B基本容许解是最优解，则称B是最优基。例2.5考虑标准线性规划12341341231234min25..214,,,0.xxxxstxxxxxxxxxx试分别求关于基042[,]Baa112[,]Baa和的基本解。若是容许解，则判别其最优性。解关于0B的基变量取值0410210,4BxxBbbx故关于的基本解0B00,4,0,1Tx是基本容许解。计算00102410114033,5,10,15,115,125,1211,1TBucBuacuac最优性准则未满足，因