1、運籌學,教材：運籌學基礎和應用,參考文獻,運籌學,清華大學出版社 運籌與管理,中國運籌學會會刊,核心刊物 系統(tǒng)工程理論和實踐,中國系統(tǒng)工程學會會刊,核心刊物 系統(tǒng)工程,湖南系統(tǒng)工程學會會刊,運籌學一詞的來源,運籌學一詞起源于二十世紀三十年代. 運籌學一詞的英文原名是Operations Research(縮寫為O.R).可直譯為“運用研究”,“作業(yè)研究”. 1957年我國從“夫運籌帷幄之中,決勝于千里之外”(見史記高祖本記)這句古語中摘取“運籌”二字,將O.R正式譯成”運籌學”,包含運用籌劃,以策略取勝的意義.,運籌學的定義,運籌學是一門應用于管理有組織系統(tǒng)的科學,它為掌握這類系統(tǒng)的人提供決策

2、目標和數(shù)量分析的工具(大英百科全書). 運籌學應用分析,試驗,量化的方法,對經(jīng)濟管理系統(tǒng)中的人,財,物等有限資源進行統(tǒng)籌安排,為決策者提供有依據(jù)的最優(yōu)方案,以實現(xiàn)最有效的管理(中國企業(yè)管理百科全書). 運籌學是一種給出問題不壞答案的藝術，否則的話問題的結果會更壞。,運籌學的定義,運籌學是一門新興的邊緣科學, 它使用數(shù)學方法，利用計算機等現(xiàn)代化工具，把復雜的研究對象當作綜合系統(tǒng),進行定量分析,從整體最優(yōu)出發(fā),提出一個最優(yōu)的可行方案,提供給執(zhí)行機構作為決策的參考.,早期運籌學思想,齊王和田忌賽馬的故事 丁渭修皇宮的故事(丁渭修宮,一舉而三役濟) 丹麥工程師A.K.Erlang研究電話占線問題 哥尼

3、斯堡七橋問題 E.Zermelo用集合論研究下棋問題 美國Thomas Edison在第一次世界大戰(zhàn)中研究商船航行策略,防止敵潛艇的攻擊.,運籌學的發(fā)展簡史(軍事運籌學),1938年7月,為作好反侵略戰(zhàn)爭的準備工作,波得塞(Bawdsey)雷達站的負責人羅伊(A.P.Rowe)提出進行整個防空作戰(zhàn)系統(tǒng)運行的研究,并用”O(jiān)perational Research”一詞作為這方面工作的描述.這就是”運籌學”一詞的來源. 1939年,蘇聯(lián)經(jīng)濟學家康托洛維奇出版了生產(chǎn)組織和計劃中的數(shù)學方法,首次提出了線性規(guī)劃數(shù)學模型及”解乘數(shù)法”的求解方法.,運籌學發(fā)展簡史(戰(zhàn)后運籌學),1945年-20世紀五十年代初

4、:稱為創(chuàng)建時期. 成立運籌學會:英國在1948年成立”運籌學俱樂部”,美國在1952年成立運籌學會. 運籌學成為大學課程:英國伯明翰大學,美國麻省理工學院開設運籌學課程. 最輝煌的成果:1947年美國Dantzig提出解線性規(guī)劃的單純形法;1951年美國R.Bellman提出了解決多階段決策問題的動態(tài)規(guī)劃方法;1959年R.Gomory提出了解整數(shù)規(guī)劃的割平面法等.,運籌學的成長期(19501970),決策論,博弈論,排隊論,網(wǎng)絡分析,目標規(guī)劃等運籌學分支相繼出現(xiàn). 電子計算機技術的迅速發(fā)展,促進了運籌學的推廣和應用. 1959年成立國際運籌學會.,運籌學的發(fā)展普及期(70年代以來),運籌學進

