運(yùn)籌與決策之2線(xiàn)性規(guī)劃

1、1 Question 線(xiàn)性規(guī)劃的概念和建模線(xiàn)性規(guī)劃的概念和建模 線(xiàn)性規(guī)劃的圖解法線(xiàn)性規(guī)劃的圖解法 單純形法基本步驟單純形法基本步驟 計(jì)算機(jī)軟件求解計(jì)算機(jī)軟件求解LP問(wèn)題（下料優(yōu)化）問(wèn)題（下料優(yōu)化） Case 2:哈特風(fēng)險(xiǎn)哈特風(fēng)險(xiǎn) 靈敏度分析靈敏度分析( 2 1緒論緒論 Introduction 2線(xiàn)性規(guī)劃線(xiàn)性規(guī)劃 Linear Programming 3運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 Transportation Models 4整數(shù)規(guī)劃整數(shù)規(guī)劃 Integer Programming 5網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Models 6項(xiàng)目計(jì)劃項(xiàng)目計(jì)劃 PERT k =A,B,C,D)第第i年初投年初投k

2、項(xiàng)目的資金數(shù)項(xiàng)目的資金數(shù) max Z = 1.15x4A +1.40 x2C+1.25x3B+1.11x5D x1A+x1D 10 x2A+x2C+x2D= 1.11 x1D x2C 3 x3A +x3B+x3D =1.15 x1A+ 1.11 x2D x3B 4 x4A +x4D =1.15 x2A+ 1.11 x3D x5D =1.15 x3A+ 1.11 x4D xik 0 25 AX=b (1) X 0 (2) max Z = CX (3) 定義定義1 1:滿(mǎn)足約束滿(mǎn)足約束(1)、(2)的的X=(X1 Xn)T稱(chēng)為稱(chēng)為L(zhǎng)P 問(wèn)題的問(wèn)題的可行解可行解，全部可行解集合稱(chēng)為，全部可行解集合稱(chēng)

3、為可行域。可行域。 定義定義2 2:滿(mǎn)足滿(mǎn)足(3)的可行解稱(chēng)為的可行解稱(chēng)為L(zhǎng)P問(wèn)題的問(wèn)題的最優(yōu)解。最優(yōu)解。 26 產(chǎn)品產(chǎn)品 A B 備用資源備用資源 木工木工 1 2 30 油漆工油漆工 3 2 60 搬運(yùn)工搬運(yùn)工 0 2 24 利潤(rùn)利潤(rùn) 40 50 例例1、家具廠生產(chǎn)計(jì)劃問(wèn)題、家具廠生產(chǎn)計(jì)劃問(wèn)題 A, B 各生產(chǎn)多少各生產(chǎn)多少, 可獲最大利潤(rùn)可獲最大利潤(rùn)? 27 建立模型建立模型 max Z = 40X1+ 50X2 X1 + 2X2 30 3X1 + 2X2 60 2X2 24 X1 , X2 0 0 建模后如何計(jì)算？建模后如何計(jì)算？ 28 解：解：(1)、確定可行域、確定可行域 X1 0

4、 0 X1 =0=0 ( (橫軸橫軸) ) X2 0 0 X2=0=0 ( (縱軸縱軸) ) X1+2X2 30 X1+2X2 =30 兩點(diǎn)兩點(diǎn) (0,15)、 (30,0) 203010 0 10 20 30 X2 D A B C 3X1+2X2 =60 (0,30) (20,0) 2X2 =24 X1 29 (2)、求最優(yōu)解、求最優(yōu)解 解：解：X* = (15,7.5) Zmax =975 Z= 40X1+50X2 0=40X1+50X2 (0,0)， ， (10,-8) 0 203010 10 20 30 X1 X2 D A B C D A B C C點(diǎn)：點(diǎn)： X1+2X2 =30 3X

