林齊寧-數(shù)據(jù)、模型與決策一運(yùn)籌學(xué).ppt

1、運(yùn)籌學(xué)Operational Research,TelE_mail:,緒 論,一、運(yùn)籌學(xué)的起源與發(fā)展 二、運(yùn)籌學(xué)的定義和主要研究分支 三、運(yùn)籌學(xué)的特點(diǎn)及研究對(duì)象 四、運(yùn)籌學(xué)解決問(wèn)題的方法步驟 五、運(yùn)籌學(xué)與其他學(xué)科的關(guān)系,一、運(yùn)籌學(xué)的起源與發(fā)展,起源于二次大戰(zhàn)的一門新興交叉學(xué)科 與作戰(zhàn)問(wèn)題相關(guān) 如雷達(dá)的設(shè)置、運(yùn)輸船隊(duì)的護(hù)航、反潛作戰(zhàn)中深水炸彈的深度、飛行員的編組、軍事物資的存儲(chǔ)等 英國(guó)稱為 Operational Research 美國(guó)稱為 Operations Research 戰(zhàn)后在經(jīng)濟(jì)、管理和機(jī)關(guān)學(xué)校及科研單位繼續(xù)研究 1952年，Morse 和 Kimball出

2、版運(yùn)籌學(xué)方法 1948年英國(guó)首先成立運(yùn)籌學(xué)會(huì) 1952年美國(guó)成立運(yùn)籌學(xué)會(huì) 1959年成立國(guó)際運(yùn)籌學(xué)聯(lián)合會(huì)(IFORS) 我國(guó)于1982年加入IFORS，并于1999年8月組織了第15屆大會(huì),一、運(yùn)籌學(xué)的起源與發(fā)展,1、中國(guó)運(yùn)籌學(xué)會(huì)簡(jiǎn)介 50年代中期，我國(guó)著名科學(xué)家錢學(xué)森、許國(guó)志等教授將運(yùn)籌學(xué)從西方引入國(guó)內(nèi)。1980年4月，中國(guó)數(shù)學(xué)會(huì)運(yùn)籌學(xué)分會(huì)成立。1991年，中國(guó)運(yùn)籌學(xué)會(huì)成立。歷屆學(xué)會(huì)理事長(zhǎng)有，華羅庚、越民義，徐光輝，章祥蓀，袁亞湘， 2、中國(guó)系統(tǒng)工程學(xué)會(huì)簡(jiǎn)介 1、1979年由錢學(xué)森、宋健、關(guān)肇直、許國(guó)志等21名專家、學(xué)者共同倡議并籌備。1980年11月18日在北京正式成立。 第一屆理事會(huì)理事

3、長(zhǎng)關(guān)肇直，第二、三屆理事長(zhǎng)許國(guó)志。第四、五屆理事長(zhǎng)顧基發(fā)、第六屆理事長(zhǎng)陳光亞。 3、運(yùn)籌學(xué)、系 統(tǒng)工程 主要研究人員構(gòu)成 1）數(shù)學(xué)：如華羅庚、越民義，徐光輝，章祥蓀，袁亞湘，許國(guó)志，顧基發(fā)等； 2）控制論：張仲俊，劉豹，陳珽，鄭維敏，趙純均，陳劍等 3）管理等專業(yè)相關(guān)教學(xué)、科研技術(shù)人員,一、運(yùn)籌學(xué)的起源與發(fā)展,4、相關(guān)研究機(jī)構(gòu)和高校 1）中國(guó)科學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)研究院系統(tǒng)科學(xué)研究所 2）中國(guó)科學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)研究院應(yīng)用數(shù)學(xué)研究所 3）哈工大：胡運(yùn)權(quán)，黃梯云，錢國(guó)明等 4）天津大學(xué)：劉豹，顧培亮，張維，杜 綱等 5）西安交大：汪應(yīng)洛，席酉民等 6）上海交大：張仲俊，王浣塵等 7）清華大學(xué)：鄭維

