第一章线性规划问题及单纯形解法课件.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页，此课件共67页哦 单单

4、位位 单位单位 时耗时耗资源资源 一一 二二现有工现有工时时搅拌机搅拌机/小时小时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 3x1 1+5x+5x2

5、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页哦1.1.2 线性规划数学模型的一般表示方式第11页，此课件共

6、67页哦1.1.3 线性规划数学模型的标准型第12页，此课件共67页哦1 1、标准型的几种不同的表示方式、标准型的几种不同的表示方式1）和式第13页，此课件共67页哦2）向量式）向量式第14页，此课件共67页哦3）矩阵）矩阵第15页，此课件共67页哦 1 1）A A中中没有多余方程没有多余方程；2 2）b b 0 0 2 2、对标准型问题作出的假设、对标准型问题作出的假设第16页，此课件共67页哦 最优解最优解l使使z达到最优的达到最优的可行解可行解就是就是最优解最优解l（有解（有解（给定的Lp 问题有最优解）、否则无解）否则无解）可行解可行解 满足约束条件和非负条件的解满足约束条件和非负条件

7、的解 X X 称为称为可行解可行解，所有可行解组成的集合称之为所有可行解组成的集合称之为可行解集可行解集（可行域）（可行域）3、LP问题解的几个基本概念第17页，此课件共67页哦2.第第i 个约束的个约束的bi 为负值，则在为负值，则在bi所在所在之方程的两边乘以之方程的两边乘以-1。4、一般型变标准型的变换方法：1.目标函数为目标函数为min型时，价值系数一型时，价值系数一律反号。即令律反号。即令 z(x)=-z-z(x)=-CX第18页，此课件共67页哦3.3.第第i i 个约束为个约束为 型，在不等式左型，在不等式左边增加一个非负的变量边增加一个非负的变量x xn+in+i ，称为称为松

8、弛变量（原有变量为构造变量）；松弛变量（原有变量为构造变量）；同时令同时令 c cn+in+i =0=04.4.第第i i 个约束为个约束为 型，在不等式左型，在不等式左边减去一个非负的变量边减去一个非负的变量x 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 ，代入非标，代入非标准型，则

9、有准型，则有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 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页哦例2第23页，此课件共67页哦标准型：标准

10、型：max f(x)=-3x1+2x2-4x3+4x3+0 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、

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

12、共部分，如P7图1-2所示。100100 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，

13、B B，C C，D D，E E是可行域的顶点，对是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。有限个约束条件则其可行域的顶点也是有限的。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 xMa

14、x z=50 x1 1+100 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单位单位产品

15、将消耗完所有资源产品将消耗完所有资源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

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

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

18、数列向量线性无关。对应的系数列向量线性无关。只要存在可行解，就一定存在极点只要存在可行解，就一定存在极点 极点的个数是有限的极点的个数是有限的第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页哦 基、基变量、非基变量基、基变量、非基变量技术系数矩阵技

19、术系数矩阵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=

20、0=0，求得基变量，求得基变量X XB B的值称为基解的值称为基解.基可行解：若基解中所有的若基解中所有的X XB B 都都0 0 时，称为时，称为基可行解基可行解.第40页，此课件共67页哦l 若若基可行解基可行解的所有的所有基变量均取正值，基变量均取正值，则称为则称为非退化的基可行解，非退化的基可行解，如果某些基如果某些基变量取零值，则为变量取零值，则为退化的基可行解退化的基可行解。第41页，此课件共67页哦可行解、基解和基可行解举例第42页，此课件共67页哦可行解、基础解和基础可行解举例第43页，此课件共67页哦 X X是极点的充分必要条件是：它是基是极点的充分必要条件是：它是基可行解。

21、由此，有关极点的结果可转到可行解。由此，有关极点的结果可转到基可行解上：基可行解上：只要存在可行解，就一定存在基可行只要存在可行解，就一定存在基可行解；基可行解的个数是有限的；若解；基可行解的个数是有限的；若LPLP问题问题有最优解，则最优解一定可以在基可行解中有最优解，则最优解一定可以在基可行解中找到。找到。第44页，此课件共67页哦 1.3 单纯型法的基本思路确定初始基可行解是否为最优确定改善方向求新的基可行解求最优解的目标函数值是否第45页，此课件共67页哦(1)(1)单纯形表的组成及形式单纯形表的组成及形式设设 B 是初始可行基向量，则目标函是初始可行基向量，则目标函数可写为两部分数可

