线性规划问题的基本理论.ppt

《线性规划问题的基本理论.ppt》由会员分享，可在线阅读，更多相关《线性规划问题的基本理论.ppt（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 第二章第二章 第第2 2节节线性规划问题的基本理论线性规划问题的基本理论一、线性规划问题的标准化一、线性规划问题的标准化二、线性规划问题的解二、线性规划问题的解三、线性规划问题的几何意义三、线性规划问题的几何意义一、线性规划问题的标准化一般形式一般形式目标函数：目标函数：Max Max（MinMin）z=cz=c1 1 x x1 1+c+c2 2 x x2 2+c+cn n x xn n 约束条件：约束条件：a a1111 x x1 1+a a1212 x x2 2+a a1n1n x xn n （=,=,）b b1 1a a2121 x x1 1+a a2222 x x2 2+a a2n2

2、n x xn n （=,=,）b b2 2 a am1m1 x x1 1+a am2m2 x x2 2+a amnmn x xn n （=,=,）b bmm 决策变量：决策变量：x x1 1，x x2 2，x xn n ()0 ()0 标准形式标准形式目标函数：目标函数：Max z=cMax z=c1 1 x x1 1+c+c2 2 x x2 2+c+cn n x xn n 约束条件：约束条件：a a1111 x x1 1+a a1212 x x2 2+a a1n1n x xn n =b=b1 1a a2121 x x1 1+a a2222 x x2 2+a a2n2n x xn n =b=b

3、2 2 a am1m1 x x1 1+a am2m2 x x2 2+a amnmn x xn n =b=bmm 决策变量：决策变量：bi 0bi 0 x x1 1，x x2 2，x xn n 0 0一般型和标准型的区别一般型和标准型的区别可以看出，线性规划的标准形式有如下四个特点：目标最大化；约束为等式；决策变量均非负；右端项非负。对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:1 1、极小化目标函数的问题：、极小化目标函数的问题：设目标函数为设目标函数为 Min Min f f=c c1 1x x1 1 +c c2 2x x2 2 +c cn nx xn n (

4、可可以以)令令 z z -f-f ，则则该该极极小小化化问问题题与与下下面面的的极极大大化问题有相同的最优解，化问题有相同的最优解，即即 Max Max z z=-c-c1 1x x1 1 -c-c2 2x x2 2-c-cn nx xn n 但必须注意，尽管以上两个问题的最优解相同，但必须注意，尽管以上两个问题的最优解相同，但它们最优解的目标函数值却相差一个符号，即但它们最优解的目标函数值却相差一个符号，即 Min Min f f -Max-Max z z2 2、约束条件不是等式的问题、约束条件不是等式的问题：设约束条件为设约束条件为 a ai1 i1 x x1 1+a ai2 i2 x x

5、2 2+a ain in x xn n b bi i 可以引进一个新的变量可以引进一个新的变量s s ，使它等于约束右边与，使它等于约束右边与左边之差（一般称左边之差（一般称S S为为松弛变量松弛变量）s s=b bi i(a ai1 i1 x x1 1 +a ai2 i2 x x2 2 +a ain in x xn n )显然，显然，s s 也具有非负约束，即也具有非负约束，即s s00，这时新的约束条件成为这时新的约束条件成为 a ai1 i1 x x1 1+a ai2 i2 x x2 2+a ain in x xn n+s s=b bi i当约束条件为当约束条件为 a ai1 i1 x

6、x1 1+a ai2 i2 x x2 2+a ain in x xn n b bi i 时，时，类似地令类似地令 s s=(=(a ai1 i1 x x1 1+a ai2 i2 x x2 2+a ain in x xn n)-)-b bi i 显然，显然，s s 也具有非负约束，即也具有非负约束，即s s00，这时新的约，这时新的约束条件成为束条件成为 a ai1 i1 x x1 1+a ai2 i2 x x2 2+a ain in x xn n-s s=b bi i称称S S为剩余变量。为剩余变量。不等式情况下：不等式情况下：当当，引入松弛变量，引入松弛变量s s当当，引入剩余变量，引入剩余

7、变量s s松弛变量：需要补充的资源松弛变量：需要补充的资源剩余变量：没有使用的资源剩余变量：没有使用的资源如果原问题中有若干个非等式如果原问题中有若干个非等式约束，则将其约束，则将其转化为标准形式时，必须对各个约束引进不转化为标准形式时，必须对各个约束引进不同的松弛变量。同的松弛变量。3 3、右端项有负值的问题：、右端项有负值的问题：在标准形式中，要求右端项必须每一个在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如分量非负。当某一个右端项系数为负时，如 b bi i00，则把该等式约束两端同时乘以，则把该等式约束两端同时乘以-1-1，得，得到：到：-a ai1i1 x

