1、運籌學Operational Research,運籌帷幄，決勝千里 ?史記《張良傳》,2,目 錄,緒 論第一章 線性規(guī)劃問題及單純型解法第二章 線性規(guī)劃的對偶理論及其應用第三章 運輸問題數(shù)學模型及其解法第四章 整數(shù)規(guī)劃第五章 動態(tài)規(guī)劃第六章 圖與網路分析第七章 隨機服務理論概論第八章 生滅服務系統(tǒng)第九章 特殊隨機服務

2、系統(tǒng)第十章 存儲理論,3,緒 論,一、運籌學的起源與發(fā)展二、運籌學的特點及研究對象三、運籌學解決問題的方法步驟四、運籌學的發(fā)展趨勢,4,一、運籌學的起源與發(fā)展,起源于二次大戰(zhàn)的一門新興交叉學科與作戰(zhàn)問題相關如雷達的設置、運輸船隊的護航、反潛作戰(zhàn)中深水炸彈的深度、飛行員的編組、軍事物資的存儲等英國稱為 Operational Research美國稱為 Operations Research戰(zhàn)后在經濟、管理和機關學校及科

3、研單位繼續(xù)研究1952年，Morse 和 Kimball出版《運籌學方法》1948年英國首先成立運籌學會1952年美國成立運籌學會1959年成立國際運籌學聯(lián)合會(IFORS)我國于1982年加入IFORS，并于1999年8月組織了第15屆大會,5,二、運籌學的特點及研究對象,運籌學的定義為決策機構對所控制的業(yè)務活動作決策時，提供以數(shù)量為基礎的科學方法——Morse 和 Kimball運籌學是把科學方法應用在指導人員、工商企

4、業(yè)、政府和國防等方面解決發(fā)生的各種問題，其方法是發(fā)展一個科學的系統(tǒng)模式，并運用這種模式預測，比較各種決策及其產生的后果，以幫助主管人員科學地決定工作方針和政策——英國運籌學會運籌學是應用分析、試驗、量化的方法對經濟管理系統(tǒng)中人力、物力、財力等資源進行統(tǒng)籌安排，為決策者提供有根據(jù)的最優(yōu)方案，以實現(xiàn)最有效的管理——中國百科全書現(xiàn)代運籌學涵蓋了一切領域的管理與優(yōu)化問題，稱為 Management Science,6,二、運籌學的特點及研究

5、對象,運籌學的分支數(shù)學規(guī)劃：線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃、動態(tài)規(guī)劃、目標規(guī)劃等圖論與網路理論隨機服務理論：排隊論存儲理論決策理論對策論系統(tǒng)仿真：隨機模擬技術、系統(tǒng)動力學可靠性理論金融工程,7,三、運籌學解決問題的方法步驟,明確問題建立模型設計算法整理數(shù)據(jù)求解模型評價結果,明確問題,建立模型,設計算法,,整理數(shù)據(jù),求解模型,評價結果,簡化？,,滿意？,Yes,No,No,8,四、運籌學的發(fā)展趨勢,運籌學的危機

6、脫離實際應用，陷入數(shù)學陷阱IT對運籌學的影響MIS, DSS, MRP-II, CIMS, ERPOR Dept. --> Dept. Of OR & IS運籌學與行為科學結合群決策和談判對策理論多層規(guī)劃合理性分析服務行業(yè)中的應用金融服務業(yè)信息、電信服務業(yè)醫(yī)院管理,9,四、運籌學的發(fā)展趨勢,軟計算面向強復雜系統(tǒng)的計算、實時控制、知識推理智能算法：模擬退火、遺傳算法、人工神經網絡、戒律算法等系

7、統(tǒng)仿真面向問題后勤(Logistics)全球供應鏈管理電子商務：集成特性隨機和模糊 OR問題本身的不確定性人類知識的局限性,10,第一章 線性規(guī)劃問題及單純型解法,1.1 線性規(guī)劃問題及其一般數(shù)學模型1.1.1 線性規(guī)劃問題舉例例1、多產品生產問題（Max, ?）設x1, x2 分別代表甲、乙兩種電纜的生產量，,11,例2、配料問題（min, ?),設 x1, x2分別代表每粒膠丸中甲、乙兩種原料的用量,12,例3、

