線性規(guī)劃的基本概念與基本定理

1、第十二章線性規(guī)劃的基本概念和基本定理12.1線性規(guī)劃的基本概念可行解，可行域定義:稱滿足全部約束條件的向量為可行解或可行點(diǎn)m axf = CZ例如：SLP'AZ=bs.t Z _0L如果Z0滿足這些約束，即AZ°=b且z0 _ 0,則Z0就是SLP的可行解.定義12.1.2 :稱所有可行解(點(diǎn))構(gòu)成的集合為可行集或可行域也稱為可行解集例如：上面 SLP的可行域?yàn)镽二AZ二b,Z _0定義 12.1.3 :若一個(gè)線性規(guī)劃問題的可行集為空集時(shí)，則稱這一線性規(guī)劃無可行解.這時(shí)線性規(guī)劃的約束條件不相容.矚慫潤厲釤瘞睞櫪廡賴。由上一章的分析可以看到：一個(gè)線性規(guī)劃的可行解集可以是空集，

2、有界非空 集和無界非空集.最優(yōu)解，無界解定義12.1.4 :稱使目標(biāo)函數(shù)值達(dá)到最優(yōu)值的可行解為線性規(guī)劃問題的最優(yōu) 解定義12.1.5 :對(duì)于極大化目標(biāo)函數(shù)的標(biāo)準(zhǔn)線性規(guī)劃問題，定義其無界解如下：對(duì)于任何給定的正數(shù)M，存在可行解 X滿足AX二b, X 一 0，使CX M .聞創(chuàng)溝燴鐺險(xiǎn)愛氌譴凈。無界解的意思是：若是極大化目標(biāo)函數(shù)， 極小化目標(biāo)函數(shù)，則在可行域上目標(biāo)函數(shù)值無下界則在可行域上目標(biāo)函.那么，有.殘騖樓諍錈瀨濟(jì)溆塹籟。那么稱該線性規(guī)劃問題有無界解 由定義可知，數(shù)值無上界；若是 無界解的線性規(guī)劃問題一定沒有最優(yōu)解例考慮線性規(guī)劃問題：max(X| x2)X| -血-1st二-x1 x2 玄 1

3、為 _ 0, x2 _ 0圖 解：問題的可行域是上圖所示的無界凸多邊形區(qū)域，在此無界可行域上，目標(biāo)函數(shù)值無上界，所以這個(gè)線性規(guī)劃問題有無界解 .釅錒極額閉鎮(zhèn)檜豬訣錐。X"i i X2 1I例 12.1.2 max f =咅一x2st -x- +x2 <1x 0, x2 亠0解：此問題的可行域如上圖，是一個(gè)無界的多邊形.但極大化目標(biāo)函數(shù)卻以1 為上界.因此這個(gè)線性規(guī)劃問題沒有無界解，而且事實(shí)上，此問題目標(biāo)函數(shù)最優(yōu) 值max f=1在可行域射線x, -x2 =1上均可達(dá)到.彈貿(mào)攝爾霽斃攬磚鹵廡。12.1.3.基本可行解定義12.1.6 :對(duì)于約束條件Ax=b，設(shè)A是秩m的mx n矩

4、陣，用(片，j=1 n)表示A的第j列向量.即A=(p1.pn).由A的m個(gè)列向量構(gòu)成的m階方陣B=( pj , pj .pj )謀養(yǎng)摶篋飆鐸懟類蔣薔。若B是非奇異的，即detBO,則稱B為一個(gè)基或稱為一個(gè)基矩陣.因?yàn)镾LP問題中含有約束條件 Ax=b，因此也通常稱B為線性規(guī)劃SLP的 一個(gè)基.由上面定義可知，B中m個(gè)列向量是線性無關(guān)的，并且它是 A的列向量組 的一個(gè)最大無關(guān)組.按定義，A中m個(gè)列向量，只要是線性無關(guān)的就可以構(gòu)成一個(gè)基 .定義12.1.7 :若變量對(duì)應(yīng)A中列向量pj包含在基B中，則稱為B的 基變量；若變量兀對(duì)應(yīng)A中的列向量pk不包含在基B中，則稱兀為B中的非基 變量.廈礴懇蹣駢

