最优化方法课件_图解法和LP基本定理

1、线线 性性 规规 划划Linear Programming邵红梅邵红梅考虑如下约束数学规划模型考虑如下约束数学规划模型 maxmin. .( )0,1,2,( )0,1,2,nijf xf xxRs t h xilgxjm或其中其中: : 都是都是线性函数线性函数. .( ), ( ),( )ijf x h x g x11max (min)( ). .( ,) ,1,2,njjjnijjijf xc xs ta xbiml 即即: :3. LPLP基本定理基本定理4. 单纯形法单纯形法 1. 图解法图解法5. 大大M法法第二章第二章 线性规划（线性规划（LP）6. LPLP对偶理论（对偶单纯形

2、法）对偶理论（对偶单纯形法）2.LP2.LP标准形标准形3 37. 灵敏度分析及应用灵敏度分析及应用确定可行域：确定可行域： 画约束直线，确定满足约束条件的半平画约束直线，确定满足约束条件的半平面，所有半平面的交集，即为线性规划的面，所有半平面的交集，即为线性规划的可行域。可行域。确定目标函数的等值线及优化方向确定目标函数的等值线及优化方向： 画一条目标函数等值线，并确定目标函数画一条目标函数等值线，并确定目标函数优化的方向。优化的方向。平行移动目标函数等值线，通过观察得平行移动目标函数等值线，通过观察得到线性规划的最优解。到线性规划的最优解。图解图解法的法的步骤步骤4 4 第一节第一节 图解

3、法图解法例例1. 用图解法求解线性规划问题用图解法求解线性规划问题二、例题解析二、例题解析5 5121212min23412. .220,1,2jzxxxxs txxxj x1x2o-3X1 -4X2 =-12() Lo： 0 = 2X1 + X2 D此点是唯一最优解，此点是唯一最优解，且最优目标函数值且最优目标函数值 min Z=-7可行域可行域6 61222( )xx 163,55解：解：121212min23412. .220,1,2jzxxxxs txxxj 例例2. 1212121212max35.71.910.21.93.8. .1.93.81.93.8zxxxxxxs txxxx

4、 x1x2oX1 - 1.9X2 = 3.8 ()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8()X1 + 1.9X2 = 10.2 ()（7.6，2）DL0： 0=3X1+5.7X2 max Z（3.8，4）30.6 = 3X1+5.7X2 蓝色线段上的所有点都是最蓝色线段上的所有点都是最优解。这优解。这种情形为有无穷多最种情形为有无穷多最优解，但是最优目标函数值优解，但是最优目标函数值max Z=30.6是相同的是相同的。可行域可行域8 8例例2. 1212121212max35.71.910.21.93.8. .1.93.81.93.8zxxxxxxs txxx

5、x x1x2O10203040102030405050可行域是空集可行域是空集无无可行解可行解(即无最优解即无最优解)121212122401.530. .500,0 xxxxs txxxx max Z=3x1+4x29 9例例3. 2X1 + X2 = 40()X1 +1.5 X2 = 30()X1 + X2 = 50()线性规划的图解法启示：线性规划的图解法启示：线性规划问题的解有多种情形；线性规划问题的解有多种情形；若线性规划的可行域非空，则一定是凸若线性规划的可行域非空，则一定是凸集（区域内任意两点连线都在其中）；集（区域内任意两点连线都在其中）；线性规划问题若有最优解线性规划问题若有

6、最优解, ,则最优解在可则最优解在可行域的某顶点上达到行域的某顶点上达到. .优缺点优缺点简单、直观、便于初学者理解和记忆；简单、直观、便于初学者理解和记忆；仅适用于低维情况，通常适用于含两个仅适用于低维情况，通常适用于含两个或三个变量的情况。或三个变量的情况。1111对于高维情况对于高维情况, 怎么求解呢怎么求解呢? - 单纯形法单纯形法 第二节第二节 线性规划的标准形线性规划的标准形1212线性规划的形式线性规划的形式是多种多样的是多种多样的: 目标函数求极大目标函数求极大( (极小极小);); 约束可能有等式约束约束可能有等式约束, 也可能有不等式约束也可能有不等式约束; 决策变量有的受

