運(yùn)籌學(xué)基礎(chǔ)與應(yīng)用

緒論（1）運(yùn)籌學(xué)簡(jiǎn)述（2）運(yùn)籌學(xué)的主要內(nèi)容（3）本課程的主要學(xué)習(xí)內(nèi)容（4）運(yùn)籌學(xué)的應(yīng)用（5）本課程的教材及參考書（6）本課程授課方式與考核本章主要內(nèi)容：第一頁(yè)，共121頁(yè)。一、古代樸素的運(yùn)籌學(xué)思想國(guó)外英文原名OperationsResearch

簡(jiǎn)稱“O.R.”直譯為：運(yùn)用研究或作業(yè)研究正式出現(xiàn)于1938年7月英國(guó)一份關(guān)于防空作戰(zhàn)系統(tǒng)運(yùn)行的研究報(bào)告中中國(guó)古代運(yùn)籌學(xué)案例二、運(yùn)籌學(xué)的起源（一）運(yùn)籌學(xué)簡(jiǎn)述第二頁(yè)，共121頁(yè)。運(yùn)作研究(OperationalResearch)小組”:二戰(zhàn)期間解決復(fù)雜的戰(zhàn)略和戰(zhàn)術(shù)問(wèn)題。例如：如何合理運(yùn)用雷達(dá)有效地對(duì)付德軍空襲對(duì)商船如何進(jìn)行編隊(duì)護(hù)航，使船隊(duì)遭受德國(guó)潛艇攻擊時(shí)損失最少；在各種情況下如何調(diào)整反潛深水炸彈的爆炸深度，才能增加對(duì)德國(guó)潛艇的殺傷力等。二戰(zhàn)后運(yùn)籌學(xué)的發(fā)展經(jīng)歷了三個(gè)階段（1）1945年到20世紀(jì)50年代初——?jiǎng)?chuàng)建時(shí)期

（2）20世紀(jì)50年代初到20世紀(jì)50年代末——成長(zhǎng)時(shí)期

（3）20世紀(jì)60年代以來(lái)——迅速發(fā)展和普及的時(shí)期第三頁(yè)，共121頁(yè)。國(guó)內(nèi)1956年成立第一個(gè)運(yùn)籌學(xué)小組1957年從“夫運(yùn)籌策帷幄之中，決勝于千里之外”中摘取“運(yùn)籌”二字，將O.R.正式翻譯為“運(yùn)籌學(xué)”三、運(yùn)籌學(xué)的定義研究工具：數(shù)學(xué)，計(jì)算機(jī)科學(xué)及其他相關(guān)科學(xué)研究目的：對(duì)有限資源進(jìn)行合理規(guī)劃、使用，并提供優(yōu)化決策方案。研究對(duì)象：復(fù)雜系統(tǒng)的組織和管理參考《大英百科全書》、《辭?！?、《中國(guó)企業(yè)管理百科全書》等。第四頁(yè)，共121頁(yè)。四、運(yùn)籌學(xué)研究的基本特點(diǎn)

系統(tǒng)的整體優(yōu)化多學(xué)科的配合模型方法的應(yīng)用五、運(yùn)籌學(xué)研究的基本步驟

分析與表述問(wèn)題建立數(shù)學(xué)模型對(duì)問(wèn)題求解對(duì)模型和模型導(dǎo)出的解進(jìn)行檢驗(yàn)建立對(duì)解的有效控制方案的實(shí)施第五頁(yè)，共121頁(yè)。（二）運(yùn)籌學(xué)的主要內(nèi)容數(shù)學(xué)規(guī)劃（線性規(guī)劃、整數(shù)規(guī)劃、目標(biāo)規(guī)劃、動(dòng)態(tài)規(guī)劃等）圖論存貯論排隊(duì)論對(duì)策論（博弈論）決策論第六頁(yè)，共121頁(yè)。（三）運(yùn)籌學(xué)的應(yīng)用運(yùn)籌學(xué)方法應(yīng)用例線性規(guī)劃生產(chǎn)結(jié)構(gòu)優(yōu)化非線性規(guī)劃投資組合優(yōu)化整數(shù)規(guī)劃選址問(wèn)題動(dòng)態(tài)規(guī)劃資源分配問(wèn)題網(wǎng)絡(luò)分析工程計(jì)劃優(yōu)化排隊(duì)論服務(wù)系統(tǒng)優(yōu)化

存貯論訂貨庫(kù)存管理決策分析機(jī)會(huì)選擇第七頁(yè)，共121頁(yè)。運(yùn)籌學(xué)的廣泛實(shí)際背景促使其不斷發(fā)展并在經(jīng)濟(jì)管理和系統(tǒng)工程等多領(lǐng)域中發(fā)揮著令人矚目的重要作用。諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)從1969年首發(fā)至今的57位獲獎(jiǎng)?wù)咧芯陀卸辔皇沁\(yùn)籌學(xué)家。1975年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)授給了庫(kù)普曼和康脫羅維奇，以表彰首先將線性規(guī)劃與經(jīng)濟(jì)問(wèn)題相聯(lián)系而做出的貢獻(xiàn)；

