運籌學(xué)中線性規(guī)劃圖解法動態(tài)演示實用教案

1、會計學(xué)1運籌學(xué)中線性規(guī)劃運籌學(xué)中線性規(guī)劃(xin xn u hu)圖圖解法動態(tài)演示解法動態(tài)演示第一頁，共57頁。甲電纜乙電纜資源量銅（噸）2110鉛（噸）118價格（萬元）64另外，市場對乙電纜的最大需求量為7單位，而對甲乙電纜的需求量無限制。問該工廠(gngchng)應(yīng)如何安排生產(chǎn)才能使工廠(gngchng)的總收入最大？第1頁/共57頁第二頁，共57頁。2146maxxxz101221 xx821xx0,21xxs.t.72xObject：解：設(shè)x1，x2分別代表甲乙兩種電纜的生產(chǎn)量，z代表工廠的總收入，則上述問題可用如下(rxi)數(shù)學(xué)模型來表示：第2頁/共57頁第三頁，共57頁。目標函數(shù)

2、中的變量系數(shù)用目標函數(shù)中的變量系數(shù)用Cj表示表示,Cj稱為價稱為價值系數(shù)值系數(shù);約束條件的變量系數(shù)用約束條件的變量系數(shù)用aij表示表示,aij稱為工藝系數(shù)稱為工藝系數(shù);約束條件右端的常數(shù)約束條件右端的常數(shù)(chngsh)用用bi表示表示,bj稱為資源限量稱為資源限量(系系數(shù)數(shù))2146maxxxz101221 xx821xx0,21xx約束條件(subject to)72x目標(mbio)Object：指出(zh ch)模型中的可行解第3頁/共57頁第四頁，共57頁?；靖拍罨靖拍?1、什么、什么(shn me)是可行解是可行解?2、什么、什么(shn me)是最優(yōu)解是最優(yōu)解?第4頁/共57

3、頁第五頁，共57頁。1、圖解法；、圖解法；2、單純形法（時代標志、單純形法（時代標志(biozh)）；）；3、計算機軟件求解。、計算機軟件求解。第5頁/共57頁第六頁，共57頁。第6頁/共57頁第七頁，共57頁。x1x207條件條件(tiojin)(tiojin)約約束圖示束圖示: :第7頁/共57頁第八頁，共57頁。x1x25100788圖示圖示: :101221 xx821xx0,21xxs.t.72x可行域第8頁/共57頁第九頁，共57頁。x1x25100788可行域最優(yōu)解101221 xx821xx0,21xxs.t.72x第9頁/共57頁第十頁，共57頁。x1x2目標(mbio)函數(shù)

4、等值線可行域最優(yōu)解66-84第10頁/共57頁第十一頁，共57頁。圖解法例3：x1x22004000250300最優(yōu)解300（z=27500=50 x1+100 x2) X1=50,x2=25050第11頁/共57頁第十二頁，共57頁。Global optimal solution found. Objective value: 9.857143 Total solver iterations: 2 Variable Value Reduced Cost X1 1.714286 0.000000 X2 2.142857 0.000000 Row Slack or Surplus Dual Pr

5、ice 1 9.857143 1.000000 2 0.000000 1.285714 3 0.000000 0.1428571第12頁/共57頁第十三頁，共57頁。LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 9.857142 VARIABLE VALUE REDUCED COST X1 1.714286 0.000000 X2 2.142857 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 1.285714 3) 0.000000 0.142857 NO. ITER

6、ATIONS= 2 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 2.000000 3.000000 0.500000 X2 3.000000 1.000000 1.800000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 6.000000 4.000000 3.000000 3

7、15.000000 14.999999 6.000000第13頁/共57頁第十四頁，共57頁。約束條件資源量使用量剩余數(shù)量銅（噸）10100鉛（噸）880市場量761 在線性規(guī)劃中，對于一個約束條件中沒有使用的資源(zyun)或能力的大小稱之為松馳量。在不等式中添加一個變量Si ，則原約束條件變?yōu)椋呵蠼?qi ji)結(jié)果：X1=2，X2=6，第14頁/共57頁第十五頁，共57頁。1012121sxx8221sxx0,21xxs.t.732 sx3212100046maxsssxxz目標(mbio)函數(shù)：第15頁/共57頁第十六頁，共57頁。1012121sxx8221sxx0,21xxs.t.

