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

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

1、第1章 线性规划及其扩展第第1节节 线性规划问题及其数学模型线性规划问题及其数学模型第第2节节 线性规划问题的几何意义线性规划问题的几何意义第第3节节 单纯形法单纯形法第第4节节 单纯形法的计算步骤单纯形法的计算步骤第第5节节 单纯形法的进一步讨论单纯形法的进一步讨论第第6节节 应用举例应用举例 1.3线性规划问题的标准形式(其其中中bi0(i=1,2,.,m)称称下下列列形形式式为为线线性性规规划划问问题题的的标标准准形形式式:目标函数求极大目标函数求极大,约束条件为等式约束条件为等式,决策变量及右边常数项为非负决策变量及右边常数项为非负线性规划问题的几种表示形式用向量表示为：则标准形式的矩

2、阵表示：则标准形式的矩阵表示：若令若令A称为系数矩阵称为系数矩阵b称为资源向量称为资源向量C称为价值向量称为价值向量X称为决策变量向量称为决策变量向量用矩阵表示为：非标准形式化为标准形式的方法1.当目标函数为求极小值当目标函数为求极小值,即即 min z=c1x1+c2x2+.+cnxn因为求因为求min z 等价于等价于max(-z)故可令故可令则目标函数化为则目标函数化为:2.当右端项当右端项 bim)其其秩秩为为m,B是是矩矩阵阵A中中的的一一个个mm阶阶的的满满秩秩子子矩矩阵阵,称称B是是线线性性规规划划问问题题的一个基的一个基。一一.线性规划问题解的概念（线性规划问题解的概念（2）=

3、(P1,P2,.,Pm)B中的每一列向量中的每一列向量Pj(j=1,2,.m)称为基向量称为基向量 基向量：基向量：与基向量与基向量Pj的对应的变量的对应的变量xj 称为基变量称为基变量 基变量：基变量：非基变量：非基变量：线性规划中的其余变量称为非基向量线性规划中的其余变量称为非基向量 5.基解基解 设设X是是（LP）的的约约束束方方程程AX=b的的一一个个解解，B是是一一个个基基，若若X中中对对应应基基B的的非非基基变变量量取取值值全全为为零零，则则称称X为为(LP)关于关于基基B的基解的基解，记作，记作X(B)不妨设基为不妨设基为 基解的个数不会超过 个一一.线性规划问题解的概念（线性规

4、划问题解的概念（3）可证明可证明:一个基可以而且唯一地确定一个基解一个基可以而且唯一地确定一个基解.6.基可行解：基可行解：若若基基解解X(B)满满足足非非负负条条件件X(B)0，则则称基解称基解X(B)为基可行解为基可行解 7.基最优解：基最优解：若若基基可可行行解解X(B)是是(LP)的的最最优优解解,则则称称X(B)为为(LP)的的基最优解基最优解.最优基：最优基：基最优解对应的可行基基最优解对应的可行基B称为最优基称为最优基.可行基：可行基：基可行解对应的基基可行解对应的基B称为可行基称为可行基.注注:基解没有基解没有X0的限制的限制,故基解不一定是可行解故基解不一定是可行解.X(B)

5、=一一.线性规划问题解的概念（线性规划问题解的概念（4）8.退化解：退化解：若若基基本本可可行行解解X的的所所有有基基变变量量的的值值均均大大于于0，则称，则称X是非退化的是非退化的，否则称，否则称X为退化的为退化的。若若(LP)的的所所有有基基本本可可行行解解都都是是非非退退化化的的,则称则称线性规划问题是非退化的线性规划问题是非退化的.二二.例题例题考虑线性规划问题考虑线性规划问题：约束方程的系数矩阵约束方程的系数矩阵A很显然很显然A中的后中的后3列是线性无关的，它们构成一个基列是线性无关的，它们构成一个基基基B1对应的对应的变量变量x3,x4,x5是是基变量基变量,x1,x2是是非基变量

6、非基变量二二.例题（例题（2）若令若令：得得该解是对应该解是对应B1的基解，它是基可行解，的基解，它是基可行解，B1是可行基；是可行基；如取如取是（是（LP）的一个基，）的一个基，若令若令：基基B2对应的对应的变量变量x1,x2,x3是是基变量，基变量，,x4,x5是是非基变量非基变量得得该该解解是是对对应应B2的的基基解解，它它不不是是基基可可行行解解，B2不不是是可可行行基；基；三三.线性规划问题解的关系图线性规划问题解的关系图AX=b的解的解 基解基解若非基变量为若非基变量为0 基可行解基可行解 基最优解基最优解B是是A的的m阶子矩阵阶子矩阵基基B若若|B|0可行基可行基B当当B-1b

