第一章线性规划问题及单纯形解法.ppt

《第一章线性规划问题及单纯形解法.ppt》由会员分享，可在线阅读，更多相关《第一章线性规划问题及单纯形解法.ppt（67页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一章线性规划问题及单纯形解法现在学习的是第1页，共67页 线性规划及应用简介 线性规划是运筹学的一个最基本的分支，它线性规划是运筹学的一个最基本的分支，它已成为帮助各级管理人员进行决策的已成为帮助各级管理人员进行决策的一种十分重一种十分重要的工具是一种目前最常用而又最为成功的要的工具是一种目前最常用而又最为成功的定性分析和定量分析相结合的管理优化技术。定性分析和定量分析相结合的管理优化技术。其原因有三：其原因有三：一、应用广泛管理工作中的大量优化问题可一、应用广泛管理工作中的大量优化问题可以用线性规划的模型来表达以用线性规划的模型来表达现在学习的是第2页，共67页三、求解方法采用成熟的单纯形

2、法目三、求解方法采用成熟的单纯形法目前，用单纯形法解线性规划的计算机程前，用单纯形法解线性规划的计算机程序已大量涌现，在计算机上求解此类问序已大量涌现，在计算机上求解此类问题已十分容易题已十分容易二、模型较为简单，容易建立，容易学习和二、模型较为简单，容易建立，容易学习和掌握掌握现在学习的是第3页，共67页 线性规划的一种最大量、最普遍的应用就是研线性规划的一种最大量、最普遍的应用就是研究有限资源的合理利用问题，或说资源的最优配置究有限资源的合理利用问题，或说资源的最优配置问题资源分配问题有多种多样的具体形式例：问题资源分配问题有多种多样的具体形式例：线性规划解决的问题：1 1、生产的合理安排

3、问题、生产的合理安排问题 2 2、投资决策问题、投资决策问题 3 3、运输问题、运输问题现在学习的是第4页，共67页1.1 1.1 什么是线性规划什么是线性规划（Linear Programming)Linear Programming)1.1.1 Lp1.1.1 Lp的简单例子和模型的简单例子和模型 （1 1）数学模型数学模型 一个实际问题的数学模型，是依据客观一个实际问题的数学模型，是依据客观规律，对该问题中我们所关心的那些量进规律，对该问题中我们所关心的那些量进行科学的分析后得出的反映这些量之间本行科学的分析后得出的反映这些量之间本质联系的数学关系式。质联系的数学关系式。现在学习的是第5

4、页，共67页 单单 位位 单位单位 时耗时耗资源资源 一一 二二现有工现有工时时搅拌机搅拌机/小时小时3515成形机成形机/小时小时215烘箱烘箱/小时小时2211利润（百元利润（百元/吨）吨）54例1.2-1 饼干生产问题现在学习的是第6页，共67页 问题问题 ：如何制订生产计划，才：如何制订生产计划，才能使资源利用充分并使厂方获最大能使资源利用充分并使厂方获最大利润。利润。现在学习的是第7页，共67页解：设由解：设由x x1 1，x x2 2 分别表示分别表示1 1，2 2型饼干每天的型饼干每天的生产量。生产量。max max z=5xz=5x1 1+4x+4x2 2 s.t.s.t.3x

5、 3x1 1+5x+5x2 2 15,15,2x 2x1 1+x+x2 25,5,2x 2x1 1+2x+2x2 211,11,x x1 1,x,x2 20.0.maxmaxmaximize,s.t.maximize,s.t.subject tosubject to现在学习的是第8页，共67页单台运费B1(100)B2(80)B3(90,120)A1(200)152118A2(150)162516问题：问题：如何调运才能即满足用户需要，又使如何调运才能即满足用户需要，又使总运费最少？总运费最少？例1.2-2 运输问题现在学习的是第9页，共67页现在学习的是第10页，共67页技术系数右端项价值系

