第二章最優(yōu)化線性規(guī)劃詳解演示文稿

第二章最優(yōu)化線性規(guī)劃詳解演示文稿當(dāng)前1頁(yè)，總共165頁(yè)。優(yōu)選第二章最優(yōu)化線性規(guī)劃當(dāng)前2頁(yè)，總共165頁(yè)。凸集設(shè)集合D

Rn,若對(duì)于任意點(diǎn)x,y∈

D,及實(shí)數(shù)a,0≤a≤1,都有ax+(1-a)y∈

D,則稱集合D為凸集.常見的凸集:單點(diǎn)集{x},空集,整個(gè)歐式空間Rn,超平面H={x∈

Rn|a1x1+a2x2+…anxn=b}，半空間H+={x∈Rn|a1x1+a2x2+…anxn≥b}，實(shí)心圓，實(shí)心球，實(shí)心長(zhǎng)方體等都是凸集。3當(dāng)前3頁(yè)，總共165頁(yè)。凸集從直觀上看，沒有凹入部分，或沒有空洞的是凸集。幾何解釋為：集合D中任兩點(diǎn)連線上的每一點(diǎn)仍在D中，則D為凸集。4當(dāng)前4頁(yè)，總共165頁(yè)。凸集的例超球||x||≤r為凸集證明設(shè)x,y為超球中任意兩點(diǎn),0≤a≤1,則有||ax+(1-a)y||≤a||x||+(1-a)||y||≤a

r+(1-a)r=r,即點(diǎn)ax+(1-a)y屬于超球,所以超球?yàn)橥辜?5當(dāng)前5頁(yè)，總共165頁(yè)。凸集的性質(zhì)(i)有限個(gè)(可以改成無(wú)限)凸集的交集為凸集.即:若Dj(j∈

J)是凸集,則它們的交集D={x|x∈

Dj,j∈J}是凸集.(ii)設(shè)D是凸集,b是一實(shí)數(shù),則下面集合是凸集bD={y|y=bx,x∈

D}.6當(dāng)前6頁(yè)，總共165頁(yè)。凸集的性質(zhì)(iii)設(shè)D1,D2是凸集,則D1與D2的和集D1+D2={y|y=x+z,x∈

D1,z∈D2}是凸集.注:和集與并集有很大的區(qū)別,凸集的并集未必是凸集,而凸集的和集是凸集.例:D1={(x,0)T|x∈

R}表示x軸上的點(diǎn),D2={(0,y)T|y∈R},表示y軸上的點(diǎn).則D1∪D2表示兩個(gè)軸的所有點(diǎn),它不是凸集;D1+D2=R2是凸集7當(dāng)前7頁(yè)，總共165頁(yè)。推論凸集的線性組合是凸集.定義2.1.2設(shè)xi∈

Rn,i=1,…,k,實(shí)數(shù)li≥0,則稱為x1,x2,…,xk的凸組合.容易證明:凸集中任意有限個(gè)點(diǎn)的凸組合仍然在該凸集中.兩點(diǎn)的凸組合三點(diǎn)的凸組合多點(diǎn)的凸組合8當(dāng)前8頁(yè)，總共165頁(yè)。極點(diǎn)設(shè)D為凸集,x∈D.若D中不存在兩個(gè)相異的點(diǎn)y,z及某一實(shí)數(shù)a∈(0,1)使得

x=ay+(1-a)z

則稱x為D的極點(diǎn).凸集極點(diǎn)凸集極點(diǎn)9當(dāng)前9頁(yè)，總共165頁(yè)。極點(diǎn)例D={x∈Rn|||x||≤a}(a>0),則||x||=a上的點(diǎn)均為極點(diǎn)證明:設(shè)||x||=a,若存在y,z∈D及a∈(0,1),使得x=ay+(1-a)z.則a2=||x||2≤a2||y||2+(1-a)2||z||2+2a(1-a)||y||||z||≤a2不等式取等號(hào),必須||y||=||z||=a,容易證明y=z=x,根據(jù)定義可知,x為極點(diǎn).10當(dāng)前10頁(yè)，總共165頁(yè)。凸函數(shù)設(shè)函數(shù)f(x)定義在凸集DRn上,若對(duì)任意的x,y∈D,及任意的a∈

[0,1]都有

f(ax+(1-a)y)≤af(x)+(1-a)f(y)

則稱函數(shù)f(x)為凸集D上的凸函數(shù).11當(dāng)前11頁(yè)，總共165頁(yè)。凸函數(shù)設(shè)函數(shù)f(x)定義在凸集DRn上,若對(duì)任意的x,y∈D,x≠y,及任意的a∈(0,1)都有

f(ax+(1-a)y)<af(x)+(1-a)f(y)

則稱函數(shù)f(x)為凸集D上的嚴(yán)格凸函數(shù).將上述定義中的不等式反向,可以得到凹函數(shù)和嚴(yán)格凹函數(shù)的定義.12當(dāng)前12頁(yè)，總共165頁(yè)。凸函數(shù)的例設(shè)f(x)=(x–1)2,試證明f(x)在(–∞,+∞)上是嚴(yán)格凸函數(shù).證明:設(shè)x,y∈R,且x≠y,a∈(0,1)都有f(ax+(1-a)y)-(af(x)+(1-a)f(y))

=(ax+(1-a)y-1)2-a(x-1)2-(1-a)(y-1)2=–a(1-a)(x-y)2<0因此f(x)在(–∞,+∞)上是嚴(yán)格凸函數(shù).13當(dāng)前13頁(yè)，總共165頁(yè)。凸函數(shù)的幾何性質(zhì)對(duì)一元函數(shù)f(x),在幾何上af(x1)+(1-a)f(x2)

