线性规划图解法几何意.ppt

《线性规划图解法几何意.ppt》由会员分享，可在线阅读，更多相关《线性规划图解法几何意.ppt（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于线性规划图解法几何意现在学习的是第1页，共59页 1.3线性规划问题的标准形式1 12211 11221121 1222221 122.0(1,2,.,)nnnnnnmmmnnmjmax zc xc xc xa xa xa xba xa xa xbstaxaxaxbxjn(其中其中bi0(i=1,2,.,m)称下列形式为线性规划问题的标准形式称下列形式为线性规划问题的标准形式:1:M目标函数求极大目标函数求极大,约束条件为等式约束条件为等式,决策变量及右边常数项为非负决策变量及右边常数项为非负现在学习的是第2页，共59页线性规划问题的几种表示形式n,j,xm,i,bxaxczmax:Mjn

2、jijijnjjj21021111约束条件：目标函数：现在学习的是第3页，共59页用向量表示为：n,j;bbbb;aaaP;xxxX;c,c,cCn,j,xbxPCXzmax:Mmmjjjjnnjnjjj 212102121212111约束条件：目标函数：现在学习的是第4页，共59页().0max zCXLPAXbstX则标准形式的矩阵表示：则标准形式的矩阵表示：mnmnaaaaA.11111(.)Tmbbb，1(.)nCcc，1(.)TnXxx，若令若令A称为系数矩阵称为系数矩阵b称为资源向量称为资源向量C称为价值向量称为价值向量X称为决策变量向量称为决策变量向量用矩阵表示为：现在学习的是第

3、5页，共59页非标准形式化为标准形式的方法zz 1.当目标函数为求极小值当目标函数为求极小值,即即 min z=c1x1+c2x2+.+cnxn因为求因为求min z 等价于等价于max(-z)故可令故可令则目标函数化为则目标函数化为:2.当右端项当右端项 bim)其秩为其秩为m,B是矩阵是矩阵A中的一个中的一个mm阶的满秩子矩阵阶的满秩子矩阵,称称B是线性规划问题的一个是线性规划问题的一个基基。现在学习的是第12页，共59页一一.线性规划问题解的概念（线性规划问题解的概念（2）mmmmaaaaB.1111=(P1,P2,.,Pm)B中的每一列向量中的每一列向量Pj(j=1,2,.m)称为基向

4、量称为基向量 基向量：基向量：与基向量与基向量Pj的对应的变量的对应的变量xj 称为基变量称为基变量 基变量：基变量：非基变量：非基变量：线性规划中的其余变量称为非基向量线性规划中的其余变量称为非基向量 5.基解基解 设设X是（是（LP）的约束方程）的约束方程AX=b的一个解，的一个解，B是一个基，是一个基，若若X中对应基中对应基B的非基变量取值全为零的非基变量取值全为零，则称，则称X为为(LP)关关于于基基B的基解的基解，记作，记作X(B)不妨设基为不妨设基为 基解的个数不会超过 个mnC现在学习的是第13页，共59页一一.线性规划问题解的概念（线性规划问题解的概念（3）可证明可证明:一个基

5、唯一地确定一个基解一个基唯一地确定一个基解.6.基可行解：基可行解：若基解若基解X(B)满足非负条件满足非负条件X(B)0，则称，则称基解基解X(B)为基可行解为基可行解 7.基最优解：基最优解：若基可行解若基可行解X(B)是是(LP)的最优解的最优解,则称则称X(B)为为(LP)的的基最优解基最优解.最优基：最优基：基最优解对应的可行基基最优解对应的可行基B称为最优基称为最优基.可行基：可行基：基可行解对应的基基可行解对应的基B称为可行基称为可行基.注注:基解没有基解没有X0的限制的限制,故基解不一定是可行解故基解不一定是可行解.X(B)=NBXX01bB现在学习的是第14页，共59页一一.

