運(yùn)籌學(xué)線性規(guī)劃和單純形法

緒論（1）運(yùn)籌學(xué)簡述（2）運(yùn)籌學(xué)的主要內(nèi)容（3）本課程的教材及參考書（4）本課程的特點(diǎn)和要求（5）本課程授課方式與考核（6）運(yùn)籌學(xué)在經(jīng)濟(jì)管理中的應(yīng)用本章主要內(nèi)容：第2頁,共121頁，2024年2月25日，星期天緒論什么是運(yùn)籌學(xué)?OperationalResearch運(yùn)用研究、運(yùn)作研究第3頁,共121頁，2024年2月25日，星期天緒論什么是運(yùn)籌學(xué)是一門應(yīng)用學(xué)科，它廣泛應(yīng)用現(xiàn)有的科學(xué)技術(shù)知識和數(shù)學(xué)方法解決實(shí)際中提出的專門問題，為決策者選擇最優(yōu)決策提供量化依據(jù)。第4頁,共121頁，2024年2月25日，星期天運(yùn)籌學(xué)簡述運(yùn)籌學(xué)（OperationsResearch,簡寫OR

） 系統(tǒng)工程的最重要的理論基礎(chǔ)之一，在美國有人把運(yùn)籌學(xué)稱之為管理科學(xué)(ManagementScience)。運(yùn)籌學(xué)所研究的問題，可簡單地歸結(jié)為一句話：“依照給定條件和目標(biāo)，從眾多方案中選擇最佳方案”故有人稱之為最優(yōu)化技術(shù)。第5頁,共121頁，2024年2月25日，星期天緒論運(yùn)籌學(xué)的歷史與發(fā)展“運(yùn)籌學(xué)思想的出現(xiàn)可以追溯到很早—“田忌賽馬”。

齊王要與大臣田忌賽馬，雙方各出上、中、下馬各一匹，對局三次，每次勝負(fù)1000金。田忌在好友、著名的軍事謀略家孫臏的指導(dǎo)下，以以下安排：齊王 上 中 下 田忌 下 上 中 第6頁,共121頁，2024年2月25日，星期天緒論丁謂的皇宮修復(fù)工程北宋年間，丁謂負(fù)責(zé)修復(fù)火毀的開封皇宮。他的施工方案是：先將皇宮前的一條大街挖成一條大溝，將大溝與汴水相通。使用挖出的土就地制磚，令與汴水相連形成的河道承擔(dān)繁重的運(yùn)輸任務(wù)；修復(fù)工程完成后，實(shí)施大溝排水，并將原廢墟物回填，修復(fù)成原來的大街。丁謂將取材、運(yùn)輸及清廢用“一溝三用”巧妙地解決了，體現(xiàn)了系統(tǒng)規(guī)劃的思想。第7頁,共121頁，2024年2月25日，星期天緒論

國際上運(yùn)籌學(xué)的思想可追溯到1914年，當(dāng)時的蘭徹斯特提出了軍事運(yùn)籌學(xué)的作戰(zhàn)模型。1917年，丹麥工程師埃爾朗在研究自動電話系統(tǒng)中通話線路與用戶呼叫的數(shù)量關(guān)系問題時，提出了埃爾朗公式，研究了隨機(jī)服務(wù)系統(tǒng)中的系統(tǒng)排隊(duì)與系統(tǒng)擁擠問題。存儲論的最優(yōu)批量公式是在20世紀(jì)20年代初提出的。第8頁,共121頁，2024年2月25日，星期天運(yùn)籌學(xué)簡述“運(yùn)作研究(OperationalResearch)小組”:解決復(fù)雜的戰(zhàn)略和戰(zhàn)術(shù)問題。例如：如何合理運(yùn)用雷達(dá)有效地對付德軍德空襲對商船如何進(jìn)行編隊(duì)護(hù)航，使船隊(duì)遭受德國潛艇攻擊時損失最少；在各種情況下如何調(diào)整反潛深水炸彈的爆炸深度，才能增加對德國潛艇的殺傷力等。第9頁,共121頁，2024年2月25日，星期天緒論

在生產(chǎn)管理方面的應(yīng)用，最早是1939年前蘇聯(lián)的康特洛為奇提出了生產(chǎn)組織與計(jì)劃中的線性規(guī)劃問題，并給出解乘數(shù)法的求解方法，出版了第一部關(guān)于線性規(guī)劃的著作《生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法》。但當(dāng)時并沒有引起重視，直到1960年康特洛為奇再次出版了《最佳資源利用的經(jīng)濟(jì)計(jì)算》，才受到國內(nèi)外的一致重視，為此康特洛為奇獲得了諾貝爾經(jīng)濟(jì)學(xué)獎。線性規(guī)劃提出后很快受到經(jīng)濟(jì)學(xué)家的重視，如：二次世界大戰(zhàn)中從事運(yùn)輸模型研究的美國經(jīng)濟(jì)學(xué)家?guī)炱章梗═.C.Koopmans），他很快看到了線性規(guī)劃在經(jīng)濟(jì)中應(yīng)用的意義，并呼吁年輕的經(jīng)濟(jì)學(xué)家要關(guān)注線性規(guī)劃。其中阿羅、薩謬爾遜、西蒙、多夫曼和胡爾威茨等都獲得了諾貝爾獎。第10頁,共121頁，2024年2月25日，星期天緒論

20世紀(jì)50年代中期，錢學(xué)森、許國志等教授在國內(nèi)全面介紹和推廣運(yùn)籌學(xué)知識，1956年，中國科學(xué)院成立第一個運(yùn)籌學(xué)研究室，1957年運(yùn)籌學(xué)運(yùn)用到建筑和紡織業(yè)中，1958年提出了圖上作業(yè)法，山東大學(xué)的管梅谷教授提出了“中國郵遞員問題”，1970年，在華羅庚教授的直接指導(dǎo)下，在全國范圍內(nèi)推廣統(tǒng)籌方法和優(yōu)選法。

