第一章-隨機(jī)事件及其概率

1、運(yùn)籌學(xué),,教材：運(yùn)籌學(xué)基礎(chǔ)和應(yīng)用,,參考文獻(xiàn),《運(yùn)籌學(xué)》,清華大學(xué)出版社《運(yùn)籌與管理》,中國運(yùn)籌學(xué)會(huì)會(huì)刊,核心刊物《系統(tǒng)工程理論和實(shí)踐》,中國系統(tǒng)工程學(xué)會(huì)會(huì)刊,核心刊物《系統(tǒng)工程》,湖南系統(tǒng)工程學(xué)會(huì)會(huì)刊,運(yùn)籌學(xué)一詞的來源,運(yùn)籌學(xué)一詞起源于二十世紀(jì)三十年代.運(yùn)籌學(xué)一詞的英文原名是Operations Research(縮寫為O.R).可直譯為“運(yùn)用研究”,“作業(yè)研究”.1957年我國從“夫運(yùn)籌帷幄之中,決勝于千里之外”(見《史記

2、?高祖本記》)這句古語中摘取“運(yùn)籌”二字,將O.R正式譯成”運(yùn)籌學(xué)”,包含運(yùn)用籌劃,以策略取勝的意義.,運(yùn)籌學(xué)的定義,運(yùn)籌學(xué)是一門應(yīng)用于管理有組織系統(tǒng)的科學(xué),它為掌握這類系統(tǒng)的人提供決策目標(biāo)和數(shù)量分析的工具(大英百科全書).運(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)最有效的管理(中國企業(yè)管理百科全書).運(yùn)籌學(xué)是一種給出問題不壞答案的藝術(shù)，否則的話問題的結(jié)

3、果會(huì)更壞。,運(yùn)籌學(xué)的定義,運(yùn)籌學(xué)是一門新興的邊緣科學(xué), 它使用數(shù)學(xué)方法，利用計(jì)算機(jī)等現(xiàn)代化工具，把復(fù)雜的研究對(duì)象當(dāng)作綜合系統(tǒng),進(jìn)行定量分析,從整體最優(yōu)出發(fā),提出一個(gè)最優(yōu)的可行方案,提供給執(zhí)行機(jī)構(gòu)作為決策的參考.,早期運(yùn)籌學(xué)思想,齊王和田忌賽馬的故事丁渭修皇宮的故事(丁渭修宮,一舉而三役濟(jì))丹麥工程師A.K.Erlang研究電話占線問題哥尼斯堡七橋問題E.Zermelo用集合論研究下棋問題美國Thomas Edison在第一次世

4、界大戰(zhàn)中研究商船航行策略,防止敵潛艇的攻擊.,運(yùn)籌學(xué)的發(fā)展簡史(軍事運(yùn)籌學(xué)),1938年7月,為作好反侵略戰(zhàn)爭的準(zhǔn)備工作,波得塞(Bawdsey)雷達(dá)站的負(fù)責(zé)人羅伊(A.P.Rowe)提出進(jìn)行整個(gè)防空作戰(zhàn)系統(tǒng)運(yùn)行的研究,并用”O(jiān)perational Research”一詞作為這方面工作的描述.這就是”運(yùn)籌學(xué)”一詞的來源.1939年,蘇聯(lián)經(jīng)濟(jì)學(xué)家康托洛維奇出版了《生產(chǎn)組織和計(jì)劃中的數(shù)學(xué)方法》,首次提出了線性規(guī)劃數(shù)學(xué)模型及”解乘數(shù)法”的求

5、解方法.,運(yùn)籌學(xué)發(fā)展簡史(戰(zhàn)后運(yùn)籌學(xué)),1945年---20世紀(jì)五十年代初:稱為創(chuàng)建時(shí)期.成立運(yùn)籌學(xué)會(huì):英國在1948年成立”運(yùn)籌學(xué)俱樂部”,美國在1952年成立運(yùn)籌學(xué)會(huì).運(yùn)籌學(xué)成為大學(xué)課程:英國伯明翰大學(xué),美國麻省理工學(xué)院開設(shè)運(yùn)籌學(xué)課程.最輝煌的成果:1947年美國Dantzig提出解線性規(guī)劃的單純形法;1951年美國R.Bellman提出了解決多階段決策問題的動(dòng)態(tài)規(guī)劃方法;1959年R.Gomory提出了解整數(shù)規(guī)劃的割平面法等

