運籌學緒論、第一章 2

運籌學基礎及應用(O.R.)(美OperationsResearch)(英OperationalResearch)苗文靜華北科技學院wenjingmiao@163.com1課程簡介運籌學類似于數(shù)學建?！，F(xiàn)在普遍認為，運籌學是近代應用數(shù)學的一個分支，主要是將生產(chǎn)、管理中出現(xiàn)的一些帶有普遍性的運籌問題加以提煉，構建數(shù)學模型并進行求解。隨著科學技術和生產(chǎn)的發(fā)展，運籌學已滲入很多領域里，發(fā)揮了越來越重要的作用，如資源分配、廠址定位、庫存、人員配置等各個方面。2運籌學本身也在不斷發(fā)展，現(xiàn)在已經(jīng)包括多個分支。如：數(shù)學規(guī)劃（包含線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃、目標規(guī)劃等）、圖論、決策分析、排隊論、存貯論、對策論等。通過學習該課程，應了解運籌學對優(yōu)化決策問題進行定量研究的特點，理解線性規(guī)劃、運輸問題、整數(shù)規(guī)劃、目標規(guī)劃、動態(tài)規(guī)劃、網(wǎng)絡計劃等的基本優(yōu)化原理，掌握其中常用的模型和算法。先修課程主要為線性代數(shù)，為了深入學習這門課程，最好作必要的復習或學習。3胡運權主編.《運籌學教程》.清華大學出版社。運籌學編寫組.《運籌學》.清華大學出版社。參考書目4要求考勤：曠課按考勤次數(shù)從平時成績中逐級扣分；有事請請假.課堂：認真聽講，做好筆記.成績：平時30%（包括考勤和平時作業(yè)）+期末考試70%.5運籌學軟件LindoLingoExcel規(guī)劃求解Matlab6緒論內(nèi)容提要一、運籌學簡介二、運籌學發(fā)展簡史三、主要研究內(nèi)容四、運籌學的工作步驟五、運籌學的性質與特點六、如何學好運籌學7運籌學簡介運籌學的稱謂

美國：OperationsResearch英國：OperationalResearch縮寫：OR日本譯作“運用學”，香港、臺灣譯為“作業(yè)研究”，我國學者從古語“運籌帷幄之中，決勝千里之外”取“運籌”二字，充分體現(xiàn)了這門學科運心籌謀、策略取勝的精髓。譯作“運籌學”。北美：ManagementScience管理科學8《大英百科全書》釋義：運籌學是一門應用于管理有組織系統(tǒng)的科學，運籌學為掌管這類系統(tǒng)的人提供決策目標和數(shù)量分析的工具?！吨袊蟀倏啤丰屃x：運籌學用數(shù)學方法研究國民經(jīng)濟、民政和國防等部門在內(nèi)外環(huán)境的約束條件下合理分配人力、物力、財力等資源，使實際系統(tǒng)有效運行的技術科學，它可以用來預測發(fā)展趨勢，制定行動規(guī)劃或優(yōu)選可行方案。運籌學簡介9運籌學是一門應用科學，它廣泛應用現(xiàn)有的科學技術知識和數(shù)學方法，來解決實際中提出的專門問題，并為決策者選擇最優(yōu)策略提供定量依據(jù)。運籌學是一門交叉學科；運籌的目標是最優(yōu)策略。運籌學簡介101.運籌學問題和樸素的運籌學思想，可以追溯到古代.如：圍魏救趙；田忌賽馬；丁渭主持皇宮的修復等.2.運籌學誕生的三個來源：軍事、管理和經(jīng)濟。孫武：運籌為計，知人善用，應敵為變；運籌學發(fā)展簡史運籌學發(fā)展簡史11運籌學的產(chǎn)生在階級社會中，科學技術的發(fā)展往往受到戰(zhàn)爭的極大推動，許多新科學、新技術首先是由軍事斗爭的需要而產(chǎn)生和發(fā)展起來的.運籌學也不例外，它的產(chǎn)生背景為第二次世界大戰(zhàn).121938年7月，波德塞(Bawdsey)雷達站的負責人羅伊(A．P．Rowe)提出立即進行整個防空作戰(zhàn)系統(tǒng)運行的研究，用“operationalresearch”一詞作為這方面研究的描述，這就是O.R.（運籌學)這個名詞的起源。

