運(yùn)籌學(xué)完整版課件-002

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

(OperationsResearch)經(jīng)濟(jì)管理學(xué)核心課程梁偉河海大學(xué)商學(xué)院（常州）liangw@運(yùn)籌學(xué)

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

） 系統(tǒng)工程的最重要的理論基礎(chǔ)之一，在美國(guó)有人把運(yùn)籌學(xué)稱(chēng)之為管理科學(xué)(ManagementScience)。運(yùn)籌學(xué)所研究的問(wèn)題，可簡(jiǎn)單地歸結(jié)為一句話(huà)：“依照給定條件和目標(biāo)，從眾多方案中選擇最佳方案”故有人稱(chēng)之為最優(yōu)化技術(shù)。運(yùn)籌學(xué)簡(jiǎn)述運(yùn)籌學(xué)（OperationsResearch,簡(jiǎn)緒論運(yùn)籌學(xué)的歷史與發(fā)展“運(yùn)籌學(xué)思想的出現(xiàn)可以追溯到很早—“田忌賽馬”。齊王要與大臣田忌賽馬，雙方各出上、中、下馬各一匹，對(duì)局三次，每次勝負(fù)1000金。田忌在好友、著名的軍事謀略家孫臏的指導(dǎo)下，以以下安排：齊王 上 中 下 田忌 下 上 中 緒論運(yùn)籌學(xué)的歷史與發(fā)展“運(yùn)籌學(xué)思想的出現(xiàn)可以追溯到很緒論丁謂的皇宮修復(fù)工程北宋年間，丁謂負(fù)責(zé)修復(fù)火毀的開(kāi)封皇宮。他的施工方案是：先將皇宮前的一條大街挖成一條大溝，將大溝與汴水相通。使用挖出的土就地制磚，令與汴水相連形成的河道承擔(dān)繁重的運(yùn)輸任務(wù)；修復(fù)工程完成后，實(shí)施大溝排水，并將原廢墟物回填，修復(fù)成原來(lái)的大街。丁謂將取材、運(yùn)輸及清廢用“一溝三用”巧妙地解決了，體現(xiàn)了系統(tǒng)規(guī)劃的思想。緒論丁謂的皇宮修復(fù)工程緒論國(guó)際上運(yùn)籌學(xué)的思想可追溯到1914年，當(dāng)時(shí)的蘭徹斯特提出了軍事運(yùn)籌學(xué)的作戰(zhàn)模型。1917年，丹麥工程師埃爾朗在研究自動(dòng)電話(huà)系統(tǒng)中通話(huà)線(xiàn)路與用戶(hù)呼叫的數(shù)量關(guān)系問(wèn)題時(shí)，提出了埃爾朗公式，研究了隨機(jī)服務(wù)系統(tǒng)中的系統(tǒng)排隊(duì)與系統(tǒng)擁擠問(wèn)題。存儲(chǔ)論的最優(yōu)批量公式是在20世紀(jì)20年代初提出的。緒論國(guó)際上運(yùn)籌學(xué)的思想可追溯到1914年，當(dāng)時(shí)的運(yùn)籌學(xué)簡(jiǎn)述“運(yùn)作研究(OperationalResearch)小組”:解決復(fù)雜的戰(zhàn)略和戰(zhàn)術(shù)問(wèn)題。例如：如何合理運(yùn)用雷達(dá)有效地對(duì)付德軍德空襲對(duì)商船如何進(jìn)行編隊(duì)護(hù)航，使船隊(duì)遭受德國(guó)潛艇攻擊時(shí)損失最少；在各種情況下如何調(diào)整反潛深水炸彈的爆炸深度，才能增加對(duì)德國(guó)潛艇的殺傷力等。運(yùn)籌學(xué)簡(jiǎn)述“運(yùn)作研究(OperationalResearc緒論

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

20世紀(jì)50年代中期，錢(qián)學(xué)森、許國(guó)志等教授在國(guó)內(nèi)全面介紹和推廣運(yùn)籌學(xué)知識(shí)，1956年，中國(guó)科學(xué)院成立第一個(gè)運(yùn)籌學(xué)研究室，1957年運(yùn)籌學(xué)運(yùn)用到建筑和紡織業(yè)中，1958年提出了圖上作業(yè)法，山東大學(xué)的管梅谷教授提出了“中國(guó)郵遞員問(wèn)題”，1970年，在華羅庚教授的直接指導(dǎo)下，在全國(guó)范圍內(nèi)推廣統(tǒng)籌方法和優(yōu)選法。1978年11月，在成都召開(kāi)了全國(guó)數(shù)學(xué)年會(huì)，對(duì)運(yùn)籌學(xué)的理論與應(yīng)用研究進(jìn)行了一次檢閱，1980年4月在山東濟(jì)南正式成立了“中國(guó)數(shù)學(xué)會(huì)運(yùn)籌學(xué)會(huì)”，1984年在上海召開(kāi)了“中國(guó)數(shù)學(xué)會(huì)運(yùn)籌學(xué)會(huì)第二屆代表大會(huì)暨學(xué)術(shù)交流會(huì)”，并將學(xué)會(huì)改名為“中國(guó)運(yùn)籌學(xué)會(huì)”。緒論20世紀(jì)50年代中期，錢(qián)學(xué)森緒論成熟的學(xué)科分支向縱深發(fā)展新的研究領(lǐng)域產(chǎn)生與新的技術(shù)結(jié)合與其他學(xué)科的結(jié)合加強(qiáng)傳統(tǒng)優(yōu)化觀(guān)念不斷變化運(yùn)籌學(xué)的發(fā)展趨勢(shì)緒論成熟的學(xué)科分支向縱深發(fā)展運(yùn)籌學(xué)的發(fā)展趨勢(shì)運(yùn)籌學(xué)的主要內(nèi)容數(shù)學(xué)規(guī)劃（線(xiàn)性規(guī)劃、整數(shù)規(guī)劃、目標(biāo)規(guī)劃、動(dòng)態(tài)規(guī)劃等）圖論存儲(chǔ)論排隊(duì)論對(duì)策論排序與統(tǒng)籌方法決策分析運(yùn)籌學(xué)的主要內(nèi)容數(shù)學(xué)規(guī)劃（線(xiàn)性規(guī)劃、整數(shù)規(guī)劃、目標(biāo)規(guī)劃、動(dòng)態(tài)運(yùn)籌學(xué)的主要內(nèi)容1.線(xiàn)性規(guī)劃（LinearProgram）是一個(gè)成熟的分支，它有效的算法——單純形法，主要解決生產(chǎn)計(jì)劃問(wèn)題，合理下料問(wèn)題，最優(yōu)投資問(wèn)題。2.整數(shù)規(guī)劃(IntegrateProgram)：在線(xiàn)性規(guī)劃的基礎(chǔ)上，變量加上整數(shù)約束。3.非線(xiàn)性規(guī)劃(NonlinearProgram)：目標(biāo)函數(shù)和約束條件是非線(xiàn)性函數(shù)，如證券投資組合優(yōu)化:如何合理投資使風(fēng)險(xiǎn)最小。4.動(dòng)態(tài)規(guī)劃(DynamicProgram)：多階段決策問(wèn)題。是美國(guó)貝爾曼于1951年提出的。運(yùn)籌學(xué)的主要內(nèi)容1.線(xiàn)性規(guī)劃（LinearProgra運(yùn)籌學(xué)的主要內(nèi)容5、圖與網(wǎng)絡(luò)(GraphTheoryandNetwork)：中國(guó)郵遞員問(wèn)題、哥尼斯堡城問(wèn)題、最短路、最大流問(wèn)題。6、存儲(chǔ)論（InventoryTheory)：主要解決生產(chǎn)中的庫(kù)存問(wèn)題，訂貨周期和訂貨量等問(wèn)題。7、排隊(duì)論(QueueTheory)：主要研究排隊(duì)系統(tǒng)中的系統(tǒng)排隊(duì)和系統(tǒng)擁擠現(xiàn)象，從而評(píng)估系統(tǒng)的服務(wù)質(zhì)量。8、對(duì)策論(GameTheory)：主要研究具有斗爭(zhēng)性質(zhì)的優(yōu)化問(wèn)題。9、決策分析(DecisionAnalysis)：主要研究定量化決策。運(yùn)籌學(xué)的主要內(nèi)容5、圖與網(wǎng)絡(luò)(GraphTheoryan本課程的教材及參考書(shū)選用教材《運(yùn)籌學(xué)教程》胡運(yùn)權(quán)主編（第3版）清華出版社參考教材《運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用》胡運(yùn)權(quán)主編哈工大出版社《管理運(yùn)籌學(xué)》韓伯棠主編（第2版）高等教育出版社《運(yùn)籌學(xué)》(修訂版)錢(qián)頌迪主編清華出版社本課程的教材及參考書(shū)選用教材本課程的特點(diǎn)和要求先修課：高等數(shù)學(xué)，基礎(chǔ)概率、線(xiàn)性代數(shù)特點(diǎn)：系統(tǒng)整體優(yōu)化；多學(xué)科的配合；模型方法的應(yīng)用運(yùn)籌學(xué)的研究的主要步驟：真實(shí)系統(tǒng)系統(tǒng)分析問(wèn)題描述模型建立與修改模型求解與檢驗(yàn)結(jié)果分析與實(shí)施數(shù)據(jù)準(zhǔn)備本課程的特點(diǎn)和要求先修課：高等數(shù)學(xué)，基礎(chǔ)概率、線(xiàn)性代數(shù)真實(shí)本課程授課方式與考核學(xué)科總成績(jī)平時(shí)成績(jī)（40％）課堂考勤（50％）平時(shí)作業(yè)（50％）期末成績(jī)（60％）講授為主，結(jié)合習(xí)題作業(yè)本課程授課方式與考核學(xué)科總成績(jī)平時(shí)成績(jī)課堂考勤平時(shí)作業(yè)期末成運(yùn)籌學(xué)在經(jīng)濟(jì)管理中的應(yīng)用運(yùn)籌學(xué)在經(jīng)濟(jì)管理中的應(yīng)用涉及的方面：生產(chǎn)計(jì)劃運(yùn)輸問(wèn)題人事管理庫(kù)存管理市場(chǎng)營(yíng)銷(xiāo)財(cái)務(wù)和會(huì)計(jì)物流配送另外，還應(yīng)用于設(shè)備維修、更新和可靠性分析，項(xiàng)目的選擇與評(píng)價(jià)，工程優(yōu)化設(shè)計(jì)等。運(yùn)籌學(xué)在經(jīng)濟(jì)管理中的應(yīng)用運(yùn)籌學(xué)在經(jīng)濟(jì)管理中的應(yīng)用涉及的方面：“管理運(yùn)籌學(xué)”軟件介紹“管理運(yùn)籌學(xué)”2.0版包括：線(xiàn)性規(guī)劃、運(yùn)輸問(wèn)題、整數(shù)規(guī)劃（0-1整數(shù)規(guī)劃、純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃）、目標(biāo)規(guī)劃、對(duì)策論、最短路徑、最小生成樹(shù)、最大流量、最小費(fèi)用最大流、關(guān)鍵路徑、存儲(chǔ)論、排隊(duì)論、決策分析、預(yù)測(cè)問(wèn)題和層次分析法，共15個(gè)子模塊?！肮芾磉\(yùn)籌學(xué)”軟件介紹“管理運(yùn)籌學(xué)”2.0版包括：線(xiàn)性規(guī)劃、運(yùn)籌帷幄之中決勝千里之外線(xiàn)性規(guī)劃及單純形法LinearProgramming第一章運(yùn)籌帷幄之中決勝千里之Chapter1線(xiàn)性規(guī)劃

(LinearProgramming)LP的數(shù)學(xué)模型圖解法單純形法單純形法的進(jìn)一步討論－人工變量法LP模型的應(yīng)用本章主要內(nèi)容：Chapter1線(xiàn)性規(guī)劃

(LinearProgra線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型1.規(guī)劃問(wèn)題生產(chǎn)和經(jīng)營(yíng)管理中經(jīng)常提出如何合理安排，使人力、物力等各種資源得到充分利用，獲得最大的效益，這就是規(guī)劃問(wèn)題。線(xiàn)性規(guī)劃通常解決下列兩類(lèi)問(wèn)題：（1）當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源（如資金、設(shè)備、原標(biāo)材料、人工、時(shí)間等）去完成確定的任務(wù)或目標(biāo)（2）在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟(jì)效益（如產(chǎn)品量最多、利潤(rùn)最大.）線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型1.規(guī)劃問(wèn)題生產(chǎn)和經(jīng)營(yíng)管理中經(jīng)常提出線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型例1.1如圖所示，如何截取x使鐵皮所圍成的容積最大？xa線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型例1.1如圖所示，如何截取x使鐵皮線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型例1.2某廠(chǎng)生產(chǎn)兩種產(chǎn)品，下表給出了單位產(chǎn)品所需資源及單位產(chǎn)品利潤(rùn)問(wèn)：應(yīng)如何安排生產(chǎn)計(jì)劃，才能使總利潤(rùn)最大？解：1.決策變量：設(shè)產(chǎn)品I、II的產(chǎn)量分別為x1、x22.目標(biāo)函數(shù)：設(shè)總利潤(rùn)為z，則有：

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

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

x1，x2≥0線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型例1.2某廠(chǎng)生產(chǎn)兩種產(chǎn)品，下表線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型例1.3已知資料如下表所示，問(wèn)如何安排生產(chǎn)才能使利潤(rùn)最大？或如何考慮利潤(rùn)大，產(chǎn)品好銷(xiāo)。

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

C

D利潤(rùn)（元）

Ⅰ21402

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

x1≥0,x2≥0

2x1+2x2≤12x1+2x2≤84x1≤164x2≤12線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型例1.3已知資料如下表所示，問(wèn)如何安線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型例1.4某廠(chǎng)生產(chǎn)三種藥物，這些藥物可以從四種不同的原料中提取。下表給出了單位原料可提取的藥物量解：要求：生產(chǎn)A種藥物至少160單位；B種藥物恰好200單位，C種藥物不超過(guò)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線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型例1.4某廠(chǎng)生產(chǎn)三種藥物，這些

例1.5

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

解：設(shè)：xj為第j號(hào)類(lèi)型船隊(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）線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型解：設(shè)：xj為第j號(hào)類(lèi)型船隊(duì)的隊(duì)數(shù)（j=1，2，3線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型2.線(xiàn)性規(guī)劃的數(shù)學(xué)模型由三個(gè)要素構(gòu)成決策變量Decisionvariables目標(biāo)函數(shù)Objectivefunction約束條件Constraints其特征是：（1）問(wèn)題的目標(biāo)函數(shù)是多個(gè)決策變量的線(xiàn)性函數(shù)，通常是求最大值或最小值；（2）問(wèn)題的約束條件是一組多個(gè)決策變量的線(xiàn)性不等式或等式。

怎樣辨別一個(gè)模型是線(xiàn)性規(guī)劃模型？

線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型2.線(xiàn)性規(guī)劃的數(shù)學(xué)模型由三個(gè)要素構(gòu)成線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型3.建模條件(1)

優(yōu)化條件：?jiǎn)栴}所要達(dá)到的目標(biāo)能用線(xiàn)型函數(shù)描述，且能夠用極值（max或min）來(lái)表示；(2)

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

選擇條件：有多種可選擇的方案供決策者選擇，以便找出最優(yōu)方案。線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型3.建模條件(1)優(yōu)化條件：?jiǎn)栴}線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型4.建模步驟(1)

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

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