5、1+2X2 =60 30 幾何概念幾何概念代數(shù)概念代數(shù)概念 約束直線(xiàn)約束直線(xiàn)滿(mǎn)足一個(gè)等式約束的解滿(mǎn)足一個(gè)等式約束的解 約束半平面約束半平面滿(mǎn)足一個(gè)不等式約束的解滿(mǎn)足一個(gè)不等式約束的解 約束半平面的交集：約束半平面的交集： 凸多邊形凸多邊形 滿(mǎn)足一組不等式約束的解滿(mǎn)足一組不等式約束的解 約束直線(xiàn)的交點(diǎn)約束直線(xiàn)的交點(diǎn)基本解基本解 可行域的極點(diǎn)可行域的極點(diǎn)基本可行解基本可行解 目標(biāo)函數(shù)等值線(xiàn)：目標(biāo)函數(shù)等值線(xiàn)： 一組平行線(xiàn)一組平行線(xiàn) 目標(biāo)函數(shù)值等于一個(gè)常目標(biāo)函數(shù)值等于一個(gè)常 數(shù)的解數(shù)的解 如何對(duì)應(yīng)？如何對(duì)應(yīng)？ 31 （1）用字母表示可行域；）用字母表示可行域； （2）畫(huà)出目標(biāo)函數(shù)的平行線(xiàn)；）畫(huà)出目標(biāo)函

6、數(shù)的平行線(xiàn)； （3） 注意目標(biāo)函數(shù)的斜率；注意目標(biāo)函數(shù)的斜率； （4）適當(dāng)?shù)恼f(shuō)明語(yǔ)句（包括可行域、最優(yōu)）適當(dāng)?shù)恼f(shuō)明語(yǔ)句（包括可行域、最優(yōu) 解、目標(biāo)函數(shù)值等）解、目標(biāo)函數(shù)值等） 32 例例2、圖解法、圖解法 max Z =40X1+ 80X2 X1+2X2 30 3X1+2X2 60 2X2 24 X1 , X2 0 0 33 0 Z= 40 X1 + 80X2 =0 X1 + 2X2 =30 D AB C X2 X1 X(1)=(6,12) X(2)=(15,7.5) X= X(1)+(1- ) X(2) (0 1) 求解求解 最優(yōu)解：最優(yōu)解：BCBC線(xiàn)段線(xiàn)段 B B點(diǎn)點(diǎn)C C點(diǎn)點(diǎn) 無(wú)窮多解無(wú)

7、窮多解 34 X1 =6 + +(1- )15 X2=12 + +(1- )7.5 X1 =15-9 X2 =7.5+4.5 (0 1) X= = +(1- ) max Z =1200 X1 6 15 X2 12 7.5 35 無(wú)界無(wú)界 無(wú)有限最優(yōu)解無(wú)有限最優(yōu)解 例例3、 max Z =2X1+ 4X2 2X1+X2 8 8 -2X1+X2 2 X1 , X2 0 0 Z=0 -2X1+ X2=2 8 2 4 6 X2 2X1+ X2=8 4 0 X1 36 例例4、 maxZ=3X1+2X2 -X1 -X2 1 1 X1 , X2 0 0 無(wú)解無(wú)解 無(wú)可行解無(wú)可行解 -1 X2 -1 X1

8、0 37 唯一解唯一解 無(wú)窮多解無(wú)窮多解 無(wú)有限最優(yōu)解無(wú)有限最優(yōu)解 無(wú)可行解無(wú)可行解 有解有解 無(wú)解無(wú)解 38 AX=b (1) X 0 (2) maxZ=CX (3) 概念：概念： 1 1 可行解可行解? 2 2 可行域可行域? 3 3 最優(yōu)解最優(yōu)解? 39 40 41 42 43 vEXCEL規(guī)劃求解規(guī)劃求解solver的功能：可以解決的功能：可以解決 線(xiàn)性規(guī)劃、線(xiàn)性規(guī)劃、01規(guī)劃以及整數(shù)線(xiàn)性規(guī)劃等規(guī)劃以及整數(shù)線(xiàn)性規(guī)劃等 問(wèn)題。問(wèn)題。 vEXCEL中安裝好中安裝好“規(guī)劃求解規(guī)劃求解”？ v（菜單（菜單工具工具加載宏）加載宏） v線(xiàn)性問(wèn)題、非線(xiàn)性問(wèn)題，變量限制線(xiàn)性問(wèn)題、非線(xiàn)性問(wèn)題，變量限制2

