【正文】 20 100 σj 3600 34 0 0 0 12 70 1200 X3 X1 X2 84 20 24 0 0 1 1 0 0 0 1 0 σj 4280 0 0 0 OR1 42 ? 找到初始可行基，建立單純形表 ? 計(jì)算檢驗(yàn)數(shù)，若所有 σj ≤0 則得最優(yōu)解，結(jié)束。令所有非基變量等于零 ,則 X=（ x1,x2,…x m,0,…, 0)T稱為基解 。所有約束條件的交集，也就是各半平面的公共部分。飼料 II x2kg。學(xué)生模擬企業(yè)管理系統(tǒng)運(yùn)行。 ?Churchman定義：運(yùn)籌學(xué)是應(yīng)用科學(xué)的方法、技術(shù)和工具，來(lái)處理一個(gè)系統(tǒng)運(yùn)行中的問(wèn)題，使系統(tǒng)控制得到最優(yōu)的解決方法。但定量不可替代定性。 LP有一組有待決策的變量， 一個(gè)線性的目標(biāo)函數(shù)， 一組線性的約束條件 。所有半平面的交集稱之為可行域，可行域內(nèi)的任意一點(diǎn)，就是滿足所有約束條件的解，稱之為可行解。 ? 不等式約束的轉(zhuǎn)化： ∑aijxj≤bi 加入松弛變量 ∑aijxj≥bi 減去剩余變量 ?非正變量：即 xk ≤0 則令 x’k =－ xk 自由變量：即 xk無(wú)約束，令 xk= x’k－ x”k OR1 29 非標(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 30 非標(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 31 ?基的概念 ：如前所述 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。進(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 37 ? ： 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 38 單純形法 一般性表示 ： 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 39 單純形法 ? 若存在 σj ≥ 0，則取 max{σj } = σK ，相應(yīng)之非基變量 XK若取非零，將使 Z增加 ,故令 XK 進(jìn)基。 方案 料型 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 46 應(yīng)用舉例之二 ? 例 14混合配方問(wèn)題 A、 B、 C、 D四種原料配制三種產(chǎn)品，三類約束：技術(shù)要求、原料限量、市場(chǎng)容量。 3y1