6、线性规划问题解的概念（线性规划问题解的概念（4）8.退化解：退化解：若基本可行解若基本可行解X的所有基变量的值均大于的所有基变量的值均大于0，则，则称称X是非退化的是非退化的，否则称，否则称X为退化的为退化的。若若(LP)的所有基本可行解都是非退化的的所有基本可行解都是非退化的,则称则称线性规划问题是非退化的线性规划问题是非退化的.现在学习的是第15页，共59页二二.例题例题考虑线性规划问题考虑线性规划问题：约束方程的系数矩阵约束方程的系数矩阵A123451231425123452300028()416.412,0max ZxxxxxxxxLPxxstxxx x x x x1004001004

7、00121A很显然很显然A中的后中的后3列是线性无关的，它们构成一个基列是线性无关的，它们构成一个基1345(,)BP P PE基基B1对应的对应的变量变量x3,x4,x5是是基变量基变量,x1,x2是是非基变量非基变量现在学习的是第16页，共59页二二.例题（例题（2）若令若令：得得120,xx 0,0,8,16,12TX该解是对应该解是对应B1的基解，它是基可行解，的基解，它是基可行解，B1是可行基；是可行基；如取如取2123121(,)400040BP P P是（是（LP）的一个基，）的一个基，若令若令：450,xx 基基B2对应的对应的变量变量x1,x2,x3是是基变量，基变量，,x4

8、,x5是是非基变量非基变量得得4,3,-2,0,0TX该解是对应该解是对应B2的基解，它不是基可行解，的基解，它不是基可行解，B2不是可行基；不是可行基；现在学习的是第17页，共59页三三.线性规划问题解的关系图线性规划问题解的关系图AX=b的解的解 基解基解若非基变量为若非基变量为0 基可行解基可行解 基最优解基最优解B是是A的的m阶子矩阵阶子矩阵基基B若若|B|0可行基可行基B当当B-1b 0最优基最优基B若基变量取非负若基变量取非负若对应目标函数若对应目标函数 值最优值最优现在学习的是第18页，共59页非可行解非可行解三三.线性规划问题解的关系图（线性规划问题解的关系图（2）可可行行解解

9、基基可可行行解解基基解解基基可可行行基基最最优优基基现在学习的是第19页，共59页第2节 线性规划问题的几何意义现在学习的是第20页，共59页一一.凸集与顶点凸集与顶点凸集凸集:如果集合如果集合K中任意两个点中任意两个点X(1),X(2),其连线上的所有点也其连线上的所有点也都是集合都是集合K中的点中的点,则称集合则称集合K为凸集为凸集.或或K=X|X=X(1)+(1-)X(2),X(1)K,X(2)K,01 定理定理:D xRn|Ax=b,x0是凸集是凸集顶点顶点:凸集凸集K中满足下列条件的中满足下列条件的点点X称为顶点称为顶点:如如果果K中不存在任何两个不同的点中不存在任何两个不同的点X1

