【正文】 ,…,m xj ≥0 j=1,2,…,n j=1 n n j=1 OR1 25 線(xiàn)性規(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 線(xiàn)性規(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ù)的極大化。設(shè)A=B+N ， B是 A中 m?m階非奇異子矩陣，則稱(chēng)B是 LP的一個(gè) 基 ，即： B是 A中 m個(gè)線(xiàn)性無(wú)關(guān)向量組。令所有非基變量等于零 ,則 X=（ x1,x2,…x m,0,…, 0)T稱(chēng)為基解 。 ? 退化的基可行解 ： 若某個(gè)基變量取值為零，則稱(chēng)之為退化的基可行解。 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) 。令 XK≠0 ，其余非基變量保持為零。 這時(shí)原基變量 XL=0，由基變量變成非基變量， a’Lk處在變量轉(zhuǎn)換的交叉點(diǎn)上，稱(chēng)之為樞軸元素 σj ≥ 0 OR1 40 單純形法解題舉例 單純形表的格式： Cj C1 C2 … Cn θi CB XB b x1 x2 …. xn C1 C2 … 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 ? 找到初始可行基，建立單純形表 ? 計(jì)算檢驗(yàn)數(shù)，若所有 σj ≤0 則得最優(yōu)解，結(jié)束。否則轉(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 43 ? ：檢驗(yàn)數(shù)的判別由所有 σj ≤0 即為最優(yōu)，變?yōu)樗?σj ≥ 0則為最優(yōu)。如何截取余料最少？關(guān)鍵：設(shè)變量。已知產(chǎn)品價(jià)格和原料價(jià)格，求利潤(rùn)最大的配方。 OR1 47 應(yīng)用舉例之三 ? 例 茲有 100萬(wàn)元閑錢(qián)，投資方向有四： 第四年 第一年 第二年 第三年 A項(xiàng)目 110% B項(xiàng)目 135% C項(xiàng)目 125% D項(xiàng)目 104% 第五年 各年投資什么項(xiàng)目，使第五年末資本總額為最大？ OR1 48 應(yīng)用舉例之四 ? 例 16動(dòng)態(tài)生產(chǎn)計(jì)劃問(wèn)題 工廠(chǎng)做 n個(gè)月的生產(chǎn)計(jì)劃，第 j月需求量 dj、正常生產(chǎn)能力 aj、加班生產(chǎn)能力 bj、正常生產(chǎn)成本 cj、加班生產(chǎn)成本 ej、庫(kù)存能力為 I、庫(kù)存費(fèi)用hj，設(shè)期初、期末庫(kù)存為零。 設(shè)第月正常生產(chǎn) xj件，加班生產(chǎn)件 yj，存儲(chǔ) zj件。 出租收入不低于生產(chǎn)收入： 9y1+4y2+3y3 ≥70 4y1+5y2+10y3 ≥120 目標(biāo)： ω=360y1+200y2+300y3 出租收入越多越好？至少不低于某數(shù) OR1 52 原問(wèn)題與對(duì)偶問(wèn)題之比較 原問(wèn)題： 對(duì)偶問(wèn)題： maxZ=70X1+120X2 minω=360y1+200y2+300y3 9X1+4X2≤360 9y1+4y2+3y3 ≥70 4X1+5X2 ≤200 () 4y1+5y2+10y3 ≥120 () 3X