1978年11月，在成都召開了全國數(shù)學(xué)年會，對運(yùn)籌學(xué)的理論與應(yīng)用研究進(jìn)行了一次檢閱，1980年4月在山東濟(jì)南正式成立了“中國數(shù)學(xué)會運(yùn)籌學(xué)會”，1984年在上海召開了“中國數(shù)學(xué)會運(yùn)籌學(xué)會第二屆代表大會暨學(xué)術(shù)交流會”，并將學(xué)會改名為“中國運(yùn)籌學(xué)會”。第11頁,共121頁，2024年2月25日，星期天緒論成熟的學(xué)科分支向縱深發(fā)展新的研究領(lǐng)域產(chǎn)生與新的技術(shù)結(jié)合與其他學(xué)科的結(jié)合加強(qiáng)傳統(tǒng)優(yōu)化觀念不斷變化運(yùn)籌學(xué)的發(fā)展趨勢第12頁,共121頁，2024年2月25日，星期天運(yùn)籌學(xué)的主要內(nèi)容數(shù)學(xué)規(guī)劃（線性規(guī)劃、整數(shù)規(guī)劃、目標(biāo)規(guī)劃、動態(tài)規(guī)劃等）圖論存儲論排隊(duì)論對策論排序與統(tǒng)籌方法決策分析第13頁,共121頁，2024年2月25日，星期天運(yùn)籌學(xué)的主要內(nèi)容1.線性規(guī)劃（LinearProgram）是一個成熟的分支，它有效的算法——單純形法，主要解決生產(chǎn)計(jì)劃問題，合理下料問題，最優(yōu)投資問題。2.整數(shù)規(guī)劃(IntegrateProgram)：在線性規(guī)劃的基礎(chǔ)上，變量加上整數(shù)約束。3.非線性規(guī)劃(NonlinearProgram)：目標(biāo)函數(shù)和約束條件是非線性函數(shù)，如證券投資組合優(yōu)化:如何合理投資使風(fēng)險(xiǎn)最小。4.動態(tài)規(guī)劃(DynamicProgram)：多階段決策問題。是美國貝爾曼于1951年提出的。第14頁,共121頁，2024年2月25日，星期天運(yùn)籌學(xué)的主要內(nèi)容5、圖與網(wǎng)絡(luò)(GraphTheoryandNetwork)：中國郵遞員問題、哥尼斯堡城問題、最短路、最大流問題。6、存儲論（InventoryTheory)：主要解決生產(chǎn)中的庫存問題，訂貨周期和訂貨量等問題。7、排隊(duì)論(QueueTheory)：主要研究排隊(duì)系統(tǒng)中的系統(tǒng)排隊(duì)和系統(tǒng)擁擠現(xiàn)象，從而評估系統(tǒng)的服務(wù)質(zhì)量。8、對策論(GameTheory)：主要研究具有斗爭性質(zhì)的優(yōu)化問題。9、決策分析(DecisionAnalysis)：主要研究定量化決策。第15頁,共121頁，2024年2月25日，星期天本課程的教材及參考書選用教材《運(yùn)籌學(xué)》（第4版）清華出版社參考教材《運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用》胡運(yùn)權(quán)主編哈工大出版社《管理運(yùn)籌學(xué)》韓伯棠主編（第2版）高等教育出版社《運(yùn)籌學(xué)》熊偉主編機(jī)械工業(yè)出版社第16頁,共121頁，2024年2月25日，星期天

本課程的特點(diǎn)和要求先修課：高等數(shù)學(xué)，基礎(chǔ)概率、線性代數(shù)特點(diǎn)：系統(tǒng)整體優(yōu)化；多學(xué)科的配合；模型方法的應(yīng)用運(yùn)籌學(xué)的研究的主要步驟：真實(shí)系統(tǒng)系統(tǒng)分析問題描述模型建立與修改模型求解與檢驗(yàn)結(jié)果分析與實(shí)施數(shù)據(jù)準(zhǔn)備第17頁,共121頁，2024年2月25日，星期天本課程授課方式與考核學(xué)科總成績平時成績（40％）考勤、作業(yè)課堂表現(xiàn)期末成績（60％）講授為主，結(jié)合習(xí)題作業(yè)缺交作業(yè)、曠課累計(jì)五次無平時成績。第18頁,共121頁，2024年2月25日，星期天運(yùn)籌學(xué)在經(jīng)濟(jì)管理中的應(yīng)用運(yùn)籌學(xué)在經(jīng)濟(jì)管理中的應(yīng)用涉及的方面：生產(chǎn)計(jì)劃運(yùn)輸問題人事管理庫存管理市場營銷財(cái)務(wù)和會計(jì)物流配送另外，還應(yīng)用于設(shè)備維修、更新和可靠性分析，項(xiàng)目的選擇與評價(jià)，工程優(yōu)化設(shè)計(jì)等。第19頁,共121頁，2024年2月25日，星期天“管理運(yùn)籌學(xué)”軟件介紹“管理運(yùn)籌學(xué)”2.0版包括：線性規(guī)劃、運(yùn)輸問題、整數(shù)規(guī)劃（0-1整數(shù)規(guī)劃、純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃）、目標(biāo)規(guī)劃、對策論、最短路徑、最小生成樹、最大流量、最小費(fèi)用最大流、關(guān)鍵路徑、存儲論、排隊(duì)論、決策分析、預(yù)測問題和層次分析法，共15個子模塊。第20頁,共121頁，2024年2月25日，星期天運(yùn)籌帷幄之中決勝千里之外線性規(guī)劃及單純形法LinearProgramming第一章第21頁,共121頁，2024年2月25日，星期天Chapter1線性規(guī)劃

(LinearProgramming)LP的數(shù)學(xué)模型圖解法單純形法單純形法的進(jìn)一步討論－人工變量法