13●1940年9月，英國成立了由物理學家P.M.S.布萊克特領導的第一個運籌學小組。成員有：三名生物學家、兩名數(shù)學物理學家、一名天文學家、一名軍官、一名測量員、一名普通物理學家和兩名數(shù)學家。由于人員組成多專業(yè)性，所以有人稱這個小組為“布萊克特馬戲團”?！?942年，美國和加拿大都相繼建立了運籌學小組。這些運籌學小組在確定護航艦隊的規(guī)模、開展反潛艇戰(zhàn)的偵察、組織有效的對敵轟炸等方面作了大量研究，為運籌學有關分支的建立作出了貢獻。改進威耳孫云室方法及在核物理和宇宙線領域的發(fā)現(xiàn)，獲得1948年諾貝爾物理學獎14

1947年丹齊克(G.B.Danzig)在研究美國空軍資源的優(yōu)化配置時提出了線性規(guī)劃及其通用解法——單純形法;1948年美國麻省理工學院把運籌學作為一門課程介紹；50年代初用電子計算機求解線性規(guī)劃獲得成功;1951年莫爾斯(P.M.Morse)和金博爾(G.E.KimbaU)合著的“運籌學方法”一書正式出版。1．從1945年到50年代初，被稱為創(chuàng)建時期。特點：從事研究的人數(shù)不多，范圍較小，人員從軍事轉為民用。所有這些，標志運籌學這門學科的基本形成。運籌學的發(fā)展階段1550年代末，美國大約有半數(shù)的大公司在自己的經(jīng)營管理中應用運籌學，如用于制訂生產(chǎn)計劃、物資儲備、資源分配、設備更新等方面酌決策。有更多刊物、學會出現(xiàn)。1957年在英國牛律大學召開了第一次國際運籌學會議。1959年成立國際運籌學聯(lián)合會。2．50年代初到50年代末，被認為是其成長時期。特點：電子計算機技術的迅速發(fā)展，使得運籌學中一些方法如單純形法、動態(tài)規(guī)劃方法等，得以用來解決實際管理系統(tǒng)中的優(yōu)化問題．促進了運籌學的推廣應用。運籌學發(fā)展簡史163．自60年代以來，是其迅速發(fā)展和開始普及的時期。第三代電子數(shù)字計算機的出現(xiàn)，促使運籌學得以用來研究一些大的復雜的系統(tǒng)，如城市交通、環(huán)境污染、國民經(jīng)濟計劃等。特點：運籌學進一步細分為各個分支，專業(yè)學術團體的迅速增多，更多期刊的創(chuàng)辦，運籌學書籍的大量出版以及更多學校將運籌學課程納入教學計劃之中。運籌學發(fā)展簡史17成熟的學科分支向縱深發(fā)展新的研究領域產(chǎn)生與新的技術結合與其他學科的結合加強傳統(tǒng)優(yōu)化觀念不斷變化運籌學的發(fā)展趨勢運籌學發(fā)展簡史18我國于上世紀50年代開始研究運籌學。50年代中期由錢學森、許國志等教授由西方引入；投入產(chǎn)出表、質量管理的研究和應用開展較早；1970年后，華羅庚教授在全國范圍內(nèi)推廣統(tǒng)籌法和優(yōu)選法，一大批數(shù)學家開始研究運籌學；中國運籌學會于1980年成立，1982年作為正式成員加入了國際運籌學聯(lián)合會（IFORS）。某些分支的研究達到當時國際水平。運籌學發(fā)展簡史19主要內(nèi)容線性規(guī)劃、對偶理論、運輸問題整數(shù)規(guī)劃、目標規(guī)劃、動態(tài)規(guī)劃

圖論與網(wǎng)絡分析決策分析庫存?zhèn)悓Σ哒?0運籌學解決問題的方法步驟提出并形成問題

建立模型分析并求解模型檢驗并評價模型

應用或實施模型的解21引入數(shù)學方法解決實際問題

--定性與定量方法結合系統(tǒng)與整體性

--從全局考察問題應用性

--源于實踐、為了實踐、服務于實踐交叉學科

--涉及經(jīng)濟、管理、數(shù)學、工程和系統(tǒng)等多學科開放性

--不斷產(chǎn)生新的問題和學科分支多分支

--問題的復雜和多樣性運籌學的性質與特點22如何學習運籌學課程