8、732 sx3212100046maxsssxxz目標(mbio)函數(shù)：于是(ysh)，重新得到一個數(shù)學(xué)模型：上述過程(guchng)，稱為線性規(guī)劃的標準化過程(guchng)，其模型被稱為線性規(guī)劃的標準模型。第16頁/共57頁第十七頁，共57頁。0;, 2 , 1, 0max221122222121112121112211iimnmnmmnnnnnnbnixbxaxaxabxaxaxabxaxaxaxcxcxcz目標目標(mbio)函函數(shù)：數(shù)：約束條件約束條件第17頁/共57頁第十八頁，共57頁。第18頁/共57頁第十九頁，共57頁。 原模型(mxng)：標準化模型(mxng)：第19頁/共

9、57頁第二十頁，共57頁。101221 xx821 xx0,21xxs.t.72x1、若碰到0的約束條件該如何(rh)標準化？2、Min問題。第20頁/共57頁第二十一頁，共57頁。1012121sxx8221sxx0,32121sssxxs.t.732sx對于對于Min問題，只需要問題，只需要(xyo)將系數(shù)由正號（將系數(shù)由正號（+）變?yōu)樨摚ǎ┳優(yōu)樨摚?）即要。）即要。第21頁/共57頁第二十二頁，共57頁。第22頁/共57頁第二十三頁，共57頁。101221 xx821 xx0,21xxs.t.72x2134minxxz目標(mbio)函數(shù)：2134maxxxz101221 xx821 x

10、x0,21xxs.t.72x之前(zhqin)之后(zhhu)第23頁/共57頁第二十四頁，共57頁。2134maxxxz101221 xx821 xx0,21xxs.t.72x之后(zhhu)2134maxxxz1011221sxx8221sxx03, 2, 10,21sssxxs.t.732sx第24頁/共57頁第二十五頁，共57頁。第25頁/共57頁第二十六頁，共57頁。極點凸集不是(b shi)凸集凸集第26頁/共57頁第二十七頁，共57頁。第27頁/共57頁第二十八頁，共57頁。第28頁/共57頁第二十九頁，共57頁。x2 50403020101020 3040 x1 第29頁/共5

11、7頁第三十頁，共57頁。x2 50403020101020 3040 x1 Q1（25，0） Q2（15，20）第30頁/共57頁第三十一頁，共57頁。第31頁/共57頁第三十二頁，共57頁。x2 50403020101020 3040 x1 第32頁/共57頁第三十三頁，共57頁。 x2 3 -2x1+x2 4 x1,x2 0 第33頁/共57頁第三十四頁，共57頁。第34頁/共57頁第三十五頁，共57頁。 (d)可行域無界可行域無界 (e)可行域無界可行域無界 (f)可行域為空集可行域為空集(kn j) 多個最優(yōu)解多個最優(yōu)解 目標函數(shù)無界目標函數(shù)無界 無可行解無可行解 (a)可行域有界可行