1994年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)授給了三位博弈論專家：納什、澤爾騰、海薩尼。博弈論已經(jīng)成為當(dāng)代經(jīng)濟(jì)學(xué)的基石。2005年以色列經(jīng)濟(jì)學(xué)家羅伯特-奧曼和美國(guó)經(jīng)濟(jì)學(xué)家托馬斯-斯切林，因“通過(guò)博弈論分析加強(qiáng)了我們對(duì)沖突和合作的理解”所作出的貢獻(xiàn)而獲獎(jiǎng)。第八頁(yè)，共121頁(yè)。發(fā)表的部分獲獎(jiǎng)項(xiàng)目組織應(yīng)用效果聯(lián)合航空公司在滿足乘客需求的前提下，以最低成本進(jìn)行訂票及機(jī)場(chǎng)工作班次安排每年節(jié)約成本600萬(wàn)美元Citgo石油公司優(yōu)化煉油程序及產(chǎn)品供應(yīng)、配送和營(yíng)銷每年節(jié)約成本7000萬(wàn)AT&T優(yōu)化商業(yè)用戶的電話銷售中心選址每年節(jié)約成本4.06億美元，銷售額大幅增加標(biāo)準(zhǔn)品牌公司控制成本庫(kù)存（制定最優(yōu)再定購(gòu)點(diǎn)和定購(gòu)量確保安全庫(kù)存）每年節(jié)約成本380萬(wàn)美元法國(guó)國(guó)家鐵路公司制定最優(yōu)鐵路時(shí)刻表并調(diào)整鐵路日運(yùn)營(yíng)量每年節(jié)約成本1500萬(wàn)美元，年收入大幅增加。TacoBell優(yōu)化員工安排，以最低成本服務(wù)客戶每年節(jié)約成本1300萬(wàn)美元Delta航空公司優(yōu)化配置上千個(gè)國(guó)內(nèi)航線航班來(lái)實(shí)現(xiàn)利潤(rùn)最大化每年節(jié)約成本1億美元第九頁(yè)，共121頁(yè)。（四）本課程的教材及參考書選用教材《運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用》胡運(yùn)權(quán)主編（第五版）高等教育出版社參考教材《運(yùn)籌學(xué)教程》胡運(yùn)權(quán)主編（第4版）清華出版社《管理運(yùn)籌學(xué)》韓伯棠主編（第2版）高等教育出版社《運(yùn)籌學(xué)》(修訂版)錢頌迪主編清華出版社第十頁(yè)，共121頁(yè)。（五）本課程的主要學(xué)習(xí)內(nèi)容

第一章線性規(guī)劃及單純形法第二章線性規(guī)劃的對(duì)偶理論第三章運(yùn)輸問(wèn)題第四章整數(shù)規(guī)劃與分配問(wèn)題

第十一頁(yè)，共121頁(yè)。（六）本課程授課方式與考核學(xué)科總成績(jī)平時(shí)成績(jī)（30％）課堂考勤（12％）平時(shí)作業(yè)（18％）期末成績(jī)（70％）講授為主，結(jié)合討論、習(xí)題作業(yè)第十二頁(yè)，共121頁(yè)。第一章線性規(guī)劃及單純形法LinearProgrammingandSimplexMethod第十三頁(yè)，共121頁(yè)。

線性規(guī)劃-發(fā)展簡(jiǎn)史

法國(guó)數(shù)學(xué)家J.-B.-J.傅里葉和C.瓦萊－普森分別于1832和1911年獨(dú)立地提出線性規(guī)劃的想法，但未引起注意。1939年蘇聯(lián)數(shù)學(xué)家Л.В.康托羅維奇在《生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法》一書中提出線性規(guī)劃問(wèn)題，也未引起重視。1947年美國(guó)數(shù)學(xué)家G.B.丹齊克提出線性規(guī)劃的一般數(shù)學(xué)模型和求解線性規(guī)劃問(wèn)題的通用方法──單純形法，為這門學(xué)科奠定了基礎(chǔ)。1947年美國(guó)數(shù)學(xué)家J.von諾伊曼提出對(duì)偶理論,開(kāi)創(chuàng)了線性規(guī)劃的許多新的研究領(lǐng)域，擴(kuò)大了它的應(yīng)用范圍和解題能力。1951年美國(guó)經(jīng)濟(jì)學(xué)家T.C.庫(kù)普曼斯把線性規(guī)劃應(yīng)用到經(jīng)濟(jì)領(lǐng)域，為此與康托羅維奇一起獲1975年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。第十四頁(yè)，共121頁(yè)。50年代后對(duì)線性規(guī)劃進(jìn)行大量的理論研究，并涌現(xiàn)出一大批新的算法。例如，1954年C.萊姆基提出對(duì)偶單純形法，1954年S.加斯和T.薩迪等人解決了線性規(guī)劃的靈敏度分析和參數(shù)規(guī)劃問(wèn)題，1956年A.塔克提出互補(bǔ)松弛定理，1960年G.B.丹齊克和P.沃爾夫提出分解算法等。線性規(guī)劃的研究成果還直接推動(dòng)了其他數(shù)學(xué)規(guī)劃問(wèn)題包括整數(shù)規(guī)劃、隨機(jī)規(guī)劃和非線性規(guī)劃的算法研究。由于數(shù)字電子計(jì)算機(jī)的發(fā)展，出現(xiàn)了許多線性規(guī)劃軟件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解幾千個(gè)變量的線性規(guī)劃問(wèn)題。第十五頁(yè)，共121頁(yè)。1979年蘇聯(lián)數(shù)學(xué)家Л.Г.哈奇揚(yáng)提出解線性規(guī)劃問(wèn)題的橢球算法，并證明它是多項(xiàng)式時(shí)間算法。1984年美國(guó)貝爾電話實(shí)驗(yàn)室的印度數(shù)學(xué)家N.卡馬卡提出解線性規(guī)劃問(wèn)題的新的多項(xiàng)式時(shí)間算法-內(nèi)點(diǎn)算法。用這種方法求解線性規(guī)劃問(wèn)題在變量個(gè)數(shù)為5000時(shí)只要單純形法所用時(shí)間的1/50?，F(xiàn)已形成線性規(guī)劃多項(xiàng)式算法理論。50年代后線性規(guī)劃的應(yīng)用范圍不斷擴(kuò)大。第十六頁(yè)，共121頁(yè)。1.1939年，前蘇聯(lián)科學(xué)家康托洛維奇--《生產(chǎn)組織與管理中的數(shù)學(xué)方法》是線性規(guī)劃應(yīng)用于工業(yè)生產(chǎn)問(wèn)題的開(kāi)山之作；