22、写为两部分(1)约束条件也写为两部分，经整理得约束条件也写为两部分，经整理得 XB 的表达式的表达式(2)，注意，注意 XB中含有非基变中含有非基变量作参数量作参数把把 XB 代入目标函数，整理得到代入目标函数，整理得到(3)式式若所有非基变量的检验数若所有非基变量的检验数i i 0,则则达到最优达到最优第46页，此课件共67页哦单纯形表第47页，此课件共67页哦例1.1试列出下面线性规划问题的初始单纯形表第48页，此课件共67页哦 找初找初 始基础可行基始基础可行基l对于对于(max,)，松弛变量对应的列构成一个单位阵，松弛变量对应的列构成一个单位阵l若有若有 bi 0 中找最大者，选中者称

23、为中找最大者，选中者称为入入基变量基变量 xj*l第第j*列称为主列列称为主列第50页，此课件共67页哦l设第设第 i*i*行使行使 最小，则第最小，则第 i*i*行对应的行对应的基变量称为基变量称为出基变量出基变量，第，第 i*i*行称行称为主行为主行5 5 迭代过程迭代过程l主行主行 i*i*行与行与主列主列 j*j*相交的元素相交的元素a ai*j*i*j*称称为主元为主元，迭代以主元为中心进行，迭代以主元为中心进行l迭代的实质是线性变换，即要将主元迭代的实质是线性变换，即要将主元 a ai*j*i*j*变为变为1 1，主列主列上其它元素变为上其它元素变为0 0，变换步，变换步骤如下：骤

24、如下：(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 基可行解的判别和改进定理定理1.6 若所有检验数若所有检验数 j 0，则为最优解，则为最优解定理

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

26、67页哦 由于所添加的由于所添加的剩余变量剩余变量的技术系的技术系数为数为 1 1，不能作为初始可行基变量，不能作为初始可行基变量，为此引入一个人为的变量为此引入一个人为的变量（注意，此（注意，此时约束条件已为时约束条件已为“=”型），型），以便取以便取得初始基变量，故称为得初始基变量，故称为人工变量人工变量.两种方法：大两种方法：大M M法法 两阶段法两阶段法第57页，此课件共67页哦l多个基础可行解都是最优解，这些多个基础可行解都是最优解，这些解在同一个平面上，且该平面与目解在同一个平面上，且该平面与目标函数等值面平行标函数等值面平行l最优单纯形表中最优单纯形表中有非基变量的检验有非基变量

27、的检验数为数为0 01.5 1.5 单纯形法应用的特例单纯形法应用的特例 1.5.1 1.5.1 关于多重解问题关于多重解问题第58页，此课件共67页哦第59页，此课件共67页哦例1.5.1 的单纯形表及其迭代过程第60页，此课件共67页哦 在单纯形法计算过程中，确定出基在单纯形法计算过程中，确定出基变量时有时存在两个以上的相同的最小变量时有时存在两个以上的相同的最小比值，即同时有多个基变量可选作出基比值，即同时有多个基变量可选作出基变量，这样在下一次迭代中就有了一个变量，这样在下一次迭代中就有了一个或几个基变量等于零，这称之为退化。或几个基变量等于零，这称之为退化。1.5.2 关于退化问题第

28、61页，此课件共67页哦例例1.5.2 用单纯形表求解下列线性规划问题用单纯形表求解下列线性规划问题第62页，此课件共67页哦迭迭代代次次数数基基变变量量CBbx1 x2 x3 s1 s2 s3比值比值2 0 3/2 0 0 00s1s2s30002431 -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页哦第65页，此课件共67页哦l可行区域不闭合可行区域不闭合l单纯形表中入基变量单纯形表中入基变量 x xj*j*(其对其对应检验数大于应检验数大于0)0)对应的列中所有对应的列中所有1.5.4 关于无界解问题第66页，此课件共67页哦第67页，此课件共67页哦