寫(xiě)出目標(biāo)函數(shù)：即問(wèn)題所要達(dá)到的目標(biāo)，并明確是max還是min。線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型4.建模步驟(1)確定決策變量：線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型目標(biāo)函數(shù)：約束條件：5.線(xiàn)性規(guī)劃數(shù)學(xué)模型的一般形式簡(jiǎn)寫(xiě)為：線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型目標(biāo)函數(shù)：約束條件：5.線(xiàn)性規(guī)劃數(shù)學(xué)線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型向量形式：其中：線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型向量形式：其中：線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型矩陣形式：其中：線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型矩陣形式：其中：線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型6.線(xiàn)性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式特點(diǎn)：(1)目標(biāo)函數(shù)求最大值（有時(shí)求最小值）(2)約束條件都為等式方程，且右端常數(shù)項(xiàng)bi都大于或等于零(3)決策變量xj為非負(fù)。線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型6.線(xiàn)性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式特點(diǎn)：線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型（2）如何化標(biāo)準(zhǔn)形式目標(biāo)函數(shù)的轉(zhuǎn)換如果是求極小值即，則可將目標(biāo)函數(shù)乘以(-1)，可化為求極大值問(wèn)題。也就是：令，可得到上式。即

若存在取值無(wú)約束的變量，可令其中：變量的變換線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型（2）如何化標(biāo)準(zhǔn)形式目標(biāo)函數(shù)的轉(zhuǎn)換線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。稱(chēng)為松弛變量稱(chēng)為剩余變量常量bi＜0的變換:約束方程兩邊乘以（－1）線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型例1.6將下列線(xiàn)性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式用替換，且解:（１）因?yàn)閤3無(wú)符號(hào)要求，即x3取正值也可取負(fù)值，標(biāo)準(zhǔn)型中要求變量非負(fù)，所以線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型例1.6將下列線(xiàn)性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型(2)第一個(gè)約束條件是“≤”號(hào)，在“≤”左端加入松馳變量x4，x4≥0,化為等式；(3)第二個(gè)約束條件是“≥”號(hào)，在“≥”左端減去剩余變量x5，x5≥0；(4)第3個(gè)約束方程右端常數(shù)項(xiàng)為-5，方程兩邊同乘以(-1),將右端常數(shù)項(xiàng)化為正數(shù)；(5)目標(biāo)函數(shù)是最小值，為了化為求最大值，令z′=-z,得到maxz′=-z，即當(dāng)z達(dá)到最小值時(shí)z′達(dá)到最大值，反之亦然;線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型(2)第一個(gè)約束條件是“≤”號(hào)，在“線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型標(biāo)準(zhǔn)形式如下：線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型標(biāo)準(zhǔn)形式如下：