(LEONIDVITALIYEVICHKANTOROV(1912-1986)

第十七頁(yè)，共121頁(yè)。2.1947年，美國(guó)數(shù)學(xué)家喬治·伯納德·丹齊格--單純形法，被稱為線性規(guī)劃之父。

GeorgeBernardDantzig(1914~2005)

第十八頁(yè)，共121頁(yè)。丹齊格在1946年獲伯克利大學(xué)的博士學(xué)位。1947年，33歲提出了解決一種最優(yōu)化問(wèn)題的單純形法,該方法奠定了線性規(guī)劃的基礎(chǔ)，使得經(jīng)濟(jì)學(xué)、環(huán)境科學(xué)、統(tǒng)計(jì)學(xué)應(yīng)用等學(xué)科獲得了迅速發(fā)展。Dantzig也因而被譽(yù)為“線性規(guī)劃之父”。1952年他在蘭德公司任研究數(shù)學(xué)家，在公司電腦上實(shí)行線性規(guī)劃。1960年他被母校聘任教授計(jì)算機(jī)科學(xué)，終于當(dāng)上運(yùn)籌學(xué)中心主任。1966年他在史丹福大學(xué)當(dāng)類似職位，留在那里直到1990年代退休。

Dantzig在運(yùn)籌學(xué)建樹(shù)極高，獲得了包括“馮諾伊曼理論獎(jiǎng)”在內(nèi)的諸多獎(jiǎng)項(xiàng)。他在Linearprogrammingandextensions一書中研究了線性編程模型，為計(jì)算機(jī)語(yǔ)言的發(fā)展做出了不可磨滅的貢獻(xiàn)。他除了線性規(guī)劃和單純形法的杰出工作，還推進(jìn)很多領(lǐng)域的發(fā)展，有分解論、靈敏度分析、互補(bǔ)主元法、大系統(tǒng)最優(yōu)化、非線性規(guī)劃和不確定規(guī)劃。SIAMJournalonOptimization1991年創(chuàng)刊號(hào)是獻(xiàn)給他的。MathematicalProgrammingSociety為表彰丹齊格，設(shè)立丹齊格獎(jiǎng)，1982年起每三年頒給一至兩位在數(shù)學(xué)規(guī)劃有突出貢獻(xiàn)的人。第十九頁(yè)，共121頁(yè)。xa此為無(wú)約束的極值問(wèn)題§1.1一般線性規(guī)劃問(wèn)題的數(shù)學(xué)模型1-1問(wèn)題的提出例1

用一塊邊長(zhǎng)為a的正方形鐵皮做一個(gè)無(wú)蓋長(zhǎng)方體容器，應(yīng)如何裁剪可使做成的容器的容積最大？解：如圖設(shè)四個(gè)角上減去的小正方形邊長(zhǎng)為x，則容器體積為：時(shí)，容積最大第二十頁(yè)，共121頁(yè)。

例2

常山機(jī)器廠生產(chǎn)I、II

兩型產(chǎn)品。這兩型產(chǎn)品都分別要在A、B、C三種不同設(shè)備上加工。按工藝規(guī)定，生產(chǎn)每件產(chǎn)品的單位利潤(rùn)、消耗三種設(shè)備的工時(shí)以及各種設(shè)備工時(shí)的限額如下表：

單位產(chǎn)品消耗設(shè)備工時(shí)III設(shè)備工時(shí)限量（小時(shí)）設(shè)備A設(shè)備B設(shè)備C240205121615單位利潤(rùn)（元）23如何安排生產(chǎn)才能使總的利潤(rùn)最大？第二十一頁(yè)，共121頁(yè)。解：設(shè)計(jì)劃期內(nèi)兩種產(chǎn)品的數(shù)量分別為x1，x2，則總利潤(rùn)為：max z=2x1+3

x2

2x1+2x212 4x1165

x2

15x10，

x20簡(jiǎn)記為：

s.t.（約束于：）z=2x1+3

x2在滿足限制條件下求z的最大值。此為有約束極值問(wèn)題第二十二頁(yè)，共121頁(yè)。1-2線性規(guī)劃問(wèn)題的數(shù)學(xué)模型原型模型數(shù)學(xué)模型提煉數(shù)學(xué)工具1、原型：現(xiàn)實(shí)世界中人們關(guān)心、研究的實(shí)際對(duì)象。

模型：將某一部分信息簡(jiǎn)縮、提煉而構(gòu)造的原型替代物。

數(shù)學(xué)模型：對(duì)現(xiàn)實(shí)世界的一個(gè)特定對(duì)象，為達(dá)到一定目的，根據(jù)內(nèi)在規(guī)律做出必要的簡(jiǎn)化假設(shè),并運(yùn)用適當(dāng)數(shù)學(xué)工具得到的一個(gè)數(shù)學(xué)結(jié)構(gòu)。第二十三頁(yè)，共121頁(yè)。3、規(guī)劃問(wèn)題數(shù)學(xué)模型的三要素（2）目標(biāo)函數(shù)：?jiǎn)栴}要達(dá)到的目標(biāo)要求，表示為決策變量的函數(shù)。用z=f(x1，x2，…，xn)表示。（1）決策變量：決策者為實(shí)現(xiàn)規(guī)劃目標(biāo)采取的方案、措施，是問(wèn)題中要確定的未知量。用x1，x2，…，xn表示。（3）約束條件：決策變量取值時(shí)受到的各種可用資源的限制，表示為含決策變量的等式或不等式。2、規(guī)劃問(wèn)題即求目標(biāo)函數(shù)在若干約束條件下的最值。第二十四頁(yè)，共121頁(yè)。4、線性規(guī)劃問(wèn)題（LinearProgramming）的數(shù)學(xué)模型（2）一般形式：（1）條件：決策變量為可控的連續(xù)變量，目標(biāo)函數(shù)和約束條件都是線性的。簡(jiǎn)記為“L.P.”max(或

min)z=c1x1+c2x2+…+cnxn

s.t.a11x1+a12x2+…+a1nxn

≤（=，≥）b1a21x1+a22x2+…+a2nxn

≤（=，≥）

b2 …am1x1+am2x2+…+amnxn≤（=，≥）

bm

x1

,x2,…,xn≥0第二十五頁(yè)，共121頁(yè)。（3）其他形式：連加形式第二十六頁(yè)，共121頁(yè)。向量形式其中

稱為價(jià)值行向量；決策列向量系數(shù)列向量右端列向量第二十七頁(yè)，共121頁(yè)。矩陣形式其中