LP模型的應(yīng)用本章主要內(nèi)容：第22頁,共121頁，2024年2月25日，星期天線性規(guī)劃問題的數(shù)學(xué)模型1.規(guī)劃問題生產(chǎn)和經(jīng)營管理中經(jīng)常提出如何合理安排，使人力、物力等各種資源得到充分利用，獲得最大的效益，這就是規(guī)劃問題。線性規(guī)劃通常解決下列兩類問題：（1）當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源（如資金、設(shè)備、原標(biāo)材料、人工、時間等）去完成確定的任務(wù)或目標(biāo)（2）在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟(jì)效益（如產(chǎn)品量最多、利潤最大.）第23頁,共121頁，2024年2月25日，星期天例1：某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)I、II兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及A、B兩種原材料的消耗如下表所示：12千克40原材料B16千克04原材料A8臺時21設(shè)備合計(jì)III該工廠每生產(chǎn)一件I可獲利2元，每生產(chǎn)一件產(chǎn)品II可獲利3元。問應(yīng)如何安排計(jì)劃使該工廠獲利最多？線性規(guī)劃問題的數(shù)學(xué)模型第24頁,共121頁，2024年2月25日，星期天是一個求極大值問題,可用數(shù)學(xué)模型來描述。設(shè)計(jì)劃期內(nèi)產(chǎn)品的產(chǎn)量為：Ix1IIx2則得到利潤z為:z=2x1+3x2約束條件：臺時約束：

x1+2x2

8原材料約束：

4

x1

164x2

12問題為求

x1、

x2的值，使得利潤z最大1.1.1問題的提出第25頁,共121頁，2024年2月25日，星期天例1數(shù)學(xué)模型歸結(jié)為：目標(biāo)函數(shù)Max

z=2x1+3x2約束條件x1+2x2

84x1

16s.t.4x2

12x1,x2

0s.t.Subjectto受…約束1.1.1問題的提出第26頁,共121頁，2024年2月25日，星期天線性規(guī)劃問題的數(shù)學(xué)模型例1.2某廠生產(chǎn)兩種產(chǎn)品，下表給出了單位產(chǎn)品所需資源及單位產(chǎn)品利潤問：應(yīng)如何安排生產(chǎn)計(jì)劃，才能使總利潤最大？解：1.決策變量：設(shè)產(chǎn)品I、II的產(chǎn)量分別為x1、x22.目標(biāo)函數(shù)：設(shè)總利潤為z，則有：

maxz=2x1+x23.約束條件：

5x2≤156x1+2x2≤24x1+x2≤5

x1，x2≥0第27頁,共121頁，2024年2月25日，星期天線性規(guī)劃問題的數(shù)學(xué)模型例1.3已知資料如下表所示，問如何安排生產(chǎn)才能使利潤最大？或如何考慮利潤大，產(chǎn)品好銷。

設(shè)備產(chǎn)品AB

C

D利潤（元）

Ⅰ21402

Ⅱ22043

有效臺時1281612解：1.決策變量：設(shè)產(chǎn)品I、II的產(chǎn)量分別為x1、x22.目標(biāo)函數(shù)：設(shè)總利潤為z，則有：maxz=2x1+x23.約束條件：

x1≥0,x2≥0

2x1+2x2≤12x1+2x2≤84x1≤164x2≤12第28頁,共121頁，2024年2月25日，星期天線性規(guī)劃問題的數(shù)學(xué)模型例1.4

某廠生產(chǎn)三種藥物，這些藥物可以從四種不同的原料中提取。下表給出了單位原料可提取的藥物量解：要求：生產(chǎn)A種藥物至少160單位；B種藥物恰好200單位，C種藥物不超過180單位，且使原料總成本最小。1.決策變量：設(shè)四種原料的使用量分別為：x1、x2、x3

、x42.目標(biāo)函數(shù)：設(shè)總成本為zmin

z=5x1+6x2+7x3+8x43.約束條件：

x1+2x2+x3+x4≥1602x1+4x3+2x4

＝2003x1

＋x2+x3+2x4

≤180

x1、x2

、x3

、x4≥0第29頁,共121頁，2024年2月25日，星期天

例1.5

某航運(yùn)局現(xiàn)有船只種類、數(shù)量以及計(jì)劃期內(nèi)各條航線的貨運(yùn)量、貨運(yùn)成本如下表所示：航線號船隊(duì)類型編隊(duì)形式貨運(yùn)成本（千元／隊(duì)）貨運(yùn)量（千噸）拖輪A型駁船B型駁船1112—362521—4362023224724041—42720船只種類船只數(shù)拖輪30A型駁船34B型駁船52航線號合同貨運(yùn)量12002400問：應(yīng)如何編隊(duì)，才能既完成合同任務(wù)，又使總貨運(yùn)成本為最?。烤€性規(guī)劃問題的數(shù)學(xué)模型第30頁,共121頁，2024年2月25日，星期天

解：設(shè)：xj為第j號類型船隊(duì)的隊(duì)數(shù)（j=1，2，3，4），

z為總貨運(yùn)成本則：

minz=36x1+36x2+72x3+27x4

x1+x2+2x3+x4≤302x1+2x3≤344x2+4x3+4x4≤5225x1+20x2

＝20040x3+20x4＝400xj≥0（j=1,2,3,4）線性規(guī)劃問題的數(shù)學(xué)模型第31頁,共121頁，2024年2月25日，星期天線性規(guī)劃問題的數(shù)學(xué)模型2.線性規(guī)劃的數(shù)學(xué)模型由三個要素構(gòu)成決策變量Decisionvariables目標(biāo)函數(shù)Objectivefunction約束條件Constraints其特征是：（1）問題的目標(biāo)函數(shù)是多個決策變量的線性函數(shù)，通常是求最大值或最小值；（2）問題的約束條件是一組多個決策變量的線性不等式或等式。

怎樣辨別一個模型是線性規(guī)劃模型？

第32頁,共121頁，2024年2月25日，星期天線性規(guī)劃問題的數(shù)學(xué)模型3.建模條件(1)

優(yōu)化條件：問題所要達(dá)到的目標(biāo)能用線型函數(shù)描述，且能夠用極值（max或min）來表示；(2)

