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