稱為價(jià)值行向量；決策列向量右端列向量約束矩陣或系數(shù)矩陣第二十八頁(yè)，共121頁(yè)。1-3線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式1、標(biāo)準(zhǔn)形式或第二十九頁(yè)，共121頁(yè)。2、條件目標(biāo)函數(shù)求極大值約束條件全是等式（線性方程組）決策變量全非負(fù)右端常數(shù)全非負(fù)第三十頁(yè)，共121頁(yè)。3、標(biāo)準(zhǔn)化方法（1）若目標(biāo)函數(shù)求極小值，即則令轉(zhuǎn)化為第三十一頁(yè)，共121頁(yè)。（2）若約束條件為不等式，則依次引入松弛變量或剩余變量（統(tǒng)稱為松弛變量），轉(zhuǎn)化為等式約束條件。注意：松弛變量在目標(biāo)函數(shù)中系數(shù)全為0。約束為≥不等式，減去松弛變量，化為等式約束條件；約束為≤不等式，加上松弛變量，化為等式約束條件。多退少補(bǔ)例：maxz=2x1+3

x2

2x1+2x212 4x1165

x2

15x10，

x20s.t.標(biāo)準(zhǔn)化第三十二頁(yè)，共121頁(yè)。（3）若決策變量xj≤0，則令（4）若決策變量xj取值無(wú)限制，則令（5）若約束等式的右端常數(shù)bi

≤0，則等式兩邊同時(shí)乘以“-1”。其中（“一分為二”）第三十三頁(yè)，共121頁(yè)。例：將下列線性規(guī)劃模型化為標(biāo)準(zhǔn)形式。第三十四頁(yè)，共121頁(yè)。則問(wèn)題化為標(biāo)準(zhǔn)形式：并引入松弛變量x4,x5,第三十五頁(yè)，共121頁(yè)。課堂練習(xí)：將下列線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式第三十六頁(yè)，共121頁(yè)。線性規(guī)劃問(wèn)題的數(shù)學(xué)模型標(biāo)準(zhǔn)形式如下：第三十七頁(yè)，共121頁(yè)。1-4線性規(guī)劃問(wèn)題的解已知線性規(guī)劃的標(biāo)準(zhǔn)形式：或1、求解線性規(guī)劃問(wèn)題：從滿足（2）、（3）的方程組中找出一個(gè)解使目標(biāo)函數(shù)（1）達(dá)到最大值。第三十八頁(yè)，共121頁(yè)。2、可行解：所有可行解的集合?？尚杏颍簼M足約束條件（2）、（3）的解。記做最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大值的可行解。第三十九頁(yè)，共121頁(yè)。（1）基：設(shè)A為線性規(guī)劃問(wèn)題約束條件的mn

系數(shù)矩陣（m<n），且B

為其mm

子矩陣，若|B|≠0（即B可逆），則稱B為該線性規(guī)劃問(wèn)題的一個(gè)基。（3）基變量：每個(gè)基向量所對(duì)應(yīng)的決策變量，即x1，x2,…,xm

記為XB=(x1,x2,…,xm)T（4）非基變量：除去基變量之外的其他決策變量，即xm+1，xm+2,…,xn，

記為XN=(xm+1,xm+2,…,xn)T3、基不妨假設(shè)

A中前m

行m列對(duì)應(yīng)的子矩陣為一個(gè)基，即（2）基向量：基B中每個(gè)列向量，即P1，P2,…,Pm第四十頁(yè)，共121頁(yè)。（5）基解（基本解）：在約束方程組中，令所有非基變量xm+1=xm+2=…=xn=0

后，解出基變量的唯一解，得到的解（6）基可行解（基本可行解）：滿足決策變量非負(fù)要求的基解。（7）可行基：與基可行解對(duì)應(yīng)的基。（8）基最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大值的基可行解。注意：基解最多個(gè)。（9）最優(yōu)基：與基最優(yōu)解對(duì)應(yīng)的基。第四十一頁(yè)，共121頁(yè)。4、線性規(guī)劃問(wèn)題各種解之間的關(guān)系約束方程的解空間基解可行解非可行解基可行解第四十二頁(yè)，共121頁(yè)。例：在下述線性規(guī)劃問(wèn)題中，列出全部基、基解、基可行解，并指出最優(yōu)解。第四十三頁(yè)，共121頁(yè)。解：系數(shù)矩陣為若取基為B=(P1,P2,P3),則基變量為x1,x2,x3,

非基變量為x4,x5令x4=x5=0，代入約束方程組解得x1=4,x2=3,x3=-2從而得到一個(gè)基解X=(4,3,-2,0,0)

T這個(gè)基解不是基可行解！該L.P.共有8個(gè)基解。第四十四頁(yè)，共121頁(yè)。若取基為B=(P3,P4,P5)=I3,則基變量為x3,x4,x5,

非基變量為x1,x2令x1=x2=0，代入約束方程組從而得到一個(gè)基解X=(0,0,12,16,15)

T這個(gè)基解是基可行解！（注意：選擇單位矩陣為基可以較方便的求出一個(gè)基可行解。）同理可得其他基解.第四十五頁(yè)，共121頁(yè)?；鵅基解是基可行解？目標(biāo)函數(shù)值x1x2x3x4x5P1P2P343-200否17P1P2P433040是15P1P2P542005是14P1P3P5404015是8P1P4P5600-815否12P2P3P4036160是9P2P4P506016-15否18P3P4P500121615是0（最優(yōu)基）（最優(yōu)解）（最優(yōu)目標(biāo)函數(shù)值）第四十六頁(yè)，共121頁(yè)?！?.2圖解法1、適用范圍：僅含兩個(gè)決策變量的L.P.2、步驟：（1）作平面直角坐標(biāo)系，標(biāo)上刻度； （2）作出約束方程所在直線，確定可行域； （3）作出一組目標(biāo)函數(shù)的等值線，判定優(yōu)化方向；（4）沿優(yōu)化方向移動(dòng)，確定與可行域相切的點(diǎn)，確定最優(yōu)解，并計(jì)算最優(yōu)目標(biāo)函數(shù)值。第四十七頁(yè)，共121頁(yè)。例：用圖解法求解下列線性規(guī)劃問(wèn)題。（1）maxz=2x1+3x2 s.t.2x1+2x212----------①

4x116----------② 5x215----------③ x10,x20

第四十八頁(yè)，共121頁(yè)。x1x222468460①2x1+2x2=12③5x2

=15②4x1

=16

Z=6Z=0A(3,3)Zmax有唯一最優(yōu)解，當(dāng)x1=x2=3時(shí)，Zmax

