运筹学课件ch1单纯形法

《运筹学课件ch1单纯形法》由会员分享，可在线阅读，更多相关《运筹学课件ch1单纯形法（51页珍藏版）》请在装配图网上搜索。

1、1第二节 单纯形法 单纯形法是求解线性规划的主要算法，1947年由美国斯坦福大学教授丹捷格（G.B.Danzig）提出。尽管在其后的几十年中，又有一些算法问世，但单纯形法以其简单实用的特色始终保持着绝对的“市场”占有率。21.线性规划的标准型 用单纯形法求解线性规划的前提是先将模型化为标准型表示为0.XbAXtsCXMaxz 标准型的特征：Max型、等式约束、非负约束一、单纯形法的预备知识。）（的秩为其中，0,bnmmAnm3非标准形式如何化为标准1)MinMin型化为型化为MaxMax型型 CXMinzCXMaxz/加负号 因为，求一个函数的极小点，等价于求该函数的负函数的极大点。)(xf)

2、(xf*x注意：Min型化为Max型求解后，最优解不变，但最优值差负号。4.约束方程的转换：由不等式转换为等式。约束方程的转换：由不等式转换为等式。ijijbxa0 iniinjijxbxxa称为松弛变量称为松弛变量 ijijbxa0 iniinjijxbxxa称为剩余变量称为剩余变量5 例1 某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源。现将有关数据列表如下：试拟订使总收入最大的生产方案。资源单耗 产品资源甲 乙资源限量煤电油9 44 5 3 10360200300单位产品价格 7 122)不等式约束化为等式约束不等式约束化为等式约束62)不等式约束化为等式约束分析：以例1中煤的约束

3、为例3604921 xx之所以“不等”是因为左右两边有一个差额，称为“松弛量”，若在左边加上这个松弛量，则化为等式。而这个松弛量也是变量，记为X3，则有36049321xxxX3称为松弛变量。问题：它的实际意义是什么？煤资源的“剩余”。7练习：请将例1的约束化为标准型0,3001032005436049.21212121xxxxxxxxts解：增加松弛变量则约束化为,543xxx0,300 10320054360 49.54321521421321xxxxxxxxxxxxxxts易见，增加的松弛变量的系数恰构成一个单位阵I。8一般地，记松弛变量的向量为 Xs，则0.XbAXts0,.ssXXb

4、IXAXts0.XbAXts0,.ssXXbIXAXts问题：松弛变量在目标中的系数为何？0。3)当模型中有某变量 xk 没有非负要求，称为自由变量,则可令 0,/kkkkkxxxxx化为标准型。sXCXzMAX092.基本概念（1）可行解与最优解；的解，记为可行解：满足全体约束X。，有解则对任可行的，记为最优解：可行解中最优*,CXCXXX直观上，可行解是可行域中的点，是一个可行的方案；最优解是可行域的角点，是一个最优的方案。10（2）基矩阵与基变量基矩阵(简称基)：由系数阵A中的线性无关的列线性无关的列组成的m阶子矩阵阶子矩阵，记为B；其余列构成非基矩阵，记为N。基向量：基B中的列；其余的

5、列称非基向量。基变量：与基向量Pj对应的决策变量xj，记其组成的 向量为XB；与非基向量对应的变量称非基变 量，记其组成的向量为XN。基矩阵的特点:1.基B是可逆矩阵,即2.基B是一个 方阵mm0Br（B）=m或者nmmnmppppA.11A=(B N )111231241432123,0 xxxxxxxx例：下 面 为 某 线 性 规 划 的 约 束请 例 举 出 其 基 矩 阵 和 相 应 的 基 向 量、基 变 量。阶可逆子阵有中的，解：本例中，210011221AA 6个。一般地，mn 阶矩阵A中基的个数最多有多少个？个。mnC;,100143434311xxXxxPPBB，基变量为，

6、其相应的基向量为。基变量为其相应的基向量为21212122,1221xxXxxPPBB问题：本例的A中一共有几个基？12【例【例4】线性规划】线性规划 32124maxxxxZ5,1,0226103553214321jxxxxxxxxxj 求所有基矩阵求所有基矩阵。【解】约束方程的系数矩阵为【解】约束方程的系数矩阵为25矩阵矩阵 10261001115A,610151B,010152B,110053B26114B10019B,12017B,02118B,16016B,06115B容易看出容易看出r(A)=2，2阶子矩阵有阶子矩阵有C52=10个，个，其中第其中第1列与第列与第3列构成的列构成的

