管理運(yùn)籌學(xué)全套

管理運(yùn)籌學(xué)整理課件數(shù)學(xué)的魅力與實(shí)質(zhì)數(shù)學(xué)的本質(zhì)是處理抽象對(duì)象，是比語(yǔ)言更精煉、更嚴(yán)謹(jǐn)?shù)姆?hào)系統(tǒng)。是人類理性的集中表達(dá)。數(shù)學(xué)的方法是建立一個(gè)牢不可破的公理體系，并以演繹推理的方法去構(gòu)建和擴(kuò)展整個(gè)學(xué)科體系。整理課件數(shù)學(xué)分支數(shù)學(xué)分支數(shù)學(xué)分支應(yīng)用

演繹方法

公理體系數(shù)學(xué)大廈整理課件數(shù)學(xué)的魅力與實(shí)質(zhì)數(shù)學(xué)方法在自然科學(xué)體系中無(wú)處不在，并取得了光輝的成就。19世紀(jì)以后，數(shù)學(xué)被廣泛深入地應(yīng)用于社會(huì)科學(xué)領(lǐng)域。經(jīng)濟(jì)學(xué)、管理學(xué)領(lǐng)域的許多大師具有高超的數(shù)學(xué)技能。整理課件數(shù)學(xué)的魅力與實(shí)質(zhì)本門課程不僅要學(xué)習(xí)一門課程，一套方法，更重要的是要學(xué)會(huì)理性分析問(wèn)題的方法。培養(yǎng)邏輯思維能力和抽象思維能力。數(shù)學(xué)在開(kāi)展的過(guò)程中遇到過(guò)許多問(wèn)題，而且也并非確切無(wú)疑，大家要敢于質(zhì)疑，敢于提問(wèn)題。整理課件數(shù)學(xué)的魅力與實(shí)質(zhì)一個(gè)例子：S=1-1+1-1+1…請(qǐng)問(wèn)S等于多少？？整理課件數(shù)學(xué)的魅力與實(shí)質(zhì)至少有三種解法：1、S=〔1-1〕+〔1-1〕+〔1-1〕…2、S=1+〔-1+1〕+〔-1+1〕…3、1-S=1-(1-1+1-1…)=1-1+1-1+1-1…=S得到2S=1，從而S=1/2。整理課件數(shù)學(xué)的魅力與實(shí)質(zhì)事實(shí)上，這是一個(gè)爭(zhēng)論未定的題目，反映了人類對(duì)自然認(rèn)識(shí)的缺乏。無(wú)窮的概念存在許多缺乏之處，而且并非絕對(duì)精確。不同的學(xué)派對(duì)無(wú)窮有著不同的認(rèn)識(shí)。整理課件考核方法平時(shí)成績(jī)占20%，每位同學(xué)的初始成績(jī)都是60分〔按100分為總分值計(jì)算〕。每次作業(yè)交上加1分，不交不加不減，拷貝別人作業(yè)一次扣2分。上課主動(dòng)答復(fù)以下問(wèn)題每次加2分。提出有價(jià)值問(wèn)題或發(fā)現(xiàn)老師錯(cuò)誤每次加5分。整理課件運(yùn)籌學(xué)的體系和開(kāi)展歷史定義運(yùn)籌學(xué)是一門應(yīng)用于管理有組織系統(tǒng)的科學(xué)它為掌管這類系統(tǒng)的人提供決策目標(biāo)和數(shù)量分析的工具運(yùn)籌學(xué)應(yīng)用分析、實(shí)驗(yàn)、量化的方法，對(duì)經(jīng)濟(jì)管理系統(tǒng)中人、財(cái)、物等有限資源進(jìn)行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實(shí)現(xiàn)最有效的管理正式起源與二次世界大戰(zhàn)，被稱為Operationsresearch,日本人翻譯為運(yùn)做學(xué)，臺(tái)灣人翻譯為作業(yè)研究整理課件運(yùn)籌學(xué)的體系和開(kāi)展歷史田忌賽馬萌芽在20世紀(jì)初，Lanchester戰(zhàn)斗方程。丹麥工程師愛(ài)爾朗研究通訊系統(tǒng)時(shí)提出了一些排隊(duì)論的公式。30年代，數(shù)學(xué)家列溫遜運(yùn)用運(yùn)籌思想分析商業(yè)廣告、顧客心理。整理課件運(yùn)籌學(xué)的體系和開(kāi)展歷史二次世界大戰(zhàn)中，英美科學(xué)家研究如何有效運(yùn)用雷達(dá)，研究船隊(duì)遇到襲擊如何減少損失，以及如何使用深水炸彈等緊迫問(wèn)題。應(yīng)用：德國(guó)潛艇被摧毀數(shù)增加到400%，船只中彈數(shù)由47%減少到29%。結(jié)果：打贏了空戰(zhàn)和海戰(zhàn)，保證了二次世界大戰(zhàn)的最終勝利。整理課件運(yùn)籌學(xué)在現(xiàn)實(shí)生活中的例子企業(yè)安排生產(chǎn)方案庫(kù)存管理公交系統(tǒng)優(yōu)化食堂窗口設(shè)置電腦游戲，帝國(guó)時(shí)代、魔獸爭(zhēng)霸等。整理課件運(yùn)籌學(xué)的學(xué)科體系規(guī)劃論：包括線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃等。1947年，Danzig提出單純形法，隨后規(guī)劃方法得到了廣泛的應(yīng)用。圖論與網(wǎng)絡(luò)分析：圖是研究離散事物之間關(guān)系的一種分析模型。例：有甲、乙、丙、丁、戊、己6名同學(xué)參加ABCDEF六個(gè)工程的比賽，下表是各運(yùn)發(fā)動(dòng)報(bào)名參賽的工程，問(wèn)6個(gè)工程順序如何安排，作到每名運(yùn)發(fā)動(dòng)不連續(xù)參加兩項(xiàng)比賽。整理課件運(yùn)籌學(xué)的學(xué)科體系A(chǔ)BCDEF甲**乙***丙**丁**戊**己**整理課件運(yùn)籌學(xué)的學(xué)科體系排隊(duì)論：研究公共效勞系統(tǒng)的運(yùn)行與優(yōu)化的數(shù)學(xué)理論方法。決策論：研究不確定情況以及風(fēng)險(xiǎn)情況下的決策。存儲(chǔ)論：研究企業(yè)的庫(kù)存方案，進(jìn)貨周期等。博弈論：研究競(jìng)爭(zhēng)環(huán)境下決策者行為的數(shù)學(xué)方法。整理課件運(yùn)籌學(xué)的工作步驟提出和形成問(wèn)題：弄清問(wèn)題的目標(biāo)，可能的約束，問(wèn)題的可控變量，相關(guān)參數(shù)等。建立模型：把問(wèn)題中的可控變量、參數(shù)、目標(biāo)、約束之間的關(guān)系用一定的模型表示出來(lái)。求解：用計(jì)算或?qū)嶒?yàn)方法求出問(wèn)題的解。解的檢驗(yàn)：檢查求解過(guò)程，檢查解能否反映現(xiàn)實(shí)問(wèn)題。解的實(shí)施：將解運(yùn)用到實(shí)際問(wèn)題中。整理課件第一章線性規(guī)劃整理課件本章內(nèi)容線性規(guī)劃模型線性規(guī)劃問(wèn)題的圖解法單純形法非標(biāo)準(zhǔn)形線性規(guī)劃的解法整理課件線性規(guī)劃模型規(guī)劃問(wèn)題：就是否合理利用有限資源的問(wèn)題。線性規(guī)劃：線性的規(guī)劃問(wèn)題。兩個(gè)意思：1、目標(biāo)函數(shù)是線性的2、約束條件是線性的

