2012秋--第2章-第2部分-单纯形算法.docVIP

硕士研究生课程—线性与整数规划2012-秋 Ocean University of China Q. Fang PAGE  PAGE 18 第2章 第2部分：单纯形算法 (Chapter2: The Simplex Algorithm §2.4—§2.6, §2.8, §2.9) 单纯形法的基本思路： 初始bfs 判定最优性 改进得新bfs 最优解 是 否 1.初始bfs如何找? 2.如何判定? 3.如何改进? ` （由此而引发上述三个问题，以下主要针对解决这些问题来讨论） 给定线性规划问题 (LP)： s.t. (A为矩阵且,即A行满秩) 1. 关于线性规划问题bfs 的典式： 不妨设基为（LP）的一个可行基，则（LP）的约束条件通过线性方程组的恒等变换即可化为： （2.1） （2.2） 写成方程组展开的形式即为： x1 + β1m+1xm+1 + β1m+2xm+2 + … +β1kxk …+ β1nxn = α1 x2 + β2m+1xm+1 + β2m+2xm+2 + … +β2kxk …+ β2nxn = α2 (★) …… …… …… …… …… …… xm + βmm+1xm+1 + βmm+2xm+2 + … +βmkxk …+ βmnxn = αm 目标函数 z =z0 + λm+1xm+1 + … + λnxn 即所有基变量和目标函数均用非基变量来表示，式(★)称为关于基B的典式。由于基B是可行基，故上式中约束条件右端的常数α1，α2，…αm均非负。 关于（LP）典式的几点说明： 任意给定两个基B1，B2，它们对应的典式是同解的，也都与原（LP）同解； 典式的优点或特点：用非基变量表示基变量及目标函数，对基本解而言，由于非 基变量取值为0，可从典式立即得到基本可行解及其目标值——基变量的取值恰好是典式约束条件的右端值，而对应的目标值恰为典式中目标函数中的常数项。 2．从一个bfs到另一个bfs的变换 (§2.4 Moving form bfs to bfs) 不失一般性，以下均针对可行基来进行讨论。 对任意，考察在其它非基变量不变的前提下，非基变量的值可以增加（取正值）吗？最多可以增加多少？ 分析：从典式来看，当其他非基变量都保持为0时，约束条件为： (2.3) 此时是否可增加及增加多少，都由要求x1,x2…xm ≥ 0来确定： 令要求： 。 的范围： 若βik ≤ 0：任意增加都可保证； 若βik 0：须满足，即。 由此可知增加的范围是：。 定理1 (Theorem 2.7). 不妨设bfs 对应的基为,是一个非基变量。令（此最小值在基变量处取到）。 ① 是一个基； ② 由下式给出的解是关于新基的bfs： (2.4) 且若确定时有多于一行同时达到最小值，则新bfs 是退化的。 Proof：① 往证是(LP)的一个基，即其系数列向量线性无关。因为是基（线性无关），故可由它们线性表出： ， (2.5) 这里线性系数恰好为典式(★)约束条件中非基变量的系数。 事实上,由于,而 ，， 即 (β1k ,β2k ,…βmk)T=β1k(1 ,0 ,…0)T +β2k(0 , 1 ,…0)T + … +βmk(0 , 0 ,…1)T B-1Pk B-1P1 B-1P2 B-1Pm 故(2.5)式成立。 又因为βik 0，故不能由线性表出，即是一个基。 ② 由(2.3)式和(2.4)式容易验证结论成立。 ■ 注1： 上述这种从一个bfs变换到另一个bfs的方式称为旋转变换，称为入基变量和入基列；称为出基变量和出基列。 注2：若现行bfs非退化，必有。 当现行bfs退化时，可能取值为0。当时，新bfs与原bfs是相同的， 此时称非基变量以0水平入基。但需强调的是：这同一个解对应的基是不同的，一个基是B={P1,P2,…Pm}，而另一个是。 注3：若入基列中各分量均有βik ≤0，此时令，无论多大，总能保证原基变量；也就是说可行解域无界。 3．入基变量的选择与bfs的最优性的判定： (§2.6 Choosing a Profit