(0≤a≤1)表示連接(x1,f(x1)),(x2,f(x2))的線段,f(ax1+(1-a)x2)表示在點(diǎn)ax1+(1-a)x2處的函數(shù)值,所以一元凸函數(shù)表示連接函數(shù)圖形上任意兩點(diǎn)的線段總是位于曲線弧的上方.對(duì)于一元凸函數(shù)f(x),可以發(fā)現(xiàn),位于函數(shù)曲線上方的圖形是凸集.事實(shí)上這一結(jié)論對(duì)于多元函數(shù)也是成立的,而且是充要條件,即有下面的定理.14當(dāng)前14頁(yè)，總共165頁(yè)。凸函數(shù)的性質(zhì)(i)設(shè)f(x)是凸集DRn上的凸函數(shù),實(shí)數(shù)k≥0,則kf(x)也是D上的凸函數(shù).(ii)設(shè)f1(x),f2(x)是凸集DRn上的凸函數(shù),實(shí)數(shù)l,m≥0,則lf1(x)+mf2(x)也是D上的凸函數(shù).(iii)設(shè)f(x)是凸集DRn上的凸函數(shù),b為實(shí)數(shù),則水平集S(f,b)={x|x∈D,f(x)≤b}是凸集.下面的圖形給出了凸函數(shù)f(x,y)=x4+3x2+y4+y2+xy的等值線(f(x,y)=2,4,6,8,10,12)的圖形.可以看出水平集為凸集.15當(dāng)前15頁(yè)，總共165頁(yè)。凸函數(shù)的性質(zhì)16當(dāng)前16頁(yè)，總共165頁(yè)。凸函數(shù)的判斷設(shè)f(x)定義在凸集DRn上,x,y∈D.令F(t)=f(tx+(1-t)y),t∈[0,1],則該定理的幾何意義是:凸函數(shù)上任意兩點(diǎn)之間的部分是一段向下凸的弧線.(i)f(x)是凸集D上的凸函數(shù)的充要條件是對(duì)任意的x,y∈D,一元函數(shù)F(t)為[0,1]上的凸函數(shù).(ii)f(x)是凸集D上的嚴(yán)格凸函數(shù)的充要條件是對(duì)任意的x,y∈D(x≠y),一元函數(shù)F(t)為[0,1]上的嚴(yán)格凸函數(shù).17當(dāng)前17頁(yè)，總共165頁(yè)。凸函數(shù)的判斷18當(dāng)前18頁(yè)，總共165頁(yè)。一階條件

(一階條件)設(shè)在凸集DRn上f(x)可微,則f(x)在D上為凸函數(shù)的充要條件是對(duì)任意的x,y∈D,都有f(y)≥f(x)+f(x)T(y-x)定理2.1.3(一階條件)設(shè)在凸集DRn上f(x)可微,則f(x)在D上為嚴(yán)格凸函數(shù)的充要條件是對(duì)任意的x,y∈D,x≠y,都有f(y)>f(x)+f(x)T(y-x)19當(dāng)前19頁(yè)，總共165頁(yè)。二階條件設(shè)在開凸集DRn上f(x)可微,則(i)f(x)是D內(nèi)的凸函數(shù)的充要條件為,在D內(nèi)任一點(diǎn)x處,f(x)的Hesse矩陣G(x)半正定,其中(ii)若在D內(nèi)G(x)正定,則f(x)在D內(nèi)是嚴(yán)格凸函數(shù).20當(dāng)前20頁(yè)，總共165頁(yè)。凸規(guī)劃設(shè)DRn為凸集,則f(x)為D上的凸函數(shù),則稱規(guī)劃問(wèn)題

minf(x)

s.t.x∈D

為凸規(guī)劃問(wèn)題.(i)凸規(guī)劃的任一局部極小點(diǎn)x是整體極小點(diǎn),全體極小點(diǎn)組成凸集.(ii)若f(x)是DRn上的嚴(yán)格凸函數(shù),且凸規(guī)劃問(wèn)題minf(x)s.t.x∈D的整體極小點(diǎn)存在,則整體極小點(diǎn)唯一.21當(dāng)前21頁(yè)，總共165頁(yè)。§2.2線性規(guī)劃的標(biāo)準(zhǔn)型

與基本概念22當(dāng)前22頁(yè)，總共165頁(yè)。線性規(guī)劃的一般形式min(max)c1x1+c2x2+···+cnxns.t.a11x1+a12x2+···+a1nxn≥(或≤,=)b1a21x1+a22x2+···+a2nxn(或≤,=)b2······am1x1+am2x2+···+amnxn(或≤,=)bmx1,x2,···,xn≥023當(dāng)前23頁(yè)，總共165頁(yè)。線性規(guī)劃的標(biāo)準(zhǔn)型minc1x1+c2x2+···+cnxns.t.a11x1+a12x2+···+a1nxn=b1a21x1+a22x2+···+a2nxn=b2······am1x1+am2x2+···+amnxn=bmx1,x2,···,xn≥0其中bi≥0.在標(biāo)準(zhǔn)形式中目標(biāo)函數(shù)一律改為最大化或最小化，此處我們統(tǒng)一為最小化，約束條件（非負(fù)約束條件除外）一律化成等式，且要求其右端項(xiàng)大于等于零。24當(dāng)前24頁(yè)，總共165頁(yè)。矩陣-向量形式的標(biāo)準(zhǔn)型mincTx(LP)s.t.Ax=bx≥0其中c=(c1,c2,···,cn)T,x=(x1,x2,···,xn)T,b=(b1,b2,···,bm)Tc:價(jià)格向量A:約束矩陣b:右端向量25當(dāng)前25頁(yè)，總共165頁(yè)。矩陣-向量形式的標(biāo)準(zhǔn)型記A=(p1,p2,···,pn),其中pj=(a1j,a2j,···,amj)T,線性規(guī)劃(LP)又可以表示為26當(dāng)前26頁(yè)，總共165頁(yè)。線性規(guī)劃解的情況滿足約束條件的向量x是可行解,全體可行解構(gòu)成可行域D.D≠F

時(shí)但目標(biāo)函數(shù)無(wú)下界時(shí),稱線性規(guī)劃(LP)無(wú)界或無(wú)最優(yōu)解;D=F

時(shí),稱線性規(guī)劃無(wú)可行解;D≠F

時(shí)若目標(biāo)函數(shù)有下界,可以證明線性規(guī)劃(LP)必有最優(yōu)解.27當(dāng)前27頁(yè)，總共165頁(yè)?？尚杏?yàn)橥辜€性規(guī)劃問(wèn)題mincTx(LP)s.t.Ax=bx≥0的可行域D為凸集.證明任取x,y∈D,則有Ax=b,x≥0,Ay=b,y≥0對(duì)任意的a∈[0,1],設(shè)z=ax+(1-a)y,則z≥0,且Az=A(ax+(1-a)y)=aAx+(1-a)Ay=ab+(1-a)b=b因此z∈DD為凸集.28當(dāng)前28頁(yè)，總共165頁(yè)。一般形式轉(zhuǎn)化為標(biāo)準(zhǔn)型(i)極大極小