7、0最优基最优基B若基变量取非负若基变量取非负若对应目标函数若对应目标函数 值最优值最优非可行解非可行解三三.线性规划问题解的关系图（线性规划问题解的关系图（2）可可行行解解基基可可行行解解基基解解基基可可行行基基最最优优基基第2节 线性规划问题的几何意义2.1 基本概念2.2 几个定理一一.凸集与顶点凸集与顶点凸集凸集:如如果果集集合合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是凸集

8、是凸集顶点顶点:凸集凸集K中满足下列条件的中满足下列条件的点点X称为顶点称为顶点:如如果果K中不存在任何两个不同的点中不存在任何两个不同的点X1,X2,使使X成为这两个点连线上的一个点成为这两个点连线上的一个点.定理定理:有限个凸集的交集还是有限个凸集的交集还是凸集凸集凸组合凸组合:设设是是n维欧氏空间中的维欧氏空间中的k个点个点则称则称X是的凸组合是的凸组合凸集的概念：凸集凸集不是凸集顶点不是凸集二二.几个基本定理几个基本定理定理定理1 若若线线性性规规划划问问题题存存在在可可行行解解,则则问问题题的的可可行域是凸集行域是凸集.定理定理2 若若线线性性规规划划问问题题有有非非零零可可行行解解

9、，则则其其必必有有基可行解。基可行解。定理定理4 若若线线性性规规划划问问题题有有最最优优解解，一一定定存存在在一一个个基可行解是最优解。基可行解是最优解。定理定理3线线性性规规划划问问题题的的基基可可行行解解X X对对应应线线性性规规划划问题可行域问题可行域(凸集凸集)的顶点的顶点.引理引理1 线线性性规规划划的的可可行行解解X(x1,x2,xn)T为为基基可可行行解解的的充充要要条条件件是是X的的正正分分量量所所对对应应的的系系数列向量是线性无关的。数列向量是线性无关的。第第3节节 单单 纯纯 形形 法法一一.单纯形法迭代的基本思想单纯形法迭代的基本思想 开开始始于于某某一一个个可可行行基

10、基及及其其对对应应的的基基可可行行解解，从从一一个个基基可可行行解解迭迭代代到到另另一一个个基基可可行行解解，并并且且使使目目标标函函数数值值不不断断增增大大，经经过过有有限限步步必必能能求求得得线线性性规规划划问问题题的的最最优优解解或或者者判判定定线线性性规规划划问问题题无无有有界界的的最最优优解解（无无界解）。界解）。二二.单纯形法引例单纯形法引例考虑线性规划问题考虑线性规划问题：约束方程的系数矩阵约束方程的系数矩阵A很显然很显然A中的后中的后3列是线性无关的，它们构成一个基列是线性无关的，它们构成一个基基基B对应的对应的变量变量x3,x4,x5是是基变量，则基变量，则二二.单纯形法引例

11、（单纯形法引例（2）即即：将它们代入目标函数中得将它们代入目标函数中得令令非基变量非基变量x1=x2=0,得目标值得目标值z0 一个基可行解一个基可行解X(0)(0,0,8,16,12)为了使目标函数能更大，为了使目标函数能更大，让让x2变成基变量变成基变量，原基变量原基变量的的x3，x4，x5要有一个变为非基变量要有一个变为非基变量当当x1=0,由最上式得由最上式得从上式可看出，当从上式可看出，当x2=3仍可保证仍可保证所有变量非负所有变量非负，并使并使目标函数增大目标函数增大二二.单纯形法引例（单纯形法引例（3）为为了了得得到到以以x3,x4,x2为为基基变变量量的的一一个个基基可可行行解

12、解，则则对对左左边边方程中的方程中的x2与与x5互换互换 得得再令再令非基变量非基变量x1=x5=0,得目标值得目标值z9 一个基可行解一个基可行解X(0)(0,3,2,16,0)为了使目标函数能更大，为了使目标函数能更大，让让x1变成基变量，原基变量变成基变量，原基变量的的x3，x4，x2要有一个变为非基变量要有一个变为非基变量目标函数变为目标函数变为二二.单纯形法引例（单纯形法引例（4）这样如此下去，可得这样如此下去，可得X(2)(2,3,0,8,0)为了使目标函数能更大，为了使目标函数能更大，让让x1变成基变量变成基变量，原基变量原基变量的的x3，x4，x2要有一个变为非基变量要有一个变

