數(shù)據(jù)模型與決策一運(yùn)籌學(xué)和特殊情況下的投資決策

運(yùn)籌學(xué)

OperationalResearch林齊寧博士，教授北京郵電大學(xué)經(jīng)濟(jì)管理學(xué)院Telmail:linqining66@

緒論一、運(yùn)籌學(xué)的起源與發(fā)展二、運(yùn)籌學(xué)的定義和主要研究分支三、運(yùn)籌學(xué)的特點(diǎn)及研究對(duì)象四、運(yùn)籌學(xué)解決問題的方法步驟五、運(yùn)籌學(xué)與其他學(xué)科的關(guān)系一、運(yùn)籌學(xué)的起源與發(fā)展起源于二次大戰(zhàn)的一門新興交叉學(xué)科與作戰(zhàn)問題相關(guān)如雷達(dá)的設(shè)置、運(yùn)輸船隊(duì)的護(hù)航、反潛作戰(zhàn)中深水炸彈的深度、飛行員的編組、軍事物資的存儲(chǔ)等英國稱為OperationalResearch美國稱為OperationsResearch戰(zhàn)后在經(jīng)濟(jì)、管理和機(jī)關(guān)學(xué)校及科研單位繼續(xù)研究1952年，Morse和Kimball出版《運(yùn)籌學(xué)方法》1948年英國首先成立運(yùn)籌學(xué)會(huì)1952年美國成立運(yùn)籌學(xué)會(huì)1959年成立國際運(yùn)籌學(xué)聯(lián)合會(huì)(IFORS)我國于1982年加入IFORS，并于2023年8月組織了第15屆大會(huì)一、運(yùn)籌學(xué)的起源與發(fā)展1、中國運(yùn)籌學(xué)會(huì)簡介50年代中期，我國著名科學(xué)家錢學(xué)森、許國志等教授將運(yùn)籌學(xué)從西方引入國內(nèi)。1980年4月，中國數(shù)學(xué)會(huì)運(yùn)籌學(xué)分會(huì)成立。1991年，中國運(yùn)籌學(xué)會(huì)成立。歷屆學(xué)會(huì)理事長有，華羅庚、越民義，徐光輝，章祥蓀，袁亞湘，2、中國系統(tǒng)工程學(xué)會(huì)簡介1、1979年由錢學(xué)森、宋健、關(guān)肇直、許國志等21名專家、學(xué)者共同倡議并籌備。1980年11月18日在北京正式成立。第一屆理事會(huì)理事長關(guān)肇直，第二、三屆理事長許國志。第四、五屆理事長顧基發(fā)、第六屆理事長陳光亞。3、運(yùn)籌學(xué)、系統(tǒng)工程主要研究人員構(gòu)成1）數(shù)學(xué)：如華羅庚、越民義，徐光輝，章祥蓀，袁亞湘，許國志，顧基發(fā)等；2）控制論：張仲俊，劉豹，陳珽，鄭維敏，趙純均，陳劍等3）管理等專業(yè)相關(guān)教學(xué)、科研技術(shù)人員567一、運(yùn)籌學(xué)的起源與發(fā)展4、相關(guān)研究機(jī)構(gòu)和高校1）中國科學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)研究院系統(tǒng)科學(xué)研究所2）中國科學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)研究院應(yīng)用數(shù)學(xué)研究所3）哈工大：胡運(yùn)權(quán)，黃梯云，錢國明等4）天津大學(xué)：劉豹，顧培亮，張維，杜