整理課件線性規(guī)劃模型生產(chǎn)決策問(wèn)題某汽車工廠生產(chǎn)大轎車和載重汽車兩種型號(hào)的汽車,每輛汽車所用的鋼材都是2噸/輛，該工廠每年供給的鋼材為1600噸；工廠的生產(chǎn)能力是每2.5小時(shí)可生產(chǎn)一輛載重汽車，每5小時(shí)可生產(chǎn)一輛大轎車，工廠全年的有效工時(shí)為2500小時(shí)；供給給該廠大轎車用的座椅每年可裝配400輛。據(jù)市場(chǎng)調(diào)查，出售一輛大轎車可獲利4000元，出售一輛載重汽車可獲利3000元。如何安排生產(chǎn)才能使工廠獲利最大？整理課件線性規(guī)劃模型建模型如下：設(shè)大轎車數(shù)量為x1,載重汽車數(shù)量為x2。s.t.是subjectto的簡(jiǎn)寫(xiě)，表示受限制于。整理課件線性規(guī)劃模型某工廠在方案期間內(nèi)生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗，如下表所示：ⅠⅡ設(shè)備11300臺(tái)時(shí)原料A21400Kg原料B01250KgⅠ、Ⅱ兩種產(chǎn)品每單位分別可以獲利50元、100元，問(wèn)工廠應(yīng)該如何安排生產(chǎn)才能使工廠獲利最多。整理課件線性規(guī)劃模型設(shè)置變量：生產(chǎn)Ⅰ產(chǎn)品x1個(gè)，Ⅱ產(chǎn)品x2個(gè)目標(biāo)函數(shù)是利潤(rùn)最大化：資源是有限的，第一個(gè)限制是設(shè)備臺(tái)時(shí)的限制：整理課件線性規(guī)劃模型第二個(gè)限制是原材料A的限制：第三個(gè)限制是原材料B的限制：顯然，產(chǎn)量不可能為負(fù)數(shù)：整理課件線性規(guī)劃模型建模型如下：設(shè)生產(chǎn)Ⅰ產(chǎn)品x1件,Ⅱ產(chǎn)品x2件。整理課件線性規(guī)劃模型〔1〕，〔2〕分別被稱為目標(biāo)函數(shù)和約束條件。目標(biāo)函數(shù)中變量的系數(shù)被稱為價(jià)值系數(shù)，約束條件不等號(hào)右端稱為資源向量或限定系數(shù)，約束條件左端變量的系數(shù)被稱為技術(shù)系數(shù)。目標(biāo)函數(shù)和約束條件都是一次冪函數(shù)，或稱線性函數(shù)，因此這類規(guī)劃問(wèn)題被稱為線性規(guī)劃問(wèn)題。整理課件線性規(guī)劃模型例3：生產(chǎn)卷煙的主要原材料包括煙葉和煙梗。國(guó)家規(guī)定每千克焦油含量不超過(guò)15mg，煙氣煙堿含量不超過(guò)1.4mg，現(xiàn)在知道每千克煙葉含焦油12mg，煙氣煙堿1.5mg，煙梗含焦油18mg，煙氣煙堿0.3mg，煙葉每千克50元，煙梗每千克20元，問(wèn)如何搭配使生產(chǎn)本錢最小。整理課件線性規(guī)劃模型設(shè)每千克卷煙用煙葉x1千克，煙梗x2千克，模型如下：這是目標(biāo)函數(shù)一個(gè)求最小化的問(wèn)題。整理課件線性規(guī)劃的標(biāo)準(zhǔn)形為求解方便，一般線性規(guī)劃都可以轉(zhuǎn)化成如下標(biāo)準(zhǔn)形式：要求整理課件線性規(guī)劃的標(biāo)準(zhǔn)形目標(biāo)函數(shù)為求最小化時(shí)，等式兩端同乘以-1，變?yōu)榍笞畲蠡＜s束條件為<=時(shí)，加一個(gè)松弛變量，約束條件為>=時(shí)，減一個(gè)剩余變量。資源變量為負(fù)數(shù)時(shí)，等式兩端同乘以-1。變量為<=0時(shí)，令變量無(wú)約束時(shí)，令整理課件線性規(guī)劃的圖解法以例1為例：整理課件線性規(guī)劃的圖解法x2800400400800x1整理課件線性規(guī)劃的圖解法從圖中可以得到：x1=200,x2=600,z=2600最優(yōu)解為：生產(chǎn)200輛大轎車，生產(chǎn)600輛載重汽車，可獲利潤(rùn)2600千元。鋼材和工時(shí)全部用完，座椅剩余200套。

整理課件幾個(gè)概念凸集：設(shè)k是n維歐氏空間中的一個(gè)點(diǎn)集，在集合中任意取兩點(diǎn)x1,x2∈k。如果這兩點(diǎn)連線上的一切點(diǎn)都落在k中，那么稱k為凸集。角頂：設(shè)k為凸集，x∈k，如果不能用不同的兩點(diǎn)x1,x2∈k線性表出x，那么稱x為k的一個(gè)角頂。角頂可行解和角頂不可行解：既是角頂解又是可行解的解稱為角頂可行解，是角頂解而不是可行解的解稱為角頂不可行解。整理課件圖解法的幾點(diǎn)啟示線性規(guī)劃的可行域必定為凸集。線性規(guī)劃的最優(yōu)解必定在頂點(diǎn)取得。如果有多個(gè)最優(yōu)解，那么至少有兩個(gè)相鄰的角頂可行解是最優(yōu)解。角頂可行解的數(shù)目是有限的。如果一個(gè)角頂可行解的目標(biāo)函數(shù)值比相鄰的所有角頂解好，它就是最優(yōu)解。整理課件解決線性規(guī)劃問(wèn)題的思路根本思路是在滿足約束條件的前提下，從一個(gè)初始頂點(diǎn)開(kāi)始，不斷尋找改進(jìn)目標(biāo)函數(shù)的頂點(diǎn)，直到無(wú)法改進(jìn)為止。步驟1：從一個(gè)角頂可行解出發(fā)，判斷相鄰的角頂可行解是否比目前的點(diǎn)更好。如果相鄰的角頂可行解都劣與這個(gè)頂點(diǎn)，那么說(shuō)明這個(gè)點(diǎn)已經(jīng)是最優(yōu)解，算法結(jié)束。步驟2：如果相鄰的角頂可行解更好，就向這個(gè)點(diǎn)移動(dòng)。重復(fù)步驟1。整理課件線性規(guī)劃問(wèn)題解的根本概念可行解：滿足約束條件解稱為可行解，對(duì)應(yīng)圖解法的陰影局部?；杭s束條件中任意一個(gè)m階非奇異子矩陣確定一個(gè)線性規(guī)劃問(wèn)題的基。對(duì)應(yīng)圖解法中的頂點(diǎn)。基可行解：既是可行解又是基解稱為基可行解。最優(yōu)解：滿足目標(biāo)函數(shù)和約束條件的解稱為最優(yōu)解。整理課件單純形法求解單純形法的步驟單純形表法單純形表法中的一些特殊情況整理課件求解單純形法的步驟步驟1：將模型轉(zhuǎn)化為標(biāo)準(zhǔn)形。步驟2：找到一個(gè)初始可行基，列出初始單純形表。步驟3：判斷初始可行基是否最優(yōu)。如果是最優(yōu)解那么結(jié)束，否那么轉(zhuǎn)步驟4。步驟4：如果不是最優(yōu)，那么通過(guò)一定的規(guī)那么將一個(gè)變量換出，另一個(gè)變量換入，構(gòu)成一個(gè)新的基解。轉(zhuǎn)步驟3。整理課件求解單純形法的步驟x2800400400800x1整理課件求解單純形法的步驟圖形解法只能解決2維的線性規(guī)劃問(wèn)題〔僅有兩個(gè)變量〕。對(duì)超過(guò)3維的情況，既無(wú)法在平面上畫(huà)出圖形，也無(wú)法進(jìn)行直觀的想象。根據(jù)圖形解法的啟示，提出單純形法解決線性規(guī)劃問(wèn)題的根本思路。整理課件單純形表法以例一為例：整理課件單純形表法步驟1：首先轉(zhuǎn)化為標(biāo)準(zhǔn)形式：添加松弛變量。整理課件單純形表法步驟2：找到一個(gè)初始可行基。即尋找一個(gè)m階的非奇異子矩陣。從標(biāo)準(zhǔn)形的線性規(guī)劃問(wèn)題中可以看出，x3,x4,x5構(gòu)成了一個(gè)3階的單位矩陣，把這三個(gè)變量作為初始可行基。列出初始單純形表。整理課件單純形表法列出初始單純形表：x1x2x3x4x5xCj

