【正文】 題不標(biāo)準(zhǔn) ?例題 2 max ω=7y1+4y22y3 minZ=3x1+2x26x3+x5 2y1+ y2 y3 ≤3 2x1+x24x3+x4+3x5 ≥7 y1 +3y3 ≤2 x1+ 2x3 x4 ≤ 4 4y1+ 2y2 ≤6 x1+3x2 x4+ x5 =2 y1 y2 y3 ≥ 0 x1， x2， x3 ≥0。 設(shè)第月正常生產(chǎn) xj件，加班生產(chǎn)件 yj，存儲(chǔ) zj件。 OR1 48 應(yīng)用舉例之三 ? 例 茲有 100萬元閑錢，投資方向有四： 第四年 第一年 第二年 第三年 A項(xiàng)目 110% B項(xiàng)目 135% C項(xiàng)目 125% D項(xiàng)目 104% 第五年 各年投資什么項(xiàng)目，使第五年末資本總額為最大？ OR1 49 應(yīng)用舉例之四 ? 例 16動(dòng)態(tài)生產(chǎn)計(jì)劃問題 工廠做 n個(gè)月的生產(chǎn)計(jì)劃，第 j月需求量 dj、正常生產(chǎn)能力 aj、加班生產(chǎn)能力 bj、正常生產(chǎn)成本 cj、加班生產(chǎn)成本 ej、庫存能力為 I、庫存費(fèi)用hj，設(shè)期初、期末庫存為零。已知產(chǎn)品價(jià)格和原料價(jià)格，求利潤(rùn)最大的配方。如何截取余料最少？關(guān)鍵：設(shè)變量。否則轉(zhuǎn)下步 ? 根據(jù) max {σj } = σK 原則確定 XK 進(jìn)基變量；根據(jù) θ規(guī)則 ： θ = min {b’i / a’ik a’ik 0} = b’L/ a’Lk 確定 XL為出基變量 ? 以 a’Lk 為樞軸元素進(jìn)行迭代，回到第二步 OR1 44 ? ：檢驗(yàn)數(shù)的判別由所有 σj ≤0 即為最優(yōu)，變?yōu)樗?σj ≥ 0則為最優(yōu)。 這時(shí)原基變量 XL=0，由基變量變成非基變量， a’Lk處在變量轉(zhuǎn)換的交叉點(diǎn)上，稱之為樞軸元素 σj ≥0OR1 41 單純形法解題舉例 單純形表的格式： Cj C1 C2 … C n θi CB XB b x1 x2 …. xn C1 C2 … Cm x1 x2…xm b 1 b2 … bm a11 a12 … a 1n a21 a22 … a 2n … … … am1 am2… a mn θ1 θ2 … θm σj σ1 σ2 … σ n OR1 42 Cj C1 C2 … C n 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 43 ? 找到初始可行基，建立單純形表 ? 計(jì)算檢驗(yàn)數(shù)，若所有 σj ≤0 則得最優(yōu)解，結(jié)束。令 XK≠0 ，其余非基變量保持為零。 Cmn=10 OR1 36 例題 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 37 ? 從系數(shù)矩陣中找到一個(gè)可行基 B，不妨設(shè) B由 A的前 m列組成，即 B=(P1,P2,……Pm) 。 ? 退化的基可行解 ： 若某個(gè)基變量取值為零，則稱之為退化的基可行解。令所有非基變量等于零 ,則 X=（ x1,x2,… xm,0,… ,0)T稱為基解 。設(shè)A=B+N ， B是 A中 m?m階非奇異子矩陣，則稱B是 LP的一個(gè) 基 ，即： B是 A中 m個(gè)線性無關(guān)向量組。如：實(shí)心球、三角形 OR1 23 結(jié)論 ? 可行域是個(gè)凸集 ? 可行域有有限個(gè)頂點(diǎn) ? 最優(yōu)值在可行域的頂點(diǎn)上達(dá)到 ? 無窮多解的情形 ? 無界解情形 ? 無解情形 OR1 24 ? 代數(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 25 線性規(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 26 線性規(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=