《第五讲--修正单纯形法(1)(运筹学-清华大学-林谦).ppt》由会员分享，可在线阅读，更多相关《第五讲--修正单纯形法(1)(运筹学-清华大学-林谦).ppt（19页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 1 13/8/20233/8/2023第九讲第五讲 修正单纯形法（修正单纯形法（1）大约在1954年，Dantzig和他的同事就发现了更有效的单纯形法。我们知道，在单纯(扩展)表格中，共有3组元素，分别与矢量组“a1，an”，“b”及“e1em”相对应，如果说前面讲的习惯用的一般单纯形表格法可只采用左边两组的话，那么，修正单纯形法在运算迭
2、代中只应用右边两组，下面就具体阐述该种方法。仍假设：AX=b，X0，CTX=min(1)且A、b、C已知，属非退化情形，计算过程，将始终用到A，B，C这些原始数据，故需保存。每一个阶段仍用单纯形表格迭代，只用右边两组，即m+1列，每个表格与当前基础解集相对应（j1，jm）：Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 2 23/8/20233/8/2023第九讲修正单纯形法（修正单纯
3、形法（2）t10tm0u11u1mum1ummz0 y1ym(2)其中：ti0给出当前基础解uij给出当前基础阵之逆z0给出当前基础解费用yi给出当前基础阵之联立方程解YTM=(3)Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 3 33/8/20233/8/2023第九讲修正单纯形法（修正单纯形法（3）(5)其中 当前基础解的目标系数。表格的起步可根据两阶段法的第1阶段之初始基础解表
4、格开始，即：ti0=bi，uij=ij，z0=bi，yi=1(4)第1阶段结束后，第2阶段开始的表格需加以修改，唯一修改处是最末一行，这是由于目标函数发生了变化z0和yi计算公式为：Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 4 43/8/20233/8/2023第九讲修正单纯形法（修正单纯形法（4）(6)如果zj cj，则令j=s，并作为支点列。如果zj cj，则去试探其它非基础
5、列j，假若所有非基础列j的zj cj，则已达到最优解，其最优解值为：下面来阐述表格的迭代过程。在一般单纯形表格法中，每次检验元素zjcj全部算出，然后寻找支点列，而在修正单纯形表格中，不需一次计算全部检验元素，而是逐个计算。设j属非基础集，则：Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 5 53/8/20233/8/2023第九讲修正单纯形法（修正单纯形法（5）(7)其最小费用为z
6、0和最优对偶解为yT。否则，计算zj(按6式)，找出zj cj，并令j=s，然后处理如下：首先，计算单纯形表的支点列s：(8)Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 6 63/8/20233/8/2023第九讲修正单纯形法（修正单纯形法（6）如果所有tis0，则最优解不存在，最优目标无限，即，(9)费用若存在tis0,可求出支点行：(10)Operations Research
7、 Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 7 73/8/20233/8/2023第九讲修正单纯形法（修正单纯形法（7）求出支点行后，就可进行修正单纯形表格的转换，其表格转换元素的计算只需计算后面m+1列，即：新行r=(原行r)/trs(11)新行i(ir)=(原行i)i(原行r)(12)其中：最后，用as取代旧表格Vr中表示的基矢量。Operations Research Operations Research Pr
8、of.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 8 83/8/20233/8/2023第九讲修正单纯形法（修正单纯形法（8）例1-23已知线性规划为：解1）应用阶段1，求出初始基础可行解构成新规划：AX=b，X0,CTX=minOperations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpa
9、ge page 9 93/8/20233/8/2023第九讲修正单纯形法（修正单纯形法（9）令人工变量作为第1个基础可行解之基础变量，其对应的表格为：e1e2be1e251013011811Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 10103/8/20233/8/2023第九讲修正单纯形法（修正单纯形法（10）检验非基础变量a1，a2，a3能否进基，可按任何次序检验。先检验a1：
10、Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 11113/8/20233/8/2023第九讲修正单纯形法（修正单纯形法（11）e1e2a1be1e215104130151811min5/1，13/4=13/4r=2。支点元素为t21，进行变换使(t1)列中：t21=1，t11=0，z1c1=0，得：将(t1)临时放入表格中，以便求出支点行，Operations Research Op
11、erations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 12123/8/20233/8/2023第九讲修正单纯形法（修正单纯形法（12）当前表格对应的基础矢量为e1和a1。再次校验非基础矢量，看是否可进入基础矢量，任意选择a3检验。e1a1a1 be1e207/41-1/4113/401/407/41-1/4Operations Research Operations Research Prof.Wang Prof.Wang Schoo
12、l of Economics&ManagementSchool of Economics&Managementpage page 13133/8/20233/8/2023第九讲修正单纯形法（修正单纯形法（13）将(t3)加入修正单纯形表格中，并求出支点行r。e1a1a3 be1e23/27/41-1/43/213/401/43/27/41-1/4Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage p
13、age 14143/8/20233/8/2023第九讲修正单纯形法（修正单纯形法（14）即e1离开基，a3进基，将表格变换得：a3a1a3 be1e217/62/3-1/603/2-11/20000从表中看出，故阶段1结束，得出初始基础可行解为x3=7/6，x1=3/2，x2=0。Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 15153/8/20233/8/2023第九讲修正单纯形法
14、（修正单纯形法（15）2）现进行阶段2，阶段2的第1个表格可借用阶段1的最后表格，仅仅将最后一行加以修改。此时：A，B，C恢复到原问题数值，这时CT=(7，1，1)。其初始表格为：a3a1be1e27/62/3-1/63/2-11/235/3-19/310/3其中，Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 16163/8/20233/8/2023第九讲修正单纯形法（修正单纯形法（
15、16）现判断非基矢量a2是否应进入基础解集。Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 17173/8/20233/8/2023第九讲修正单纯形法（修正单纯形法（17）即支点行r=1，a3离开，支点元素t12=1/2。将a2加入表格并转换a2 be1e21/27/62/3-1/61/23/2-11/2335/3-19/310/3将a2对应的t2列变为t12=1，t22=0，z2c2
16、=0得出新表格为：Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 18183/8/20233/8/2023第九讲修正单纯形法（修正单纯形法（18）目前基础矢量为a2和a1。再检验非基矢量a3：a2 be1e217/34/3-1/301/3-5/32/3014/3-31/313/3a2a1故已得最优解：x2=7/3，x1=1/3y1=-31/3，y2=13/3，且z=14/3Operat
17、ions Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 19193/8/20233/8/2023第九讲修正单纯形法（修正单纯形法（19）与此相应的有另一种方法对偶单纯型法，它的迭代原则是：在保证“优化”前提下，寻找原问题可行解，即在保证对偶可行解基础上，逐步找出原规划可行解。这些概念体现在表格上，即使每一步表格的检验行的元素(zjcj)都0，而表格的b列元素可能0。迭代的原则就是逐步将B列元素全变为0的值（求得最优解）或证明无可行解。对偶单纯形的迭代思路与前述单纯形法一样，此处不再赘述，感兴趣者，可参阅有关书籍。