5、一步細分為各分支,專業(yè)學術團體迅速增多,運籌學書籍和期刊大量出版,更多的大學將運籌學納入教學計劃. 運籌學理論深入發(fā)展:如線性規(guī)劃的橢球算法(蘇聯(lián),哈奇揚,1979),Karmakar算法(印度,Karmakar,1984). 第三代計算機的發(fā)展促使運籌學應用于復雜的大系統(tǒng)的研究(城市交通,環(huán)境污染,國民經(jīng)濟計劃等),中國運籌學的發(fā)展概況,20世紀50年代后期由錢學森,華羅庚,許國志等科學家引入中國. 中國運籌學家在打麥場選址問題,中國郵遞員問題,優(yōu)選法以及統(tǒng)籌方法等方面有突出的貢獻. 中國運籌學會于1980年成立,1982年參加了國際運籌學會,1991年中國運籌學會成為國家一級學會.,運籌學

6、研究的特點,系統(tǒng)的整體優(yōu)化 多學科的配合 模型方法的應用:確定一組決策變量 使目標函數(shù) 達到最優(yōu)（optimization) 并受到一組約束條件的限制,模型方法應用的步驟,分析和表述問題 建立數(shù)學模型 對模型求解 對模型和由模型導出的解進行檢驗 建立起對解的有效控制 方案的實施,運籌學的重要分支,線性規(guī)劃(Linear programming) 運輸問題(Transportation problem) 目標規(guī)劃(Goal programming) 整數(shù)規(guī)劃(Integer programming) 分配問題(Assignment problem) 動態(tài)規(guī)劃(Dynamic programmin

7、g),運籌學的重要分支,圖和網(wǎng)絡模型(Graph and network modeling) 存儲論(Inventory theory) 博弈論(Game theory) 決策論(Decision theory) 排隊論(Queueing theory),計算機求解方法,使用WinQSB 初步了解一下WinQSB,第一章 線性規(guī)劃(LP),線性規(guī)劃問題的數(shù)學模型 圖解法 單純形法原理 單純形法的計算步驟 WINQSB簡介(LP部分),第一章 線性規(guī)劃(LP),教學目的與要求:通過學習使學生掌握LP的建模方法,熟練地使用單純形法和WINQSB軟件求解LP問題. 重點與難點:重點是LP的建模與解法

8、;難點是單純形法的原理. 教學方法:課堂講授為主并配合課件和WINQSB軟件. 思考題,討論題,作業(yè):教材第一章習題 參考資料:見前言. 學時分配:8學時.,第一章 線性規(guī)劃(LP),1939年蘇聯(lián)的經(jīng)濟學家.在生產(chǎn)組織與計劃中的數(shù)學方法一書中，首次用線性規(guī)劃方法解決了生產(chǎn)組織與運輸問題。 1947年美國數(shù)學家G.B.Dantzig提出了線性規(guī)劃的數(shù)學模型，并給出了求解該模型的單純形法（Simplex method).這標志著線性規(guī)劃這一運籌學的重要分支的誕生。 計算機的發(fā)展促進了LP計算理論的發(fā)展，使其應用更加廣泛和深入。,線性規(guī)劃的應用范圍,生產(chǎn)的組織與計劃問題 運輸問題 合理下料問題 配

9、料問題 生產(chǎn)布局問題 特點：在現(xiàn)有條件下，統(tǒng)籌安排，使總的經(jīng)濟效益最好。,第1節(jié) 線性規(guī)劃的數(shù)學模型,例1 某工廠制造A,B兩種產(chǎn)品，它們的原材料單位消耗，單位利潤以及資源現(xiàn)有量如下表,問如何組織生產(chǎn)可使工廠獲得最大利潤？,如何建立數(shù)學模型？,1.選擇決策變量：設A，B兩種產(chǎn)品各生產(chǎn) 個單位；,2.建立目標函數(shù)：利潤函數(shù)是 求它的最大值，即,3.生產(chǎn)的產(chǎn)量受到限制：,4.決策變量必須有非負限制：,綜合上述各點，該問題的數(shù)學模型如下,目標函數(shù),約束條件,非負限制,注意：目標函數(shù)和約束條件中變量的次數(shù)都是一次的，這樣的模型稱為線性規(guī)劃數(shù)學模型。,生產(chǎn)計劃安排的一般提法是：根據(jù)下列數(shù)據(jù)，如何安排生產(chǎn)