6、.,運(yùn)籌學(xué)的成長期(1950—1970),決策論,博弈論,排隊(duì)論,網(wǎng)絡(luò)分析,目標(biāo)規(guī)劃等運(yùn)籌學(xué)分支相繼出現(xiàn).電子計(jì)算機(jī)技術(shù)的迅速發(fā)展,促進(jìn)了運(yùn)籌學(xué)的推廣和應(yīng)用.1959年成立國際運(yùn)籌學(xué)會(huì).,運(yùn)籌學(xué)的發(fā)展普及期(70年代以來),運(yùn)籌學(xué)進(jìn)一步細(xì)分為各分支,專業(yè)學(xué)術(shù)團(tuán)體迅速增多,運(yùn)籌學(xué)書籍和期刊大量出版,更多的大學(xué)將運(yùn)籌學(xué)納入教學(xué)計(jì)劃.運(yùn)籌學(xué)理論深入發(fā)展:如線性規(guī)劃的橢球算法(蘇聯(lián),哈奇揚(yáng),1979),Karmakar算法(印度,Karm

7、akar,1984).第三代計(jì)算機(jī)的發(fā)展促使運(yùn)籌學(xué)應(yīng)用于復(fù)雜的大系統(tǒng)的研究(城市交通,環(huán)境污染,國民經(jīng)濟(jì)計(jì)劃等),中國運(yùn)籌學(xué)的發(fā)展概況,20世紀(jì)50年代后期由錢學(xué)森,華羅庚,許國志等科學(xué)家引入中國.中國運(yùn)籌學(xué)家在打麥場選址問題,中國郵遞員問題,優(yōu)選法以及統(tǒng)籌方法等方面有突出的貢獻(xiàn).中國運(yùn)籌學(xué)會(huì)于1980年成立,1982年參加了國際運(yùn)籌學(xué)會(huì),1991年中國運(yùn)籌學(xué)會(huì)成為國家一級(jí)學(xué)會(huì).,運(yùn)籌學(xué)研究的特點(diǎn),系統(tǒng)的整體優(yōu)化多學(xué)科的配合模

8、型方法的應(yīng)用:確定一組決策變量使目標(biāo)函數(shù) 達(dá)到最優(yōu)（optimization)并受到一組約束條件的限制,模型方法應(yīng)用的步驟,分析和表述問題建立數(shù)學(xué)模型對(duì)模型求解對(duì)模型和由模型導(dǎo)出的解進(jìn)行檢驗(yàn)建立起對(duì)解的有效控制方案的實(shí)施,運(yùn)籌學(xué)的重要分支,線性規(guī)劃(Linear programming)運(yùn)輸問題(Transportation problem)目標(biāo)規(guī)劃(Goal programming)整

9、數(shù)規(guī)劃(Integer programming)分配問題(Assignment problem)動(dòng)態(tài)規(guī)劃(Dynamic programming),運(yùn)籌學(xué)的重要分支,圖和網(wǎng)絡(luò)模型(Graph and network modeling)存儲(chǔ)論(Inventory theory)博弈論(Game theory)決策論(Decision theory)排隊(duì)論(Queueing theory),計(jì)算機(jī)求解方法,使用WinQSB初步

10、了解一下WinQSB,第一章 線性規(guī)劃(LP),線性規(guī)劃問題的數(shù)學(xué)模型圖解法單純形法原理單純形法的計(jì)算步驟WINQSB簡介(LP部分),第一章 線性規(guī)劃(LP),教學(xué)目的與要求:通過學(xué)習(xí)使學(xué)生掌握LP的建模方法,熟練地使用單純形法和WINQSB軟件求解LP問題.重點(diǎn)與難點(diǎn):重點(diǎn)是LP的建模與解法;難點(diǎn)是單純形法的原理.教學(xué)方法:課堂講授為主并配合課件和WINQSB軟件.思考題,討論題,作業(yè):教材第一章習(xí)題 參考資

11、料:見前言.學(xué)時(shí)分配:8學(xué)時(shí).,第一章 線性規(guī)劃(LP),1939年蘇聯(lián)的經(jīng)濟(jì)學(xué)家Л.В.КОНТОРОВИЧ在《生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法》一書中，首次用線性規(guī)劃方法解決了生產(chǎn)組織與運(yùn)輸問題。1947年美國數(shù)學(xué)家G.B.Dantzig提出了線性規(guī)劃的數(shù)學(xué)模型，并給出了求解該模型的單純形法（Simplex method).這標(biāo)志著線性規(guī)劃這一運(yùn)籌學(xué)的重要分支的誕生。計(jì)算機(jī)的發(fā)展促進(jìn)了LP計(jì)算理論的發(fā)展，使其應(yīng)用更加廣泛和深入。

12、,線性規(guī)劃的應(yīng)用范圍,生產(chǎn)的組織與計(jì)劃問題運(yùn)輸問題合理下料問題配料問題生產(chǎn)布局問題特點(diǎn)：在現(xiàn)有條件下，統(tǒng)籌安排，使總的經(jīng)濟(jì)效益最好。,第1節(jié) 線性規(guī)劃的數(shù)學(xué)模型,例1 某工廠制造A,B兩種產(chǎn)品，它們的原材料單位消耗，單位利潤以及資源現(xiàn)有量如下表,,,問如何組織生產(chǎn)可使工廠獲得最大利潤？,如何建立數(shù)學(xué)模型？,1.選擇決策變量：設(shè)A，B兩種產(chǎn)品各生產(chǎn)個(gè)單位；,2.建立目標(biāo)函數(shù)：利潤函數(shù)是 求它