4、敏，趙純均，陳劍等； 8）大連理工：王眾托，胡祥培等 9）北航：顧昌耀，黃海軍等 10）北理工 ：吳滄浦，吳祈宗，張強(qiáng)等,二、運(yùn)籌學(xué)的定義和主要研究分支,運(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)人員、工商企業(yè)、政府和國(guó)防等方面解決發(fā)生的各種問(wèn)題，其方法是發(fā)展一個(gè)科學(xué)的系統(tǒng)模式，并運(yùn)用這種模式預(yù)測(cè)，比較各種決策及其產(chǎn)生的后果，以幫助主管人員科學(xué)地決定工作方針和政策英國(guó)運(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)最

5、有效的管理中國(guó)百科全書 現(xiàn)代運(yùn)籌學(xué)涵蓋了一切領(lǐng)域的管理與優(yōu)化問(wèn)題，稱為 Management Science,二、運(yùn)籌學(xué)的定義和主要研究分支,運(yùn)籌學(xué)的分支 數(shù)學(xué)規(guī)劃：線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃、動(dòng)態(tài)規(guī)劃、目標(biāo)規(guī)劃等 圖論與網(wǎng)路理論 隨機(jī)服務(wù)理論：排隊(duì)論 存儲(chǔ)理論 網(wǎng)絡(luò)計(jì)劃方法 決策理論 對(duì)策論 系統(tǒng)仿真：隨機(jī)模擬技術(shù)、系統(tǒng)動(dòng)力學(xué) 可靠性理論 金融工程,11,三、運(yùn)籌學(xué)的特點(diǎn)及研究對(duì)象,運(yùn)籌學(xué)的特點(diǎn)： 1)優(yōu)化 以整體最優(yōu)為目標(biāo)，從系統(tǒng)的觀點(diǎn)出發(fā)，力圖以整個(gè)系統(tǒng)最佳的方式來(lái)協(xié)調(diào)各部門之間的利害沖突，從而求出問(wèn)題的最優(yōu)解。所以運(yùn)籌學(xué)可看成是一門優(yōu)化技術(shù)，為解決各類問(wèn)題提供優(yōu)化方法 2定量 為所

6、研究的問(wèn)題提供定量的解決方案。如采用運(yùn)籌學(xué)研究資源分配問(wèn)題時(shí)，其求解結(jié)果是一個(gè)定量的最優(yōu)資源分配方案。 運(yùn)籌學(xué)的研究對(duì)象： 來(lái)自生產(chǎn)管理過(guò)程中的具體問(wèn)題，如資源分配、物資調(diào)度，生產(chǎn)計(jì)劃與控制等。,四、運(yùn)籌學(xué)解決問(wèn)題的方法步驟,1、理清問(wèn)題、明確目標(biāo) 2、建立模型 討論：什么叫模型 3、求解模型。建立模型之后，需要設(shè)計(jì)相應(yīng)算法進(jìn)行求解，實(shí)際問(wèn)題運(yùn)算量一般都很大，通常需要用計(jì)算機(jī)求解。 4、結(jié)果分析 討論：模型計(jì)算結(jié)果與已有的經(jīng)驗(yàn)或知識(shí)進(jìn)行比較 1）模型計(jì)算結(jié)果和已有的經(jīng)驗(yàn)或知識(shí)比較一致 2）模型計(jì)算結(jié)果和已有的經(jīng)驗(yàn)或知識(shí)差異較大 你喜歡那一種情況？,五、運(yùn)籌學(xué)與其他學(xué)科的關(guān)系,運(yùn)籌學(xué)目標(biāo)分析、建