8、合理下料問題 設 xj 分別代表采用切割方案1~8的套數(shù)，,13,1.1.2 線性規(guī)劃數(shù)學模型的一般表示方式,14,1、和式,15,2、向量式,16,3、矩陣式,17,1.1.3 線性規(guī)劃的圖解法,,,,,,,,,,,f(x)=36,18,線性規(guī)劃問題的幾個特點：,線性規(guī)劃問題的可性解的集合是凸集線性規(guī)劃問題的基礎可行解一般都對應于凸集的極點凸集的極點的個數(shù)是有限的最優(yōu)解只可能在凸集的極點上，而不可能發(fā)生在凸集的內部,19

9、,1.2 線性規(guī)劃問題的單純型解法1.2.1 線性規(guī)劃問題的標準形式為了使線性規(guī)劃問題的解法標準，就要把一般形式化為標準形式,20,變換的方法：,目標函數(shù)為min型，價值系數(shù)一律反號。令 f?(x) = -f(x) = -CX, 有 min f(x) = - max [- f(x)] = - max f ?(x)第i 個約束的bi 為負值，則該行左右兩端系數(shù)同時反號，同時不等號也要反向第i 個約束為 ? 型，在不等式左邊增加

10、一個非負的變量xn+i ，稱為松弛變量；同時令 cn+i = 0第i 個約束為 ? 型，在不等式左邊減去一個非負的變量xn+i ，稱為剩余變量；同時令 cn+i = 0若xj ?0，令 xj= -xj? ，代入非標準型，則有xj? ? 0若xj ?不限，令 xj= xj? - xj?， xj? ? 0，xj? ? 0，代入非標準型,21,變換舉例：,22,關于標準型解的若干基本概念：,標準型有 n+m 個變量， m 個約束行“基

11、”的概念在標準型中，技術系數(shù)矩陣有 n+m 列，即 A = ( P1, P2 , … , Pn+m )A中線性獨立的 m 列，構成該標準型的一個基，即 B = ( P1 ?, P2 ? , … , Pm ?)， | B | ? 0 P1 ?, P2 ? , … , Pm ?稱為基向量與基向量對應的變量稱為基變量，記為 XB = ( x1 ?, x2 ? , … , xm ? )T，其余的變量稱為非基

12、變量，記為 XN = ( xm+1 ?, xm+2 ?, … , xm+n ? ) T ， 故有 X = XB + XN最多有 個基,23,關于標準型解的若干基本概念：,可行解與非可行解滿足約束條件和非負條件的解 X 稱為可行解，滿足約束條件但不滿足非負條件的解 X 稱為非可行解基礎解令非基變量 XN = 0，求得基變量 XB的值稱為基礎解 即 XB = B?1 bXB 是基礎解的必要

13、條件為XB 的非零分量個數(shù) ? m基礎可行解基礎解 XB 的非零分量都 ? 0 時，稱為基礎可行解，否則為基礎非可行解基礎可行解的非零分量個數(shù) < m 時，稱為退化解,24,線性規(guī)劃標準型問題解的關系,約束方程的解空間,,,基礎解,可行解,非可行解,基礎可行解,,退化解,,25,可行解、基礎解和基礎可行解舉例,26,1.2.2 單純型法的基本思路,27,1.2.3 單純型表及其格式,28,例1.2.2 試列出下面線性規(guī)

14、劃問題的初始單純型表,29,關于檢驗數(shù)的數(shù)學解釋,設 B 是初始可行基，則目標函數(shù)可寫為兩部分(1)約束條件也寫為兩部分，經整理得 XB 的表達式(2)，注意 XB中含有非基變量作參數(shù)把 XB 代入目標函數(shù)，整理得到(3)式第 j 個非基變量的機會成本如(4)式若有cj?zj>0, 則未達到最優(yōu),30,1.2.4 標準型的單純型算法,找初始基礎可行基對于(max,?)，松弛變量對應的列構成一個單位陣若有 bi 0 中找

15、最大者，選中者稱為入變量， xj* 第j*列稱為主列確定入變量的最大值和出變量最小比例原則,31,1.2.4 標準型的單純型算法,確定入變量的最大值和出變量設第 i* 行使 ? 最小，則第 i* 行對應的基變量稱為出變量，第 i* 行稱為主行迭代過程主行 i* 行與主列 j* 相交的元素ai*j* 稱為主元，迭代以主元為中心進行迭代的實質是線性變換，即要將主元 ai*j*變?yōu)?，主列上其它元素變?yōu)?，變換步驟如下：(1)