zj

zj-cj430002210052.501010001bθ整理課件單純形表法步驟3：確定換入換出變量。方法：先確定換入變量，計(jì)算檢驗(yàn)數(shù)zj-cj，計(jì)算方法：，cj為對(duì)應(yīng)xj的系數(shù)。以最負(fù)的檢驗(yàn)數(shù)對(duì)應(yīng)的系數(shù)列作為主列元素。隨后確定換出變量，計(jì)算檢驗(yàn)數(shù)θ，計(jì)算方法：，選擇θ值最小的行對(duì)應(yīng)的主列元素作為換出變量。整理課件單純形表法確定換入換出變量：x1x2x3x4x5xCj

zj-4-3000

zj-cj00000430002210052.5010[1]0001bθ0整理課件單純形表法步驟4：以主元素為中心，進(jìn)行迭代運(yùn)算。x1x2x3x4x5xCj

zj0-3004

zj-cj40004430000210-202.5

01-5

10001bθ1600整理課件單純形表法檢驗(yàn)數(shù)仍然有負(fù)數(shù)，繼續(xù)確定換出換入變量x1x2x3x4x5xCj

zj0-3004

zj-cj40004430000210-202.501-5

10001bθ1600整理課件單純形表法迭代運(yùn)算x1x2x3x4x5xCj

zj0001.2-2

zj-cj4301.2-243000001-0.8[4]01

00.4-2

10001bθ2200整理課件單純形表法繼續(xù)迭代：x1x2x3x4x5xCj

zj0010.40

zj-cj43000000.5-0.4101

0-0.4010-0.50.40b4310.402600整理課件單純形表法從表中可以看出，檢驗(yàn)數(shù)全部為正數(shù)或零，說(shuō)明已到達(dá)最優(yōu)。求得最優(yōu)解為：x1=200，x2=600，x3=0，x4=0，x5=200，Z=2600。生產(chǎn)方案為：生產(chǎn)大轎車200輛，生產(chǎn)載重汽車600輛，剩余座椅200套，利潤(rùn)為2600千元。整理課件單純形表法思考題1、用單純形法求解線性規(guī)劃問(wèn)題時(shí)為什么要首先轉(zhuǎn)化為標(biāo)準(zhǔn)形？2、為什么要選擇松弛變量作為初始可行基，能不能任意選擇幾個(gè)變量作為初始可行基？整理課件作業(yè)求解線性規(guī)劃問(wèn)題：整理課件作業(yè)某工廠在方案期內(nèi)要生產(chǎn)A、B兩種產(chǎn)品，生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及甲、乙兩種原材料的消耗如下表所示：AB設(shè)備128臺(tái)時(shí)原材料甲4016公斤原材料乙0412公斤整理課件作業(yè)該工廠每生產(chǎn)一件產(chǎn)品A可以獲利2元，每生產(chǎn)一件產(chǎn)品B可以獲利3元，問(wèn)應(yīng)該如何安排方案使該工廠獲利最多？要求：建立線性規(guī)劃模型并用單純形法求解。整理課件單純形表法例2：用單純形表法求解線性規(guī)劃問(wèn)題：整理課件單純形表法步驟1：首先轉(zhuǎn)化為標(biāo)準(zhǔn)形式：添加松弛變量。整理課件單純形表法步驟2：找到一個(gè)初始可行基。從標(biāo)準(zhǔn)形的線性規(guī)劃問(wèn)題中可以看出，x3,x4,x5構(gòu)成了一個(gè)3階的單位矩陣，把這三個(gè)變量作為初始可行基。列出初始單純形表。整理課件單純形表法列出初始單純形表：x1x2x3x4x5xCj

zj

zj-cj50100000111002101001001bθ整理課件單純形表法步驟3：確定換入換出變量。確定換入變量，計(jì)算檢驗(yàn)數(shù)zj-cj，計(jì)算方法：，cj為對(duì)應(yīng)xj的系數(shù)。以最負(fù)的檢驗(yàn)數(shù)對(duì)應(yīng)的系數(shù)列作為主列元素。隨后確定換出變量，計(jì)算檢驗(yàn)數(shù)θ，計(jì)算方法：，選擇θ值最小的行對(duì)應(yīng)的主列元素作為換出變量。整理課件單純形表法確定換入換出變量：x1x2x3x4x5xCj

zj-50-100000

zj-cj000005010000011100210100[1]001bθ0整理課件單純形表法步驟4：以主元素為中心，進(jìn)行迭代運(yùn)算。x1x2x3x4x5xCj

zj-500000

zj-cj0100000501000001010-12001-101001bθ25000整理課件單純形表法檢驗(yàn)數(shù)仍然有負(fù)數(shù)，繼續(xù)確定換出換入變量x1x2x3x4x5xCj

zj-500000

zj-cj010000050100000[1]010-12001-101001bθ25000整理課件單純形表法迭代運(yùn)算x1x2x3x4x5xCj

zj0050050

zj-cj501005005050100000

1010-100-21101001bθ27500整理課件單純形表法檢驗(yàn)數(shù)全部大于等于0，已經(jīng)求得最優(yōu)解。最優(yōu)解為：x1=50,x2=250,x3=0,x4=50,x5=0;Z=27500整理課件單純形表法例3：某工廠在方案期內(nèi)要生產(chǎn)A、B兩種產(chǎn)品，生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及甲、乙兩種原材料的消耗如下表所示：AB設(shè)備128臺(tái)時(shí)原材料甲4016公斤原材料乙0412公斤整理課件單純形表法該工廠每生產(chǎn)一件產(chǎn)品A可以獲利2元，每生產(chǎn)一件產(chǎn)品B可以獲利3元，問(wèn)應(yīng)該如何安排方案使該工廠獲利最多？要求：建立線性規(guī)劃模型并用單純形法求解。整理課件單純形表法A產(chǎn)品的產(chǎn)量設(shè)為x1，B產(chǎn)品的產(chǎn)量設(shè)為x2，建立模型如下：整理課件單純形表法最終單純形表為：x1x2x3x4x5xCj

zj001.50.1250