5、時(shí)盡繼價(jià)騷。為 + x2 + x3 = 5使 f = 2x, x2例 12.1.3 求 X1X5 滿足 J 一NF+xr-2'1 110 0'1A =-110 10則B =0(6 2 0 0 1,<0x - 0,i = 1 5解：156治+2x2+x5 =210 010的列是線性無關(guān)的，即0 10 'p5 = 0是線性無關(guān)，因此x3 x4(1、組基.而p1 =-1,P2 =1丿a.)x?是，不在這個(gè)基中，所以X1,X2為非基變量.定義12.1.8 :設(shè)Ax=b, x>0 一個(gè)基B = (pj1.pjm )，其對(duì)應(yīng)的基變量構(gòu)成的m維列向量記為XB=(Xji.X

6、jm)T這時(shí)若全非基變量等0,則Ax=b = Bxb二b, 得唯一解Xb =BJb .記為Bb = ( b. bT)于是得到方程組Ax=b的一個(gè)解 Xji - b1, Xj2 = b2 Xjm = bm,非基變量Xj =0,( j =1,2.n, i Hjjm)稱之為對(duì)應(yīng)于基B的基本解這個(gè)定義也告訴 我們?cè)鯓诱乙粋€(gè)基本解)煢楨廣鰳鯡選塊網(wǎng)羈淚。女如:上面例12.1.2 中，非基變量Xi=X2=0.則可得Xs =5,X4=4,Xs=21.所以x0 =(0,0,5, -2,21)是對(duì)應(yīng)于基B的一個(gè)基本解，但由于x4 =-2<0.不能滿足約 束條件，所以這個(gè)基本解不是原問題的可行解 .(為什么

7、？)鵝婭盡損鶴慘歷蘢鴛賴。這是因?yàn)?，按照定義，基本解中的 n-m個(gè)非基變量必須取0值只有m 個(gè)基變量取值才可能不等于0.但可以取負(fù)值.因此基本解不一定滿足SLP的非負(fù) 要求.籟叢媽羥為贍債蟶練淨(jìng)。定義12.1.9 :對(duì)應(yīng)于基B的基本解，若基變量取非負(fù)值，即xB = B_ b , b>0， 則稱它為滿足約束 Ax=b, x>o的基本可行解.預(yù)頌圣鉉儐歲齦訝驊糴。對(duì)應(yīng)地稱B為可行基，因SLP中具有此約束條件.也通常 稱為SLP的基本 可行解.定義12.1.10:使目標(biāo)函數(shù)達(dá)到最優(yōu)值的基本可行解，稱為基本最優(yōu)值.例：(SLP)如例,試找一個(gè)基本可行解. 10、解：B = -1 0 0是其

8、一個(gè)基矩陣.p-j, p3, p5是一個(gè)基.則x1,x3,x5為基變<6 0 b量.x2, x 為非基變量.令 X2 “4 =0.得 X1 = 2, X3 = 3, X5 =9.故 x, = (2,0,3,0,9)是 原問題的一個(gè)基本可行解，B1為基可行基.滲釤嗆儼勻諤鱉調(diào)硯錦。上面我們講到基本解中有n-m個(gè)分量必須取零值，而只有m個(gè)基變量取非 零值.而基本可行解，它一方面是基本解，另一方面又是可行解，因?yàn)樗腔?解，所以n-m個(gè)非基變量取0值；它是可行解，則 m個(gè)基變量取非負(fù)值，從而 基本可行解正分量是個(gè)數(shù)不超過 m.鐃誅臥瀉噦圣騁貺頂廡。那么滿足Ax=b,x -0的正分量個(gè)數(shù)不超過