10、,X2,使使X成为这两个点连线上的一个点成为这两个点连线上的一个点.定理定理:有限个凸集的交集还是有限个凸集的交集还是凸集凸集凸组合凸组合:设设)()2()1(,.,kXXX是是n维欧氏空间中的维欧氏空间中的k个点个点)()2(2)1(1.kkXXXX10,1ii则称则称X是的凸组合是的凸组合)()2()1(,.,kXXX现在学习的是第21页，共59页凸集的概念：凸集凸集不是凸集顶点不是凸集现在学习的是第22页，共59页二二.几个基本定理几个基本定理定理定理1 若线性规划问题存在可行解若线性规划问题存在可行解,则问题的可行则问题的可行域是凸集域是凸集.定理定理2 若线性规划问题有非零可行解，则

11、其必有基若线性规划问题有非零可行解，则其必有基可行解。可行解。定理定理4 若线性规划问题有最优解，一定存在一个基可行若线性规划问题有最优解，一定存在一个基可行解是最优解。解是最优解。定理定理3线性规划问题的基可行解线性规划问题的基可行解X X对应线性规划问题对应线性规划问题可行域可行域(凸集凸集)的顶点的顶点.引理引理1线性规划的可行解线性规划的可行解X(x1,x2,xn)T为基可行为基可行解的充要条件是解的充要条件是X的正分量所对应的系数列的正分量所对应的系数列向量是线性无关的。向量是线性无关的。现在学习的是第23页，共59页第第3节节 单单 纯纯 形形 法法现在学习的是第24页，共59页一

12、一.单纯形法迭代的基本思想单纯形法迭代的基本思想 开始于某一个可行基及其对应的基可行开始于某一个可行基及其对应的基可行解，从一个基可行解迭代到另一个基可行解解，从一个基可行解迭代到另一个基可行解，并且使目标函数值不断增大，经过有限步，并且使目标函数值不断增大，经过有限步必能求得线性规划问题的最优解或者判定线必能求得线性规划问题的最优解或者判定线性规划问题性规划问题无有界的最优解无有界的最优解（无界解）。（无界解）。现在学习的是第25页，共59页二二.单纯形法引例单纯形法引例考虑线性规划问题考虑线性规划问题：约束方程的系数矩阵约束方程的系数矩阵A123451231425123452300028(

13、)416.412,0max ZxxxxxxxxLPxxstxxx x x x x100400100400121A很显然很显然A中的后中的后3列是线性无关的，它们构成一个基列是线性无关的，它们构成一个基345(,)BP P PE基基B对应的对应的变量变量x3,x4,x5是是基变量，则基变量，则现在学习的是第26页，共59页二二.单纯形法引例（单纯形法引例（2）即即：将它们代入目标函数中得将它们代入目标函数中得251421341241628xxxxxxx12023zxx令令非基变量非基变量x1=x2=0,得目标值得目标值z0 一个基可行解一个基可行解X(0)(0,0,8,16,12)为了使目标函数

14、能更大，为了使目标函数能更大，让让x2变成基变量变成基变量，原基变量原基变量的的x3，x4，x5要有一个变为非基变量要有一个变为非基变量当当x1=0,由最上式得由最上式得041201602825423xxxxx从上式可看出，当从上式可看出，当x2=3仍可保证仍可保证所有变量非负所有变量非负，并使并使目标函数增大目标函数增大现在学习的是第27页，共59页二二.单纯形法引例（单纯形法引例（3）为了得到以为了得到以x3,x4,x2为基变量的为基变量的一个基可行解，则对左边方一个基可行解，则对左边方程中的程中的x2与与x5互换互换 得得251421341241628xxxxxxx341592zxx再令

15、再令非基变量非基变量x1=x5=0,得目标值得目标值z9 一个基可行解一个基可行解X(0)(0,3,2,16,0)为了使目标函数能更大，为了使目标函数能更大，让让x1变成基变量，原基变量变成基变量，原基变量的的x3，x4，x2要有一个变为非基变量要有一个变为非基变量1231541142521643xxxxxxx 目标函数变为目标函数变为现在学习的是第28页，共59页二二.单纯形法引例（单纯形法引例（4）这样如此下去，可得这样如此下去，可得34141.50.125zxxX(2)(2,3,0,8,0)为了使目标函数能更大，为了使目标函数能更大，让让x1变成基变量变成基变量，原基变量原基变量的的x3

16、，x4，x2要有一个变为非基变量要有一个变为非基变量此时目标函数变为此时目标函数变为X(3)(4,2,0,0,4)由于目标函数中的变量系数都小于等于由于目标函数中的变量系数都小于等于0，所以所以X(3)（4,2,0,0,4)为最优解，为最优解，最优值最优值z14下面从几何角度分析一下最优解的寻求过程：现在学习的是第29页，共59页几何意义：顶点转移，目标增大现在学习的是第30页，共59页三三.单纯形法原理单纯形法原理1.确定初始基可行解：确定初始基可行解：对标准型的LP问题1max1.1.0,1,2,1.2njjjjzCXP xbstxjn 在约束条件(1.1)的变量的系数矩阵中总会存在一个单