7、2阶矩阵不是一个基，阶矩阵不是一个基，基矩阵只有基矩阵只有9个，即个，即02101513（3）基本解与基本可行解.0,0,1111bBXbBXXNXBbBXbXXNBbAXXXXNBAmABBABkkBkBTkB时，有当取即可表示为约束中的相应地）（列，则可记中的前表示取定后，不妨设中的基当解；为线性规划的一个基本的解称0NbBXbAX可见：一个基本解是由一个基决定的。注意：基本解仅是资源约束的解，并未要求其非负，因此其未必可行。称非负的基本解为基本可行解基本可行解（简称基可行解）。14例3中0,321241421321xxxxxxxx 求相应于基B1和B2的基本解，它们是否基本可行解？,31

8、311001,1001,1001111bBBBNN解：是基本可行解。的基本解为相应于基,)3,1,0,0(NTXB,51-573151-525251,51-525251,1-221112bBBB22不是基本可行解。的基本解为相应于基,0,0)51,-57(2TXB15,610151B对对来说，来说，x1,x2是基变量，是基变量，x3,x4，x5是非基变是非基变量，令量，令x3=x4=x5=0，因因|B1|，由克莱姆法则知，由克莱姆法则知，x1、x2有唯一解有唯一解x12/5,x2=1则则 基本解为基本解为TX)0,0,0,1,52()1(32124maxxxxZ5,1,022610355321

9、4321jxxxxxxxxxj在例4中,Xi0,是基本可行解16在在 中中x10,因此不是可行解，也就不是基本可行解。因此不是可行解，也就不是基本可行解。）（2X反之，可行解不一定是基本可行解反之，可行解不一定是基本可行解例如例如 满足所有约束式满足所有约束式,但不是但不是任何基矩阵的基本解。任何基矩阵的基本解。TX)1,27,21,0,0(32124maxxxxZ,010152B5,1,0226103553214321jxxxxxxxxxjTX)0,4,0,0,51()2(基本解为基本解为0不全为NX17上二组概念间的联系：系数阵A中可找出若干个基B每个基B都对应于一个基本解非负的基本解就是

10、基本可行解几种解之间的关系：可行解基本解非可行解基本可行解问题：基本可行解是可行域中的哪些点？使目标函数值最优的基本可行解是最优解183.基本定理（1）线性规划的可行域是一个凸多面体。（2）线性规划的最优解（若存在的话）必能在可行 域的角点获得。（3）线性规划可行域的角点与基本可行解一一对应。19二、单纯形法的步骤 单纯形法是一种迭代的算法，它的思想是在可行域的角点基本可行解中寻优。由于角点是有限个（为什么？），因此，算法经有限步可终止。确定一个初始基可行解检验这个基可行解是否最优寻找一个更好的基可行解否是停止201.确定初始基可行解 由于基可行解是由一个可行基决定的，因此，确定初始基可行解X

11、0相当于确定一个初始可行基B0。方法：若A中含I，则B0=I；若A中不含I，则可用人工变量法构 造一个I。问题：若B0=I，则X0=？可行。,000NMMbbBX212.最优性检验问题：用什么检验？目标。kBkBkkkBkbkBXNBCCbBCXCNXBbBCXXCCCXz)(NN)()(11而目标优。时，当前基可行解为最，则当记 01NBCCBk问题：非最优的特征为何？。至少有某个检验数0k22NNBBNBNBNBNBNBXCXCXXCCCXZNXBbBXbNXBXXXNBAX)()(11NBNBXNBCCbBCz)(11因为:将XB代入Z,有0Z*为最优值的条件是233.寻找更好的基可行解

12、 由于基可行解与基对应，即寻找一个新的基可行解，相当于从上一个基B0变换为下一个新的基B1，因此，本步骤也称为基变换。（基变换）0NNMNbBzz可行：改善：基变换的原则）变换的方法：（nklPPPP,N进基出基进基；对应的令保证“改善”进基kkP0可决定出基。由保证“可行”出基011kBNXBbBX 称作检验比。i24 以例1为例，可按上述单纯形法的步骤求出其最优解，其大致的过程如下。（1）先将模型化为标准型0,3001032005436049.54321521421321xxxxxxxxxxxxxxts 21127xxMaxz(2)确定初始基可行解、检验;00,300)(0,0,360,2

13、,00)(360,200,3,0100TTXbBB111;,52PP向量为再计算检验比确定出基，确定进基向量为计算非基向量的检验数2500011000100010000CC3133PBB基B=(P3,P4,P5)=100010001=B-10054，同样可知，非基N=(P1,P2)=105434973491000100010007CC1111PBB122确定进基向量为确定进基向量为P2计算检验数计算检验数,确定进基向量确定进基向量Max(0)26计算检验比计算检验比,确定出基向量确定出基向量Min(0)ik1i1ikPBbB300200360bB110541054100010001PB2130

14、40901030052004360P5出基出基B1=(P3,P4,P2)确定确定新基新基27（3）换基、计算下一个基可行解、再检验，直至最优;50,0)(0,24,240,)(240,50,30,1051411111TTXbBB;0,0)(20,24,84,(84,20,24),103544912122TTXbBB00;,41PP向量为再计算检验比确定出基量为计算检验数确定进基向前解为最优。计算检验数均非正，当问题：当模型规模较大时，计算量很大。事实上，单纯形法的实现是在单纯形表上完成的。28练习：对于下面的线性规划0,6222min2N2N2N2Nxxxxxxxxz（1）用图解法求解；（2）

15、将模型化为标准型；（3）用单纯形法步骤求出其最优解，并指出求 解过程中每一个基可行解相当于可行域的 哪一个角点。29三、单纯形表 单纯形表是基于单纯形法的步骤设计的计算格式，是单纯形法的具体实现。110101100)()(000BmBbBmBCcbBXBikiiijBBjjmi nM回顾单纯形法步骤bBN需计算ABN需计算,AbB1内容是因此，单纯形表的主体 121110AbBAbBAbB 即30单纯形表单纯形表CjC1C2CjCBXBB-1bX1X2XjP1P2pj(0?)Ab分别将系数C,矩阵A和资源限制b填入,得到单纯形表的初表,计算检验数,进行最优性检验,若非优,就做初等行变换,形成新

16、基的单纯形表=C-CBB-1A31单纯形表的主要结构：X CABNbBN问题：第一张表的B-1=？单位阵I。检验数的公式是什么？jBjjPBCcN在哪里？jPBN列中的第jAB1 32例5：用单纯形法求解例10,3001032005436049.21212121xxxxxxxxts21127xxMaxz将模型化为标准型：解：增加松弛变量,543xxx 0,3001032005436049.54321521421321xxxxxxxxxxxxxxts 21127xxMaxz问题：标准模型的A中是否含I？松弛变量系数恰好构成I。3354321 xxxxxbBNBXBC0 0 0 12 710010

17、3010540014930020036054Pxxx000 0 0 0 12 7 3040907;3490)0 (071111pBCcB其中检验数904360P 中表示进基列与出基行的交叉元，下一张表将实行以它为主元的初等行变换行变换（称高斯消去）。方法是：先将主元消成1，再用此1将其所在列的其余元消成0。3454321 xxxxxbBNBXBC0 0 0 12 7100103010540014930020036054Pxxx000 0 0 0 12 7 3040900.1 0 0 1 0.3 300.4-0 1 0 7.8 2400.5-1 0 0 2.5 50243xxx1200 1.2-

18、0 0 0 3.41002030.8 0.2-0.4 0 0 1 201.16 0.32-1 0 0 840.16 0.12-0 1 0 24213xxx1270428.,0,0)(20,24,84,*zXT（请解释其实际意义）0.52-1.36-0 0 0此行元素除以主元1030 0.3 1 0 0 0.1此行元素乘以(-5)加入上行此行元素除以主元2.535练习：用单纯形法求解下面的线性规划0,62-2-.2121 21xxxxxxts 212-xxMins将模型化为标准型：解：增加松弛变量,43xx212xxMaxz0,622 -.4342132121xxxxxxxxxxts36 432

19、1xxxx 0 0 2-1bBNBXBC10 2 101 1 1-6243xx006 0 0 2-1 1 0 2 1 6 1 1 3 0 813xx10 1-0 4-0TX)0,8,0,6(6s注：1.表上每一列的含义：),(),(NNNNNnPBPBbBAbB2.每张表上B-1的位置在哪？对应于初表中I 的位置。,1110B,101111B3754321 xxxxxbBNBXBC0 0 0 12 7100103010540014930020036054Pxxx000 0 0 0 12 7 3040900.1 0 0 1 0.3 300.4-0 1 0 7.8 2400.5-0 1 0 2.5

20、 50243xxx1200 1.2-0 0 0 3.41002030.8 0.2-0.4 0 0 1 201.16 0.32-1 0 0 840.16 0.12-0 1 0 24213xxx1270 1.2-1.36-0 0 0.428,)0,0,84,24,20(*zXT,111NMB,0.10.5-10.4-111B.0.160.12-0.2-0.41.163.12-112B最优基解XB=(x3,x1,x2)最优基B=(p3,p1,p2)在哪里?.10305404912B3854321 xxxxxbBNBXBC100103010540014930020036054Pxxx000 0 0 0

21、 12 7 0.2-0.4 0 1 1.16 0.32-1 0 0.16 0.12-0 0 213xxx1270 0.52-1.36-0 0 0例6：填表：,2420843002003600.160.1200.20.401.163.1211bB解：10010540.160.1200.20.401.163.12112PB242084100初表终表39练习：用单纯形法求解下面的线性规划0,25.2121 21xxxxxxts105153212.5xxMaxz将模型化为标准型：解：增加松弛变量,43xx21xxMaxz5.20,102515 53.4342132121xxxxxxxxxxts4010

22、 2 501 5 3101543xx00 0 0 1 2.525 4321xxxx 0 0 1 2.5bBNBXBC51 0 52 153-1 519 02913xx2.50 0.5-0 0 0TX)09,0,2,(5z,1110B,51053-111B问题：本题的单纯形终表检验数有何特点？非基变量x2 的检验数等于零。41注：（1）解的几种情况在单纯形表上的体现（Max型）：-唯一最优解：终表非基变量检验数均小于零；-多重最优解：终表非基变量检验数中有等于零的；-无界解：任意表有正检验数相应的系数列均非正。不同类型的解的判别不同类型的解的判别:42 （2）Min型单纯形表与Max型的区别仅在

23、于：检验数反号，即 -令负检验数中最小的对应的变量进基；min -当检验数均大于等于零时为最优。Min型的单纯形法型的单纯形法0043大M法方法:在一个标准的线性规划问题的约束条件中加进人工变量Xr并给定该人工变量在目标函数中的系数为(-M)(M为任意大的正数)bIXrAXMXCXzrmaxrMXCXzmin对于min型 有何不同?最优性最优基中不含人工变量若基变量中不含有非零的人工变量，表示原问题有若基变量中不含有非零的人工变量，表示原问题有解。若对于解。若对于MAX型，当型，当 0，而还有人工变量（非，而还有人工变量（非零）时，则表示原问题无可行解。零）时，则表示原问题无可行解。设规划模型

24、约束条件为设规划模型约束条件为AXb或者或者AX=b，此时需加入人，此时需加入人工变量，以便在工变量，以便在A矩阵中得到一个矩阵中得到一个mm的单位矩阵，的单位矩阵，使初始基可行。使初始基可行。44例8 现有线性规划问题，试用大M法求解。0,123241123min32131321321321xxxxxxxxxxxxxxz45解解 在上述问题的约束条件中加入松弛变量x4，剩余变量x5，人工变量x6,x7，得到0,12324112003min76543217316532143217654321xxxxxxxxxxxxxxxxxxxMxMxxxxxxz这里M是一个任意大的正数。思考:能不能将第二个

25、等式乘以-1?不能。基解要可行,不能为负46 因本例的目标函数是要求min，所以用所有cj-zj0来判别目标函数是否实现了最小化.用单纯形法进行计算时，初表如下:Cj-31100MMCBXBB-1bX1X2X3X4X5X6X7P1P2P3P4P5P6P70X4111-21100011MX63-4120-1103/2MX71-20100011(j0?)-3+6M1-M1-3M0M00MIN进基47Cj-31100MMCBXBB-1bX1X2X3X4X5X6X7P1P2P3P4P5P6P70X4103-20100-1-MX610100-11-211X31-2010001-(j0?)-11-M00M

26、03M-10X4123001-22-541X210100-11-2-1X31-2010001-(j0?)-10001M-1M+148Cj-31100MMCBXBB-1bX1X2X3X4X5X6X7P1P2P3P4P5P6P7-3X141001/3-2/32/3-5/31X210100-11-21X390012/3-4/34/3-7/3(j0?)0001/3M03M-1终终 表表最终计算结果表中，表明已得到最优解是：x1=4,x2=1,x3=9，x4=x5=x6=x7=0；目标函数z=-249建建立立模模型型个个 数数取取 值值右右 端端 项项等式或等式或不等式不等式极大或极小极大或极小新加新加

27、变量变量系数系数两两个个三个三个以上以上xj0 xj无无约束约束xj 0 bi 0bi 0=maxZminZxs xa求求解解图图解解法、法、单单纯纯形形法法单单纯纯形形法法不不处处理理令令xj=xj-xj xj 0 xj 0令令 xj=-xj不不处处理理约束约束条件条件两端两端同乘同乘以以-1加加松松弛弛变变量量xs加加入入人人工工变变量量xa减减去去xs加加入入xa不不处处理理令令z=-ZminZ=max z0-M50对目标函数求max的线性规划问题，用单纯形法计算步骤的框图见图1-9。51作业作业:用单纯形法求解下述线性规划问题,并列出初始单纯形表和计算的终表.0,52151565935.121510321321321321321xxxxxxxxxxxxtsxxxzMax