【正文】 i = 1,2,3, …… ,m j = 1,2,3, …… ,n 第三章 線性規(guī)劃模型 j=1 n Xj 的單位貢獻(xiàn) 第 i 資源的約束量 Xj 的技術(shù)性系數(shù)： 表示第 j 種活動消耗資源 i 的數(shù)量 ? 線性規(guī)劃問題的標(biāo)準(zhǔn)形式 目標(biāo)函數(shù)為最大化； 約束條件（非負(fù)條件除外）全為等式； 約束條件右端項(xiàng)為大于等于零； max Z = C1X1+C2X2+…+C nXn . a11X1+a12X2+…+a 1nXn=b1 a21X1+a22X2+…+a 2nXn=b2 …………… am1X1+am2X2+…+a mnXn=bm X1,X2,...,Xn≥0 第三章 線性規(guī)劃模型 ? 將非標(biāo)準(zhǔn)形式轉(zhuǎn)化為標(biāo)準(zhǔn)形式 ? 目標(biāo)函數(shù)為最小化： 令 Z’ = Z , Z’ 為最大化問題。 ? 若約束條件是大于等于型： 在不等式左邊減去一個新變量（剩余變量）， 不等式改為等式，目標(biāo)函數(shù)中新變量系數(shù)為零。 ? 若決策變量 Xk沒有非負(fù)要求： 作 兩個新變量 Xk’≥0, Xk” ≥0,令 Xk＝ Xk’ Xk” ，在原有模型中用（ Xk’ － Xk” ）代替所有的 Xk， 在非負(fù)約束中增加 Xk’≥0和 Xk” ≥0 。x239?！?， x239?！?, 得到以下等價的標(biāo)準(zhǔn)形式 : MAX z’= 2x1 +3x239。39。 +x239。 +2x3 +x4 =3 2x1 +3x239。39。 x239。 +x3 =4 x1, x239。39。每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機(jī)時數(shù)，每件產(chǎn)品可以獲得的利潤以及三種設(shè)備可利用的時數(shù)如下表所示： 用線性規(guī)劃制訂使總利潤最大的生產(chǎn)計(jì)劃。生產(chǎn)一件甲產(chǎn)品可獲利 2元，生產(chǎn)乙產(chǎn)品獲利 3元。設(shè)用 Y1,Y2,Y3分別表示出租單位設(shè)備臺時的租金和出讓原材料 A、 B 的附加值。因此有 Y1+4Y2≥2 。但從接受者來講，支付越少越好。 因此有線性規(guī)劃模型： 目標(biāo)函數(shù)： min W = 8Y1+16Y2+12Y3 Y1+4Y2≥2 2Y1+4Y3≥3 Y1,Y2,Y3≥0 第三章 線性規(guī)劃模型 線性規(guī)劃模型： 目標(biāo)函數(shù)： MAX Z = 2X1+3X2 . X1+2X2≤ 8 4X1 ≤16 4X2≤12 X1, X2≥0 第三章 線性規(guī)劃模型 線性規(guī)劃模型： 目標(biāo)函數(shù)： MIN W = 8Y1+16Y2+12Y3 . Y1+4Y2≥ 2 2Y1 +4Y3≥ 3 Y1, Y2,Y3≥0 最優(yōu)解： X1=4, X2=2, Z=14 最優(yōu)解： Y1=,Y2=, Y3=0,W=14 原問題 對偶問題 ? 對偶問題與影子價格 定義： 設(shè)以下線性規(guī)劃問題 MAX Z = CTX . AX≤b X≤0 為原始問題，則稱以下問題 MIN W = bTY . ATY≤C Y≥0 為原始問題的 對偶問題 ，最優(yōu)值 Y為 影子價格 第三章 線性規(guī)劃模型 第三章 線性規(guī)劃模型對 偶 問 題 對 偶 問 題 第三章 線性規(guī)劃模型 原問題與對偶問題轉(zhuǎn)換： m ax Z = 6x 1 +8x 2 . 3x 1 +x 2 ≥ 4 5x 1 +2x 2 ≤ 7 x 1 ≥ 0 , x 2 ≤ 0 m in Y = 4w 1 +7w 2 . 3w 1 +5w 2 ≥ 6 w 1 +2w 2 ≤ 8 w 1 ≤ 0 , w 2 ≥ 0 ? 對偶問題與原始問題的關(guān)系 第三章 線性規(guī)劃模型 目標(biāo) 極大化問題 Cj（ max Z） 極小化問題 bi（ min W） 目標(biāo) 變 量 n xj≥0 ?—— ? ?aTijyi≥cj 約 束 n xj無約束 ?—— ? ?aTijyi=cj xj≤0 ?—— ? ?aTijyi≤cj 約 束 m ?aijxj≥bi ?—— ? yi≤0 變 量 m ?aijxj=bi ?—— ? yi無約束 ?aijxj≤bi ?—— ? yi≥0 ? 對偶問題的性質(zhì) ? 對偶問題的對偶是原問題。 ? 若 X*,Y*分別是原問題和對偶問題的可行解，則 X*,Y*為最優(yōu)解的充分必要條件是 Y*XL=0和 YSX*=0。因此， 對偶解的經(jīng)濟(jì)含義就是資源的單位改變引起目標(biāo)函數(shù)值的增加量 。 第三章 線性規(guī)劃模型 ? 影子價格的作用：決定企業(yè)的經(jīng)營策略 影子價格真實(shí)地反映了資源在經(jīng)濟(jì)結(jié)構(gòu)中最優(yōu)決策下對總收益的影響和貢獻(xiàn)大小。 影子價格為正數(shù)（非零），該資源約束的松弛變量取值為零（沒有松弛變量） ，因此表明了該資源在最優(yōu)決策下已充分利用耗盡，并成為進(jìn)一步增加總收益的緊缺資源。影子價格為零，表明該資源在最優(yōu)決策下尚有剩余。 當(dāng)?shù)? i 種資源的市場價格低于影子價格時 ， 企業(yè)應(yīng)適量購進(jìn)這種資源 ， 組織和增加生產(chǎn)；相反 ， 當(dāng)市場價格高于影子價格時 ， 可以賣出資源而不安排生產(chǎn)或提高產(chǎn)品的價格 。 第三章 線性規(guī)劃模型 ? 影子價格的作用：決定企業(yè)的經(jīng)營策略 ? 從資源最優(yōu)利用的角度，提出企業(yè)挖潛改革，揚(yáng)長避短的方向。 ? 指導(dǎo)管理部門對緊缺資源進(jìn)行擇優(yōu)分配。 ? 幫助預(yù)測產(chǎn)品的價格。 第三章 線性規(guī)劃模型 第三章 線性規(guī)劃模型 ?例 35: 生產(chǎn)計(jì)劃問題（例 31） 影子價格 最優(yōu)解： x1= x2=1500 x3=0 x4= Z= 每 件 產(chǎn) 品 占 用 的 機(jī) 時 數(shù) （ 小 時 / 件 ） 產(chǎn) 品甲 產(chǎn) 品乙 產(chǎn) 品丙 產(chǎn) 品丁 設(shè) 備 能 力 （ 小 時 ） 設(shè) 備 A 2022 設(shè) 備 B 8000 設(shè) 備 C 5000 利 潤 （ 元 / 件 ） ? 敏感性分析 分析參數(shù)（ A， b， C）的改變對最優(yōu)值的影響，推算出模型的最優(yōu)解對原有模型系數(shù)變化的敏感范圍（最優(yōu)解能夠允許其系數(shù)變化的范圍）。 要保持 E點(diǎn)仍為最優(yōu)解， K必須介于直線 AB 和直線 CD的斜率之間，即 KCD K KAB ② K KCD E → C ③ K KAB E → B K = KCD E → EC K = KAB E → EB X1 X2 B E ① D C ③ ② O KAB A KCD K 敏感性分析－－ 約束方程系數(shù) aij 變化 第三章 線性規(guī)劃模型 X1 X2 B E D C O KC’D A KCD KAB aij的變化，使直線 AB與 CD的斜率發(fā)生變化。 最優(yōu)解的極點(diǎn)變化？ C’