17、位矩阵。(2)当线性规划的约束条件都为号时，其松弛变量对应的系数列向量构成的矩阵即为单位阵；(3)当线性规划的约束条件为或的情况，引入人工变量后也可实现。(1)系数矩阵中可以直接观察得到一个单位子矩阵；现在学习的是第31页，共59页三三.单纯形法原理（单纯形法原理（2）2.从一个基可行解转换为相邻的基可行解：从一个基可行解转换为相邻的基可行解：定义：两个基可行解称为相邻的，如果他们之间变换且仅变换一个基变量。设初始基可行解为：000012,0,0TmXxxx可知：011.3miiiPxb 其对应的系数矩阵的增广矩阵为：1211,11112,1222,1100010001mmjnmjnmjnm

18、mmjmnmPPPPPPbaaabaaabaaab 现在学习的是第32页，共59页三三.单纯形法原理（单纯形法原理（3）易得：111.41,mmjijijijiiiPa PPa Pjmn(1.3)+(1.4)(0),得011.5miijijixaPPb令：10001122,0TjjmmjXxaxaxa 显然：1AXb为使X(1)成为可行解，令：00min01.6ilijiijljxxaaa可证明:将(1.6)式代回到X(1)中,X(1)为基可行解，此时完成了从一个基可行解到另一个与其相邻的基可行解的转换。现在学习的是第33页，共59页三三.单纯形法原理（单纯形法原理（4）证明：将与变量 x1,

19、xl-1,xl+1,xm,xj对应的列向量，经重新排列后加上b列有如下形式：1211112211,11,1000001000001000000000010000001ljlmjjlljlljlljmPPPPPP bbababababab因为P1,P2,Pl-1，Pj,Pl+1,Pm线性无关，故X(1)为基可行解。现在学习的是第34页，共59页三三.单纯形法原理（单纯形法原理（5）3.最优性检验与解的判别：最优性检验与解的判别：将2中的基可行解X(0)与X(1)分别代入目标函数，得 001miiizc x 称为检验数j 101()miiijjizc xac011mmjiijiiiicc ac x

20、 00jz现在学习的是第35页，共59页三三.单纯形法原理（单纯形法原理（6）(1)当所有的j0时，现行基可行解为最优解；当所有的j0且对应的列向量Pj 0时，该线性规划问题有无界解；(4)对线性规划问题无可行解的判别将在后面讨论。(2)当存在某个j0且对应的列向量Pj 中有正分量时，说明目标函数值还可以增大，需要进行基变换；现在学习的是第36页，共59页第第 4 节节 单单 纯纯 形形 法的计算步骤法的计算步骤现在学习的是第37页，共59页一一.单纯形法的计算步骤单纯形法的计算步骤第一步：第一步：求初始基可行解，列出初始单纯形表求初始基可行解，列出初始单纯形表XB bx1 x2 .xm xm

21、+1 .xj .xnx1x2.xmb1b2.bm 1 0 .0 a1,m+1 .a1j.a1n 0 1 .0 a2,m+1 .a2j.a2n.0 0 .1 am,m+1.amj.amn c c1 c2.cm cm+1 .cj .cn首先写出关于价值系数的表：（非单纯形表）现在学习的是第38页，共59页一一.单纯形法的计算步骤（单纯形法的计算步骤（2）1,11mmii micc a将基变量下方的价值系数通过变换化为零，得初始单纯形表将基变量下方的价值系数通过变换化为零，得初始单纯形表XB bx1 x2.xm xm+1 .xj .xnx1x2.xm b1b2.bm 1 0 .0 a1,m+1 .a