10、使工廠獲得最大利潤。,資源,產(chǎn)品,消耗,資源現(xiàn)有量,單位產(chǎn)品利潤,建立數(shù)學模型,解：設 表示生產(chǎn)產(chǎn)品 的單位數(shù)，則有如下的數(shù)學模型。,例2 設有某種物資從A，B，C三個產(chǎn)地調出，運往甲，乙，丙三個需求地，其調運量及運價如下表：求一個運費最省的調運方案.,甲 乙 丙 調出量 A 2 4 5 7 B 1 3 4 4 C 3 2 3 9 調入量 6 8 6 （20）,調出,調入,運價,設 表示從i地調往j地的調運量,i=1,2,3 J=1,2,3.,一般地,產(chǎn)銷平衡運輸問題的數(shù)學模型如下:,產(chǎn)量,銷量,產(chǎn)地,銷地,運價,建立數(shù)學模型:設 表示從i地調往j地的調運量,i=1,2, ,m j=1,2,

11、,n.,第2節(jié) 線性規(guī)劃問題解的性質 兩個變量的線性規(guī)劃問題的圖解法,幾個基本概念: 滿足所有約束條件的解稱為LP問題的可行解;所有可行解的集合稱為可行解集. 使目標函數(shù)達到最優(yōu)的可行解稱為LP問題的最優(yōu)解.,問題:線性規(guī)劃是一個帶有約束條件的極值問題,能否用微積分方法求解?,例1 用圖解法求解下面的LP問題,目標函數(shù)等值線,此點為LP的最優(yōu)解,目標函數(shù)等值線,可行解集,計算出這個最優(yōu)解:,上述作法稱為LP的圖解法.,本問題有唯一最優(yōu)解.,例2 用圖解法解下面的線性規(guī)劃,目標函數(shù)等值線,目標函數(shù)等值線,計算出LP的最優(yōu)解及目標函數(shù)最優(yōu)值:,除A,B兩個最優(yōu)解外,AB線段上的所有點都是LP的最優(yōu)

12、解.本問題有無窮多最優(yōu)解.,例3 用圖解法解下面的線性規(guī)劃,無界的可行解集,此題有可行解 但無最優(yōu)解,例4 用圖解法解下面的線性規(guī)劃,無可行解,本題無可行解,更無最優(yōu)解,有唯一最優(yōu)解,這個最優(yōu)解一定在可行解集合的某一頂點上達到; 有無窮多最優(yōu)解,最優(yōu)解充滿一個線段,可以用它的兩個端點作為代表; 有可行解,但無最優(yōu)解; 無可行解.,小結:兩個變量的LP圖解法有如下四種情況, 線性規(guī)劃問題的標準形式,規(guī)定:, 求目標函數(shù)的最大值為標準形,即目標函數(shù)為maxS.如果問題是求minS時,可設 求 , 相當于求minS., 以等式約束為標準形.設第k個等式為, LP中所有的變量都有非負限制.如果實際問題

13、中的LP里某個變量無非負限制,可如下處理:,（4）約束條件右端常數(shù)項全為非負值。,根據(jù)以上的規(guī)定,LP的標準形為,兩種縮寫形式:,矩陣表示法:,3. LP問題解的性質, 幾個概念 凸集:若連接n維點集S中任意兩點 的線段仍在S內(nèi),則稱S為凸集.即,凸集,凸集,不是凸集,極點, 極點:若凸集S中的點x,不能成為S中任何線段的內(nèi)點,則稱x為S的極點., 設 為LP的一個可行解,若 或 的非零分量對應的A中列向量線性無關,則稱它為基礎可行解.由這些列向量組成的矩陣稱為基矩陣,與這些列向量對應的變量稱為基變量,其余的變量稱為非基變量.,使目標函數(shù)值達到最大值的可行解稱為最優(yōu)解;使目標函數(shù)達到最大值的基