例1.7將下列線(xiàn)性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式為無(wú)約束（無(wú)非負(fù)限制）線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型例1.7將下列線(xiàn)性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式為無(wú)約束（

解:用替換，且，將第3個(gè)約束方程兩邊乘以（－1）將極小值問(wèn)題反號(hào)，變?yōu)榍髽O大值標(biāo)準(zhǔn)形式如下：引入變量線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型解:用替換，且

例1.8將線(xiàn)性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)型解：線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型例1.8將線(xiàn)性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)型解：線(xiàn)性規(guī)劃問(wèn)題

例1.9將線(xiàn)性規(guī)劃問(wèn)題化為標(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無(wú)約束

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

線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型例1.9將線(xiàn)性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)型解：Minf線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型7.線(xiàn)性規(guī)劃問(wèn)題的解線(xiàn)性規(guī)劃問(wèn)題求解線(xiàn)性規(guī)劃問(wèn)題，就是從滿(mǎn)足約束條件(2)、(3)的方程組中找出一個(gè)解，使目標(biāo)函數(shù)(1)達(dá)到最大值。線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型7.線(xiàn)性規(guī)劃問(wèn)題的解線(xiàn)性規(guī)劃問(wèn)題求解線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型

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

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

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

對(duì)應(yīng)的變量xj為基變量。除基變量以外的變量為非基變量。線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型可行解：滿(mǎn)足約束條件②、③的解為可線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型

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

基可行解：滿(mǎn)足變量非負(fù)約束條件的基本解，簡(jiǎn)稱(chēng)基可行解?？尚谢簩?duì)應(yīng)于基可行解的基稱(chēng)為可行基。非可行解可行解基解基可行解線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型基解：某一確定的基B，令非基變量等線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型例1.10求線(xiàn)性規(guī)劃問(wèn)題的所有基矩陣。解:約束方程的系數(shù)矩陣為2×5矩陣r(A)=2，2階子矩陣有10個(gè)，其中基矩陣只有9個(gè)，即線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型例1.10求線(xiàn)性規(guī)劃問(wèn)題的所有基矩圖解法線(xiàn)性規(guī)劃問(wèn)題的求解方法一般有兩種方法圖解法單純形法兩個(gè)變量、直角坐標(biāo)三個(gè)變量、立體坐標(biāo)適用于任意變量、但必需將一般形式變成標(biāo)準(zhǔn)形式下面我們分析一下簡(jiǎn)單的情況——只有兩個(gè)決策變量的線(xiàn)性規(guī)劃問(wèn)題，這時(shí)可以通過(guò)圖解的方法來(lái)求解。圖解法具有簡(jiǎn)單、直觀(guān)、便于初學(xué)者窺探線(xiàn)性規(guī)劃基本原理和幾何意義等優(yōu)點(diǎn)。圖解法線(xiàn)性規(guī)劃問(wèn)題的求解方法一般有圖解法兩個(gè)變量、直解題步驟4將最優(yōu)解代入目標(biāo)函數(shù)，求出最優(yōu)值。1在直角平面坐標(biāo)系中畫(huà)出所有的約束等式，并找出所有約束條件的公共部分，稱(chēng)為可行域，可行域中的點(diǎn)稱(chēng)為可行解。2標(biāo)出目標(biāo)函數(shù)值增加或者減小的方向。3若求最大（?。┲担瑒t令目標(biāo)函數(shù)等值線(xiàn)沿（逆）目標(biāo)函數(shù)值增加的方向平行移動(dòng)，找與可行域最后相交的點(diǎn)，該點(diǎn)就是最優(yōu)解。圖解法解題步驟4將最優(yōu)解代入目標(biāo)函數(shù)，求出最優(yōu)值。1在直圖解法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用圖解法求解線(xiàn)性規(guī)劃問(wèn)題圖解法maxZ=2X1+X2例1.11用圖解法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圖解法x1x2oX1-1.9X2=3.8(≤)X1圖解法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)色線(xiàn)段上的所有點(diǎn)都是最優(yōu)解這種情形為有無(wú)窮多最優(yōu)解，但是最優(yōu)目標(biāo)函數(shù)值maxZ=34.2是唯一的?？尚杏驁D解法maxZ=3X1+5.7X2x1x2oX1-1.圖解法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)解圖解法minZ=5X1+4X2x1x2oX1-1.9X圖解法246x1x2246無(wú)界解(無(wú)最優(yōu)解)maxZ=x1+2x2例1.6x1+x2=4(≥)x1+3x2=6(≥)3x1+x2=6(≥)maxZminZ圖解法246x1x2246無(wú)界解(無(wú)最優(yōu)解)maxZ=x1x1x2O10203040102030405050無(wú)可行解(即無(wú)最優(yōu)解)maxZ=3x1+4x2例1.7x1x2O10203040102030405050無(wú)可行解(由圖解法得到的幾種情況根據(jù)以上例題，進(jìn)一步分析討論可知線(xiàn)性規(guī)劃的可行域和最優(yōu)解有以下幾種可能的情況：1.可行域?yàn)榉忾]的有界區(qū)域(a)有唯一的最優(yōu)解；(b)有無(wú)窮多個(gè)最優(yōu)解；2.可行域?yàn)榉忾]的無(wú)界區(qū)域(c)有唯一的最優(yōu)解；(d)有無(wú)窮多個(gè)最優(yōu)解；(e)目標(biāo)函數(shù)無(wú)界(即雖有可行解，但在可行域中，目標(biāo)函數(shù)可以無(wú)限增大或無(wú)限減少)，因而沒(méi)有有限最優(yōu)解。3.可行域?yàn)榭占?f)沒(méi)有可行解，原問(wèn)題無(wú)最優(yōu)解圖解法由圖解法得到的幾種情況根據(jù)以上例題，進(jìn)由圖解法得到的啟示(1)線(xiàn)性規(guī)劃問(wèn)題解的情況：唯一最優(yōu)解；無(wú)窮多最優(yōu)解；無(wú)界解；無(wú)可行解(3)最優(yōu)解一定是在凸集的某個(gè)頂點(diǎn)(2)線(xiàn)性規(guī)劃問(wèn)題的可行域是凸集（凸多邊形）(4)解題思路是，先找出凸集的任一頂點(diǎn)，計(jì)算其目標(biāo)函數(shù)值，再與周?chē)旤c(diǎn)的目標(biāo)函數(shù)值比較，如不是最大，繼續(xù)比較，直到找出最大為止。圖解法由圖解法得到的啟示(1)線(xiàn)性規(guī)劃問(wèn)題解的情況：唯一圖解法 學(xué)習(xí)要點(diǎn)： 1.通過(guò)圖解法了解線(xiàn)性規(guī)劃有幾種解的形式（唯一最優(yōu)解；無(wú)窮多最優(yōu)解；無(wú)界解；無(wú)可行解）