7、模、求解和結(jié)果分析需要用到很多相關(guān)學(xué)科的知識(shí)，它與如下學(xué)科的知識(shí)關(guān)系比較密切。 1、數(shù)學(xué)：學(xué)習(xí)、應(yīng)用運(yùn)籌學(xué)應(yīng)該具備較廣的數(shù)學(xué)知識(shí)，許多運(yùn)籌學(xué)者來(lái)自數(shù)學(xué)專業(yè)就是這個(gè)原因，有人甚至認(rèn)為運(yùn)籌學(xué)是一門應(yīng)用數(shù)學(xué)； 2、管理學(xué)：運(yùn)籌學(xué)研究對(duì)象是生產(chǎn)管理過(guò)程的具體問(wèn)題，在利用運(yùn)籌學(xué)理論和方法解決具體問(wèn)題時(shí)，需要的涉及管理科學(xué)的有關(guān)理論； 3、計(jì)算機(jī)：運(yùn)籌學(xué)所研究的實(shí)際問(wèn)題通常都是比較復(fù)雜，而且規(guī)模比較大，在求解這些問(wèn)題時(shí)，必須借助計(jì)算機(jī)來(lái)完成。,第一章 線性規(guī)劃,1.1 線性規(guī)劃模型 1.1.1問(wèn)題的提出 一、例1、多產(chǎn)品生產(chǎn)問(wèn)題（Max, ）,另,問(wèn)該工廠應(yīng)如何安排生產(chǎn)才能使工廠的總收入最大？,一、例1、

8、多產(chǎn)品生產(chǎn)問(wèn)題（Max, ）,設(shè)x1, x2 分別代表甲、乙兩種電纜的生產(chǎn)量，f(x)為工廠的總收入，則上述問(wèn)題可用如下數(shù)學(xué)模型來(lái)表示,其中，OBJ（Objective）表示目標(biāo)，S.t.（Subject to）表示滿足于。表示在滿足銅、鉛資源和需求等約束條件下，使工廠的總收入這一目標(biāo)達(dá)到最大。最優(yōu)解為,二、例2、配料問(wèn)題（min, ),某混合飼料加工廠計(jì)劃從市場(chǎng)上購(gòu)買甲、乙兩種原料生產(chǎn)一種混合飼料。混合飼料對(duì)VA、VB1、VB2和VD的最低含量有一定的要求。已知單位甲、乙兩種原料VA、VB1、VB2和VD的含量，單位混合飼料對(duì)VA、VB1、VB2和VD的最低含量以及甲、乙兩種原料的單位價(jià)格如

9、下表所示。,問(wèn)該該加工廠應(yīng)如何搭配使用甲乙兩種原料，才能使混合飼料在滿足VA、VB1、VB2和VD的最低含量要求條件下，總成本最??？,二、例2、配料問(wèn)題（MIN, ),設(shè) x1, x2分別代表混合單位飼料對(duì)甲、乙兩種原料的用量，f(x)表示單位混合飼料所需要的成本，則上述問(wèn)題的線性規(guī)劃數(shù)學(xué)模型如下：,該數(shù)學(xué)模型的最優(yōu)解為該問(wèn)題的最優(yōu)解為 x1=3.69，x2=0.77，minf(x)=1.49,三、線性規(guī)劃數(shù)學(xué)模型的特征和定義,1、線性規(guī)劃數(shù)學(xué)模型的特征： 1）有一組決策變量（x1，x2，xn）表示某一方案。這一組決策變量的具體值就代表一個(gè)具體方案； 2）有一個(gè)目標(biāo)函數(shù)，該目標(biāo)函數(shù)根據(jù)其的具體

10、性質(zhì)取最大值或最小值。當(dāng)目標(biāo)為成本型時(shí)取最小，而當(dāng)目標(biāo)為效益型時(shí)取最大。 3）有一組約束方程，包括決策變量的非負(fù)約束； 4）目標(biāo)函數(shù)和約束方程都是線性的。 2、線性規(guī)劃數(shù)學(xué)模型的定義 定義1.1 有一個(gè)目標(biāo)函數(shù)和一組約束方程，且目標(biāo)函數(shù)和約束方程都是線性的數(shù)學(xué)模型稱為線性規(guī)劃數(shù)學(xué)模型。,四、線性規(guī)劃數(shù)學(xué)模型的背景模型和思考,1、線性規(guī)劃數(shù)學(xué)模型的背景模型： 例1.1的多產(chǎn)品生產(chǎn)計(jì)劃問(wèn)題的數(shù)學(xué)模型稱為線性規(guī)劃的背景模型。把該背景模型的條件一般化后可敘述如下：用有限量的幾種資源生產(chǎn)若干種產(chǎn)品，如何安排生產(chǎn)，才能使工廠的總收入或利潤(rùn)達(dá)到最大。 2、背景模型的思考 1）討論：什么叫背景模型 能夠幫助我