zj-cj231.50.1250230001000.25000-20.51010.5-0.1250bθ14整理課件單純形表法中一些問(wèn)題如果兩個(gè)θ相同，有可能產(chǎn)生退化現(xiàn)象〔死循環(huán)〕，可以用攝動(dòng)法求解，就是選下標(biāo)最小的變量作為換出變量。有一個(gè)以上的非基變量為0時(shí)，說(shuō)明有無(wú)窮多解，這時(shí)換入換出變量做完之后Z值不變，這時(shí)兩個(gè)點(diǎn)連線上的任何一點(diǎn)都是最優(yōu)解。主列元素全部為負(fù)數(shù)或0時(shí)，這時(shí)θ值無(wú)法計(jì)算，也無(wú)法確定換出變量，那么此時(shí)說(shuō)明有無(wú)界解，此時(shí)檢查你的計(jì)算過(guò)程看前面計(jì)算是否出現(xiàn)錯(cuò)誤，或檢查建模是否有錯(cuò)誤。整理課件思考題當(dāng)變量無(wú)約束時(shí)，需要做變換：請(qǐng)問(wèn)，會(huì)同時(shí)出現(xiàn)在最終單純形表中嗎？為什么？整理課件單純形法的進(jìn)一步討論目標(biāo)函數(shù)求最小化時(shí)，有兩種解決方法：1、目標(biāo)函數(shù)左右同乘以-1，變成求最大化的問(wèn)題。2、直接用單純形法計(jì)算，但是檢驗(yàn)規(guī)那么改變，以正的檢驗(yàn)數(shù)對(duì)應(yīng)的變量作為換入變量，當(dāng)全部檢驗(yàn)數(shù)為負(fù)數(shù)時(shí)迭代結(jié)束。整理課件單純形法的進(jìn)一步討論當(dāng)約束條件出現(xiàn)等號(hào)約束時(shí)，無(wú)法通過(guò)增加松弛變量的方法產(chǎn)生初始可行解，這時(shí)要使用增加人工變量的方法來(lái)產(chǎn)生初始可行基。由于人工變量在最終解中必須為0，否那么無(wú)法滿足約束條件，如何使人工變量在最優(yōu)解中為0？用大M法。整理課件大M法當(dāng)目標(biāo)函數(shù)是求極大值時(shí)，令人工變量在目標(biāo)函數(shù)中的系數(shù)為-M，其中M是一個(gè)非常大的正數(shù)。這樣，如果人工變量不為0，那么目標(biāo)函數(shù)就無(wú)法取到最優(yōu)。當(dāng)目標(biāo)函數(shù)是求最小時(shí)，令人工變量在目標(biāo)函數(shù)中的系數(shù)為M〔為什么？〕。整理課件大M法例4：整理課件大M法化為標(biāo)準(zhǔn)形，約束條件變?yōu)椋赫碚n件大M法系數(shù)行列式為：這時(shí)無(wú)法直接在系數(shù)矩陣中找到一個(gè)初始可行解。把第三個(gè)約束條件添加一個(gè)人工變量。整理課件大M法約束條件：變?yōu)椋河蛇@兩個(gè)式子可以看出x5必定等于0。整理課件大M法系數(shù)行列式變?yōu)椋撼霈F(xiàn)了一個(gè)三維的單位矩陣，可以用單純形法求解了，但還要保證x5=0，所以目標(biāo)函數(shù)變形為：整理課件大M法列出初始單純形表：x1x2x3x4x5xCj

zj-3M-3–2M-5000

zj-cj-3M-2M00-M3500-M[1]01000201032001bθ-18M整理課件大M法迭代計(jì)算-6M+12x1x2x3x4x5xCj

zj0–2M-53M+300

zj-cj3-2M3M+30-M3500-M

10100020100[2]-301bθ整理課件大M法迭代運(yùn)算x1x2x3x4x5xCj

zj00-4.502.5+M

zj-cj35-4.502.53500-M

101000031-101-1.500.5bθ27整理課件大M法迭代計(jì)算x1x2x3x4x5xCj

zj0001.5M+1

zj-cj3501.513500-M

100-1/31/30011/3-1/30101/20bθ36整理課件大M法大于等于約束條件當(dāng)出現(xiàn)大于等于約束條件時(shí)，首先添加一個(gè)剩余變量，使約束條件變?yōu)榈仁郊s束，然后再添加一個(gè)人工變量，用大M法求解。常數(shù)項(xiàng)為負(fù)數(shù)時(shí)，先在等式兩邊同乘-1，使資源變量變?yōu)檎龜?shù)，然后再根據(jù)相應(yīng)情況進(jìn)行處理。整理課件趣味數(shù)學(xué)這是基諾未能想出來(lái)的又一個(gè)悖論。一條蠕蟲(chóng)在橡皮繩的一端。橡皮繩長(zhǎng)一公里。蠕蟲(chóng)以每秒1厘米的穩(wěn)定速度沿橡皮繩爬行。在1秒鐘之后，橡皮繩就像橡皮筋一樣拉長(zhǎng)為2公里。再過(guò)一秒鐘后，它又拉長(zhǎng)為3公里，如此下去。蠕蟲(chóng)最后究竟會(huì)不會(huì)到達(dá)終點(diǎn)呢？整理課件作業(yè)將本問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)形，并列出初始單純形表。整理課件作業(yè)求解線性規(guī)劃問(wèn)題：整理課件第二章對(duì)偶理論和靈敏度分析整理課件本章內(nèi)容對(duì)偶問(wèn)題的提出原問(wèn)題與對(duì)偶問(wèn)題原問(wèn)題與對(duì)偶問(wèn)題的轉(zhuǎn)化影子價(jià)格對(duì)偶問(wèn)題的求解靈敏度分析整理課件對(duì)偶問(wèn)題的提出對(duì)偶現(xiàn)象無(wú)論是從理論還是實(shí)踐，對(duì)偶問(wèn)題是線性規(guī)劃最重要和最有趣的概念和理論刻劃四邊形面積與周長(zhǎng)之間的關(guān)系周長(zhǎng)一定的四邊形中，面積為最大面積一定的四邊形中，周長(zhǎng)為最小一種現(xiàn)象的兩種提法線性規(guī)劃問(wèn)題原問(wèn)題：求目標(biāo)最大對(duì)偶問(wèn)題：求目標(biāo)最小整理課件對(duì)偶問(wèn)題的提出例1美佳公司方案制造Ⅰ、Ⅱ兩種家電產(chǎn)品的生產(chǎn)，生產(chǎn)單位產(chǎn)品所需的設(shè)備A、B、C臺(tái)時(shí)如下。該公司每生產(chǎn)一單位產(chǎn)品Ⅰ、Ⅱ可獲利50元、100元。問(wèn)：如何到達(dá)利潤(rùn)最大？ⅠⅡ資源限制設(shè)備A設(shè)備B設(shè)備C120111300臺(tái)時(shí)400臺(tái)時(shí)250臺(tái)時(shí)整理課件對(duì)偶問(wèn)題的提出例1的決策問(wèn)題：生產(chǎn)多少個(gè)Ⅰ產(chǎn)品和Ⅱ產(chǎn)品才能使利潤(rùn)到達(dá)最大設(shè)決策變量x1為生產(chǎn)Ⅰ產(chǎn)品的數(shù)量，x2為生產(chǎn)Ⅱ產(chǎn)品的數(shù)量最大利潤(rùn)：maxz=50x1+100x2約束條件：x1+x2≤3002x1+x2≤400x2≤250x1，x2≥0整理課件對(duì)偶問(wèn)題的提出生產(chǎn)產(chǎn)品，創(chuàng)造最大利潤(rùn)？出賃設(shè)備，確定合理租金？出賃設(shè)備總租金不應(yīng)低于原利潤(rùn)全部設(shè)備的總租金越低越好整理課件對(duì)偶問(wèn)題的提出設(shè)決策變量

y1,y2,y3為設(shè)備A、B、C每臺(tái)時(shí)的租金最小租金：minf=300y1+400y2+250y3