7、非负约束决策变量有的受非负约束,有的是无限制有的是无限制. 为了方便研究为了方便研究, 考虑将各种形式的考虑将各种形式的LPLP化为一种统一化为一种统一的形式的形式, 这种形式即被称为这种形式即被称为LPLP的标准形式的标准形式. .11min. .,1,2,0,1,2,njjjnijjijjzc xs ta xbimxjn 1313一、一、LP标准形标准形三大特点三大特点目标函数：目标函数：min约束条件：约束条件：=变量符号：变量符号：0二、化二、化LPLP为标准型的方法为标准型的方法1414min fz 15)nijjija xb 0.ix 其其中中称称为为弛弛变变量量松松16)nijj

8、ija xb 0.ix 其其称称为为剩剩余余中中变变量量2)(0)jjjxh h4)jx 的的符符号号无无限限制制0,0,jjjjjjyyxyyx 引引入入令令代代入入模模型型消消去去,0;jjjjyxhy引引入入则则10,nijjijiixxa xb 10,inijjiija xbxx 1) max z3)0jx ,0;jjjyxy 令令则则1515例例1121212121max23674. .230zxxxxxxs txxx 2. 举例举例分析分析: :共有共有4 4处不符合处不符合标准形的要求标准形的要求. .1)fz 令令12min fxx 23434),0,0 xxxxx2 2 令令

9、2,x并并将将上上式式代代入入原原模模型型 消消去去),3 3 对对于于不不等等式式约约束束条条件件 分分别别引引入入松松弛弛变变量量和和剩剩余余变变量量将将它它们们化化为为等等式式约约束束. .解解: :161613413413413546min2336774. .230,1,3,4,5,6jxfxxxxxxxxxxs txxxxj 则相应的标准形为则相应的标准形为56, x, x.其其中中为为松松弛弛变变量量为为剩剩余余变变量量1717例例21212121212max54351525. .22110,0zxxxxxxs txxxx 分析分析: :共有共有5 5处不符合处不符合标准形的要求标

10、准形的要求. .1)fz 令令1254min fxx 323),0 xxx 2 2 令令则则2,x并并将将上上式式代代入入原原模模型型 消消去去),3 3 对对于于不不等等式式约约束束条条件件 分分别别引引入入松松弛弛变变量量和和剩剩余余变变量量将将它它们们化化为为等等式式约约束束. .解解: :181851313134136min54351525. .22110,1,3,4,5,6jxxxfxxxxxxs txxxj 则相应的标准形为则相应的标准形为465,.xxx其其中中和和 为为松松弛弛变变量量为为剩剩余余变变量量第三节 LP基本定理 将将LPLP化为标准形后化为标准形后,如何求最优解呢

11、如何求最优解呢? 有一个定理给出了这个问题的答案有一个定理给出了这个问题的答案, 这就是这就是LPLP基本定理基本定理.2020 LP标准形的矩阵形式标准形的矩阵形式min. .0TzC Xs tAXbX 其中其中 121212,(),TTnnTijm nmCcccXxxxAabb bb 11min. .,1,2,0,1,2,njjjnijjijjzc xs ta xbimxjn 2121 考虑具有标准形的考虑具有标准形的LP:LP:一、线性规划的基本概念一、线性规划的基本概念min.0TfC XAXbs tX 约束系数矩阵约束系数矩阵A是是mn 矩阵矩阵, mn，并且，并且 r (A)m.

12、当当 mn 时，基矩阵唯一时，基矩阵唯一; 当当 m n 时，基矩阵就可时，基矩阵就可能有多个，但数目不超过能有多个，但数目不超过 个。个。mnC1. 基矩阵基矩阵: 若若A中的中的mm子矩阵子矩阵B满足满足 r (B)m, 即即则称则称B是是LPLP问题的一个基矩阵（简称为问题的一个基矩阵（简称为基基）。）。 0,B 于是于是A中至少有一个中至少有一个mm子矩阵子矩阵B，使得：使得：r (B)m。约束方程的系数矩阵为约束方程的系数矩阵为：511 1010620 1A 91001B710,21B811,20B610,61B151,10 6B251,10 0B350,10 1B41162B51