maxf(x)min–f(x)(ii)若約束條件是小于等于型，則在該約束條件不等式左邊加上一個(gè)新變量——稱為松弛變量，將不等式改為等式。如(iii)若約束條件是大于等于型，則在該約束條件不等式左邊減去一個(gè)新變量——稱為剩余變量，將不等式改為等式。如29當(dāng)前29頁(yè)，總共165頁(yè)。一般形式轉(zhuǎn)化為標(biāo)準(zhǔn)型(iv)若某個(gè)約束方程右端項(xiàng)，則在約束方程兩端乘以（-1），不等號(hào)改變方向，然后再將不等式化為等式。(v)若變量xj無(wú)非負(fù)約束，則引入非負(fù)變量xj’≥0,xj’’≥0,令xj=xj’-xj”.30當(dāng)前30頁(yè)，總共165頁(yè)。例將線性規(guī)劃miny=2x1-x2-3x3s.t.x1+x2+x3≤7x1-x2+x3≥2-3x1-x2+2x3=5x1,x2≥0,x3是自由變量化為標(biāo)準(zhǔn)型解:令x3=x3’-x3’’,得到標(biāo)準(zhǔn)型miny=2x1-x2-3x3’+3x3’’s.t.x1+x2+x3’-x3’’+x4=7x1-x2+x3’-x3’’-x5=2-3x1-x2+2x3’-2x3’’=5x1,x2,x3’,x3’’,x4,x5≥031當(dāng)前31頁(yè)，總共165頁(yè)。例將線性規(guī)劃maxy=250x1+350x2s.t.5x1+6x2≥2508x1+6x2≤

30010x1+20x2=-700x1≥0,x2≤

0化為標(biāo)準(zhǔn)型解:令x2’=-x2,得到標(biāo)準(zhǔn)型min-y=-250x1+350x2’s.t.5x1-6x2’

-x3=2508x1-6x2’+x4=

300-10x1+20x2’=700x1≥0,x2’≥0,x3≥0,

x4≥032當(dāng)前32頁(yè)，總共165頁(yè)?；靖拍钤O(shè)約束矩陣A的秩為m(行滿秩),且m≤n,則A中必存在m階非奇異子陣B,不妨設(shè)B=(p1,p2,···,pm)稱B為線性規(guī)劃問(wèn)題(LP)的一個(gè)基矩陣,或稱為基,基矩陣中的列向量稱為基向量,對(duì)應(yīng)的決策變量稱為基變量,其余變量稱為非基變量.33當(dāng)前33頁(yè)，總共165頁(yè)?；靖拍钤诩s束方程組取定基矩陣B=(p1,p2,···,pm)之后,令非基變量均為0,得到的方程組p1x1+p2x2+···+pmxm=b有唯一解,這樣得到約束方程組的一個(gè)解向量x=(x1,x2,···xm)T通過(guò)這種方法得到的滿足約束方程組的解稱為基矩陣B對(duì)應(yīng)的基解.34當(dāng)前34頁(yè)，總共165頁(yè)?；靖拍钊绻庥譂M足非負(fù)條件,則稱之為基可行解.此時(shí)的基B稱為可行基.基可行解中非零分量的個(gè)數(shù)不會(huì)超過(guò)m,若基可行解中非零分量的個(gè)數(shù)恰為m,稱此基可行解為非退化的基可行解,否則稱為退化的基可行解.若一個(gè)線性規(guī)劃的所有基可行解都是非退化的,稱此線性規(guī)劃是非退化的.線性規(guī)劃(LP)的基解個(gè)數(shù)不會(huì)超過(guò)35當(dāng)前35頁(yè)，總共165頁(yè)。例考慮線性規(guī)劃min2x1-x2

s.t.x1+x2+x3=5

-x1-x2+x4=0

2x1+2x2+x5=22

x1,x2,x3,x4,x5≥0該線性規(guī)劃有5個(gè)變量,3個(gè)約束,最多個(gè)基解.事實(shí)上,該線性規(guī)劃只有7個(gè)基解(p1,p2線性相關(guān))下面列出7個(gè)基解及對(duì)應(yīng)的基(p1,p3,p4),(11,0,-6,11,0)T不可行(p1,p3,p5),(0,0,5,0,22)T退化(p1,p4,p5),(5,0,0,5,12)T非退化(p2,p3,p4),(0,11,-6,11,0)T不可行(p2,p3,p5),(0,0,5,0,22)T退化(p2,p4,p5),(0,5,0,5,12)T非退化(p3,p4,p5),(0,0,5,0,22)T退化36當(dāng)前36頁(yè)，總共165頁(yè)。§2.3線性規(guī)劃的

基本定理37當(dāng)前37頁(yè)，總共165頁(yè)。本節(jié)的基本定理要說(shuō)明要找線性規(guī)劃的最優(yōu)解只需在基可行解中選擇就可以了,這樣將選擇的范圍控制在有限個(gè).設(shè)x是標(biāo)準(zhǔn)型線性規(guī)劃(LP)的可行解,x為(LP)的基可行解的充要條件是,x的正分量對(duì)應(yīng)的系數(shù)列向量線性無(wú)關(guān).38當(dāng)前38頁(yè)，總共165頁(yè)。設(shè)x是標(biāo)準(zhǔn)型線性規(guī)劃(LP)的可行解,x為(LP)的基可行解的充要條件是,x為可行域D的極點(diǎn).證明:

