運(yùn)籌學(xué) 胡運(yùn)權(quán) 第一章

1、 胡運(yùn)權(quán) 清華大學(xué)出版社運(yùn)籌學(xué) 施泉生 中國(guó)電力出版社, 2004.7運(yùn)籌學(xué)習(xí)題集(第三版) 胡運(yùn)權(quán),清華大學(xué)出版社,2002.9 “運(yùn)籌學(xué)” O.R. Operations Research (美國(guó)) Operational Research (英國(guó)) 在現(xiàn)有的條件下，如何科學(xué)地設(shè) 計(jì)和操作某復(fù)雜系統(tǒng)，使其在某 種意義上達(dá)到最優(yōu)。本 課 程 內(nèi) 容規(guī)劃論：線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃、動(dòng)態(tài)規(guī)劃、網(wǎng)絡(luò)規(guī)劃、多目標(biāo)規(guī)劃、隨機(jī)規(guī)劃、圖與網(wǎng)絡(luò)分析：關(guān)鍵路線、最短路、最大流、最小樹、各種模型與問(wèn)題：運(yùn)輸問(wèn)題、分派問(wèn)題、存貯論、排隊(duì)論、決策論、對(duì)策論、軟 件 Excel Matlab Lindo, L

2、ingo 名稱由來(lái)： 二次大戰(zhàn) 課程設(shè)置： 1948年麻省理工學(xué)院 學(xué)術(shù)團(tuán)體： 1957年 英國(guó)牛津大學(xué) 第一屆國(guó)際運(yùn)籌學(xué)會(huì)議 1959年 “國(guó)際運(yùn)籌學(xué)聯(lián)合會(huì)” 學(xué)術(shù)刊物： 1950年 英國(guó)“運(yùn)籌學(xué)季刊” 我國(guó)大陸譯作 “運(yùn)籌學(xué)”，是借用了 史記-漢高祖本紀(jì) “運(yùn)籌于帷幄之中，決勝于千里之外” 一語(yǔ)中“運(yùn)籌”二字，既顯示其軍事的起 源，也表明它在我國(guó)已早有萌芽。 本課程的研究方法從現(xiàn)實(shí)生活場(chǎng)合抽出本質(zhì)的要素來(lái)構(gòu)造數(shù)學(xué)模型，因而可尋求一個(gè)跟決策者的目標(biāo)有關(guān)的解；探索求解的結(jié)構(gòu)并導(dǎo)出系統(tǒng)的求解過(guò)程；從可行方案中尋求系統(tǒng)的最優(yōu)解法。 本 課 程 的 特 點(diǎn)被廣泛用于工程建設(shè)、企業(yè)管理、軍事部門、，具

3、有很強(qiáng)的實(shí)踐性。是一門優(yōu)化技術(shù)，提供的是解決各類問(wèn)題 的優(yōu)化方法。是數(shù)學(xué)模型競(jìng)賽中使用的主要工具。運(yùn)籌學(xué)解決問(wèn)題的步驟提出問(wèn)題：用自然語(yǔ)言描述問(wèn)題。建立模型：用變量、函數(shù)、方程描述問(wèn)題。求解：用數(shù)學(xué)方法求出模型的最優(yōu)解、次優(yōu)解、滿意解，復(fù)雜模型求解要用計(jì)算機(jī)。解的檢驗(yàn)：檢查模型和求解步驟有無(wú)錯(cuò)誤，檢查解是否反映現(xiàn)實(shí)問(wèn)題。決策實(shí)施：決策者根據(jù)自己的經(jīng)驗(yàn)和偏好，對(duì)方案進(jìn)行選擇和修改，作出實(shí)施的決定。運(yùn)籌學(xué)的應(yīng)用市場(chǎng)銷售、生產(chǎn)計(jì)劃、資本運(yùn)營(yíng)、 庫(kù)存管理、運(yùn)輸問(wèn)題、財(cái)政和會(huì)計(jì)、 人事管理、設(shè)備維修和更新、 項(xiàng)目評(píng)價(jià)和選擇、工程優(yōu)化設(shè)計(jì)、 計(jì)算機(jī)和信息系統(tǒng)、城市管理、發(fā)展戰(zhàn)略、 本 課 程 要 求 熟練

