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

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

緒論一、運(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ó)稱為OperationalResearch美國(guó)稱為OperationsResearch戰(zhàn)后在經(jīng)濟(jì)、管理和機(jī)關(guān)學(xué)校及科研單位繼續(xù)研究1952年，Morse和Kimball出版《運(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ì)理事長(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ù)人員567一、運(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é)：鄭維敏，趙純均，陳劍等；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è)、政府和國(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)最有效的管理——中國(guó)百科全書現(xiàn)代運(yùn)籌學(xué)涵蓋了一切領(lǐng)域的管理與優(yōu)化問(wèn)題，稱為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)運(yùn)籌學(xué)學(xué)的特特點(diǎn)及及研究究對(duì)象象運(yùn)籌學(xué)學(xué)的特特點(diǎn)：：1)優(yōu)化以整體體最優(yōu)優(yōu)為目目標(biāo)，，從系系統(tǒng)的的觀點(diǎn)點(diǎn)出發(fā)發(fā)，力力圖以以整個(gè)個(gè)系統(tǒng)統(tǒng)最佳佳的方方式來(lái)來(lái)協(xié)調(diào)調(diào)各部部門之之間的的利害害沖突突，從從而求求出問(wèn)問(wèn)題的的最優(yōu)優(yōu)解。。所以以運(yùn)籌籌學(xué)可可看成成是一一門優(yōu)優(yōu)化技技術(shù)，，為解解決各各類問(wèn)問(wèn)題提提供優(yōu)優(yōu)化方方法2定量為所研研究的的問(wèn)題題提供供定量量的解解決方方案。。如采采用運(yùn)運(yùn)籌學(xué)學(xué)研究究資源源分配配問(wèn)題題時(shí)，，其求求解結(jié)結(jié)果是是一個(gè)個(gè)定量量的最最優(yōu)資資源分分配方方案。。運(yùn)籌學(xué)學(xué)的研研究對(duì)對(duì)象：：來(lái)自生生產(chǎn)管管理過(guò)過(guò)程中中的具具體問(wèn)問(wèn)題，，如資資源分分配、、物資資調(diào)度度，生生產(chǎn)計(jì)計(jì)劃與與控制制等。。12四、運(yùn)運(yùn)籌學(xué)學(xué)解決決問(wèn)題題的方方法步步驟1、理清清問(wèn)題題、明明確目目標(biāo)2、建立立模型型討論：：什么么叫模模型3、求解解模型型。建建立模模型之之后，，需要設(shè)設(shè)計(jì)相相應(yīng)算算法進(jìn)進(jìn)行求求解，，實(shí)際際問(wèn)題題運(yùn)算量量一般般都很很大，，通常常需要要用計(jì)計(jì)算機(jī)機(jī)求解。4、結(jié)果果分析析討論：：模型型計(jì)算算結(jié)果果與已已有的的經(jīng)驗(yàn)驗(yàn)或知知識(shí)進(jìn)進(jìn)行比比較1）模型型計(jì)算算結(jié)果果和已已有的的經(jīng)驗(yàn)驗(yàn)或知知識(shí)比比較一一致2）模型型計(jì)算算結(jié)果果和已已有的的經(jīng)驗(yàn)驗(yàn)或知知識(shí)差差異較較大你喜歡歡那一一種情情況？？13五、運(yùn)籌學(xué)學(xué)與其其他學(xué)學(xué)科的的關(guān)系系運(yùn)籌學(xué)學(xué)目標(biāo)分分析、、建模、求解和結(jié)果果分析析需要要用到到很多多相關(guān)關(guān)學(xué)科科的知知識(shí)，，它與與如下下學(xué)科科的知知識(shí)關(guān)關(guān)系比比較密密切。。1、數(shù)學(xué)學(xué)：學(xué)習(xí)、、應(yīng)用用運(yùn)籌籌學(xué)應(yīng)應(yīng)該具具備較較廣的的數(shù)學(xué)學(xué)知識(shí)識(shí)，許許多運(yùn)運(yùn)籌學(xué)學(xué)者來(lái)來(lái)自數(shù)數(shù)學(xué)專專業(yè)就就是這這個(gè)原原因，，有人人甚至至認(rèn)為為運(yùn)籌籌學(xué)是是一門門應(yīng)用用數(shù)學(xué)學(xué)；2、管理理學(xué)：：運(yùn)籌籌學(xué)研研究對(duì)對(duì)象是是生產(chǎn)管管理過(guò)過(guò)程的的具體體問(wèn)題題，在在利用用運(yùn)籌籌學(xué)理理論和和方法法解決決具體體問(wèn)題題時(shí)，，需要要的涉涉及管管理科科學(xué)的的有關(guān)關(guān)理論論；3、計(jì)算算機(jī)：：運(yùn)籌學(xué)學(xué)所研研究的的實(shí)際際問(wèn)題題通常常都是是比較較復(fù)雜雜，而而且規(guī)規(guī)模比比較大大，在在求解解這些些問(wèn)題題時(shí)，，必須須借助助計(jì)算算機(jī)來(lái)來(lái)完成成。14第一章章線線性規(guī)規(guī)劃1.1線性規(guī)規(guī)劃模模型問(wèn)題的的提出出一、例1、、多產(chǎn)產(chǎn)品生生產(chǎn)問(wèn)問(wèn)題（Max,）甲電纜乙電纜資源量銅（噸）2110鉛（噸）118價(jià)格（萬(wàn)元）64需求無(wú)限制7另問(wèn)該工工廠應(yīng)應(yīng)如何何安排排生產(chǎn)產(chǎn)才能能使工工廠的的總收收入最最大？？一、例1、、多產(chǎn)產(chǎn)品生生產(chǎn)問(wèn)問(wèn)題（Max,）設(shè)x1,x2分別代代表甲甲、乙乙兩種種電纜纜的生生產(chǎn)量量，f(x)為工廠廠的總總收入入，則則上述述問(wèn)題題可用用如下下數(shù)學(xué)學(xué)模型型來(lái)表表示其中，，OBJ（Objective）表示示目標(biāo)標(biāo)，S.t.（Subjectto）表示示滿足足于。。表示示在滿滿足銅銅、鉛鉛資源源和需需求等等約束束條件件下，，使工工廠的的總收收入這這一目目標(biāo)達(dá)達(dá)到最最大。最優(yōu)優(yōu)解為為二、例例2、配料料問(wèn)題題（min,)某混合合飼料料加工工廠計(jì)計(jì)劃從從市場(chǎng)場(chǎng)上購(gòu)購(gòu)買甲甲、乙乙兩種種原料料生產(chǎn)產(chǎn)一種種混合合飼料料?；旎旌巷曪暳蠈?duì)對(duì)VA、VB1、VB2和VD的最低含量量有一定的的要求。已已知單位甲甲、乙兩種種原料VA、VB1、VB2和VD的含量，單單位混合飼飼料對(duì)VA、VB1、VB2和VD的最低含量量以及甲、、乙兩種原原料的單位位價(jià)格如下表所示。問(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ī)規(guī)劃數(shù)學(xué)模模型的特征征和定義1、線性規(guī)劃數(shù)數(shù)學(xué)模型的特征：1）有一組決策策變量（x1，x2，…，xn）表示某一一方案。這這一組決策策變量的具具體值就代代表一個(gè)具具體方案；；2）有一個(gè)目標(biāo)標(biāo)函數(shù)，該該目標(biāo)函數(shù)數(shù)根據(jù)其的的具體性質(zhì)質(zhì)取最大值值或最小值值。當(dāng)目標(biāo)標(biāo)為成本型型時(shí)取最小小，而當(dāng)目目標(biāo)為效益益型時(shí)取最最大。3）有一組約束束方程，包包括決策變變量的非負(fù)負(fù)約束；4）目標(biāo)函數(shù)和和約束方程程都是線性性的。2、線性規(guī)劃數(shù)數(shù)學(xué)模型的的定義定義1.1有一個(gè)目標(biāo)標(biāo)函數(shù)和一一組約束方方程，且目目標(biāo)函數(shù)和和約束方程程都是線性性的數(shù)學(xué)模模型稱為線線性規(guī)劃數(shù)數(shù)學(xué)模型。。四、線性性規(guī)劃數(shù)數(shù)學(xué)模型型的背景景模型和和思考1、線性規(guī)劃劃數(shù)學(xué)模模型的背景模模型：例1.1的多產(chǎn)品品生產(chǎn)計(jì)計(jì)劃問(wèn)題題的數(shù)學(xué)學(xué)模型稱稱為線性性規(guī)劃的的背景模模型。把把該背景景模型的的條件一一般化后后可敘述述如下：：用有限限量的幾幾種資源源生產(chǎn)若若干種產(chǎn)產(chǎn)品，如如何安排排生產(chǎn)，，才能使使工廠的的總收入入或利潤(rùn)潤(rùn)達(dá)到最最大。2、背景模模型的思思考1）討論：：什么叫叫背景模模型能夠幫助助我們理理解和記記住一些些相對(duì)抽抽象和復(fù)復(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è)個(gè)特點(diǎn)，，希望大家家用心體會(huì)會(huì)。線性規(guī)劃劃數(shù)學(xué)模模型的一一般表示示方式211、和式222、向量式233、矩陣式24線性規(guī)劃的圖圖解法f(x)=36線性規(guī)劃問(wèn)題題的幾個(gè)特點(diǎn)點(diǎn)：1、線性規(guī)劃的的可行域?yàn)橥雇辜挥懻摚菏裁唇薪型辜考现腥我鈨蓛牲c(diǎn)連線上的的一切點(diǎn)仍然然在該集合中中，在平面上上為凸多邊形形，在空間上上為凸幾何體體；討論：最優(yōu)解解在那里取得得？2、線性規(guī)劃的的最優(yōu)解一定定可在其凸集集的某一頂點(diǎn)點(diǎn)上達(dá)到；討論：什么情情況有最優(yōu)解解？最優(yōu)解的的存在性條件件？3、線性規(guī)劃若若有可行域且且其可行域有有界，則一定定有最優(yōu)解。。上述3個(gè)結(jié)論是線性性規(guī)劃的3個(gè)基礎(chǔ)定理，可以用用嚴(yán)格的數(shù)學(xué)學(xué)方法進(jìn)行證證明。我們以簡(jiǎn)單、、直觀的圖解解法方式給出出，相信大家家是可以接受受的。1.3線性規(guī)劃求解解的基礎(chǔ)原理和單純形形法線性規(guī)劃問(wèn)題題的標(biāo)準(zhǔn)形一、線性規(guī)劃劃模型一般形形式二、求解思路路1、規(guī)定一標(biāo)準(zhǔn)型型線性的規(guī)劃劃問(wèn)題數(shù)學(xué)模模型；2、如何把非標(biāo)準(zhǔn)準(zhǔn)形的線性規(guī)規(guī)劃問(wèn)題數(shù)學(xué)學(xué)模型轉(zhuǎn)化為為標(biāo)準(zhǔn)形線性性規(guī)劃問(wèn)題數(shù)數(shù)學(xué)模型？3、如何求解標(biāo)準(zhǔn)準(zhǔn)形線性規(guī)劃劃問(wèn)題數(shù)學(xué)模模型。三、線性規(guī)劃問(wèn)題題的標(biāo)準(zhǔn)形在上述線性規(guī)規(guī)劃標(biāo)準(zhǔn)形中中，決策變量量的個(gè)數(shù)取n+m個(gè)是習(xí)慣表示示法。我們知知道，對(duì)于線線性規(guī)劃背景景模型，有m個(gè)約束方程，，且每個(gè)約束束方程的不等等式均為“”號(hào)。如果我我們?cè)诿總€(gè)約約束方程的左左邊加上一個(gè)個(gè)大于等于0的變量，則可可將各個(gè)約束束方程的“”號(hào)轉(zhuǎn)變?yōu)椤啊?”。此時(shí)，決決策變量就有有n+m個(gè)。28四、變換的方法1、目標(biāo)函數(shù)為為min型，價(jià)值系數(shù)數(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ù)負(fù)的變量xn+i，稱為松弛變量量；同時(shí)令cn+i=04、第i個(gè)約束束為型型，在在不等等式左左邊減減去一一個(gè)非非負(fù)的的變量量xn+i，稱為為剩剩余余變變量量；；同同時(shí)時(shí)令令cn+i=05、若若xj0，令令xj=-xj，代代入入非非標(biāo)標(biāo)準(zhǔn)準(zhǔn)型型，，則則有有xj06、若若xj不限限，，令令xj=xj-xj，xj0，xj0，代入非標(biāo)標(biāo)準(zhǔn)型29五、變換舉例例：線性規(guī)劃劃問(wèn)題的的解和基礎(chǔ)定理本章開始始到現(xiàn)在在已討論論的內(nèi)容容，相信信大部分分讀者都都會(huì)感到到比較容容易理解解和掌握握。這一一節(jié)我們們將要討討論關(guān)于于線性規(guī)規(guī)劃問(wèn)題題解的一一些基礎(chǔ)概念和定定理，與與前面討討論的內(nèi)內(nèi)容相比比，線性性規(guī)劃問(wèn)問(wèn)題解的的一些基礎(chǔ)概念略顯顯難一些些，其中中比較難難的概念念有線性性規(guī)劃問(wèn)問(wèn)題的基基和基礎(chǔ)礎(chǔ)解等相相關(guān)概念念。為了了幫助大大家比較較容易理理解這些些概念，，我們先先從大家家熟悉的的兩個(gè)變變量?jī)蓚€(gè)個(gè)線性方方程組這這一簡(jiǎn)單單問(wèn)題入入手，然然后逐步步過(guò)渡到到我們所所要討論論的線性性規(guī)劃問(wèn)問(wèn)題的基基和基礎(chǔ)礎(chǔ)解等相相關(guān)概念念。著名數(shù)學(xué)學(xué)家笛卡卡爾曾說(shuō)說(shuō)過(guò)，他他最擅長(zhǎng)長(zhǎng)做的兩兩件事是是：1)第一做簡(jiǎn)簡(jiǎn)單事；；2)第二是將將復(fù)雜事事變?yōu)楹?jiǎn)簡(jiǎn)單事。。本課程將從大家家熟悉的的一些簡(jiǎn)簡(jiǎn)單問(wèn)題題入手，，然后逐逐步過(guò)渡渡到運(yùn)籌籌學(xué)一些些相對(duì)比比較抽象象和難的的概念和和原理。。這是本本課程教學(xué)學(xué)力求的另另一特點(diǎn)點(diǎn)。一、線性性方程組組的解考慮如下下線性方方程組的的解：再考慮如如下線性性方程組組的解：：一、線性性方程組組的解類似地，，如果將將方程組組（3）中的變變量x2或x1當(dāng)成常數(shù)數(shù)，分別別移到其其方程的的右邊后后采用消消元法進(jìn)進(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ù)列列向量是是線性無(wú)無(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ù)負(fù)約束條條件后就就變成一一標(biāo)準(zhǔn)型型線性規(guī)規(guī)劃。如如：一、線性性方程組組的解對(duì)于上述標(biāo)準(zhǔn)準(zhǔn)型線性性規(guī)劃（（10）,稱B1、B2和B3為線性規(guī)規(guī)劃（10）的基。。因利用用其中任任何一個(gè)個(gè)基B1或B2或B3，都能得得到線性性規(guī)劃（（10）的一組組通解和和特解（（見式（（4）--（9））。變量x1和x2為基變量量，變量量x3為非基變變量，令令x3=0，得解（5）為線性性規(guī)劃（（10）的基礎(chǔ)礎(chǔ)解，但但因該基礎(chǔ)解解中x1=-1<0，不滿足足線性規(guī)規(guī)劃（10）的變量量非負(fù)約約束條件件，因此此，該基基礎(chǔ)解（（5）是線性規(guī)規(guī)劃（10）的基礎(chǔ)礎(chǔ)非可行行解。變量x1和x3為基變量量，變量量x2為非基變變量，令令x2=0，得解（7）為線性性規(guī)劃（（10）的基礎(chǔ)礎(chǔ)解。該基礎(chǔ)解解中x1和x3均大于0，滿足線線性規(guī)劃劃（10）的變量量非負(fù)約約束條件件，因此此，該基基礎(chǔ)解（（7）是線性規(guī)規(guī)劃（10）的基礎(chǔ)礎(chǔ)可行解解。變量x2和x3為基變量量，變量量x1為非基基變量量，令令x1=0，得解（9）為線線性規(guī)規(guī)劃（（10）的基基礎(chǔ)解解.該基礎(chǔ)礎(chǔ)解中中x2和x3均大于0，滿足線性性規(guī)劃（10）的變量非非負(fù)約束條條件，因此此，該基礎(chǔ)礎(chǔ)解（9）是線性規(guī)劃劃（10）的的基基礎(chǔ)礎(chǔ)可可行行解解。。二、、標(biāo)準(zhǔn)準(zhǔn)型型線線性性規(guī)規(guī)劃劃解解的的若若干干基基礎(chǔ)礎(chǔ)概概念念標(biāo)準(zhǔn)準(zhǔn)型型有有n+m個(gè)變變量量，，m個(gè)約約束束行行“基”的的概概念念在標(biāo)標(biāo)準(zhǔn)準(zhǔn)型型中中，，技技術(shù)術(shù)系系數(shù)數(shù)矩矩陣陣有有n+m列，，即即A=(P1,P2,……,Pn+m)A中線線性性獨(dú)獨(dú)立立的的m列，，構(gòu)構(gòu)成成該該標(biāo)標(biāo)準(zhǔn)準(zhǔn)型型的的一一個(gè)個(gè)基，即即B=(P1,P2,……,Pm)，|B|0P1,P2,……,Pm稱為為基向向量量與基向向量量對(duì)應(yīng)應(yīng)的的變變量量稱稱為為基變變量量，記記為為XB=(x1,x2,……,xm)T，其其余余的的變變量量稱稱為為非基變量，記為XN=(xm+1,xm+2,……,xm+n)T，故有X=（XB，XN)最多有有個(gè)個(gè)基基二、標(biāo)標(biāo)準(zhǔn)型型線性性規(guī)劃劃解的的若干干基礎(chǔ)礎(chǔ)概念念可行解解與非可行行解滿足約約束條條件和和非負(fù)負(fù)條件件的解解X稱為可行解解，不滿滿足約約束條條件或或非負(fù)負(fù)條件件的解解X稱為非可行行解基礎(chǔ)解解對(duì)應(yīng)某某一基基B且令其其非基變變量XN=0，求得得基變量量XB的值。。稱X=(XB,XN)T為基礎(chǔ)解解。其中，XB=B1b，XN=0XB是基礎(chǔ)解解必須滿滿足如如下條條件：：1）非0分量的的個(gè)數(shù)數(shù)m；2、m個(gè)基變變量所所對(duì)應(yīng)應(yīng)的系系數(shù)矩矩陣為為非奇奇異的的；3、滿足足m個(gè)約束束條件件。二、標(biāo)標(biāo)準(zhǔn)型型線性性規(guī)劃劃解的的若干干基礎(chǔ)礎(chǔ)概念念基礎(chǔ)可可行解解與基礎(chǔ)非非可行行解基礎(chǔ)解解XB的非零零分量量都0時(shí)，稱稱為基礎(chǔ)可可行解解，否則則為基礎(chǔ)非非可行行解。。退化解基礎(chǔ)可行解解的非零分量量個(gè)數(shù)<m時(shí)，稱為退化解可行基對(duì)應(yīng)于基礎(chǔ)礎(chǔ)可行解的的基稱為可行基最優(yōu)解使目標(biāo)函數(shù)數(shù)達(dá)到最優(yōu)優(yōu)的基礎(chǔ)可行解稱為為最優(yōu)解無(wú)窮多最優(yōu)優(yōu)解當(dāng)最優(yōu)解的的基變量組組成不止一一個(gè)時(shí)，線線性規(guī)劃有有無(wú)窮多最優(yōu)優(yōu)解39三、線性規(guī)劃標(biāo)標(biāo)準(zhǔn)型問(wèn)題題解的關(guān)系系約束方程的的解空間基礎(chǔ)解可行解非可行解基礎(chǔ)可行解退化解四、線性規(guī)規(guī)劃解的判判定對(duì)于某一線線性規(guī)劃的的任意一個(gè)個(gè)解X，我們?nèi)绾魏闻卸╔是基礎(chǔ)解、、或是基礎(chǔ)礎(chǔ)可行解、、或是基礎(chǔ)礎(chǔ)非可行解解、或是非非可行解、、或是可行行解呢？判定步驟：1、寫出給定定線性規(guī)劃劃問(wèn)題的標(biāo)標(biāo)準(zhǔn)型線性性規(guī)劃；2、根據(jù)基礎(chǔ)礎(chǔ)解的三個(gè)個(gè)條件判定定X是否是基礎(chǔ)礎(chǔ)解。當(dāng)三三個(gè)條件均均滿足時(shí)，，X才是基礎(chǔ)解解；否則X不是基礎(chǔ)解解。若X是基礎(chǔ)解，，轉(zhuǎn)3；否則，轉(zhuǎn)轉(zhuǎn)4；3、X是否滿足非非負(fù)約束，，即其基變變量值是否否都大于0？若是，X是基礎(chǔ)可行行解；否則則X是基礎(chǔ)非可可行解。4、將X代入給定線線性規(guī)劃的的所有約束束方程，包包括非負(fù)約約束，若X滿足所有約約束方程，，則X為可行解，，否則X為非可行解解。41五、線性規(guī)規(guī)劃解的判判定舉例六、線性規(guī)規(guī)劃問(wèn)題解解的一些基基本定理42定理1若線性規(guī)劃劃問(wèn)題存在在可行域，，則其可行行域是凸集集。定理2線性規(guī)劃問(wèn)問(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)優(yōu)解一定可可以在其可可行域的某某個(gè)頂點(diǎn)上上取得。43單純型法的的基礎(chǔ)原理理一、單純形形法的基礎(chǔ)思路和步驟驟（一）基礎(chǔ)礎(chǔ)思路從一個(gè)基礎(chǔ)可行解出發(fā)發(fā)，設(shè)法得得到另一個(gè)個(gè)更好的基礎(chǔ)可行解，直直到目標(biāo)函函數(shù)達(dá)到最最優(yōu)時(shí)，基礎(chǔ)可行解即為為最優(yōu)解。。（二）基礎(chǔ)礎(chǔ)步驟1、求一個(gè)基礎(chǔ)可行解，稱稱為初始基礎(chǔ)可行解。求求初始基礎(chǔ)可行解的方方法必須簡(jiǎn)簡(jiǎn)單實(shí)用，，且具有通通用性；2、最優(yōu)檢驗(yàn)。。即檢驗(yàn)任任一基礎(chǔ)可行解是否否是最優(yōu)解解。若是，，則停止計(jì)計(jì)算；否則則，轉(zhuǎn)3）；3、確定改善方方向，求得得另一個(gè)更更好的基礎(chǔ)可行解；轉(zhuǎn)轉(zhuǎn)2，直到求得得最優(yōu)解為為止。通常把這三三個(gè)基礎(chǔ)步驟稱為最最優(yōu)化三步步曲。事實(shí)實(shí)上，這三三部曲對(duì)求求解其它最最優(yōu)化問(wèn)題題（如非線線性規(guī)劃等等）也是適適用的。44單純型法的的基礎(chǔ)步驟驟二、單純性性法基本原原理45為了使大家家比較直觀觀容易地理理解利用單單純形法求求解線性規(guī)規(guī)劃問(wèn)題三三個(gè)步驟的的基礎(chǔ)原理，我們先以解線性性方程組組的方法法來(lái)求解解例1線性規(guī)劃劃。解：（一一）標(biāo)準(zhǔn)準(zhǔn)化（二）選選擇初始始基礎(chǔ)可行解46從系數(shù)矩矩陣A中可知，，x3、x4和x5的系數(shù)列列向量P3，P4和P5是線性獨(dú)獨(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ì)對(duì)應(yīng)于X(0)的目標(biāo)函函數(shù)f(X(0))=6x1+4x2=0（三）最最優(yōu)檢驗(yàn)驗(yàn)47將（2）式代入入(1)的目標(biāo)函函數(shù)后可可得f(X)=0+6x1+4x2（3）從目標(biāo)函函數(shù)（3）可知，，非基變變量x1和x2的系數(shù)都都是正數(shù)數(shù)，所以X(0)不是最優(yōu)優(yōu)解。（四）求求另一個(gè)個(gè)更好的的基礎(chǔ)可行解1、確定換換入變量量及其值值從從目標(biāo)標(biāo)函數(shù)（（3）可知，，非基變變量x1的系數(shù)大大于x2的系數(shù)，，所以，，可確定定x1為換入變變量由于所以，當(dāng)另一個(gè)個(gè)非基變變量x2仍然為0時(shí)，由（4）式可得到到換入變變量x1的值為x1=Min{10/2，8/1，--}=52、確定換換出變量量48由于基變變量的個(gè)個(gè)數(shù)只能能等于約約束方程程的個(gè)數(shù)數(shù)m，在本例例中，m=3，所以，，當(dāng)有一一個(gè)非基基變量做做為換入入變量變變?yōu)榛冏兞繒r(shí)，，就必須須有一個(gè)個(gè)基變量量做為換換出變量量變?yōu)榉欠腔兞苛?。即從從所有基基變量中中，將其其中一個(gè)個(gè)大于0的基變量變變?yōu)榈扔?的非基變量量，該非基基變量就是是換出變量量。從（4）式可知，，當(dāng)x1=5時(shí)，x3=0，所以x3為換出變量量。由此得得到線性規(guī)規(guī)劃（1）的一個(gè)新新的基B1和一組新的基基變量與非非基變量。。XB1=（x1，x4，x5)T，XN1=（x3，x2)T3、求另一個(gè)個(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)應(yīng)于X(1)的目標(biāo)函數(shù)數(shù)f(X(1))=6x1+4x2=30>f(X(0))=0（五）最優(yōu)檢驗(yàn)驗(yàn)將（5）式代入(1)的目標(biāo)函數(shù)數(shù)后可得f(X)=30+x2-3x3（6）從目標(biāo)函數(shù)數(shù)（6）可知，非非基變量x2的系數(shù)是正正數(shù)，所以X(1)不是最優(yōu)解解。（六）求另一個(gè)個(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ī)規(guī)劃（1）的一個(gè)新新的基B2和一組新的基基變量與非非基變量。。B2=(P1,P2,P5),XB2=（x1，x2，x5)T，XN2=（x3，x4)T513、求另一個(gè)個(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)標(biāo)函數(shù)數(shù)（9）可知，非基基變量量x3和x4的系數(shù)數(shù)都是是負(fù)數(shù)，所以X(2)是最優(yōu)優(yōu)解。。即X*=X(2)=(2，6，0，0，1)T,f(X*)=36三、求求初始始基礎(chǔ)礎(chǔ)可行行解（（背景景模型型，MAX,≤≤)52設(shè)線性性規(guī)劃劃問(wèn)題題為另設(shè)bi0(i=1,2,…,m)。標(biāo)準(zhǔn)準(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)標(biāo)準(zhǔn)化化線性性規(guī)劃劃問(wèn)題題(2)，經(jīng)過(guò)過(guò)若干干次迭迭代后后，如如果對(duì)對(duì)xj及aij重新編編號(hào)，，則約約束方方程可可化為為其中，，b’i和a’ij表示經(jīng)經(jīng)過(guò)若若干次次迭代代后，，當(dāng)前前的右右端系系數(shù)和和技術(shù)術(shù)系數(shù)數(shù)，以以便區(qū)區(qū)別于于原始始的右右端系系數(shù)bi和技術(shù)術(shù)系數(shù)數(shù)aij。將上式代入入（2）的目標(biāo)函函數(shù)后后可得得機(jī)會(huì)成成本54在一般般情況況下，，目標(biāo)標(biāo)函數(shù)數(shù)值OBJ計(jì)算算公公