13、1,6 0B1234123553.106220 ,1,5jxxxxs txxxxxj 例例1 1 设设123min42fxxx 易看出易看出 r（A）=2，2 阶子矩阵有阶子矩阵有 = 10个，而基矩阵只有个，而基矩阵只有9个，个，25C222210101051,0 ,102BBB不不是是基基。但但对对于于：由由于于故故2. 基向量基向量: 基矩阵对应的列向量称为基向量基矩阵对应的列向量称为基向量，其余列向量称其余列向量称为非基向量为非基向量. 3. 基变量基变量: 基向量对应的变量称为基变量，非基向量对应的变基向量对应的变量称为基变量，非基向量对应的变量称为量称为非基变量非基变量(自由变量自

14、由变量)。例如例如：对于基：对于基B2而言，而言，x1 , x4是基变量，是基变量，x2 , x3 , x5是非基变量。是非基变量。251,10 0B511 1010620 1Ax1 x4思考思考：基变量的选取唯一吗？取法有多少种？：基变量的选取唯一吗？取法有多少种？【注注】基变量、非基变量是针对某一确定基而言的，不同的基基变量、非基变量是针对某一确定基而言的，不同的基对应的基变量和非基变量也不同。对应的基变量和非基变量也不同。 4. 基本解基本解: 对于某一确定的基对于某一确定的基B，令，令所有的自由变量等于零所有的自由变量等于零, 求出求出 Ax=b的解，称这组解为的解，称这组解为LP问题

15、的关于基问题的关于基 的基本解。的基本解。 5. 基可行解基可行解: 非负的基本解称为基可行解（基本可行解）非负的基本解称为基可行解（基本可行解）.【注注】基可行解基可行解也被定义为也被定义为“可行的基本解可行的基本解”。 2424注注: 基变量的选取方式基变量的选取方式 有限有限, 所以基本解的个数也为所以基本解的个数也为有限个有限个.mnC 可见：可见：求基可行解要先求基本解求基可行解要先求基本解, 然后看是否非负即可。然后看是否非负即可。 另外，基本可行解也一定为有限个。另外，基本可行解也一定为有限个。 二、基本解的求法二、基本解的求法例例1 1 求求134123246.350 ,1,4

16、jxxxs txxxxj 1234min324zxxxx的一个基本解和一个基本可行解的一个基本解和一个基本可行解. .解解: : 约束方程的增广矩阵约束方程的增广矩阵20416( , )11305A b x2 x4 注意到注意到A是是24矩阵矩阵, ,r(Ar(A) )2.2.由于第由于第2 2列和第列和第4 4列线性无关列线性无关, ,构成一个构成一个2 2阶单位子块阶单位子块，因此可构成一个基矩阵因此可构成一个基矩阵. .24,xx取取为基变量为基变量, ,13,xx为自由变量为自由变量, ,表示基变量得如下同解方程组表示基变量得如下同解方程组: :21353xxx 4136 24xxx

17、用自由变量用自由变量213413536 24xxxxxx 130:xx令令得得 0, 5, 0, 6Tx 又因该解非负，所以又是一个基本可行解。又因该解非负，所以又是一个基本可行解。思考思考: 若基变量选为其他变量时若基变量选为其他变量时,如何求基本解呢如何求基本解呢?启发启发: 若系数矩阵中含有若系数矩阵中含有m阶单位子块很容易求基本解阶单位子块很容易求基本解.于是，得一个基本解：于是，得一个基本解：245,6xx三、线性规划的基本定理三、线性规划的基本定理考虑标准形式的线性规划问题考虑标准形式的线性规划问题min. .0TzCXs tAXbX ( )r Amn 12,TnnXx xxR 12,Tnnbb bbR 2828定理定理3.1（2）线性规划问题若有最优解，那么一定）线性规划问题若有最优解，那么一定有最优的基本可行解。有最优的基本可行解。（1）线性规划问题若有可行解，那么一定）线性规划问题若有可行解，那么一定 有基本可行解。有基本可行解。定理定理3.2 线性规划问题的