9、00個(gè)，個(gè)， 約束條件最多可達(dá)約束條件最多可達(dá)100個(gè)。個(gè)。 44 45 1 在約束中使用的在約束中使用的運(yùn)算符運(yùn)算符有下列有下列5個(gè)：個(gè)： =大于等于大于等于; int 整數(shù)整數(shù); bin 二進(jìn)制（二進(jìn)制（0或或1） 2 求解中用到下列概念：求解中用到下列概念： 目標(biāo)單元格最大值（最小值）：指滿(mǎn)足可變單元格約目標(biāo)單元格最大值（最小值）：指滿(mǎn)足可變單元格約 束條件后，單元格可取的最大值（最小值）。束條件后，單元格可取的最大值（最小值）。 3 可變單元格可變單元格（目標(biāo)函數(shù)、變量和約束條件）（目標(biāo)函數(shù)、變量和約束條件） 例如，問(wèn)題中例如，問(wèn)題中B1、D6、D7格由公式構(gòu)成，分別對(duì)應(yīng)格由公式構(gòu)成，

10、分別對(duì)應(yīng) 模型中的目標(biāo)函數(shù)（如：模型中的目標(biāo)函數(shù)（如：B1=B3*B5+C3*C5）和約）和約 束條件；束條件；B5、C5為為“可變單元格可變單元格”，分別對(duì)應(yīng)模型，分別對(duì)應(yīng)模型 中的變量。中的變量。 4 求解過(guò)程（見(jiàn)求解過(guò)程（見(jiàn)Excel） 46 47軟件求解下料優(yōu)化問(wèn)題軟件求解下料優(yōu)化問(wèn)題 48 49 lLet S = fraction of the Security Systems project funded by HVC lM = fraction of the Market Analysis project funded by HVC 50 51 52 53 l圖解法靈敏度分析圖解

11、法靈敏度分析 l靈敏度分析：計(jì)算機(jī)求解靈敏度分析：計(jì)算機(jī)求解 l多于兩個(gè)變量的情況多于兩個(gè)變量的情況 54 l如果在計(jì)劃實(shí)施前或?qū)嵤┲杏行┮蛩匾寻l(fā)如果在計(jì)劃實(shí)施前或?qū)嵤┲杏行┮蛩匾寻l(fā) 生了改變，則決策者所關(guān)心的是目前所執(zhí)生了改變，則決策者所關(guān)心的是目前所執(zhí) 行的計(jì)劃還行的計(jì)劃還是不是最優(yōu)是不是最優(yōu)？企業(yè)應(yīng)當(dāng)作出什？企業(yè)應(yīng)當(dāng)作出什 么樣的反應(yīng)，運(yùn)用靈敏度分析而么樣的反應(yīng)，運(yùn)用靈敏度分析而不需建立不需建立 新的模型。新的模型。 l模型中模型中目標(biāo)函數(shù)系數(shù)目標(biāo)函數(shù)系數(shù)哪個(gè)更能影響最優(yōu)解哪個(gè)更能影響最優(yōu)解 。 l約束條件的約束條件的右端值變化右端值變化對(duì)最優(yōu)解的影響。對(duì)最優(yōu)解的影響。 55 l模型參數(shù)

12、是粗略的模型參數(shù)是粗略的估計(jì)值估計(jì)值 l獲取所需數(shù)據(jù)必須付出許多的獲取所需數(shù)據(jù)必須付出許多的時(shí)間與精力時(shí)間與精力 l有些因素只有在研究完成后才能精確測(cè)量有些因素只有在研究完成后才能精確測(cè)量 lwhat-ifwhat-if分析表明改變這些決策對(duì)結(jié)果的分析表明改變這些決策對(duì)結(jié)果的 影響，從而有效指導(dǎo)管理者作出影響，從而有效指導(dǎo)管理者作出最終決策最終決策 56 A（原材料消耗）（原材料消耗）代表企業(yè)的技術(shù)狀況；代表企業(yè)的技術(shù)狀況； b（資源供應(yīng)量）（資源供應(yīng)量）代表企業(yè)的資源狀況；代表企業(yè)的資源狀況； C（價(jià)值系數(shù)）（價(jià)值系數(shù)）代表企業(yè)產(chǎn)品的市場(chǎng)狀況；代表企業(yè)產(chǎn)品的市場(chǎng)狀況； 在這些因素（原材料消耗

