发布时间 : 星期四 文章线性规划问题更新完毕开始阅读
我们可以采取如下方法求解:通过作图，首先画出各个方程所代表的直线，然后 根据其几何位置判断出最优点A为直线L:a;:x，+a12xZ=b;和xZ轴的交点，将其求 出并代入f(x)=c、x、+c2x2就可以求出最优目标函数值。
在此过程中，我们在判断最优点为凰2时.实际上是利用了目标函数梯度C的正交分 解，将C投影到直线L上，有C二C，+C2，由直线L上C‘的方向就可以判断出最优 解是直线L与坐标轴xZ即直线x;=0的交点A。明显地，如果目标函数梯度C在直 中南大学硕士学位论文线性规划逐维选优强多项式解法8 线L上的投影向量CL=0，直线L是一维最优解集。 再看三维空间，假设存在如下线性规划问题 毗xf(x)=elx，+eZxZ+e3x3 5.t.al:x;+a12x2+al3x3=bl aZlxl+a22x2+a23x3=bZ xl)0 xZ)0
x3)0
同样，通过作图我们也可直接判断出实际存在的某一维数的最优解集并将其 通过直接计算求出。与二维空间解法类似，设直线L是
a;lx:+aLZxZ+al3x3=bl a21xl+a22x2+a23x3=bZ
的公共解，将目标函数梯度C向其投影，在下图图左的情形，点A是零维最优解 集，目标函数梯度C在点A上的投影向量为零，可以通过正交化产生它的三个线 性无关的法向量;在下图图右的情形，目标函数梯度C在直线L上的投影向量为 零，直线L是一维最优解集，可以通过正交化产生它的两个线性无关的法向量。 虽然在二维或三维情况谈到确定最优解集的二个或三个相互正交的线性无关法 向量和考查目标函数梯度C在最优解集上的投影向量为零的事实没有很大必要， 一般情况下我们都不会这样做，但是对于更高维的情况，要确定最优解集的线性 无关法向量和考查目标函数梯度C在低维平面上的投影向量是否为零就是完全 不同的关键所在了，这在后面我们会详细讨论。
若如下图图右，目标函数梯度C在直线L上的投影向量为零，则说明L与第 一象限的交就是最优解集，剩下的工作就是对其进行判断，看它是否穿过第一象 限，这可以通过判断直线L上是否存在某一点x的所有坐标满足x，)O来进行。 若如上图图左，目标函数梯度C在直线L上的投影向量不为零，则说明L与第一 象限的交不是最优解集，下一步的工作是继续进行向更低维的平面投影，直到出 中南大学硕士学位论文线性规划逐维选优强多项式解法9
现目标函数梯度C在低维平面上的投影向量为零的情形。由于向量在零维平面即 一点上的投影向量总为零，对于一般的n维高维空间的线性规划问题SLP，这种 逐维降维进行投影的工作最多做n次。 为为 卒木、 右 “ 舀筹冬 一xl一xl 图2.2
我们再回过头来对单纯形迭代解法进行分析，与上述几何求解方法比较就会 发现它们二者的不同之处在于单纯形法是通过对坐标超平面上的极点进行搜索 而得到最优点，在搜索过程中实际上是以极点的函数值作为判断的依据，这样对 于存在多个极点的坐标超平面，一般情况会出现在该坐标超平面多次甚至重复搜 索的状况。而从几何解法可以看出，如果我们对坐标超平面按照其与可行域的交 的几何位置进行排序，然后依此顺序逐个进行搜索，对于已经查找过的坐标超平 面就不会再进行重复搜索，于是可以大大减少运算的次数，实现基于强多项式时 间复杂度的算法。
2.2基于逐维选优算法的设想 2.2.1目标分解
为了实现线性规划基于逐维选优算法的设想，我们首先分析线性规划问题最 优集的构成，它由两部分凸集的交构成，一部分是由代数方程组Ax=b的解集构 成的n一m维原始等式约束平面，另一部分是所有坐标xi)O(1簇i簇n)的点集即n 维空间的第一象限，而n维空间的第一象限的n个边界是n个n一1维的坐标超平 中南大学硕士学位抢文线性规划逐维选优强多项式解法10
面:、:xi二O的非负部分。由于问题的线性，如果线性规划问题存在最优解集，则 最优解集一定是n一m维原始等式约束平面与若干个坐标超平面的非负部分的交。 所以，我们可以断定线性规划问题最优解集是n维空间的一个低维平面r(在此， 我们把直线和点都看成低维平面的特例)的非负部分。为了明确描述n维空间的 一个低维平面P的非负部分，我们必须引入平面的内部和平面的内法向的定义。 定义2.1称Rn的凸域DI={Xla仪)b}为平面aTx=b的内部，a为平面犷x=b的 内法向，Rn一D，为扩x=b的外部。多个平面的内部的交为这多个平面的交的内部。 于是，利用法向基和切向基互补的性质，为了确定n维空间中一个k(k成n)
维的低维平面的非负部分，我们只需要确定它的一组k个线性无关的内法向量构 成的内法向基以及在此平面上的一个可行点即其所有坐标x;)0(1毛i簇n)的点 即可。这样也就可以接着求出n一k个切向量构成的切向基并用它们和求出的可行 点直接表出线性规划问题最优集上的所有点。
至此，我们明确了实现线性规划基于逐维选优算法的关键，是寻找出最优解 集的一组内法向基和最优集上的一个可行点。 2.2.2初步设想
我们把由Ax=b确定的原始等式约束平面记作FO，f’“与某个坐标超平面:‘:
xj=0(1毛i延n)相交时，其交记作F:。F。与k(o毛k蕊n一m)个坐标超平面的交是 。k、Fk与坐标超平面二j的交是r尸、Rn的原点。在Fk上的投影为O众、Rn的标准正 交基向量ej(1簇j成n)和目标函数梯度c在rk上的投影向量为e}(1簇j毛n)和ck. 若r“上有点x)O，称I’*是可行的，由于SLP的可行域连续，也就有rk是SLP的可行 域的n一m--k维低维界面;否则称rk是不可行的.明显地，当点x在Fk上移动时，当 且仅当它穿过Fk与坐标超平面二‘的交时，其坐标x，才改变正负号。
在线性规划逐维选优算法中，确定当前可行低维平面rk与坐标超平面:‘的
位置关系是其核心问题之一。由于rk是维数比坐标超平面二‘的维数要小的低维 平面，它们之间的位置关系总共只有三种状态。 (1)Fk与二’平行
中南大学硕士学位伦文线性规划逐维选优强多项式解法11
当rk有法向量与二‘的法向量相同且它们没有公共点时，rk与二‘平行。此
时若rk在所有坐标超平面二‘(1延i蕊n)的内部，Fk的内部可行;若Fk在某一个
坐标超平面二‘的外部，r“的内部不可行。
(2)Fk在二‘上
当rk有法向量与二‘的法向量相同且它们有公共点时，rk在二‘上。此时r“ 与二‘的交的可行性与Fk的可行性相同。 (3)rk在二‘相交
当Fk的所有法向量都与二‘的法向量不同时，Fk与:‘相交。此时若rk可行， 则Fk与二‘的交r梦+l又存在两种状态。
(3 .
1)rk与二‘的交F黔中存在可行点，这说明F)+1可行，r尸上还具
有存在最优解的可能性，若rk不是最优解集，可以降维到F梦+l上继续逐维选优。 (3
.
2):k与二‘的交F全+l中不存在可行点，这说明F梦+l不可行，F)+l上 不可能存在最优解，若Fk不是最优解集，应该降维到别的存在可行点的r{+1上 继续逐维选优。
若rk可行且己经判定最优解在Fk上达到，但Fk不是最优解集，其上可行
的r}+1可能有多个，应该降维到哪一个F{+l上继续逐维选优呢?我们可以仍然由 二维情况得到启发。 rk+l J
rk+l J 口
沙、ej讯人lleseses C k.几l
W下e爪人lleewewe ‘爪
C
图2‘3
上图图左中可行域的边界面r{+1在rk上的内法向e:与rk上的梯度ck反 向垂直，因而P尸是最优解集;上图图右中可行域的所有边界面中没有一个的内 法向与ck反向垂直，但一定有某一r州在Fk上的内法向e{与ck最接近反向垂 直，因而最优解不论其是否有界都一定在F{+l上达到。“r{+l在Fk上的内法向 中南大学硕士学位论文线性规划逐维选优强多项式解法12
e
:与Ck最接近反向垂直”就是计及正负号时rk上。k与所有非零的e梦的夹角中 ck与e:的夹角最小。
由此我们可以写出基本的解题步骤。
(i)对于犷x=b的处理:利用Sc腼idt正交化求出原始等式约束平面
r。的m个法向量构成的法向基并由它求出原点O在r。上的投影。
(11)对于x)0的处理:将n个坐标基向量ei(1毛i共n)投影到P“，记其投
影向量为ei0。由于F。有法向量与二‘的法向量相同等价于ei。=0，可以判断出n
个坐标超平面二’(1毛i毛n)与r。的几何位置。首先判断F。是否可行，如果可行， 将目标函数梯度C投影到r“上，记其投影向量为C0。然后将与F“相交也就是ei0 护O对应的坐标超平面(假设其个数为q)按C0与e，”夹角计及正负号由小到大排 序。
_
(111)按所排次序逐个判断对应的r‘是否可行，对第一个可行的F’继续判
断F‘是否为最优解集，若是最优解集，计算终止，若不是最优解集，进行投影 降维到该厂’，用它取代ro继续逐维选优，直到求出最优解集或确定最优解无界。 (iv)若求出了n一m一k维的最优解集rk，则同时可以确定它的k个相互正交 的法向量及原点在Fk上的投影Zk，利用这k个正交法向量可以确定rk的n一In--k 个线性无关的切向量(::，下2，?，T。~)
(v)最优解集Fk中的任何点都可用x=zk十入;!，十入2TZ+.二十人n~kTn~k表出， 其中n一In--k个参数人i的变化范围可由对应的n一二k个独立的xi多0确定。 中南大学硕士学位论文线性规划逐维选优强多项式解法13 第三章新理论的构成 3.1相关定义
新算法的解题步骤明确后，为了从数学上进一步明确地描述和准确地展开讨 论，需要先给出如下一些定义。 一、低维有向平面
定义3.1称卫，?k={xla丁x=b:，a百x=bZ，?，a万x==bk，xERn，1蕊k簇n，bl、 bZ、?、bkER，aL、aZ、?、akER“且线性无关}为Rn的n一k(1毛k毛n)维平面。 注1.低维有向平面的基本构成
二卜~k有k个线性无关的法向量a，、?、ak和n一k个线性无关的切向量 e犷、?、e:_、。并且这k个法向量的任意线性组合人;al十?十人ka、都是平面二卜二 的法向量，它们一起构成了平面二，一k在Rn中的正交补二八。
注2.低维平面的切向确定
平面二卜一，上的任意一点Pk和二，一、的n一k个切向量的线性组合x=Pk十 巧e卜·‘’十汽一ke;‘构成了该n一k维平面。明显地，切向确定的办法不能描述低维 有向平面的方向。
注3.低维有向平面的法向确定
如果我们规定a，、?、氏为平面二卜~、的内法向，则得到的是Rn的一个
n一k维有向平面，可以认为n一k维有向平面就是平面:卜一、及它的k个线性无关的 内法向共同构成的。
注4.Rn中的0维有向平面
特别地，Rn中的O维有向平面由Rn中的某一点和它的n个线性无关内法 向共同构成。 二、凸多面锥
中南大学硕士学往论文线性规划逐维选优强多项式解法14
定义3.ZRn中k(k)n)个含n个线性无关法向量的超平面的内部的交称作
Rn中的凸多面锥，这些超平面称作该凸多面锥的界定平面，界定平面与凸多面锥 的交称作该凸多面锥的界面。凸多面锥的若干界面的交称作该凸多面锥的一个低 维界面，两个相交的维数相同的低维界面互为邻接界面。 注1.凸多面锥的界面的基本构成
Rn中的凸多面锥的界定平面不一定是该凸多面锥的界面，只有那些与凸