=15C(4,0)D(0,3)(0,0)B(4,2)第四十九頁(yè)，共121頁(yè)。頂點(diǎn)基可行解A（3,3）（3,3,0,4,0）B（4,2）（4,2,0,0,5）C（4,0）（4,0,4,0,15）D（0,3）（0,3,6,16,0）O（0,0）（0,0,12,16,15）一一對(duì)應(yīng)第五十頁(yè)，共121頁(yè)。x1x2omaxZ=3x1+3x2

x1≥0,x2≥0s.t.2x1+2x2≤124x1≤165x2≤154x1=16（≤）5x2=15（≤）2x1+2x2=12（≤）紅色線段上的所有點(diǎn)都是最優(yōu)解這種情形為有無(wú)窮多最優(yōu)解，但是最優(yōu)目標(biāo)函數(shù)值maxZ=18是唯一的。D可行域(4,2)(3,3)第五十一頁(yè)，共121頁(yè)。x1x2omaxZ=2x1+3x2

x1≥0,x2≥0s.t.4x1≤164x1=16（≤）無(wú)界解(無(wú)最優(yōu)解)第五十二頁(yè)，共121頁(yè)。x1x2無(wú)可行解(即無(wú)最優(yōu)解)maxZ=2x1+3x2

x1≥0,x2≥0s.t.2x1+2x2≤12x1+2x2≥14x1+2x2=14（≥）2x1+2x2=12（≤)第五十三頁(yè)，共121頁(yè)。3、線性規(guī)劃問(wèn)題解的類型（1）唯一最優(yōu)解：只有一個(gè)解為最優(yōu)解（2）無(wú)窮多最優(yōu)解：有無(wú)窮多個(gè)解為最優(yōu)解 （3）無(wú)界解：目標(biāo)函數(shù)的取值無(wú)界 （4）無(wú)可行解：可行域?yàn)榭占?，即存在互相矛盾的約束條件。4、可行域的特征（1）若L.P.的可行域不是空集，則可行域?yàn)橥辜?（2）若L.P.有最優(yōu)解，則一定可以在可行域的頂點(diǎn)上找到最優(yōu)解。（3）L.P.的頂點(diǎn)與基可行解一一對(duì)應(yīng)。

第五十四頁(yè)，共121頁(yè)?！?.3單純形法（SimplexMethod）原理3-1預(yù)備知識(shí)：凸集與頂點(diǎn)（1）凸集：對(duì)于集合C中任意兩點(diǎn)連線段上的點(diǎn)，若全在C內(nèi)，則稱集合C為凸集?；?qū)θ魏蝀1∈C，

X2∈C，有a

X1+(1-a)X2∈C，則稱C為凸集.

直觀特征：圖形從內(nèi)部向外部凸出。凸集非凸集第五十五頁(yè)，共121頁(yè)。（2）頂點(diǎn)：凸集中不在任意兩點(diǎn)的連線段內(nèi)部的點(diǎn)。X1X4X3X5X2第五十六頁(yè)，共121頁(yè)。3-2幾個(gè)基本結(jié)論（1）若線性規(guī)劃問(wèn)題存在可行解，則可行域?yàn)橥辜?。?）線性規(guī)劃問(wèn)題的可行解X=(x1,x2,···,xn)T

為基可行解的充要條件是X的正分量所對(duì)應(yīng)的系數(shù)列向量線性無(wú)關(guān)。（3）線性規(guī)劃問(wèn)題的基可行解1-1對(duì)應(yīng)可行域的頂點(diǎn)。例如：比較表1-1和圖1-3（4）若線性規(guī)劃問(wèn)題有最優(yōu)解，則一定存在一個(gè)基可行解為最優(yōu)解。注意：若線性規(guī)劃問(wèn)題有最優(yōu)解，不一定所有的最優(yōu)解都是基可行解。第五十七頁(yè)，共121頁(yè)。單純形法的計(jì)算步驟：

初始基可行解使目標(biāo)函數(shù)值增大的新的基可行解是否最優(yōu)解？結(jié)束是否第五十八頁(yè)，共121頁(yè)。3-3確定初始基可行解已知線性規(guī)劃問(wèn)題形如：引入松弛變量xsi(i=1,2,…,m)化為標(biāo)準(zhǔn)形式：注意：約束條件全是≤第五十九頁(yè)，共121頁(yè)。此時(shí)系數(shù)矩陣為：取后m列對(duì)應(yīng)的單位子矩陣為基，得到初始基可行解：X=(0,0,······,0,b1,b2,······,bm)Tn個(gè)0注意：用這個(gè)方法確定初始基可行解，必須保證約束條件全是“≤”。第六十頁(yè)，共121頁(yè)。

取前m列為基，則基可行解為X（0）=(x10,x20,···,xm0,0,···,0)T

，且前m個(gè)分量為正值。P1P2……PmPm+1……Pj……Pn

10……0 a1,m+1·····a1j·····a1n

01……0 a2,m+1·····a2j·····a2n

00……1 am,m+1·····amj·····amn………………………………………………3-4從一個(gè)基可行解轉(zhuǎn)換為另一個(gè)基可行解n-m

個(gè)0且系數(shù)矩陣A為第六十一頁(yè)，共121頁(yè)。因?yàn)閄（0）是基可行解，所以滿足約束方程組：又因?yàn)镻1,P2,…,Pm是一個(gè)基，非基變量xj(j≥m+1)的系數(shù)列向量Pj

可以用這個(gè)基線性表示：①第六十二頁(yè)，共121頁(yè)。將上式乘以一個(gè)正數(shù)θ得到：移項(xiàng)得：上式與①式相加得：從而找到了滿足約束方程組的另一個(gè)解：第j個(gè)分量第六十三頁(yè)，共121頁(yè)。為使成為基可行解，只需要取即可。第j個(gè)分量（j≥m+1）注意：若某個(gè)xi0=0，則允許θ=0第六十四頁(yè)，共121頁(yè)。3-5最優(yōu)性檢驗(yàn)和解的判別將基可行解X（0）和X（1）分別代入目標(biāo)函數(shù)中：為了比較Z（0）和Z（1）的大小，記稱為線性規(guī)劃問(wèn)題的非基變量xj的檢驗(yàn)數(shù)。第六十五頁(yè)，共121頁(yè)。又>0，∴有如下結(jié)論：(1)若對(duì)所有j≥m+1，有j＜