2.作圖的關(guān)鍵有三點(diǎn)： (1)可行解區(qū)域要畫(huà)正確 (2)目標(biāo)函數(shù)增加的方向不能畫(huà)錯(cuò) (3)目標(biāo)函數(shù)的直線(xiàn)怎樣平行移動(dòng)圖解法 學(xué)習(xí)要點(diǎn)：連接幾何形體中任意兩點(diǎn)的線(xiàn)段仍完全在該幾何形體之中。有限個(gè)凸集的交集仍然是凸集。單純形法基本原理連接幾何形體中任意兩點(diǎn)的線(xiàn)段仍完全在該幾何形體之中。單純單純形法基本原理凸集：如果集合C中任意兩個(gè)點(diǎn)X1、X2，其連線(xiàn)上的所有點(diǎn)也都是集合C中的點(diǎn)，稱(chēng)C為凸集。凸集凸集不是凸集頂點(diǎn)頂點(diǎn)：如果凸集C中不存在任何兩個(gè)不同的點(diǎn)X1，X2，使X成為這兩個(gè)點(diǎn)連線(xiàn)上的一個(gè)點(diǎn)單純形法基本原理凸集：如果集合C中任意兩個(gè)點(diǎn)X1、X2，其連單純形法基本原理定理1：若線(xiàn)性規(guī)劃問(wèn)題存在可行解，則該問(wèn)題的可行域是凸集。定理2：線(xiàn)性規(guī)劃問(wèn)題的基可行解X對(duì)應(yīng)可行域(凸集)的頂點(diǎn)。定理3：若問(wèn)題存在最優(yōu)解，一定存在一個(gè)基可行解是最優(yōu)解。（或在某個(gè)頂點(diǎn)取得）單純形法基本原理定理1：若線(xiàn)性規(guī)劃問(wèn)題存在可行解，則該問(wèn)題的單純形法的計(jì)算步驟單純形法的思路找出一個(gè)初始可行解是否最優(yōu)轉(zhuǎn)移到另一個(gè)基本可行解（找出更大的目標(biāo)函數(shù)值）最優(yōu)解是否循環(huán)核心是：變量迭代結(jié)束單純形法的計(jì)算步驟單純形法的思路找出一個(gè)初始可行解是否最優(yōu)轉(zhuǎn)單純形法的計(jì)算步驟單純形表單純形法的計(jì)算步驟單純形表單純形法的計(jì)算步驟例1.12用單純形法求下列線(xiàn)性規(guī)劃的最優(yōu)解解：1）將問(wèn)題化為標(biāo)準(zhǔn)型，加入松馳變量x3、x4則標(biāo)準(zhǔn)型為:單純形法的計(jì)算步驟例1.12用單純形法求下列線(xiàn)性規(guī)劃的最單純形法的計(jì)算步驟2）求出線(xiàn)性規(guī)劃的初始基可行解，列出初始單純形表。cj3400θicB基bx1x2x3x40x34021100x43013013400檢驗(yàn)數(shù)單純形法的計(jì)算步驟2）求出線(xiàn)性規(guī)劃的初始基可行解，列出初始單單純形法的計(jì)算步驟3）進(jìn)行最優(yōu)性檢驗(yàn)如果表中所有檢驗(yàn)數(shù)，則表中的基可行解就是問(wèn)題的最優(yōu)解，計(jì)算停止。否則繼續(xù)下一步。4）從一個(gè)基可行解轉(zhuǎn)換到另一個(gè)目標(biāo)值更大的基可行解，列出新的單純形表確定換入基的變量。選擇，對(duì)應(yīng)的變量xj作為換入變量，當(dāng)有一個(gè)以上檢驗(yàn)數(shù)大于0時(shí)，一般選擇最大的一個(gè)檢驗(yàn)數(shù)，即：，其對(duì)應(yīng)的xk作為換入變量。確定換出變量。根據(jù)下式計(jì)算并選擇θ

