運籌學OperationalResearch1.ppt

運籌學 Operational Research,運籌帷幄，決勝千里 史記張良傳,2,目 錄,緒 論 第一章 線性規(guī)劃問題及單純型解法 第二章 線性規(guī)劃的對偶理論及其應用 第三章 運輸問題數(shù)學模型及其解法 第四章 整數(shù)規(guī)劃 第五章 動態(tài)規(guī)劃 第六章 圖與網(wǎng)路分析 第七章 隨機服務理論概論 第八章 生滅服務系統(tǒng) 第九章 特殊隨機服務系統(tǒng) 第十章 存儲理論,3,緒 論,一、運籌學的起源與發(fā)展 二、運籌學的特點及研究對象 三、運籌學解決問題的方法步驟 四、運籌學的發(fā)展趨勢,4,一、運籌學的起源與發(fā)展,起源于二次大戰(zhàn)的一門新興交叉學科 與作戰(zhàn)問題相關 如雷達的設置、運輸船隊的護航、反潛作戰(zhàn)中深水炸彈的深度、飛行員的編組、軍事物資的存儲等 英國稱為 Operational Research 美國稱為 Operations Research 戰(zhàn)后在經(jīng)濟、管理和機關學校及科研單位繼續(xù)研究 1952年，Morse 和 Kimball出版運籌學方法 1948年英國首先成立運籌學會 1952年美國成立運籌學會 1959年成立國際運籌學聯(lián)合會(IFORS) 我國于1982年加入IFORS，并于1999年8月組織了第15屆大會,5,二、運籌學的特點及研究對象,運籌學的定義 為決策機構對所控制的業(yè)務活動作決策時，提供以數(shù)量為基礎的科學方法Morse 和 Kimball 運籌學是把科學方法應用在指導人員、工商企業(yè)、政府和國防等方面解決發(fā)生的各種問題，其方法是發(fā)展一個科學的系統(tǒng)模式，并運用這種模式預測，比較各種決策及其產生的后果，以幫助主管人員科學地決定工作方針和政策英國運籌學會 運籌學是應用分析、試驗、量化的方法對經(jīng)濟管理系統(tǒng)中人力、物力、財力等資源進行統(tǒng)籌安排，為決策者提供有根據(jù)的最優(yōu)方案，以實現(xiàn)最有效的管理中國百科全書 現(xiàn)代運籌學涵蓋了一切領域的管理與優(yōu)化問題，稱為 Management Science,6,二、運籌學的特點及研究對象,運籌學的分支 數(shù)學規(guī)劃：線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃、動態(tài)規(guī)劃、目標規(guī)劃等 圖論與網(wǎng)路理論 隨機服務理論：排隊論 存儲理論 決策理論 對策論 系統(tǒng)仿真：隨機模擬技術、系統(tǒng)動力學 可靠性理論 金融工程,7,三、運籌學解決問題的方法步驟,明確問題 建立模型 設計算法 整理數(shù)據(jù) 求解模型 評價結果,明確問題,建立模型,設計算法,整理數(shù)據(jù),求解模型,評價結果,簡化？,滿意？,Yes,No,No,8,四、運籌學的發(fā)展趨勢,運籌學的危機 脫離實際應用，陷入數(shù)學陷阱 IT對運籌學的影響 MIS, DSS, MRP-II, CIMS, ERP OR Dept. Dept. Of OR & IS 運籌學與行為科學結合 群決策和談判 對策理論 多層規(guī)劃 合理性分析 服務行業(yè)中的應用 金融服務業(yè) 信息、電信服務業(yè) 醫(yī)院管理,9,四、運籌學的發(fā)展趨勢,軟計算 面向強復雜系統(tǒng)的計算、實時控制、知識推理 智能算法：模擬退火、遺傳算法、人工神經(jīng)網(wǎng)絡、戒律算法等 系統(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、合理下料問題 設 xj 分別代表采用切割方案18的套數(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,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 個約束為 型，在不等式左邊增加一個非負的變量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 個約束行 “基”的概念 在標準型中，技術系數(shù)矩陣有 n+m 列，即 A = ( P1, P2 , , Pn+m ) A中線性獨立的 m 列，構成該標準型的一個基，即 B = ( P1 , P2 , , Pm )， | B | 0 P1 , P2 , , Pm 稱為基向量 與基向量對應的變量稱為基變量，記為 XB = ( x1 , x2 , , xm )T，其余的變量稱為非基變量，記為 XN = ( xm+1 , xm+2 , , xm+n ) T ， 故有 X = XB + XN 最多有 個基,23,關于標準型解的若干基本概念：,可行解與非可行解 滿足約束條件和非負條件的解 X 稱為可行解，滿足約束條件但不滿足非負條件的解 X 稱為非可行解 基礎解 令非基變量 XN = 0，求得基變量 XB的值稱為基礎解 即 XB = B1 b XB 是基礎解的必要條件為XB 的非零分量個數(shù) m 基礎可行解 基礎解 XB 的非零分量都 0 時，稱為基礎可行解，否則為基礎非可行解 基礎可行解的非零分量個數(shù) m 時，稱為退化解,24,線性規(guī)劃標準型問題解的關系,約束方程的 解空間,基礎解,可行解,非可行解,基礎 可行解,退化解,25,可行解、基礎解和基礎可行解舉例,26,1.2.2 單純型法的基本思路,27,1.2.3 單純型表及其格式,28,例1.2.2 試列出下面線性規(guī)劃問題的初始單純型表,29,關于檢驗數(shù)的數(shù)學解釋,設 B 是初始可行基，則目標函數(shù)可寫為兩部分(1) 約束條件也寫為兩部分，經(jīng)整理得 XB 的表達式(2)，注意 XB中含有非基變量作參數(shù) 把 XB 代入目標函數(shù)，整理得到(3)式 第 j 個非基變量的機會成本如(4)式 若有cjzj0, 則未達到最優(yōu),30,1.2.4 標準型的單純型算法,找初始基礎可行基 對于(max,)，松弛變量對應的列構成一個單位陣 若有 bi 0 中找最大者，選中者稱為入變量， xj* 第j*列稱為主列 確定入變量的最大值和出變量 最小比例原則,31,1.2.4 標準型的單純型算法,確定入變量的最大值和出變量 設第 i* 行使 最小，則第 i* 行對應的基變量稱為出變量，第 i* 行稱為主行 迭代過程 主行 i* 行與主列 j* 相交的元素ai*j* 稱為主元，迭代以主元為中心進行 迭代的實質是線性變換，即要將主元 ai*j*變?yōu)?，主列上其它元素變?yōu)?，變換步驟如下： (1)變換主行,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, OBJ=1700,35,單純型表中元素的幾點說明,任何時候，基變量對應的列都構成一個單位矩陣 當前表中的 b 列表示當前基變量的解值，通過變換 B 1 b 得到 (資源已變成產品) 當前非基變量對應的向量可通過變換 B 1 AN 得到， 表示第 j 個變量對第 i 行對應的基變量的消耗率 非基變量的機會成本由 給出 注意基變量所對應的行,36,1.3 人工變量的引入及其解法 1.3.1 當約束條件為“”型，引入剩余變量和人工變量,由于所添加的剩余變量的技術系數(shù)為1，不能作為初始可行基變量，為此引入一個人為的變量（注意，此時約束條件已為“=”型），以便取得初始基變量，故稱為人工變量 由于人工變量在原問題的解中是不能存在的，應盡快被迭代出去，因此人工變量在目標函數(shù)中對應的價值系數(shù)應具有懲罰性，稱為罰系數(shù)。罰系數(shù)的取值視解法而定 兩種方法 大M法 二階段法,37,1.3.2 大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法 二階段法手算可能容易,40,1.3.3 二階段法的求解過程,第一階段的任務是將人工變量盡快迭代出去，從而找到一個沒有人工變量的基礎可行解 第二階段以第一階段得到的基礎可行解為初始解，采用原單純型法求解 若第一階段結束時，人工變量仍在基變量中，則原問題無解 為了簡化計算，在第一階段重新定義價值系數(shù)如下：,41,表1.3.2 用二階段法求解例1.3.1的第一階段,42,表1.3.2 用二階段法求解例1.3.1的第二階段,最優(yōu)解對應的B1在哪？,43,1.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)解，這些解在同一個超平面上，且該平面與目標函數(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 關于無可行解