0

，則z（1）＜

z（0）

，即z

（0）為最優(yōu)函數(shù)值，X（0）為唯一最優(yōu)解；(2)若對(duì)所有j≥m+1

，有j

0，且存在某個(gè)非基變量的檢驗(yàn)數(shù)k=0，則將Pk作為新的基向量得出新的基可行解X（1）

，滿足z（1）

=

z（0）

，故z（1）也為最優(yōu)函數(shù)值，從而X（1）也為最優(yōu)解，∴X（0）

、X（1）

連線上所有點(diǎn)均為最優(yōu)解，因此該線性規(guī)劃模型具有無(wú)窮多最優(yōu)解；(3)若存在某個(gè)j

>

0，但對(duì)應(yīng)的第j列系數(shù)全非正，即aij0，則當(dāng)

+時(shí)，有z（1）

+，∴該線性規(guī)劃模型具有無(wú)界解。第六十六頁(yè)，共121頁(yè)?！?.4單純形法的計(jì)算步驟1、前提：標(biāo)準(zhǔn)化的線性規(guī)劃問(wèn)題的系數(shù)矩陣含有單位子矩陣。不妨假設(shè)A中前m列對(duì)應(yīng)的子矩陣是單位矩陣，取其為基B，得到初始基可行解第六十七頁(yè)，共121頁(yè)。m+3行n+4列第1行：價(jià)值行cj第2行：變量行xj最后一行：檢驗(yàn)數(shù)行σj第1列：基價(jià)值列CB第2列：基變量列XB第3列：基解列b最后一列：比值列θ主體：系數(shù)矩陣Am×n2、單純形表的結(jié)構(gòu)第六十八頁(yè)，共121頁(yè)。第六十九頁(yè)，共121頁(yè)。3、初始單純形表：含初始基可行解的單純形表

最優(yōu)單純形表：含最優(yōu)解的單純形表

4、單純形法（SimplexMethod

）：利用單純形表求解線性規(guī)劃問(wèn)題的方法。第七十頁(yè)，共121頁(yè)。5、單純形法的計(jì)算步驟(1)化L.P.問(wèn)題為標(biāo)準(zhǔn)形式,建立初始單純形表；(3)計(jì)算

以alk為主元素(簡(jiǎn)稱主元，用[]表示)，進(jìn)行線性方程組的初等行變換，將主元列Pk化為單位向量得到新的單純形表，轉(zhuǎn)入(2)。（最大正檢驗(yàn)數(shù)決定換入變量）（最小比值θ決定換出變量）第七十一頁(yè)，共121頁(yè)。例1：用單純形法求解下列線性規(guī)劃問(wèn)題.maxz=2x1+3

x2

2x1+2x212 4x1165

x2

15x10，

x20s.t.解：先標(biāo)準(zhǔn)化第七十二頁(yè)，共121頁(yè)。Cj23000CBXBbX1X2X3X4X50X30X40X5121615221004001005001

再列初始單純形表：θ6-323000第七十三頁(yè)，共121頁(yè)。Cj23000CBXBbX1X2X3X4X50X30X40X512161522100640010-0[5]0013

23000以[5]為主元進(jìn)行初等行變換Cj23000CBXBbX1X2X3X4X50X30X43X26163[2]010-2/5340010401001/5-

2000-3/5x1為換入變量下面開(kāi)始單純形法迭代：x5為換出變量x2為換入變量以[2]為主元進(jìn)行初等行變換x3為換出變量主元化為1，主元列的其他元素化為0第七十四頁(yè)，共121頁(yè)。Cj23000CBXBbX1X2X3X4X52X10X43X234310?0-1/500-214/501001/5

00-10-1/5此時(shí)得到唯一最優(yōu)解X*=(3,3)T,Zmax=15。第七十五頁(yè)，共121頁(yè)。例2用單純形法求解下列線性規(guī)劃問(wèn)題解：先標(biāo)準(zhǔn)化第七十六頁(yè)，共121頁(yè)。210054

x3x400x1x2x3x4bxBcB2100cj24153510[6]201第七十七頁(yè)，共121頁(yè)。00

x3x102x1x2x3x4bxBcB2100cj4301[4]1

01/3-1/21/61/3-1/33/412第七十八頁(yè)，共121頁(yè)。00-1/12-7/24

x2x112x1x2x3x4bxBcB2100cj15/43/4011/4-1/810-1/125/24唯一最優(yōu)解第七十九頁(yè)，共121頁(yè)。6、單純形法中存在的問(wèn)題（1）存在兩個(gè)以上的最大正檢驗(yàn)數(shù)。任取一個(gè)最大正檢驗(yàn)數(shù)對(duì)應(yīng)的變量作為換入變量。（2）θ出現(xiàn)兩個(gè)以上相同的最小值。任取一個(gè)最小θ對(duì)應(yīng)的變量作為換出變量。此時(shí)L.P.問(wèn)題出現(xiàn)退化現(xiàn)象。第八十頁(yè)，共121頁(yè)。練習(xí)：第八十一頁(yè)，共121頁(yè)。5-1人工變量法（大M法）§1.5單純形法的進(jìn)一步討論 前面討論了在標(biāo)準(zhǔn)型中系數(shù)矩陣有單位矩陣，很容易確定一組基可行解。在實(shí)際問(wèn)題中有些模型并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變量，構(gòu)成的可行基稱為人工基，用大M法或兩階段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法。第八十二頁(yè)，共121頁(yè)。例1：用單純形法求解下列線性規(guī)劃問(wèn)題。第八十三頁(yè)，共121頁(yè)。解：先標(biāo)準(zhǔn)化為系數(shù)矩陣但是A中沒(méi)有單位矩陣，在A中人為的增加兩列此時(shí)對(duì)應(yīng)的約束方程組為：該問(wèn)題新增加了兩個(gè)變量：x4,x5（稱為人工變量）A有單位子矩陣，選擇這個(gè)單位矩陣作為基（稱為人工基）。第八十四頁(yè)，共121頁(yè)。為使

必須保證在可行解中人工變量x4=x5=0，故令x4，x5在目標(biāo)函數(shù)中的系數(shù)為－M