13、的最大值，即,3.生產(chǎn)的產(chǎn)量受到限制：,4.決策變量必須有非負(fù)限制：,綜合上述各點(diǎn)，該問題的數(shù)學(xué)模型如下,目標(biāo)函數(shù),約束條件,非負(fù)限制,注意：目標(biāo)函數(shù)和約束條件中變量的次數(shù)都是一次的，這樣的模型稱為線性規(guī)劃數(shù)學(xué)模型。,生產(chǎn)計(jì)劃安排的一般提法是：根據(jù)下列數(shù)據(jù)，如何安排生產(chǎn)使工廠獲得最大利潤。,,,,,資源,產(chǎn)品,消耗,,,資源現(xiàn)有量,單位產(chǎn)品利潤,建立數(shù)學(xué)模型,解：設(shè) 表示生產(chǎn)產(chǎn)品的單位數(shù)，則有如下的

14、數(shù)學(xué)模型。,例2 設(shè)有某種物資從A，B，C三個(gè)產(chǎn)地調(diào)出，運(yùn)往甲，乙，丙三個(gè)需求地，其調(diào)運(yùn)量及運(yùn)價(jià)如下表：求一個(gè)運(yùn)費(fèi)最省的調(diào)運(yùn)方案.,甲 乙 丙 調(diào)出量 A 2 4 5 7 B 1 3 4 4 C

15、 3 2 3 9調(diào)入量 6 8 6 （20）,,,,,調(diào)出,調(diào)入,運(yùn)價(jià),,,設(shè) 表示從i地調(diào)往j地的調(diào)運(yùn)量,i=1,2,3J=1,2,3.,一般地,產(chǎn)銷平衡運(yùn)輸問題的數(shù)學(xué)模型如下:,,,,,,,產(chǎn)量,銷量,產(chǎn)地,銷地,運(yùn)價(jià),建立數(shù)學(xué)模型:設(shè) 表示從i地調(diào)往j地的調(diào)運(yùn)量,i=1,2, …,m j=1,2,

16、…,n.,第2節(jié) 線性規(guī)劃問題解的性質(zhì)⒈ 兩個(gè)變量的線性規(guī)劃問題的圖解法,幾個(gè)基本概念:⑴ 滿足所有約束條件的解稱為LP問題的可行解;所有可行解的集合稱為可行解集.⑵ 使目標(biāo)函數(shù)達(dá)到最優(yōu)的可行解稱為LP問題的最優(yōu)解.,問題:線性規(guī)劃是一個(gè)帶有約束條件的極值問題,能否用微積分方法求解?,例1 用圖解法求解下面的LP問題,,,,,,,,,,目標(biāo)函數(shù)等值線,此點(diǎn)為LP的最優(yōu)解,目標(biāo)函數(shù)等值線,可行解集,,計(jì)算出這個(gè)最優(yōu)解:,上述作法稱

17、為LP的圖解法.,本問題有唯一最優(yōu)解.,例2 用圖解法解下面的線性規(guī)劃,,,,,,,,,,目標(biāo)函數(shù)等值線,目標(biāo)函數(shù)等值線,計(jì)算出LP的最優(yōu)解及目標(biāo)函數(shù)最優(yōu)值:,除A,B兩個(gè)最優(yōu)解外,AB線段上的所有點(diǎn)都是LP的最優(yōu)解.本問題有無窮多最優(yōu)解.,例3 用圖解法解下面的線性規(guī)劃,,,,,,,無界的可行解集,此題有可行解但無最優(yōu)解,,例4 用圖解法解下面的線性規(guī)劃,,,,,無可行解,,,,,本題無可行解,更無最優(yōu)解,有唯一最優(yōu)解,這個(gè)最優(yōu)

18、解一定在可行解集合的某一頂點(diǎn)上達(dá)到;有無窮多最優(yōu)解,最優(yōu)解充滿一個(gè)線段,可以用它的兩個(gè)端點(diǎn)作為代表;有可行解,但無最優(yōu)解;無可行解.,小結(jié):兩個(gè)變量的LP圖解法有如下四種情況,⒉ 線性規(guī)劃問題的標(biāo)準(zhǔn)形式,規(guī)定:,⑴ 求目標(biāo)函數(shù)的最大值為標(biāo)準(zhǔn)形,即目標(biāo)函數(shù)為maxS.如果問題是求minS時(shí),可設(shè) 求 , 相當(dāng)于求minS.,⑵ 以等式約束為標(biāo)準(zhǔn)形.設(shè)第k個(gè)等式為,⑶ LP中所有的變量都有非負(fù)

19、限制.如果實(shí)際問題中的LP里某個(gè)變量無非負(fù)限制,可如下處理:,（4）約束條件右端常數(shù)項(xiàng)全為非負(fù)值。,根據(jù)以上的規(guī)定,LP的標(biāo)準(zhǔn)形為,兩種縮寫形式:,矩陣表示法:,3. LP問題解的性質(zhì),⑴ 幾個(gè)概念① 凸集:若連接n維點(diǎn)集S中任意兩點(diǎn) 的線段仍在S內(nèi),則稱S為凸集.即,,,,凸集,凸集,不是凸集,極點(diǎn),,,,,,,,,,,② 極點(diǎn):若凸集S中的點(diǎn)x,不能成為S中任何線段的內(nèi)點(diǎn),則稱x為S的極點(diǎn).,③ 設(shè)

