【正文】 到： X*3=0,X*4=0,X*5=0 因此有： 3X1 X2=1 X1+2X2=2 得到： X*1=4/7,X*2=5/7 原問題的解為： X*1=4/7,X*2=5/7,X*3=0 Z*=W*=23/7 第三章 線性規(guī)劃模型 ? 線性規(guī)劃問題的提出 ? 線性規(guī)劃問題的建模 ? 典型特征和基本條件 ? 一般模型和標(biāo)準模型 ? 線性規(guī)劃的圖解方法 ? 影子價格與敏感分析 ? 線性規(guī)劃模型的應(yīng)用 第三章 線性規(guī)劃模型?線性規(guī)劃模型的應(yīng)用 生產(chǎn)計劃問題（教材 P42,實例 ,例 36,7) 項目投資問題（教材 P43,實例 ,例 38) 配料配套問題（教材 P44,實例 ,思考題 ) 合理下料問題（ 例 39) 人力資源問題（例 310） 運輸調(diào)運問題（線性規(guī)劃問題擴展） 任務(wù)指派問題（線性規(guī)劃問題擴展） 第三章 線性規(guī)劃模型 ? 例 36: 生產(chǎn)計劃問題 某車間在每個生產(chǎn)期 5天所需要的每種刀具的統(tǒng)計資料如下： 每一把刀具成本為 ，用過的刀具送到機修車間研磨，每把需花費 。 當(dāng) KCD → KC’D 時： 最優(yōu)值 E → E1’ ； KAB → KA’B 時： 最優(yōu)值 E → E2’ ； 同時變化時： 最優(yōu)值 E → E3’ E1’ KA’B E3’ E2’ 最優(yōu)解的極點不變， 但坐標(biāo)變化， Z值變。 目標(biāo)函數(shù)的變化 所需資源的變化 資源消耗的變化 決策變量的變化 第三章 線性規(guī)劃模型 敏感性分析－－ 目標(biāo)函數(shù)的變化 第三章 線性規(guī)劃模型 ① Cj的變化影響到目標(biāo)函數(shù)直線斜率 K的變化。買方要購入賣方的產(chǎn)品作為資源投入生產(chǎn)，要求其價格必須小于該產(chǎn)品作為自己最優(yōu)生產(chǎn)的影子價格，賣方要求出售其產(chǎn)品的價格必須大于自己的生產(chǎn)成本，因此，產(chǎn)品的價格應(yīng)在雙方的成本和影子價格之間。 ? 資源影子價格的高低作為同類企業(yè)經(jīng)濟效益的評價指標(biāo)之一。剩余資源也是進一步發(fā)展生產(chǎn)的潛在優(yōu)勢。 在完全的市場條件下 ， 隨著資源的買進和賣出 ， 影子價格隨之 變 化 ， 直 到 影 子 價 格 與 市 場 價 格 保持同等水平。 第三章 線性規(guī)劃模型 ? 影子價格的作用：決定企業(yè)的經(jīng)營策略 影子價格也是機會成本 。影子價格越高，表明該種資源越緊缺。影子價格越高，表明該種資源的貢獻越大。 定量表達了在最優(yōu)生產(chǎn)方案下對單位第 i 種資源的一種估價 ，這種估價不是該種資源的市場價格 ， 而是在最優(yōu)生產(chǎn)方案下的一種虛擬價格 ， 故稱其為影 子 價 格 （ s h a d o w p r i c e ) 。 第三章 線性規(guī)劃模型 原問題標(biāo)準型： Max Z= CX AX + XL= b X,XL≥0 對偶問題標(biāo)準型： Min W= Yb YA YS= C Y,YS≥0 Y i* 0 可以推出 x n + i* = 0 ； x n+i*0 可以推出 Y i* = 0 ； Y m+j*0 可以推出 x j* = 0 ； x j* 0 可以推出 Y m+j*= 0 第三章 線性規(guī)劃模型 ? 對偶問題的性質(zhì)（續(xù)） ? 原問題和對偶問題的互補松松弛關(guān)系 第三章 線性規(guī)劃模型 例 34: 根據(jù)對偶原理求解以下線性規(guī)劃問題 ： min z= 6x 1 +8x 2 +3x 3 . x 1 +x 2 ≥ 1 x 1 +2x 2 +x 3 ≥ 1 x 1 , x 2 , x 3 ≥ 0 ? 作業(yè) ： 運用對偶原理求以下原問題的最優(yōu)解： 目標(biāo)函數(shù)： MIN Z = 2X1+3X2+X3 ： 3X1 X2+ X3≥1 X1+2X23X3≥2 X1,X2,X3≥0 第三章 線性規(guī)劃模型 第三章 線性規(guī)劃模型 ? 對偶問題解的經(jīng)濟解釋－－影子價格 根據(jù)對偶問題的性質(zhì)有： Z* = W* = ∑bi yi* 兩邊對 bi求偏導(dǎo)數(shù)得到： ? Z* = yi* (i= 1,2, …,m) ? bi 即 yi* 表示每增加一個單位 bi 后 Z* 的增量 第三章 線性規(guī)劃模型m i=1 ? 對偶問題解的經(jīng)濟解釋－－影子價格 bi 在原問題中是約束條件的右端項，表明了第 i 種資源的可用量。 ? 若兩個互為對偶問題之一有最優(yōu)解，則另一個必有最優(yōu)解，且目標(biāo)函數(shù)值相等 (Z*=W*)，最優(yōu)解滿足 CX*=Y*b。為提高競爭力，因此工廠只能在滿足 ≥所有產(chǎn)品的利潤條件，使其總收入具有競爭力的，因此， W需要求解最小值。 同樣地乙產(chǎn)品也有： 2Y1+4Y3≥3 第三章 線性規(guī)劃模型 ? 對偶問題的提出 全部出讓或出租的總收入為 W = 8Y1+16Y2+12Y3 從決策者來看，當(dāng)然希望 W值越大越好。作如下比較，用一個單位設(shè)備臺時和四個單位的原材料可以生產(chǎn)甲產(chǎn)品一件，獲利 2元，那么出租和出讓的收益不應(yīng)低于自己生產(chǎn)時的收益。問在 以 下條件下如何安排生產(chǎn)？ 甲 乙 總量 設(shè)備臺時 原材料 A 原材料 B 1 4 0 2 0 4 8 16 12 ? 對偶問題的提出 建立線性規(guī)劃模型： 目標(biāo)函數(shù)： MAX Z = 2X1+3X2 約束條件： X1+2X2≤ 8 4X1+ ≤16 4X2≤12 X1, X2≥0 從另一角度考慮： 如果該廠決定不生產(chǎn)甲、乙兩種產(chǎn)品，而將其資源出租或出售，這時工廠的決策者就要考慮給每種資源如何定價的問題。 每件產(chǎn)品占用的 機時數(shù)（小時 / 件） 產(chǎn)品甲 產(chǎn)品乙 產(chǎn)品丙 產(chǎn)品丁 設(shè)備能力 （小時） 設(shè)備 A 1 .5 1 .0 2 .4 1 .0 2 0 0 0 設(shè)備 B 1 .0 5 .0 1 .0 3 .5 8 0 0 0 設(shè)備 C 1 .5 3 .0 3 .5 1 .0 5 0 0 0 利潤 （元 / 件） 5 .24 7 .30 8 .34 4 .18 第三章 線性規(guī)劃模型 ? 線性規(guī)劃問題的提出 ? 線性規(guī)劃問題的建模 ? 典型特征和基本條件 ? 一般模型和標(biāo)準模型 ? 線性規(guī)劃的圖解方法 ? 影子價格與敏感分析 ? 線性規(guī)劃模型的應(yīng)用 第三章 線性規(guī)劃模型第三章 線性規(guī)劃模型 某廠生產(chǎn)甲、乙兩種產(chǎn)品，消耗 A、 B兩種原材料 。, x3, x4, x5 ≥0 第三章 線性規(guī)劃模型 ? 兩個變量的線性規(guī)劃問題的幾何解釋 例 33: z=0 z=3 z=6 z=9 z=12 z= 0 1 2 3 4 5 6 8 7 6 5 4 3 2 1 6 5 4 3 2 1 x1 x2 目標(biāo)函數(shù)等值線 Z = X1+3X2 可行域 (4/3,14/3) Max z = X1+3X2 . X1+ X2≤6 X1+2X2≤8 X1 , X2≥0 ? 線性規(guī)劃的可行域及最優(yōu)解的性質(zhì) ? 若線性規(guī)劃的可行域非空，則可行域必為凸集 ? 若線性規(guī)劃有最優(yōu)解，則最優(yōu)解至少在一個極點上 第三章