11、們理解和記住一些相對(duì)抽象和復(fù)雜問(wèn)題的簡(jiǎn)單問(wèn)題模型。 2）背景模型的思考 利用一些相對(duì)比較簡(jiǎn)單的問(wèn)題來(lái)闡述一些相對(duì)復(fù)雜和抽象的運(yùn)籌學(xué)中的一些基礎(chǔ)概念和原理是本課程力求在教學(xué)中體現(xiàn)的第一個(gè)特點(diǎn)，希望大家用心體會(huì)。,1.1.2 線性規(guī)劃數(shù)學(xué)模型的一般表示方式,1、和式,2、向量式,3、矩陣式,1.1.3 線性規(guī)劃的圖解法,f(x)=36,線性規(guī)劃問(wèn)題的幾個(gè)特點(diǎn)：,1、線性規(guī)劃的可行域?yàn)橥辜?討論：什么叫凸集？ 集合中任意兩點(diǎn)連線上的一切點(diǎn)仍然在該集合中，在平面上為凸多邊形，在空間上為凸幾何體； 討論：最優(yōu)解在那里取得？ 2、線性規(guī)劃的最優(yōu)解一定可在其凸集的某一頂點(diǎn)上達(dá)到； 討論：什么情況有最優(yōu)解？

12、最優(yōu)解的存在性條件？ 3、線性規(guī)劃若有可行域且其可行域有界，則一定有最優(yōu)解。 上述3個(gè)結(jié)論是線性規(guī)劃的3個(gè)基礎(chǔ)定理，可以用嚴(yán)格的數(shù)學(xué)方法進(jìn)行證明。我們以簡(jiǎn)單、直觀的圖解法方式給出，相信大家是可以接受的。,1.3 線性規(guī)劃求解的基礎(chǔ)原理和單純形法,1.3.1 線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形 一、線性規(guī)劃模型一般形式,二、求解思路 1、規(guī)定一標(biāo)準(zhǔn)型線性的規(guī)劃問(wèn)題數(shù)學(xué)模型； 2、如何把非標(biāo)準(zhǔn)形的線性規(guī)劃問(wèn)題數(shù)學(xué)模型轉(zhuǎn)化為標(biāo)準(zhǔn)形線性規(guī)劃問(wèn)題數(shù)學(xué)模型？ 3、如何求解標(biāo)準(zhǔn)形線性規(guī)劃問(wèn)題數(shù)學(xué)模型。,三、線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形,在上述線性規(guī)劃標(biāo)準(zhǔn)形中，決策變量的個(gè)數(shù)取n+m個(gè)是習(xí)慣表示法。我們知道，對(duì)于線性規(guī)劃背景模型，

13、有m個(gè)約束方程，且每個(gè)約束方程的不等式均為“”號(hào)。如果我們?cè)诿總€(gè)約束方程的左邊加上一個(gè)大于等于0的變量，則可將各個(gè)約束方程的“”號(hào)轉(zhuǎn)變?yōu)椤?”。此時(shí)，決策變量就有n+m個(gè)。,四、變換的方法,1、目標(biāo)函數(shù)為min型，價(jià)值系數(shù)一律反號(hào)。令 g(x) = -f(x) = -CX, 有 min f(x) = - max - f(x) = - max g(x) 2、第i 個(gè)約束的bi 為負(fù)值，則該行左右兩端系數(shù)同時(shí)反號(hào)，同時(shí)不等號(hào)也要反向 3、第i 個(gè)約束為 型，在不等式左邊增加一個(gè)非負(fù)的變量xn+i ，稱為松弛變量；同時(shí)令 cn+i = 0 4、第i 個(gè)約束為 型，在不等式左邊減去一個(gè)非負(fù)的變量xn+