20、 為LP的一個(gè)可行解,若或 的非零分量對(duì)應(yīng)的A中列向量線性無關(guān),則稱它為基礎(chǔ)可行解.由這些列向量組成的矩陣稱為基矩陣,與這些列向量對(duì)應(yīng)的變量稱為基變量,其余的變量稱為非基變量.,,使目標(biāo)函數(shù)值達(dá)到最大值的可行解稱為最優(yōu)解;使目標(biāo)函數(shù)達(dá)到最大值的基礎(chǔ)可行解稱為基礎(chǔ)最優(yōu)解.,例 設(shè)線性規(guī)劃為,則下述解中為基礎(chǔ)可行解的是 。A.(2,0,4,0);B.(6,0,3,3);C.(3

21、,2,3,2);D.(0,6,0,0),,解:容易驗(yàn)證D 是LP 的可行解,同時(shí)它對(duì)應(yīng)的系數(shù)矩陣中第二列線性無關(guān)。,,,,可行解集,基礎(chǔ)可行解,最優(yōu)解,基礎(chǔ)最優(yōu)解,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,目標(biāo)函數(shù),約束條件,行列式≠0基矩陣,右邊常數(shù),=,⑵ 幾個(gè)重要定理,定理1 線性規(guī)劃問題的可行解集為凸集,即連接線性規(guī)劃問題任意兩個(gè)可行解的線段上的點(diǎn)仍為可行解.,定

22、理2 可行解集S中的點(diǎn)x是極點(diǎn)的充要條件是x為基礎(chǔ)可行解(簡單地說,凸多邊形的頂點(diǎn)就是基礎(chǔ)可行解).,定理3 線性規(guī)劃的目標(biāo)函數(shù)的最優(yōu)值,一定可在極點(diǎn)上達(dá)到.,第3節(jié) 單純形方法(Simplex method),⒈ 用消去法解LP問題,解:引入松弛變量將其化為標(biāo)準(zhǔn)形,由此可以得出:目標(biāo)函數(shù)中非基變量的系數(shù)可以用來檢驗(yàn)線性規(guī)劃是否已得到最優(yōu)解了.,第三步:換基迭代,第四步:求新的基礎(chǔ)可行解,2. 單純形方法 給定LP問題,設(shè)

23、A是 的矩陣,且R(A)=m (m<n),即A是行滿秩的.于是,A中一定存在m列線性無關(guān),這m行m列構(gòu)成A的一個(gè)非奇異子矩陣,稱為線性規(guī)劃的一個(gè)基矩陣B(簡稱為一個(gè)基),基矩陣B各列對(duì)應(yīng)的變量稱為基變量.為方便起見,不妨設(shè)A的前m列線性無關(guān).現(xiàn)將A,B,C,x按一定規(guī)則作成分塊 矩陣.,設(shè),類似地,,設(shè),下面證明,線性規(guī)劃的有解判別定理:,3. 單純形表,基變量取值,檢驗(yàn)數(shù),基變量,基變量在目標(biāo)函數(shù)中的系數(shù),單純

24、形法的計(jì)算步驟:,第一步:列出單純形表,例1.用單純形法解線性規(guī)劃,解:⑴化為標(biāo)準(zhǔn)形,⑵計(jì)算,⑶填寫單純形表:,,,,,⑷ 換基迭代檢驗(yàn)數(shù)有兩種情況:① 所有檢驗(yàn)數(shù)小于等于零,則基B已是最優(yōu)基,得到最優(yōu)表及最優(yōu)解,停止計(jì)算;② 有某些檢驗(yàn)數(shù)為正值,此表不是最優(yōu)表即基B不是最優(yōu)基,則應(yīng)進(jìn)行換基迭代.,換基迭代的步驟:,ⅰ.選取入基變量:設(shè) 則相應(yīng)的非基變量 為入基變量,簡稱“

25、入基”.如果j不唯一,可選取較大的 值對(duì)應(yīng)的非基變量入基.,ⅱ.求主元素并確定出基變量:觀察在入基變量 所對(duì)應(yīng)的 中的第j列,如果該列所有的分量均小于等于零,則該LP問題無最優(yōu)解(定理).如果該列存在正分量,則以這些正分量為分母,以這些正分量所在行中對(duì)應(yīng)的基變量取值為分子,求出這些比值中的最小值,該最小值對(duì)應(yīng)的基變量為出基變量,簡稱“出基”,出入基交叉點(diǎn)上的元素稱為主元素或軸心項(xiàng),用方框?qū)⑵淇蚱饋?/p>

26、. 這種求出基變量的方法稱為 法則.,ⅲ.換基迭代:利用矩陣的初等變換,將主元素變?yōu)?,將其所在列的其余元素變?yōu)?,得一張新單純形表.重復(fù)上述步驟,經(jīng)過有限次換基迭代,一定可得到最優(yōu)解.,,,,,,,該表檢驗(yàn)數(shù)全部小于等于零,稱此表為最優(yōu)表.其結(jié)果如下表示:,注意:松弛變量的取值不必寫出.本題迭代2次.,問題:表1中我們選取了 入基,如果選取 入基結(jié)果又如何呢?,,,,,,,,,,,,,,路徑1,路徑2,結(jié)