6、数线性规划问题的规模约束行数变量个数为决策变量为约束条件为目标函数或:;:;:;:;:,.z0,),(),(),(.)(max)min(2121221122222121112121112211ijjjnnmnmnmmnnnnnnabcmnmnxxxtsxxxbxaxaxabxaxaxabxaxaxatsxcxcxcxz1.1.2 线性规划数学模型的一般表示方式现在学习的是第11页，共67页0,.)(max21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcxz1.1.3 线性规划数学模型的标准型现在学习的

7、是第12页，共67页njxmibxatsxcxzjinjjijnjjj,2,1 ,0,2,1 ,.)(max111 1、标准型的几种不同的表示方式、标准型的几种不同的表示方式1）和式现在学习的是第13页，共67页0000 ),(;),(.)(max210212121010bPXC0XbPCXmmjjjjTnnnjjjbbbaaaxxxcccxtsxz2）向量式）向量式现在学习的是第14页，共67页 ),(),(),(.)(max212121212222111211TmTnnmnmmnnbbbxxxcccaaaaaaaaatsxzbXCA0XbAXCX3）矩阵）矩阵现在学习的是第15页，共67页

8、 1 1）A A中中没有多余方程没有多余方程；2 2）b b 0 0 2 2、对标准型问题作出的假设、对标准型问题作出的假设现在学习的是第16页，共67页 0,|xbAxRxsn最优解最优解l 使使z达到最优的达到最优的可行解可行解就是就是最优解最优解l（有解（有解（给定的Lp 问题有最优解）、否则无解）否则无解）可行解可行解 满足约束条件和非负条件的解满足约束条件和非负条件的解 X X 称为称为可可行解行解，所有可行解组成的集合称之为所有可行解组成的集合称之为可行解集（可行解集（可行域）可行域）3、LP问题解的几个基本概念现在学习的是第17页，共67页2.第第i 个约束的个约束的bi 为负值

9、，则在为负值，则在bi所在所在之方程的两边乘以之方程的两边乘以-1。4、一般型变标准型的变换方法：1.目标函数为目标函数为min型时，价值系数一律型时，价值系数一律反号。即令反号。即令 z(x)=-z-z(x)=-CX现在学习的是第18页，共67页3.3.第第i i 个约束为个约束为 型，在不等式型，在不等式左边增加一个非负的变量左边增加一个非负的变量x xn+in+i ，称称为松弛变量（原有变量为构造变为松弛变量（原有变量为构造变量）；同时令量）；同时令 c cn+in+i =0=04.4.第第i i 个约束为个约束为 型，在不等式左边型，在不等式左边减去一个非负的变量减去一个非负的变量x

10、xn+in+i ，称为剩余变称为剩余变量；同时令量；同时令 c cn+in+i =0=0现在学习的是第19页，共67页6.6.若若x xj j 无符号限制，令无符号限制，令 x xj j=x xj j -x xj j，x xj j 0 0，x xj j 0 0，代入非标准型代入非标准型5.5.若若x xj j 0 0，令，令 x xj j=-=-x xj j ，代入非标准，代入非标准型，则有型，则有x xj j 0 0现在学习的是第20页，共67页原非标准型：原非标准型：max z=5xmax z=5x1 1+4x+4x2 2 s.t.3xs.t.3x1 1+5x+5x2 2 15,15,2x

11、 2x1 1+x+x2 25,5,2x 2x1 1+2x+2x2 211,11,x x1 1,x,x2 20.0.5、变换举例例1.现在学习的是第21页，共67页标准型：标准型：max z=5x1+4x2 s.t.3x1+5x2+x3=15,2x1+x2 +x4=5,2x1+2x2 +x5=11,x1，x2，x3，x4，x50.现在学习的是第22页，共67页0,20040065300432.423)(min:213321321321321xxxxxxxxxxxxtsxxxxf不限原非标准型例2现在学习的是第23页，共67页标准型：标准型：max f(x)=-3x1+2x2-4x3+4x3+0

12、x4+0 x5+0 x6 s.t.2x1+3x2+4x3-4x3-x4=300,x1+5x2+6x3-6x3+x5=400,x1+x2+x3-x3+x6=200,x1,x2,x3,x3,x4,x5,x6 0.现在学习的是第24页，共67页1.2 求解LP问题的基本定理 1.2.1 LP的图解法 对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。如：现在学习的是第25页，共67页例例1.3 Maxz=50 x1+100 x2 s.t.x1+x2 300 2 x1+x2 400 x2 250 x1、x2 0现在学习的是第26页，共67页采用图采用图

13、解解 法法(1)分别取决策变量X1,X2 为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1.3的每个约束条件都代表一个半平面。x2x1X20X2=0 x2x1X10X1=0现在学习的是第27页，共67页（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。100200300100200300 x1+x2300 x1+x2=3001001002002x1+x24002x1+x2=400300200300400现在学习的是第28页，共67页（3）把五个图合并成一个图，取各约束条件的公共部分，如P7图1-2所示。100100

14、 x2250 x2=250200300200300 x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x2=400图1-2现在学习的是第29页，共67页（4 4）目标函数）目标函数z=50 xz=50 x1 1+100 x+100 x2 2，当，当z z取某一固定值时得到一条直取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为线，直线上的每一点都具有相同的目标函数值，称之为“等等值线值线”。平行移动等值线，当移动到。平行移动等值线，当移动到B B点时，点时，z z在可行域内在可行域内实现了最大化。实现了最大化。A A，B B，C C，D D，E E是可行

15、域的顶点，对有限是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。个约束条件则其可行域的顶点也是有限的。x1x2z=20000=50 x1+100 x2图1-3z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x1+100 x2CBADEx1+x2=300现在学习的是第30页，共67页得到最优解：x1=50，x2=250 最优目标值z=27500现在学习的是第31页，共67页若在上例模型中中引入松弛变量若在上例模型中中引入松弛变量s s1 1 s s2 2 s s3 3模型化为：模型化为：Max z=50 xMax z=50 x1 1+10

16、0 x+100 x2 2+0s+0s1 1+0s+0s2 2+0s+0s3 3 s.t.x s.t.x1 1+x+x2 2+s+s1 1=300=300 2x 2x1 1+x+x2 2 +s+s2 2=400=400 x x2 2 +s+s3 3=250250 x x1 1,x,x2 2,s,s1 1,s,s2 2,s,s3 300 可求解得其最优解为：可求解得其最优解为：x x1 1=50 x=50 x2 2=250=250 s s1 1=0 s=0 s2 2=50 s=50 s3 3=0=0说明：生产说明：生产5050单位单位产品和产品和250250单位单位产品将消耗完所有资产品将消耗完所

17、有资源源1 1和和3 3，但资源，但资源2 2还剩余还剩余5050。现在学习的是第32页，共67页 max z=5x1+4x2 1.1 s.t.3x1+5x2 15,1.2 2x1+x25,1.3 2x1+2x211,1.4 x1,x20.1.5无需化标准形 例1.2-1 求解饼干生产问题现在学习的是第33页，共67页图中的OABC即为满足约束条件的可行解集S,需在S中找出最优解,若z 为一常数 z0则z0=5x1+4x2为目标函数等值线（x1=10/7,x2=15/7,z*=110/7)。现在学习的是第34页，共67页例1.2-2 假设上例中的目标函数变为 z=3x1+5x2 此时最优目标函