限定條件：達(dá)到目標(biāo)受到一定的限制，且這些限制能夠用決策變量的線性等式或線性不等式表示；(3)

選擇條件：有多種可選擇的方案供決策者選擇，以便找出最優(yōu)方案。第33頁,共121頁，2024年2月25日，星期天線性規(guī)劃問題的數(shù)學(xué)模型4.建模步驟(1)

確定決策變量：即需要我們作出決策或選擇的量。一般情況下，題目問什么就設(shè)什么為決策變量；(2)

找出所有限定條件：即決策變量受到的所有的約束；(3)

寫出目標(biāo)函數(shù)：即問題所要達(dá)到的目標(biāo)，并明確是max還是min。第34頁,共121頁，2024年2月25日，星期天線性規(guī)劃問題的數(shù)學(xué)模型目標(biāo)函數(shù)：約束條件：5.線性規(guī)劃數(shù)學(xué)模型的一般形式簡寫為：第35頁,共121頁，2024年2月25日，星期天線性規(guī)劃問題的數(shù)學(xué)模型向量形式：其中：第36頁,共121頁，2024年2月25日，星期天線性規(guī)劃問題的數(shù)學(xué)模型矩陣形式：其中：第37頁,共121頁，2024年2月25日，星期天線性規(guī)劃問題的數(shù)學(xué)模型6.線性規(guī)劃問題的標(biāo)準(zhǔn)形式特點(diǎn)：(1)目標(biāo)函數(shù)求最大值（有時求最小值）(2)約束條件都為等式方程，且右端常數(shù)項(xiàng)bi都大于或等于零(3)決策變量xj為非負(fù)。第38頁,共121頁，2024年2月25日，星期天線性規(guī)劃問題的數(shù)學(xué)模型（2）如何化標(biāo)準(zhǔn)形式

目標(biāo)函數(shù)的轉(zhuǎn)換

如果是求極小值即，則可將目標(biāo)函數(shù)乘以(-1)，可化為求極大值問題。也就是：令，可得到上式。即

若存在取值無約束的變量，可令其中：

變量的變換第39頁,共121頁，2024年2月25日，星期天線性規(guī)劃問題的數(shù)學(xué)模型

約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。稱為松弛變量稱為剩余變量

常量bi＜0

的變換:約束方程兩邊乘以（－1）第40頁,共121頁，2024年2月25日，星期天線性規(guī)劃問題的數(shù)學(xué)模型例1.6

將下列線性規(guī)劃問題化為標(biāo)準(zhǔn)形式用替換，且解:（１）因?yàn)閤3無符號要求，即x3取正值也可取負(fù)值，標(biāo)準(zhǔn)型中要求變量非負(fù)，所以第41頁,共121頁，2024年2月25日，星期天線性規(guī)劃問題的數(shù)學(xué)模型(2)第一個約束條件是“≤”號，在“≤”左端加入松馳變量x4，x4≥0,化為等式；(3)第二個約束條件是“≥”號，在“≥”左端減去剩余變量x5，x5≥0；(4)第3個約束方程右端常數(shù)項(xiàng)為-5，方程兩邊同乘以(-1),將右端常數(shù)項(xiàng)化為正數(shù)；(5)目標(biāo)函數(shù)是最小值，為了化為求最大值，令z′=-z,得到maxz′=-z，即當(dāng)z達(dá)到最小值時z′達(dá)到最大值，反之亦然;第42頁,共121頁，2024年2月25日，星期天線性規(guī)劃問題的數(shù)學(xué)模型標(biāo)準(zhǔn)形式如下：第43頁,共121頁，2024年2月25日，星期天

例1.7將下列線性規(guī)劃問題化為標(biāo)準(zhǔn)形式為無約束（無非負(fù)限制）線性規(guī)劃問題的數(shù)學(xué)模型第44頁,共121頁，2024年2月25日，星期天

解:用替換，且，將第3個約束方程兩邊乘以（－1）將極小值問題反號，變?yōu)榍髽O大值標(biāo)準(zhǔn)形式如下：引入變量線性規(guī)劃問題的數(shù)學(xué)模型第45頁,共121頁，2024年2月25日，星期天

例1.8將線性規(guī)劃問題化為標(biāo)準(zhǔn)型解：線性規(guī)劃問題的數(shù)學(xué)模型第46頁,共121頁，2024年2月25日，星期天

例1.9將線性規(guī)劃問題化為標(biāo)準(zhǔn)型解：Minf=-3x1

+5x2+8x3

-7x4s.t.2x1

-3x2+5x3+6x4

≤284x1

+2x2+3x3-9x4

≥396x2+2x3+3x4≤-58

x1,x3,x4

≥0；x2無約束

Maxz=3x1–5x2’+5x2”–8x3+7x4s.t.2x1–3x2’+3x2”+5x3+6x4+x5=284x1+2x2’-2x2”+3x3-9x4-x6=39-6x2’+6x2”-2x3-3x4-x7

=58

x1,x2’,x2”,x3,x4,x5,x6,x7

≥0

線性規(guī)劃問題的數(shù)學(xué)模型第47頁,共121頁，2024年2月25日，星期天線性規(guī)劃問題的數(shù)學(xué)模型7.線性規(guī)劃問題的解線性規(guī)劃問題求解線性規(guī)劃問題，就是從滿足約束條件(2)、(3)的方程組中找出一個解，使目標(biāo)函數(shù)(1)達(dá)到最大值。第48頁,共121頁，2024年2月25日，星期天線性規(guī)劃問題的數(shù)學(xué)模型

可行解：滿足約束條件②、③的解為可行解。所有可行解的集合為可行域。

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

基：設(shè)A為約束條件②的m×n階系數(shù)矩陣(m<n)，其秩為m，B是矩陣A中m階滿秩子矩陣（∣B∣≠0），稱B是規(guī)劃問題的一個基。設(shè)：稱B中每個列向量Pj(j=12…

…m)

為基向量。與基向量Pj