，選最小的θ對(duì)應(yīng)基變量作為換出變量。 單純形法的計(jì)算步驟3）進(jìn)行最優(yōu)性檢驗(yàn)如果表中所有檢驗(yàn)數(shù)單純形法的計(jì)算步驟用換入變量xk替換基變量中的換出變量，得到一個(gè)新的基。對(duì)應(yīng)新的基可以找出一個(gè)新的基可行解，并相應(yīng)地可以畫(huà)出一個(gè)新的單純形表。5）重復(fù)3）、4）步直到計(jì)算結(jié)束為止。 單純形法的計(jì)算步驟用換入變量xk替換基變量中的換出變量，得到單純形法的計(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單純形法的計(jì)算步驟cj3400θicB基變量bx1x2x3x單純形法的計(jì)算步驟例1.13用單純形法求解解：將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式：不難看出x4、x5可作為初始基變量，列單純形表計(jì)算。單純形法的計(jì)算步驟例1.13用單純形法求解解：將數(shù)學(xué)模型單純形法的計(jì)算步驟cj12100θicB基變量bx1x2x3x4x50x4152-32100x5201/31501121000x42x220－x221/3150120753017131/30－90－22560x111017/31/31250128/9-1/92/335/300-98/9-1/9-7/3單純形法的計(jì)算步驟cj12100θicB基變量bx1x2x3變成標(biāo)準(zhǔn)型單純形法的計(jì)算步驟例1.14用單純形法求解變成標(biāo)準(zhǔn)型單純形法的計(jì)算步驟例1.14用單純形法求解約束方程的系數(shù)矩陣為基變量為非基變量I為單位矩陣且線(xiàn)性獨(dú)立單純形法的計(jì)算步驟約束方程的系數(shù)矩陣為基變量為非基變量I為單位矩陣且線(xiàn)性獨(dú)單純形法的計(jì)算步驟－cjcBxBb0000x3x4x5x61281612

2x2

單純形法的計(jì)算步驟－cjcBxBb0x312

運(yùn)籌學(xué)ppt完整版課件運(yùn)籌學(xué)ppt完整版課件運(yùn)籌學(xué)ppt完整版課件單純形法的計(jì)算步驟 學(xué)習(xí)要點(diǎn)：

1.線(xiàn)性規(guī)劃解的概念以及3個(gè)基本定理 2.熟練掌握線(xiàn)性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)化3.熟練掌握單純形法的解題思路及求解步驟單純形法的計(jì)算步驟 學(xué)習(xí)要點(diǎn)：?jiǎn)渭冃畏ǖ倪M(jìn)一步討論－人工變量法人工變量法： 前面討論了在標(biāo)準(zhǔn)型中系數(shù)矩陣有單位矩陣，很容易確定一組基可行解。在實(shí)際問(wèn)題中有些模型并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱(chēng)為人工變量，構(gòu)成的可行基稱(chēng)為人工基，用大M法或兩階段法求解，這種用人工變量作橋梁的求解方法稱(chēng)為人工變量法。單純形法的進(jìn)一步討論－人工變量法人工變量法：?jiǎn)渭冃畏ǖ倪M(jìn)一步討論－人工變量法例1.10用大M法解下列線(xiàn)性規(guī)劃解：首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式系數(shù)矩陣中不存在單位矩陣，無(wú)法建立初始單純形表。單純形法的進(jìn)一步討論－人工變量法例1.10用大M法解下列單純形法的進(jìn)一步討論－人工變量法故人為添加兩個(gè)單位向量，得到人工變量單純形法數(shù)學(xué)模型：其中：M是一個(gè)很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個(gè)確定數(shù)值；再用前面介紹的單純形法求解該模型，計(jì)算結(jié)果見(jiàn)下表。單純形法的進(jìn)一步討論－人工變量法故人為添加兩個(gè)單位向量，得到單純形法的進(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→→→單純形法的進(jìn)一步討論－人工變量法cj32-100-M-MCB單純形法的進(jìn)一步討論－人工變量法例1.11用大M法解下列線(xiàn)性規(guī)劃解：首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式系數(shù)矩陣中不存在單位矩陣，無(wú)法建立初始單純形表。單純形法的進(jìn)一步討論－人工變量法例1.11用大M法解下列單純形法的進(jìn)一步討論－人工變量法故人為添加兩個(gè)單位向量，得到人工變量單純形法數(shù)學(xué)模型：其中：M是一個(gè)很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個(gè)確定數(shù)值；再用前面介紹的單純形法求解該模型，計(jì)算結(jié)果見(jiàn)下表。單純形法的進(jìn)一步討論－人工變量法故人為添加兩個(gè)單位向量，得到單純形法的進(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→→單純形法的進(jìn)一步討論－人工變量法Cj3-1-100-M-MC單純形法的進(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→單純形法的進(jìn)一步討論－人工變量法Cj3-1-100-M-MC單純形法的進(jìn)一步討論－兩階段法

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

第一階段：在原線(xiàn)性規(guī)劃問(wèn)題中加入人工變量，構(gòu)造如下模型：對(duì)上述模型求解（單純形法），若ω=0,說(shuō)明問(wèn)題存在基可行解，可以進(jìn)行第二個(gè)階段；否則，原問(wèn)題無(wú)可行解，停止運(yùn)算。單純形法的進(jìn)一步討論－兩階段法用計(jì)算機(jī)處理數(shù)據(jù)時(shí)，只單純形法的進(jìn)一步討論－兩階段法第一階段的線(xiàn)性規(guī)劃問(wèn)題可寫(xiě)為：第一階段單純形法迭代的過(guò)程見(jiàn)下表（注意：沒(méi)有化為極大化問(wèn)題）單純形法的進(jìn)一步討論－兩階段法第一階段的線(xiàn)性規(guī)劃問(wèn)題可寫(xiě)為：?jiǎn)渭冃畏ǖ倪M(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→→單純形法的進(jìn)一步討論－兩階段法Cj3-1-100-M-MCB單純形法的進(jìn)一步討論－兩階段法

第二階段：在第一階段的最終表中，去掉人工變量，將目標(biāo)函數(shù)的系數(shù)換成原問(wèn)題的目標(biāo)函數(shù)系數(shù)，作為第二階段計(jì)算的初始表（用單純形法計(jì)算）。例：?jiǎn)渭冃畏ǖ倪M(jìn)一步討論－兩階段法第二階段：例：?jiǎn)渭冃畏ǖ倪M(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單純形法的進(jìn)一步討論－兩階段法cj3-1-100cBxBbx單純形法的進(jìn)一步討論通過(guò)大Ｍ法或兩階段法求初始的基本可行解。但是如果在大Ｍ法的最優(yōu)單純形表的基變量中仍含有人工變量，或者兩階段法的輔助線(xiàn)性規(guī)劃的目標(biāo)函數(shù)的極小值大于零，那么該線(xiàn)性規(guī)劃就不存在可行解。

無(wú)可行解單純形法的進(jìn)一步討論通過(guò)大Ｍ法或兩階段法求初C

-3-2-1000-M-M

CB

XB

b

x1x2x3x4x5x6x7x8

θ

0-M-M

x4x7x8

643

1111000010-10-101001-100-101

6/1-3/1

Z

-7M

-6-4M

-15-M

-3+M-2+M-1-2M0-M-M00

0-M-2

x4x7x2

343

1021010-110-10-101001-100-101

3/14/1-

Z

Z

-3+M0-3-M0-M-202-M

-3-M-2

x1x7x2

313

1021010-100-3-1-1-11101-100-101

003-3M3-M-M1-M0-1

例單純形法的進(jìn)一步討論運(yùn)算到檢驗(yàn)數(shù)全負(fù)為止，仍含有人工變量，無(wú)可行解。C-3-2-1單純形法的進(jìn)一步討論無(wú)最優(yōu)解與無(wú)可行解時(shí)兩個(gè)不同的概念。無(wú)可行解是指原規(guī)劃不存在可行解，從幾何的角度解釋是指線(xiàn)性規(guī)劃問(wèn)題的可行域?yàn)榭占?；無(wú)最優(yōu)解則是指線(xiàn)性規(guī)劃問(wèn)題存在可行解，但是可行解的目標(biāo)函數(shù)達(dá)不到最優(yōu)值，即目標(biāo)函數(shù)在可行域內(nèi)可以趨于無(wú)窮大（或者無(wú)窮?。o(wú)最優(yōu)解也稱(chēng)為有限最優(yōu)解，或無(wú)界解。

判別方法：無(wú)最優(yōu)解判別定理在求解極大化的線(xiàn)性規(guī)劃問(wèn)題過(guò)程中，若某單純形表的檢驗(yàn)行存在某個(gè)大于零的檢驗(yàn)數(shù)，但是該檢驗(yàn)數(shù)所對(duì)應(yīng)的非基變量的系數(shù)列向量的全部系數(shù)都為負(fù)數(shù)或零，則該線(xiàn)性規(guī)劃問(wèn)題無(wú)最優(yōu)解無(wú)最優(yōu)解單純形法的進(jìn)一步討論無(wú)最優(yōu)解與無(wú)可行解時(shí)兩個(gè)不同的概念。C2200θ

CXB

B

x1

x2

x3

x4

0X3

1-11100X4

2-1/2101Z02200因但所以原問(wèn)題無(wú)最優(yōu)解單純形法的進(jìn)一步討論C220退化即計(jì)算出的θ（用于確定換出變量）存在有兩個(gè)以上相同的最小比值，會(huì)造成下一次迭代中由一個(gè)或幾個(gè)基變量等于零，這就是退化（會(huì)產(chǎn)生退化解）。為避免出現(xiàn)計(jì)算的循環(huán)，勃蘭特(Bland)提出一個(gè)簡(jiǎn)便有效的規(guī)則（攝動(dòng)法原理）：⑴當(dāng)存在多個(gè)時(shí)，選下標(biāo)最小的非基變量為換入變量；(2)當(dāng)θ值出現(xiàn)兩個(gè)以上相同的最小值時(shí)，選下標(biāo)最小的基變量為換出變量。單純形法的進(jìn)一步討論退化即計(jì)算出的θ（用于確定換出變量）存在有兩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

θ

第一次迭代中使用了攝動(dòng)法原理，選擇下標(biāo)為6的基變量x6離基?？傻米顑?yōu)解maxZ=５，單純形法的進(jìn)一步討論000-242-8030Z-5-60-420-805Z100無(wú)窮多最優(yōu)解若線(xiàn)性規(guī)劃問(wèn)題某個(gè)基本可行解所有的非基變量檢驗(yàn)數(shù)都小于等于零，但其中存在一個(gè)檢驗(yàn)數(shù)等于零，那么該線(xiàn)性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。例３：最優(yōu)表：非基變量檢驗(yàn)數(shù)，