8、x1 1-a ai2i2 x x2 2-a ain in x xn n=-=-b bi i。4 4、决策变量不定：、决策变量不定：当当X Xi i0oo当某一个变量当某一个变量x xj j没有非负约束时，可以令没有非负约束时，可以令 x xj j=x xj j-x xj j”其中其中 x xj j00，x xj j”00 即用两个非负变量之差来表示一个无符号限即用两个非负变量之差来表示一个无符号限制的变量，当然制的变量，当然x xj j的符号取决于的符号取决于x xj j和和x xj j”的的大小。大小。例：将以下线性规划问题转化为标准形式例：将以下线性规划问题转化为标准形式 Min Min

9、f f =2 =2 x x1 1-3-3x x2 2+4 +4 x x3 3 s.t.3 s.t.3 x x1 1 +4+4x x2 2-5 -5 x x3 3 6 6 2 2 x x1 1 +x x3 3 8 8 x x1 1 +x x2 2 +x x3 3 =-9 =-9 x x1 1,x x2 2,x x3 3 0 0 解：首先解：首先,将目标函数转换成极大化：将目标函数转换成极大化：令令 z z=-=-f f=-2=-2x x1 1+3+3x x2 2-4-4x x3 3 其次考虑约束，有其次考虑约束，有2 2个不等式约束，引进松个不等式约束，引进松弛变量弛变量x x4 4，和剩余变量

10、，和剩余变量x x5 5 00。第三个约束条件的右端值为负，在等式两第三个约束条件的右端值为负，在等式两边同时乘边同时乘-1-1。通过以上变换，可以得到以下标准形式的线通过以上变换，可以得到以下标准形式的线性规划问题：性规划问题：Max Max z z=-2=-2x x1 1 +3+3 x x2 2-4-4x x3 3 s.t.3 s.t.3x x1 1+4+4x x2 2-5-5x x3 3+x x4 4 =6=6 2 2x x1 1 +x x3 3 -x x5 5=8=8 -x x1 1 -x x2 2 -x x3 3 =9=9 x x1 1,x,x2 2,x,x3 3,x,x4 4,x,

11、x5 5 0 0练习：练习：P24 P24 习题习题3 3（1 1）和）和 （2 2）作业：作业：P24 P24 习题习题3 3 （3 3）二、线性规划问题的解二、线性规划问题的解1 1、解的情况、解的情况2 2、几个重要的解概念、几个重要的解概念1 1、解的情况、解的情况 （1 1）存在有限最优解：）存在有限最优解：a a）唯一最优解唯一最优解 b b）无穷多个最优解）无穷多个最优解 （2 2）不存在最优解）不存在最优解 a a）无有限最优解（无界解）无有限最优解（无界解）b b）无可行解（可行域空）无可行解（可行域空）判断题：判断题：线性规划问题无有限最优解的充要条件是可线性规划问题无有限