必要性不妨設(shè)x=(x1,x2,···,xm,0,···,0)T是(LP)的基可行解,且x1,x2,···,xm是基變量,假設(shè)有u,v∈D,0<a<1,使得x=au+(1-a)v當(dāng)m+1≤j≤n時(shí),0=xj=auj+(1-a)vj,因此uj=vj=0.所以p1u1+p2u2+···+pmum=p1v1+p2v2+···+pmvm=b從而p1(u1-v1)+p2(u2-v2)+···+pm(um-vm)=0由于x是基可行解,所以p1,p2,···,pm線性無(wú)關(guān),uj=vj(i=1,2,···,m).從而u=v.這說(shuō)明x為極點(diǎn).39當(dāng)前39頁(yè)，總共165頁(yè)。充分性設(shè)x=(x1,x2,···,xk,0,···,0)T是可行域的極點(diǎn),其中x1,x2,···,xk>0.假設(shè)x不是基可行解,于是p1,p2,···,pk線性相關(guān),即有一組不全為0的數(shù)a1,a2,···,ak,使得a1p1+a2p2+···+akpk=0 (2.4)又x∈D,所以x1p1+x2p2+···+xkpk=b(2.5)用e>0乘(2.4)再與(2.5)相加減得(x1+ea1)p1+(x2+ea2)p2+···+(xk+eak)pk=b(x1–ea1)p1+(x2–ea2)p2+···+(xk–eak)pk=b40當(dāng)前40頁(yè)，總共165頁(yè)。令u=(x1+ea1,x2+ea2,···,xk+eak,0,···,0)Tv=(x1–ea1,x2–ea2,···,xk–eak,0,···,0)T則有Au=b,Av=b,當(dāng)e充分小時(shí),可使u≥0,v≥0.因此,當(dāng)e充分小時(shí),u,v都是(LP)的可行解,且u≠v,x=1/2u+1/2v,這與x是D的極點(diǎn)相矛盾.因此x是基可行解.推論:線性規(guī)劃(LP)的可行域D={x|Ax=b,x≥0}最多具有有限個(gè)極點(diǎn)41當(dāng)前41頁(yè)，總共165頁(yè)。(p1,p3,p4),(11,0,-6,11,0)T不可行(p1,p3,p5),(0,0,5,0,22)T退化(p1,p4,p5),(5,0,0,5,12)T非退化(p2,p3,p4),(0,11,-6,11,0)T不可行(p2,p3,p5),(0,0,5,0,22)T退化(p2,p4,p5),(0,5,0,5,12)T非退化(p3,p4,p5),(0,0,5,0,22)T退化前例中三個(gè)退化的基可行解對(duì)應(yīng)著同一個(gè)極點(diǎn)(基可行解與極點(diǎn)不是一一對(duì)應(yīng))42當(dāng)前42頁(yè)，總共165頁(yè)。有可行解有基可行解若線性規(guī)劃(LP)存在可行解,則它一定存在基可行解.43當(dāng)前43頁(yè)，總共165頁(yè)。有最優(yōu)解有最優(yōu)的基可行解若線性規(guī)劃(LP)存在最優(yōu)解,則必存在基可行解是最優(yōu)解.44當(dāng)前44頁(yè)，總共165頁(yè)。單純形方法的思路找出一基可行解(極點(diǎn))若其不是最優(yōu),找到一個(gè)相鄰極點(diǎn)新的目標(biāo)函數(shù)值不大于原目標(biāo)函數(shù)值經(jīng)過(guò)有限次迭代給出最優(yōu)解或判斷無(wú)最優(yōu)解45當(dāng)前45頁(yè)，總共165頁(yè)。單純形方法的思路(幾何)線性規(guī)劃min-72x1-64x2

s.t.x1+x2+x3=50

12x1+8x2+x4=490

3x1

+x5=100

x1,x2,x3,x4,x5≥0的等價(jià)形式為min-72x1-64x2

s.t.x1+x2≤50

12x1+8x2≤490

3x1≤100

x1,x2≥046當(dāng)前46頁(yè)，總共165頁(yè)。OABCD梯度方向x2=0x1=0x5=0x3=0x4=0等值線基可行解O47當(dāng)前47頁(yè)，總共165頁(yè)。OABCDx2=0x1=0x5=0x3=0x4=0基可行解A48當(dāng)前48頁(yè)，總共165頁(yè)。OABCDx2=0x1=0x5=0x3=0x4=0基可行解B49當(dāng)前49頁(yè)，總共165頁(yè)。OABCDx2=0x1=0x5=0x3=0x4=0基可行解C是最優(yōu)解50當(dāng)前50頁(yè)，總共165頁(yè)。單純形方法的思路(代數(shù))例考察線性規(guī)劃min-72x1-64x2

s.t.x1+x2+x3=50

12x1+8x2+x4=490

3x1

+x5=100

x1,x2,x3,x4,x5≥0以x3,x4,x5為基變量,容易得到基可行解(0,0,50,490,100)T.由于x1的價(jià)格系數(shù)為負(fù)數(shù),增加x1的取值可以使得目標(biāo)函數(shù)值減少.類似的,我們也可以增加x2的取值,使得目標(biāo)函數(shù)值減少.由于-72負(fù)得多一些,我們先增加x1.51當(dāng)前51頁(yè)，總共165頁(yè)。單純形方法的思路(代數(shù))min-72x1-64x2

s.t.x1+x2+x3=50

12x1+8x2+x4=490

3x1

+x5=100

x1,x2,x3,x4,x5≥0x1可以增加多少?x1≤50x1≤490/12x1≤100/3因此x1的最大取值為min(50,490/12,100/3)=100/3此時(shí)x5的取值為0,x5“出基”.52當(dāng)前52頁(yè)，總共165頁(yè)。單純形方法的思路(代數(shù))根據(jù)3x1+x5=100,我們將原來(lái)的線性規(guī)劃改寫如下min-64x2+24x5-2400s.t.x2+x3-x5/3=50/3

8x2+x4-4x5=90

x1

+x5/3=100/3

x1,x2,x3,x4,x5≥0此時(shí),基變量為x1,x3,x4,基可行解為(100/3,0,50/3,90,0)T.若x2(其系數(shù)為負(fù))的取值增加,可以使得目標(biāo)函數(shù)值減少x2≤50/3x2≤90/8因此x2的最大取值為min(50/3,90/8)=90/8x4“出基”.53當(dāng)前53頁(yè)，總共165頁(yè)。單純形方法的思路(代數(shù))此時(shí),x4,x5是非基變量,將原規(guī)劃化為min8x4-8x5-3120s.t.x3-x4/8+x5/6=65/12

x2+x4/8-x5/2

=45/4

x1

+x5/3=100/3