整理課件原問(wèn)題與對(duì)偶問(wèn)題原問(wèn)題某企業(yè)有m種資源，生產(chǎn)n種產(chǎn)品各種資源的擁有量為bi,xj為產(chǎn)量,aij為生產(chǎn)第j種產(chǎn)品所消耗第i種資源的數(shù)量，cj為產(chǎn)值整理課件原問(wèn)題與對(duì)偶問(wèn)題對(duì)偶問(wèn)題出讓資源，獲取回報(bào)，付出代價(jià)條件：同等數(shù)量資源出讓的代價(jià)應(yīng)不低于組織生產(chǎn)的產(chǎn)值yi出讓第i種資源付出的代價(jià)整理課件原問(wèn)題與對(duì)偶問(wèn)題兩者的關(guān)系原問(wèn)題對(duì)偶問(wèn)題目標(biāo)函數(shù)求最大約束條件的右端目標(biāo)函數(shù)系數(shù)約束條件“≤”約束條件的行約束條件的列約束條件的個(gè)數(shù)原問(wèn)題變量的個(gè)數(shù)目標(biāo)函數(shù)求最小目標(biāo)函數(shù)系數(shù)約束條件的右端約束條件“≥”約束條件的列約束條件的行對(duì)偶變量的個(gè)數(shù)約束條件的個(gè)數(shù)整理課件原問(wèn)題與對(duì)偶問(wèn)題的轉(zhuǎn)化例2.寫(xiě)出以下問(wèn)題的對(duì)偶問(wèn)題及對(duì)偶的對(duì)偶問(wèn)題整理課件原問(wèn)題與對(duì)偶問(wèn)題的轉(zhuǎn)化對(duì)偶問(wèn)題對(duì)偶的對(duì)偶問(wèn)題整理課件原問(wèn)題與對(duì)偶問(wèn)題的轉(zhuǎn)化原問(wèn)題非對(duì)稱形式原問(wèn)題對(duì)稱形式對(duì)偶問(wèn)題目標(biāo)函數(shù)求最小等式約束xj

≤0xj

取值無(wú)約束整理課件原問(wèn)題與對(duì)偶問(wèn)題的轉(zhuǎn)化例3寫(xiě)出下述線性規(guī)劃的對(duì)偶問(wèn)題整理課件原問(wèn)題與對(duì)偶問(wèn)題的轉(zhuǎn)化對(duì)偶問(wèn)題整理課件影子價(jià)格原問(wèn)題與對(duì)偶問(wèn)題的重要性質(zhì)Yi對(duì)一個(gè)第i種資源的估價(jià)，不是資源的市場(chǎng)價(jià)格是企業(yè)根據(jù)資源在生產(chǎn)中作出的奉獻(xiàn)的估價(jià)影子價(jià)格：對(duì)資源在生產(chǎn)中作出的奉獻(xiàn)的估價(jià)對(duì)偶變量Yi單位資源在最優(yōu)利用條件下所產(chǎn)生的經(jīng)濟(jì)效果特征影子價(jià)格依賴于資源利用情況，是未知量。隨生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)情況變化。整理課件影子價(jià)格一種邊際價(jià)格：yi的值相當(dāng)于在給定的生產(chǎn)條件下，bi每增加一個(gè)單位時(shí)，目標(biāo)函數(shù)z的增加量一種時(shí)機(jī)本錢當(dāng)市場(chǎng)價(jià)格低于影子價(jià)格時(shí)，購(gòu)進(jìn)資源，增加生產(chǎn)，提高利潤(rùn)當(dāng)市場(chǎng)價(jià)格高于影子價(jià)格時(shí)，出售資源，提高利潤(rùn)隨著影子價(jià)格的買進(jìn)和賣出，影子價(jià)格隨之變動(dòng)，直到影子價(jià)格與市場(chǎng)價(jià)格保持同等水平，才處于平衡整理課件影子價(jià)格線性規(guī)劃的原問(wèn)題是確定資源的最優(yōu)分配方案，而對(duì)偶問(wèn)題是確定對(duì)資源的恰當(dāng)評(píng)估大公司借助資源的影子價(jià)格確定一些內(nèi)部結(jié)算價(jià)格，以控制資源的使用和考核下屬企業(yè)的經(jīng)營(yíng)狀況在社會(huì)資源的有效配置中，可借助影子價(jià)格規(guī)定使用最緊缺資源一個(gè)單位必須上繳的利潤(rùn)額，以控制一些效益低的企業(yè)自覺(jué)節(jié)約使用緊缺資源整理課件對(duì)偶問(wèn)題的求解利用原問(wèn)題單純形法確定初始基可行解轉(zhuǎn)換為新基可行解建立最優(yōu)解判斷準(zhǔn)那么整理課件例4.求對(duì)偶問(wèn)題的解對(duì)偶問(wèn)題的求解整理課件對(duì)偶問(wèn)題的求解用單純形法解，添加兩個(gè)剩余變量，兩個(gè)人工變量，用大M法求解。非常麻煩，運(yùn)算量比較大。當(dāng)約束條件個(gè)數(shù)很多時(shí)，計(jì)算量成倍增加。整理課件對(duì)偶問(wèn)題的性質(zhì)弱對(duì)偶性，如果X，Y分別是原問(wèn)題和對(duì)偶問(wèn)題的可行解，那么存在：CX≤YB對(duì)偶定理：假設(shè)原問(wèn)題有最優(yōu)解，那么對(duì)偶問(wèn)題也有最優(yōu)解，且目標(biāo)函數(shù)值相等。解的互補(bǔ)松弛性：原問(wèn)題的基變量對(duì)應(yīng)于對(duì)偶問(wèn)題的松弛變量的檢驗(yàn)數(shù)，原問(wèn)題的松弛變量對(duì)應(yīng)于對(duì)偶問(wèn)題的基變量的檢驗(yàn)數(shù)。整理課件對(duì)偶單純形法根本思想:在保持對(duì)偶問(wèn)題為可行解的根底上,逐步迭代,減小目標(biāo)值,當(dāng)原問(wèn)題也到達(dá)可行解時(shí),得到了目標(biāo)函數(shù)的最小值對(duì)偶問(wèn)題的求解cjc1…

cm…

cj…

cn基CBx1…

xm…

xj…

xn

b

………………

j=

zj-

cj0

…

0

…

…

整理課件對(duì)偶問(wèn)題的求解步驟1：根據(jù)線性規(guī)劃問(wèn)題，列出初始單純形表，檢查b列數(shù)字，假設(shè)都為非負(fù)，檢驗(yàn)數(shù)也均為非負(fù)，那么已經(jīng)得到最優(yōu)解。否那么轉(zhuǎn)步驟2。步驟2：確定換出變量，選擇最負(fù)的基變量為換出變量。步驟3：確定換入變量，如果換出變量對(duì)應(yīng)的行系數(shù)全部非負(fù)，那么無(wú)可行解。否那么，用換出變量那一行具有負(fù)值的系數(shù)分別去除同列的檢驗(yàn)數(shù)，取絕對(duì)值最小者對(duì)應(yīng)的變量為換入變量。整理課件對(duì)偶問(wèn)題的求解步驟4：以換入變量對(duì)應(yīng)的行和換出變量對(duì)應(yīng)的列交點(diǎn)對(duì)應(yīng)的元素做為主元素，進(jìn)行迭代運(yùn)算，得到新的單純形表。步驟5：最優(yōu)性檢驗(yàn)，如果b列元素和檢驗(yàn)數(shù)全部為非負(fù)，那么已得到最優(yōu)解，否那么轉(zhuǎn)步驟2。整理課件對(duì)偶單純形法步驟1：轉(zhuǎn)換并列出初始單純形表整理課件對(duì)偶單純形法:初始單純形表by1y2y3y4y5YCj

zj30040025000

zj-cj000000-300-400-25000-1-2010-1-1-101b列系數(shù)為負(fù)，檢驗(yàn)數(shù)為正，說(shuō)明原問(wèn)題為可行解，而對(duì)偶問(wèn)題為不可行解。轉(zhuǎn)步驟2。整理課件對(duì)偶單純形法:確定換入換出變量y1y2y3y4y5YCj

zj30040025000

