运筹学课件2 07-10线性规划-2.ppt

《运筹学课件2 07-10线性规划-2.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、本讲内容单纯形法(Simplexmethod)计算机求解线性规划的例子线性规划应用举例单纯形法基本思想由于线性规划问题的最优解必定会在顶点达到，而顶点（基可行解）又是有限的。单纯形法的基本思想正是在有限的基可行解中通过有限次迭代寻找最优解。单纯形法的求解过程是否方法前提：化为标准型三个问题如何得到初始基？如何判断当前基可行解是否达到最优？如何转换到另一个基可行解？确定初始基可行解由于基可行解是由一个可行基决定的，因此，确定一个初始可行解X0就是要确定一个初始可行基B0方法：若A中含I，则B0=I；若A中不含I，则可用人工变量法构造一个I问题：若B0=I，则X0=？初始基可行解（initia

2、lbasicfeasiblesolution）如何判断当前基可行解是否达到最优？最优性检验把目标函数用非基变量表示检验数向量，记为，当≤0时，当前解为最优检验数计算方法（1）计算每个Xj的检验数，（2）若当前所有的；则当前的解最优；否则，至少有一个，则转下一步。Ps.检验数（testnumber）;最优解（optimalsolution）如何转换到另一个基可行解？基变换(basisiteration)由于基可行解与基对应，即寻找下一个基可行解相当于从上一个基B0转换为下一个基B1。基变换原则：改善Z1>Z0;可行变换方法：（P1,···,Pl,···,Pk,···,Pn)进基—保证“改

3、善”—令对应的Pk进基出基—保证“可行”—由决定出基方法：令Ps.进基变量(enteringbasicvariable);主元(pivotnumber)出基变量(leavingbasicvarible)单纯形表单纯形表是基于单纯形法步骤设计的一种计算表格。单纯形法过程回顾：需计算单纯形表的主要体内容是B-1(bA)由于相邻两个B只有一列不相同，所以相邻两个B-1可以通过初等行变换求得，由此设计了基于初等行变换的单纯形表。单纯形表CXB-1bB-1A单纯形表主要结构问题：第一张表的B-1=？--单位阵I检验数公式是什么？--B-1Pj在哪里？--B-1A的第j列cj3-305-1CBXBb

4、X1X2X3X4X5θ10-22001-20000-431例Maxz=3x1-3x2+5x4-x5X1-2x3+2x4=12X2-2x3=1-4X3+3x4+x5=27x1,…,x5≥0X1X2X53-3-11212700-420主元旋转变换cj3-305-1CBXBbX1X2X3X4X5θ-3-1X2x561271/20-11001-20000-431旋转变换cj3-305-1CBXBbX1X2X3X4X5θ-3-1X2x56191/20-11001-200-3/20-101旋转变换cj3-305-1CBXBbX1X2X3X4X5θ5-3-1X4X2x56191/20-11001-200

5、-3/20-101计算检验系数cj3-305-1CBXBbX1X2X3X4X5θ5-3-1X4X2x56191/20-11001-200-3/20-101-10-200全小于等于0判断是否达到最优,若达到则计算出最优值cj3-305-1CBXBbX1X2X3X4X5θ5-3-1X4X2x56191/20-11001-200-3/20-10118-10-200最优值最优解？课堂习题用单纯形表法求解下述LP问题：XBCBB-1bx1x2x3x4x5x303609410090x402004501040x5030031000130712000x302407.8010-0.430.8x40502

6、.5001-0.520x212300.31000.11003.4000-1.2x3084001-3.121.16x17201000.4-0.2x21221010-0.12-0.16000-1.36-0.52课堂习题注：单纯形表中的信息：(1)每列的含义B-1(bA)=(B-1b,B-1P1,···,B-1Pn)(2)每个表中的B与B-1的查找B在初表中查找；B-1在当前表中查找，对应初表中的I的位置以第二个表为例：XBCBB-1bx1x2x3x4x5x303609410090x402004501040x5030031000130712000x302407.8010-0.430.8x

7、40502.5001-0.520x212300.31000.11003.4000-1.2x3084001-3.121.16x17201000.4-0.2x21221010-0.120.16000-1.36-0.52(3)终表分析最优基B*和(B*)-1用单纯形表法求解下述LP问题：课堂习题CBXBB-1b2.5100x1x2x3x40x315351050x410520122.51000x39019/51-3/52