14、礎可行解稱為基礎最優(yōu)解.,例 設線性規(guī)劃為,則下述解中為基礎可行解的是 。 A.(2,0,4,0);B.(6,0,3,3);C.(3,2,3,2);D.(0,6,0,0),解:容易驗證D 是LP 的可行解,同時它對應的系數(shù)矩陣中第二列線性無關。,可行解集,基礎可行解,最優(yōu)解,基礎最優(yōu)解,目標函數(shù),約束條件,行列式0 基矩陣,右邊常數(shù),=, 幾個重要定理,定理1 線性規(guī)劃問題的可行解集為凸集,即連接線性規(guī)劃問題任意兩個可行解的線段上的點仍為可行解.,定理2 可行解集S中的點x是極點的充要條件是x為基礎可行解(簡單地說,凸多邊形的頂點就是基礎可行解).,定理3 線性規(guī)劃的目標函數(shù)的最優(yōu)值,一定可在

15、極點上達到.,第3節(jié) 單純形方法(Simplex method), 用消去法解LP問題,解:引入松弛變量 將其化為標準形,由此可以得出:目標函數(shù)中非基變量的系數(shù)可以用來檢驗線性規(guī)劃是否已得到最優(yōu)解了.,第三步:換基迭代,第四步:求新的基礎可行解,2. 單純形方法 給定LP問題,設A是 的矩陣,且R(A)=m (mn),即A是行滿秩的.于是,A中一定存在m列線性無關,這m行m列構成A的一個非奇異子矩陣,稱為線性規(guī)劃的一個基矩陣B(簡稱為一個基),基矩陣B各列對應的變量稱為基變量.為方便起見,不妨設A的前m列線性無關.現(xiàn)將A,B,C,x按一定規(guī)則作成分塊 矩陣.,設,類似地,設,下面證明,線性規(guī)劃

16、的有解判別定理:,3. 單純形表,基變量取值,檢驗數(shù),基變量,基變量在目標函數(shù)中的系數(shù),單純形法的計算步驟:,第一步:列出單純形表,例1.用單純形法解線性規(guī)劃,解:化為標準形,計算,填寫單純形表:, 換基迭代 檢驗數(shù)有兩種情況: 所有檢驗數(shù)小于等于零,則基B已是最優(yōu)基,得 到最優(yōu)表及最優(yōu)解,停止計算; 有某些檢驗數(shù)為正值,此表不是最優(yōu)表即基B不是最優(yōu)基,則應進行換基迭代.,換基迭代的步驟:,.選取入基變量:設 則相應的非基變量 為入基變量,簡稱“入基”.如果j不唯一,可選取較大的 值對應的非基變量入基.,.求主元素并確定出基變量:觀察在入基變量 所對應的 中的第j列,如果該列所有的分量均小于等

17、于零,則該LP問題無最優(yōu)解(定理).如果該列存在正分量,則以這些正分量為分母,以這些正分量所在行中對應的基變量取值為分子,求出這些比值中的最小值,該最小值對應的基變量為出基變量,簡稱“出基”,出入基交叉點上的元素稱為主元素或軸心項,用方框將其框起來. 這種求出基變量的方法稱為 法則.,.換基迭代:利用矩陣的初等變換,將主元素變?yōu)?,將其所在列的其余元素變?yōu)?,得一張新單純形表.重復上述步驟,經(jīng)過有限次換基迭代,一定可得到最優(yōu)解.,該表檢驗數(shù)全部小于等于零,稱此表為最優(yōu)表.其結果如下表示:,注意:松弛變量的取值不必寫出.本題迭代2次.,問題:表1中我們選取了 入基,如果選取 入基結果又如何呢?,