對應(yīng)的變量xj

為基變量。除基變量以外的變量為非基變量。第49頁,共121頁，2024年2月25日，星期天線性規(guī)劃問題的數(shù)學(xué)模型

基解：某一確定的基B，令非基變量等于零，由約束條件方程②解出基變量，稱這組解為基解。在基解中變量取非0值的個數(shù)不大于方程數(shù)m，基解的總數(shù)不超過

基可行解：滿足變量非負(fù)約束條件的基本解，簡稱基可行解?？尚谢簩?yīng)于基可行解的基稱為可行基。非可行解可行解基解基可行解第50頁,共121頁，2024年2月25日，星期天線性規(guī)劃問題的數(shù)學(xué)模型例1.10

求線性規(guī)劃問題的所有基矩陣。解:約束方程的系數(shù)矩陣為2×5矩陣r(A)=2，2階子矩陣有10個，其中基矩陣只有9個，即第51頁,共121頁，2024年2月25日，星期天圖解法線性規(guī)劃問題的求解方法一般有兩種方法圖解法單純形法兩個變量、直角坐標(biāo)三個變量、立體坐標(biāo)適用于任意變量、但必需將一般形式變成標(biāo)準(zhǔn)形式下面我們分析一下簡單的情況——

只有兩個決策變量的線性規(guī)劃問題，這時可以通過圖解的方法來求解。圖解法具有簡單、直觀、便于初學(xué)者窺探線性規(guī)劃基本原理和幾何意義等優(yōu)點(diǎn)。第52頁,共121頁，2024年2月25日，星期天

解題步驟4將最優(yōu)解代入目標(biāo)函數(shù)，求出最優(yōu)值。1在直角平面坐標(biāo)系中畫出所有的約束等式，并找出所有約束條件的公共部分，稱為可行域，可行域中的點(diǎn)稱為可行解。2標(biāo)出目標(biāo)函數(shù)值增加或者減小的方向。3若求最大（?。┲?，則令目標(biāo)函數(shù)等值線沿（逆）目標(biāo)函數(shù)值增加的方向平行移動，找與可行域最后相交的點(diǎn)，該點(diǎn)就是最優(yōu)解。圖解法第53頁,共121頁，2024年2月25日，星期天圖解法maxZ=2X1+X2

X1+1.9X2≥3.8X1-1.9X2≤3.8s.t.X1+1.9X2≤10.2X1-1.9X2≥-3.8X1，X2≥0例1.11用圖解法求解線性規(guī)劃問題第54頁,共121頁，2024年2月25日，星期天圖解法x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)4=2X1+X2

20=2X1+X2

17.2=2X1+X2

11=2X1+X2

Lo：0=2X1+X2

（7.6，2）DmaxZminZ此點(diǎn)是唯一最優(yōu)解，且最優(yōu)目標(biāo)函數(shù)值

maxZ=17.2可行域maxZ=2X1+X2第55頁,共121頁，2024年2月25日，星期天圖解法maxZ=3X1+5.7X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)（7.6，2）DL0：0=3X1+5.7X2

maxZ（3.8，4）34.2=3X1+5.7X2

藍(lán)色線段上的所有點(diǎn)都是最優(yōu)解這種情形為有無窮多最優(yōu)解，但是最優(yōu)目標(biāo)函數(shù)值maxZ=34.2是唯一的?？尚杏虻?6頁,共121頁，2024年2月25日，星期天圖解法minZ=5X1+4X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1+1.9X2=10.2(≤)DL0：0=5X1+4X2

maxZminZ8=5X1+4X2

43=5X1+4X2

（0，2）可行域此點(diǎn)是唯一最優(yōu)解第57頁,共121頁，2024年2月25日，星期天圖解法246x1x2246無界解(無最優(yōu)解)maxZ=x1+2x2例1.6x1+x2=4(≥)x1+3x2=6(≥)3x1+x2=6(≥)maxZminZ第58頁,共121頁，2024年2月25日，星期天x1x2O10203040102030405050無可行解(即無最優(yōu)解)maxZ=3x1+4x2例1.7第59頁,共121頁，2024年2月25日，星期天

由圖解法得到的幾種情況

根據(jù)以上例題，進(jìn)一步分析討論可知線性規(guī)劃的可行域和最優(yōu)解有以下幾種可能的情況：

1.可行域?yàn)榉忾]的有界區(qū)域

(a)有唯一的最優(yōu)解；(b)有無窮多個最優(yōu)解；

2.可行域?yàn)榉忾]的無界區(qū)域

(c)有唯一的最優(yōu)解；(d)有無窮多個最優(yōu)解；

(e)目標(biāo)函數(shù)無界(即雖有可行解，但在可行域中，目標(biāo)函數(shù)可以無限增大或無限減少)，因而沒有有限最優(yōu)解。

3.可行域?yàn)榭占?/p>

(f)沒有可行解，原問題無最優(yōu)解圖解法第60頁,共121頁，2024年2月25日，星期天

由圖解法得到的啟示(1)線性規(guī)劃問題解的情況：唯一最優(yōu)解；無窮多最優(yōu)解；無界解；無可行解(3)最優(yōu)解一定是在凸集的某個頂點(diǎn)(2)線性規(guī)劃問題的可行域是凸集（凸多邊形）(4)解題思路是，先找出凸集的任一頂點(diǎn)，計(jì)算其目標(biāo)函數(shù)值，再與周圍頂點(diǎn)的目標(biāo)函數(shù)值比較，如不是最大，繼續(xù)比較，直到找出最大為止。圖解法第61頁,共121頁，2024年2月25日，星期天圖解法

學(xué)習(xí)要點(diǎn)：

1.通過圖解法了解線性規(guī)劃有幾種解的形式（唯一最優(yōu)解；無窮多最優(yōu)解；無界解；無可行解）

2.作圖的關(guān)鍵有三點(diǎn)：

(1)可行解區(qū)域要畫正確

(2)目標(biāo)函數(shù)增加的方向不能畫錯