zj-cj000000-300-400-25000-1-2010-1-1[-1]01選b列系數(shù)最負(fù)的值為換出變量，用換出變量那一行具有負(fù)值的系數(shù)分別去除同列的檢驗(yàn)數(shù)，取絕對(duì)值最小者對(duì)應(yīng)的變量為換入變量，轉(zhuǎn)步驟4。b整理課件對(duì)偶單純形法:迭代運(yùn)算y1y2y3y4y5YCj

zj5015000250

zj-cj-250-250-2500250-25000-300-400-25000-1-20101110-1以換入變量對(duì)應(yīng)的行和換出變量對(duì)應(yīng)的列交點(diǎn)對(duì)應(yīng)的元素做為主元素，進(jìn)行迭代運(yùn)算，得到新的單純形表。b列系數(shù)仍存在負(fù)數(shù)，轉(zhuǎn)步驟2。b整理課件對(duì)偶單純形法:確定換入換出變量y1y2y3y4y5YCj

zj5015000250

zj-cj-250-250-2500250-25000-300-400-25000[-1]-20101110-1以換入變量對(duì)應(yīng)的行和換出變量對(duì)應(yīng)的列交點(diǎn)對(duì)應(yīng)的元素做為主元素，進(jìn)行迭代運(yùn)算，得到新的單純形表。b列系數(shù)仍存在負(fù)數(shù)，轉(zhuǎn)步驟2。b整理課件對(duì)偶單純形法:迭代運(yùn)算y1y2y3y4y5YCj

zj050050250

zj-cj-300-350-25050250-27500-300-400-25000

120-100-111-1以第一行和第一列交點(diǎn)對(duì)應(yīng)的元素做為主元素，進(jìn)行迭代運(yùn)算，得到新的單純形表。b列系數(shù)全部非負(fù)，檢驗(yàn)數(shù)也全部非負(fù)，已求得最優(yōu)解。b整理課件對(duì)偶單純形法：解的說(shuō)明Y=〔50,0,50,0,0〕，-f=-27500即f=27500。與原問(wèn)題比較可以看到，y1,y3恰好是原問(wèn)題第一、第三個(gè)約束條件的松弛變量。檢驗(yàn)數(shù)恰好是原問(wèn)題的解。這就是所謂的互補(bǔ)松弛性。原問(wèn)題與對(duì)偶問(wèn)題的最優(yōu)解相同。整理課件對(duì)偶單純形法例5.求對(duì)偶問(wèn)題的解整理課件對(duì)偶單純形法例5的最終單純形表如下：y1y2y3y4y5YCj

zj001.81.60.2

zj-cj-2-3-2.21.60.2-5.6-2-3-40001-0.2-0.40.2101.4-0.2-0.4b整理課件對(duì)偶單純形法初始解可以是非可行解，當(dāng)檢驗(yàn)數(shù)都為負(fù)數(shù)時(shí)，就可以進(jìn)行基的變換，這時(shí)不需要參加人工變量，可以簡(jiǎn)化計(jì)算。當(dāng)變量多于約束條件時(shí)，用對(duì)偶單純形法可以減少計(jì)算工作量，因此對(duì)變量較少，而約束條件很多的線性規(guī)劃問(wèn)題，可先轉(zhuǎn)化為對(duì)偶問(wèn)題，然后用對(duì)偶單純形法求解。在靈敏度分析中，有時(shí)需要用對(duì)偶單純形法，這樣可以使問(wèn)題簡(jiǎn)化。整理課件對(duì)偶單純形法：作業(yè)1、什么是資源的影子價(jià)格，同相應(yīng)的市場(chǎng)價(jià)格之間有何區(qū)別，研究影子價(jià)格的意義何在。2、試述對(duì)偶單純形法的計(jì)算步驟，它的優(yōu)點(diǎn)及應(yīng)用上的局限性。3、寫(xiě)出線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題：整理課件對(duì)偶單純形法：作業(yè)用對(duì)偶單純形法求解以下問(wèn)題：整理課件靈敏度分析由于市場(chǎng)條件、工藝條件以及企業(yè)規(guī)模的變化，價(jià)值系數(shù)、資源向量、技術(shù)系數(shù)等都會(huì)發(fā)生變化。提出兩個(gè)問(wèn)題：一、當(dāng)這些系數(shù)有一個(gè)或幾個(gè)發(fā)生變化時(shí)，最優(yōu)解會(huì)發(fā)生變化；二、這些系數(shù)在什么范圍內(nèi)變化時(shí)，線性規(guī)劃問(wèn)題的最優(yōu)解不變。如果每有參數(shù)發(fā)生變化就重新構(gòu)建模型計(jì)算，太麻煩，也沒(méi)有必要?？梢园寻l(fā)生變化的個(gè)別系數(shù)，經(jīng)過(guò)一定計(jì)算后直接填入最終計(jì)算表中，進(jìn)行分析。整理課件靈敏度分析價(jià)值系數(shù)的靈敏度分析資源向量的靈敏度分析約束方程系數(shù)矩陣的靈敏度分析決策變量增減的靈敏度分析約束條件增減的靈敏度分析整理課件價(jià)值系數(shù)的靈敏度分析某工廠在方案期間內(nèi)生產(chǎn)1、2、3三種產(chǎn)品，生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗，如下表所示：123設(shè)備1228臺(tái)時(shí)原料A40816Kg原料B04012Kg1、2、3每單位產(chǎn)品分別可以獲利2元，3元，a元，求如何安排生產(chǎn)可以使工廠利潤(rùn)最大。整理課件價(jià)值系數(shù)的靈敏度分析線性規(guī)劃問(wèn)題：?jiǎn)?，?dāng)a=1，2，3，5時(shí)，最優(yōu)解分別為多少，最優(yōu)基分別為那些變量。整理課件價(jià)值系數(shù)的靈敏度分析當(dāng)a=1時(shí)，最終單純形表如下：x1x2x3x4x5x6xCj

zj0031.50.1250

zj-cj2341.50.125023100010200.250000-20.510100.5-0.1250bθ14整理課件價(jià)值系數(shù)的靈敏度分析當(dāng)a=2時(shí)，最終單純形表如下：x1x2x3x4x5x6xCj

zj0021.50.1250

zj-cj2341.50.125023200010200.250000-20.510100.5-0.1250bθ14整理課件價(jià)值系數(shù)的靈敏度分析當(dāng)a=3時(shí)，最終單純形表如下：x1x2x3x4x5x6xCj

zj0011.50.1250

zj-cj2341.50.125023300010200.250000-20.510100.5-0.1250bθ14整理課件價(jià)值系數(shù)的靈敏度分析當(dāng)a=5時(shí)，最終單純形表如下：x1x2x3x4x5x6xCj

zj0.5001.50.250

zj-cj2.5351.50.2502350000100.5-0.12500.50100.1250000-20.51bθ16整理課件價(jià)值系數(shù)的靈敏度分析當(dāng)a=1，2，3時(shí)，zj-cj≥0，最終單純形表根本沒(méi)有改變，最優(yōu)解沒(méi)有改變，僅有x3的檢驗(yàn)數(shù)有所不同。當(dāng)a=5時(shí)，zj-cj≤0，最優(yōu)基改變，最終單純形表也發(fā)生改變。當(dāng)最優(yōu)基發(fā)生變化時(shí)，事實(shí)上我們不必重新進(jìn)行全部計(jì)算，只需要在原來(lái)最終單純形表的根底上繼續(xù)迭代就可以得到最優(yōu)解。整理課件價(jià)值系數(shù)的靈敏度分析當(dāng)a由3變?yōu)?時(shí)：x1x2x3x4x5x6xCj

zj00-11.50.1250