x1,x2,x3,x4,x5≥0解為(100/3,45/4,65/12,0,0)T.x5最大可以取為65/2.對(duì)應(yīng)的,線性規(guī)劃可以轉(zhuǎn)化為下頁(yè)的形式54當(dāng)前54頁(yè)，總共165頁(yè)。單純形方法的思路(代數(shù))min48x3+2x4-3380s.t.6x3-3x4/4+x5=65/2

x2+3x3-x4/4

=55/2

x1-2x3+x4/4=45/2

x1,x2,x3,x4,x5≥0對(duì)應(yīng)的解為(45/2,55/2,0,0,65/2)T.此時(shí),目標(biāo)函數(shù)中非基變量的系數(shù)為正,因此目標(biāo)函數(shù)的取值不能再減少.最優(yōu)值為

-3380.55當(dāng)前55頁(yè)，總共165頁(yè)。單純形方法的思路(代數(shù))單純形方法求解線性規(guī)劃,首先找出一個(gè)基可行解.將目標(biāo)函數(shù)寫成非基變量的線性組合(再加上一個(gè)常數(shù))的形式.如果組合的系數(shù)全部非負(fù),則已經(jīng)找到最優(yōu)解.如果組合的系數(shù)中有負(fù)數(shù),從中選取一個(gè)變量(“進(jìn)基”)來(lái)增加取值,可以使得函數(shù)值減少.根據(jù)約束條件,可以控制增加的范圍.在進(jìn)基變量取最大值時(shí),有一個(gè)變量出基,從而得到另一個(gè)基可行解.重復(fù)上面的過(guò)程,可以求得最優(yōu)解.56當(dāng)前56頁(yè)，總共165頁(yè)?！?.4單純形方法57當(dāng)前57頁(yè)，總共165頁(yè)。設(shè)線性規(guī)劃R(A)=m，x1,x2,…,xm是基變量，而xm+1,…,xn是非基變量，并記基矩陣B=(p1,p2,…,pm),N=(pm+1,…,pn),A=(B,N),則上述線性規(guī)劃問(wèn)題化為58當(dāng)前58頁(yè)，總共165頁(yè)。進(jìn)一步可以將線性規(guī)劃問(wèn)題轉(zhuǎn)化為以下形式59當(dāng)前59頁(yè)，總共165頁(yè)。規(guī)范式線性規(guī)劃與基變量x1,···,xm對(duì)應(yīng)的規(guī)范式線性規(guī)劃與基變量xj1,···,xjm對(duì)應(yīng)的規(guī)范式S={j1,···,jm},

T={1,2,···,n}\S60當(dāng)前60頁(yè)，總共165頁(yè)。2.4.1基可行解是最優(yōu)解的判斷準(zhǔn)則在規(guī)范式中,令非基變量xj=0,j∈T,得到一個(gè)基解x0=(x1,···,xn)T,其中如果b’j≥0(j∈S),則x0是基可行解.61當(dāng)前61頁(yè)，總共165頁(yè)。最優(yōu)性條件目標(biāo)函數(shù)中各個(gè)變量的系數(shù)就是判別數(shù).在規(guī)范式中,設(shè)x0是線性規(guī)劃(LP)對(duì)應(yīng)于基B=(pj1,···,pjm)的基可行解.與基變量xj1,···,xjm對(duì)應(yīng)的規(guī)范式中,若x0的全體判別數(shù)非負(fù),則x0是(LP)的最優(yōu)解.62當(dāng)前62頁(yè)，總共165頁(yè)。判斷無(wú)最優(yōu)解設(shè)x0是線性規(guī)劃(LP)對(duì)應(yīng)于基B=(p1,···,pm)的基可行解.與基變量x1,···,xm對(duì)應(yīng)的規(guī)范式中,若存在sk<0,且對(duì)所有的i=1,2,···,m有aik’≤0,則線性規(guī)劃(LP)無(wú)最優(yōu)解.63當(dāng)前63頁(yè)，總共165頁(yè)?；尚薪獾霓D(zhuǎn)換從上面定理可以看出,如果某個(gè)判別數(shù)為負(fù)時(shí),可以構(gòu)造新的可行解,使得目標(biāo)函數(shù)值減少.1.確定進(jìn)基變量負(fù)的判別數(shù)對(duì)應(yīng)的變量都可以作為進(jìn)基變量.一般的,若sk=min{sj|sj<0}則以xk為進(jìn)基變量.64當(dāng)前64頁(yè)，總共165頁(yè)?；尚薪獾霓D(zhuǎn)換2.確定離基變量(采用最小比值準(zhǔn)則)設(shè)已確定xk為進(jìn)基變量,根據(jù)min{qi=b’i/a’ik|a’ik>0}=b’l/a’lk=ql,則稱第l行為主行，與主行所對(duì)應(yīng)的基變量xl為離基變量.65當(dāng)前65頁(yè)，總共165頁(yè)。單純形方法如果線性規(guī)劃是非退化的,則按照上面的方法(進(jìn)基,離基)迭代一次后,目標(biāo)函數(shù)值有所下降.經(jīng)過(guò)有限次迭代之后,一定可以得到一個(gè)基可行解,使得其所有判別數(shù)非負(fù)(得到最優(yōu)解),或者其有一個(gè)判別數(shù)是負(fù)的,但對(duì)應(yīng)列向量的所有分量非正(線性規(guī)劃無(wú)最優(yōu)解).這種求解線性規(guī)劃的方法稱為單純形方法.66當(dāng)前66頁(yè)，總共165頁(yè)。§2.5單純形表67當(dāng)前67頁(yè)，總共165頁(yè)。建立實(shí)用單純形表以下是初始單純形表：

68當(dāng)前68頁(yè)，總共165頁(yè)。用單純形法解線性規(guī)劃minf=–2x1–3x2s.t.x1+x2≤6x1+2x2≤8x1≤4x2≤3x1,x2≥0解引入松弛變量將原問(wèn)題化為標(biāo)準(zhǔn)型minf=–2x1–3x2s.t.x1+x2+x3=6x1+2x2+x4=8x1+x5=4x2+x6=3x1,x2,x3,x4,x5,x6≥069當(dāng)前69頁(yè)，總共165頁(yè)。顯然p3,p4,p5,p6是一組基,標(biāo)準(zhǔn)型線性規(guī)劃中的系數(shù)以及這一組基可用表格的形式給出minf=-2x1-3x2s.t.x1+x2+x3=6x1+2x2+x4=8x1+x5=4x2+x6=3x1,x2,x3,x4,x5,x6≥0目標(biāo)函數(shù)中的系數(shù)基向量基變量的價(jià)格系數(shù)右端系數(shù)約束等式的系數(shù)cj-2-30000