14、i ，稱為剩余變量；同時(shí)令 cn+i = 0 5、若xj 0，令 xj= -xj ，代入非標(biāo)準(zhǔn)型，則有xj 0 6、若xj 不限，令 xj= xj - xj， xj 0，xj 0，代入非標(biāo)準(zhǔn)型,五、 變換舉例：,1.3.2 線性規(guī)劃問(wèn)題的解和基礎(chǔ)定理,本章開始到現(xiàn)在已討論的內(nèi)容，相信大部分讀者都會(huì)感到比較容易理解和掌握。這一節(jié)我們將要討論關(guān)于線性規(guī)劃問(wèn)題解的一些基礎(chǔ)概念和定理，與前面討論的內(nèi)容相比，線性規(guī)劃問(wèn)題解的一些基礎(chǔ)概念略顯難一些，其中比較難的概念有線性規(guī)劃問(wèn)題的基和基礎(chǔ)解等相關(guān)概念。為了幫助大家比較容易理解這些概念，我們先從大家熟悉的兩個(gè)變量?jī)蓚€(gè)線性方程組這一簡(jiǎn)單問(wèn)題入手，然后逐步過(guò)渡

15、到我們所要討論的線性規(guī)劃問(wèn)題的基和基礎(chǔ)解等相關(guān)概念。 著名數(shù)學(xué)家笛卡爾曾說(shuō)過(guò)，他最擅長(zhǎng)做的兩件事是： 1)第一做簡(jiǎn)單事； 2)第二是將復(fù)雜事變?yōu)楹?jiǎn)單事。 本課程將從大家熟悉的一些簡(jiǎn)單問(wèn)題入手，然后逐步過(guò)渡到運(yùn)籌學(xué)一些相對(duì)比較抽象和難的概念和原理。這是本課程教學(xué)力求的另一特點(diǎn)。,一、線性方程組的解,考慮如下線性方程組的解：,再考慮如下線性方程組的解：,一、線性方程組的解,類似地，如果將方程組（3）中的變量x2或x1當(dāng)成常數(shù)，分別移到其方程的右邊后采用消元法進(jìn)行求解，則也可得到如下兩組通解及其特解：,一、線性方程組的解,仔細(xì)觀察和思考方程組（3）的三組通解（4）、（6）和（8）或三組特解（5）、（

16、7）和（9）是如何得到的，以及能夠得到這些通解或特解的條件是什么？根據(jù)求解線性方程組克萊姆條件可知，能夠得到方程組（3）的通解（4）或特解（5）的條件是方程組（3）中的變量x1和x2的系數(shù)矩陣行列式不等于0，即,或變量x1和x2的系數(shù)矩陣B1是非奇異矩陣或變量x1和x2的系數(shù)列向量是線性無(wú)關(guān)。顯然，這三個(gè)條件是等價(jià)的。,一、線性方程組的解,同樣，由于方程組組（3）中的變量x1和x3的系數(shù)矩陣行列式|B2|不等于0與變量x2和x3的系數(shù)矩陣行列式|B3|不等于0，即,才能得到方程組（3）的通解或特解（6）或（7）與通解或特解（8）或（9）。,將上面討論的方程組（3）加上一目標(biāo)函數(shù)和變量非負(fù)約束條