12、最优解的充要条件是可行域为空？行域为空？2、几个重要的解概念、几个重要的解概念（1 1）可行解、可行域、最优解、最优值）可行解、可行域、最优解、最优值（2 2）基、基本解）基、基本解（3 3）基本可行解（基可行解）基本可行解（基可行解）（4 4）可行基）可行基（1 1）可行解、可行域、最优解、最优值）可行解、可行域、最优解、最优值满足约束条件满足约束条件(1-2)(1-2)、(1-3)(1-3)式的解式的解X X=(=(x x1 1,x x2 2，x xn n)T T，称，称为线性规划问题的为线性规划问题的可行解可行解，其中使目标函数达到最大值的，其中使目标函数达到最大值的可行解称为可行解称为

13、最优解最优解。由可行解组成的集合就是由可行解组成的集合就是可行域可行域（满足约束条件不等式所（满足约束条件不等式所有点组成的集合），将最优解代目标函数得到的函数值就有点组成的集合），将最优解代目标函数得到的函数值就是是最优值最优值。例：例：Max Max z z=1500=1500 x x1 1 +2500+2500 x x2 2 s.t.3 s.t.3x x1 1+2+2x x2 2 65 65 2 2x x1 1+x x2 2 40 40 3 3x x2 2 75 75 x1 ,x2 x1 ,x2 0 0（2 2）基、基本解）基、基本解设设B B为为A A中的一个基，令中的一个基，令Ax=

14、bAx=b，中所有的非基变量（，中所有的非基变量（n-mn-m个）为个）为0 0，得出的解，得出的解x x，称为是，称为是B B的基本解。的基本解。x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 b bi i3 2 1 0 0 653 2 1 0 0 652 1 0 1 0 402 1 0 1 0 400 3 0 0 1 750 3 0 0 1 75P P1 1 P P2 2 P P3 3 P P4 4 P P5 5A=A=（P P1 1，P P2 2，P P3 3，P P4 4，P P5 5）B=B=（P P1 1，P P2 2，P P3 3），基变量（），基变量（x

15、x3 3 x x4 4 x x5 5 ）非基变量（非基变量（x x1 1 x x2 2 ），），B B的基本解是（的基本解是（0 0，0 0，6565，4040，7070）（3 3）基本可行解）基本可行解（1 1）满足非负的基本解，为基本可行解。）满足非负的基本解，为基本可行解。（2 2）可行解满足的条件是：）可行解满足的条件是：Ax=bAx=b和和x 0 x 0，而基本解必然满足而基本解必然满足Ax=bAx=b，只需满足，只需满足X 0X 0。（4 4）可行基）可行基对应于基可行解的基，称为可行基。对应于基可行解的基，称为可行基。基本解数目最多是基本解数目最多是 C Cn nmm个，一般基可

16、行解的个，一般基可行解的数目要小于基本解的数目。数目要小于基本解的数目。当基本解中的非零分量的个数小于当基本解中的非零分量的个数小于mm时，时，该基本解是该基本解是退化解退化解。练习：练习：P96 P96 例题例题1 1作业：作业：P96 P96 例题例题2 2（1 1）找出所有基本解，并指出哪些是基本可）找出所有基本解，并指出哪些是基本可行解？行解？1 1、基本概念、基本概念2 2、基本定理、基本定理3 3、几何意义、几何意义三、线性规划问题的几何意义三、线性规划问题的几何意义三、线性规划问题的几何意义三、线性规划问题的几何意义1 1、基本概念：、基本概念：（1 1）凸集）凸集（2 2）顶点

17、）顶点（1）凸集定义：设K是n维欧氏空间的一点集，若任意两点X(1)K，X(2)K的连线上的所有点X(1)+(1)X(2)K，(01)，则称K为凸集。（任何两个凸集的交集是凸集）（2 2）顶点）顶点设设K K是凸集，是凸集，X XK K；若；若X X不能用不能用不同的两点不同的两点X X(1)(1)K K和和X X(2)(2)K K的线性组合表示为的线性组合表示为 X X=XX(1)(1)+(1+(1)X X(2)(2)，(0(0 1)1)，则称，则称X X为为K K的一个顶点的一个顶点(或极点或极点)。2 2、基本定理、基本定理定理定理1 1：若线性规划问题有可行域，则可行若线性规划问题有可

18、行域，则可行域必为凸集。域必为凸集。定理定理2 2：线性规划问题的线性规划问题的基可行解基可行解X X对应于对应于可行域可行域DD的顶点。的顶点。定理定理 3 3：若可行域有界，则最优解一定在若可行域有界，则最优解一定在顶点上达到。顶点上达到。定理的意义：定理的意义：定理定理1 1：可行域是凸集。：可行域是凸集。定理定理2 2：基本可行解对应顶点。：基本可行解对应顶点。定理定理3 3：最优解在顶点上找。：最优解在顶点上找。几何意义的作用几何意义的作用线性规划问题的所有可行解构成的集合是凸集，线性规划问题的所有可行解构成的集合是凸集，也可能为无界域，它们有有限个顶点，线性规划也可能为无界域，它们

19、有有限个顶点，线性规划问题的每个基可行解对应可行域的一个顶点。问题的每个基可行解对应可行域的一个顶点。若线性规划问题有最优解，必在某顶点上得到。若线性规划问题有最优解，必在某顶点上得到。虽然顶点数目是有限的，若采用虽然顶点数目是有限的，若采用“枚举法枚举法”找所找所有基可行解，然后一一比较，最终必然能找到最有基可行解，然后一一比较，最终必然能找到最优解。但当优解。但当n n,mm较大时，这种办法是行不通的，较大时，这种办法是行不通的，所以要继续讨论如何有效寻找最优解的方法。本所以要继续讨论如何有效寻找最优解的方法。本课程将主要介绍课程将主要介绍单纯形法单纯形法。单纯性法实质：从一个顶点向一个顶点迭代，保单纯性法实质：从一个顶点向一个顶点迭代，保持最优性，一直到达到最优解。持最优性，一直到达到最优解。