18、路徑1,路徑2,結論:1.每一個單純形表對應一個極點, 表一對應黃點;表二對應綠點;表三對應藍點. 2.一般來說,路徑不同,迭代次數(shù)可能不同.,說明:(1)如果單純形表中的基變量取值皆為正數(shù),稱這個基可行解為非退化解.若LP的所有基可形解都是非退化的,則LP經(jīng)過有限次迭代可達到最優(yōu). (2)如果單純形表中的基變量取值有的為零時,稱為LP的退化解,此時稱LP是退化的,理論上認為這種線性規(guī)劃在迭代過程中可能產(chǎn)生循環(huán),從而得不到最優(yōu)解.為避免循環(huán),常采用1976年R.G.Bland提出Bland法則:單純形表中有若干個檢驗數(shù) 時,取下標號小的非基變量入基; 用 法則選取出基變量時,若比值相同,則選取

19、下標號小的基變量出基.,(3) 當所有的檢驗數(shù)全部小于等于零時,若有某個非基變量的檢驗數(shù)也是零,則該線性規(guī)劃有無窮多組解,否則有唯一解.,例2.解線性規(guī)劃,先將線性規(guī)劃化為標準型,解：,注意到 對應A中的列向量恰好構成三階單位方陣,可以作為第一個可行基.,最優(yōu)解為 最優(yōu)值S=-20,書上的作法:,線性規(guī)劃問題的標準形式:,單純形法的計算步驟:,第一步:列出單純形表,說明:表中設系數(shù)矩陣中的前m列構成單位陣,即,表中 為非基變量,它下面的數(shù)據(jù)由下式算出:,表中基變量的檢驗數(shù)皆為零;而非基變量 的檢驗數(shù) 由下面的方法計算:,用 上面的數(shù)字 減去 下面這一列數(shù)字與 中同行的數(shù)字分別相乘的結果.,第二

20、步:進行最優(yōu)性檢驗,如果表中所有的檢驗數(shù) 則表中的基可行解就是問題的最優(yōu)解,計算結束.否則轉下一步.,第三步:換基迭代,該步與我們講的方法相同.,例,解:化為標準形,表中的檢驗數(shù)全部小于等于零,該表為最優(yōu)表. 最優(yōu)解為,目標函數(shù)的最優(yōu)值計算出的,3. 第一個可行基的求法,以上各例的系數(shù)矩陣A中,都存在一個m階單位陣,因此很容易用單純行法求解.但是大多數(shù)LP問題并不是這樣.,例 3,化為標準形,說明:關于大M法的幾種情況,1. 表4稱為終止表.在終止表中,如果基變量里不含有人工變量,則LP一定有最優(yōu)解;,2. 在終止表中,如果基變量里含有人工變量,但是人工變量取值為零,則LP有最優(yōu)解;,3. 在

21、終止表中,如果基變量里含有人工變量,且人工變量取值大于零,則LP無最優(yōu)解.,4.關于WinQSB,作業(yè):,提示：先改為最大化標準型再用大M 法（添加-M),線性規(guī)劃的對偶理論,對偶問題的提出 原問題與對偶問題 對偶問題的基本性質 影子價格 對偶單純形法 靈敏度分析,線性規(guī)劃的對偶理論,教學目的與要求:了解對偶問題產(chǎn)生的經(jīng)濟背景,熟練掌握對偶單純形法和影子價格概念,熟練掌握靈敏度分析方法. 重點與難點:重點同上,難點是對偶理論. 教學方法:課堂講授為主并配合課件和WINQSB軟件. 思考題,討論題,作業(yè):教材第二章習題 參考資料:見前言. 學時分配:8學時.,第4節(jié) 對偶線性規(guī)劃問題,對偶問題的