(3)目標(biāo)函數(shù)的直線怎樣平行移動第62頁,共121頁，2024年2月25日，星期天

連接幾何形體中任意兩點(diǎn)的線段仍完全在該幾何形體之中。有限個凸集的交集仍然是凸集。單純形法基本原理第63頁,共121頁，2024年2月25日，星期天單純形法基本原理凸集：如果集合C中任意兩個點(diǎn)X1、X2，其連線上的所有點(diǎn)也都是集合C中的點(diǎn)，稱C為凸集。凸集凸集不是凸集頂點(diǎn)

頂點(diǎn)：如果凸集C中不存在任何兩個不同的點(diǎn)X1，X2，使X成為這兩個點(diǎn)連線上的一個點(diǎn)第64頁,共121頁，2024年2月25日，星期天單純形法基本原理定理1：若線性規(guī)劃問題存在可行解，則該問題的可行域是凸集。定理2：線性規(guī)劃問題的基可行解X對應(yīng)可行域(凸集)的頂點(diǎn)。定理3：若問題存在最優(yōu)解，一定存在一個基可行解是最優(yōu)解。（或在某個頂點(diǎn)取得）第65頁,共121頁，2024年2月25日，星期天單純形法的計(jì)算步驟單純形法的思路找出一個初始可行解是否最優(yōu)轉(zhuǎn)移到另一個基本可行解（找出更大的目標(biāo)函數(shù)值）最優(yōu)解是否循環(huán)核心是：變量迭代結(jié)束第66頁,共121頁，2024年2月25日，星期天單純形法的計(jì)算步驟單純形表第67頁,共121頁，2024年2月25日，星期天單純形法的計(jì)算步驟例1.12用單純形法求下列線性規(guī)劃的最優(yōu)解解：1）將問題化為標(biāo)準(zhǔn)型，加入松馳變量x3、x4則標(biāo)準(zhǔn)型為:第68頁,共121頁，2024年2月25日，星期天單純形法的計(jì)算步驟2）求出線性規(guī)劃的初始基可行解，列出初始單純形表。cj3400θicB基bx1x2x3x40x34021100x43013013400檢驗(yàn)數(shù)第69頁,共121頁，2024年2月25日，星期天單純形法的計(jì)算步驟3）進(jìn)行最優(yōu)性檢驗(yàn)如果表中所有檢驗(yàn)數(shù)，則表中的基可行解就是問題的最優(yōu)解，計(jì)算停止。否則繼續(xù)下一步。4）從一個基可行解轉(zhuǎn)換到另一個目標(biāo)值更大的基可行解，列出新的單純形表確定換入基的變量。選擇，對應(yīng)的變量xj作為換入變量，當(dāng)有一個以上檢驗(yàn)數(shù)大于0時，一般選擇最大的一個檢驗(yàn)數(shù)，即：，其對應(yīng)的xk作為換入變量。確定換出變量。根據(jù)下式計(jì)算并選擇θ

，選最小的θ對應(yīng)基變量作為換出變量。 第70頁,共121頁，2024年2月25日，星期天單純形法的計(jì)算步驟用換入變量xk替換基變量中的換出變量，得到一個新的基。對應(yīng)新的基可以找出一個新的基可行解，并相應(yīng)地可以畫出一個新的單純形表。5）重復(fù)3）、4）步直到計(jì)算結(jié)束為止。 第71頁,共121頁，2024年2月25日，星期天單純形法的計(jì)算步驟cj3400θicB基變量bx1x2x3x40x34021100x430130134000x34x23x14x2換入列bi/ai2，ai2>04010換出行將3化為15/311801/301/3101－1/3303005/30－4/3乘以1/3后得到103/5－1/51801－1/5－2/5400－1－1第72頁,共121頁，2024年2月25日，星期天單純形法的計(jì)算步驟例1.13

用單純形法求解解：將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式：不難看出x4、x5可作為初始基變量，列單純形表計(jì)算。第73頁,共121頁，2024年2月25日，星期天單純形法的計(jì)算步驟cj12100θicB基變量bx1x2x3x4x50x4152-32100x5201/31501121000x42x220－x221/3150120753017131/30－90－22560x111017/31/31250128/9-1/92/335/300-98/9-1/9-7/3第74頁,共121頁，2024年2月25日，星期天變成標(biāo)準(zhǔn)型單純形法的計(jì)算步驟例1.14用單純形法求解第75頁,共121頁，2024年2月25日，星期天約束方程的系數(shù)矩陣為基變量為非基變量I為單位矩陣且線性獨(dú)立單純形法的計(jì)算步驟第76頁,共121頁，2024年2月25日，星期天單純形法的計(jì)算步驟－cjcBxBb0000x3x4x5x61281612

2x2

第77頁,共121頁，2024年2月25日，星期天第78頁,共121頁，2024年2月25日，星期天第79頁,共121頁，2024年2月25日，星期天第80頁,共121頁，2024年2月25日，星期天單純形法的計(jì)算步驟

學(xué)習(xí)要點(diǎn)：

1.線性規(guī)劃解的概念以及3個基本定理

2.熟練掌握線性規(guī)劃問題的標(biāo)準(zhǔn)化