綱等5）西安交大：汪應(yīng)洛，席酉民等6）上海交大：張仲俊，王浣塵等7）清華大學(xué)：鄭維敏，趙純均，陳劍等；8）大連理工：王眾托，胡祥培等9）北航：顧昌耀，黃海軍等10）北理工：吳滄浦，吳祈宗，張強(qiáng)等9二、運(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è)、政府和國防等方面解決發(fā)生的各種問題，其方法是發(fā)展一個(gè)科學(xué)的系統(tǒng)模式，并運(yùn)用這種模式預(yù)測(cè)，比較各種決策及其產(chǎn)生的后果，以幫助主管人員科學(xué)地決定工作方針和政策——英國運(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)最有效的管理——中國百科全書現(xiàn)代運(yùn)籌學(xué)涵蓋了一切領(lǐng)域的管理與優(yōu)化問題，稱為ManagementScience10二、運(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)最佳的方式來協(xié)調(diào)各部門之間的利害沖突，從而求出問題的最優(yōu)解。所以運(yùn)籌學(xué)可看成是一門優(yōu)化技術(shù)，為解決各類問題提供優(yōu)化方法2定量為所研究的問題提供定量的解決方案。如采用運(yùn)籌學(xué)研究資源分配問題時(shí)，其求解結(jié)果是一個(gè)定量的最優(yōu)資源分配方案。運(yùn)籌學(xué)的研究對(duì)象：來自生產(chǎn)管理過程中的具體問題，如資源分配、物資調(diào)度，生產(chǎn)計(jì)劃與控制等。12四、運(yùn)籌學(xué)解決問題的方法步驟1、理清問題、明確目標(biāo)2、建立模型討論：什么叫模型3、求解模型。建立模型之后，需要設(shè)計(jì)相應(yīng)算法進(jìn)行求解，實(shí)際問題運(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í)差異較大

你喜歡那一種情況？13五、運(yùn)籌學(xué)與其他學(xué)科的關(guān)系

運(yùn)籌學(xué)目標(biāo)分析、建模、求解和結(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é)者來自數(shù)學(xué)專業(yè)就是這個(gè)原因，有人甚至認(rèn)為運(yùn)籌學(xué)是一門應(yīng)用數(shù)學(xué)；2、管理學(xué)：運(yùn)籌學(xué)研究對(duì)象是生產(chǎn)管理過程的具體問題，在利用運(yùn)籌學(xué)理論和方法解決具體問題時(shí)，需要的涉及管理科學(xué)的有關(guān)理論；3、計(jì)算機(jī)：運(yùn)籌學(xué)所研究的實(shí)際問題通常都是比較復(fù)雜，而且規(guī)模比較大，在求解這些問題時(shí)，必須借助計(jì)算機(jī)來完成。14第一章線性規(guī)劃1.1線性規(guī)劃模型1.1.1問題的提出一、例1、多產(chǎn)品生產(chǎn)問題（Max,）甲電纜乙電纜資源量銅（噸）2110鉛（噸）118價(jià)格（萬元）64需求無限制7另

問該工廠應(yīng)如何安排生產(chǎn)才能使工廠的總收入最大？一、例1、多產(chǎn)品生產(chǎn)問題（Max,）設(shè)x1,x2

分別代表甲、乙兩種電纜的生產(chǎn)量，f(x)為工廠的總收入，則上述問題可用如下數(shù)學(xué)模型來表示其中，OBJ（Objective）表示目標(biāo)，S.t.（Subjectto）表示滿足于。表示在滿足銅、鉛資源和需求等約束條件下，使工廠的總收入這一目標(biāo)達(dá)到最大。最優(yōu)解為二、例2、配料問題（min,)某混合飼料加工廠計(jì)劃從市場上購買甲、乙兩種原料生產(chǎn)一種混合飼料?；旌巷暳蠈?duì)VA、VB1、VB2和VD的最低含量有一定的要求。已知單位甲、乙兩種原料VA、VB1、VB2和VD的含量，單位混合飼料對(duì)VA、VB1、VB2和VD的最低含量以及甲、乙兩種原料的單位價(jià)格如下表所示。問該該加工廠應(yīng)如何搭配使用甲乙兩種原料，才能使混合飼料在滿足VA、VB1、VB2和VD的最低含量要求條件下，總成本最??？二、例2、配料問題（MIN,)設(shè)x1,x2分別代表混合單位飼料對(duì)甲、乙兩種原料的用量，f(x)表示單位混合飼料所需要的成本，則上述問題的線性規(guī)劃數(shù)學(xué)模型如下：該數(shù)學(xué)模型的最優(yōu)解為該問題的最優(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ù)其的具體性質(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ì)劃問題的數(shù)學(xué)模型稱為線性規(guī)劃的背景模型。把該背景模型的條件一般化后可敘述如下：用有限量的幾種資源生產(chǎn)若干種產(chǎn)品，如何安排生產(chǎn)，才能使工廠的總收入或利潤達(dá)到最大。2、背景模型的思考1）討論：什么叫背景模型能夠幫助我們理解和記住一些相對(duì)抽象和復(fù)雜問題的簡單問題模型。2）背景模型的思考利用一些相對(duì)比較簡單的問題來闡述一些相對(duì)復(fù)雜和抽象的運(yùn)籌學(xué)中的一些基礎(chǔ)概念和原理是本課程力求在教學(xué)中體現(xiàn)的第一個(gè)特點(diǎn)，希望大家用心體會(huì)。