13、为非基变量此时目标函数变为此时目标函数变为X(3)(4,2,0,0,4)由于目标函数中的变量系数都小于等于由于目标函数中的变量系数都小于等于0，所以所以X(3)（4,2,0,0,4)为最优解，为最优解，最优值最优值z14下面从几何角度分析一下最优解的寻求过程：几何意义：顶点转移，目标增大三三.单纯形法原理单纯形法原理1.确定初始基可行解：确定初始基可行解：对标准型的LP问题在约束条件(1.1)的变量的系数矩阵中总会存在一个单位矩阵。(2)当线性规划的约束条件都为号时，其松弛变量对应的系数列向量构成的矩阵即为单位阵；(3)当线性规划的约束条件为或的情况，引入人工变量后也可实现。(1)系数矩阵中可

14、以直接观察得到一个单位子矩阵；三三.单纯形法原理（单纯形法原理（2）2.从一个基可行解转换为相邻的基可行解：从一个基可行解转换为相邻的基可行解：定义：两个基可行解称为相邻的，如果他们之间变换且仅变换一个基变量。设初始基可行解为：可知：其对应的系数矩阵的增广矩阵为：三三.单纯形法原理（单纯形法原理（3）易得：(1.3)+(1.4)(0),得令：显然：为使X(1)成为可行解，令：可证明:将(1.6)式代回到X(1)中,X(1)为基可行解，此时完成了从一个基可行解到另一个与其相邻的基可行解的转换。三三.单纯形法原理（单纯形法原理（4）证明：将与变量 x1,xl-1,xl+1,xm,xj对应的列向量，

15、经重新排列后加上b列有如下形式：因为P1,P2,Pl-1，Pj,Pl+1,Pm线性无关，故X(1)为基可行解。三三.单纯形法原理（单纯形法原理（5）3.最优性检验与解的判别：最优性检验与解的判别：将2中的基可行解X(0)与X(1)分别代入目标函数，得 称为检验数三三.单纯形法原理（单纯形法原理（6）(1)当所有的j0时，现行基可行解为最优解；当所有的j0且对应的列向量Pj 0时，该线性规划问题有无界解；(4)对线性规划问题无可行解的判别将在后面讨论。(2)当存在某个j0且对应的列向量Pj 中有正分量时，说明目标函数值还可以增大，需要进行基变换；第第 4 节节 单单 纯纯 形形 法的计算步骤法的

16、计算步骤一一.单纯形法的计算步骤单纯形法的计算步骤第一步：第一步：求初始基可行解，列出初始单纯形表求初始基可行解，列出初始单纯形表XB bx1 x2 .xm xm+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首先写出关于价值系数的表：（非单纯形表）一一.单纯形法的计算步骤（单纯形法的计算步骤（2）将基变量下方的价值系数通过变换化为零，得初始单纯形表将基变量下方的价值系数通过变换化为零，得初始单纯形表XB bx1

17、 x2.xm xm+1 .xj .xnx1x2.xm b1b2.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-z 0 0 .0 .一一.单纯形法的计算步骤（单纯形法的计算步骤（3）第二步：第二步：最优性检验最优性检验(1)当所有的j0时，现行基可行解为最优解；当所有的j0且对应的列向量Pj 0时，该线性规划问题有无界解；(3)当存在某个j0且对应的列向量Pj 中有正分量时，说明目标函数值还可以增大，需要进行基变换。一一.单纯形法的计算步骤单纯形法的计算步骤(4)第三步：换基迭代第三步：换基迭

18、代 (1)确定进基变量确定进基变量选择检验数最大的非基变量为进基变量选择检验数最大的非基变量为进基变量 k=max j|j0,j=1,2,.,n则则xk为进基变量为进基变量(2)确定出基变量确定出基变量 根据下列原则确定出基变量根据下列原则确定出基变量 则则l所对应的基变量所对应的基变量xl为出基变量为出基变量元素元素alk为为轴心项轴心项(或称为主元素或称为主元素)(3)以以alk为轴心项进行换基迭代为轴心项进行换基迭代 即利用矩阵的初等行变换即利用矩阵的初等行变换 把元素把元素alk所在的列化为单位向量所在的列化为单位向量.得到新的单纯形表得到新的单纯形表 一一.单纯形法的计算步骤（单纯形