13、系數(shù)、資源供應(yīng)量、在這些因素（原材料消耗系數(shù)、資源供應(yīng)量、 價(jià)值系數(shù)）不變的情況下企業(yè)的最優(yōu)生產(chǎn)計(jì)價(jià)值系數(shù)）不變的情況下企業(yè)的最優(yōu)生產(chǎn)計(jì) 劃和最大利潤(rùn)由線(xiàn)性規(guī)劃的最優(yōu)解和最優(yōu)值劃和最大利潤(rùn)由線(xiàn)性規(guī)劃的最優(yōu)解和最優(yōu)值 決定。決定。 在生產(chǎn)計(jì)劃問(wèn)題的一般形式在生產(chǎn)計(jì)劃問(wèn)題的一般形式 中，中，A，b，C各代表什么各代表什么 標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型 max Z=CX AX = =b X 0 如何回答？如何回答？ 57 l模型參數(shù)是粗略的估計(jì)值模型參數(shù)是粗略的估計(jì)值 l獲取所需數(shù)據(jù)必須付出許多的時(shí)間與精力獲取所需數(shù)據(jù)必須付出許多的時(shí)間與精力 l有些因素只有在研究完成后才能精確測(cè)量有些因素只有在研究完成后才能精確測(cè)

14、量 lwhat-ifwhat-if分析表明改變這些決策對(duì)結(jié)果的分析表明改變這些決策對(duì)結(jié)果的 影響，從而有效指導(dǎo)管理者作出最終決策影響，從而有效指導(dǎo)管理者作出最終決策 58 1. C(價(jià)格系數(shù)價(jià)格系數(shù))變化的分析變化的分析: 最優(yōu)條件最優(yōu)條件 CBB-1A C 0. 2.增加一個(gè)新變量增加一個(gè)新變量(例如新產(chǎn)品投產(chǎn)例如新產(chǎn)品投產(chǎn))的分析的分析: 如果最優(yōu)條件如果最優(yōu)條件CBB-1Pj - Cj 0滿(mǎn)足，不生產(chǎn)滿(mǎn)足，不生產(chǎn); 如果滿(mǎn)足如果滿(mǎn)足CBB-1Pj - Cj 0，新產(chǎn)品生產(chǎn)，新產(chǎn)品生產(chǎn). 3. b(資源量資源量)變化的分析變化的分析: 最優(yōu)條件最優(yōu)條件B-1b0. 4. 增加一個(gè)新的約束條

15、件的分析：增加一個(gè)新的約束條件的分析： 最優(yōu)解滿(mǎn)足約束條件，則不變；最優(yōu)解滿(mǎn)足約束條件，則不變； 最優(yōu)解不滿(mǎn)足約束條件，則用對(duì)偶單純形法，最優(yōu)解不滿(mǎn)足約束條件，則用對(duì)偶單純形法， 目標(biāo)值變差。目標(biāo)值變差。 59 標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型 max Z=CX AX = =b X 0 (1)、參數(shù)、參數(shù)A，b，C在什么范圍內(nèi)變動(dòng)，對(duì)當(dāng)在什么范圍內(nèi)變動(dòng)，對(duì)當(dāng) 前方案無(wú)影響？前方案無(wú)影響？ (2)、參數(shù)、參數(shù)A，b，C中的一個(gè)中的一個(gè)(幾個(gè)幾個(gè))變動(dòng)，對(duì)變動(dòng)，對(duì) 當(dāng)前方案影響？當(dāng)前方案影響？ (3)、如果最優(yōu)方案改變，如何用簡(jiǎn)便方法求、如果最優(yōu)方案改變，如何用簡(jiǎn)便方法求 新方案？新方案？ 60 l遞減成本（遞減成本

