【正文】 m x1 x2…xm b 1 b2 … bm a11 a12 … a1n a21 a22 … a2n … … … am1 am2… amn θ1 θ2 … θm σj σ1 σ2 … σn OR1 41 Cj C1 C2 … Cn CB XB b X1 X2 X3 X4 X5 θj 0 0 0 X3 X4 X5 360 200 300 9 4 1 0 0 4 5 0 1 0 3 10 0 0 1 90 40 30 σj 0 70 120 0 0 0 0 0 120 X3 X4 X2 240 50 30 0 1 0 0 0 1 1 0 0 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é)束。 Cmn=10 OR1 35 例題 6 基可行解說(shuō)明 ? 基（ p3,p4,p5） ，令非基變量 x1,x2=0，則基變量 x3=360, x4=200, x5=300, 可行解 ? 基（ p2,p4,p5） ,令非基變量 x1=0,x3=0基變量x2=90,x4=－ 250,x5=－ 600. 非可行解 ? 基（ p2,p3,p4 ），令非基變量 x1,x5=0，則基變量 x2=30, x3=240, x4=50,可行解 （ P21圖） OR1 36 ? 從系數(shù)矩陣中找到一個(gè)可行基 B，不妨設(shè) B由 A的前 m列組成，即 B=(P1,P2,……Pm) 。令所有非基變量等于零 ,則 X=（ x1,x2,?x m,0,?, 0)T稱(chēng)為基解 。如：實(shí)心球、三角形 OR1 22 結(jié)論 ? 可行域是個(gè)凸集 ? 可行域有有限個(gè)頂點(diǎn) ? 最優(yōu)值在可行域的頂點(diǎn)上達(dá)到 ? 無(wú)窮多解的情形 ? 無(wú)界解情形 ? 無(wú)解情形 OR1 23 ? 代數(shù)式 maxZ=c1x1+c2x2+…+c nxn a11x1+a12x2+…+a 1nxn=b1 a21x1+a22x2+…+a 2nxn=b2 … … … am1x1+am2x2+…+a mnxn=bm xj ≥0 j=1,2,…,n OR1 24 線性規(guī)劃的標(biāo)準(zhǔn)型 ? 和式： maxZ=∑cjxj ∑aijxj=bi i=1,2,…,m xj ≥0 j=1,2,…,n j=1 n n j=1 OR1 25 線性規(guī)劃的標(biāo)準(zhǔn)型 ?向量式： maxZ=CX ∑pjxj=bi i=1,2,…,m xj ≥0 j=1,2,…,n C=(c1,c2,c3,…,c n) X=(X1,X2,X3,…,X n) T n j=1 OR1 26 線性規(guī)劃的標(biāo)準(zhǔn)型 ? 矩陣式： maxZ=CX AX=b X ≥0 其中： b=(b1,b2,…,b m)T a11 a12 …. a1n A= a21 a22 … a2n … … … am1 am2 … amn OR1 27 標(biāo)準(zhǔn)型的特征 ? 目標(biāo)函數(shù)極大化 ? 約束條件為等式 ? 決策變量非負(fù) OR1 28 非標(biāo)準(zhǔn)型轉(zhuǎn)化為標(biāo)準(zhǔn)型 ? 目標(biāo)函數(shù)極小化轉(zhuǎn)為極大化： minZ=－ max(－ Z) ，一個(gè)數(shù)的極小化等價(jià)于其相反數(shù)的極大化。所有約束條件的交集，也就是各半平面的公共部分。 9x1+4x2 ≤360 → x 1 ≤360/94/9x2 是直線 x1=360/94/9x2 下方的半平面。飼料 II x2kg。 OR1 11 第二章 線性規(guī)劃與單純形法 ? LP(linear programming)的基本概念 LP是在有限資源的條件下，合理分配和利用資源，以期取得最佳的經(jīng)濟(jì)效益的優(yōu)化方法。學(xué)生模擬企業(yè)管理系統(tǒng)運(yùn)行。管理科學(xué)的發(fā)展，定量越來(lái)越多。 ?Churchman定義：運(yùn)籌學(xué)是應(yīng)用科學(xué)的方法、技術(shù)和工具，來(lái)處理一個(gè)系統(tǒng)運(yùn)行中的問(wèn)題，使系統(tǒng)控制得到最優(yōu)的解決方法。 ?中國(guó)定義：運(yùn)籌學(xué)是應(yīng)用分析、試驗(yàn)、量化的方法，對(duì)經(jīng)濟(jì)管理系統(tǒng)中人力、物力、財(cái)力等資源進(jìn)行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實(shí)現(xiàn)最有效的管理。但定量不可替代定性。 ? 數(shù)學(xué)模型：用符號(hào)或數(shù)學(xué)工具描述現(xiàn)實(shí)系統(tǒng)。 LP有一組有待決策的變量， 一個(gè)線性的目標(biāo)函數(shù)， 一組線性的約束條件 。飼料 III x3kg…… ? 目標(biāo)函數(shù)：最省錢(qián) minZ=2x1+7x2+4x3+9x4+5x5 ? 約束條件： 3x2+2x2+x3+6x4+18x5 ≥700 營(yíng)養(yǎng)要求： x1+++2x4+ ≥30 +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 16 例題 3：人員安排問(wèn)題 ? 醫(yī)院護(hù)士 24小時(shí)值班，每次值班 8小時(shí)。所有半平面的交集稱(chēng)之為可行域，可行域內(nèi)的任意一點(diǎn)，就是滿足所有約束條件的解，稱(chēng)之為可行解。滿足所