學習運籌學要把重點放在分析、理解有關的概念、思路上。在自學過程中，應該多向自己提問，例如一個方法的實質是什么，為什么這樣進行，怎么進行等。

自學時要掌握三個重要環(huán)節(jié)：

1.認真閱讀教材和參考資料，以指定教材為主，同時參考其他有關書籍。

2.要在理解了基本概念和理論的基礎上研究例題，注意例題是為了幫助理解概念、理論的。3.要學會做學習小結。23LinearProgramming（LP）

線性規(guī)劃問題及其數(shù)學模型

線性規(guī)劃問題的求解方法

線性規(guī)劃的圖解法

線性規(guī)劃的單純形法

線性規(guī)劃模型的應用第一章線性規(guī)劃及單純形法24

線性規(guī)劃問題及其數(shù)學模型第一章線性規(guī)劃及單純形法LinearProgramming（LP）

線性規(guī)劃問題的求解方法

線性規(guī)劃的圖解法

線性規(guī)劃的單純形法

線性規(guī)劃模型的應用25一、問題的提出

為了完成一項任務或達到一定的目的，怎樣用最少的人力、物力去完成或者用最少的資源去完成較多的任務或達到一定的目的，這個過程就是規(guī)劃。例1、有一正方形鐵皮，應如何裁剪能使容積最大？xa無約束的極值問題26例2、如何安排生產(chǎn)才能使利潤最大？資料如圖

設備產(chǎn)品ABCD利潤（元）

Ⅰ21402

Ⅱ22043有效臺時1281612目標max

x1≥0,x2≥0s.t.2x1+2x2≤12

帶約束的極值問題x1x2z=2x1+3x2

約束條件x1+2x2≤84x1≤164x2≤12subjectto函數(shù)數(shù)學模型27例3、合理配料問題數(shù)學模型x1x2

x3

x4

x5

x6z=4x1+3x2+6x3+5x4+2.7x5+2.2x6mins.t.x1+0x2+2x3+2x4+x5+2x6≥9

0x1+x2+3x3+x4+3x5+2x6≥19

x1,x2,…,x6≥0

每天服用這六種營養(yǎng)物各多少克，才能既獲得每日最少所需又使花費最??？28二、數(shù)學模型組成要素：

決策變量

約束條件

目標函數(shù)線性規(guī)劃：連續(xù)的（數(shù)值取實數(shù)）關于變量的線性等式或不等式關于變量的線性函數(shù)（一次方）問題中有未知的變量，需要我們?nèi)デ蠼?，此外有目標函?shù)及約束條件，一般有非負條件存在，由此組成規(guī)劃問題的數(shù)學模型。29線性規(guī)劃數(shù)學模型的一般形式s.t.s.t.30向量形式s.t.s.t.31向量形式矩陣形式s.t.s.t.32線性規(guī)劃問題的數(shù)學模型s.t.s.t.s.t.s.t.33三、線性規(guī)劃問題的標準形式s.t.s.t.s.t.s.t.34標準形式的主要特征s.t.③決策變量xj取值非負④約束條件右端常數(shù)項bi為非負值①目標函數(shù)為求極大值（也可用求極小值）②所有約束條件都是等式（非負條件除外）

√35非標準形式化為標準形式的方法⑴目標函數(shù)的轉換⑵約束方程的轉換：由不等式轉換為等式⑶變量的變換稱為松弛變量稱為剩余變量x1+x24x1+x2－

x3=4⑷約束條件右端常數(shù)項的變換：bi﹤0x1+x23x1+x2+x3=336例1、將下列線性規(guī)劃問題化為標準形式+0x5+0x4maxz

=－2x1

+

x2

－3x3

maxz

=－2x1

+

(x2－

x2)

+3x3

+0x4+0x53x1

－2(x2－

x2)－

x3

=－4－3x1

+2(x2－

x2)+

x3

=4解：設min

x1≥0,x2取值無約束,x3≤0s.t.x1+2x2+4x3≤6z=2x1

－x2

+3x3

3x1

－2x2+x3=－4

2x1

－

x2－3x3≥

5

x1,x2,x2,x3,x4,x5≥0

x1+2x2+4x3+x4

=6s.t.

2x1

－

x2－

3x3－

x5

=5引入變量令x1

+

2(x2－

x2)－4x3