9、 m的可行解.Rank(An n)二m是否一 定是基本可行解呢？我們舉例說明這個(gè)問題.X1 X2 X3 = 4例已知約束條件為：2x1 2x2 x4 =8為 - 0, x2 - 0, x3 - 0,x4 - 0它有正分量個(gè)數(shù)等于m(m=2)的可行解.為=3, x2 =1, x3 =0,X4 =0但它不是基本可行解.證明：(反證法)假設(shè)可行解x=(3,1,0,0)T面約束的基本可行解.因?yàn)榛究尚?解中非基變量取0值，基變量取非負(fù)值.擁締鳳襪備訊顎輪爛薔。在這個(gè)可行解中X!,X2非零正值，因此X,X2不可能是非基變量，只能是基變 量.按定義，基變量對(duì)應(yīng)的系數(shù)矩陣中的列向量 pp2應(yīng)構(gòu)成一個(gè)基矩陣

10、B.但這 里Pl, P2是線性相關(guān)的(Pi = P2),這與B是基矩陣矛盾.故知X=(2,1,0,0)T是基可 行解 .贓熱俁閫歲匱閶鄴鎵騷。由此例可見，雖然可行解(3, 1, 0, 0)T正分量個(gè)數(shù)不超過m,但它的正 分量對(duì)應(yīng)的列向量線性無關(guān)，不能與一基矩陣相聯(lián)系，所以它不是一個(gè)基本可行 解 .壇搏鄉(xiāng)囂懺蔞鍥鈴氈淚?，F(xiàn)在我們把例中松弛變量x3,x4去掉，約束變?yōu)閤1 x2 _ 42x1 2x2 _8禺=0,x2亠0其可行域如圖，可行解(3，1, 0, 0) T用x1,x2表示為圖上點(diǎn)(3，1). 由圖可見這不是可行域的頂點(diǎn).而我們今天將證明基本可行解是可行域的頂點(diǎn).而 在例中口，卩2線性無關(guān)

11、，所以B=( SP2)是一個(gè)基矩陣，對(duì)應(yīng)的基本解為(4,0, 0, 0) T用坐標(biāo)X1,X2表示則為平面上的點(diǎn)(4, 0),是上圖可行域的頂點(diǎn).對(duì)于這 個(gè)基B=(Pi,P3)的基本可行解(4, 0, 0, 0) T .除了非基變量X2=X4=0夕卜，還 有基變量x3=0,這樣的基本可行解稱為 退化的基本可行解.蠟變黲癟報(bào)倀鉉錨鈰贅。定義12.1.11 :有基變量取0值的基本可行解，稱為退化的基本可行解，它 對(duì)應(yīng)的基B稱為退化的可行基.m個(gè)基變量均取正值的基本可行解，稱為非退化的基本可行解，對(duì)應(yīng)基B稱為非退化的可行基如果一個(gè)線性規(guī)劃問題的所有基本可行解都是非退化的， 則稱這個(gè)線性規(guī)劃問題是非退化

12、的.買鯛鴯譖曇膚遙閆擷凄。由以上定義可知，如果約束問題有m個(gè)基變量，則在退化的基本可行解中， 正分量個(gè)數(shù)一定小于m.在基本可行解中去正值的變量一定是基變量.這樣基本可行解中正分量個(gè)數(shù)也不會(huì)超過m.但是上面的例4已經(jīng)說明，正分量個(gè)數(shù)不超過m可行解不一定是基本可行解，還要看可行解中正分量對(duì)應(yīng)的列向量是否線性無關(guān)而定.綾鏑鯛駕櫬鶘蹤韋轔糴。然而基本可行解中正分量對(duì)應(yīng)的系數(shù)矩陣的列向量一定線性無關(guān).定理設(shè)A是mXn矩陣，秩為 m,對(duì)于Ax=b, x > 0有：(1) 可行解x(x1°,x2°.xn0T是基本可行解的充要條件是Xo的分量x；,x02.xj，對(duì)應(yīng)A中的列向量PjP

13、j2.Pjk線性無關(guān).(2) 如果x=(0,0.0)即x=0是可行解，則它一定是基本可行解.證明：(1)必要性.假定x0是基本可行解，由基本可行解定義可知， x0中的 正分量一定是基變量，基變量對(duì)應(yīng)系數(shù)矩陣 A中的列向量一定在基 B中，則 Pji, Pj2 .pjk線性無關(guān).驅(qū)躓髏彥浹綏譎飴憂錦。充分性.假定x0正分量對(duì)應(yīng)A中的列向量線性無關(guān)，只要證明x0是基本可行 解.因?yàn)榫仃嘇的秩m，貝U k<m ( k是x0的正分量個(gè)數(shù))當(dāng)k=m時(shí)，只要m個(gè)線性無關(guān)的向量構(gòu)成一個(gè)基，而對(duì)應(yīng) x0中的分量xh ,xj2.xjm，取正值的列向量PjPj2. Pjk線性無關(guān).因此也構(gòu)成一個(gè)基，所以x0就

