運(yùn)籌學(xué)OperationalResearch1.ppt

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