1.1.2線性規(guī)劃數(shù)學(xué)模型的一般表示方式21

1、和式22

2、向量式23

3、矩陣式24

1.1.3線性規(guī)劃的圖解法f(x)=36線性規(guī)劃問題的幾個(gè)特點(diǎn)：1、線性規(guī)劃的可行域?yàn)橥辜挥懻摚菏裁唇型辜?？集合中任意兩點(diǎn)連線上的一切點(diǎn)仍然在該集合中，在平面上為凸多邊形，在空間上為凸幾何體；討論：最優(yōu)解在那里取得？2、線性規(guī)劃的最優(yōu)解一定可在其凸集的某一頂點(diǎn)上達(dá)到；討論：什么情況有最優(yōu)解？最優(yōu)解的存在性條件？3、線性規(guī)劃若有可行域且其可行域有界，則一定有最優(yōu)解。上述3個(gè)結(jié)論是線性規(guī)劃的3個(gè)基礎(chǔ)定理，可以用嚴(yán)格的數(shù)學(xué)方法進(jìn)行證明。我們以簡單、直觀的圖解法方式給出，相信大家是可以接受的。1.3線性規(guī)劃求解的基礎(chǔ)原理和單純形法1.3.1線性規(guī)劃問題的標(biāo)準(zhǔn)形一、線性規(guī)劃模型一般形式二、求解思路1、規(guī)定一標(biāo)準(zhǔn)型線性的規(guī)劃問題數(shù)學(xué)模型；2、如何把非標(biāo)準(zhǔn)形的線性規(guī)劃問題數(shù)學(xué)模型轉(zhuǎn)化為標(biāo)準(zhǔn)形線性規(guī)劃問題數(shù)學(xué)模型？3、如何求解標(biāo)準(zhǔn)形線性規(guī)劃問題數(shù)學(xué)模型。三、線性規(guī)劃問題的標(biāo)準(zhǔn)形在上述線性規(guī)劃標(biāo)準(zhǔn)形中，決策變量的個(gè)數(shù)取n+m個(gè)是習(xí)慣表示法。我們知道，對(duì)于線性規(guī)劃背景模型，有m個(gè)約束方程，且每個(gè)約束方程的不等式均為“”號(hào)。如果我們?cè)诿總€(gè)約束方程的左邊加上一個(gè)大于等于0的變量，則可將各個(gè)約束方程的“”號(hào)轉(zhuǎn)變?yōu)椤?”。此時(shí)，決策變量就有n+m個(gè)。28

四、變換的方法1、目標(biāo)函數(shù)為min型，價(jià)值系數(shù)一律反號(hào)。令g(x)=-f(x)=-CX,有minf(x)=-max[-f(x)]=-maxg(x)2、第i個(gè)約束的bi

為負(fù)值，則該行左右兩端系數(shù)同時(shí)反號(hào)，同時(shí)不等號(hào)也要反向3、第i個(gè)約束為型，在不等式左邊增加一個(gè)非負(fù)的變量xn+i

，稱為松弛變量；同時(shí)令cn+i

=04、第i個(gè)約束為型，在不等式左邊減去一個(gè)非負(fù)的變量xn+i

，稱為剩余變量；同時(shí)令cn+i

=05、若xj0，令

xj=-xj

，代入非標(biāo)準(zhǔn)型，則有xj

06、若xj不限，令

xj=xj-xj，xj

0，xj0，代入非標(biāo)準(zhǔn)型29

五、