所以有無(wú)窮多最優(yōu)解。C12000θCBXBbx1x2x3x4x5021x3x2x12320012-101010100-212/23/1-Z’80000-1單純形法的進(jìn)一步討論無(wú)窮多最優(yōu)解若線(xiàn)性規(guī)劃問(wèn)題某個(gè)基本可行解所有的非單純形法的進(jìn)一步討論解的判別：1）唯一最優(yōu)解判別：最優(yōu)表中所有非基變量的檢驗(yàn)數(shù)非零,則線(xiàn)性規(guī)劃具有唯一最優(yōu)解。2）多重最優(yōu)解判別：最優(yōu)表中存在非基變量的檢驗(yàn)數(shù)為零,則線(xiàn)性規(guī)劃具有多重最優(yōu)解（或無(wú)窮多最優(yōu)解）。3）無(wú)界解判別：某個(gè)λk>0且aik≤０（i=1，2,…,m）則線(xiàn)性規(guī)劃具有無(wú)界解。4）無(wú)可行解的判斷：當(dāng)用大M單純形法計(jì)算得到最優(yōu)解并且存在Ri>0時(shí)，則表明原線(xiàn)性規(guī)劃無(wú)可行解。5）退化解的判別：存在某個(gè)基變量為零的基本可行解。單純形法的進(jìn)一步討論解的判別：?jiǎn)渭冃畏ǖ倪M(jìn)一步討論單純性法小結(jié):建立模型個(gè)數(shù)取值右端項(xiàng)等式或不等式極大或極小新加變量系數(shù)兩個(gè)三個(gè)以上x(chóng)j≥0xj無(wú)約束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單純形法的進(jìn)一步討論單純性法小結(jié):建個(gè)數(shù)取值右AA線(xiàn)性規(guī)劃模型的應(yīng)用 一般而言，一個(gè)經(jīng)濟(jì)、管理問(wèn)題凡是滿(mǎn)足以下條件時(shí)，才能建立線(xiàn)性規(guī)劃模型。要求解問(wèn)題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來(lái)反映，且為線(xiàn)性函數(shù)存在著多種方案要求達(dá)到的目標(biāo)是在一定條件下實(shí)現(xiàn)的，這些約束可用線(xiàn)性等式或不等式描述線(xiàn)性規(guī)劃模型的應(yīng)用 一般而言，一個(gè)經(jīng)濟(jì)、管理問(wèn)題凡是滿(mǎn)足以線(xiàn)性規(guī)劃模型的應(yīng)用常見(jiàn)問(wèn)題合理利用線(xiàn)材問(wèn)題：如何下料使用材最少。配料問(wèn)題：在原料供應(yīng)量的限制下如何獲取最大利潤(rùn)。投資問(wèn)題：從投資項(xiàng)目中選取方案，使投資回報(bào)最大。產(chǎn)品生產(chǎn)計(jì)劃：合理利用人力、物力、財(cái)力等，使獲利最大。勞動(dòng)力安排：用最少的勞動(dòng)力來(lái)滿(mǎn)足工作的需要。運(yùn)輸問(wèn)題：如何制定調(diào)運(yùn)方案，使總運(yùn)費(fèi)最小。線(xiàn)性規(guī)劃模型的應(yīng)用常見(jiàn)問(wèn)題合理利用線(xiàn)材問(wèn)題：如何下料使用材線(xiàn)性規(guī)劃模型的應(yīng)用(1)設(shè)立決策變量；(2)明確約束條件并用決策變量的線(xiàn)性等式或不等式表示；(3)用決策變量的線(xiàn)性函數(shù)表示目標(biāo)，并確定是求極大（Max）還是極?。∕in）；(4)根據(jù)決策變量的物理性質(zhì)研究變量是否有非負(fù)性。建立線(xiàn)性規(guī)劃模型的過(guò)程可以分為四個(gè)步驟：線(xiàn)性規(guī)劃模型的應(yīng)用(1)設(shè)立決策變量；建立線(xiàn)性規(guī)劃模線(xiàn)性規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用1.資源的合理利用某廠(chǎng)計(jì)劃在下一生產(chǎn)周期內(nèi)生產(chǎn)B1,B2,…Bn種產(chǎn)品，要消耗A1,A2,…Am種資源，已知每件產(chǎn)品所消耗的資源數(shù)、每種資源的數(shù)量限制以及每件產(chǎn)品可獲得的利潤(rùn)如表所示，問(wèn)如何安排生產(chǎn)計(jì)劃，才能充分利用現(xiàn)有的資源，使獲得的總利潤(rùn)最大？單件產(chǎn)消耗品資源資源限制單件利潤(rùn)線(xiàn)性規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用1.資源的合理利用線(xiàn)性規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用2.生產(chǎn)組織與計(jì)劃問(wèn)題某工廠(chǎng)用機(jī)床A1,A2,…Am加工B1,B2,…Bn種零件。在一個(gè)周期內(nèi)，各機(jī)床可能工作的機(jī)時(shí)（臺(tái)時(shí)），工廠(chǎng)必須完成各種零件的數(shù)量、各機(jī)床加工每個(gè)零件的時(shí)間（機(jī)時(shí)/個(gè)）和加工每個(gè)零件的成本（元/個(gè)）如表所示，問(wèn)如何安排各機(jī)床的生產(chǎn)任務(wù)，才能完成加工任務(wù)，又使總成本最低？加工零時(shí)間件機(jī)床機(jī)時(shí)限制必須零件數(shù)加工零成本件機(jī)床線(xiàn)性規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用2.生產(chǎn)組織與計(jì)劃問(wèn)題線(xiàn)性規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用線(xiàn)性規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用 某廠(chǎng)生產(chǎn)Ⅰ、Ⅱ、Ⅲ三種產(chǎn)品，都分別經(jīng)A、B兩道工序加工。設(shè)A工序可分別在設(shè)備A1和A2上完成，有B1、B2、B3三種設(shè)備可用于完成B工序。已知產(chǎn)品Ⅰ可在A、B任何一種設(shè)備上加工；產(chǎn)品Ⅱ可在任何規(guī)格的A設(shè)備上加工，但完成B工序時(shí)，只能在B1設(shè)備上加工；產(chǎn)品Ⅲ只能在A2與B2設(shè)備上加工。加工單位產(chǎn)品所需工序時(shí)間及其他各項(xiàng)數(shù)據(jù)如下表，試安排最優(yōu)生產(chǎn)計(jì)劃，使該廠(chǎng)獲利最大。線(xiàn)性規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用 某廠(chǎng)生產(chǎn)Ⅰ、Ⅱ、Ⅲ三種產(chǎn)品，都分別經(jīng)A、B兩道工序加工。設(shè)線(xiàn)性規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用設(shè)備產(chǎn)品設(shè)備有效臺(tái)時(shí)設(shè)備加工費(fèi)（單位小時(shí)）ⅠⅡⅢ27910000321B168124000250B247000783B37114000200原料費(fèi)（每件）0.250.350.5售價(jià)（每件）1.252.002.8線(xiàn)性規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用設(shè)備產(chǎn)品設(shè)備有效臺(tái)時(shí)設(shè)備加工費(fèi)Ⅰ解：設(shè)xijk表示產(chǎn)品i在工序j的設(shè)備k上加工的數(shù)量。約束條件有：線(xiàn)性規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用解：設(shè)xijk表示產(chǎn)品i在工序j的設(shè)備k上加工的數(shù)量。約束條線(xiàn)性規(guī)劃在管理中的應(yīng)用目標(biāo)是利潤(rùn)最大化，即利潤(rùn)的計(jì)算公式如下：帶入數(shù)據(jù)整理得到：線(xiàn)性規(guī)劃在管理中的應(yīng)用目標(biāo)是利潤(rùn)最大化，即利潤(rùn)的計(jì)算公式如線(xiàn)性規(guī)劃在管理中的應(yīng)用因此該規(guī)劃問(wèn)題的模型為：線(xiàn)性規(guī)劃在管理中的應(yīng)用因此該規(guī)劃問(wèn)題的模型為：線(xiàn)性規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用例：現(xiàn)有一批某種型號(hào)的圓鋼長(zhǎng)8米，需要截取2.5米長(zhǎng)的毛坯100根，長(zhǎng)1.3米的毛坯200根。問(wèn)如何才能既滿(mǎn)足需要，又能使總的用料最少？解：為了找到一個(gè)省料的套裁方案，必須先設(shè)計(jì)出較好的幾個(gè)下料方案。其次要求這些方案的總體能裁下所有各種規(guī)格的圓鋼，以滿(mǎn)足對(duì)各種不同規(guī)格圓鋼的需要并達(dá)到省料的目的，為此可以設(shè)計(jì)出4種下料方案以供套裁用。ⅠⅡⅢⅣ2.5m32101.3m0246料頭0.50.40.30.23.合理下料問(wèn)題線(xiàn)性規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用例：現(xiàn)有一批某種型號(hào)的圓鋼長(zhǎng)8米線(xiàn)性規(guī)劃在管理中的應(yīng)用設(shè)按方案Ⅰ、Ⅱ、Ⅲ、Ⅳ下料的原材料根數(shù)分別為xj(j=1，2,3,4)，可列出下面的數(shù)學(xué)模型：線(xiàn)性規(guī)劃在管理中的應(yīng)用設(shè)按方案Ⅰ、Ⅱ、Ⅲ、Ⅳ下料的原材料根線(xiàn)性規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用4.合理配料問(wèn)題某飼養(yǎng)場(chǎng)用n種飼料B1,B2,…Bn配置成含有m種營(yíng)養(yǎng)成分A1,A2,…Am的混合飼料，其余資料如表所示。問(wèn)應(yīng)如何配料，才能既滿(mǎn)足需要，又使混合飼料的總成本最低？解：線(xiàn)性規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用4.合理配料問(wèn)題線(xiàn)性規(guī)劃在管理中的應(yīng)用例：某人每天食用甲、乙兩種食物（如豬肉、雞蛋），其資料如下：?jiǎn)杻煞N食物各食用多少，才能既滿(mǎn)足需要、又使總費(fèi)用最??？21.5原料單價(jià)1.007.5010.000.10.151.70.751.101.30A1A2A3