16、變換主行,32,1.2.4 標準型的單純型算法,迭代過程(2)變換主列除主元保留為1，其余都置0(3)變換非主行、主列元素 aij (包括 bi)四角算法公式：,33,1.2.4 標準型的單純型算法,5、迭代過程(4)變換CB，XB(5)計算目標函數(shù)、機會成本 zj 和檢驗數(shù) cj ? zj 6、返回步驟 2,34,表1.2.4 例1.2.2 單純型表的迭代過程,,,答：最優(yōu)解為 x1=20, x2=20, x3=0,

17、OBJ=1700,35,單純型表中元素的幾點說明,任何時候，基變量對應的列都構成一個單位矩陣當前表中的 b 列表示當前基變量的解值，通過變換 B ?1 b 得到 (資源已變成產品)當前非基變量對應的向量可通過變換 B ?1 AN 得到， 表示第 j 個變量對第 i 行對應的基變量的消耗率非基變量的機會成本由 給出注意基變量所對應的行,36,1.3

18、人工變量的引入及其解法 1.3.1 當約束條件為“?”型，引入剩余變量和人工變量,由于所添加的剩余變量的技術系數(shù)為?1，不能作為初始可行基變量，為此引入一個人為的變量（注意，此時約束條件已為“=”型），以便取得初始基變量，故稱為人工變量由于人工變量在原問題的解中是不能存在的，應盡快被迭代出去，因此人工變量在目標函數(shù)中對應的價值系數(shù)應具有懲罰性，稱為罰系數(shù)。罰系數(shù)的取值視解法而定兩種方法大M法二階段法,37,1.3.2

19、 大M法的求解過程 例1.3.1,38,表1.3.1 例1.3.1的單純型表迭代過程,答：最優(yōu)解為 x1=2, x2=2, x3=0, OBJ=36,39,大M法的一些說明,大M法實質上與原單純型法一樣，M 可看成一個很大的常數(shù)人工變量被迭代出去后一般就不會再成為基變量當檢驗數(shù)都滿足最優(yōu)條件，但基變量中仍有人工變量，說明原線性規(guī)劃問題無可行解大M法手算很不方便因此提出了二階段法計算機中常用大M法二階段法手算可能容

20、易,40,1.3.3 二階段法的求解過程,第一階段的任務是將人工變量盡快迭代出去，從而找到一個沒有人工變量的基礎可行解第二階段以第一階段得到的基礎可行解為初始解，采用原單純型法求解若第一階段結束時，人工變量仍在基變量中，則原問題無解為了簡化計算，在第一階段重新定義價值系數(shù)如下：,41,表1.3.2 用二階段法求解例1.3.1的第一階段,42,表1.3.2 用二階段法求解例1.3.1的第二階段,最優(yōu)解對應的B–1在哪？,43,1

21、.5 單純型法的一些具體問題,1.5.1 關于無界解問題可行區(qū)域不閉合(約束條件有問題)單純型表中入變量 xj* 對應的列中所有,44,表1.5.1 例1.5.1 的單純型表及其迭代過程,?,45,1.5.2 關于退化問題,退化問題的原因很復雜，當原問題存在平衡約束時當單純型表中同時有多個基變量可選作出變量時退化的嚴重性在于可能導致死循環(huán)，克服死循環(huán)的方法有“字典序”法,46,1.5.3 關于多重解問題,多個基礎可行解都是最優(yōu)解

22、，這些解在同一個超平面上，且該平面與目標函數(shù)等值面平行最優(yōu)單純型表中有非基變量的檢驗數(shù)為0最優(yōu)解的線性組合仍是最優(yōu)解，即 X=aX1+bX2，a+b=1,47,表1.5.3 例1.5.3 的單純型表及其迭代過程,48,1.5.4 關于無可行解問題,約束條件互相矛盾，無可行域單純型表達到最優(yōu)解檢驗條件時，人工變量仍在基變量中,49,表1.5.4 例1.5.4 第一階段的單純型表,50,1.4 修正單純型法,原單純型法迭代所需存儲量