變換舉例：1.3.2線性規(guī)劃問題的解和基礎(chǔ)定理本章開始到現(xiàn)在已討論的內(nèi)容，相信大部分讀者都會(huì)感到比較容易理解和掌握。這一節(jié)我們將要討論關(guān)于線性規(guī)劃問題解的一些基礎(chǔ)概念和定理，與前面討論的內(nèi)容相比，線性規(guī)劃問題解的一些基礎(chǔ)概念略顯難一些，其中比較難的概念有線性規(guī)劃問題的基和基礎(chǔ)解等相關(guān)概念。為了幫助大家比較容易理解這些概念，我們先從大家熟悉的兩個(gè)變量兩個(gè)線性方程組這一簡單問題入手，然后逐步過渡到我們所要討論的線性規(guī)劃問題的基和基礎(chǔ)解等相關(guān)概念。著名數(shù)學(xué)家笛卡爾曾說過，他最擅長做的兩件事是：1)第一做簡單事；2)第二是將復(fù)雜事變?yōu)楹唵问?。本課程將從大家熟悉的一些簡單問題入手，然后逐步過渡到運(yùn)籌學(xué)一些相對(duì)比較抽象和難的概念和原理。這是本課程教學(xué)力求的另一特點(diǎn)。一、線性方程組的解考慮如下線性方程組的解：再考慮如下線性方程組的解：一、線性方程組的解類似地，如果將方程組（3）中的變量x2或x1當(dāng)成常數(shù)，分別移到其方程的右邊后采用消元法進(jìn)行求解，則也可得到如下兩組通解及其特解：一、線性方程組的解仔細(xì)觀察和思考方程組（3）的三組通解（4）、（6）和（8）或三組特解（5）、（7）和（9）是如何得到的，以及能夠得到這些通解或特解的條件是什么？根據(jù)求解線性方程組克萊姆條件可知，能夠得到方程組（3）的通解（4）或特解（5）的條件是方程組（3）中的變量x1和x2的系數(shù)矩陣行列式不等于0，即或變量x1和x2的系數(shù)矩陣B1是非奇異矩陣或變量x1和x2的系數(shù)列向量是線性無關(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ù)約束條件后就變成一標(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=-1<0，不滿足線性規(guī)劃（10）的變量非負(fù)約束條件，因此，該基礎(chǔ)解（5）是線性規(guī)劃（10）的基礎(chǔ)非可行解。變量x1和x3為基變量，變量x2為非基變量，令x2=0，得解（7）為線性規(guī)劃（10）的基礎(chǔ)解。該基礎(chǔ)解中x1和x3均大于0，滿足線性規(guī)劃（10）的變量非負(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,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=0XB

是基礎(chǔ)解必須滿足如下條件：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)解無窮多最優(yōu)解

當(dāng)最優(yōu)解的基變量組成不止一個(gè)時(shí)，線性規(guī)劃有無窮多最優(yōu)解39

三、線性規(guī)劃標(biāo)準(zhǔn)型問題解的關(guān)系約束方程的解空間基礎(chǔ)解可行解非可行解基礎(chǔ)可行解退化解四、線性規(guī)劃解的判定對(duì)于某一線性規(guī)劃的任意一個(gè)解X，我們?nèi)绾闻卸╔是基礎(chǔ)解、或是基礎(chǔ)可行解、或是基礎(chǔ)非可行解、或是非可行解、或是可行解呢？判定步驟：1、寫出給定線性規(guī)劃問題的標(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為非可行解。41五、線性規(guī)劃解的判定舉例六、線性規(guī)劃問題解的一些基本定理42定理1若線性規(guī)劃問題存在可行域，則其可行域是凸集。定理2線性規(guī)劃問題可行域的頂點(diǎn)與其基礎(chǔ)可行解一一對(duì)應(yīng)。定理3若線性規(guī)劃問題存在可行域，則它必有基礎(chǔ)可行解。定理4若線性規(guī)劃問題存在可行域且其可行域有界，則它必有最優(yōu)解。定理5若線性規(guī)劃問題存在最優(yōu)解，則其最優(yōu)解一定可以在其可行域的某個(gè)頂點(diǎn)上取得。43

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ǔ)可行解的方法必須簡單實(shí)用，且具有通用性；2、最優(yōu)檢驗(yàn)。即檢驗(yàn)任一基礎(chǔ)可行解是否是最優(yōu)解。若是，則停止計(jì)算；否則，轉(zhuǎn)3）；3、確定改善方向，求得另一個(gè)更好的基礎(chǔ)可行解；轉(zhuǎn)2，直到求得最優(yōu)解為止。通常把這三個(gè)基礎(chǔ)步驟稱為最優(yōu)化三步曲。事實(shí)上，這三部曲對(duì)求解其它最優(yōu)化問題（如非線性規(guī)劃等）也是適用的。44