22、1j .a1n 0 1 .0 a2,m+1 .a2j .a2n.0 0 .1 am,m+1 .amj .amn-z 0 0 .0 .1mjiijicc a1mniinicc a1mi iicb现在学习的是第39页，共59页一一.单纯形法的计算步骤（单纯形法的计算步骤（3）第二步：第二步：最优性检验最优性检验(1)当所有的j0时，现行基可行解为最优解；当所有的j0且对应的列向量Pj 0时，该线性规划问题有无界解；(3)当存在某个j0且对应的列向量Pj 中有正分量时，说明目标函数值还可以增大，需要进行基变换。现在学习的是第40页，共59页一一.单纯形法的计算步骤单纯形法的计算步骤(4)第三步：换基

23、迭代第三步：换基迭代 (1)确定进基变量确定进基变量选择检验数最大的非基变量为进基变量选择检验数最大的非基变量为进基变量 k=max j|j0,j=1,2,.,n则则xk为进基变量为进基变量(2)确定出基变量确定出基变量 根据下列原则确定出基变量根据下列原则确定出基变量 则则l所对应的基变量所对应的基变量xl为出基变量为出基变量元素元素alk为为轴心项轴心项(或称为主元素或称为主元素)(3)以以alk为轴心项进行换基迭代为轴心项进行换基迭代 即利用矩阵的初等行变换即利用矩阵的初等行变换 min|0,1,2,.,ilikiklkbbaimaa把元素把元素alk所在的列化为单位向量所在的列化为单位

24、向量.得到新的单纯形表得到新的单纯形表 现在学习的是第41页，共59页一一.单纯形法的计算步骤（单纯形法的计算步骤（5）第四步：第四步：重复第二、三步，一直到计算结束为止。重复第二、三步，一直到计算结束为止。现在学习的是第42页，共59页二单纯形法二单纯形法 例例1(1)例例 用单纯形法解下列线性规划用单纯形法解下列线性规划 12121212max2328()416.412,0zxxxxLPxs txxx解解:将原问题化为标准形为：将原问题化为标准形为：121231425max228416().4120(1,2,3,4,5)jzxxxxxxxLPs txxxj得单纯形初表为得单纯形初表为:现在

25、学习的是第43页，共59页 XB b x1 x2 x3 x4 x5 x3x4x5 8 16 12 1 2 1 0 0 4 0 0 1 0 0 4 0 0 1 z 0 2 3 0 0 0二单纯形法二单纯形法 例例1(2)T(B1)x3 x4x2-z21 0 1 0 -1/2164 0 0 1 0301 001/4-92 000-3/4 T(B2)现在学习的是第44页，共59页 XB b x1 x2 x3 x4 x5 x3x4x2 2 16 3 1 0 1 0 -1/2 4 0 0 1 0 0 1 0 0 1/4-z-9 2 0 0 0 -3/4 T(B2)x1x4x2-z21 0 1 0 -1/

26、280 0 -4 1 2301 0 01/4-1300-201/4 T(B3)二单纯形法二单纯形法 例例1(3)现在学习的是第45页，共59页 XB b x1 x2 x3 x4 x5 x1x4x2 2 8 3 1 0 1 0 -1/2 0 0 -4 1 2 0 1 0 0 1/4-z-13 0 0 -2 0 1/4 T(B3)x1x5x2-z41 0 0 1/4 040 0 -2 1/2 1201 1/2 -1/8 0-1400-3/2-1/8 0 T(B4)二单纯形法二单纯形法 例例1(4)现在学习的是第46页，共59页二单纯形法二单纯形法 例例1(4)在单纯形终表中，x3,x4为非基变量，

27、所有非基变量检验数均小于零，故该线性规划问题有唯一最优解唯一最优解X*=(4,2,0,0,4)T，最优值为 Z*=14。现在学习的是第47页，共59页二单纯形法二单纯形法 例例2(1)例例2:用单纯形法解下列线性规划用单纯形法解下列线性规划 解解:将原问题化为标准形为：将原问题化为标准形为：12121212max24()3.28,0zxxxLPxs txxxx121324125max243().280(1,2,3,4,5)jzxxxxxxLPstxxxxj得单纯形初表为得单纯形初表为:现在学习的是第48页，共59页 XB b x1 x2 x3 x4 x5 x3x4x5 4 3 8 1 0 1