27、論:1.每一個(gè)單純形表對(duì)應(yīng)一個(gè)極點(diǎn),表一對(duì)應(yīng)黃點(diǎn);表二對(duì)應(yīng)綠點(diǎn);表三對(duì)應(yīng)藍(lán)點(diǎn). 2.一般來說,路徑不同,迭代次數(shù)可能不同.,說明:(1)如果單純形表中的基變量取值皆為正數(shù),稱這個(gè)基可行解為非退化解.若LP的所有基可形解都是非退化的,則LP經(jīng)過有限次迭代可達(dá)到最優(yōu).(2)如果單純形表中的基變量取值有的為零時(shí),稱為LP的退化解,此時(shí)稱LP是退化的,理論上認(rèn)為這種線性規(guī)劃在迭代過程中可能產(chǎn)生循環(huán),從而得不到最優(yōu)解.為避免循環(huán),常采用197

28、6年R.G.Bland提出Bland法則:⒈單純形表中有若干個(gè)檢驗(yàn)數(shù) 時(shí),取下標(biāo)號(hào)小的非基變量入基; ⒉ 用 法則選取出基變量時(shí),若比值相同,則選取下標(biāo)號(hào)小的基變量出基.,(3) 當(dāng)所有的檢驗(yàn)數(shù)全部小于等于零時(shí),若有某個(gè)非基變量的檢驗(yàn)數(shù)也是零,則該線性規(guī)劃有無窮多組解,否則有唯一解.,例2.解線性規(guī)劃,先將線性規(guī)劃化為標(biāo)準(zhǔn)型,解：,注意到 對(duì)應(yīng)A中的列向量恰好構(gòu)成三階單位方陣,可以作

29、為第一個(gè)可行基.,,,,,,,,,,,最優(yōu)解為 最優(yōu)值S=-20,書上的作法:,線性規(guī)劃問題的標(biāo)準(zhǔn)形式:,單純形法的計(jì)算步驟:,第一步:列出單純形表,說明:表中設(shè)系數(shù)矩陣中的前m列構(gòu)成單位陣,即,表中 為非基變量,它下面的數(shù)據(jù)由下式算出:,表中基變量的檢驗(yàn)數(shù)皆為零;而非基變量 的檢驗(yàn)數(shù) 由下面的方法計(jì)算:,用 上面的數(shù)字 減去 下面這一列數(shù)字與 中同行的數(shù)字分別

30、相乘的結(jié)果.,第二步:進(jìn)行最優(yōu)性檢驗(yàn),如果表中所有的檢驗(yàn)數(shù) 則表中的基可行解就是問題的最優(yōu)解,計(jì)算結(jié)束.否則轉(zhuǎn)下一步.,第三步:換基迭代,該步與我們講的方法相同.,例,解:化為標(biāo)準(zhǔn)形,,,,表中的檢驗(yàn)數(shù)全部小于等于零,該表為最優(yōu)表.最優(yōu)解為,目標(biāo)函數(shù)的最優(yōu)值計(jì)算出的,3. 第一個(gè)可行基的求法,以上各例的系數(shù)矩陣A中,都存在一個(gè)m階單位陣,因此很容易用單純行法求解.但是大多數(shù)LP問題并不是這樣.,例 3,化為標(biāo)準(zhǔn)形,

31、,,,,,,,,,說明:關(guān)于大M法的幾種情況,1. 表4稱為終止表.在終止表中,如果基變量里不含有人工變量,則LP一定有最優(yōu)解;,2. 在終止表中,如果基變量里含有人工變量,但是人工變量取值為零,則LP有最優(yōu)解;,3. 在終止表中,如果基變量里含有人工變量,且人工變量取值大于零,則LP無最優(yōu)解.,4.關(guān)于WinQSB,作業(yè):,提示：先改為最大化標(biāo)準(zhǔn)型再用大M 法（添加-M),線性規(guī)劃的對(duì)偶理論,對(duì)偶問題的提出原問題與對(duì)偶問題對(duì)偶問題

32、的基本性質(zhì)影子價(jià)格對(duì)偶單純形法靈敏度分析,線性規(guī)劃的對(duì)偶理論,教學(xué)目的與要求:了解對(duì)偶問題產(chǎn)生的經(jīng)濟(jì)背景,熟練掌握對(duì)偶單純形法和影子價(jià)格概念,熟練掌握靈敏度分析方法.重點(diǎn)與難點(diǎn):重點(diǎn)同上,難點(diǎn)是對(duì)偶理論.教學(xué)方法:課堂講授為主并配合課件和WINQSB軟件.思考題,討論題,作業(yè):教材第二章習(xí)題 參考資料:見前言.學(xué)時(shí)分配:8學(xué)時(shí).,第4節(jié) 對(duì)偶線性規(guī)劃問題,對(duì)偶問題的提出內(nèi)容一致,而從相反的角度提出的一對(duì)問題,稱為一對(duì)