p1

p2

p3

p4

p5

p6Bp3p4p5p6cB0000b684311100012010010001001000170當(dāng)前70頁(yè)，總共165頁(yè)。第一步的判別數(shù):由于在此例中基變量的價(jià)格系數(shù)均為0,所以判別數(shù)就是價(jià)格系數(shù).cj-2-30000cBBbp1p2p3p4p5p60000p3p4p5p66843111000120100100010010001sj

-2-30000進(jìn)基變量:s2=-3=min{sj|sj<0},所以x2為進(jìn)基變量離基變量的判別標(biāo)準(zhǔn):qi=bi/ai2(ai2>0)qi64/3離基變量:q6

=minqi,所以x6為離基變量()-33標(biāo)出主元71當(dāng)前71頁(yè)，總共165頁(yè)。第二步迭代過(guò)程cj-2-30000qicBBbp1p2p3p4p5p60000p3p4p5p668431110001201001000100(1)000164/3sj-2-30000p3p4p5p2寫出基向量(p6換成p2)歸一化:若主元不等于1,則進(jìn)行行變換,將主元變?yōu)?(此處不變)3010001寫出價(jià)格系數(shù)000-3消去:用初等行變換將主元所在列其它元素消為0p5所在行不變4100010p2所在行乘以-1加到p3所在行310100-1p2所在行乘以-2加到p4所在行210010-2p2所在行乘以3加到判別數(shù)所在行

sj-20000372當(dāng)前72頁(yè)，總共165頁(yè)。第二步迭代過(guò)程cj-2-30000qicBBbp1p2p3p4p5p60000p3p4p5p668431110001201001000100(1)000164/3sj-2-30000p3p4p5p23010001000-34100010310100-1210010-2

sj-20000373當(dāng)前73頁(yè)，總共165頁(yè)。cj-2-30000cBBbp1p2p3p4p5p6000-3p3p4p5p2324310100-110010-2100010010001sj

-200003進(jìn)基變量:s1=-2=min{sj|sj<0},所以x1為進(jìn)基變量離基變量的判別標(biāo)準(zhǔn):qi=bi/ai1(ai1>0)qi324/離基變量:q4=2=minqi,x4為離基變量()-22標(biāo)出主元74當(dāng)前74頁(yè)，總共165頁(yè)。第三步迭代過(guò)程cj-2-30000qicBBbp1p2p3p4p5p6000-3p3p4p5p2324310100-1(1)0010-2100010010001324/sj-200003p3p1p5p2寫出基向量(p4換成p1)歸一化:若主元不等于1,則進(jìn)行行變換,將主元變?yōu)?(此處不變)3010001寫出價(jià)格系數(shù)0-20-3消去:用初等行變換將主元所在列其它元素消為0p2所在行不變2000-112p1所在行乘以-1加到p3所在行1001-101p1所在行乘以-1加到p5所在行210010-2p1所在行乘以2加到判別數(shù)所在行

sj00020-175當(dāng)前75頁(yè)，總共165頁(yè)。第三步迭代過(guò)程cj-2-30000qicBBbp1p2p3p4p5p6000-3p3p4p5p2324310100-1(1)0010-2100010010001324/sj-200003p3p1p5p230100010-20-32000-1121001-101210010-2

sj00020-176當(dāng)前76頁(yè)，總共165頁(yè)。cj-2-30000cBBbp1p2p3p4p5p60-20-3p3p1p5p21223001-10110010-2000-112010001sj

00020-1進(jìn)基變量:s6=–1=min{sj|sj<0},所以x6為進(jìn)基變量離基變量的判別標(biāo)準(zhǔn):qi=bi/ai6(ai6>0)qi1/13離基變量:q5=1=minqi,x5為離基變量(此處可選x3)()-11標(biāo)出主元77當(dāng)前77頁(yè)，總共165頁(yè)。第四步迭代過(guò)程cj-2-30000qicBBbp1p2p3p4p5p60-20-3p3p1p5p21223001-10110010-2000-11(2)0100011/13sj00020-1p3p1p6p2寫出基向量(p5換成p6)歸一化:若主元不等于1,則進(jìn)行行變換,將主元變?yōu)?(此處除以2)2010?-?0寫出價(jià)格系數(shù)0-20-3消去:用初等行變換將主元所在列其它元素消為01000-??1p6所在行乘以-1加到p3所在行0001-?-?0p6所在行乘以2加到p1所在行4100010p6所在行乘以1加到判別數(shù)所在行

sj0003/2?0p6所在行乘以-1加到p2所在行78當(dāng)前78頁(yè)，總共165頁(yè)。第四步迭代過(guò)程cj-2-30000qicBBbp1p2p3p4p5p60-20-3p3p1p5p21223001-10110010-2000-11(2)0100011/13sj00020-1p3p1p6p22010?-?00-20-31000-??10001-?-?04100010

sj0003/2?079當(dāng)前79頁(yè)，總共165頁(yè)。cj-2-30000cBBbp1p2p3p4p5p60-20-3p3p1p6p20412001-1/2-1/20100010000-1/21/210101/2-1/20sj