17、件后就變成一標(biāo)準(zhǔn)型線性規(guī)劃。如：,一、線性方程組的解,對(duì)于上述標(biāo)準(zhǔn)型線性規(guī)劃（10）,稱 B1 、B2和B3為線性規(guī)劃（10）的基。因利用其中任何一個(gè)基B1 或B2或B3，都能得到線性規(guī)劃（10）的一組通解和特解（見式（4）-（9）。,變量x1和x2為基變量，變量x3為非基變量，令x3=0，得解（5）為線性規(guī)劃（10）的基礎(chǔ)解，但因該基礎(chǔ)解中x1= -10，不滿足線性規(guī)劃（10）的變量非負(fù)約束條件，因此，該基礎(chǔ)解（5）是線性規(guī)劃（10）的基礎(chǔ)非可行解。,變量x1和x3為基變量，變量x2為非基變量，令x2=0，得解（7）為線性規(guī)劃（10）的基礎(chǔ)解。該基礎(chǔ)解中x1和x3均大于0，滿足線性規(guī)劃（10

18、）的變量非負(fù)約束條件，因此，該基礎(chǔ)解（7）是線性規(guī)劃（10）的基礎(chǔ)可行解。,變量x2和x3為基變量，變量x1為非基變量，令x1=0，得解（9）為線性規(guī)劃（10）的基礎(chǔ)解.該基礎(chǔ)解中x2和x3均大于0，滿足線性規(guī)劃（10）的變量非負(fù)約束條件，因此，該基礎(chǔ)解（9）是線性規(guī)劃（10）的基礎(chǔ)可行解。,二、標(biāo)準(zhǔn)型線性規(guī)劃解的若干基礎(chǔ)概念,標(biāo)準(zhǔn)型有 n+m 個(gè)變量， m 個(gè)約束行 “基”的概念 在標(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 ,

19、 P2 , , Pm 稱為基向量 與基向量對(duì)應(yīng)的變量稱為基變量，記為 XB = ( x1 , x2 , , xm )T，其余的變量稱為非基變量，記為 XN = ( xm+1 , xm+2 , , xm+n ) T ， 故有 X = （XB ， XN ) 最多有 個(gè)基,二、標(biāo)準(zhǔn)型線性規(guī)劃解的若干基礎(chǔ)概念,可行解與非可行解 滿足約束條件和非負(fù)條件的解 X 稱為可行解，不滿足約束條件或非負(fù)條件的解 X 稱為非可行解 基礎(chǔ)解 對(duì)應(yīng)某一基B且令其非基變量 XN = 0，求得基變量 XB的值。稱X = (XB , XN)T為基礎(chǔ)解。 其中，XB = B1 b， XN = 0 XB 是基礎(chǔ)解必須滿足如下條件

20、： 1）非0分量的個(gè)數(shù) m； 2、m個(gè)基變量所對(duì)應(yīng)的系數(shù)矩陣為非奇異的； 3、滿足m個(gè)約束條件。,二、標(biāo)準(zhǔn)型線性規(guī)劃解的若干基礎(chǔ)概念,基礎(chǔ)可行解與基礎(chǔ)非可行解 基礎(chǔ)解 XB 的非零分量都 0 時(shí)，稱為基礎(chǔ)可行解，否則為基礎(chǔ)非可行解。 退化解 基礎(chǔ)可行解的非零分量個(gè)數(shù) m 時(shí)，稱為退化解 可行基 對(duì)應(yīng)于基礎(chǔ)可行解的基稱為可行基 最優(yōu)解 使目標(biāo)函數(shù)達(dá)到最優(yōu)的基礎(chǔ)可行解稱為最優(yōu)解 無(wú)窮多最優(yōu)解 當(dāng)最優(yōu)解的基變量組成不止一個(gè)時(shí)，線性規(guī)劃有無(wú)窮多最優(yōu)解,三、線性規(guī)劃標(biāo)準(zhǔn)型問(wèn)題解的關(guān)系,約束方程的 解空間,基礎(chǔ)解,可行解,非可行解,基礎(chǔ) 可行解,退化解,四、線性規(guī)劃解的判定,對(duì)于某一線性規(guī)劃的任意一個(gè)解X