33、對(duì)偶問題.,例1.某工廠在計(jì)劃期內(nèi)安排生產(chǎn)甲,乙兩種產(chǎn)品,這些產(chǎn)品分別需要在A,B,C,D四種不同的設(shè)備上加工.產(chǎn)品在各臺(tái)設(shè)備上需要加工的臺(tái)時(shí)數(shù)是:,,,,A B C D,甲 2 1 4 0乙 2 2 0 4,產(chǎn)品,設(shè)備,已知各設(shè)備的有效臺(tái)時(shí)數(shù)分別是12,8,16,12.生產(chǎn)一件產(chǎn)品甲獲利2(萬元),一件產(chǎn)品乙獲利3(萬元).如何安排生產(chǎn)使工廠獲利最大.,解

34、:,從相反的角度提出問題:工廠決策者決定不生產(chǎn)甲乙兩種產(chǎn)品,而對(duì)設(shè)備的有效臺(tái)時(shí)數(shù)進(jìn)行出租,用收取加工費(fèi)的方法獲得最大利潤.應(yīng)如何考慮?,決策者首先要考慮給每一種設(shè)備出租一個(gè)臺(tái)時(shí)的定價(jià).在何種價(jià)格下,決策者接受外加工呢?,建立LP數(shù)學(xué)模型,顯然,當(dāng)maxZ=minW時(shí),對(duì)于決策者來說這兩種方案都是最優(yōu)的.,,,2.對(duì)偶線性規(guī)劃的模型,特點(diǎn):1.一個(gè)規(guī)劃中的每一個(gè)約束,對(duì)應(yīng)對(duì)偶規(guī)劃中的一個(gè)決策變量; 2.一個(gè)規(guī)劃中目標(biāo)函數(shù)系數(shù)

35、恰為對(duì)偶規(guī)劃約束條件右端常數(shù)項(xiàng); 3.一個(gè)規(guī)劃求最小化,而對(duì)偶規(guī)劃求最大化; 4.目標(biāo)函數(shù)求最小化搭配”》”約束;目標(biāo)函數(shù)求最大化搭配”《”約束; 5.兩個(gè)規(guī)劃都有非負(fù)限制. 6.兩個(gè)規(guī)劃約束方程組的系數(shù)矩陣互為轉(zhuǎn)置矩陣.,例1 寫出下面原規(guī)劃的對(duì)偶規(guī)劃,解:,例2 寫出下面原規(guī)劃的對(duì)偶規(guī)劃,解:,定理1 如果線性規(guī)劃中第k個(gè)約束條件是等式,則它的對(duì)偶規(guī)劃中的第k個(gè)變量無

36、非負(fù)限制,反之亦然.,例3 寫出下面原規(guī)劃的對(duì)偶規(guī)劃,解:,例4 寫出下列線性規(guī)劃的對(duì)偶問題（p55例2）,,,,,3.對(duì)偶線性規(guī)劃的性質(zhì),定理2(弱對(duì)偶定理) 對(duì)偶規(guī)劃(1),(2)有最優(yōu)解的充分必要條件是它們同時(shí)有可行解.,定理3(最優(yōu)性定理) 如果 分別是(1),(2)的可行解,且 則 分別是(1),(2)的最優(yōu)解.,證明(定理2):必要性是顯然的。充分性：

37、設(shè)（1），（2）分別有可行解 ，對(duì)（1）的任一可行解 ，有,即S=CX在可行域內(nèi)有下界，于是一定有最小值，所以（1）的最優(yōu)解存在。同理可證另一結(jié)論。,例 已知線性規(guī)劃問題,用對(duì)偶理論證明該問題的最優(yōu)解的目標(biāo)函數(shù)值不大于25。,解：寫出它的對(duì)偶問題,任取可行解 （滿足所有約束條件）且 。,有定理2可知，,定理4 （強(qiáng)對(duì)偶定理）如果對(duì)偶規(guī)劃(1),(2)中有一個(gè)有最優(yōu)解,那

38、么另一個(gè)也一定有最優(yōu)解.并且兩個(gè)規(guī)劃的目標(biāo)函數(shù)的最優(yōu)值相等.,定理5 （互補(bǔ)松弛性質(zhì)）在線性規(guī)劃問題的最優(yōu)解中，如果對(duì)應(yīng)某一約束條件的對(duì)偶變量值為非零，則該約束條件取嚴(yán)格等式；反之如果約束條件取嚴(yán)格不等式，則其對(duì)應(yīng)的對(duì)偶變量一定為零。即如果,給定,則對(duì)偶規(guī)劃為,下面我們驗(yàn)證定理4：,分別化為標(biāo)準(zhǔn)形,,,重要結(jié)論:給出一對(duì)對(duì)偶線性規(guī)劃,只需解其中一個(gè)線性規(guī)劃得出最優(yōu)解和目標(biāo)函數(shù)最優(yōu)值.它的對(duì)偶規(guī)劃的目標(biāo)函數(shù)最優(yōu)值與原規(guī)劃的目標(biāo)函數(shù)值相同,