18、数等值线与AB边重合，AB上每一点均为最优解（无穷个）例1.2-3 可行解集为一无界集合 见P18图1.3 若是求目标函数最小值，则有最优解。若是求目标函数最大值，则无最优解。若可行解集为空集，则无解，P19图1.4现在学习的是第35页，共67页求解求解LPLP问题的重要规律：问题的重要规律：一、解的存在性问题一、解的存在性问题二、解的结构问题二、解的结构问题三、关于最优解的获得方法问题三、关于最优解的获得方法问题（在可行解集的某些（在可行解集的某些“顶点顶点”得到）得到）现在学习的是第36页，共67页关于LP问题求解的一些基本概念和特点：1 1、两个基本概念、两个基本概念凸集凸集:实向量空间

19、实向量空间E 中任意两点连线上的中任意两点连线上的一切点仍属于一切点仍属于E(见见P20)极点极点就是不能成为就是不能成为E 中任何线段的内点中任何线段的内点的那种点的那种点现在学习的是第37页，共67页 2、Lp问题的几个特点问题的几个特点(相关证明请看相关证明请看 1.7节节)：最优解只可能在凸集的极点上，而不可能发生最优解只可能在凸集的极点上，而不可能发生在凸集的内部在凸集的内部 线性规划问题的可行解集线性规划问题的可行解集S是凸集是凸集 设设X属于属于S,若若x=0,则一定为极点；若则一定为极点；若x 0，则为极点的充要条件是：则为极点的充要条件是：x的正分量所对应的正分量所对应的系数