單純型法的基礎(chǔ)步驟二、單純性法基本原理45為了使大家比較直觀容易地理解利用單純形法求解線性規(guī)劃問題三個(gè)步驟的基礎(chǔ)原理，我們先以解線性方程組的方法來求解例1線性規(guī)劃。解：（一）標(biāo)準(zhǔn)化（二）選擇初始基礎(chǔ)可行解46從系數(shù)矩陣A中可知，x3、x4和x5的系數(shù)列向量P3，P4和P5是線性獨(dú)立，這些向量可構(gòu)成一個(gè)基B0（初始基）對(duì)應(yīng)于基B0的變量x3、x4和x5為基變量，其它兩個(gè)變量x1和x2為非基變量。即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)47將（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í)，由（4）式可得到換入變量x1的值為x1=Min{10/2，8/1，--}=52、確定換出變量48由于基變量的個(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)T3、求另一個(gè)更好的基礎(chǔ)可行解49將（1)約束方程中對(duì)應(yīng)于基B1的非基變量x3和x2移到方程的右邊后可得令非基變量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ǔ)可行解501、確定換入變量及其值從從目標(biāo)函數(shù)（6）可知，只有非基變量x2的系數(shù)為正，所以，可確定x2為換入變量。由于所以，當(dāng)另一個(gè)非基變量x3仍然為0時(shí)，由（7）式可得到換入變量x1的值為x2=Min{10/0.5，3/0.5，7/1}=62、確定換出變量從（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)T513、求另一個(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,≤)52設(shè)線性規(guī)劃問題為另設(shè)bi0(i=1,2,…,m)。標(biāo)準(zhǔn)化后，若對(duì)xj和aij重新編號(hào)，則約束方程可化為變量x1，x2，…，xm作為初始基變量，其余變量作為初始非基變量，并令xm+1=xm+1=…=xn+m=0，則得初始本可行解四、最優(yōu)檢驗(yàn)53對(duì)于標(biāo)準(zhǔn)化線性規(guī)劃問題(2)，經(jīng)過若干次迭代后，如果對(duì)xj及aij重新編號(hào)，則約束方程可化為其中，b’i和a’ij表示經(jīng)過若干次迭代后，當(dāng)前的右端系數(shù)和技術(shù)系數(shù)，以便區(qū)別于原始的右端系數(shù)bi和技術(shù)系數(shù)aij。將上式代入（2）的目標(biāo)函數(shù)后可得機(jī)會(huì)成本54在一般情況下，目標(biāo)函數(shù)值OBJ計(jì)算公式和機(jī)會(huì)成本計(jì)算公式可寫成四、最優(yōu)檢驗(yàn)其中，I為基變量的下標(biāo)集。最優(yōu)檢驗(yàn)條件為其中，J表示非基變量的下標(biāo)集。對(duì)于基變量的檢驗(yàn)數(shù)為因?yàn)榛兞康募夹g(shù)系數(shù)滿足：aij=1,當(dāng)i=jaij=0,當(dāng)ij五、求另一個(gè)更好的基礎(chǔ)可行解

55若某一基礎(chǔ)可行解經(jīng)過最優(yōu)檢驗(yàn)表明不是最優(yōu)解，則需要設(shè)法求得另一個(gè)更好的基礎(chǔ)可行解。求另一個(gè)更好的基礎(chǔ)可行解的主要步驟如下：1、確定換入變量；2、確定換出變量；3、通過基變換或初等變換求得另一個(gè)更好的基礎(chǔ)可行解。我們已在前面例子中說明了這種初等變換方法的基礎(chǔ)思路。下一小節(jié)我們將用單純形表進(jìn)一步說明這種初等變換方法。56

1.3.4單純形法表及單純形法57

例

試列出下面線性規(guī)劃問題的初始單純型表單純形法步驟581、求初始基礎(chǔ)可行解