14、 是對(duì)應(yīng)于該基的一個(gè)非退化的基本可行解.當(dāng)k<m時(shí)，因rank(A)=m現(xiàn)在, Pj2 .Pjk線性無關(guān)，可以再從A的其余列中找出適當(dāng)m-k個(gè)向量，不妨設(shè)卩了卩人使P, Pj2.P Pjki.Pjm線性無關(guān)，從而 構(gòu)成A的一個(gè)基，對(duì)應(yīng)x0中的基變量取值為：X； 0.x0k 0,x0 =0.x：m =0貓蠆 驢繪燈鮒誅髏貺廡。因?yàn)橛腥?值的基變量，所以x0是對(duì)應(yīng)于基(PjPj2.Pjk Pjk+.Pjm)的 一個(gè)退化基本可行基解.(2)因?yàn)锳的秩為m ,所以在A中一定存在m個(gè)線性無關(guān)的列向量，將 其構(gòu)成一個(gè)B,對(duì)應(yīng)于可行解x=(0,0，0)T中的基變量取0值，所以可行解 x=0 是對(duì)應(yīng)于基

15、B的退化的基本可行解.鍬籟饗逕瑣筆襖鷗婭薔。根據(jù)這個(gè)定理，基本可行解也可以定義如下：定義:設(shè)A是mKn矩陣，秩為 m,對(duì)于Ax=b, x >0的可行解x, 如果滿足：(1) x的正分量個(gè)數(shù)小于或等于 m(2) x的正分量對(duì)應(yīng) A中的列向量線性無關(guān).則稱x是一個(gè)基本可行解.若x=0是可行解，則定義它是一個(gè)基本可行解.注：定義與定義的等價(jià)性可由定義推出.12.1.4 凸集我們先考察二維平面上直線段上任意一點(diǎn)的表示形式取x.y為平面上兩點(diǎn)，用以原點(diǎn)為起點(diǎn)的向量來表示x和y. 并設(shè)z是線段xy上任意一點(diǎn)，得向量z-y.它與向量x-y平行且方向相同.Hz y|于是有0蘭 !=丸蘭1當(dāng)九=0時(shí)，z=

16、y;人=1時(shí)，z=x構(gòu)氽頑黌碩飩薺齦話騖。k-y|當(dāng)由0連續(xù)變動(dòng)到1時(shí)，點(diǎn)z由y沿此直線連續(xù)的變動(dòng)到x，且因z-y平行 x-y，則有:z-yY.(x-y)于是有：zVx (1-Jy這說明當(dāng)0豈 <1時(shí)， x (1 - )y表示以x, y為端點(diǎn)的直線段上的所有點(diǎn)， 因而它代表以x，y為端點(diǎn)的直線段.一般地，如果x，y是n維歐氏空間Rn中的兩點(diǎn)，則有如下定義：定義12.1.13 :如果x=(X1x2)T,y=(y1yj 是Rn中任意兩點(diǎn)，定義 z = x (1 - )y,C；三 0,1)Z =,Z2,.Zn)T的點(diǎn)所構(gòu)成的集合為以x，y為端點(diǎn)的線段，對(duì)應(yīng)歐0A的點(diǎn)x, y叫做這線段的端點(diǎn)，而