最低需要量

甲乙含量食物成分線(xiàn)性規(guī)劃在管理中的應(yīng)用例：某人每天食用甲、乙兩種食物（如豬線(xiàn)性規(guī)劃在管理中的應(yīng)用解：設(shè)Xj表示Bj種食物用量線(xiàn)性規(guī)劃在管理中的應(yīng)用解：設(shè)Xj表示Bj種食物用量線(xiàn)性規(guī)劃在管理中的應(yīng)用5.人力資源分配問(wèn)題例1.11某晝夜服務(wù)的公交線(xiàn)路每天各時(shí)間段內(nèi)所需司機(jī)和乘務(wù)人員人數(shù)如下表所示：班次時(shí)間所需人員16:00——10:0060210:00——14:0070314:00——18:0060418:00——22:0050522:00——2:002062:00——6:0030設(shè)司機(jī)和乘務(wù)人員分別在各時(shí)間段開(kāi)始時(shí)上班，并連續(xù)工作8小時(shí)，問(wèn)該公交線(xiàn)路應(yīng)怎樣安排司機(jī)和乘務(wù)人員，即能滿(mǎn)足工作需要，又使配備司機(jī)和乘務(wù)人員的人數(shù)減少?線(xiàn)性規(guī)劃在管理中的應(yīng)用5.人力資源分配問(wèn)題例1.11線(xiàn)性規(guī)劃在管理中的應(yīng)用解：設(shè)xi表示第i班次時(shí)開(kāi)始上班的司機(jī)和乘務(wù)人員人數(shù)。此問(wèn)題最優(yōu)解：x1＝50，x2＝20，x3＝50，x4＝0，x5＝20，x6＝10，一共需要司機(jī)和乘務(wù)員150人。線(xiàn)性規(guī)劃在管理中的應(yīng)用解：設(shè)xi表示第i班次時(shí)開(kāi)始上班的司Chapter2對(duì)偶理論

(DualityTheory)線(xiàn)性規(guī)劃的對(duì)偶模型對(duì)偶性質(zhì)對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋?zhuān)白觾r(jià)格對(duì)偶單純形法靈敏度分析本章主要內(nèi)容：Chapter2對(duì)偶理論