20、列向量线性无关。的系数列向量线性无关。只要存在可行解，就一定存在极点只要存在可行解，就一定存在极点 极点的个数是有限的极点的个数是有限的现在学习的是第38页，共67页2、“基基”的概念的概念在在标准型标准型中，技术系数矩阵有中，技术系数矩阵有 n+m列，即列，即 A=(P1,P2 ,Pn,Pn+1,Pn+2,.Pn+m)因因r(A)=m,所以所以A的极大无关组含有的极大无关组含有 m个线性个线性无关的向量。无关的向量。关于标准型解的若干基本概念：1、标准型有、标准型有 n+m个变量，个变量，m 个约束行个约束行现在学习的是第39页，共67页 基、基变量、非基变量基、基变量、非基变量技术系数矩阵

21、技术系数矩阵A（标准线性规划模型（标准线性规划模型）中）中m个个线性无关的列向量所对应的线性无关的列向量所对应的m个变量，构成该个变量，构成该LP问题的问题的一个基，这一个基，这m个变量的系数列向量组成的矩阵称为基阵，记个变量的系数列向量组成的矩阵称为基阵，记为为B。基中的每个变量称为基变量。基中的每个变量称为基变量,记为记为XB。其余的变量即为非基。其余的变量即为非基变量变量,记为记为XN。如：如：Max z=50 x1+100 x2s.t.x1+x2+s1 =300 2x1+x2 +s2 =400 x2 +s3=250 x1,x2,s1,s2,s30基解:令非基变量令非基变量 X XN N