0003/21/20此時(shí)所有的判別數(shù)都非負(fù),迭代終止.最優(yōu)解為x*=(4,2,0,0,0,1)T,原問(wèn)題的最優(yōu)解為x*=(4,2)T,最優(yōu)值為f*=(-2)·4+(-3)·2=-14.80當(dāng)前80頁(yè)，總共165頁(yè)?！?.6初始基可行解的求法81當(dāng)前81頁(yè)，總共165頁(yè)。對(duì)于線性規(guī)劃問(wèn)題mincTxs.t.Ax≤b(b≥0)x≥0引入松弛變量化為標(biāo)準(zhǔn)型mincTxs.t.Ax+IxS=bx,xS≥0其中I是單位矩陣,xS=(xn+1,···,xn+m)T.則可以將xS作為基變量,以(0,···,0,b1,···,bm)T為初始基可行解進(jìn)行單純形迭代.對(duì)于一般的線性規(guī)劃問(wèn)題,無(wú)法簡(jiǎn)單給出初始基可行解.82當(dāng)前82頁(yè)，總共165頁(yè)。為了使初始可行基成為一個(gè)單位矩陣，在有些約束條件中需要加入人工變量，但加入人工變量后的數(shù)學(xué)模型與未加入人工變量的數(shù)學(xué)模型一般是不等價(jià)的。在這一點(diǎn)上，人工變量與松弛變量或剩余變量是不同的，松弛變量或剩余變量只是將不等式改寫為等式，而改寫前后，兩個(gè)約束是等價(jià)的。83當(dāng)前83頁(yè)，總共165頁(yè)。2.6.1大M單純形法對(duì)于線性規(guī)劃問(wèn)題引入人工變量xn+1,···,xn+m,構(gòu)造輔助線性規(guī)劃問(wèn)題84當(dāng)前84頁(yè)，總共165頁(yè)。M是相當(dāng)大的正數(shù)(可以理解為正無(wú)窮),對(duì)人工變量起到懲罰的作用,逼迫輔助線性規(guī)劃的最優(yōu)解中人工變量均為0.

上述輔助線性規(guī)劃模型與原規(guī)劃模型一般是不等價(jià)的，只有當(dāng)最優(yōu)解中，人工變量都取零值時(shí)，才可認(rèn)為兩個(gè)問(wèn)題的最優(yōu)解是相當(dāng)?shù)?。關(guān)于這一點(diǎn)有以下的結(jié)論：（1）輔助線性規(guī)劃問(wèn)題的最優(yōu)解中，人工變量都處在非基變量位置（即取零值），則原問(wèn)題有最優(yōu)解，且將前者最優(yōu)解中去掉人工變量部分即為后者最優(yōu)解。85當(dāng)前85頁(yè)，總共165頁(yè)。（2）若輔助線性規(guī)劃問(wèn)題的最優(yōu)解中包含非零的人工變量，則原問(wèn)題無(wú)可行解。（3）若輔助線性規(guī)劃問(wèn)題的最優(yōu)解的基變量中包含人工變量，但該人工變量取值為0，這時(shí)可將某個(gè)非基變量引入基變量中來(lái)替換該人工變量，從而得到原問(wèn)題的最優(yōu)解。

86當(dāng)前86頁(yè)，總共165頁(yè)。大M方法算例例2.6.1用大M單純形法求解線性規(guī)劃minf(x)=-3x1+x2+x3s.t.x1-2x2+x3≤11-4x1+x2+2x3-x4=3-2x1+x3=1x1,x2,x3,x4≥0引入松弛變量x5,人工變量x6,x7,構(gòu)造輔助線性規(guī)劃min–3x1+x2+x3+Mx6+Mx7s.t.x1-2x2+x3+x5=11–4x1+x2+2x3-x4+x6=3–2x1+x3+x7=1x1,···,x7≥0注:根據(jù)線性規(guī)劃問(wèn)題本身的形式,可以少引進(jìn)一些人工變量.87當(dāng)前87頁(yè)，總共165頁(yè)。單純形方法求解第一步的判別數(shù):s1=-3-1·0-(-4)M-(-2)M=6M-3類似地可以給出其它各個(gè)判別數(shù).cj-31100M

McBBbp1p2p3p4p5p6p70MMp5p6p711311-210100-412-1010-20

10001sj

6M-3-M+1-3M+1

M000qi113/2

1x3進(jìn)基,x7離基,標(biāo)出主元.()注:人工變量一旦離基,則在迭代時(shí)不再參與計(jì)算.88當(dāng)前88頁(yè)，總共165頁(yè)。續(xù)表cj-31100M

McBBbp1p2p3p4p5p6p70MMp5p6p711311-210100-412-1010-20(1)0001sj6M-3-M+1-3M+1M0000M1p5p6p310113-20010010-101-20

1000sj-1-M+10M0089當(dāng)前89頁(yè)，總共165頁(yè)。0M1p5p6p310113-200100(1)0-101-20

1000/1/sj-1-M+10M00011p5p2p31211(3)00-21010-10-20

1004//sj-10010-311p1p2p3419100-2/31/3010-1000

1-4/32/3sj0001/31/390當(dāng)前90頁(yè)，總共165頁(yè)。求得輔助規(guī)劃問(wèn)題的最優(yōu)解為(4,1,9,0,0,0,0)T,原線性規(guī)劃的最優(yōu)解為(4,1,9,0)T,最優(yōu)值為

-3·4+1·3+1·9=-2.注:根據(jù)各個(gè)判別數(shù),可以發(fā)現(xiàn)M應(yīng)滿足–3M+1<–M+1,–3M+1<6M–3,–M+1<–1即M>2.在實(shí)際問(wèn)題中可以取M為適當(dāng)大的一個(gè)數(shù),比如比問(wèn)題中的系數(shù)大一個(gè)數(shù)量級(jí).91當(dāng)前91頁(yè)，總共165頁(yè)。2.6.2兩階段單純形法對(duì)于線性規(guī)劃問(wèn)題引入人工變量xn+1,···,xn+m,構(gòu)造輔助線性規(guī)劃問(wèn)題92當(dāng)前92頁(yè)，總共165頁(yè)。將上述輔助線性規(guī)劃問(wèn)題拆成兩個(gè)線性規(guī)劃，即為兩階段法。第1階段求解第1個(gè)線性規(guī)劃，第1個(gè)線性規(guī)劃的目標(biāo)函數(shù)是對(duì)所有人工變量之和求最小。（1）若求得的最優(yōu)解中，所有人工變量都處在非基變量的位置，即，則從第1階段的最優(yōu)解中去掉人工變量后，即為原問(wèn)題的一個(gè)基本可行解，作為原問(wèn)題的一個(gè)初始基本可行解，再求解原問(wèn)題，從而進(jìn)入第2階段。93當(dāng)前93頁(yè)，總共165頁(yè)。（2）假若求得第1階段的最優(yōu)解中，至少有一個(gè)人工變量不為零值，則說(shuō)明添加人工變量之前的原問(wèn)題無(wú)可行解，不再需要進(jìn)入第2階段。因此兩階段法的第1階段求解，有兩個(gè)目的：一為判斷原問(wèn)題有無(wú)可行解；二，若有，則可求得原問(wèn)題的一個(gè)初始基本可行解，再對(duì)原問(wèn)題進(jìn)行第2階段的計(jì)算。94當(dāng)前94頁(yè)，總共165頁(yè)。兩階段法算例用兩階段法求解線性規(guī)劃