4、掌握各種模型及其求解方法。 掌握與基本模型有關(guān)的基本概念及基本原理。 領(lǐng)會(huì)原理、掌握方法、強(qiáng)化應(yīng)用， 提高解決實(shí)際問(wèn)題的能力。 中國(guó)： 都江堰水利工程 (公元前250年)丁謂修開封皇宮 (北宋年間)齊王賽馬 (齊王與田忌) 外國(guó)： 哥尼斯堡七橋問(wèn)題 (1736) 歐拉 二戰(zhàn)期間： 反潛艇問(wèn)題 (英吉利海峽) 渡大西洋船隊(duì)規(guī)模問(wèn)題 德國(guó)“飛彈”襲擊倫敦問(wèn)題 線性規(guī)劃：LP求有線性約束的線性函數(shù)的最優(yōu)解。第一章 線性規(guī)劃及單純形法 線性規(guī)劃是運(yùn)籌學(xué)的重要內(nèi)容。本章介紹 (1) 線性規(guī)劃數(shù)學(xué)模型; (2) 線性規(guī)劃的基本理論; (3) 求解線性規(guī)劃的基本算法單純形法。G.B.Dantzig 于194

5、7年提出了求解線性規(guī) 劃問(wèn)題的單純形法。單純形法至今還是求解線性規(guī)劃最有效的方法。 解：將這個(gè)問(wèn)題化為線性規(guī)劃模型:1確定決策變量：x1=生產(chǎn)桌子的數(shù)量 x2=生產(chǎn)椅子的數(shù)量2確定目標(biāo)函數(shù)：家具廠的目標(biāo)是銷售收入最大 max (50 x1+30 x2)3確定約束條件： 4x1+3x2 120（木工工時(shí)限制） 2x1+x2 50 （油漆工工時(shí)限制）4變量取值限制：決策變量只取正值（非負(fù)值） x1 0, x2 0 數(shù)學(xué)模型 max (50 x1+30 x2) s.t. 4x1+3x2 120 2x1+ x2 50 x1, x2 0線性規(guī)劃數(shù)學(xué)模型三要素： 決策變量、約束條件、目標(biāo)函數(shù) 每一個(gè)線性規(guī)

6、劃問(wèn)題都有一組決策變量 (x1, x2, , xn) , 這組決策變量的值就代 表一個(gè)具體方案。 有使用各種資源的的約束條件。 有一個(gè)要達(dá)到的目標(biāo)，是決策變量的線性函數(shù)。 一般形式 矩陣形式 標(biāo)準(zhǔn)形式 將一般線性規(guī)劃化成標(biāo)準(zhǔn)形線性規(guī)劃問(wèn)題的一般形式：max(min) Z = c1x1+c2x2+.+cnxns.t. a11x1+a12x2+.+a1nxn (=, )b1 a21x1+a22x2+.+a2nxn (=, )b2 . am1x1+am2x2+.+amnxn (=, )bm x1, x2, ., xn 0線性規(guī)劃的矩陣形式： max Z = CTX s.t. AX=b X 0a11

7、a12 . a1n b1 A = a21 a22 . a2n b = b2 . am1 am2 . amn bmc1 x1 0 c2 x2 0C = X = 0 = . cn xn 0線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式：max Z = c1x1+c2x2+.+cnxns.t. a11x1+a12x2+.+a1nxn = b1 a21x1+a22x2+.+a2nxn = b2 . am1x1+am2x2+.+amnxn = bm x1, x2, ., xn 0其中：bi 0, i=1, 2,., m.四點(diǎn)要求:將一般線性規(guī)劃化成標(biāo)準(zhǔn)形 求max 等式約束 bi 0 xi 0(1) 若目標(biāo)函數(shù)是求最小值: m

8、in Z = CTX 令 Z = Z, 則化成 max Z= CTX注意: 因?yàn)?min Z = max(Z ) 所以變換后的最優(yōu)解不變，最優(yōu)值變號(hào)。(2) 若約束條件是不等式i)若約束條件是“ ” 不等式， 則不等式左邊 “加上” 非負(fù)的松馳變量；ii)若約束條件是“ ” 不等式， 則不等式左邊 “減去” 非負(fù)的松馳變量。(3) 若約束條件右面的某一常數(shù)項(xiàng) bi0, 這時(shí)只要在 bi 相對(duì)應(yīng)的約束方程兩邊乘 1。(4) 若變量 xj 無(wú)非負(fù)限制 引進(jìn)兩個(gè)非負(fù)變量 xj xj” 0 令 xj= xj xj（可正可負(fù)）任何形式的線性規(guī)劃總可以化成標(biāo)準(zhǔn)型例 將下列問(wèn)題化成標(biāo)準(zhǔn)型: min Z =

9、x1+ 2x2 3x3 s.t. x1+ x2 + x3 7 x1 x2 + x3 2 3x1 + x2 + 2x3 = 5 x1 0, x2 0, x3 無(wú)限制例 將下列問(wèn)題化成標(biāo)準(zhǔn)型: max ( x1 2x2 + 3x3) s.t. x1+ x2 + x3 7 x1 x2 + x3 2 3x1 + x2 + 2x3 = 5 x1 0, x2 0, x3 無(wú)限制例 將下列問(wèn)題化成標(biāo)準(zhǔn)型: max ( x1 2x2 + 3x3) s.t. x1+ x2 + x3 + x4 = 7 x1 x2 + x3 2 3x1 + x2 + 2x3 = 5 x1 0, x2 0, x3 無(wú)限制例 將下列問(wèn)