(DualityThe線(xiàn)性規(guī)劃的對(duì)偶模型 設(shè)某工廠(chǎng)生產(chǎn)兩種產(chǎn)品甲和乙，生產(chǎn)中需4種設(shè)備按A，B，C，D順序加工，每件產(chǎn)品加工所需的機(jī)時(shí)數(shù)、每件產(chǎn)品的利潤(rùn)值及每種設(shè)備的可利用機(jī)時(shí)數(shù)列于下表：產(chǎn)品數(shù)據(jù)表設(shè)備產(chǎn)品ABCD產(chǎn)品利潤(rùn)（元／件）

甲

21402乙

22043設(shè)備可利用機(jī)時(shí)數(shù)（時(shí)）

1281612問(wèn)：充分利用設(shè)備機(jī)時(shí)，工廠(chǎng)應(yīng)生產(chǎn)甲和乙型產(chǎn)品各多少件才能獲得最大利潤(rùn)？1.對(duì)偶問(wèn)題的提出線(xiàn)性規(guī)劃的對(duì)偶模型 設(shè)某工廠(chǎng)生產(chǎn)兩種產(chǎn)品甲和乙，生產(chǎn)中需4種線(xiàn)性規(guī)劃的對(duì)偶模型解：設(shè)甲、乙型產(chǎn)品各生產(chǎn)x1及x2件，則數(shù)學(xué)模型為：反過(guò)來(lái)問(wèn)：若廠(chǎng)長(zhǎng)決定不生產(chǎn)甲和乙型產(chǎn)品，決定出租機(jī)器用于接受外加工，只收加工費(fèi)，那么４種機(jī)器的機(jī)時(shí)如何定價(jià)才是最佳決策？線(xiàn)性規(guī)劃的對(duì)偶模型解：設(shè)甲、乙型產(chǎn)品各生產(chǎn)x1及x2件，則數(shù)線(xiàn)性規(guī)劃的對(duì)偶模型在市場(chǎng)競(jìng)爭(zhēng)的時(shí)代，廠(chǎng)長(zhǎng)的最佳決策顯然應(yīng)符合兩條：

（1）不吃虧原則。即機(jī)時(shí)定價(jià)所賺利潤(rùn)不能低于加工甲、乙型產(chǎn)品所獲利潤(rùn)。由此原則，便構(gòu)成了新規(guī)劃的不等式約束條件。（2）競(jìng)爭(zhēng)性原則。即在上述不吃虧原則下，盡量降低機(jī)時(shí)總收費(fèi)，以便爭(zhēng)取更多用戶(hù)。設(shè)A、B、C、D設(shè)備的機(jī)時(shí)價(jià)分別為y1、y2、y3、y4，則新的線(xiàn)性規(guī)劃數(shù)學(xué)模型為：線(xiàn)性規(guī)劃的對(duì)偶模型在市場(chǎng)競(jìng)爭(zhēng)的時(shí)代，廠(chǎng)長(zhǎng)的最佳決策顯然應(yīng)符合線(xiàn)性規(guī)劃的對(duì)偶模型把同種問(wèn)題的兩種提法所獲得的數(shù)學(xué)模型用表2表示，將會(huì)發(fā)現(xiàn)一個(gè)有趣的現(xiàn)象。原問(wèn)題與對(duì)偶問(wèn)題對(duì)比表A（y1）

B（y2）C（y3）

D（y4）

甲（x1）

21402乙（x2）

220431281612

minωmaxz

對(duì)偶性是線(xiàn)性規(guī)劃問(wèn)題的最重要的內(nèi)容之一。每一個(gè)線(xiàn)性規(guī)劃（LP）必然有與之相伴而生的另一個(gè)線(xiàn)性規(guī)劃問(wèn)題，即任何一個(gè)求maxZ的LP都有一個(gè)求minZ的LP。其中的一個(gè)問(wèn)題叫“原問(wèn)題”，記為“P”，另一個(gè)稱(chēng)為“對(duì)偶問(wèn)題”，記為“D”。線(xiàn)性規(guī)劃的對(duì)偶模型把同種問(wèn)題的兩種提法所獲得的數(shù)學(xué)模型用表2線(xiàn)性規(guī)劃的對(duì)偶模型2.原問(wèn)題與對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系原問(wèn)題-P對(duì)偶問(wèn)題-D線(xiàn)性規(guī)劃的對(duì)偶模型2.原問(wèn)題與對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系原問(wèn)題-線(xiàn)性規(guī)劃的對(duì)偶模型23x1

x2

原問(wèn)題12y1

22≤128y2

12≤816y340≤1612y404≤12對(duì)偶問(wèn)題23線(xiàn)性規(guī)劃的對(duì)偶模型23x1x2原問(wèn)題12y122≤12線(xiàn)性規(guī)劃的對(duì)偶模型（1）對(duì)稱(chēng)形式 特點(diǎn)：目標(biāo)函數(shù)求極大值時(shí)，所有約束條件為≤號(hào)，變量非負(fù);目標(biāo)函數(shù)求極小值時(shí)，所有約束條件為≥號(hào)，變量非負(fù).原問(wèn)題對(duì)偶問(wèn)題目標(biāo)函數(shù)maxmin約束條件≤≥變量數(shù)量約束條件個(gè)數(shù)約束條件個(gè)數(shù)變量數(shù)量線(xiàn)性規(guī)劃的對(duì)偶模型（1）對(duì)稱(chēng)形式 特點(diǎn)：目標(biāo)函數(shù)求極大值時(shí)，線(xiàn)性規(guī)劃的對(duì)偶模型例2.1寫(xiě)出線(xiàn)性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題解：首先將原問(wèn)題變形為對(duì)稱(chēng)形式

注意：以后不強(qiáng)調(diào)等式右段項(xiàng)b≥0，原因在對(duì)偶單純型表中只保證而不保證，故b可以是負(fù)數(shù)。線(xiàn)性規(guī)劃的對(duì)偶模型例2.1寫(xiě)出線(xiàn)性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題解：線(xiàn)性規(guī)劃的對(duì)偶模型線(xiàn)性規(guī)劃的對(duì)偶模型線(xiàn)性規(guī)劃的對(duì)偶模型(2)非對(duì)稱(chēng)型對(duì)偶問(wèn)題 若給出的線(xiàn)性規(guī)劃不是對(duì)稱(chēng)形式，可以先化成對(duì)稱(chēng)形式再寫(xiě)對(duì)偶問(wèn)題。也可直接按教材表2-2中的對(duì)應(yīng)關(guān)系寫(xiě)出非對(duì)稱(chēng)形式的對(duì)偶問(wèn)題。線(xiàn)性規(guī)劃的對(duì)偶模型(2)非對(duì)稱(chēng)型對(duì)偶問(wèn)題 若給出的線(xiàn)性規(guī)劃線(xiàn)性規(guī)劃的對(duì)偶模型原問(wèn)題（或?qū)ε紗?wèn)題）對(duì)偶問(wèn)題（或原問(wèn)題）目標(biāo)函數(shù)max目標(biāo)函數(shù)min約束條件m個(gè)m個(gè)變量≤≥0≥≤0=無(wú)約束變量n個(gè)n個(gè)約束條件≥0≥≤0≤無(wú)約束=b約束條件右端項(xiàng)目標(biāo)函數(shù)變量的系數(shù)C目標(biāo)函數(shù)變量的系數(shù)約束條件右端項(xiàng)線(xiàn)性規(guī)劃的對(duì)偶模型原問(wèn)題（或?qū)ε紗?wèn)題）對(duì)偶問(wèn)題（或原問(wèn)題）目線(xiàn)性規(guī)劃的對(duì)偶模型例2.2寫(xiě)出下列線(xiàn)性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題.解：原問(wèn)題的對(duì)偶問(wèn)題為無(wú)約束線(xiàn)性規(guī)劃的對(duì)偶模型例2.2寫(xiě)出下列線(xiàn)性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題線(xiàn)性規(guī)劃的對(duì)偶模型例2.3寫(xiě)出下列線(xiàn)性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題.解：原問(wèn)題的對(duì)偶問(wèn)題為線(xiàn)性規(guī)劃的對(duì)偶模型例2.3寫(xiě)出下列線(xiàn)性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題線(xiàn)性規(guī)劃的對(duì)偶模型例2.4線(xiàn)性規(guī)劃的對(duì)偶模型例2.4線(xiàn)性規(guī)劃的對(duì)偶模型線(xiàn)性規(guī)劃的對(duì)偶模型對(duì)偶性質(zhì)性質(zhì)1對(duì)稱(chēng)性定理：對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題minZ’=-CXs.t.-AX≤-b X≥0

minW=Ybs.t.YA≥CY≤0maxZ=CXs.t.AX≥bX≥0對(duì)偶的定義對(duì)偶的定義maxW’=-Ybs.t.YA≥CY≤0對(duì)偶性質(zhì)性質(zhì)1對(duì)稱(chēng)性定理：對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題minZ對(duì)偶性質(zhì)性質(zhì)2

弱對(duì)偶原理(弱對(duì)偶性)：設(shè)和分別是問(wèn)題(P)和(D)的可行解，則必有推論1:原問(wèn)題任一可行解的目標(biāo)函數(shù)值是其對(duì)偶問(wèn)題目標(biāo)函數(shù)值的下界；反之，對(duì)偶問(wèn)題任意可行解的目標(biāo)函數(shù)值是其原問(wèn)題目標(biāo)函數(shù)值的上界。推論2:

在一對(duì)對(duì)偶問(wèn)題（P）和（D）中，若其中一個(gè)問(wèn)題可行但目標(biāo)函數(shù)無(wú)界，則另一個(gè)問(wèn)題無(wú)可行解；反之不成立。這也是對(duì)偶問(wèn)題的無(wú)界性。對(duì)偶性質(zhì)性質(zhì)2弱對(duì)偶原理(弱對(duì)偶性)：設(shè)和對(duì)偶性質(zhì)無(wú)界（原）無(wú)可行解（對(duì)）關(guān)于無(wú)界性有如下結(jié)論：?jiǎn)栴}無(wú)界無(wú)可行解無(wú)可行解問(wèn)題無(wú)界對(duì)偶問(wèn)題原問(wèn)題例2.5對(duì)偶性質(zhì)無(wú)界（原）無(wú)可（對(duì)）關(guān)于無(wú)界性有如下結(jié)論：?jiǎn)栴}無(wú)界無(wú)對(duì)偶性質(zhì)推論3：在一對(duì)對(duì)偶問(wèn)題（P）和（D）中，若一個(gè)可行（如P），而另一個(gè)不可行（如D），則該可行的問(wèn)題目標(biāo)函數(shù)值無(wú)界。試估計(jì)它們目標(biāo)函數(shù)的界，并驗(yàn)證弱對(duì)偶性原理。（P）例2.6對(duì)偶性質(zhì)推論3：在一對(duì)對(duì)偶問(wèn)題（P）和（D）中，若一個(gè)可行（對(duì)偶性質(zhì)解：（D）由觀(guān)察可知：=（），=（1.1），分別是（P）和（D）的可行解。Z=10，W=40，故有，弱對(duì)偶定理成立。由推論⑴可知，W的最小值不能小于10，Z的最大值不能超過(guò)40。＜對(duì)偶性質(zhì)解：（D）由觀(guān)察可知：=（1.1對(duì)偶性質(zhì)性質(zhì)3

最優(yōu)性定理：如果是原問(wèn)題的可行解，是其對(duì)偶問(wèn)題的可行解，并且:則是原問(wèn)題的最優(yōu)解，是其對(duì)偶問(wèn)題的最優(yōu)解。例如:在一對(duì)對(duì)偶問(wèn)題（P）和（D）中，可找到X*=（），Y*=（1.2，0.2）,且Z=W28，則X*，Y*分別是P和D的最優(yōu)解。對(duì)偶性質(zhì)性質(zhì)3最優(yōu)性定理：如果是原問(wèn)題的可行解，對(duì)偶性質(zhì)性質(zhì)4強(qiáng)對(duì)偶性：若原問(wèn)題及其對(duì)偶問(wèn)題均具有可行解，則兩者均具有最