+

x4=6第二個約束方程兩邊乘(－1),從而得到標準形式2x1

－

(x2－

x2)＋3x3

－

x5

=5－3x1

+2x2－2x2+

x3

=4

x1,x2,x2,x3,x4,x5≥0s.t.x1

+2x2－2x2－4x3

+

x4=62x1

－

x2＋

x2＋3x3

－

x5

=5maxz

=－2x1

+

x2－

x2+3x3

+0x4+0x537例2、將下列線性規(guī)劃問題化為標準形式x1

＋2(x2－

x2)＋

x3

＋

x4

=5x1,x2,x2,x3,x4,

x5,

x6

≥0x1

＋

(x2－

x2)＋

x3

＋

x6

=2maxz=x1

+2(x2－

x2)

+3x3

+0x4+0x5+

0x6解：max

x1≥0,x2取值無約束,x3≤0s.t.x1+2x2－

x3≤5z=x1+2x2

－3x3

2x1+

3x2－

x3≥6

－x1

－

x2+

x3≥

－2引入變量令第三個約束方程兩邊乘(－1),從而得到標準形式2x1

＋3(x2－

x2)＋

x3

－

x5

=6s.t.x1

＋2x2－2x2＋

x3

＋

x4

=5x1,x2,x2,x3,x4,x5,x6≥0x1

＋

x2－

x2＋

x3

＋

x6

=2maxz=x1

+2x2－2x2+3x3

+0x4+0x5+

0x62x1

＋3x2－3x2＋

x3

－

x5

=638練習：將下列線性規(guī)劃問題化為標準形式min

x1,x2≥0,x3取值無約束s.t.x1

－

x2+x3≤10z=－2x1+3x2

－

x3

3x1+

2x2－

x3≥8x1

－3x2+

x3=－1－x1

＋3x2

－

x3＋

x3

=1maxz

=2x1

－3x2+

x3－

x3

+0x4+0x53x1

＋2x2

－

x3＋

x3

－

x5

=8

x1,x2,x3,x3,x4,x5≥0s.t.x1

－

x2

＋

x3－

x3

＋

x4

=10解：設引入變量令第三個約束方程兩邊乘(－1),從而得到標準形式39

線性規(guī)劃問題的求解方法第一章線性規(guī)劃及單純形法LinearProgramming（LP）

線性規(guī)劃問題及其數(shù)學模型

線性規(guī)劃的圖解法

線性規(guī)劃的單純形法

線性規(guī)劃模型的應用40一、預備知識：解的概念

可行解：滿足約束條件的解

最優(yōu)解：使目標函數(shù)達到極值的可行解

可行域：所有可行解構成的集合s.t.41一、預備知識：凸集與頂點x1x2x2x1x1x2x1x2x1x2x1x2凸集：集合C中任意兩點連線上的所有點還在C內(nèi)

任給x1,x2C,x=x1+(1－)x2

C(0<<1)頂點：凸集C中不在任意兩不同點連線上的點對x,任給x1,x2C,不存在x=x1+(1－)x2(0<<1)凸集非凸集42二、圖解法步驟：將約束條件在圖上表示建立直角坐標系確立滿足約束條件的解的范圍(可行域)繪制出目標函數(shù)的圖形在可行域中確定最優(yōu)解定義：用圖示的方法求解線性規(guī)劃問題的最優(yōu)解優(yōu)點：直觀性強，計算方便缺點：只適用于問題中是兩(三)個變量的情況43123456781234562x1+2x2=12x1+2x2=84x1=164x2=12唯一最優(yōu)解此時z=14。(4,2)示例1：s.t.①②③④0x2

x1z=0x1=4,x2=2,

44123456781234563x1+2x2=12x1+2x2=6x2=2無窮多最優(yōu)解示例2：0x2

x1s.t.①②③45x1－x2=－1x1+2x2=2無界解(無最優(yōu)解)示例3：s.t.①②x1x2

0思考：若目標函數(shù)改為minz=x1+x2呢？若改為minz=x1+

2x2呢？46無可行解示例4：s.t.①②x1+x2=1x1x2

02x1+3x2=6472x2=12練習：s.t.x1=83x1+4x2

=36(4,6)x1812x243690唯一最優(yōu)解此時z=42。x1=4,x2=6,