21、，我們?nèi)绾闻卸╔是基礎(chǔ)解、或是基礎(chǔ)可行解、或是基礎(chǔ)非可行解、或是非可行解、或是可行解呢？ 判定步驟： 1、寫出給定線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型線性規(guī)劃； 2、根據(jù)基礎(chǔ)解的三個(gè)條件判定X是否是基礎(chǔ)解。當(dāng)三個(gè)條件均滿足時(shí)，X才是基礎(chǔ)解；否則X不是基礎(chǔ)解。若X是基礎(chǔ)解，轉(zhuǎn)3；否則，轉(zhuǎn)4； 3、X是否滿足非負(fù)約束，即其基變量值是否都大于0？若是，X是基礎(chǔ)可行解；否則X是基礎(chǔ)非可行解。 4、將X代入給定線性規(guī)劃的所有約束方程，包括非負(fù)約束，若X滿足所有約束方程，則X為可行解，否則X為非可行解。,五、線性規(guī)劃解的判定舉例,六、線性規(guī)劃問(wèn)題解的一些基本定理,定理1 若線性規(guī)劃問(wèn)題存在可行域，則其可行域是凸集。 定理

22、2 線性規(guī)劃問(wèn)題可行域的頂點(diǎn)與其基礎(chǔ)可行解一一對(duì)應(yīng)。 定理3 若線性規(guī)劃問(wèn)題存在可行域，則它必有基礎(chǔ)可行解。 定理4 若線性規(guī)劃問(wèn)題存在可行域且其可行域有界，則它必有最優(yōu)解。 定理5 若線性規(guī)劃問(wèn)題存在最優(yōu)解，則其最優(yōu)解一定可以在其可行域的某個(gè)頂點(diǎn)上取得。,1.3.3 單純型法的基礎(chǔ)原理,一、單純形法的基礎(chǔ)思路和步驟 （一）基礎(chǔ)思路 從一個(gè)基礎(chǔ)可行解出發(fā)，設(shè)法得到另一個(gè)更好的基礎(chǔ)可行解，直到目標(biāo)函數(shù)達(dá)到最優(yōu)時(shí)，基礎(chǔ)可行解即為最優(yōu)解。 （二）基礎(chǔ)步驟 1、求一個(gè)基礎(chǔ)可行解，稱為初始基礎(chǔ)可行解。求初始基礎(chǔ)可行解的方法必須簡(jiǎn)單實(shí)用，且具有通用性； 2、最優(yōu)檢驗(yàn)。即檢驗(yàn)任一基礎(chǔ)可行解是否是最優(yōu)解。若是

23、，則停止計(jì)算；否則，轉(zhuǎn)3）； 3、確定改善方向，求得另一個(gè)更好的基礎(chǔ)可行解；轉(zhuǎn)2，直到求得最優(yōu)解為止。 通常把這三個(gè)基礎(chǔ)步驟稱為最優(yōu)化三步曲。事實(shí)上，這三部曲對(duì)求解其它最優(yōu)化問(wèn)題（如非線性規(guī)劃等）也是適用的。,單純型法的基礎(chǔ)步驟,二、單純性法基本原理,為了使大家比較直觀容易地理解利用單純形法求解線性規(guī)劃問(wèn)題三個(gè)步驟的基礎(chǔ)原理，我們先以解線性方程組的方法來(lái)求解例1線性規(guī)劃。,解：（一）標(biāo)準(zhǔn)化,（二）選擇初始基礎(chǔ)可行解,從系數(shù)矩陣A中可知，x3、x4和x5的系數(shù)列向量P3，P4和P5是線性獨(dú)立，這些向量可構(gòu)成一個(gè)基B0（初始基） 對(duì)應(yīng)于基B0的變量 x3、x4和x5為基變量，其它兩個(gè)變量x1和x2