17、對(duì)應(yīng)0；：' ：1的點(diǎn)叫做這線段的內(nèi)點(diǎn).輒嶧陽檉籪癤 網(wǎng)儂號(hào)澩。定義：設(shè)R是Rn中的一個(gè)點(diǎn)集，(即RRn )，對(duì)于任意兩點(diǎn)xR, r R以及滿足0汨的實(shí)數(shù)恒有-x ( )y 則稱R為凸集.堯側(cè)閆繭絳闕絢勵(lì)蜆贅。根據(jù)以上定義及可以看到，凸集的幾何意義是：連接凸集中 任意兩點(diǎn)的直線段仍在此集合內(nèi).識(shí)饒鎂錕縊灩筧嚌儼淒。例如實(shí)心的圓，實(shí)心的矩形，實(shí)心的球體，實(shí)心的長方體等等均是凸集，圓 周不是凸集.直觀地看，凸集是沒有凹入的部分，其內(nèi)部沒有孔洞.凍鈹鋨勞臘錯(cuò)癇婦脛糴。（a）（b）（d）圖 上圖中(a)(b)是凸集，而(c)(d)不是凸集.例12.1.5:集合1x|xi X2-2x3 =5,

18、X，R3是R3中的一個(gè)凸集.(可按定義證明）例 :R =x | 2x!- x2乞 4, -捲x2空 5必 _ 0, x2_ 0, x R3是 R2中的一個(gè)凸集.imax cx例 12.1.7: （LP）問題：的可行域 R .x|Axb,x_0,x R,s.t. Ax 蘭 b,xK0證明：設(shè)x1 R,x2 R由定義知，只要證明x1, x2的任意凸組合X1（1- ）x2R,0 乞 <1 即可.因_ b,x1 _0,Ax2 _b,x2 _0, -0,1】有'x1 （1 -，）x2 _ 0Af. x1 （1 -，）x2 Ax1 （1 -，）Ax2 b （1 -，）b 二 b可見 x1(

19、- )x R故知R是凸集.注：可以用歸納法證明：如果 R是凸集，則R中任意有限個(gè)點(diǎn)的凸組合均 在R中.frm a xx定理: (SLP)問題的可行集R =x| Ax b x 0、s.t ,Ax 蘭 b x A 0是Rn中的一個(gè)凸集.(證明與例相似)恥諤銪滅縈歡煬鞏鶩錦。定義：設(shè)A是m n矩陣，b是m維列向量，集合Rx|Ax",xRn ?如果R不是凸集，則稱R為多面凸集.鯊腎鑰詘漣鉀溈懼統(tǒng)庫。注：此處b的分量可取負(fù)值.一般地，我們可以把任何線性規(guī)劃問題的條件都寫成AX乞b的形式.例如：約束條件為AX二b,X _0寫成：AX 蘭 b，Z A '% _Ax 蘭-b =-Ax<

20、-b、x蘭 0因此，(SLP)問題的可行集是一個(gè)多面凸集.多面凸集可以有界，亦可無界2為 x2乞4|例:將下面的約束條件：x, x 1寫成Axv=b的形式.論 _ 0,x2 _ 0解：上面的約束條件可以轉(zhuǎn)化為:廣21A-11<1:101X2丿03b0其圖如下（1），是一個(gè)二維有界的多面凸集(1)(2)圖 （1 _1f 0、.如上圖例9.AxEb為丙“所確定的是一個(gè)無界的多面凸集（一10八x2丿-1丿（2）12.2線形規(guī)劃的基本定理基本可行解與極點(diǎn)解的等價(jià)性定義：設(shè)集合R Rn為凸集，又設(shè)R但不能為R中其他任意兩點(diǎn) 的凸組合，則稱x為R的極點(diǎn)（或頂點(diǎn)）.例如多邊形，多面體的頂點(diǎn)，圓周上，球

