最优化方法课件Lecture2 LP基本性质

最优化方法Optimization第二章线性规划的基本性质主要内容•线性规划的标准形•线性规划的图解法•线性规划的基本性质LP的标准形1、极小化型2、约束方程为等式3、所有的决策变量为非负值4、约束方程的右端项系数为非负值11min.1,,01,,njjjnijjijjzcxstaxbimxjnmin,0,where,,,.Tnmmnzcxs.t.AxbxcxRbRAR矩阵形式(LP)非标准形LP模型转化为标准形LP模型maxminTTcxcx,,0.xxxxx•目标函数是极大化的转化•决策变量无约束转化为非负约束•不等式约束转化为等式约束(松弛变量)b,0b,0TTTTaxaxsbsaxaxsbs•决策变量有上下界的转换333314'10,'3.xxxx12312123312max32s.t75160,xxxxxxxxxxx例：free1223122412235361223456min32()(1)s.t()7()45,,,,,,0xxxxxxxxxxxxxxxxxxxxxxmax||||..23xystxyx1212123434340,0,,||0,0,,||xxxxxxxxxxyxxyxx则1324||||22||||22xxyyxxxxyyxx令123412345126min..230,1,2,,6ixxxxstxxxxxxxxxi•含有绝对值两变量线性规划问题的图解法1.线性不等式的几何意义—半平面1)作出LP问题的可行域2)作出目标函数的等值线3)移动等值线到可行域边界得到最优点2.图解法步骤例1187654322x1876543O109x2ABCEDFGH123f(x)=0f(x)=120,78102..46max212212121xxxxxxxtsxxZ1187654322x1876543O109x2ABCEDFGH1233662:21Zxx最优解结论：若LP问题存在最优解，则必在可行域的某个极点上找到。一般的，当等值线沿目标函数法向量(梯度)方向平行移动时，目标函数值逐步增加；当等值线沿目标函数法向量反方向平行移动时，目标函数值逐步减少。1212112212min1015s.t2330021.5180,0zxxxxlxxlxxLPz结论：以为参数的直线族与可行域某一条边平行，最终重合，则该存在多个解。x1x25010015015010050l2OABCz=500z=1000z=1260(30,80)几种特殊情况•LP存在多个最优解l1•LP问题无可行解1212112212min1012.5690023300,0zxxstxxlxxlxx例：LPLP结论：若的可行域为空集，则该问题无可行解。5015010015050x2O100l1x1l2•LP问题存在无界解121112212min34s.t31,0zxxxlxxlxx例：判断：若LP的可行域无界，则该LP可能存在无界解。Ox1x22314123l1l2ABzC图解法的作用•能解决少量问题LP问题有可行解有最优解唯一解无穷多解无最优解（可行域为无界）无可行解（无解）规律1：•揭示了线性规划问题的若干规律Ex将下列线性规划变成标准形式121212min3..9,15,06.xxstxxxxLP问题的基本性质可行解：满足LP模型的约束条件且满足非负条件的解。例：12121212max32.3624,0511321TTTzxxstxxxxxxXXX判断（），（），（）是否为可行解？定理1:线性规划(LP)的可行域是凸集。最优极点1212111min..0|,0.,,,,,,.1,0,1,,0,1,,.klkljjjjjjkjjjjcxstAxbxSxAxbxxxxdddxSxxdjkjl考虑标准形式：设可行域极点：极方向：由表示定理，对任意代入标准形111min..1,0,1,,0,1,,.kljjjjjjkjjjjcxcdfxstjkjl1111,0,2,0,0,1,,min..1,0,1,,min,1,0jjjkjjjkjjjpjjkpjpjcdfxjcdjlcxstjkcxcxjpfxcx若存在使得，则即该问题无界.对任意令得令则当时，最小。11111,kljjjjjjkkjpjjjjkppjjpxScxcxcdcxcxcxcxx对任意由于所以，极点是原问题的最优解。定理2．设线性规划(L)的可行域非空，则（1）(L)存在有限最优解的充要条件是对任意的j,cd(j)≥0,其中d(j)为可行域的极方向。（2）若(L)存在有限最优解，则目标函数的最优值可在某个极点达到。基和基本解（1）系数矩阵A中任意m列所组成的m阶可逆子方阵B，称为(LP)的一个基(矩阵)，变量xj，若它所对应的列Pj包含在基B中，则称xj为基变量，否则称为非基变量。基变量的全体称为一组基变量，记111min00,nmnmnzcxcs.t.AxbAnmbxxrAmA设按列分块12,,,nPPP1122nnAxbPxPxPxb等价于12,,,.mBBBxxx!!()!mnnCmnm基矩阵的个数最多为1112,,.00BNBNBNNxABNrBmxxAxbBxNxbxBbBNxBbxx设其中设由得，令，得称x为(LP)的基本解。12111300,,,40mBBBBbBbxLPBxxxBb若，则称为的，称为可行基矩阵，为一组可行基。若，则称基本可行解是非退化的，否则称为退化的。基本可行解基矩阵为：121212312436243613-101-20124xxxxxxxAxxx例：引入松弛变量化为系数矩阵1131-2B21-110B4563-13010-20-2101BBB31011B1231243624xxxxxx求基解1111111323111-21152423615114255242,,0,0.55TBBBbx基本解为(3)(600-2)Tx(4)(5)(6)(0-2-120)(0208)(00-64)TTTxxx11121361361-241-24BBXbxx增广矩阵或1360-5-2初等变换13601251024501251224255xx(1)2420055Tx(2)(40-20)Tx只有x(1)和x(5)为基本可行解。线性规划问题解的关系约束方程的解空间基解可行解非可行解基本可行解可行解、基解和基本可行解举例0,78102..46max212212121xxxxxxxtsxxZ211001101001001A121231242512345max642108..7,,,,0Zxxxxxxxxstxxxxxxx可行解、基本解和基本可行解举例1187654322x1876543O109x2ABCEDFGH123f(x)=36K非基变量基变量图中的点解x1,x2x3=10x4=8x5=7O基本可行解x1,x3x2=10x4=-2x5=-3F基本解x1,x4x2=8x3=2x5=-1E基本解x1,x5x2=7x3=3x4=1A基本可行解x2,x3x1=5x4=3x5=7D基本可行解x2,x4x1=8x3=-6x5=7H基本解x3,x4x1=2x2=6x5=1C基本可行解最优解x3,x5x1=1.5x2=7x4=-0.5G基本解x4,x5x1=1x2=7x3=1B基本可行解x1=2,x2=2,x3=4,x4=4,x5=3K可行解基本可行解与极点之间的关系1212121212112121212,,,,0,,0,0,1,,.,,,,.,,,,.,,,,,,,,,,,,TkjkkkkkmkmmxkxxxxxjkPPPkmPxPxPxbkmBPPPkmmkPPPPPPBPPPBPxPx证明：不妨设的前个分量为正分量设线性无关则若则就是基若则可从其余列向量中再挑出个列向量使线性无关。令则是基，且.mnmnPxPxbxB所以，是相应于的基本可行解。xxA可行解是基本可行解的非引理零分量所对应的的列向量线：性无关。111212112212,,,,,0,1,,,0,1,,.,,,,.0,,,,01,2,,1,2,,01,,01TkknjjjjkkkkjjjjjjxxxxxSxjkxjknxPPPPyyyyPyPyPxyjkxyjkxxjknjk证明：设是的极点，其中设对应的列向量为则线性无关否则，存在不全为的数使得令“”（必要性）121212,,0,1,2,,,00.,.jkknxjkxxxSAxbxPxPxPb因为所以，当充分小时，有，由于，因此即定理设是LP的可行域，，则是的极点是LP的基本可行解SxSxSx11121112121122212121212,,,,,,,,,0,,011,22,,,TkkknkkkkkkAxPPPPPxyxyxPxPxPyPyPyPbAxbxxSxxxxxxPPPx则同理可证所以，，且，但与是极点矛盾，所以线性无关。由引理，是基本可行解11212,00.0,0,11.BNxAxbxxBbxxxxSxxx已知是的基本可行解“”(充分性，即假设存在及使得)1212121212112121212121212112,,1101,,,0,10,0,,,01BBNNBBBBNNNNNNNNBNNxxxxxxxxxxBbxxxxxxSxxxxxxSAxbAxbxBxxNx设则有又因为所以。即122121112,NBNBBbBxNxbxBbxBbxxxx且因此有所以即是极点。基可行解的存在性定理1．如果LP有可行解,则一定存在基本可行解.121121211122,,,,,,,0,,00,1,,.,,,,,,0,,0.1,2,min|001,,Tnsjsssss