第四章 线性规划本章主要内容:线性规划的基本理论 线性规划的单纯形法 线性规划的对偶理论 线性规划的对偶单纯形法教学目的及要求:理解线性规划的基本理论;掌握线性规划的单纯形法;理解线性规划的对偶理论;掌握线性规划的对偶单纯形法。

教学重点:线性规划的单纯形法. 教学难点:线性规划的对偶单纯形法. 教学方法:启发式.教学手段:多媒体演示、演讲与板书相结合. 教学时间:6学时. 教学内容:§4、1 线性规划的基本理论考虑线性规划问题11min ;,1,2,,,0,1,2,,.nj j j n ij j i j j c x a x b i m x j n ==⎧⎪⎪⎪==⎨⎪⎪≥=⎪⎩∑∑s.t. (LP)或min ;,0.T c x Ax b x ⎧⎪=⎨⎪≥⎩s.t. 其中 121212(,,,),(,,,),(,,,),(),T T T n n m ij m n x x x x c c c c b b b b A a ⨯====A 称为约束矩阵,Ax b =称为约束方程组,0x ≥称为非负约束.假定:rank()A m =.定义 在(LP)中,满足约束方程组及非负约束的向量x 称为可行解或可行点;所有可行解的全体称为可行解集或可行域,记作K ,即{,0}K Ax b x ==≥.使目标函数在K 上取到最小值的可行解称为最优解;最优解对应的目标函数值称为最优值.定义 在(LP)中,约束矩阵A 的任意一个m 阶满秩子方阵B 称为基,B 中m 个线性无关的列向量称为基向量,x 中与B 的列对应的分量称为关于B 的基变量,其余的变量称为关于B 的非基变量.任取(LP)的一个基12(,,,)m j j j B p p p =,记12(,,,)m T B j j j x x x x =,若令关于B的非基变量都取0,则约束方程Ax b =变为B Bx b =.由于B 就是满秩方阵,因此B Bx b =有唯一解1B x B b -=.记121(,,,)m T j j j B b x x x -=,则由12,1,2,,,0,{1,2,,}{,,,}k k j j j m x x k m x j n j j j ===∀∈-所构成的n 维向量x 就是Ax b =的一个解,称之为(LP)的关于B 的基本解.基本解满足约束方程组,但不一定满足非负约束,所以不一定就是可行解.若10B b -≥,即基本解x 也就是可行解,则称x 为(LP)的关于基B 的基本可行解,相应的基B 称为(LP)的可行基;当10B b ->时,称此基本可行解x 就是非退化的,否则,称之为退化的.若一个(LP)的所有基本可行解都就是非退化的,则称该(LP)就是非退化的,否则,称它就是退化的.例1 求下列线性规划问题的所有基本可行解.12123124min 44;4,2,0,1,2,3,4.j x x x x x x x x x j -⎧⎪-+=⎪⎨-++=⎪⎪≥=⎩s.t. 解 约束矩阵的4个列向量依次为12341110,,,1101p p p p -⎛⎫⎛⎫⎛⎫⎛⎫==== ⎪ ⎪ ⎪ ⎪-⎝⎭⎝⎭⎝⎭⎝⎭.全部基为113214323424534(,),(,),(,),(,),(,),B p p B p p B p p B p p B p p =====对于1B ,1x 与3x 为基变量,2x 与4x 为非基变量.令2x =4x =0,有1314,2,x x x +=⎧⎨-=⎩ 得到关于1B 的基本解(1)(2,0,6,0)T x =-,它不就是可行解.对于2B ,1x 与4x 为基变量,2x 与3x 为非基变量.令2x =3x =0,有1144,2,x x x =⎧⎨-+=⎩ 得到关于2B 的基本解(2)(4,0,0,6)T x =,它就是一个非退化的基本可行解.同理,可求得关于345,,B B B 的基本解分别为(3)(4)(5)(0,2,6,0),(0,4,0,6),(0,0,4,2)T T T x x x ==-=,显然,(3)x 与(5)x 均就是非退化的基本可行解,而(4)x 不就是可行解.因此,该问题的所有基本可行解为(2)(3)(5),,x x x .此外,因为这些基本可行解都就是非退化的,所以该问题就是非退化的.定理 1 设x 为(LP)的可行解,则x 为(LP)的基本可行解的充要条件就是它的非零分量所对应的列向量线性无关.证明 不妨设x 的前r 个分量为正分量,即12(,,,,0,,0),0(1,2,,).T r j x x x x x j r =>=若x 就是基本可行解,则取正值的变量12,,,r x x x 必定就是基变量,而这些基变量对应的列向量12,,,r p p p 就是基向量.故必定线性相关.反之,若12,,,r p p p 线性无关,则必有0r m ≤≤.当r m =时,12(,,,)r B p p p =就就是一个基;当r m <时,一定可以从约束矩阵A 的后n r -个列向量中选出m r -个,不妨设为12,,,r r m p p p ++,使121(,,,,,,)r r m B p p p p p +=成为一个基.由于x 就是可行解,因此1rj j j x p b ==∑,从而必有1mj j j x p b ==∑.由此可知x 就是关于B 的基本可行解.定理 2 x 就是(LP)的基本可行解的充要条件就是x 为(LP)的可行域的极点.证明 由定理4.1.1与定理2、2、2知结论成立. 例2 求下列线性规划问题的可行域的极点.1212314min ;22,2,0,1,2,3,4.j x x x x x x x x j -⎧⎪++=⎪⎨+=⎪⎪≥=⎩s.t. 解 因为约束矩阵的4个列向量依次为12341210,,,1001p p p p ⎛⎫⎛⎫⎛⎫⎛⎫==== ⎪ ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭⎝⎭.全部基为112213314424534(,),(,),(,),(,),(,),B p p B p p B p p B p p B p p =====求得关于基12345,,,,B B B B B 的基本解分别为(1)(2)(3)(4)(5)(2,0,0,0),(2,0,0,0),(2,0,0,0),(0,1,0,2),(0,0,2,2)T T T T Tx x x x x =====显然,(1)(2)(3),,x x x 均为退化的基本可行解,(4)(5),x x 就是非退化的基本可行解.可行域有三个极点:(2,0,0,0)T ,(0,1,0,2)T ,(0,0,2,2)T .定理3 若(LP)有可行解,则它必有基本可行解. 证明 由定理2.2.1及定理4、1、2知结论成立.定理 4 若(LP)的可行域K 非空有界,则(LP)必存在最优解,且其中至少有一个基本可行解为最优解.证明 根据推论 2.2.6,(LP)的任一可行解x 都可表示为(LP)的全部基本可行解12,,,k x x x 的凸组合,即 1,ki i i x x x K λ==∀∈∑,其中10(1,2,,),1ki i i i k λλ=≥==∑.设s x 就是使(LP)中目标函数值达到最小的基本可行解,即 1min T T s i i kc x c x ≤≤=,则11,k kTTT T i i i s s i i c x c x c x c x x K λλ===≥=∀∈∑∑.这表明,基本可行解s x 为(LP)的最优解.定理 5 设(LP)的可行域K 无界,则(LP)存在最优解的充要条件就是对K 的任一极方向d ,均有0T c d ≥.证明 根据定理2.2.10,(LP)的任一可行解x 都可写成11kli i j j i j x x d λμ===+∑∑,其中12,,,k x x x 为(LP)的全部基本可行解,12,,,l d d d 为K 的全部极方向,且10(1,2,,),1,0(1,2,,)ki i j i i k j l λλμ=≥==≥=∑.于就是,(LP)等价于下面以0(1,2,,)0(1,2,,)i j i k j l λμ≥=≥=和为决策变量的线性规划问题111min ()();1,0,1,2,,,0,1,2,,.k lT Ti i j j i j k i i i j c x c d i k j l λμλλμ===⎧+⎪⎪⎪⎪=⎨⎪⎪≥=⎪≥=⎪⎩∑∑∑s.t. 由于j μ可以任意大,因此若存在某个j d ,使0T j c d <,则上述问题的目标函数无下界,从而不存在最优解,从而(LP)不存在最优解.若1,2,,j l ∀=,均有0T j c d ≥,设1min T T s i i kc x c x ≤≤=,则11()(),k lTTT T i i j j s i j c x c x c d c x x K λμ===+≥∀∈∑∑.所以基本可行解s x 就是(LP)的最优解.推论 6 若(LP)的可行域K 无界,且(LP)存在最优解,则至少存在一个基本可行解为最优解.证明 由定理4.1.5的证明过程可知结论成立. 定理7 设在(LP)的全部基本可行解12,,,k x x x 中,使目标函数值最小者为12,,,s i i i x x x ;在K 的全部极方向12,,,l d d d 中,满足0T j c d =者为12,,,t j j j d d d .若(LP)存在最优解,则x 为(LP)的最优解的充要条件就是存在10(1,2,,),1,0(1,2,,)pp q si i j p p s q t λλμ=≥==≥=∑使 11p p q qsti i j j p q x x d λμ===+∑∑.(*)证明 因为(LP)存在最优解,所以由定理4.1.4与推论4、1、6及其证明知,基本可行解12,,,s i i i x x x 就是(LP)的最优解.设x 具有(*)式的形式,则由推论2.2.6与定理2、2、10知,x 为(LP)的可行解,从而由(*)式知,111p p q q stTTT T i i j j i p q c x c x c d c x λμ===+=∑∑因此,x 为(LP)的最优解.反之,设x 为(LP)的任一最优解,则x 为可行解,于就是由推论2.2.6与定理2、2、10知,存在 10(1,2,,),1,0(1,2,,)ki i j i i k j l λλμ=≥==≥=∑,使 11kli i j j i j x x d λμ===+∑∑. (**)根据定理1.1.5,有 0,1,2,,T j c d j l ≥=,且由1i x 为最优解知1,1,2,,T T i i c x c x i k ≥=.从而由上述两式容易用反证法证明:若(**)式中某个0i λ>,则i x 必为(LP)的最优解;若(**)式中某个0j μ>,则必有0T j c d =。