24、為非基變量。即 XB0=（x3，x4，x5)T， XN0=（x1，x2)T,令非基變量x1=x2=0，可得一初始基礎(chǔ)可行解 X(0) = (0，0，10，8，7)T 此時(shí)，對(duì)應(yīng)于X(0)的目標(biāo)函數(shù)f (X(0) )=6x1+4x2=0,（三）最優(yōu)檢驗(yàn),將（2）式代入(1)的目標(biāo)函數(shù)后可得 f (X)=0+6x1+4x2 （3） 從目標(biāo)函數(shù)（3）可知，非基變量x1和x2的系數(shù)都是正數(shù)，所以X(0)不是最優(yōu)解。 （四）求另一個(gè)更好的基礎(chǔ)可行解 1、確定換入變量及其值 從從目標(biāo)函數(shù)（3）可知，非基變量x1的系數(shù)大于x2的系數(shù)，所以，可確定x1為換入變量,由于,所以，當(dāng)另一個(gè)非基變量x2仍然為0時(shí)，由

25、（4）式可得到換入變量x1的值為 x1=Min10/2，8/1，-=5,2、確定換出變量,由于基變量的個(gè)數(shù)只能等于約束方程的個(gè)數(shù)m，在本例中，m=3，所以，當(dāng)有一個(gè)非基變量做為換入變量變?yōu)榛兞繒r(shí)，就必須有一個(gè)基變量做為換出變量變?yōu)榉腔兞?。即從所有基變量中，將其中一個(gè)大于0的基變量變?yōu)榈扔?的非基變量，該非基變量就是換出變量。從（4）式可知，當(dāng)x1=5時(shí)，x3=0，所以x3為換出變量。由此得到線性規(guī)劃（1）的一個(gè)新的基B1和一組新的基變量與非基變量。,XB1=（x1，x4，x5)T，XN1=（x3，x2)T,3、求另一個(gè)更好的基礎(chǔ)可行解,將（1)約束方程中對(duì)應(yīng)于基B1的非基變量x3和x2移到

26、方程的右邊后可得,令非基變量x2=x3=0，可得另一基礎(chǔ)可行解 X(1) = (5，0，0，3，7)T 此時(shí)，對(duì)應(yīng)于X(1)的目標(biāo)函數(shù)f (X(1) )=6x1+4x2=30 f (X(0) )=0,（五）最優(yōu)檢驗(yàn),將（5）式代入(1)的目標(biāo)函數(shù)后可得 f (X)=30+x2-3x3 （6） 從目標(biāo)函數(shù)（6）可知，非基變量x2的系數(shù)是正數(shù)，所以X(1)不是最優(yōu)解。,（六）求另一個(gè)更好的基礎(chǔ)可行解,1、確定換入變量及其值 從從目標(biāo)函數(shù)（6）可知，只有非基變量x2的系數(shù)為正，所以，可確定x2為換入變量。,由于,所以，當(dāng)另一個(gè)非基變量x3仍然為0時(shí)，由（7）式可得到換入變量x1的值為 x2=Min1

27、0/0.5，3/0.5，7/1=6,2、確定換出變量 從（7）式可知，當(dāng)x2=6時(shí)，x4=0，所以x4為換出變量。由此得到線性規(guī)劃（1）的一個(gè)新的基B2和一組新的基變量與非基變量。 B2=(P1 ,P2 ,P5 ), XB2=（x1，x2，x5)T，XN2=（x3，x4)T,3、求另一個(gè)更好的基礎(chǔ)可行解,將（1)約束方程中對(duì)應(yīng)于基B2的非基變量x3和x4移到方程的右邊后可得,令非基變量x3=x4=0，可得另一基礎(chǔ)可行解 X(2) = (2，6，0，0，1)T 此時(shí)，對(duì)應(yīng)于X(2)的目標(biāo)函數(shù)f (X(2) )=6x1+4x2=36 f (X(1) )=30,（七）最優(yōu)檢驗(yàn) 將（8）式代入(1)的目標(biāo)函數(shù)后可得 f (X)=36-2x3-2x4 （9） 從目標(biāo)函數(shù)（9）可知，非基變量x3和x4的系數(shù)都是負(fù)數(shù)，所以X(2)是最優(yōu)解。即X*= X(2) = (2，6，0，0，1)T ,f (X*)=36,三、求初始基礎(chǔ)可行解（背景模型，MAX, ),設(shè)線性規(guī)劃問(wèn)題為,另設(shè)bi0 (i=1,