48（4）無可行解：無可行域，模型約束條件矛盾圖解法的幾點啟示線性規(guī)劃問題解的情況有：（1）唯一最優(yōu)解：只有一點為最優(yōu)解點（2）無窮多最優(yōu)解：有許多點為最優(yōu)解點（3）無界解：最優(yōu)解取值無界，無最優(yōu)解LP問題的可行域若存在則一定是凸集(有限個頂點)LP問題若有最優(yōu)解，則定能在可行域某頂點達到LP問題的解題思路：頂點→相鄰頂點→……49三、單純形法（SimplexMethod）美國數(shù)學家丹齊格(G.B.Dantzig)1947年創(chuàng)建簡捷、規(guī)范，是舉世公認的解決線性規(guī)劃問題行之有效的方法。

理論根據(jù)：基本思想：在凸集的有限個頂點上搜索最優(yōu)解該搜索策略可極大地減少訪問頂點的數(shù)量。

由可行域的一個頂點出發(fā)，沿著凸集邊緣逐個計算與判定所遇到的頂點，直至找到最優(yōu)解所對應的頂點為止。

線性規(guī)劃問題的可行域是n維向量空間中的多面凸集，其最優(yōu)值如果存在則必在該凸集的某頂點處達到。50s.t.(一)基解與基可行解系數(shù)矩陣A是m×n矩陣（設m<n），其秩R(A)=m。線性規(guī)劃問題的基：矩陣A中的m×m階滿秩子矩陣B。(|B|≠0)基解：令非基變量為零，對m個基變量求解后合并所得的解。最多個基向量：B中的m個列向量Pr?；兞浚号c基向量對應的m個變量xr。剩下n-m個非基變量。51(一)基解與基可行解基解：令非基變量為零，對m個基變量求解后合并所得的解。設

，

令非基變量基變量為，|B|≠0基變量的唯一解基解最多個52(一)基解與基可行解基解：令非基變量為零，對m個基變量求解后合并所得的解。基可行解：滿足變量非負約束條件xj≥0的基解。可行基：對應于基可行解的基。基可行解可行解非可行解基解53基基解是否基可行解目標函數(shù)值例題：列出全部基、基解、基可行解和指出最優(yōu)解s.t.s.t.標準化系數(shù)矩陣:54例題：用圖解法求最優(yōu)解s.t.x1+x2=3x1+2x2=4(2,1)12341230x2

x1基解對應于各直線交點基可行解是可行域的頂點55(二)單純形法的基本定理定理1：若線性規(guī)劃問題存在可行解，則問題的可行域是凸集。定理3：若線性規(guī)劃問題有最優(yōu)解，則一定存在一個基可行解是最優(yōu)解。定理2：線性規(guī)劃問題的基可行解對應其可行域的頂點。理論根據(jù)：

線性規(guī)劃問題的可行域是n維向量空間中的多面凸集，其最優(yōu)值如果存在則必在該凸集的某頂點處達到。在有限個基可行解中搜索最優(yōu)解（迭代）56(三)單純形法的求解思路確定一個初始基可行解是否最優(yōu)改進為新的基可行解最優(yōu)解是否循環(huán)結束化標準形571、確定初始基可行解s.t.s.t.標準化約束方程組的系數(shù)矩陣：基變量值：初始基可行解：58記2、最優(yōu)性檢驗s.t.初始基可行解：任一可行解：由約束方程組得代入目標函數(shù)可得：則有：檢驗數(shù)基變量的59其中2、最優(yōu)性檢驗當前基可行解是最優(yōu)解若所有，則對任意可行解X，都有線性規(guī)劃問題存在無界解（無最優(yōu)解）若存在某個，且所有令只需保證由所有顯然此時因找可行解X，使z無限大。60線性規(guī)劃問題無可行解2、最優(yōu)性檢驗當前基可行解是最優(yōu)解：所有線性規(guī)劃問題有唯一最優(yōu)解′線性規(guī)劃問題有無窮多最優(yōu)解′′線性規(guī)劃問題存在無界解（無最優(yōu)解）若存在某個，且所有存在和當前基可行解非最優(yōu)解，但LP問題有最優(yōu)解其中所有；

或