28、0 0 0 1 0 1 0 1 2 0 0 1-z 0 1 2 0 0 0 T(B1)x3x2x5-z41 0 1 0 030 1 0 1 02100-21-6 100-20 T(B2)二单纯形法二单纯形法 例例2(2)现在学习的是第49页，共59页 XB b x1 x2 x3 x4 x5 x3x2x5 4 3 2 1 0 1 0 0 0 1 0 1 0 1 0 0 -2 1-z-6 1 0 0 -2 0 T(B2)x3x2x1-z20 0 1 2 -130 1 0 1 02100-21-80000-1 T(B3)二单纯形法二单纯形法 例例2(3)现在学习的是第50页，共59页二单纯形法二单纯

29、形法 例例2(4)在单纯形终表中，x4,x5为非基变量，非基变量检验数均小于等于零，且4=0,5=-10时，始终选取下标值为最小的变量为进基变量；(2)当计算值出现两个以上相同的最小比值时，始终选取下标值为最小的变量为出基变量。按最小比值来确定出基变量时，有时会出现两个以上相同的最小比值，从而使下一个单纯形表中出现一个或多个基变量等于零的退化解。将使得多个基可行解对应同一顶点，可能出现迭代计算的循环。现在学习的是第54页，共59页注：目标函数求最小的情况(1)化成标准型，目标函数求极大；(2)有些书中规定目标函数的极小化作为线性规划的标准形式，这时只需以所有检验数j0作为判别表中解是否是最优的

30、标志。(1)当所有的j0时，现行基可行解为最优解；当所有的j0时，该线性规划问题有唯一最优解；当所有的j 0，且对某个非基变量xk，有k=0,该线性规划问题有无穷多最优解。(2)当存在某个j0且对应的列向量Pj 0时，该线性规划问题有无界解；现在学习的是第55页，共59页确定进基变量确定进基变量选择检验数最小的非基变量为进基变量选择检验数最小的非基变量为进基变量 k=min j|j0,j=1,2,.,n则则xk为进基变量为进基变量 确定出基变量确定出基变量 根据下列原则确定出基变量根据下列原则确定出基变量 则则l所对应的基变量所对应的基变量xl为出基变量为出基变量元素元素alk为为轴心项轴心项

31、(或称为主元素或称为主元素)以以alk为轴心项进行换基迭代为轴心项进行换基迭代;min|0,1,2,.,ilikiklkbbaimaa(3)当存在某个j0且对应的列向量Pj 中有正分量时，说明目标函数值还可以减小，需要进行基变换。现在学习的是第56页，共59页思考题思考题(1)下表是某求极大化线性规划问题计算得到的单纯形表，表中无下表是某求极大化线性规划问题计算得到的单纯形表，表中无人工变量，人工变量，a1,a2,a3,d,c1,c2为待定常数。试说明这些常数分为待定常数。试说明这些常数分别取何值时，以下结论成立。别取何值时，以下结论成立。XBbx1x2x3x4x5x6x3d4a110a20

32、x42-1-301-10 x63a3-500-41-zc1c200-30现在学习的是第57页，共59页思考题思考题(2)(1)表中解为唯一最优解；表中解为唯一最优解；(2)表中解为最优解，但存在无穷多最优解；表中解为最优解，但存在无穷多最优解；(3)该线性规划问题具有无界解；该线性规划问题具有无界解；(4)表中解非最优，为对解改进，进基变量为表中解非最优，为对解改进，进基变量为x1，出基变量为，出基变量为x6。解：解：(1)d0，c10，c20 且且 a10；(4)d0，c10 且且 c1c2，a30,334da现在学习的是第58页，共59页感谢大家观看感谢大家观看现在学习的是第59页，共59页