3.熟練掌握單純形法的解題思路及求解步驟第81頁,共121頁，2024年2月25日，星期天單純形法的進(jìn)一步討論－人工變量法人工變量法： 前面討論了在標(biāo)準(zhǔn)型中系數(shù)矩陣有單位矩陣，很容易確定一組基可行解。在實(shí)際問題中有些模型并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變量，構(gòu)成的可行基稱為人工基，用大M法或兩階段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法。第82頁,共121頁，2024年2月25日，星期天單純形法的進(jìn)一步討論－人工變量法例1.10用大M法解下列線性規(guī)劃解：首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式系數(shù)矩陣中不存在單位矩陣，無法建立初始單純形表。第83頁,共121頁，2024年2月25日，星期天單純形法的進(jìn)一步討論－人工變量法故人為添加兩個單位向量，得到人工變量單純形法數(shù)學(xué)模型：其中：M是一個很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個確定數(shù)值；再用前面介紹的單純形法求解該模型，計(jì)算結(jié)果見下表。第84頁,共121頁，2024年2月25日，星期天單純形法的進(jìn)一步討論－人工變量法cj32-100-M-MCBXBbx1x2x3x4x5x6x7θi-Mx64-431-101040x5101-1201005-Mx712-21000113-2M2+M-1+2M↑-M-Mx63-650-1013/50x58-3300108/3-1x312-21000——5-6M5M↑0-M002x23/5－6/510－1/50——0x531/53/5003/5131/3-1x311/5－2/501－2/50——5↑00002x213010123x131/310015/3-1x319/300102/3000-5-25/3→→→第85頁,共121頁，2024年2月25日，星期天單純形法的進(jìn)一步討論－人工變量法例1.11用大M法解下列線性規(guī)劃解：首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式系數(shù)矩陣中不存在單位矩陣，無法建立初始單純形表。第86頁,共121頁，2024年2月25日，星期天單純形法的進(jìn)一步討論－人工變量法故人為添加兩個單位向量，得到人工變量單純形法數(shù)學(xué)模型：其中：M是一個很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個確定數(shù)值；再用前面介紹的單純形法求解該模型，計(jì)算結(jié)果見下表。第87頁,共121頁，2024年2月25日，星期天單純形法的進(jìn)一步討論－人工變量法Cj3-1-100-M-MCBXBbx1x2x3x4x5x6x70x4111-21100011-Mx63-4120-1103/2-Mx71-20100011Z-4M3-6M-1+M-1+3M0-M000x4103-20100-1－-Mx610100-11-21-1x31-2010001－Z-M-11-1+M00-M0-3M+1→→第88頁,共121頁，2024年2月25日，星期天單純形法的進(jìn)一步討論－人工變量法Cj3-1-100-M-MCBXBbx1x2x3x4x5x6x70x4123001-22-54-1x210100-11-2－-1x31-2010001－Z-21000-1-M+1-M-13x141001/3-2/32/3-5/3-1x210100-11-2-1x390012/3-4/34/3-7/3Z2000-1/3-1/3-M+1/3-M+2/3→第89頁,共121頁，2024年2月25日，星期天單純形法的進(jìn)一步討論－兩階段法

用計(jì)算機(jī)處理數(shù)據(jù)時，只能用很大的數(shù)代替M,可能造成計(jì)算機(jī)上的錯誤，故多采用兩階段法。

第一階段：在原線性規(guī)劃問題中加入人工變量，構(gòu)造如下模型：

對上述模型求解（單純形法），若ω=0,說明問題存在基可行解，可以進(jìn)行第二個階段；否則，原問題無可行解，停止運(yùn)算。第90頁,共121頁，2024年2月25日，星期天單純形法的進(jìn)一步討論－兩階段法第一階段的線性規(guī)劃問題可寫為：第一階段單純形法迭代的過程見下表（注意：沒有化為極大化問題）第91頁,共121頁，2024年2月25日，星期天單純形法的進(jìn)一步討論－兩階段法Cj3-1-100-M-MCBXBbx1x2x3x4x5x6x70x4111-211000111x63-4120-1103/21x71-20100011ω46-1-301000x4103-20100-1－1x610100-11-210x31-2010001－ω10-1001030x4123001-22-50x210100-11-20x31-2010000ω00000011→→第92頁,共121頁，2024年2月25日，星期天單純形法的進(jìn)一步討論－兩階段法

第二階段：在第一階段的最終表中，去掉人工變量，將目標(biāo)函數(shù)的系數(shù)換成原問題的目標(biāo)函數(shù)系數(shù)，作為第二階段計(jì)算的初始表（用單純形法計(jì)算）。例：第93頁,共121頁，2024年2月25日，星期天單純形法的進(jìn)一步討論－兩階段法cj3-1-100cBxBbx1x2x3x4x50x4123001-24-1x210100-1－-1x31-20100－Z-21000-13x141001/3-2/3-1x210100-1-1x390012/3-4/3Z2000-1/3-1/3→第二階段：∴最優(yōu)解為（41900），目標(biāo)函數(shù)Z=2第94頁,共121頁，2024年2月25日，星期天單純形法的進(jìn)一步討論

通過大Ｍ法或兩階段法求初始的基本可行解。但是如果在大Ｍ法的最優(yōu)單純形表的基變量中仍含有人工變量，或者兩階段法的輔助線性規(guī)劃的目標(biāo)函數(shù)的極小值大于零，那么該線性規(guī)劃就不存在可行解。

無可行解第95頁,共121頁，2024年2月25日，星期天C

-3-2-1000-M-MCB

XB

bx1x2x3x4x5x6x7x8

θ0-M-Mx4x7x8

6431111000010-10-101001-100-1016/1-3/1Z-7M-6-4M-15-M-3+M-2+M-1-2M0-M-M000-M-2x4x7x2

3431021010-110-10-101001-100-1013/14/1-ZZ-3+M0-3-M0-M-202-M-3-M-2x1x7x2

3131021010-100-3-1-1-11101-100-101003-3M3-M-M1-M0-1例單純形法的進(jìn)一步討論運(yùn)算到檢驗(yàn)數(shù)全負(fù)為止，仍含有人工變量，無可行解。第96頁,共121頁，2024年2月25日，星期天單純形法的進(jìn)一步討論

無最優(yōu)解與無可行解時兩個不同的概念。無可行解是指原規(guī)劃不存在可行解，從幾何的角度解釋是指線性規(guī)劃問題的可行域?yàn)榭占粺o最優(yōu)解則是指線性規(guī)劃問題存在可行解，但是可行解的目標(biāo)函數(shù)達(dá)不到最優(yōu)值，即目標(biāo)函數(shù)在可行域內(nèi)可以趨于無窮大（或者無窮?。?。無最優(yōu)解也稱為有限最優(yōu)解，或無界解。