21、面上的頂點(diǎn)等都是頂點(diǎn)上面我們已經(jīng)說（SLP）的可行域是由直線，平面或超平面為邊界構(gòu)成的凸多邊形或凸多面體（亦即多面凸集）因此線形規(guī)劃問題可行域的頂點(diǎn)就是極點(diǎn)碩癘鄴頏謅攆檸攜驤蘞。定理12.2.1 x是線形規(guī)劃（SLP）可行域R的極點(diǎn)的充要條件是x是基本 可行解.證明：必要性.設(shè)x是可行域的極點(diǎn)，要證明x是基本可行解.若x=0是可行 域的極點(diǎn)則x=0是可行解，由上節(jié)定理中（2）即知x是基本可行解周擻 輳嬪諫遷擇植秘騖。若x工0是可行域的極點(diǎn)，設(shè)x的正分量XjMj2$要證明x是基本可行解，由上節(jié)的定理知，只需證明這些數(shù)分量對(duì)應(yīng) A中的列向量pj1pj2卩氷線形無關(guān).氬嚕躑竄貿(mào)懇彈濾頷澩。利用反證法

22、：若Pj1pj2.Pjk線性相關(guān)，則存在不全為0得數(shù)rr2rk使得 APj1 DPj2 . rkPjk =0現(xiàn)在構(gòu)造一個(gè)n維列向量y，它的第j1 j2jk分量分別為r1r2rk，其余分量為0，則有y工0.且Ay= 丫仙-y?Pj2 - yk Pjk =0由于Ty工0. （K i< k）,釷鵒資贏車贖孫滅獅贅。min丿片M式0【可見且x +Ty>0因而x士日y是兩個(gè)可行解.分別記為: iiyilJx，二 x vy R， x = x - 丁y R 有:1 1八 2（xF 2（1»）解x不是可行域的極點(diǎn).則可行域中因v .0.y=0.故x，= X，,x = x，,x = X，取

23、1=-，則x = 'X， (1-%)x，這表明：x可以表示成R中其它點(diǎn)的凸組合.這與x 2是R的極點(diǎn)相矛盾.故必要性得證.慫闡譜鯪逕導(dǎo)嘯畫長涼。充分性：設(shè)x是(SLP)的基本可行解.要證x是可行域的極點(diǎn).若x=0是基 本可行解，而存在可行域中的點(diǎn)，使 x=0能表成：諺辭調(diào)擔(dān)鈧諂動(dòng)禪瀉類。 x1 (')x2，x R，x2 R. “0，11 的形式.即，x1 (1_'；)x2 =0 因此X1 _0，X2 _0_0,1-，0，表明x=0不能表成可行域中兩點(diǎn)的凸組合，因此是極點(diǎn)若x工0是基本可行解.由定理1知，x的正分量Xj1Xj2.Xjk，對(duì)應(yīng)A中列向量Pj1 Pj2pjk線

24、形無關(guān).嘰覲詿縲鐋囁偽純鉿錈。反證法：若基本可行解X不是可行域的極點(diǎn).則可行域中存在異于X的不同 兩點(diǎn)設(shè)為y和乙x 二 y (1 -%)z.(0 ： ：1)或 xyj (1)Zj.(j =1 n)時(shí) x j =0 所以上式變 為：0 二yj （1 J；）Zj 而 0,1； 0,yj -0, Zj -0 故 y二 Zj =0,（j = jjj k）因而y與z是可行解，應(yīng)滿足 熒紿譏鉦鏌觶鷹緇機(jī)庫AYj1Pj1Yj2Pj2Az 二 Zj1Pj1 - Zj2Pj2 .yjk Pik 二 bj 兩式相減得Zjk Pjk二 b山1 一引）Pj（yj2 Zj2）Pj2 . （yjk 一 ZjQ Pjk =

25、0因?yàn)閥與z是不相同的兩點(diǎn)他們的分量至少有一個(gè)不相等.即 比匚一召（=1 k）不全為0因此pj1 sPjk線性相關(guān)這與x是基本可行解相矛盾.故x是基本 可行解.則必為可行域的頂點(diǎn).基本定理定理1222假定線性規(guī)劃（SLP）的A是mx n的矩陣.秩為m,且A的列向量P1P2Pn均不是零向量（1） 若有可行解，則必有基本可行解（即非空可行集R必有極點(diǎn)）（2） 若有最優(yōu)解，則目標(biāo)函數(shù)必定在基本可行解上（極點(diǎn)）達(dá)到極值.（即 若有最優(yōu)解，則必有基本最優(yōu)解）（3）若目標(biāo)函數(shù)在多于一個(gè)極點(diǎn)上達(dá)到最優(yōu)，則必在這些極點(diǎn)的凸組合上 達(dá)到最優(yōu).證明：（1）設(shè)有可行解X0 =（x0，x0,x0）T若x0 =0，則由