39、而最優(yōu)解可用原規(guī)劃最優(yōu)表中的松弛變量的檢驗(yàn)數(shù)乘以”-1”得到(教材中的檢驗(yàn)數(shù)的計(jì)算改為 ，故不用乘-1）。,4.影子價(jià)格( Shadow price),根據(jù)最優(yōu)性定理, 是原規(guī)劃約束條件右端項(xiàng),它代表第i種資源的擁有量,對(duì)偶變量 表示對(duì)一個(gè)單位第i種資源的估價(jià).它不是該資源的市場價(jià)格,而是根據(jù)該資源在生產(chǎn)中做出的貢獻(xiàn)而作的估價(jià),稱為影子價(jià)格.,,關(guān)于影子價(jià)格的幾個(gè)重要結(jié)論:,影子價(jià)格的求法:對(duì)偶問題的

40、最優(yōu)解為原問題約束條件右端常數(shù)項(xiàng)的影子價(jià)格. 具體作法:將原規(guī)劃最優(yōu)表中的松弛變量的檢驗(yàn)數(shù)乘以負(fù)1,就得到了對(duì)應(yīng)于原規(guī)劃約束條件右端常數(shù)項(xiàng)(即資源限制量)的影子價(jià)格.,(2) 影子價(jià)格是一種邊際價(jià)格(Boundary price),在上式中對(duì) 求偏導(dǎo)數(shù)得,這說明, 的值相當(dāng)于在給定的生產(chǎn)條件下, 每增加一個(gè)單位時(shí),目標(biāo)函數(shù)S的增加量,即總收入的變化率(總收入增加一個(gè)影子價(jià)格值).,(3) 影子價(jià)格是一種機(jī)會(huì)成

41、本(Opportunity cost),在純市場經(jīng)濟(jì)條件下,當(dāng)某種資源的市場價(jià)格低于影子價(jià)格時(shí),可以買進(jìn)這種資源擴(kuò)大生產(chǎn);相反當(dāng)市場價(jià)格高于影子價(jià)格時(shí),可賣出這種資源獲取更大的利潤.,注意:由于影子價(jià)格可為決策者提供決策依據(jù),因此各種資源的影子價(jià)格應(yīng)當(dāng)保密.,(4).影子價(jià)格>0時(shí),由互補(bǔ)松弛性質(zhì)可知，該約束條件為等式,這說明此種資源已被充分利用.,在生產(chǎn)過程中，某種資源是過剩資源,沒有被充分利用，由互補(bǔ)松弛性質(zhì)可知，該種資源的影

42、子價(jià)格為零。,影子價(jià)格=0不是說該資源沒有價(jià)格,而是表明該資源已是過剩資源,再買進(jìn)此資源不會(huì)增加總收入.,例 下列關(guān)于線性規(guī)劃原問題與其對(duì)偶問題之間關(guān)系的敘述不正確的是（ ）若原問題有最優(yōu)解，則其對(duì)偶問題也有最優(yōu)解設(shè) 為對(duì)偶問題的最優(yōu)解，若 ，說明在最優(yōu)生產(chǎn)計(jì)劃中第i種資源一定有剩余任何線性規(guī)劃問題存在唯一的對(duì)偶問題如果原問題與對(duì)偶問題都有可行解，則它們必有最優(yōu)解,例 某工廠兩種產(chǎn)品生產(chǎn)的利潤最大化的

43、LP 模型為,最優(yōu)表如下：,問題：若該工廠可以通過加班的方法獲得更多的裝配時(shí)間，則工廠愿意為之付出的加班費(fèi)是多少？在加班費(fèi)為50元/小時(shí)的情況下，工廠可獲得的利潤最大增加額是多少？,答：三種資源的影子價(jià)格分別是60、0、40。特別地，第一種資源的影子價(jià)格是60，這是工廠愿意付出的加班費(fèi)，若付加班費(fèi)50元/小時(shí)，工廠利潤增加額是10元/小時(shí)。,進(jìn)一步分析:,關(guān)于影子價(jià)格的應(yīng)用:,丹捷格:分解原理J.科爾納:影子價(jià)格法,4. 對(duì)偶單純形法

44、,定義:設(shè) 是線性規(guī)劃的一組基,它對(duì)應(yīng)的基矩陣是B,對(duì)應(yīng)的基解為 ,如果這組基對(duì)應(yīng)的檢驗(yàn)數(shù)全部小于等于零,即則稱這組基為該線性規(guī)劃的一組正則基. 為正則解.,線性規(guī)劃的對(duì)偶單純形法是從第一個(gè)正則解開始迭代的.,對(duì)偶單純形法的迭代步驟:,從一個(gè)正則解開始,列出對(duì)偶單純形表;如基變量的取值全部大于等于零,則線性規(guī)劃已取得最優(yōu)解,計(jì)算結(jié)束,否則轉(zhuǎn)(3);在基變量中,挑選取

45、負(fù)值中最小的一個(gè),作為出基變量(若最小負(fù)值相同,可由Bland法則確定);在出基變量行中,如果非基變量的約束系數(shù)全部非負(fù),則原問題不存在可行解,否則轉(zhuǎn)(5);,(5)在出基變量行中,如果有些非基變量的約束系數(shù)為負(fù),則分別計(jì)算這些變量的檢驗(yàn)數(shù)與出基變量行中負(fù)系數(shù)的比值,比值最小者對(duì)應(yīng)的非基變量為入基變量(若比值相同,由Bland法則確定);(6) 出,入基交叉點(diǎn)上的元素為主元素,用方框框起來,將其變?yōu)?,用矩陣初等行變換將其所在列的