19、法的计算步骤（5）第四步：第四步：重复第二、三步，一直到计算结束为止。重复第二、三步，一直到计算结束为止。二单纯形法二单纯形法 例例1(1)例例 用单纯形法解下列线性规划用单纯形法解下列线性规划 解解:将原问题化为标准形为：将原问题化为标准形为：得单纯形初表为得单纯形初表为: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)XB

20、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/280 0 -4 1 2301 0 01/4-1300-201/4 T(B3)二单纯形法二单纯形法 例例1(3)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/

21、8 0-1400-3/2 -1/8 0 T(B4)二单纯形法二单纯形法 例例1(4)二单纯形法二单纯形法 例例1(4)在单纯形终表中，x3,x4为非基变量，所有非基变量检验数均小于零，故该线性规划问题有唯一最优解唯一最优解X*=(4,2,0,0,4)T，最优值为 Z*=14。二单纯形法二单纯形法 例例2(1)例例2:用单纯形法解下列线性规划用单纯形法解下列线性规划 解解:将原问题化为标准形为：将原问题化为标准形为：得单纯形初表为得单纯形初表为:XB b x1 x2 x3 x4 x5 x3x4x5 4 3 8 1 0 1 0 0 0 1 0 1 0 1 2 0 0 1-z 0 1 2 0 0 0

22、 T(B1)x3x2x5-z41 0 1 0 030 1 0 1 02100-21-6 100-20 T(B2)二单纯形法二单纯形法 例例2(2)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)二单纯形法二单纯形法 例例2(4)在单纯形终表中，x4,x5为非基变量，非基变量检验数均小于等于零，且4=0,5=-10时，始终选取下标值为最小的变量为

23、进基变量；(2)当计算值出现两个以上相同的最小比值时，始终选取下标值为最小的变量为出基变量。按最小比值来确定出基变量时，有时会出现两个以上相同的最小比值，从而使下一个单纯形表中出现一个或多个基变量等于零的退化解。将使得多个基可行解对应同一顶点，可能出现迭代计算的循环。注：目标函数求最小的情况(1)化成标准型，目标函数求极大；(2)有些书中规定目标函数的极小化作为线性规划的标准形式，这时只需以所有检验数j0作为判别表中解是否是最优的标志。(1)当所有的j0时，现行基可行解为最优解；当所有的j0时，该线性规划问题有唯一最优解；当所有的j 0，且对某个非基变量xk，有k=0,该线性规划问题有无穷多最

24、优解。(2)当存在某个j0且对应的列向量Pj 0时，该线性规划问题有无界解；确定进基变量确定进基变量选择检验数最小的非基变量为进基变量选择检验数最小的非基变量为进基变量 k=min j|j0,j=1,2,.,n则则xk为进基变量为进基变量 确定出基变量确定出基变量 根据下列原则确定出基变量根据下列原则确定出基变量 则则l所对应的基变量所对应的基变量xl为出基变量为出基变量元素元素alk为为轴心项轴心项(或称为主元素或称为主元素)以以alk为轴心项进行换基迭代为轴心项进行换基迭代;(3)当存在某个j0且对应的列向量Pj 中有正分量时，说明目标函数值还可以减小，需要进行基变换。思考题思考题(1)下

25、表是某求极大化线性规划问题计算得到的单纯形表，下表是某求极大化线性规划问题计算得到的单纯形表，表中无人工变量，表中无人工变量，a1,a2,a3,d,c1,c2为待定常数。试说明为待定常数。试说明这些常数分别取何值时，以下结论成立。这些常数分别取何值时，以下结论成立。XBbx1x2x3x4x5x6x3d4a110a20 x42-1-301-10 x63a3-500-41-zc1c200-30思考题思考题(2)(1)表中解为唯一最优解；表中解为唯一最优解；(2)表中解为最优解，但存在无穷多最优解；表中解为最优解，但存在无穷多最优解；(3)该线性规划问题具有无界解；该线性规划问题具有无界解；(4)表中解非最优，为对解改进，进基变量为表中解非最优，为对解改进，进基变量为x1，出基变，出基变量为量为x6。解：解：(1)d0，c10，c20 且且 a10；(4)d0，c10 且且 c1c2，a30,