12、域有界 (b)可行域有界可行域有界 (c)可行域無界可行域無界 唯一唯一(wi y)最優(yōu)解最優(yōu)解 多個最優(yōu)解多個最優(yōu)解 唯一唯一(wi y)最優(yōu)解最優(yōu)解第35頁/共57頁第三十六頁，共57頁。0;,2, 1,0),(),(),(minmax2211222221211121211122112211iimnmnmmnnnnnnnnbnixbxaxaxabxaxaxabxaxaxaxcxcxczxcxcxcz或目標目標(mbio)函函數(shù)：數(shù)：約束條件約束條件第36頁/共57頁第三十七頁，共57頁。0;, 2 , 1, 0max221122222121112121112211iimnmnmmnnnnn

13、nbnixbxaxaxabxaxaxabxaxaxaxcxcxcz目標目標(mbio)函函數(shù)：數(shù)：約束條件約束條件第37頁/共57頁第三十八頁，共57頁。1、什么是靈敏度分析？先看例子:2、如何(rh)進行靈敏度分析？第38頁/共57頁第三十九頁，共57頁。甲電纜甲電纜乙電纜乙電纜資源量資源量銅（噸）銅（噸）2110鉛（噸）鉛（噸）118價格（價格（萬元萬元）64另外，市場對乙電纜的最大需求量為7單位，而對甲乙(ji y)電纜的需求量無限制。問該工廠應(yīng)如何安排生產(chǎn)才能使工廠的總收入最大？求解結(jié)果:X1=2 ,X2=6,Z=36萬元 生產(chǎn)甲,乙電纜2個單位,6個單位,獲最大收入36萬元.問題(w

14、nt):甲的價格由6萬元降為5萬元,生產(chǎn)方案還是最優(yōu)嗎?怎么解決?(1)重新計算;(2)另想簡單辦法?第39頁/共57頁第四十頁，共57頁。1、什么是靈敏度分析？ 在實際工作中，我們往往已經(jīng)求得了最優(yōu)解，可是有時，模型中的某個系數(shù)或若干個系會發(fā)生變化，如原材料的購買單價由原來的50元上漲到為60元，那么，生產(chǎn)安排的最優(yōu)方案是否還是最優(yōu)？值得重新考慮？ 線性規(guī)劃(xin xn u hu)模型中系數(shù)的變化，引起最優(yōu)解的變化，屬于靈敏度分析的研究范圍。 定義：在建立數(shù)學(xué)模型和求得最優(yōu)解之后，研究線性規(guī)劃(xin xn u hu)的一引起系數(shù) 變化時，對最優(yōu)解產(chǎn)生什么影響？（最優(yōu)解是否會改變？）2、如

15、何進行靈敏度分析？jijibac,第40頁/共57頁第四十一頁，共57頁。2、如何進行靈敏度分析？（1）目標函數(shù)(hnsh)中的系數(shù) 的靈敏度分析 當 改變時， Z會如何改變？ 先看例子：icicAB資源限制設(shè)備11300臺時原料A21400千克原料B01250千克獲利（元）50100問該工廠應(yīng)如何安排生產(chǎn)(shngchn)才能使工廠的總收入最大？第41頁/共57頁第四十二頁，共57頁。圖解法例3：x1x22004000200300最優(yōu)解(50,250)300當X1=50,x2=250時, MAX Z=50 x1+100 x2=27500第42頁/共57頁第四十三頁，共57頁。第43頁/共57

16、頁第四十四頁，共57頁。圖解法例3：x1x22004000200300300直線(zhxin)F：直線E第44頁/共57頁第四十五頁，共57頁。第45頁/共57頁第四十六頁，共57頁。圖解法例3：x1x22004000200300最優(yōu)解300（z=27500=50 x1+100 x2) X1=50,x2=250第46頁/共57頁第四十七頁，共57頁。圖解法例3：x1x22004000200300300目標函數(shù)(hnsh)斜率:K=-c1/c221cck0121cck條件條件(tioj(tiojin):in):第47頁/共57頁第四十八頁，共57頁。圖解法例3：1005050221ccck012

17、1cck條件條件(ti(tiojiojin):n):x1x2第48頁/共57頁第四十九頁，共57頁。010011ck10001 c05012ck只要C2=100, C1在0和100之間變化,那么工廠生產(chǎn)獲取最大利潤的方案將不變.即仍然是X1=50,X2=250,即生產(chǎn)量不變，但獲取的利潤可能會變（因為產(chǎn)品的單價變了）。假設(shè)C2=100不變，C1=70上漲(shngzhng)20元，則當生產(chǎn)方案不變時，工廠獲利變?yōu)椋?0X70+100X250=3500+25000=28500，比原來多1000250c第49頁/共57頁第五十頁，共57頁。0121cck來判斷(pndun)原最優(yōu)解是否仍然最優(yōu)。如：C1=60，C2=55，-C1/C2=-60/55=-1.09要重新求解.第50頁/共57頁第