（其中M表示任意大的正數(shù)），這種添加人工變量求解LP的方法稱為人工變量法,計(jì)算過(guò)程中出現(xiàn)了M，這種方法也稱為大M法。等價(jià)于第八十五頁(yè)，共121頁(yè)。于是，這個(gè)線性規(guī)劃問(wèn)題轉(zhuǎn)化為：以下可用單純形法繼續(xù)求解。第八十六頁(yè)，共121頁(yè)。Cj→x1x2x3x4XBbCB1 1 -1 101 2 001-2 -3 0 -M-M

34x4x5-M-Mcj-zj-2+2M-3+3M-M03/1=34/2=21/2 0 -1 1-1/21/2 1 001/2x4x212cj-zj-1/2+M/2

0-M0

3/2-3M/2-M-3241 0 -2 2-10 1 1-11x1x221cj-zj0 0 -1 1-M1-M-2-3θx50唯一最優(yōu)解故zmin=7注意：此時(shí)人工變量x4=x5=0第八十七頁(yè)，共121頁(yè)。說(shuō)明：

若表中所有j0

，但存在非0的人工變量，則該模型無(wú)可行解。

采用大M法求解線性規(guī)劃模型時(shí)，如果模型中各個(gè)系數(shù)與M的值非常接近或相差很大，若用手工計(jì)算不會(huì)出現(xiàn)問(wèn)題。但是若利用計(jì)算機(jī)求解，則容易引起混淆，使得機(jī)器判斷出錯(cuò)，從而使大M法失效。在這種情況下，可采用下面的兩階段法進(jìn)行計(jì)算。第八十八頁(yè)，共121頁(yè)。5-2兩階段法(將L.P.問(wèn)題分成兩個(gè)階段來(lái)考慮)

第一階段:判斷原L.P.問(wèn)題是否存在可行解。給原L.P.問(wèn)題加入人工變量，并構(gòu)造僅含人工變量的目標(biāo)函數(shù)w（人工變量在w中的系數(shù)一般取為1）并求w的最小值；然后用單純形法求解。若求得wmin=0，則該問(wèn)題有可行解，進(jìn)入第二階段，否則該問(wèn)題無(wú)可行解，結(jié)束。

第二階段：將第一階段得到的最終表去掉人工變量，并將目標(biāo)函數(shù)還原為原L.P.問(wèn)題的目標(biāo)函數(shù)（即修改最終表中的第一行和第一列），以此作為第二階段的初始表，繼續(xù)用單純形法求解。第八十九頁(yè)，共121頁(yè)。例：用兩階段法求解下列線性規(guī)劃問(wèn)題。標(biāo)準(zhǔn)化引入人工變量z′第九十頁(yè)，共121頁(yè)。(1)第一階段，構(gòu)造判斷是否存在可行解的模型：

用單純形法求解這個(gè)問(wèn)題，先標(biāo)準(zhǔn)化為；第九十一頁(yè)，共121頁(yè)。Cj→x1x2x3x4XBbCB1 1 -1 101 2 0010 0 0 -1-1

34x4x5-1-1cj-zj23-103/1=34/2=21/2 0 -1 1-1/21/2 1 001/2x4x212cj-zj1/20-10-3/2-10241 0 -2 2-10 1 1-11x1x221cj-zj0 0 0 -1-100θx50最優(yōu)解本問(wèn)題有可行解，進(jìn)入第二階段第九十二頁(yè)，共121頁(yè)。(2)第二階段先在第一階段的最終單純形表去掉人工變量，再還原原目標(biāo)函數(shù)，即maxz′=-2x1-3x2+0x3，繼續(xù)迭代：

Cj→x1x2x3XBbCB10 -2 0 1 1-2 -3 0 21x1x2-2-3cj-zj00-1唯一最優(yōu)解故zmin=7注意：兩階段法中不再出現(xiàn)大M，但需要解兩個(gè)線性規(guī)劃問(wèn)題，要注意目標(biāo)函數(shù)系數(shù)的變化。第九十三頁(yè)，共121頁(yè)。5-3關(guān)于解的判別例7用單純形法解下列線性規(guī)劃無(wú)窮多解當(dāng)所有的，但某一非基變量檢驗(yàn)數(shù)，存在無(wú)窮多最優(yōu)解的條件是Ps列向量中至少存在一個(gè)元素，且能找出最優(yōu)解.第九十四頁(yè)，共121頁(yè)。例8用單純形法解下列線性規(guī)劃無(wú)界解

若存在某個(gè)j

>

0，但對(duì)應(yīng)的第j列系數(shù)全非正，即aij0，則問(wèn)題的解無(wú)界.第九十五頁(yè)，共121頁(yè)。例9用單純形法解下列線性規(guī)劃無(wú)可行解若表中所有j0

，但存在非0的人工變量，則該模型無(wú)可行解。第九十六頁(yè)，共121頁(yè)。用最終單純形表判斷線性規(guī)劃問(wèn)題解的類型：解的類型最終表的特征無(wú)可行解有非0的人工變量有可行解唯一最優(yōu)解無(wú)非0的人工變量，非基變量的檢驗(yàn)數(shù)全為負(fù)數(shù)無(wú)窮多最優(yōu)解無(wú)非0的人工變量，非基變量的檢驗(yàn)數(shù)全非正，且有某個(gè)非基變量的檢驗(yàn)數(shù)為0無(wú)界解無(wú)非0的人工變量，有某個(gè)非基變量的檢驗(yàn)數(shù)為正數(shù)，但該變量對(duì)應(yīng)的系數(shù)全為非正數(shù)第九十七頁(yè)，共121頁(yè)。已知線性規(guī)劃問(wèn)題形如：5-4單純形法計(jì)算的向量、矩陣描述引入松弛變量xs

記X=(XB,XN,XS)T其中，XS為松弛變量，在初始表中是基變量；

XB為最終表中基變量；

XN表示既不是初始表的基變量又不是最終表的基變量。注意：XS和XB允許有公共變量。（2）A=(B,N,I)B,N,I分別為XB、XN、

XS在初始表中對(duì)應(yīng)的矩陣。則（1）C=(CB,CN,0)CB,CN,0分別為XB、XN、XS在目標(biāo)函數(shù)中的系數(shù)。（3）A′=(I,N′,B-1)I,N′,B-1分別為XB、XN、

