第一章線性規(guī)劃問題及單純型解法

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

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

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

4、業(yè)、政府和國防等方面解決發(fā)生的各種問題，其方法是發(fā)展一個(gè)科學(xué)的系統(tǒng)模式，并運(yùn)用這種模式預(yù)測(cè)，比較各種決策及其產(chǎn)生的后果，以幫助主管人員科學(xué)地決定工作方針和政策——英國運(yùn)籌學(xué)會(huì)運(yùn)籌學(xué)是應(yīng)用分析、試驗(yàn)、量化的方法對(duì)經(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)及研究

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

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

7、統(tǒng)仿真面向問題后勤(Logistics)全球供應(yīng)鏈管理電子商務(wù)：集成特性隨機(jī)和模糊 OR問題本身的不確定性人類知識(shí)的局限性,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、

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

9、,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ù)一律反號(hào)。令 f?(x) = -f(x) = -CX, 有 min f(x) = - max [- f(x)] = - max f ?(x)第i 個(gè)約束的bi 為負(fù)值，則該行左右兩端系數(shù)同時(shí)反號(hào)，同時(shí)不等號(hào)也要反向第i 個(gè)約束為 ? 型，在不等式左邊增加

10、一個(gè)非負(fù)的變量xn+i ，稱為松弛變量；同時(shí)令 cn+i = 0第i 個(gè)約束為 ? 型，在不等式左邊減去一個(gè)非負(fù)的變量xn+i ，稱為剩余變量；同時(shí)令 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 個(gè)變量， m 個(gè)約束行“基

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

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

13、條件為XB 的非零分量個(gè)數(shù) ? m基礎(chǔ)可行解基礎(chǔ)解 XB 的非零分量都 ? 0 時(shí)，稱為基礎(chǔ)可行解，否則為基礎(chǔ)非可行解基礎(chǔ)可行解的非零分量個(gè)數(shù) < m 時(shí)，稱為退化解,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ī)

14、劃問題的初始單純型表,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 個(gè)非基變量的機(jī)會(huì)成本如(4)式若有cj?zj>0, 則未達(dá)到最優(yōu),30,1.2.4 標(biāo)準(zhǔn)型的單純型算法,找初始基礎(chǔ)可行基對(duì)于(max,?)，松弛變量對(duì)應(yīng)的列構(gòu)成一個(gè)單位陣若有 bi 0 中找

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

16、變換主行,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ī)會(huì)成本 zj 和檢驗(yàn)數(shù) cj ? zj 6、返回步驟 2,34,表1.2.4 例1.2.2 單純型表的迭代過程,,,答：最優(yōu)解為 x1=20, x2=20, x3=0,

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

18、人工變量的引入及其解法 1.3.1 當(dāng)約束條件為“?”型，引入剩余變量和人工變量,由于所添加的剩余變量的技術(shù)系數(shù)為?1，不能作為初始可行基變量，為此引入一個(gè)人為的變量（注意，此時(shí)約束條件已為“=”型），以便取得初始基變量，故稱為人工變量由于人工變量在原問題的解中是不能存在的，應(yīng)盡快被迭代出去，因此人工變量在目標(biāo)函數(shù)中對(duì)應(yīng)的價(jià)值系數(shù)應(yīng)具有懲罰性，稱為罰系數(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法實(shí)質(zhì)上與原單純型法一樣，M 可看成一個(gè)很大的常數(shù)人工變量被迭代出去后一般就不會(huì)再成為基變量當(dāng)檢驗(yàn)數(shù)都滿足最優(yōu)條件，但基變量中仍有人工變量，說明原線性規(guī)劃問題無可行解大M法手算很不方便因此提出了二階段法計(jì)算機(jī)中常用大M法二階段法手算可能容

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

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

22、，這些解在同一個(gè)超平面上，且該平面與目標(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)于無可行解問題,約束條件互相矛盾，無可行域單純型表達(dá)到最優(yōu)解檢驗(yàn)條件時(shí)，人工變量仍在基變量中,49,表1.5.4 例1.5.4 第一階段的單純型表,50,1.4 修正單純型法,原單純型法迭代所需存儲(chǔ)量