運(yùn)籌學(xué)緒論、第一章 2

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

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

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

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

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

建立模型分析并求解模型檢驗(yàn)并評價模型

應(yīng)用或?qū)嵤┠Ｐ偷慕?1引入數(shù)學(xué)方法解決實(shí)際問題

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

--從全局考察問題應(yīng)用性

--源于實(shí)踐、為了實(shí)踐、服務(wù)于實(shí)踐交叉學(xué)科

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

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

--問題的復(fù)雜和多樣性運(yùn)籌學(xué)的性質(zhì)與特點(diǎn)22如何學(xué)習(xí)運(yùn)籌學(xué)課程

學(xué)習(xí)運(yùn)籌學(xué)要把重點(diǎn)放在分析、理解有關(guān)的概念、思路上。在自學(xué)過程中，應(yīng)該多向自己提問，例如一個方法的實(shí)質(zhì)是什么，為什么這樣進(jìn)行，怎么進(jìn)行等。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ⅰ21402

Ⅱ22043有效臺時1281612目標(biāo)max

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

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

約束條件x1+2x2≤84x1≤164x2≤12subjectto函數(shù)數(shù)學(xué)模型27例3、合理配料問題數(shù)學(xué)模型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)物各多少克，才能既獲得每日最少所需又使花費(fèi)最??？28二、數(shù)學(xué)模型組成要素：

決策變量

約束條件

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

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

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

=－2x1

+

x2

－3x3

maxz

=－2x1

+

(x2－

x2)

+3x3

+0x4+0x53x1

－2(x2－

x2)－

x3

=－4－3x1

+2(x2－

x2)+

x3

=4解：設(shè)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),從而得到標(biāo)準(zhǔn)形式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ī)劃問題化為標(biāo)準(zhǔn)形式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),從而得到標(biāo)準(zhǔn)形式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練習(xí)：將下列線性規(guī)劃問題化為標(biāo)準(zhǔn)形式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解：設(shè)引入變量令第三個約束方程兩邊乘(－1),從而得到標(biāo)準(zhǔn)形式39

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

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

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

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

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

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

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

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

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

C(0<<1)頂點(diǎn)：凸集C中不在任意兩不同點(diǎn)連線上的點(diǎn)對x,任給x1,x2C,不存在x=x1+(1－)x2(0<<1)凸集非凸集42二、圖解法步驟：將約束條件在圖上表示建立直角坐標(biāo)系確立滿足約束條件的解的范圍(可行域)繪制出目標(biāo)函數(shù)的圖形在可行域中確定最優(yōu)解定義：用圖示的方法求解線性規(guī)劃問題的最優(yōu)解優(yōu)點(diǎn)：直觀性強(qiáng)，計算方便缺點(diǎn)：只適用于問題中是兩(三)個變量的情況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思考：若目標(biāo)函數(shù)改為minz=x1+x2呢？若改為minz=x1+

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

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

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

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

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

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

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

，

令非基變量基變量為，|B|≠0基變量的唯一解基解最多個52(一)基解與基可行解基解：令非基變量為零，對m個基變量求解后合并所得的解。基可行解：滿足變量非負(fù)約束條件xj≥0的基解?？尚谢簩?yīng)于基可行解的基?；尚薪饪尚薪夥强尚薪饣?3基基解是否基可行解目標(biāo)函數(shù)值例題：列出全部基、基解、基可行解和指出最優(yōu)解s.t.s.t.標(biāo)準(zhǔn)化系數(shù)矩陣:54例題：用圖解法求最優(yōu)解s.t.x1+x2=3x1+2x2=4(2,1)12341230x2

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

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

或

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

，

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

，

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

s.t.整理后可得

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

x1,x2≥0s.t.

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

4x1

≤

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

+3x2s.t.引入變量得到標(biāo)準(zhǔn)形式解：+0x55x2+x5

=154x1

+

x4=162x1

+2x2+

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

+3x2s.t.引入變量得到標(biāo)準(zhǔn)形式解：+0x55x2+x5

=154x1

+

x4=162x1

+2x2+

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

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

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

x2－x3

－

x5

=1解：引入變量從而得到標(biāo)準(zhǔn)形式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(五)單純形法的進(jìn)一步討論采用添加人工變量的方法因是在等式中人為加進(jìn)的，為保證約束條件的意義，最優(yōu)解中人工變量只能等于0

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

人工變量的添加不能影響最優(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，可令目標(biāo)函數(shù)中人工變量的系數(shù)為足夠大的一個負(fù)值，用“－M”代表。由于系數(shù)是一個足夠大的負(fù)值，因此，只要人工變量的取值不為零，目標(biāo)函數(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此時所有檢驗(yàn)數(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)任何問題。

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

第一階段：構(gòu)造判斷是否存在可行解的模型

構(gòu)造僅含人工變量(系數(shù)為1)且要求極小化的目標(biāo)函數(shù)用單純形法求解，若minw=0，說明人工變量為0，問題存在基可行解，進(jìn)入第二個階段；若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ā)，去掉人工變量，引入原來的目標(biāo)函數(shù)，繼續(xù)迭代，找出問題的最終解maxz=－3x1

+

0x2

+

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

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

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

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

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

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

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

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

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

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

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

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

問題需滿足的條件

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

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

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

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

Ⅰ21402

Ⅱ22043有效臺時1281612max

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

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

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