22、提出 內(nèi)容一致,而從相反的角度提出的一對問題,稱為 一對對偶問題.,例1.某工廠在計劃期內(nèi)安排生產(chǎn)甲,乙兩種產(chǎn)品,這些產(chǎn)品分別需要在A,B,C,D四種不同的設備上加工.產(chǎn)品在各臺設備上需要加工的臺時數(shù)是:,A B C D,甲 2 1 4 0 乙 2 2 0 4,產(chǎn)品,設備,已知各設備的有效臺時數(shù)分別是12,8,16,12.生產(chǎn)一件產(chǎn)品甲獲利2(萬元),一件產(chǎn)品乙獲利3(萬元).如何安排生產(chǎn)使工廠獲利最大.,解:,從相反的角度提出問題:工廠決策者決定不生產(chǎn)甲乙兩種產(chǎn)品,而對設備的有效臺時數(shù)進行出租,用收取加工費的方法獲得最大利潤.應如何考慮?,決策者首先要考慮給每一種設備出租一個臺時的定價.在何

23、種價格下,決策者接受外加工呢?,建立LP數(shù)學模型,顯然,當maxZ=minW時,對于決策者來說這兩種方案都是最優(yōu)的.,2.對偶線性規(guī)劃的模型,特點:1.一個規(guī)劃中的每一個約束,對應對偶規(guī)劃中的一個決策變量; 2.一個規(guī)劃中目標函數(shù)系數(shù)恰為對偶規(guī)劃約束條件右端常數(shù)項; 3.一個規(guī)劃求最小化,而對偶規(guī)劃求最大化; 4.目標函數(shù)求最小化搭配”約束;目標函數(shù)求最大化搭配”約束; 5.兩個規(guī)劃都有非負限制. 6.兩個規(guī)劃約束方程組的系數(shù)矩陣互為轉置矩陣.,例1 寫出下面原規(guī)劃的對偶規(guī)劃,解:,例2 寫出下面原規(guī)劃的對偶規(guī)劃,解:,定理1 如果線性規(guī)劃中第k個約束條件是等式,則它的對偶規(guī)劃中的第k個變量無

24、非負限制,反之亦然.,例3 寫出下面原規(guī)劃的對偶規(guī)劃,解:,例4 寫出下列線性規(guī)劃的對偶問題（p55例2）,3.對偶線性規(guī)劃的性質,定理2(弱對偶定理) 對偶規(guī)劃(1),(2)有最優(yōu)解的充分必要條件是它們同時有可行解.,定理3(最優(yōu)性定理) 如果 分別是(1),(2)的可行解,且 則 分別是(1),(2)的最優(yōu)解.,證明(定理2):必要性是顯然的。 充分性：設（1），（2）分別有可行解 ，對（1）的任一可行解 ，有,即S=CX在可行域內(nèi)有下界，于是一定有最小值，所以（1）的最優(yōu)解存在。同理可證另一結論。,例 已知線性規(guī)劃問題,用對偶理論證明該問題的最優(yōu)解的目標函數(shù)值不大于25。,解：寫出它的對

25、偶問題,任取可行解 （滿足所有約束條件）且 。,有定理2可知，,定理4 （強對偶定理）如果對偶規(guī)劃(1),(2)中有一個有最優(yōu)解,那么另一個也一定有最優(yōu)解.并且兩個規(guī)劃的目標函數(shù)的最優(yōu)值相等.,定理5 （互補松弛性質）在線性規(guī)劃問題的最優(yōu)解中，如果對應某一約束條件的對偶變量值為非零，則該約束條件取嚴格等式；反之如果約束條件取嚴格不等式，則其對應的對偶變量一定為零。即如果,給定,則對偶規(guī)劃為,下面我們驗證定理4：,分別化為標準形,重要結論:給出一對對偶線性規(guī)劃,只需解其中一個線性規(guī)劃得出最優(yōu)解和目標函數(shù)最優(yōu)值.它的對偶規(guī)劃的目標函數(shù)最優(yōu)值與原規(guī)劃的目標函數(shù)值相同,而最優(yōu)解可用原規(guī)劃最優(yōu)表中的松弛

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