有非基變量,且613、尋找改進的基可行解相鄰的基可行解：若兩個基可行解之間僅變換一個基變量。將一個基變量變成非基變量（換出），一個非基變量變成基變量（換入），進而找出一個目標函數(shù)值更大的“相鄰”基可行解。入基變量的確定由和越大，值上升的可能性越大因此，一般取對應的變量作為換入基的變量。623、尋找改進的基可行解出基變量的確定令換入變量為得到基可行解，需保證且至少一個為0（換出）則只需取其余非基變量，存在此時換出。確定為換出變量，由稱為主元素?？尚薪猓鹤C明是基可行解？§3-1引理633、尋找改進的基可行解約束方程組的系數(shù)矩陣：初始基

，

變量換入,換出，新可行解對應向量：是線性無關的，故是基可行解。s.t.64單純形法的求解思路確定一個初始基可行解是否最優(yōu)改進為新的基可行解最優(yōu)解是否循環(huán)結束化標準形？65步驟簡單總結經(jīng)過何種運算可轉到第③步，實現(xiàn)循環(huán)迭代？①將線性規(guī)劃問題化成標準形式;②找出或構造一個m階單位矩陣作初始可行基，得到初始基可行解;③計算各非基變量xj的檢驗數(shù)j，若所有j≤0，則問題已得到最優(yōu)解，停止計算，否則轉入下步;④若存在某個s>0，且對應的所有系數(shù)ais≤0，則此問題是無界解，停止計算，否則轉入下步;⑤根據(jù)max{j|j＞0}=k原則，確定xk為入基變量，再按=min{bi/aik|aik＞0}=bl/alk規(guī)則，確定xl為出基變量，得到改進的基可行解。66將其化為單位矩陣，則LP問題形式為s.t.4、迭代運算初始基

，

變量換入,換出，新可行基：s.t.674、迭代運算①主元素所在行：②其余行：684、迭代運算新檢驗數(shù)

s.t.整理后可得

69①將線性規(guī)劃問題化成標準形式;②找出或構造一個m階單位矩陣作初始可行基，得到初始基可行解;③計算各非基變量xj的檢驗數(shù)j，若所有j≤0，則問題已得到最優(yōu)解，停止計算，否則轉入下步;④若存在某個s>0，且對應的所有系數(shù)ais≤0，則此問題是無界解，停止計算，否則轉入下步;⑤根據(jù)max{j|j＞0}=k原則，確定xk為入基變量，再按=min{bi/aik|aik＞0}=bl/alk規(guī)則，確定xl為出基變量；⑥以alk為主元素進行迭代，利用初等行變換將xk所在列化為單位向量，即alk化為1，其它元素化為0，得到改進的可行基，轉入第③步。計算步驟總結70(四)單純形表格法——單純形表s.t.7172……73max

x1,x2≥0s.t.

2x1+2x2≤12z=2x1+3x2

4x1

≤

165x2≤15例題：用單純形法求解線性規(guī)劃問題+0x4+0x3maxz=2x1

+3x2s.t.引入變量得到標準形式解：+0x55x2+x5

=154x1

+

x4=162x1

+2x2+

x3=12x1,x2,x3,x4,x5≥074+0x4+0x3maxz=2x1

+3x2s.t.引入變量得到標準形式解：+0x55x2+x5

=154x1

+

x4=162x1

+2x2+

x3=12x1,x2,x3,x4,x5≥07576此時所有檢驗數(shù)得到最優(yōu)解最優(yōu)值為77①將線性規(guī)劃問題化成標準形式;②找出或構造一個單位矩陣作初始可行基，確定初始基可行解，建立初始單純形表;③檢驗各非基變量xj的檢驗數(shù)j，若所有j≤0，則問題已得到最優(yōu)解，停止計算，否則轉入下步;④若存在某個s>0，且對應的所有系數(shù)ais≤0，則此問題是無界解，停止計算，否則轉入下步;⑤根據(jù)max{j|j＞0}=k原則，確定xk為入基變量，再按=min{bi/aik|aik＞0}=bl/alk規(guī)則，確定xl為出基變量；⑥用xk替換基變量中的xl，利用初等行變換將xk所在列化為單位向量，得到新的單純形表，轉入第③步。單純形法計算步驟78練習：求解線性規(guī)劃問題：79標準化系數(shù)矩陣(五)單純形法的進一步討論

用單純形法解題時，需要有個單位矩陣作為初始可行基當約束條件都是“≤”時，加入松弛變量就形成了初始基