16、（CBB-1Pj -Cj）表示使目標(biāo)函數(shù)中表示使目標(biāo)函數(shù)中 變量的值為正數(shù)時(shí)相應(yīng)目標(biāo)函數(shù)系數(shù)的改變變量的值為正數(shù)時(shí)相應(yīng)目標(biāo)函數(shù)系數(shù)的改變 量（最大化問(wèn)題是增加；最小化問(wèn)題是減?。┝浚ㄗ畲蠡瘑?wèn)題是增加；最小化問(wèn)題是減?。?l當(dāng)某個(gè)變量對(duì)應(yīng)的當(dāng)某個(gè)變量對(duì)應(yīng)的遞減成本遞減成本0，表示含義？，表示含義？ l見(jiàn)見(jiàn)P70 例例3.4.1中圖中圖3-6的的D產(chǎn)品的遞減成本為產(chǎn)品的遞減成本為 1.15003，表明，表明D的利潤(rùn)應(yīng)增加的利潤(rùn)應(yīng)增加1.15003元，元，D 才能變?yōu)檎怠２拍茏優(yōu)檎怠?61 經(jīng)濟(jì)解釋?zhuān)航?jīng)濟(jì)解釋?zhuān)?W= yb =(y1 ym ) b1 bm = b1 y1 + b2 y2 + +

17、bm ym bi ： 第第 i 種資源的數(shù)量種資源的數(shù)量 yi ：對(duì)偶價(jià)格：對(duì)偶價(jià)格 bi增加增加 bi , ,其它資源數(shù)量不變時(shí)其它資源數(shù)量不變時(shí), ,目標(biāo)函數(shù)目標(biāo)函數(shù) 的增量的增量 Z=bi yi yi ：反映：反映bi 的邊際效益的邊際效益( (邊際成本邊際成本) ) 62 l假設(shè)目標(biāo)為假設(shè)目標(biāo)為max l對(duì)偶價(jià)格對(duì)偶價(jià)格y （dual price）：）：b 的單位改變量的單位改變量 所引起的目標(biāo)函數(shù)改變量。所引起的目標(biāo)函數(shù)改變量。 l如果如果y的大小與系統(tǒng)內(nèi)資源對(duì)目標(biāo)的貢獻(xiàn)有的大小與系統(tǒng)內(nèi)資源對(duì)目標(biāo)的貢獻(xiàn)有 關(guān)，是資源的一種估價(jià)，關(guān)，是資源的一種估價(jià)，又稱(chēng)為影子價(jià)格又稱(chēng)為影子價(jià)格。 6

18、3 對(duì)偶價(jià)格的準(zhǔn)確經(jīng)濟(jì)意義與建模有關(guān)。對(duì)偶價(jià)格的準(zhǔn)確經(jīng)濟(jì)意義與建模有關(guān)。 情況情況 模型中，目標(biāo)函數(shù)系數(shù)模型中，目標(biāo)函數(shù)系數(shù)Ci 表示利潤(rùn)時(shí)，表示利潤(rùn)時(shí)， yi 不是真正的影子價(jià)格，只表示資源不是真正的影子價(jià)格，只表示資源bi 增加增加1 1單單 位時(shí)，企業(yè)目標(biāo)增加的凈利潤(rùn)。位時(shí)，企業(yè)目標(biāo)增加的凈利潤(rùn)。 情況情況 模型中，目標(biāo)函數(shù)系數(shù)模型中，目標(biāo)函數(shù)系數(shù)Ci 表示成本時(shí)，表示成本時(shí)， yi 是真正的影子價(jià)格。是真正的影子價(jià)格。 64 勝利家具廠生產(chǎn)桌子和椅子兩種家具。桌子售價(jià)勝利家具廠生產(chǎn)桌子和椅子兩種家具。桌子售價(jià)50元個(gè)，椅子售元個(gè)，椅子售 價(jià)價(jià)30元個(gè)，生產(chǎn)桌子和椅子需要木工和油漆工兩種

19、工種。生產(chǎn)一元個(gè)，生產(chǎn)桌子和椅子需要木工和油漆工兩種工種。生產(chǎn)一 個(gè)桌子需要木工個(gè)桌子需要木工4小時(shí)，油漆工小時(shí)，油漆工2小時(shí)。生產(chǎn)一個(gè)椅子需要木工小時(shí)。生產(chǎn)一個(gè)椅子需要木工3小小 時(shí)，油漆工時(shí)，油漆工1小時(shí)。該廠每月可用木工工時(shí)為小時(shí)。該廠每月可用木工工時(shí)為120小時(shí)，油漆工工時(shí)小時(shí)，油漆工工時(shí) 為為50小時(shí)。問(wèn)該廠如何組織生產(chǎn)才能使每月的銷(xiāo)售收入最大？小時(shí)。問(wèn)該廠如何組織生產(chǎn)才能使每月的銷(xiāo)售收入最大？ 資源資源 單耗單耗 產(chǎn)品產(chǎn)品桌子桌子 椅子椅子資源限量資源限量 木工木工 4 3120小時(shí)小時(shí) 油漆工油漆工 2 1 50小時(shí)小時(shí) 售價(jià)售價(jià)(元個(gè)元個(gè))50 30 65 l模型模型1 1：產(chǎn)