26、定理12.1.1 （2）知x0就是基本可行解.若x0工0，不妨設(shè)x0的正分量為前k個(gè).x0 0x2 0.x0 0而x0t=O,£=0，如果正分量對(duì)應(yīng) A中列向量P1P2Pk線性無關(guān)，則由定理12.1.1 （1）知x0就是基本可行解.如果正分量A中的列向量P2Pk線 性相關(guān)，有定理12.1.1 （1）知pp2Pk不是基本可行解.（下面的證明思想就是 構(gòu)造比x0正分量要少的新可行解x1，考慮x1是不是基本可行解.）鶼漬螻偉閱劍鯫腎邏 蘞。由于P1P2Pk線性相關(guān)，于是存在不全為零的數(shù)yk使得% py P 2yk P 不妨設(shè)至少有一個(gè)yi0 （1 i - k ,）否則可取 -P1-y2P2

27、-ykPk =0 構(gòu)造 n 維列向量 y =(y1,y2.yk,0,.0)T ,則知a y1 p< y p 2 yk pk = 因）為存在yi - o（1乞i込k）則可取紂憂蔣氳頑薟驅(qū)藥憫騖。minX。0匚 0(1乞I乞k).Jyi可見x° -陽是可行解.它的第I個(gè)分量x0 - v y0 = 0 ,令X = X - V y = （x - V y| ,.x J - T y|,0, x 1 - V y| 1,xk - V yk 這樣得出一個(gè)正分量是個(gè)數(shù)比x°少的可行解x1，它除了后面的n-k個(gè)分量等于°外，前面k個(gè)分量中的第I個(gè)分量也等于°這樣我們便可

28、以在線性相關(guān)向量組p P2Pk中去掉向量Pi如果剩下的向量線性無關(guān)，由定理（ 1）即知x2x3就是基本可行解.否則再重復(fù)上面的步驟，可以得到可行解它的正分量個(gè) 數(shù)越來越少，經(jīng)過有限步，必然得到一個(gè)可行解.穎芻莖峽餑億頓裊賠瀧。或者XHO則它必為基本可行解（定理 12.1.1 （2）或者xO但其正分量個(gè) 數(shù)或者大于1對(duì)應(yīng)的列向量線性無關(guān).而或者正分量個(gè)數(shù)等于1，這時(shí)對(duì)應(yīng)A中 只有一個(gè)列向量，因?yàn)橐鸭俣?A的列向量不是零向量，而一個(gè)非零向量必然線 性無關(guān).因此不論怎樣x就是基本可行解（定理（ 1）濫驂膽閉驟羥闈詔寢賻。（2 ）設(shè)x° =（X10,x2.xn0）T是（SLP）最優(yōu)解.并設(shè)f

29、*是目標(biāo)函數(shù)最優(yōu)值，即 f* =cx°.現(xiàn)在證明是存在基本可行解x*是最優(yōu)解.如果x° =0，則因x°是最優(yōu)解，首先必須是可行解.因此，x°就是基本可行 解（定理（2），取X* =x°就得到基本最優(yōu)解X*.如果x°=0則x°中必有正 分量不妨設(shè)x0 =（x10,x2,.x0,O.O）T，其中xi0 - 0,1 ： i : k .若正分量對(duì)應(yīng) A中的列向 量 線性無關(guān)，則就是基本可行解（定理（ 1），取x0即得到基本最優(yōu)解x* =X0.若正分量對(duì)應(yīng)A中的列向量p1 p2.pk線性相關(guān)，則存在不全為零的數(shù) ym.yk使 y1Py