22、=0=0，求得基变量，求得基变量X XB B的值称为基解的值称为基解.基可行解：若基解中所有的若基解中所有的X XB B 都都0 0 时，称为时，称为基可行解基可行解.现在学习的是第40页，共67页l 若若基可行解基可行解的所有的所有基变量均取正值，则基变量均取正值，则称为称为非退化的基可行解，非退化的基可行解，如果某些基变量如果某些基变量取零值，则为取零值，则为退化的基可行解退化的基可行解。现在学习的是第41页，共67页.36)(max,6,2:0,78102.46)(max21543215242132121xfxxxxxxxxxxxxxxxtsxxxf最优解可行解、基解和基可行解举例现在学

23、习的是第42页，共67页可行解、基础解和基础可行解举例1187654322x1876543O109x2A BCEDFGH123f(x)=36K非基非基变量变量基变量基变量图中的点图中的点解解x1,x2x3=10 x4=8x5=7O 基础可行解基础可行解x1,x3x2=10 x4=-2x5=-3F 基础解基础解x1,x4x2=8x3=2x5=-1E 基础解基础解x1,x5x2=7x3=3x4=1 1A 基础可行解基础可行解x2,x3x1=5x4=3x5=7 7D 基础可行解基础可行解x2,x4x1=8x3=-6x5=7 7H 基础解基础解x3,x4x1=2x2=6x5=1 1C 基础可行解基础可

24、行解最优解最优解x3,x5x1=1.5x2=7x4=-0.5 G 基础解基础解x4,x5x1=1x2=7x3=1 1B 基础可行解基础可行解x1=2,x2=2,x3=4,x4=4,x5=3 3 K 可行解可行解现在学习的是第43页，共67页 X X是极点的充分必要条件是：它是基可是极点的充分必要条件是：它是基可行解。由此，有关极点的结果可转到基可行行解。由此，有关极点的结果可转到基可行解上：解上：只要存在可行解，就一定存在基可行解只要存在可行解，就一定存在基可行解；基可行解的个数是有限的；若；基可行解的个数是有限的；若LPLP问题有问题有最优解，则最优解一定可以在基可行解中最优解，则最优解一定

25、可以在基可行解中找到。找到。现在学习的是第44页，共67页 1.3 单纯型法的基本思路确定初始基可行解是否为最优确定改善方向求新的基可行解求最优解的目标函数值是否现在学习的是第45页，共67页(1)(1)单纯形表的组成及形式单纯形表的组成及形式设设 B 是初始可行基向量，则目标是初始可行基向量，则目标函数可写为两部分函数可写为两部分(1)约束条件也写为两部分，经整理得约束条件也写为两部分，经整理得 XB 的表达式的表达式(2)，注意，注意 XB中含有非基变中含有非基变量作参数量作参数把把 XB 代入目标函数，整理得到代入目标函数，整理得到(3)式式若所有非基变量的检验数若所有非基变量的检验数i

26、 i 0,则则达到最优达到最优(4)3()()()(2)(1)(iN1BNNN1BN1BNN1BNNNN1BNNBBNNBBNNABCCXABCCbBCXAbBCXCXAbBXXAbBXbBXXAXCXC检验数xfxf现在学习的是第46页，共67页单纯形表现在学习的是第47页，共67页例1.1试列出下面线性规划问题的初始单纯形表0,12023310032.244540)(max321321321321xxxxxxxxxtsxxxxf现在学习的是第48页，共67页 找初找初 始基础可行基始基础可行基l对于对于(max,)，松弛变量对应的列构成一个单位，松弛变量对应的列构成一个单位阵阵l若有若有

27、bi 0 中找最大者，选中者称为中找最大者，选中者称为入入基变量基变量 xj*l第第j*列称为主列列称为主列现在学习的是第50页，共67页nmjaaajijiji,2,1*l设第设第 i i*行使行使 最小，则第最小，则第 i i*行对应的行对应的基变量称为基变量称为出基变量出基变量，第，第 i i*行称行称为主行为主行5 5 迭代过程迭代过程l主行主行 i i*行与行与主列主列 j j*相交的元素相交的元素a ai i*j j*称称为主元为主元，迭代以主元为中心进行，迭代以主元为中心进行l迭代的实质是线性变换，即要将主元迭代的实质是线性变换，即要将主元 a ai i*j j*变为变为1 1，

28、主列主列上其它元素变为上其它元素变为0 0，变换步骤，变换步骤如下：如下：(1)(1)变换主行变换主行现在学习的是第51页，共67页(2)变换主列变换主列除主元保留为除主元保留为1，其余都置，其余都置0(3)变换非主行、主列元素变换非主行、主列元素 aij(包括包括 bi)(4)变换变换CB，XB(5)计算目标函数、机会成本计算目标函数、机会成本 zj 和检验数和检验数 cj zj6、返回步骤返回步骤 2现在学习的是第52页，共67页例1.1 单纯形表的迭代过程答：最优解为答：最优解为 x1=20,x2=20,x3=0,OBJ=1700现在学习的是第53页，共67页1.3.3 基可行解的判别和

29、改进定理定理1.6 若所有检验数若所有检验数 j 0，则为最优解，则为最优解定理定理1.7 若存在某一个检验数若存在某一个检验数0，而它所对应而它所对应的列向量的全部分量的列向量的全部分量 0，则所给问题无，则所给问题无最优解最优解ija 除上述两种情况外，若每个正检验数所对应除上述两种情况外，若每个正检验数所对应的列向量中都有正分量，则为确定最优解需要的列向量中都有正分量，则为确定最优解需要进行基的变换进行基的变换（换基）（换基）现在学习的是第54页，共67页请查看教材P29中单纯形表的组成形式。现在学习的是第55页，共67页 当约束条件为当约束条件为“”型，引入剩余型，引入剩余变量和人工变

30、量变量和人工变量1.4 1.4 人工变量的引入及其解法人工变量的引入及其解法现在学习的是第56页，共67页 由于所添加的由于所添加的剩余变量剩余变量的技术系的技术系数为数为 1 1，不能作为初始可行基变量，为，不能作为初始可行基变量，为此引入一个人为的变量此引入一个人为的变量（注意，此时约（注意，此时约束条件已为束条件已为“=”型），型），以便取得初始基以便取得初始基变量，故称为变量，故称为人工变量人工变量.两种方法：大两种方法：大M M法法 两阶段法两阶段法现在学习的是第57页，共67页l多个基础可行解都是最优解，这多个基础可行解都是最优解，这些解在同一个平面上，且该平面与些解在同一个平面上

31、，且该平面与目标函数等值面平行目标函数等值面平行l最优单纯形表中最优单纯形表中有非基变量的检验有非基变量的检验数为数为0 01.5 1.5 单纯形法应用的特例单纯形法应用的特例 1.5.1 1.5.1 关于多重解问题关于多重解问题现在学习的是第58页，共67页0,12023310032.254540)(max 1.5.1 321321321321xxxxxxxxxtsxxxxf多重最优解例现在学习的是第59页，共67页例1.5.1 的单纯形表及其迭代过程现在学习的是第60页，共67页 在单纯形法计算过程中，确定出在单纯形法计算过程中，确定出基变量时有时存在两个以上的相同的基变量时有时存在两个以

32、上的相同的最小比值，即同时有多个基变量可选最小比值，即同时有多个基变量可选作出基变量，这样在下一次迭代中就作出基变量，这样在下一次迭代中就有了一个或几个基变量等于零，这称有了一个或几个基变量等于零，这称之为退化。之为退化。1.5.2 关于退化问题现在学习的是第61页，共67页例例1.5.2 用单纯形表求解下列线性规划问题用单纯形表求解下列线性规划问题1312131231233max222,24,3,0.zxxxxxxxxxxxx目标函数约束条件现在学习的是第62页，共67页迭迭代代次次数数基基变变量量CBbx1 x2 x3 s1 s2 s3比值比值2 0 3/2 0 0 00s1s2s3000

33、2431 -1 0 1 0 02 0 1 0 1 01 1 1 0 0 12/14/23/102 0 3/2 0 0 01x1s2s32002011 -1 0 1 0 0 0 2 1 -2 1 00 2 1 -1 0 10/21/240 2 3/2 -2 0 0现在学习的是第63页，共67页l约束条件互相矛盾，无可行域约束条件互相矛盾，无可行域1.5.3 关于无可行解问题现在学习的是第64页，共67页0,1212.2)(max1.5.3 321321321321321xxxxxxxxxxxxtsxxxxf例现在学习的是第65页，共67页l可行区域不闭合可行区域不闭合l单纯形表中入基变量单纯形表中入基变量 x xj j*(其对应其对应检验数大于检验数大于0)0)对应的列中所有对应的列中所有0a*ij1.5.4 关于无界解问题现在学习的是第66页，共67页0,501002.)(max4.5.1 21212121xxxxxxtsxxxf例现在学习的是第67页，共67页