判別方法：無最優(yōu)解判別定理在求解極大化的線性規(guī)劃問題過程中，若某單純形表的檢驗(yàn)行存在某個大于零的檢驗(yàn)數(shù)，但是該檢驗(yàn)數(shù)所對應(yīng)的非基變量的系數(shù)列向量的全部系數(shù)都為負(fù)數(shù)或零，則該線性規(guī)劃問題無最優(yōu)解

無最優(yōu)解第97頁,共121頁，2024年2月25日，星期天C2200θ

CXB

B

x1

x2

x3

x4

0X3

1-11100X4

2-1/2101Z02200因但所以原問題無最優(yōu)解單純形法的進(jìn)一步討論第98頁,共121頁，2024年2月25日，星期天

退化即計(jì)算出的θ（用于確定換出變量）存在有兩個以上相同的最小比值，會造成下一次迭代中由一個或幾個基變量等于零，這就是退化（會產(chǎn)生退化解）。為避免出現(xiàn)計(jì)算的循環(huán)，勃蘭特(Bland)提出一個簡便有效的規(guī)則（攝動法原理）：⑴當(dāng)存在多個時，選下標(biāo)最小的非基變量為換入變量；(2)當(dāng)θ值出現(xiàn)兩個以上相同的最小值時，選下標(biāo)最小的基變量為換出變量。單純形法的進(jìn)一步討論第99頁,共121頁，2024年2月25日，星期天000-242-8030Z-5-60-420-805Z10001001x3

212060-2411x1

3321300-803x5

00-30-425-800Z11001001x7

00106-1-2410x1

30-1130-3-800x5

0-11001001x7

000106-1-2410x6

0000136-4-3210x5

0x7

x6

x5

x4

x3

x2

x1

b

XB

CB

000-242-803C

θ

第一次迭代中使用了攝動法原理，選擇下標(biāo)為6的基變量x6離基?？傻米顑?yōu)解maxZ=５，單純形法的進(jìn)一步討論第100頁,共121頁，2024年2月25日，星期天

無窮多最優(yōu)解若線性規(guī)劃問題某個基本可行解所有的非基變量檢驗(yàn)數(shù)都小于等于零，但其中存在一個檢驗(yàn)數(shù)等于零，那么該線性規(guī)劃問題有無窮多最優(yōu)解。例３：最優(yōu)表：非基變量檢驗(yàn)數(shù)，

所以有無窮多最優(yōu)解。C12000θCBXBbx1x2x3x4x5021x3x2x12320012-101010100-212/23/1-Z’80000-1單純形法的進(jìn)一步討論第101頁,共121頁，2024年2月25日，星期天單純形法的進(jìn)一步討論解的判別：1）唯一最優(yōu)解判別：最優(yōu)表中所有非基變量的檢驗(yàn)數(shù)非零,則線性規(guī)劃具有唯一最優(yōu)解。2）多重最優(yōu)解判別：最優(yōu)表中存在非基變量的檢驗(yàn)數(shù)為零,則線性規(guī)劃具有多重最優(yōu)解（或無窮多最優(yōu)解）。3）無界解判別：某個λk>0且aik≤０（i=1，2,…,m）則線性規(guī)劃具有無界解。4）無可行解的判斷：當(dāng)用大M單純形法計(jì)算得到最優(yōu)解并且存在Ri>0時，則表明原線性規(guī)劃無可行解。5）退化解的判別：存在某個基變量為零的基本可行解。第102頁,共121頁，2024年2月25日，星期天單純形法的進(jìn)一步討論單純性法小結(jié):建立模型個數(shù)取值右端項(xiàng)等式或不等式極大或極小新加變量系數(shù)兩個三個以上xj≥0xj無約束xj≤0

bi

≥0bi<0≤=≥maxZminZxs

xa求解圖解法、單純形法單純形法不處理令xj=

xj′

-xj″

xj′

≥0xj″

≥0令

xj’

=-xj不處理約束條件兩端同乘以-1加松弛變量xs加入人工變量xa減去xs加入xa不處理令z′=-ZminZ=－maxz′0-M第103頁,共121頁，2024年2月25日，星期天A第104頁,共121頁，2024年2月25日，星期天

線性規(guī)劃模型的應(yīng)用

一般而言，一個經(jīng)濟(jì)、管理問題凡是滿足以下條件時，才能建立線性規(guī)劃模型。

要求解問題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來反映，且為線性函數(shù)存在著多種方案要求達(dá)到的目標(biāo)是在一定條件下實(shí)現(xiàn)的，這些約束可用線性等式或不等式描述第105頁,共121頁，2024年2月25日，星期天

線性規(guī)劃模型的應(yīng)用常見問題合理利用線材問題：如何下料使用材最少。配料問題：在原料供應(yīng)量的限制下如何獲取最大利潤。投資問題：從投資項(xiàng)目中選取方案，使投資回報(bào)最大。產(chǎn)品生產(chǎn)計(jì)劃：合理利用人力、物力、財(cái)力等，使獲利最大。勞動力安排：用最少的勞動力來滿足工作的需要。運(yùn)輸問題：如何制定調(diào)運(yùn)方案，使總運(yùn)費(fèi)最小。第106頁,共121頁，2024年2月25日，星期天

線性規(guī)劃模型的應(yīng)用(1)設(shè)立決策變量；

(2)明確約束條件并用決策變量的線性等式或不等式表示；

(3)用決策變量的線性函數(shù)表示目標(biāo)，并確定是求極大（Max）還是極小（Min）；

(4)根據(jù)決策變量的物理性質(zhì)研究變量是否有非負(fù)性。建立線性規(guī)劃模型的過程可以分為四個步驟：第107頁,共121頁，2024年2月25日，星期天

線性規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用1.資源的合理利用

某廠計(jì)劃在下一生產(chǎn)周期內(nèi)生產(chǎn)B1,B2,…Bn種產(chǎn)品，要消耗A1,A2,…Am種資源，已知每件產(chǎn)品所