min4x1+x2+x3

s.t.2x1+x2+2x3=4

3x1+3x2+x3=3

x1,x2,x3≥0解,引入人工變量,構(gòu)造輔助線性規(guī)劃:

minx4+x5

s.t.2x1+x2+2x3+x4=4

3x1+3x2+x3+x5=3

x1,x2,x3,x4,x5≥095當(dāng)前95頁(yè)，總共165頁(yè)。單純形表cj00011qicBBbp1p2p3p4p511p4p54321210(3)310121sj-5-4-30010p4p1210-1(4/3)1111/303/23sj01-4/3000p3p13/21/20-3/4115/40sj00096當(dāng)前96頁(yè)，總共165頁(yè)。單純形表cj00011qicBBbp1p2p3p4p511p4p54321210(3)310021sj-5-4-30010p4p1210-1(4/3)1111/303/23sj01-4/3000p3p13/21/20-3/4115/40sj000最優(yōu)解(1/2,0,3/20,0)T,最優(yōu)值w*=0,由此得到原線性規(guī)劃的一個(gè)基可行解x0=(1/2,0,3/2)T.將上表的最后部分轉(zhuǎn)到新的單純形表中(求解原線性規(guī)劃),不過(guò)判別數(shù)要重新計(jì)算.97當(dāng)前97頁(yè)，總共165頁(yè)。求解原線性規(guī)劃的單純形表得到原線性規(guī)劃的最優(yōu)解x*=

(0,2/5,9/5)T,最優(yōu)值f*=11/5.cj411qicBBbp1p2p314p3p13/21/20-3/411(5/4)0/2/5sj0-13/4011p3p29/52/53/5014/510sj13/50098當(dāng)前98頁(yè)，總共165頁(yè)?！?.7線性規(guī)劃的

對(duì)偶理論99當(dāng)前99頁(yè)，總共165頁(yè)。假設(shè)某工廠有m種設(shè)備:B1,B2,···,Bm.一年內(nèi)各設(shè)備的生產(chǎn)能力(有效臺(tái)時(shí)數(shù))為b1,b2,···,bm.利用這些設(shè)備可以加工n種產(chǎn)品:A1,A2,···,An,單位產(chǎn)品的利潤(rùn)分別為c1,c2,···,cn.第j種產(chǎn)品需要在第i種設(shè)備上加工的臺(tái)時(shí)數(shù)為aij.問(wèn)在設(shè)備能力允許的條件下怎樣安排生產(chǎn)計(jì)劃,使全年總收入最多?設(shè)x1,x2,···,xn為各產(chǎn)品的計(jì)劃年產(chǎn)量,s為全年總收入,易建立該問(wèn)題的數(shù)學(xué)模型.100當(dāng)前100頁(yè)，總共165頁(yè)。假設(shè)某工廠有m種設(shè)備:B1,B2,···,Bm.一年內(nèi)各設(shè)備的生產(chǎn)能力(有效臺(tái)時(shí)數(shù))為b1,b2,···,bm.利用這些設(shè)備可以加工n種產(chǎn)品:A1,A2,···,An,單位產(chǎn)品的利潤(rùn)分別為c1,c2,···,cn.第j種產(chǎn)品需要在第i種設(shè)備上加工的臺(tái)時(shí)數(shù)為aij.問(wèn)在設(shè)備能力允許的條件下怎樣安排生產(chǎn)計(jì)劃,使全年總收入最多?設(shè)x1,x2,···,xn為各產(chǎn)品的計(jì)劃年產(chǎn)量,s為全年總收入,易建立該問(wèn)題的數(shù)學(xué)模型.101當(dāng)前101頁(yè)，總共165頁(yè)。對(duì)偶問(wèn)題假設(shè)工廠將所有的設(shè)備用于出租,需要給各種設(shè)備制定出租價(jià)格.定價(jià)原則有兩條:一是出租后得到的單位利潤(rùn)不得少于直接生產(chǎn)時(shí)的收入,二是出租價(jià)格盡量的低,以利于市場(chǎng)競(jìng)爭(zhēng).設(shè)第i種設(shè)備Bi的單位臺(tái)時(shí)的出租價(jià)格為yi,全年總收入為w,則該問(wèn)題的數(shù)學(xué)模型為102當(dāng)前102頁(yè)，總共165頁(yè)。對(duì)偶問(wèn)題假設(shè)工廠將所有的設(shè)備用于出租,需要給各種設(shè)備制定出租價(jià)格.定價(jià)原則有兩條:一是出租后得到的單位利潤(rùn)不得少于直接生產(chǎn)時(shí)的收入,二是出租價(jià)格盡量的低,以利于市場(chǎng)競(jìng)爭(zhēng).設(shè)第i種設(shè)備Bi的單位臺(tái)時(shí)的出租價(jià)格為yi,全年總收入為w,則該問(wèn)題的數(shù)學(xué)模型為103當(dāng)前103頁(yè)，總共165頁(yè)?？梢钥闯?原始規(guī)劃與對(duì)偶規(guī)劃是同一組數(shù)據(jù)參數(shù),只是位置有所不同,所描述的問(wèn)題實(shí)際上是同一個(gè)問(wèn)題從另一種角度去描述.原始線性規(guī)劃對(duì)偶線性規(guī)劃104當(dāng)前104頁(yè)，總共165頁(yè)。對(duì)稱形勢(shì)下對(duì)偶問(wèn)題的一般形式定義2.7.1滿足下列條件的線性規(guī)劃問(wèn)題稱為具有對(duì)稱形式：其變量均具有非負(fù)約束，其約束條件當(dāng)目標(biāo)函數(shù)求極大時(shí)取“≤”號(hào)，當(dāng)目標(biāo)函數(shù)求極小時(shí)均取“≥”號(hào)。105當(dāng)前105頁(yè)，總共165頁(yè)。對(duì)稱形勢(shì)下對(duì)偶問(wèn)題的一般形式原始線性規(guī)劃mincTx(LP)