zj-cj2341.50.125023500010[2]00.250000-20.510100.5-0.1250bθ14整理課件價(jià)值系數(shù)的靈敏度分析從上圖中看到，檢驗(yàn)數(shù)仍存在負(fù)數(shù)，繼續(xù)迭代。x1x2x3x4x5x6xCj

zj0.5001.50.250

zj-cj2.5351.50.2502350000.50100.1250000-20.510100.5-0.1250bθ16整理課件價(jià)值系數(shù)的靈敏度分析非基變量?jī)r(jià)值系數(shù)變化價(jià)值系數(shù)不在基變量中，zj保持不變，所以檢驗(yàn)數(shù)zj-cj變化Δcj〔為正數(shù)〕，要保持最優(yōu)解不變，只要Δcj≤zj-cj?；兞?jī)r(jià)值系數(shù)變化基變量?jī)r(jià)值系數(shù)發(fā)生變化時(shí)，只需將新的價(jià)值系數(shù)代入最終單純形表中，檢查檢驗(yàn)數(shù)，如果檢驗(yàn)數(shù)仍保持為正，那么最優(yōu)基不變，但最優(yōu)解的值會(huì)發(fā)生變化。如果檢驗(yàn)數(shù)出現(xiàn)負(fù)數(shù)，那么以原最終單純形表為根底，繼續(xù)進(jìn)行迭代運(yùn)算。整理課件資源向量的靈敏度分析單純形法的實(shí)質(zhì)是找到一個(gè)能得到最優(yōu)解的基xB，在約束條件中用其系數(shù)矩陣左乘一個(gè)B-1，令非基變量為0，得到最優(yōu)解向量xB=B-1b。事實(shí)上迭代過(guò)程也是用矩陣初等變換求B的逆矩陣B-1的過(guò)程。最終單純形表中的b列其實(shí)就是B-1b，當(dāng)?shù)趉個(gè)資源向量bk變?yōu)閎k+Δbk時(shí)，也就是原來(lái)單純形表中的b向量變成了b’向量。整理課件資源向量的靈敏度分析令Δb=(0,0,…Δbk,…0)T，那么有b’=b+Δb，這樣最終單純形表中基變量xB的解就變成了xB’=B-1(b+Δb〕=B-1b+B-1Δb。要使xB仍然為最優(yōu)解，只要B-1b+B-1Δb>0即可。如果bk的變化使得B-1b+B-1Δb<0，這時(shí)最優(yōu)解的基就要發(fā)生變化，這種情況下用對(duì)偶單純形法繼續(xù)求出新的最優(yōu)解。整理課件資源向量的靈敏度分析例：課本P6例1-1中，如果鋼材的供給數(shù)量發(fā)生變化，請(qǐng)問(wèn)1、鋼材供給量在什么范圍內(nèi)變化時(shí)，最優(yōu)基不會(huì)發(fā)生改變？2、當(dāng)鋼材的供給量增加到2200噸時(shí)，應(yīng)當(dāng)如何安排生產(chǎn)方案？整理課件資源向量的靈敏度分析如果例1-1中的鋼材供給數(shù)量變?yōu)?600+Δb1，最終解將變?yōu)椋簒B’=B-1b’=B-1(b+Δb〕=

=整理課件資源向量的靈敏度分析要保證最優(yōu)基不改變，要求b’中所有向量大于等于0，即：從〔1〕式中可得：Δb1≥-400，從〔2〕式中可得：Δb1≥-600，從〔3〕式中可得：Δb1≤400，得到-400≤Δb1≤400，也就是說(shuō)，鋼材供給量在1200到2000之間時(shí)，最優(yōu)基不發(fā)生變化。整理課件資源向量的靈敏度分析資源向量在一定范圍內(nèi)變化時(shí)，最優(yōu)基雖然不會(huì)發(fā)生變化，但最優(yōu)解那么會(huì)發(fā)生變化。最優(yōu)基不變時(shí)，可以直接將發(fā)生變化的資源向量代入B-1b’中，得到新的最優(yōu)解的值。例如，當(dāng)鋼材供給量變?yōu)?000時(shí)，新的最優(yōu)解的求解如下：整理課件資源向量的靈敏度分析整理課件資源向量的靈敏度分析當(dāng)鋼材的供給量增加到2200噸時(shí)：資源向量出現(xiàn)負(fù)數(shù)，不再是可行解，需要繼續(xù)迭代，用對(duì)偶單純形法。整理課件資源向量的靈敏度分析最終單純形表變?yōu)椋簒1x2x3x4x5xCj

zj0010.40

zj-cj4310.4043000000.5-0.4101

1-0.40

10[-0.5]0.40b3200整理課件資源向量的靈敏度分析以主元素為中心進(jìn)行迭代運(yùn)算：x1x2x3x4x5xCj

zj2001.20

zj-cj6321.20430001000121

00.40

-201-0.80b3000整理課件趣味數(shù)學(xué)一個(gè)富有的律師擁有11輛古董汽車，每輛值5000美元。律師死時(shí)留下了一個(gè)奇怪的遺囑。他說(shuō)他的11輛古董汽車分給他的三個(gè)兒子。把其中的一半分給長(zhǎng)子，1/4分給次子，1/6分給小兒子。同時(shí)規(guī)定不能把車賣掉。律師去世后，兒子為了這個(gè)遺囑爭(zhēng)論不休，這時(shí)一個(gè)數(shù)學(xué)家開(kāi)了一輛汽車來(lái)悼念老朋友。三個(gè)兒子把他們的難題告訴了數(shù)學(xué)家，數(shù)學(xué)家沉思片刻后說(shuō)，我有方法了。請(qǐng)問(wèn)，他該怎么分配這些汽車？整理課件約束方程系數(shù)矩陣的靈敏度分析從前邊的分析中，我們知道，單純形法的實(shí)質(zhì)是找到一個(gè)能得到最優(yōu)解的基xB，在約束條件中用其系數(shù)矩陣左乘一個(gè)B-1，同時(shí)令非基變量為0，得到最優(yōu)解向量xB=B-1b。從而我們可以得到如下結(jié)論，最終單純形表中xi的系數(shù)列向量pi’

事實(shí)上就是其初始系數(shù)列向量pi左乘以B-1，既pi’=B-1pi。根據(jù)以上分析，我們可以得到約束方程技術(shù)系數(shù)變化時(shí)靈敏度分析的方法。整理課件約束方程系數(shù)矩陣的靈敏度分析例如，在例1-1中，列向量x4的系數(shù)列向量(用p4表示〕在最終單純形表中為〔用p4’表示〕：整理課件約束方程系數(shù)矩陣的靈敏度分析根據(jù)以上分析我們可以得到系數(shù)矩陣靈敏度分析的思路。當(dāng)基變量系數(shù)列向量改變時(shí)，用初始系數(shù)列向量左乘以B-1后代入原最終單純形表，在新的單純形表中繼續(xù)進(jìn)行運(yùn)算，得到最優(yōu)解。當(dāng)新參加決策變量時(shí)，意味著約束方程組中增加了列向量，將這個(gè)列向量左乘以B-1后添加到原最終單純形表中，繼續(xù)運(yùn)算得到最優(yōu)解。整理課件約束方程系數(shù)矩陣的靈敏度分析在例1-1，為了增加平安性，當(dāng)每輛大轎車使用鋼材由2噸變?yōu)?噸時(shí)，求最優(yōu)解有什么變化？工廠具備了生產(chǎn)旅行車的技術(shù)，每輛旅行車用鋼材1.5噸，工時(shí)1.25小時(shí)，座椅0.25套，利潤(rùn)為每輛3千元，問(wèn)該不該投產(chǎn)，如果投產(chǎn)有利可圖，應(yīng)該如何安排新的生產(chǎn)方案？整理課件約束方程系數(shù)矩陣的靈敏度分析當(dāng)大轎車使用鋼材變?yōu)?噸時(shí)，x1在最終單純形表中的系數(shù)列向量變?yōu)椋赫碚n件約束方程系數(shù)矩陣的靈敏度分析最終單純形表變?yōu)椋簒1x2x3x4x5xCj