XS在最終表中對(duì)應(yīng)的矩陣。第九十八頁(yè)，共121頁(yè)。約束方程組兩端同時(shí)左乘B-1，則可得如下表達(dá)式：初始單純形表最終單純形表第九十九頁(yè)，共121頁(yè)。用單純形表表示如下：XSbB N IXBb′I N′

B-1初始表 XBXNXS

cj-zj0,······,0 N′S′=（-y1,-y2,…,-ym）=-YT

最終表

XB

XN

XS

cj-zj

B

N 0,······,0比較得：b′=B-1bN′=B-1N

或者

Pj′=B-1PjS′=-CBB-1=-YTN′=CN-CBB-1

N=CN-YTN或者j′=Cj-CBB-1

Pj···其中B-1為初始表中基變量在最終表對(duì)應(yīng)的系數(shù)矩陣，

B為最終表中基變量在初始表對(duì)應(yīng)的系數(shù)矩陣。第一百頁(yè)，共121頁(yè)。例：用單純形法求解下列線性規(guī)劃問(wèn)題.maxz=2x1+3

x2

2x1+2x212 4x1165

x2

15x10，

x20s.t.解：先標(biāo)準(zhǔn)化第一百零一頁(yè)，共121頁(yè)。Cj23000CBXBbX1X2X3X4X50X30X40X5121615221004001005001

得到初始單純形表：θ6-323000Cj23000CBXBbX1X2X3X4X52X10X43X234310?0-1/500-214/501001/5

00-10-1/5最終單純形表：X4010X4010可以驗(yàn)證：第一百零二頁(yè)，共121頁(yè)。三要素決策變量約束條件目標(biāo)函數(shù)兩個(gè)三個(gè)以上x(chóng)j≥0xj無(wú)約束xj≤0

bi

≥0bi<0≤=≥maxZminZxs

xa標(biāo)準(zhǔn)化圖解法、單純形法單純形法不處理令xj=

xj′

-xj″

xj′

≥0xj″

≥0令

xj′=-xj不處理約束條件兩端同乘以-1加松弛變量xs加人工變量xa減去xs加入xa不處理令z′=-Z

0-M根據(jù)上表可以列出初始單純形表5-5單純形法小結(jié)個(gè)數(shù)取值限制右端常數(shù)約束方向要求系數(shù)第一百零三頁(yè)，共121頁(yè)。列初始表第一百零四頁(yè)，共121頁(yè)。§1.7應(yīng)用舉例

一般而言，一個(gè)經(jīng)濟(jì)、管理問(wèn)題要滿足以下條件，才能建立線性規(guī)劃模型：⑴.需要求解問(wèn)題的目標(biāo)能用數(shù)值指標(biāo)來(lái)反映，且能用線性函數(shù)來(lái)描述目標(biāo)的要求；⑵.為達(dá)到這個(gè)目標(biāo)存在多種方案；⑶.要求達(dá)到的目標(biāo)是在一定條件下實(shí)現(xiàn)的，這些條件可用線性等式或不等式來(lái)描述。第一百零五頁(yè)，共121頁(yè)。（一）、混合配料問(wèn)題例：某糖果廠用原料A、B、C加工成三種不同牌號(hào)的糖果甲、乙、丙。已知各種牌號(hào)糖果中各種原料的含量，原料成本，各種原料的每月限制用量，三種牌號(hào)糖果的單位加工費(fèi)用及售價(jià)如下表所示。問(wèn)該廠每月生產(chǎn)這三種牌號(hào)糖果各多少千克，能使該廠獲利最大。請(qǐng)建立這個(gè)問(wèn)題的線性規(guī)劃模型。甲乙丙原料成本（元/kg）每月限制用量（kg）ABC≥60﹪≤20﹪≥30﹪≤50﹪

≤60﹪2.001.501.00200025001200加工費(fèi)（元/kg）0.500.400.30售價(jià)（元/kg）3.402.852.25第一百零六頁(yè)，共121頁(yè)。解：用i=1,2,3表示原料A、B、C；用j=1,2,3表示糖果甲、乙、丙；設(shè)xij為生產(chǎn)第j種糖果使用的第i種原料的質(zhì)量，則該問(wèn)題的數(shù)學(xué)模型為：第一百零七頁(yè)，共121頁(yè)。s.t.原料供應(yīng)限制含量要求條件用單純形法求得：即每月生產(chǎn)甲糖果kg，乙糖果kg，不生產(chǎn)丙糖果，可獲得最大利潤(rùn)為5450元。第一百零八頁(yè)，共121頁(yè)。（二）、投資項(xiàng)目組合問(wèn)題例：興安公司有一筆30萬(wàn)元的資金，考慮今后三年內(nèi)用于下列項(xiàng)目的投資：1、三年內(nèi)每年年初均可投資，每年獲利為投資額的20%，其本利可一起用于下一年投資；2、只允許第一年初投入，于第二年末收回，本利合計(jì)為投資額的150%,但此類投資限額不超過(guò)15萬(wàn)元；3、允許于第二年初投入，于第三年末收回，本利合計(jì)為投資額的160%，但限額投資20萬(wàn)元；4、允許于第三年初投入，年末收回，可獲利40%，但限額為10萬(wàn)元.試為該公司確立一個(gè)使第三年末本利和最大的投資組合方案，請(qǐng)建立這個(gè)問(wèn)題的線性規(guī)劃模型。第一百零九頁(yè)，共121頁(yè)。解：用xij表示第i年初投放到第j個(gè)項(xiàng)目的資金數(shù)，

則建立如下線性規(guī)劃模型：1234一√√二√√三√√第i年初投入第j個(gè)項(xiàng)目第一百一十頁(yè)，共121頁(yè)。1234一166666.7133333.3二0200000三100000100000第三年末本利和=580000用單純形法求得：綜上投資組合方案如下：第一百一十一頁(yè)，共121頁(yè)。(三）、人力資源分配問(wèn)題例

某晝夜服務(wù)的公交線路每天各時(shí)間段內(nèi)所需司機(jī)和乘務(wù)人員人數(shù)如下表所示：班次時(shí)間所需人員16:00——10:00602