但實際存在“≥”或“＝”型的約束，沒有現(xiàn)成的單位矩陣s.t.－2x1＋

x2－x3

－

x5

=1解：引入變量從而得到標準形式s.t.x1

＋

x2＋

x3＋

x4

=4x1,x2,x3,x4,x5≥03x2

＋

x3=9maxz=－3x1

+

0x2

+

x3+0x4+0x5約束方程組的系數(shù)矩陣：80maxz=－3x1

+

0x2

+

x3+0x4+0x5(五)單純形法的進一步討論采用添加人工變量的方法因是在等式中人為加進的，為保證約束條件的意義，最優(yōu)解中人工變量只能等于0

在等式約束中加入若干人工變量，人為構造一個單位矩陣

人工變量的添加不能影響最優(yōu)解的取值：－2x1＋

x2－x3

－

x5

=1s.t.x1

＋

x2＋

x3＋

x4

=4x1,x2,x3,x4,x5≥03x2

＋

x3=9約束方程組的系數(shù)矩陣：兩種處理方法

大M法兩階段法＋

x6

=1

＋

x7

=9=4,x6,x7≥0如何處理？811、大M法maxz=－3x1

+

0x2

+

x3+0x4+0x5－2x1＋

x2－x3

－

x5

=1s.t.x1

＋

x2＋

x3＋

x4

=4x1,x2,x3,x4,x5≥03x2

＋

x3=9＋

x6

=1

＋

x7

=9=4,x6,x7≥0－Mx6－Mx7為保證最優(yōu)解中人工變量取值為0，可令目標函數(shù)中人工變量的系數(shù)為足夠大的一個負值，用“－M”代表。由于系數(shù)是一個足夠大的負值，因此，只要人工變量的取值不為零，目標函數(shù)就不可能實現(xiàn)最大化。

計算時，把M看做一個代數(shù)符號直接參加單純形法求解。若最終單純形表中，人工變量仍是基變量且值不為零，則說明該問題求不到最優(yōu)解，即無可行解。82－2x1＋

x2－x3

－

x5

=1s.t.x1

＋

x2＋

x3＋

x4

=4x1,x2,x3,x4,x5≥03x2

＋

x3=9＋

x6

=1

＋

x7

=9=4,x6,x7≥0maxz=－3x1

+

0x2

+

x3+0x4+0x5－Mx6－Mx783使人工變量盡快出基8485此時所有檢驗數(shù)得到最優(yōu)解最優(yōu)值為86－2x1＋

x2－x3

－

x5

=1s.t.x1

＋

x2＋

x3＋

x4

=4x1,x2,x3,x4,x5≥03x2

＋

x3=9＋

x6

=1

＋

x7

=9=4,x6,x7≥0maxz=－3x1

+0x2

+

x3+0x4+0x5用大M法處理人工變量，用手工計算不會出現(xiàn)任何問題。

但用計算機求解時，由于在程序中只能用很大的數(shù)代替M，有可能受計算機的誤差影響，導致結果發(fā)生錯誤，使大M法失效。2、兩階段法

第一階段：構造判斷是否存在可行解的模型

構造僅含人工變量(系數(shù)為1)且要求極小化的目標函數(shù)用單純形法求解，若minw=0，說明人工變量為0，問題存在基可行解，進入第二個階段；若minw≠0，說明最優(yōu)解中人工變量非零，無可行解，停止。minw=x6+

x787minw=x6+

x72、兩階段法－2x1＋

x2－x3

－

x5

=1s.t.x1

＋

x2＋

x3＋

x4

=4x1,x2,x3,x4,x5≥03x2

＋

x3=9＋

x6

=1

＋

x7

=9=4,x6,x7≥0882、兩階段法

第二階段：從上階段的最終單純形表出發(fā)，去掉人工變量，引入原來的目標函數(shù)，繼續(xù)迭代，找出問題的最終解maxz=－3x1

+

0x2

+

x3+0x4+0x589人工變量法總結約束方程組

在等式約束中加人工變量，人為構造單位矩陣作初始可行基目標函數(shù)

為保證原約束條件的意義，最優(yōu)解中人工變量只能是0大M法

