運籌學線性規(guī)劃和單純形法

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

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

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

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

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

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

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

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

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

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

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

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

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

設備產(chǎn)品AB

C

D利潤（元）

Ⅰ21402

Ⅱ22043

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

x1≥0,x2≥0

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

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

、x42.目標函數(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

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

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

z為總貨運成本則：

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ù)學模型第31頁,共121頁，2024年2月25日，星期天線性規(guī)劃問題的數(shù)學模型2.線性規(guī)劃的數(shù)學模型由三個要素構(gòu)成決策變量Decisionvariables目標函數(shù)Objectivefunction約束條件Constraints其特征是：（1）問題的目標函數(shù)是多個決策變量的線性函數(shù)，通常是求最大值或最小值；（2）問題的約束條件是一組多個決策變量的線性不等式或等式。

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

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

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

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

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

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

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

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

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

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

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

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

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

常量bi＜0

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

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

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

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

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

例1.9將線性規(guī)劃問題化為標準型解：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ù)學模型第47頁,共121頁，2024年2月25日，星期天線性規(guī)劃問題的數(shù)學模型7.線性規(guī)劃問題的解線性規(guī)劃問題求解線性規(guī)劃問題，就是從滿足約束條件(2)、(3)的方程組中找出一個解，使目標函數(shù)(1)達到最大值。第48頁,共121頁，2024年2月25日，星期天線性規(guī)劃問題的數(shù)學模型

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

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

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

…m)

為基向量。與基向量Pj

對應的變量xj

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

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

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

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

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