30、2P2,. ykp0.構(gòu)造 n維列向量 y 使其第 1,2，k分量分別為 0，而其余分量為0，則有yM 0且Ay = %» + y2 p2十+ ykpk = 0fx00取 min 2乞 yj >0 ,=乞>0（1 蘭I 蘭k）.可見日 >0 且 x+日 y 30.A（x±0y） = b理yjJ yl即x 書和x - vy是兩個(gè)可行解，分別記為 x,及x” .銚銻縵嚌鰻鴻鋟謎諏涼。它們的目標(biāo)函數(shù)值分別為ex，二ex0 cy cX，二oc - cy因?yàn)?x0 是最優(yōu)解，所以：ex0 - ex' - "cy 一 0，ex0 - ex” 7cy

31、一 0又因?yàn)閞 . 0，故cy =0于是有ex，=cx” =cx° ;這表明x,及x”均為最優(yōu)解.又 由日的取法知x0 0|yi|=O,y"O,仁i蘭k當(dāng)yl 0時(shí)X|0 -0，這時(shí)x” = x0 - v y中第I分量等于0，當(dāng)yl : 0時(shí)這時(shí)X|° ：疋 =0中第I分量等于0.所以x；x”至少有一個(gè)的正分量個(gè)數(shù)比x0的 正分量個(gè)數(shù)要少，記這個(gè)解為 x1 .那么x1也是最優(yōu)解.可見，如果x0不是基本最 優(yōu)解，即x0的正分量對(duì)應(yīng)A中的列向量線性相關(guān)，那么總可以令一個(gè)最優(yōu)解x1， 其正分量個(gè)數(shù)比x0正分量個(gè)數(shù)少.如果x1是基本最優(yōu)解，即x1的正分量對(duì)應(yīng)A中 的列向量

32、線性無關(guān)，擠貼綬電麥結(jié)鈺贖嘵類。則取 x* -X1 ,即證明 （2）.如果x1的正分量對(duì)應(yīng)A中的列向量線性相關(guān)，則可重復(fù)上述步驟，得到最 優(yōu)解x2x3xq經(jīng)過有限步必達(dá)到下面的三種情形之一：（i） xq的正分量對(duì)應(yīng) A中的列向量線性無關(guān)，因此xq是基本可行解.取 x* =xq即為基本最優(yōu)解.（ii）xq只有唯一的一個(gè)正分量，因A的列向量均為非零故xq的正分量對(duì)應(yīng) A中的列向量線性無關(guān).同（I） 一樣可知x* =xq即為基本最優(yōu)解.賠荊紳諮侖驟遼輩襪錈。（iii）xq=0這時(shí)xq =0是可行解.由上面的證明已知x二xq =0就是基本最優(yōu) 解.到此，我們證明了定理的第（2）部分.（3）假定目標(biāo)函數(shù)

33、在極點(diǎn)x1x2x3Xs上達(dá)到最優(yōu)值f*又設(shè)它們的任意凸 組合為：ssx 八 伙,' =1,0 一 一1,1 一 i _si =1i =iss而 ex =、' jCxi =、' i f = fi di 1ss- ' 打b = b, x - '" _ 0i 4i 4故知x1x2Xs的凸組合也是目標(biāo)函數(shù)的最優(yōu)值點(diǎn).至此，我們?nèi)孀C明了定理1222.上面，定理,定理是線性規(guī)劃的兩個(gè)很重要的定理.證明了線性 規(guī)劃的基本可行解等同于可行域的頂點(diǎn).并且，如果線性規(guī)劃有最優(yōu)解，則必在 可行域的頂點(diǎn)上達(dá)到最優(yōu).塤礙籟饈決穩(wěn)賽釙冊(cè)庫。這樣，一個(gè)有最優(yōu)解的(SLP )問題，是一定可以從可行域的極點(diǎn)中(即基本可行解中)求得最優(yōu)解的.而基本可行解是對(duì)應(yīng)A中的m個(gè)線性無關(guān)的列向量.A只有n個(gè)列向量.從n 個(gè)列向量中取出 m個(gè)線性無關(guān)向量相成的向量組.其數(shù)目上有限的.因此基本可行解的數(shù)量也是有限的.它不會(huì)超過：cnnn!個(gè) .裊樣祕(mì)廬廂顫諺鍘羋藺。(n m)!