令目標函數(shù)中人工變量的系數(shù)為足夠大的一個負值“－M”兩階段法1、構造僅含人工變量且求極小化的目標函數(shù)，單純形法求解；2、去掉上階段最終單純形表中的人工變量，引入原目標函數(shù)，繼續(xù)迭代，找出問題的最終解。若最終單純形表中，人工變量仍是基變量且值不為零，則說明該問題求不到最優(yōu)解，即無可行解。903、由單純形表判別解的類別無可行解唯一最優(yōu)解所有無窮多最優(yōu)解無界解（無最優(yōu)解）最終單純形表的基變量中仍有非零人工變量存在某個，且所對應的系數(shù)最優(yōu)解某非基變量至少一個且91≤0≥0保證當前的基可行解是最優(yōu)解至少有一個等于0，如至少有一個大于0，如

＞0存在，保證當xp入基時有xl出基說明能得到另一個最優(yōu)基可行解兩個基可行解連線上的所有點都是最優(yōu)解92無窮多最優(yōu)解示例1：s.t.標準化s.t.9394此時所有檢驗數(shù)得到最優(yōu)解最優(yōu)值為95此時所有檢驗數(shù)得另一最優(yōu)解最優(yōu)值為96無界解(無最優(yōu)解)示例2：s.t.標準化s.t.且所對應系數(shù)取值無限制160x2

x14x1=1697無可行解示例3：s.t.標準化s.t.98此時所有檢驗數(shù)但人工變量仍留在基變量中且不為零，問題無可行解。99補充說明單純形法在計算中可能出現(xiàn)以下兩種情況：同時出現(xiàn)多個相同的最大j值同時出現(xiàn)多個相同的最小θ值理論上可能出現(xiàn)死循環(huán)，但實際很罕見，一般不需特殊處理，任選其中一個對應的變量入基或出基即可。若遇到極端情況，可利用勃蘭特(bland)規(guī)則：當存在多個j>0時，選取下標值最小的變量入基；當出現(xiàn)多個相同最小θ時，選取下標值最小的變量出基。100

線性規(guī)劃模型的應用第一章線性規(guī)劃及單純形法LinearProgramming（LP）

線性規(guī)劃問題及其數(shù)學模型

線性規(guī)劃問題的求解方法

線性規(guī)劃的圖解法

線性規(guī)劃的單純形法101線性規(guī)劃問題的建模

建模是運籌學方法的核心和精髓，建立一個正確的數(shù)學模型，是問題解決的關鍵，答案利用線性規(guī)劃程序可很快獲得。正確的建模要求建模者：理解生產(chǎn)和管理問題的本質，明確目標和錯綜復雜的約束條件，通過調(diào)查和統(tǒng)計資料獲取原始可靠的數(shù)據(jù)。建模過程的規(guī)律：①通過對實際問題的分析、理解，明確那些是決策變量，目標要求是什么，有哪些資源限制條件；②把變量、常數(shù)、約束條件、目標要求的相互關系聯(lián)系起來列出相應的方程式；③注意變量、系數(shù)、常數(shù)的計量單位要統(tǒng)一。102線性規(guī)劃問題的應用

問題需滿足的條件

①目標函數(shù)能用數(shù)值指標來反映，且為線性函數(shù)；

②存在多種方案及有關數(shù)據(jù)；

③要達到的目標是在一定約束條件下實現(xiàn)的，這些條件可用線性等式或不等式描述。相關問題生產(chǎn)計劃問題（合理利用資源，使利潤最高或完成計劃）合理配料問題（保證飲食、藥品等效果前提下使成本最低）投資方案選擇問題（固定資金投入時使效益最高）人員分派問題（多項任務分配，使人數(shù)最少或效率最大）合理下料問題（在給定材料中截取零件，使用料最?。┻\輸問題＊（多個產(chǎn)銷地及運價限制，安排方案使運費最低）……103生產(chǎn)計劃問題：如何安排生產(chǎn)使利潤最大？資料如圖

設備產(chǎn)品ABCD利潤（元）

Ⅰ21402

Ⅱ22043有效臺時1281612max

x1,x2≥0s.t.2x1+2x2≤12z=2x1+3x2

x1+2x2≤84x1≤164x2≤12設xj表示第j種產(chǎn)品在計劃期內(nèi)的產(chǎn)量104合理配料問題：資料如圖

設xj表示第j種營養(yǎng)物所需克數(shù)z=4x1+3x2+6x3+5x4+2.7x5+2.2x