20、品：產(chǎn)品A(A(桌子桌子) )，B(B(椅子椅子) )銷(xiāo)售價(jià)格發(fā)生銷(xiāo)售價(jià)格發(fā)生 變化，最優(yōu)解是否改變？變化，最優(yōu)解是否改變？ l模型模型3 3：如果家具廠木工資源可能發(fā)生變化，：如果家具廠木工資源可能發(fā)生變化， 要使生產(chǎn)計(jì)劃不變，問(wèn)木工工時(shí)要使生產(chǎn)計(jì)劃不變，問(wèn)木工工時(shí)b1b1變化范圍變化范圍 如何如何? ? l模型模型2 2：設(shè)計(jì)一種新產(chǎn)品柜子：設(shè)計(jì)一種新產(chǎn)品柜子, , 售價(jià)售價(jià)100100元元, , 單耗木工單耗木工9 9工時(shí)、油漆工工時(shí)、油漆工3 3工時(shí)問(wèn)是否投產(chǎn)工時(shí)問(wèn)是否投產(chǎn)? ? l模型模型4 4：若增加約束：若增加約束: : 每月可用木材量是每月可用木材量是1010立立 方米方米,

21、, 桌子單耗桌子單耗0.40.4立方米立方米, ,椅子單耗椅子單耗0.30.3立方立方 米。如何安排生產(chǎn)米。如何安排生產(chǎn)? ? l模型模型5 5：如果桌子價(jià)格降價(jià)：如果桌子價(jià)格降價(jià)1010，而椅子價(jià)格，而椅子價(jià)格 上漲上漲1010，該問(wèn)題的最優(yōu)解是否發(fā)生變化？，該問(wèn)題的最優(yōu)解是否發(fā)生變化？ 66 l對(duì)所有變化的目標(biāo)函數(shù)系數(shù)，對(duì)所有變化的目標(biāo)函數(shù)系數(shù)，允許的增允許的增 量和允許的減量百分比之和未達(dá)到量和允許的減量百分比之和未達(dá)到100%100%， 最優(yōu)解就不會(huì)改變。最優(yōu)解就不會(huì)改變。 l模型模型5 5：如果桌子價(jià)格：如果桌子價(jià)格降價(jià)降價(jià)1010，而椅子而椅子 價(jià)格價(jià)格上漲上漲1010，如何？如何

22、？ 目標(biāo)式目標(biāo)式 系數(shù)系數(shù) 允許的允許的 增量增量 允許的允許的 減量減量 5010101010 307.57.55 5 67 l圖解法靈敏度分析圖解法靈敏度分析（參見(jiàn)教材（參見(jiàn)教材P57P57） l應(yīng)用應(yīng)用ExcelExcel的靈敏度分析的靈敏度分析 l應(yīng)用應(yīng)用MS6.0MS6.0的靈敏度分析的靈敏度分析 68 69 分析：找出原問(wèn)題的對(duì)偶解，分析：找出原問(wèn)題的對(duì)偶解， 利用機(jī)會(huì)成本利用機(jī)會(huì)成本 C CB BB B 1 1Pj j 。從最優(yōu)表中可知： 。從最優(yōu)表中可知：Y=CY=CB BB B 1 1= =(5,15)(5,15)。 銷(xiāo)售價(jià)格銷(xiāo)售價(jià)格85元元機(jī)會(huì)成本機(jī)會(huì)成本, 新產(chǎn)品不應(yīng)生產(chǎn)新產(chǎn)品不應(yīng)生產(chǎn)! 機(jī)會(huì)成本機(jī)會(huì)