27、,在上式中對 求偏導數(shù)得,這說明, 的值相當于在給定的生產(chǎn)條件下, 每增加一個單位時,目標函數(shù)S的增加量,即總收入的變化率(總收入增加一個影子價格值).,(3) 影子價格是一種機會成本(Opportunity cost),在純市場經(jīng)濟條件下,當某種資源的市場價格低于影子價格時,可以買進這種資源擴大生產(chǎn);相反當市場價格高于影子價格時,可賣出這種資源獲取更大的利潤.,注意:由于影子價格可為決策者提供決策依據(jù),因此各種資源的影子價格應當保密.,(4).影子價格0時,由互補松弛性質可知，該約束條件為等式,這說明此種資源已被充分利用.,在生產(chǎn)過程中，某種資源是過剩資源,沒有被充分利用，由互補松弛性質可知

28、，該種資源的影子價格為零。,影子價格=0不是說該資源沒有價格,而是表明該資源已是過剩資源,再買進此資源不會增加總收入.,例 下列關于線性規(guī)劃原問題與其對偶問題之間關系的敘述不正確的是（ ） 若原問題有最優(yōu)解，則其對偶問題也有最優(yōu)解 設 為對偶問題的最優(yōu)解，若 ，說明在最優(yōu)生產(chǎn)計劃中第i種資源一定有剩余 任何線性規(guī)劃問題存在唯一的對偶問題 如果原問題與對偶問題都有可行解，則它們必有最優(yōu)解,例 某工廠兩種產(chǎn)品生產(chǎn)的利潤最大化的LP 模型為,最優(yōu)表如下：,問題：若該工廠可以通過加班的方法獲得更多的裝配時間，則工廠愿意為之付出的加班費是多少？在加班費為50元/小時的情況下，工廠可獲得的利潤最大增加額是

29、多少？,答：三種資源的影子價格分別是60、0、40。特別地，第一種資源的影子價格是60，這是工廠愿意付出的加班費，若付加班費50元/小時，工廠利潤增加額是10元/小時。,進一步分析:,關于影子價格的應用:,丹捷格:分解原理 J.科爾納:影子價格法,4. 對偶單純形法,定義:設 是線性規(guī)劃 的一組基,它對應的基矩陣是B,對應的基解為 , 如果這組基對應的檢驗數(shù)全部小于等于零,即 則稱這組基為該線性規(guī)劃的一組正則基. 為正則解.,線性規(guī)劃的對偶單純形法是從第一個正則解 開始迭代的.,對偶單純形法的迭代步驟:,從一個正則解開始,列出對偶單純形表; 如基變量的取值全部大于等于零,則線性規(guī)劃已取得最優(yōu)解

30、,計算結束,否則轉(3); 在基變量中,挑選取負值中最小的一個,作為出基變量(若最小負值相同,可由Bland法則確定); 在出基變量行中,如果非基變量的約束系數(shù)全部非負,則原問題不存在可行解,否則轉(5);,(5)在出基變量行中,如果有些非基變量的約束系數(shù)為負,則分別計算這些變量的檢驗數(shù)與出基變量行中負系數(shù)的比值,比值最小者對應的非基變量為入基變量(若比值相同,由Bland法則確定); (6) 出,入基交叉點上的元素為主元素,用方框框 起來,將其變?yōu)?,用矩陣初等行變換將其所在列的其余元素變?yōu)?得一新表,轉(2).,例1 利用對偶單純形法解下邊的線性規(guī)劃,解:首先將LP化為標準形,再變形為,基變量取值為,檢驗數(shù),存在一組正則基,列出對偶單純形表:,-2 -1 0 0 0,5. 靈敏度分析,在大多數(shù)線性規(guī)劃中,其參數(shù)值是一些估計量,有時是作為政策決定的結果而出現(xiàn),這些決定是否正確,要經(jīng)過方案實施后的效果而定