【正文】 +x2++2x4+ =200 用量要求： x1 ≤50,x2 ≤60,x3 ≤50,x4 ≤70,x5 ≤40 非負(fù)性要求： x1 ≥0,x2 ≥0,x3 ≥0,x4 ≥0,x5 ≥0 OR1 17 例題 3：人員安排問(wèn)題 ? 醫(yī)院護(hù)士 24小時(shí)值班，每次值班 8小時(shí)。所有半平面的交集稱之為可行域，可行域內(nèi)的任意一點(diǎn)，就是滿足所有約束條件的解，稱之為可行解。滿足所有約束條件的解的集合，稱為可行域。 ? 不等式約束的轉(zhuǎn)化： ∑aijxj≤bi 加入松弛變量 ∑aijxj≥bi 減去剩余變量 ? 非正變量：即 xk ≤0 則令 x’k =－ xk 自由變量：即 xk無(wú)約束，令 xk= x’k－ x”k OR1 30 非標(biāo)準(zhǔn)型轉(zhuǎn)化舉例 之一 maxZ=70X1+120X2 maxZ=70X1+120X2 9X1+4X2≤360 9X1+4X2+X3=360 4X1+5X2 ≤200 4X1+5X2 +x4=200 3X1+10X2 ≤300 3X1+10X2+x5 =300 X1≥0 X2≥0 Xj≥0 j=1,2,…,5 OR1 31 非標(biāo)準(zhǔn)型轉(zhuǎn)化舉例 之二 minZ=x1+2x23x3 maxZ’=x’1－ 2x2+3(x’3－ x”3) x1+x2+x3 ≤9 － x’1+x2+x’3－ x”3 + x4=9 x12x2+x3 ≥2 x’1－ 2x2+x’3 － x”3 x5= 2 3x1+x23x3=5 － 3x’1+x2－ 3(x’3 － x”3 )=5 x1 ≤0 x2 ≥0 x3無(wú)約束 x’1 ≥ 0 x2 ≥0 x’3 ≥0 x”3 ≥0 x4≥0 x5≥0 OR1 32 ?基的概念 ：如前所述 LP標(biāo)準(zhǔn)型 和式： maxZ= ∑cjxj ∑aijxj=bi xj ≥0 j=1,2,…,n 矩陣式： maxZ=CX AX=b X ≥0 約束方程的系數(shù)矩陣 A的秩為 m，且 mn。 OR1 34 基可行解的概念 ? 基可行解： 基解可正可負(fù)，負(fù)則不可行（違背非負(fù)性約束條件），稱滿足所有約束條件的基解為 基可行解。進(jìn)行等價(jià)變換－－約束方程兩端分別左乘 B－ 1 得 X1+ +a’1m+1xm+1+…+ a’1nxn=b’1 x2+ +a’2m+1xm+1+…+ a’2nxn=b’2 …………………………….. xm+a’mm+1xm+1+…+ a’mnxn=b’m 令非基變量為 0，得基可行解 X(0)=(b1’， b2’， ……b m， 0， ……0 ） T z0=∑cibi’ OR1 38 ? ： LP經(jīng)過(guò)若干步迭代，成為如下形式： X1+ +a’1m+1xm+1+…+ a’1nxn=b’1 x1=b’1 ∑ a’1jxj x2+ +a’2m+1xm+1+…+ a’2nxn=b’2 x2=b’2 ∑a’2jxj …………………………….. …………….. xm+a’mm+1xm+1+…+ a’mnxn=b’m xm=b’m ∑a’mjxj OR1 39 單純形法 一般性表示 ： xi=b’i ∑a’ijxj i=1,2,…m 將 xi代入目標(biāo)函數(shù)得 ： Z= ∑ cjxj = ∑ cixi+ ∑ cjxj = ∑ci（ b’i ∑a’ijxj ） + ∑ cjxj = ∑cibi’+ ∑(cj ∑ cia’ij)xj 令： σj= cj ∑ cia’ij z0=∑cibi’ 則 Z=z0+ ∑ σj xj σj判別準(zhǔn)則 ： σj ≤0 時(shí) ,達(dá)到最優(yōu)解 OR1 40 單純形法 ? 若存在 σj ≥ 0，則取 max{σj } = σK ，相應(yīng)之非基變量 XK若取非零，將使 Z增加 ,故令 XK 進(jìn)基。否則轉(zhuǎn)下步 ? 若某 σK ≥ 0而 P’K ≤0 ， 則最優(yōu)解無(wú)界，結(jié)束。 方案 料型 1 2 3 4 5 6 7 8 1 2 0 1 0 1 0 0 0 0 2 2 1 1 3 0 3 1 2 0 3 1 0 4 合計(jì) 殘料 0 OR1 47 應(yīng)用舉例之二 ? 例 14混合配方問(wèn)題 A、 B、 C、 D四種原料配制三種產(chǎn)品，三類約束：技術(shù)要求、原料限量、市場(chǎng)容量。求費(fèi)用最小的生產(chǎn)計(jì)劃。 3y1 +y3=1 x4 ≤ 0。 ? 結(jié)合例題 1講解影子價(jià)格： y1=0:第一種資源過(guò)剩 y2=：設(shè)備臺(tái)時(shí)最緊張，每增加一個(gè)臺(tái)時(shí)， 利潤(rùn)增加。對(duì)偶問(wèn)題最優(yōu)解： Y1=2,Y2=0 ? C1的變化范圍：以 C1代入末表， C1 ≥1 ?右端項(xiàng)變化范圍： xB= B1b ≥0 ? ?b1 ≥6， ?b2≥10