將線性規(guī)劃模型標(biāo)準(zhǔn)化，建立初始單純形表，求初始基礎(chǔ)可行解。2、最優(yōu)檢驗(yàn)：對(duì)任一基礎(chǔ)可行解X，若其所有檢驗(yàn)數(shù)j

=cjzj0，jJ則X為最優(yōu)解，即X*=X，計(jì)算最優(yōu)解所對(duì)應(yīng)的最優(yōu)目標(biāo)函數(shù)值f(X*)，算法停止。否則轉(zhuǎn)3。3、求另一個(gè)更好的基礎(chǔ)可行解1）確定入變量xk

若則xk為換入變量；2）確定換出變量xl*

計(jì)算若l為空集，則為無界解，算法停止。否則與右端系數(shù)b’l

同一行的基變量xl*為換出變量。轉(zhuǎn)3）3）初等變換，得到另一個(gè)更好的基礎(chǔ)可行解將入變量xk所在列k，出變量xl*所在行l(wèi)的主元技術(shù)系數(shù)a’lk變換為1，主元a’lk所在列的其余元變換為0。更換基變量（用入變量xk替換出變量xl*）及其價(jià)值系數(shù)，得到另一個(gè)更好的基礎(chǔ)可行解。轉(zhuǎn)2。幾種特殊情況下的投資決策?設(shè)備更新決策設(shè)備更新決策是比較設(shè)備更新與否對(duì)企業(yè)的利弊。通常采用凈現(xiàn)值作為投資決策指標(biāo)。設(shè)備更新決策可采用兩種決策方法，一種是比較新、舊兩種設(shè)備各自為企業(yè)帶來的凈現(xiàn)值的大?。涣硪环N是計(jì)算使用新、舊兩種設(shè)備所帶來的現(xiàn)金流量差量，考察這一現(xiàn)金流量差量的凈現(xiàn)值的正負(fù)，進(jìn)而做出恰當(dāng)?shù)耐顿Y決策。?例（教材97－98頁）

方法1，新舊設(shè)備凈現(xiàn)值比較繼續(xù)使用舊設(shè)備:每年經(jīng)營現(xiàn)金流量為20萬元，凈現(xiàn)值為：NPV＝20萬元×PVIFA（10％，10）＝20萬元×6.145＝122.9萬元?使用新設(shè)備：初始投資額＝120－10－16＝94(萬元)經(jīng)營現(xiàn)金流量現(xiàn)值＝40×PVIFA(10%,10)＝40×6.145＝245.8(萬元)終結(jié)現(xiàn)金流量現(xiàn)值＝20×0.386＝7.72(萬元)凈現(xiàn)值＝－94＋245.8＋7.72＝159.52(萬元)由于使用新設(shè)備的凈現(xiàn)值大于繼續(xù)使用舊設(shè)備的凈現(xiàn)值，故采用新設(shè)備。?方法2：差量比較法初始投資額＝120－10－16＝94(萬元)經(jīng)營現(xiàn)金流量差量＝40－20＝20(萬元)經(jīng)營現(xiàn)金流量差量現(xiàn)值＝20×6.145＝122.9(萬元)終結(jié)現(xiàn)金流量現(xiàn)值＝20×0.386＝7.72(萬元)現(xiàn)金流量差量凈現(xiàn)值＝－94＋122.9＋7.72＝36.62(萬元)?設(shè)備比較決策這一決策比較購置不同設(shè)備的效益高低。一般來講，進(jìn)行這一決策時(shí)應(yīng)比較不同設(shè)備帶來的成本與收益，進(jìn)而比較其各自凈現(xiàn)值的高低。但有時(shí)我們也假設(shè)不同設(shè)備帶來的收益是相同的，因而只比較其成本高低即可。很多情況下，不同設(shè)備的使用期限是不同的，因此我們不能直接比較不同設(shè)備在使用期間的凈現(xiàn)值大小，而需要進(jìn)行必要的調(diào)整。這種調(diào)整有兩種：一種是將不同設(shè)備的凈現(xiàn)值轉(zhuǎn)化為年金。一種是將不同設(shè)備轉(zhuǎn)化為相同的使用年限。?例