解題步驟4將最優(yōu)解代入目標函數(shù)，求出最優(yōu)值。1在直角平面坐標系中畫出所有的約束等式，并找出所有約束條件的公共部分，稱為可行域，可行域中的點稱為可行解。2標出目標函數(shù)值增加或者減小的方向。3若求最大（小）值，則令目標函數(shù)等值線沿（逆）目標函數(shù)值增加的方向平行移動，找與可行域最后相交的點，該點就是最優(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此點是唯一最優(yōu)解，且最優(yōu)目標函數(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

藍色線段上的所有點都是最優(yōu)解這種情形為有無窮多最優(yōu)解，但是最優(yōu)目標函數(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）可行域此點是唯一最優(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ù)以上例題，進一步分析討論可知線性規(guī)劃的可行域和最優(yōu)解有以下幾種可能的情況：

1.可行域為封閉的有界區(qū)域

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

2.可行域為封閉的無界區(qū)域

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

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

3.可行域為空集

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

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

學習要點：

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

2.作圖的關鍵有三點：

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

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

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

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

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

，選最小的θ對應基變量作為換出變量。 第70頁,共121頁，2024年2月25日，星期天單純形法的計算步驟用換入變量xk替換基變量中的換出變量，得到一個新的基。對應新的基可以找出一個新的基可行解，并相應地可以畫出一個新的單純形表。5）重復3）、4）步直到計算結(jié)束為止。 第71頁,共121頁，2024年2月25日，星期天單純形法的計算步驟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日，星期天單純形法的計算步驟例1.13

用單純形法求解解：將數(shù)學模型化為標準形式：不難看出x4、x5可作為初始基變量，列單純形表計算。第73頁,共121頁，2024年2月25日，星期天單純形法的計算步驟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日，星期天變成標準型單純形法的計算步驟例1.14用單純形法求解第75頁,共121頁，2024年2月25日，星期天約束方程的系數(shù)矩陣為基變量為非基變量I為單位矩陣且線性獨立單純形法的計算步驟第76頁,共121頁，2024年2月25日，星期天單純形法的計算步驟－cjcBxBb0000x3x4x5x61281612

2x2

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

學習要點：

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

2.熟練掌握線性規(guī)劃問題的標準化

3.熟練掌握單純形法的解題思路及求解步驟第81頁,共121頁，2024年2月25日，星期天單純形法的進一步討論－人工變量法人工變量法： 前面討論了在標準型中系數(shù)矩陣有單位矩陣，很容易確定一組基可行解。在實際問題中有些模型并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變量，構(gòu)成的可行基稱為人工基，用大M法或兩階段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法。第82頁,共121頁，2024年2月25日，星期天單純形法的進一步討論－人工變量法例1.10用大M法解下列線性規(guī)劃解：首先將數(shù)學模型化為標準形式系數(shù)矩陣中不存在單位矩陣，無法建立初始單純形表。第83頁,共121頁，2024年2月25日，星期天單純形法的進一步討論－人工變量法故人為添加兩個單位向量，得到人工變量單純形法數(shù)學模型：其中：M是一個很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個確定數(shù)值；再用前面介紹的單純形法求解該模型，計算結(jié)果見下表。第84頁,共121頁，2024年2月25日，星期天單純形法的進一步討論－人工變量法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日，星期天單純形法的進一步討論－人工變量法例1.11用大M法解下列線性規(guī)劃解：首先將數(shù)學模型化為標準形式系數(shù)矩陣中不存在單位矩陣，無法建立初始單純形表。第86頁,共121頁，2024年2月25日，星期天單純形法的進一步討論－人工變量法故人為添加兩個單位向量，得到人工變量單純形法數(shù)學模型：其中：M是一個很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個確定數(shù)值；再用前面介紹的單純形法求解該模型，計算結(jié)果見下表。第87頁,共121頁，2024年2月25日，星期天單純形法的進一步討論－人工變量法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日，星期天單純形法的進一步討論－人工變量法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日，星期天單純形法的進一步討論－兩階段法

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

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

對上述模型求解（單純形法），若ω=0,說明問題存在基可行解，可以進行第二個階段；否則，原問題無可行解，停止運算。第90頁,共121頁，2024年2月25日，星期天單純形法的進一步討論－兩階段法第一階段的線性規(guī)劃問題可寫為：第一階段單純形法迭代的過程見下表（注意：沒有化為極大化問題）第91頁,共121頁，2024年2月25日，星期天單純形法的進一步討論－兩階段法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日，星期天單純形法的進一步討論－兩階段法

第二階段：在第一階段的最終表中，去掉人工變量，將目標函數(shù)的系數(shù)換成原問題的目標函數(shù)系數(shù)，作為第二階段計算的初始表（用單純形法計算）。例：第93頁,共121頁，2024年2月25日，星期天單純形法的進一步討論－兩階段法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），目標函數(shù)Z=2第94頁,共121頁，2024年2月25日，星期天單純形法的進一步討論

通過大Ｍ法或兩階段法求初始的基本可行解。但是如果在大Ｍ法的最優(yōu)單純形表的基變量中仍含有人工變量，或者兩階段法的輔助線性規(guī)劃的目標函數(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例單純形法的進一步討論運算到檢驗數(shù)全負為止，仍含有人工變量，無可行解。第96頁,共121頁，2024年2月25日，星期天單純形法的進一步討論

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

判別方法：無最優(yōu)解判別定理在求解極大化的線性規(guī)劃問題過程中，若某單純形表的檢驗行存在某個大于零的檢驗數(shù)，但是該檢驗數(shù)所對應的非基變量的系數(shù)列向量的全部系數(shù)都為負數(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)解單純形法的進一步討論第98頁,共121頁，2024年2月25日，星期天

退化即計算出的θ（用于確定換出變量）存在有兩個以上相同的最小比值，會造成下一次迭代中由一個或幾個基變量等于零，這就是退化（會產(chǎn)生退化解）。為避免出現(xiàn)計算的循環(huán)，勃蘭特(Bland)提出一個簡便有效的規(guī)則（攝動法原理）：⑴當存在多個時，選下標最小的非基變量為換入變量；(2)當θ值出現(xià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

θ

第一次迭代中使用了攝動法原理，選擇下標為6的基變量x6離基。可得最優(yōu)解maxZ=５，單純形法的進一步討論第100頁,共121頁，2024年2月25日，星期天

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

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

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

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

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

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

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

(3)用決策變量的線性函數(shù)表示目標，并確定是求極大（Max）還是極?。∕in）；

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

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

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