zj

zj-cj430000.500.5-0.4111

1-0.400.50-0.50.40b整理課件約束方程系數(shù)矩陣的靈敏度分析由于x1對(duì)應(yīng)的列向量尚未化為單位向量，先進(jìn)行迭代運(yùn)算：x1x2x3x4x5xCj

zj002-0.40

zj-cj43000001-0.8101

2-1.2010-1[0.8]0b432-0.40θ1800整理課件約束方程系數(shù)矩陣的靈敏度分析檢驗(yàn)數(shù)仍然有負(fù)數(shù)，繼續(xù)迭代：x1x2x3x4x5xCj

zj0.501.500

zj-cj43000101011.51

0.5001.250-1.2510b4.531.500θ2400整理課件約束方程系數(shù)矩陣的靈敏度分析第二問(wèn)，新增加一種產(chǎn)品，模型中增加了一個(gè)新列，設(shè)新產(chǎn)品產(chǎn)量為x6，增加的系數(shù)列向量在最終單純形表中變?yōu)椋赫碚n件約束方程系數(shù)矩陣的靈敏度分析最終單純形表變?yōu)椋簒1x2x3x4x5x6xCj

zj0010.40-1

zj-cj430003001-0.41[0.5]01

0.5-0.40110-0.50.40-0.25b4310.402θ2600整理課件約束方程系數(shù)矩陣的靈敏度分析檢驗(yàn)數(shù)中存在負(fù)數(shù)，繼續(xù)迭代：x1x2x3x4x5x6xCj

zj002-0.420

zj-cj430003001-0.82101

0[0.4]-2010-0.250.20.50b432-0.423θ3000整理課件約束方程系數(shù)矩陣的靈敏度分析仍不是最優(yōu)解，繼續(xù)運(yùn)算：x1x2x3x4x5x6xCj

zj012000

zj-cj4300030210-2102.5

01-501-0.5-0.2501.50b442003θ3200整理課件約束方程系數(shù)矩陣的靈敏度分析求得最優(yōu)解為：x1=200，x2=0，x3=0，x4=500，x5=0，x6=800，Z=3200?？梢?jiàn)，生產(chǎn)旅行車是有利可圖的，新的生產(chǎn)方案為：生產(chǎn)大轎車200輛，生產(chǎn)旅行車800輛，剩余工時(shí)500小時(shí)，利潤(rùn)為3200千元。

整理課件靈敏度分析小結(jié)價(jià)值系數(shù)發(fā)生變化時(shí)：1、如果是非基變量的系數(shù)發(fā)生變化，那么只要該變量對(duì)應(yīng)的檢驗(yàn)數(shù)zj-cj在cj變化后仍然大于等于0，那么最優(yōu)解不發(fā)生任何變化。2、如果是基變量的價(jià)值系數(shù)發(fā)生變化，那么需要重新計(jì)算所有檢驗(yàn)數(shù)，如果所有檢驗(yàn)數(shù)仍然保持大于等于0，那么最優(yōu)基不變，但最優(yōu)解一般會(huì)發(fā)生變化。如果有檢驗(yàn)數(shù)變?yōu)樨?fù)數(shù)，那么在原最終單純形表中繼續(xù)迭代，求出最優(yōu)解。整理課件靈敏度分析小結(jié)當(dāng)資源向量發(fā)生改變時(shí)，用公式xB’=B-1b+B-1Δb=xB+B-1Δb〔其中Δb=(0,0,…Δbk,…0)T〕計(jì)算新的b列的值，如果新的b列的值仍然全部大于等于0，那么最優(yōu)基不變，但最優(yōu)解的值一般會(huì)發(fā)生變化。如果計(jì)算出來(lái)的新的b列的值出現(xiàn)負(fù)數(shù)，那么說(shuō)明該解是不可行解，用對(duì)偶單純形法繼續(xù)進(jìn)行迭代運(yùn)算，求出新的最優(yōu)解。整理課件靈敏度分析小結(jié)當(dāng)基變量技術(shù)系數(shù)發(fā)生變化時(shí)，求出用公式pi’=B-1pi求出發(fā)生變化的系數(shù)所在列的數(shù)值，代替最終單純形表中原來(lái)的列。然后用高斯消元法將該列化為單位向量，計(jì)算新的檢驗(yàn)數(shù)。1、如果檢驗(yàn)數(shù)不為負(fù)數(shù)，那么最優(yōu)基不變。2、如果新的檢驗(yàn)數(shù)變?yōu)樨?fù)數(shù)，那么最優(yōu)基將發(fā)生變化，用單純形法繼續(xù)迭代，求出新的最優(yōu)解。整理課件趣味數(shù)學(xué)你作為幸運(yùn)觀眾參加了一個(gè)節(jié)目，節(jié)目中你面對(duì)三個(gè)門，其中一個(gè)門后一輛汽車，另外兩個(gè)門后各有一只羊。主持人請(qǐng)你選擇一扇門，門后的物品將做為你的獎(jiǎng)品。當(dāng)你選擇后，主持人先不翻開(kāi)門，而是翻開(kāi)一扇門后有羊的門，然后問(wèn)你改變不改變你的選擇，請(qǐng)問(wèn)，你該不該改變你的選擇？整理課件作業(yè)某公司制作三種產(chǎn)品A、B、C，需要?jiǎng)趧?dòng)力和原材料兩種資源，要求制訂生產(chǎn)方案使總利潤(rùn)最大化。三種產(chǎn)品所需的資源和產(chǎn)生的利潤(rùn)如下表所示：ABC資源勞動(dòng)力63545原材料34530利潤(rùn)315整理課件作業(yè)1、請(qǐng)建立模型，解決最優(yōu)生產(chǎn)方案問(wèn)題。2、求出使得最優(yōu)解不變的產(chǎn)品A的單位利潤(rùn)變動(dòng)范圍，問(wèn)A產(chǎn)品的利潤(rùn)變?yōu)?時(shí)最優(yōu)解變不變？3、假定原材料的市場(chǎng)價(jià)格是10元每單位，可以購(gòu)置15個(gè)單位，問(wèn)以10元的價(jià)格采購(gòu)15單位原材料是否合算？4、請(qǐng)問(wèn)原材料的供給在什么范圍內(nèi)變化時(shí)，不必改變生產(chǎn)方案？整理課件作業(yè)5、廠家研制出了一種新產(chǎn)品D，生產(chǎn)一單位D需要?jiǎng)趧?dòng)力4單位，原材料3單位，而每單位的新產(chǎn)品D的利潤(rùn)為3元。請(qǐng)問(wèn)：生產(chǎn)方案是否需要修改？為什么？該如何修改？整理課件第三章運(yùn)輸問(wèn)題整理課件主要內(nèi)容運(yùn)輸問(wèn)題的背景運(yùn)輸問(wèn)題的模型運(yùn)輸問(wèn)題的表上作業(yè)法運(yùn)輸問(wèn)題的應(yīng)用整理課件運(yùn)輸問(wèn)題的背景在經(jīng)濟(jì)建設(shè)中，經(jīng)常碰到大宗物資調(diào)運(yùn)問(wèn)題，如煤炭、鋼鐵、糧食等等。主產(chǎn)區(qū)和主銷區(qū)往往不同，需要大規(guī)模的調(diào)運(yùn)，將物資從產(chǎn)地供給到銷地。大型企業(yè)有多個(gè)生產(chǎn)基地，銷售普及全國(guó)乃至全世界，