10、題化成標(biāo)準(zhǔn)型: max ( x1 2x2 + 3x3) s.t. x1+ x2 + x3 + x4 = 7 x1 x2 + x3 x5 = 2 3x1 + x2 + 2x3 = 5 x1 0, x2 0, x3 無(wú)限制max ( x1 2x2 + 3x3 3x3) s.t. x1+ x2 + x3 x3 + x4 = 7 x1 x2 + x3 x3 x5 = 2 3x1 + x2 + 2x3 2x3 = 5 x1 0, x2 0, x30, x30 令 x3 = x3 x30, ,20040065300432.423)(min:213321321321321xxxxxxxxxxxxtsxxxx

11、f不限不限原非標(biāo)準(zhǔn)型原非標(biāo)準(zhǔn)型0, ,20040065300432.423)(min:213321321321321xxxxxxxxxxxxtsxxxxf不限不限原非標(biāo)準(zhǔn)型原非標(biāo)準(zhǔn)型 0,2004006653004432.0004423)(max:65433216332153321433216543321xxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxf標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型 P43 1.2， 先畫可行域(滿足約束條件的X的全體)兩個(gè)變量LP問(wèn)題的圖解法 再畫法線方向 求 max，沿法線方向推； 求 min，沿負(fù)法線方向推。 最后的交點(diǎn)為頂點(diǎn)。例 max Z = 50 x1+30 x2

12、s.t. 4x1+3x2 120 2x1+x2 50 x1, x2 0 x240302010102030 x1 由 4x1+3x2 120 x1 0, x2 0 圍成的區(qū)域50 由 2x1+x2 50 x1 0, x2 0 圍成的區(qū)域x240302010102030 x1 由 4x1+3x2 120 2x1+x2 50 x1 0, x2 0 圍成的區(qū)域 (可行域)50可行域x240302010102030 x1 該問(wèn)題的可行域是由 Q1，Q2，Q3，Q4 作為頂點(diǎn)的凸多邊形50可行域Q1(0, 0)Q2(25, 0)Q4(0, 40)Q3(15, 20)x240302010102030 x1

13、目標(biāo)函數(shù) Z = 50 x1+30 x2 是一組平行線50可行域x240302010102030 x1 此組平行線沿其 法線方向 (50, 30) 右上方 函數(shù)值 Z 增加50可行域x240302010102030 x1當(dāng)該直線移到 Q3(15, 20)點(diǎn)時(shí)，Z 值達(dá)到最大： max Z=5015+3020=1350此時(shí)最優(yōu)解 X*=（15，20）50Q3(15, 20) 最優(yōu)解必定能在某一個(gè)頂點(diǎn)上取得。 P43 1.1LP問(wèn)題最優(yōu)解的歸類 可行解：滿足約束條件（包括非負(fù)條件）的 一組變量值，稱可行解。 可行域：可行解的全體。 最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大的可行解。 最優(yōu)值：將最優(yōu)解代入目標(biāo)函數(shù)

14、得到的值。 可行域?yàn)榭占療o(wú)可行解 可行域非空，則有三種情況：i) 有唯一解 (頂點(diǎn))ii) 有無(wú)窮多個(gè)解 (兩個(gè)頂點(diǎn)間的連線)iii) 無(wú)最優(yōu)解 (無(wú)界解)無(wú)最優(yōu)解x240302010102030 x1 當(dāng)目標(biāo)函數(shù)由 max Z=50 x1+30 x2 變成 max Z=40 x1+30 x2 目標(biāo)函數(shù)是同約束條件 4x1+3x2 120 平行的直線 Q2與Q3之間都是最優(yōu)解50Q3(15, 20)Q2(25, 0)無(wú)界解若可行域無(wú)界， 且目標(biāo)函數(shù)值可增加(減少)到正無(wú)窮(負(fù)無(wú)窮)， 稱這種無(wú)最優(yōu)解的情況為無(wú)界解。注意 可行域無(wú)界，不一定無(wú)最優(yōu)解； 可行域非空有界，則必定有最優(yōu)解。定義 (凸集)LP問(wèn)題解的性質(zhì)設(shè) D Rn 若任對(duì) X1, X2 D，對(duì)一切 0 0 中找最大者， j* = maxj ; j 0 選中者對(duì)應(yīng)的變量稱為進(jìn)基變量， xj* 第 j* 列稱為主列.換基迭代確定離基變量：如果有* *min0 =iiijiiji jbbaaa則xi* 為離基變量第 i* 行稱為主行換基