46、其余元素變?yōu)?得一新表,轉(zhuǎn)(2).,例1 利用對(duì)偶單純形法解下邊的線性規(guī)劃,解:首先將LP化為標(biāo)準(zhǔn)形,再變形為,基變量取值為,檢驗(yàn)數(shù),存在一組正則基,列出對(duì)偶單純形表:,,,,,,-2 -1 0 0 0,,,,,,5. 靈敏度分析,在大多數(shù)線性規(guī)劃中,其參數(shù)值是一些估計(jì)量,有時(shí)是作為政策決定的結(jié)果而出現(xiàn),這些決定是否正確,要經(jīng)過方案實(shí)施后的效果而定.在反映生產(chǎn)問題的線性規(guī)劃中,也由于生產(chǎn)技術(shù)條件,資源限額

47、,市場價(jià)格的變化使表示成本(或利潤)的目標(biāo)函數(shù)發(fā)生變化. 基于以上原因,只求出LP的最優(yōu)解是不夠的,還要研究這些參數(shù)的變化對(duì)最優(yōu)解產(chǎn)生的影響,或者說,這些參數(shù)在什么范圍內(nèi)變化時(shí),所求得的最優(yōu)解仍然有效.這就是靈敏度分析的內(nèi)容.,靈敏度分析的主要內(nèi)容,(1) 目標(biāo)函數(shù)系數(shù) 變化的靈敏度分析;,(2) 約束條件右端常數(shù)項(xiàng) 變化的靈敏度分析;,(3) 增加一個(gè)新決策變量的靈敏度分析;,(4) 增加一個(gè)新約束條件的靈敏度

48、分析.,例 某工廠用甲,乙兩種原料生產(chǎn)A,B,C,D四種產(chǎn)品,每種產(chǎn)品消耗的原料定額如下表,現(xiàn)有甲原料18噸,乙原料3噸.而每單位產(chǎn)品A,B,C,D的利潤分別是9萬元,8萬元,50萬元和19萬元.問如何組織生產(chǎn)才能使總利潤最大.,,,解:,最優(yōu)表為,進(jìn)行靈敏度分析:,1. 目標(biāo)函數(shù)系數(shù) 變化的靈敏度分析,,,(1) 是非基變量的系數(shù),(2) 是基變量的系數(shù),解不等式組,即當(dāng)C產(chǎn)品的利潤在(47.5,52)之間

49、時(shí),最優(yōu)解不變.,簡便方法:除基變量外,各非基變量的檢驗(yàn)數(shù)加上相應(yīng)行變號(hào)后的對(duì)應(yīng)系數(shù)為 的系數(shù),并列為小于等于零的不等式.,2. 約束條件右端常數(shù)項(xiàng)變化的靈敏度分析,,,例如第一種資源限制量發(fā)生變化:,即當(dāng) 時(shí),最優(yōu)基不變.,簡便方法:基變量的取值加上該資源的松弛變量所在列的系數(shù)為 的系數(shù),并列為大于等于零的不等式.,3.新增加一個(gè)變量的靈敏度分析,在本例中,考慮生產(chǎn)新產(chǎn)品E,已知生產(chǎn)E一

50、個(gè)單位消耗甲材料3個(gè)單位,乙材料1個(gè)單位,可獲利10萬元.問該產(chǎn)品是否有利于投產(chǎn)?如不利于投產(chǎn),問它的利潤是多少時(shí)才有利于投產(chǎn)?,引入新決策變量 表示產(chǎn)品E的產(chǎn)量,在目標(biāo)函數(shù)中 的系數(shù)為 ,在約束條件中新增加一列 .,產(chǎn)品E是否有利于投產(chǎn)關(guān)鍵要看 的檢驗(yàn)數(shù)的符號(hào),如果 ,說明 不能入基,原問題最優(yōu)解仍為最優(yōu)解,換言之,產(chǎn)品E不利于投產(chǎn);如果

51、 ,原問題沒有達(dá)到最優(yōu), 入基,則產(chǎn)品E可以生產(chǎn).,結(jié)論:產(chǎn)品E不利于投產(chǎn).,在什么情況下E能投入生產(chǎn)?,產(chǎn)品E的單位利潤超過 萬元時(shí)才有利于投產(chǎn).,4.新增加一個(gè)約束條件的靈敏度分析,例如增加約束條件,增加松弛變量使其變?yōu)榈仁?將該等式放在最優(yōu)表中的最后一行,同時(shí)增加一列,得一新表.,用紅字1將第三列和第四列化為單位列.,在用對(duì)偶單純形法求解得下一張表,下面介紹如何用winQSB對(duì)LP進(jìn)行靈敏度分