運(yùn)籌學(xué)PPT完整版.ppt

運(yùn)籌學(xué)(OperationsResearch),經(jīng)濟(jì)學(xué)核心課程,緒論,（1）運(yùn)籌學(xué)簡(jiǎn)述（2）運(yùn)籌學(xué)的主要內(nèi)容（3）本課程的教材及參考書(shū)（4）本課程的特點(diǎn)和要求（5）本課程授課方式與考核（6）運(yùn)籌學(xué)在工商管理中的應(yīng)用,本章主要內(nèi)容：,運(yùn)籌學(xué)簡(jiǎn)述,運(yùn)籌學(xué)（OperationsResearch）系統(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é)的歷史,“運(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é)的主要內(nèi)容,數(shù)學(xué)規(guī)劃（線性規(guī)劃、整數(shù)規(guī)劃、目標(biāo)規(guī)劃、動(dòng)態(tài)規(guī)劃等）圖論存儲(chǔ)論排隊(duì)論對(duì)策論排序與統(tǒng)籌方法決策分析,本課程的教材及參考書(shū),選用教材運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用胡運(yùn)權(quán)主編哈工大出版社參考教材運(yùn)籌學(xué)教程胡運(yùn)權(quán)主編（第2版）清華出版社管理運(yùn)籌學(xué)韓伯棠主編（第2版）高等教育出版社運(yùn)籌學(xué)(修訂版)錢(qián)頌迪主編清華出版社,本課程的特點(diǎn)和要求,先修課：高等數(shù)學(xué)，基礎(chǔ)概率、線性代數(shù)特點(diǎn)：系統(tǒng)整體優(yōu)化；多學(xué)科的配合；模型方法的應(yīng)用運(yùn)籌學(xué)的研究的主要步驟：,本課程授課方式與考核,講授為主，結(jié)合習(xí)題作業(yè),運(yùn)籌學(xué)在工商管理中的應(yīng)用,運(yùn)籌學(xué)在工商管理中的應(yīng)用涉及幾個(gè)方面：生產(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é)在工商管理中的應(yīng)用,Interface上發(fā)表的部分獲獎(jiǎng)項(xiàng)目,“管理運(yùn)籌學(xué)”軟件介紹,“管理運(yùn)籌學(xué)”2.0版包括：線性規(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è)子模塊。,Chapter1線性規(guī)劃(LinearProgramming),LP的數(shù)學(xué)模型圖解法單純形法單純形法的進(jìn)一步討論人工變量法LP模型的應(yīng)用,本章主要內(nèi)容：,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,1.規(guī)劃問(wèn)題,生產(chǎn)和經(jīng)營(yíng)管理中經(jīng)常提出如何合理安排，使人力、物力等各種資源得到充分利用，獲得最大的效益，這就是規(guī)劃問(wè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)最大.）,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,例1.1如圖所示，如何截取x使鐵皮所圍成的容積最大？,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,例1.2某企業(yè)計(jì)劃生產(chǎn)甲、乙兩種產(chǎn)品。這些產(chǎn)品分別要在A、B、C、D、四種不同的設(shè)備上加工。按工藝資料規(guī)定，單件產(chǎn)品在不同設(shè)備上加工所需要的臺(tái)時(shí)如下表所示，企業(yè)決策者應(yīng)如何安排生產(chǎn)計(jì)劃，使企業(yè)總的利潤(rùn)最大？,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,解：設(shè)x1、x2分別為甲、乙兩種產(chǎn)品的產(chǎn)量，則數(shù)學(xué)模型為：,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,2.線性規(guī)劃的數(shù)學(xué)模型由三個(gè)要素構(gòu)成,決策變量Decisionvariables目標(biāo)函數(shù)Objectivefunction約束條件Constraints,其特征是：（1）問(wèn)題的目標(biāo)函數(shù)是多個(gè)決策變量的線性函數(shù)，通常是求最大值或最小值；（2）問(wèn)題的約束條件是一組多個(gè)決策變量的線性不等式或等式。,怎樣辨別一個(gè)模型是線性規(guī)劃模型？,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,目標(biāo)函數(shù)：,約束條件：,3.線性規(guī)劃數(shù)學(xué)模型的一般形式,簡(jiǎn)寫(xiě)為：,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,向量形式：,其中：,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,矩陣形式：,其中：,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,3.線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式,特點(diǎn)：(1)目標(biāo)函數(shù)求最大值（有時(shí)求最小值）(2)約束條件都為等式方程，且右端常數(shù)項(xiàng)bi都大于或等于零(3)決策變量xj為非負(fù)。,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,（2）如何化標(biāo)準(zhǔn)形式,目標(biāo)函數(shù)的轉(zhuǎn)換,如果是求極小值即，則可將目標(biāo)函數(shù)乘以(-1)，可化為求極大值問(wèn)題。,也就是：令，可得到上式。,即,若存在取值無(wú)約束的變量，可令其中：,變量的變換,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。,稱(chēng)為松弛變量,稱(chēng)為剩余變量,變量的變換,可令，顯然,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,例1.3將下列線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式,用替換，且,解:（）因?yàn)閤3無(wú)符號(hào)要求，即x3取正值也可取負(fù)值，標(biāo)準(zhǔn)型中要求變量非負(fù)，所以,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,(2)第一個(gè)約束條件是“”號(hào)，在“”左端加入松馳變量x4，x40,化為等式；(3)第二個(gè)約束條件是“”號(hào)，在“”左端減去剩余變量x5，x50；(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á)到最大值，反之亦然;,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,標(biāo)準(zhǔn)形式如下：,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,4.線性規(guī)劃問(wèn)題的解,線性規(guī)劃問(wèn)題,求解線性規(guī)劃問(wèn)題，就是從滿(mǎn)足約束條件(2)、(3)的方程組中找出一個(gè)解，使目標(biāo)函數(shù)(1)達(dá)到最大值。,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,可行解：滿(mǎn)足約束條件、的解為可行解。所有可行解的集合為可行域。最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大值的可行解?；涸O(shè)A為約束條件的mn階系數(shù)矩陣(m0,40,10,換出行,將3化為1,5/3,1,18,0,1/3,0,1/3,10,1,1/3,30,30,0,5/3,0,4/3,乘以1/3后得到,1,0,3/5,1/5,18,0,1,1/5,2/5,4,0,0,1,1,單純形法的計(jì)算步驟,例1.9用單純形法求解,解：將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式：,不難看出x4、x5可作為初始基變量，列單純形表計(jì)算。,單純形法的計(jì)算步驟,20,x2,2,1/3,1,5,0,1,20,75,3,0,17,1,3,1/3,0,9,0,2,25,60,x1,1,1,0,17/3,1/3,1,25,0,1,28/9,-1/9,2/3,35/3,0,0,-98/9,-1/9,-7/3,單純形法的計(jì)算步驟,學(xué)習(xí)要點(diǎn)：1.線性規(guī)劃解的概念以及3個(gè)基本定理2.熟練掌握單純形法的解題思路及求解步驟,單純形法的進(jìn)一步討論人工變量法,人工變量法：前面討論了在標(biāo)準(zhǔn)型中系數(shù)矩陣有單位矩陣，很容易確定一組基可行解。在實(shí)際問(wèn)題中有些模型并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱(chēng)為人工變量，構(gòu)成的可行基稱(chēng)為人工基，用大M法或兩階段法求解，這種用人工變量作橋梁的求解方法稱(chēng)為人工變量法。,單純形法的進(jìn)一步討論人工變量法,例1.10用大M法解下列線性規(guī)劃,解：首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式,系數(shù)矩陣中不存在單位矩陣，無(wú)法建立初始單純形表。,單純形法的進(jìn)一步討論人工變量法,故人為添加兩個(gè)單位向量，得到人工變量單純形法數(shù)學(xué)模型：,其中：M是一個(gè)很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個(gè)確定數(shù)值；再用前面介紹的單純形法求解該模型，計(jì)算結(jié)果見(jiàn)下表。,單純形法的進(jìn)一步討論人工變量法,單純形法的進(jìn)一步討論人工變量法,解的判別：1）唯一最優(yōu)解判別：最優(yōu)表中所有非基變量的檢驗(yàn)數(shù)非零,則線規(guī)劃具有唯一最優(yōu)解。2）多重最優(yōu)解判別：最優(yōu)表中存在非基變量的檢驗(yàn)數(shù)為零,則線則性規(guī)劃具有多重最優(yōu)解（或無(wú)窮多最優(yōu)解）。3）無(wú)界解判別：某個(gè)k0且aik（i=1，2,m）則線性規(guī)劃具有無(wú)界解。4）無(wú)可行解的判斷：當(dāng)用大M單純形法計(jì)算得到最優(yōu)解并且存在Ri0時(shí)，則表明原線性規(guī)劃無(wú)可行解。5）退化解的判別：存在某個(gè)基變量為零的基本可行解。,單純形法的進(jìn)一步討論人工變量法,單純性法小結(jié):,A,線性規(guī)劃模型的應(yīng)用,一般而言，一個(gè)經(jīng)濟(jì)、管理問(wèn)題凡是滿(mǎn)足以下條件時(shí)，才能建立線性規(guī)劃模型。,要求解問(wèn)題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來(lái)反映，且為線性函數(shù)存在著多種方案要求達(dá)到的目標(biāo)是在一定條件下實(shí)現(xiàn)的，這些約束可用線性等式或不等式描述,線性規(guī)劃在管理中的應(yīng)用,人力資源分配問(wèn)題,例1.11某晝夜服務(wù)的公交線路每天各時(shí)間段內(nèi)所需司機(jī)和乘務(wù)人員人數(shù)如下表所示：,設(shè)司機(jī)和乘務(wù)人員分別在各時(shí)間段開(kāi)始時(shí)上班，并連續(xù)工作8小時(shí)，問(wèn)該公交線路應(yīng)怎樣安排司機(jī)和乘務(wù)人員，即能滿(mǎn)足工作需要，又使配備司機(jī)和乘務(wù)人員的人數(shù)減少?,線性規(guī)劃在管理中的應(yīng)用,解：設(shè)xi表示第i班次時(shí)開(kāi)始上班的司機(jī)和乘務(wù)人員人數(shù)。,此問(wèn)題最優(yōu)解：x150，x220，x350，x40，x520，x610，一共需要司機(jī)和乘務(wù)員150人。,線性規(guī)劃在管理中的應(yīng)用,2.生產(chǎn)計(jì)劃問(wèn)題,某廠生產(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ì)劃，使該廠獲利最大。,線性規(guī)劃在管理中的應(yīng)用,線性規(guī)劃在管理中的應(yīng)用,解：設(shè)xijk表示產(chǎn)品i在工序j的設(shè)備k上加工的數(shù)量。約束條件有：,線性規(guī)劃在管理中的應(yīng)用,目標(biāo)是利潤(rùn)最大化，即利潤(rùn)的計(jì)算公式如下：,帶入數(shù)據(jù)整理得到：,線性規(guī)劃在管理中的應(yīng)用,因此該規(guī)劃問(wèn)題的模型為：,線性規(guī)劃在管理中的應(yīng)用,3.套裁下料問(wèn)題,例：現(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種下料方案以供套裁用。,線性規(guī)劃在管理中的應(yīng)用,設(shè)按方案、下料的原材料根數(shù)分別為xj(j=1，2,3,4)，可列出下面的數(shù)學(xué)模型：,線性規(guī)劃在管理中的應(yīng)用,4.配料問(wèn)題,例：某人每天食用甲、乙兩種食物（如豬肉、雞蛋），其資料如下：?jiǎn)杻煞N食物各食用多少，才能既滿(mǎn)足需要、又使總費(fèi)用最??？,線性規(guī)劃在管理中的應(yīng)用,解：設(shè)Xj表示Bj種食物用量,Chapter2對(duì)偶理論(DualityTheory),線性規(guī)劃的對(duì)偶模型對(duì)偶性質(zhì)對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋影子價(jià)格對(duì)偶單純形法,本章主要內(nèi)容：,線性規(guī)劃的對(duì)偶模型,設(shè)某工廠生產(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ù)表,問(wèn)：充分利用設(shè)備機(jī)時(shí)，工廠應(yīng)生產(chǎn)甲和乙型產(chǎn)品各多少件才能獲得最大利潤(rùn)？,1.對(duì)偶問(wèn)題的現(xiàn)實(shí)來(lái)源,線性規(guī)劃的對(duì)偶模型,解：設(shè)甲、乙型產(chǎn)品各生產(chǎn)x1及x2件，則數(shù)學(xué)模型為：,反過(guò)來(lái)問(wèn)：若廠長(zhǎng)決定不生產(chǎn)甲和乙型產(chǎn)品，決定出租機(jī)器用于接受外加工，只收加工費(fèi)，那么種機(jī)器的機(jī)時(shí)如何定價(jià)才是最佳決策？,線性規(guī)劃的對(duì)偶模型,在市場(chǎng)競(jìng)爭(zhēng)的時(shí)代，廠長(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，則新的線性規(guī)劃數(shù)學(xué)模型為：,線性規(guī)劃的對(duì)偶模型,把同種問(wèn)題的兩種提法所獲得的數(shù)學(xué)模型用表2表示，將會(huì)發(fā)現(xiàn)一個(gè)有趣的現(xiàn)象。,原問(wèn)題與對(duì)偶問(wèn)題對(duì)比表,線性規(guī)劃的對(duì)偶模型,2.原問(wèn)題與對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系,原問(wèn)題（對(duì)偶問(wèn)題）,對(duì)偶問(wèn)題（原問(wèn)題）,線性規(guī)劃的對(duì)偶模型,（1）對(duì)稱(chēng)形式,特點(diǎn)：目標(biāo)函數(shù)求極大值時(shí)，所有約束條件為號(hào)，變量非負(fù);目標(biāo)函數(shù)求極小值時(shí)，所有約束條件為號(hào)，變量非負(fù).,已知P，寫(xiě)出D,線性規(guī)劃的對(duì)偶模型,例2.1寫(xiě)出線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題,解：首先將原問(wèn)題變形為對(duì)稱(chēng)形式,線性規(guī)劃的對(duì)偶模型,線性規(guī)劃的對(duì)偶模型,(2)非對(duì)稱(chēng)型對(duì)偶問(wè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)題。,線性規(guī)劃的對(duì)偶模型,線性規(guī)劃的對(duì)偶模型,例2.2寫(xiě)出下列線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題.,解：原問(wèn)題的對(duì)偶問(wèn)題為,對(duì)偶性質(zhì),例2.3分別求解下列2個(gè)互為對(duì)偶關(guān)系的線性規(guī)劃問(wèn)題,分別用單純形法求解上述2個(gè)規(guī)劃問(wèn)題，得到最終單純形表如下表：,對(duì)偶性質(zhì),原問(wèn)題最優(yōu)表,對(duì)偶問(wèn)題最優(yōu)表,對(duì)偶性質(zhì),原問(wèn)題與其對(duì)偶問(wèn)題的變量與解的對(duì)應(yīng)關(guān)系：在單純形表中，原問(wèn)題的松弛變量對(duì)應(yīng)對(duì)偶問(wèn)題的變量，對(duì)偶問(wèn)題的剩余變量對(duì)應(yīng)原問(wèn)題的變量。,對(duì)偶性質(zhì),性質(zhì)1對(duì)稱(chēng)性定理：對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題,對(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ì),推論3：在一對(duì)對(duì)偶問(wèn)題（P）和（D）中，若一個(gè)可行（如P），而另一個(gè)不可行（如D），則該可行的問(wèn)題目標(biāo)函數(shù)值無(wú)界。,性質(zhì)3最優(yōu)性定理：如果是原問(wèn)題的可行解，是其對(duì)偶問(wèn)題的可行解，并且:,則是原問(wèn)題的最優(yōu)解，是其對(duì)偶問(wèn)題的最優(yōu)解。,對(duì)偶性質(zhì),性質(zhì)4強(qiáng)對(duì)偶性：若原問(wèn)題及其對(duì)偶問(wèn)題均具有可行解，則兩者均具有最優(yōu)解，且它們最優(yōu)解的目標(biāo)函數(shù)值相等。,還可推出另一結(jié)論：若（LP）與（DP）都有可行解，則兩者都有最優(yōu)解，若一個(gè)問(wèn)題無(wú)最優(yōu)解，則另一問(wèn)題也無(wú)最優(yōu)解。,性質(zhì)5互補(bǔ)松弛性：設(shè)X0和Y0分別是P問(wèn)題和D問(wèn)題的可行解，則它們分別是最優(yōu)解的充要條件是：,其中：Xs、Ys為松弛變量,對(duì)偶性質(zhì),性質(zhì)5的應(yīng)用：該性質(zhì)給出了已知一個(gè)問(wèn)題最優(yōu)解求另一個(gè)問(wèn)題最優(yōu)解的方法，即已知Y求X或已知X求Y,互補(bǔ)松弛條件,由于變量都非負(fù)，要使求和式等于零，則必定每一分量為零，因而有下列關(guān)系：若Y0，則Xs必為0；若X0，則Ys必為0利用上述關(guān)系，建立對(duì)偶問(wèn)題（或原問(wèn)題）的約束線性方程組，方程組的解即為最優(yōu)解。,對(duì)偶性質(zhì),例2.4已知線性規(guī)劃,的最優(yōu)解是X=(6,2,0)T,求其對(duì)偶問(wèn)題的最優(yōu)解Y。,解：寫(xiě)出原問(wèn)題的對(duì)偶問(wèn)題，即,標(biāo)準(zhǔn)化,對(duì)偶性質(zhì),設(shè)對(duì)偶問(wèn)題最優(yōu)解為Y(y1，y2),由互補(bǔ)松弛性定理可知，X和Y滿(mǎn)足：,即：,因?yàn)閄10，X20，所以對(duì)偶問(wèn)題的第一、二個(gè)約束的松弛變量等于零，即y30，y40，帶入方程中：,解此線性方程組得y1=1,y2=1,從而對(duì)偶問(wèn)題的最優(yōu)解為：Y=(1,1)，最優(yōu)值w=26。,對(duì)偶性質(zhì),例2.5已知線性規(guī)劃,的對(duì)偶問(wèn)題的最優(yōu)解為Y=(0,-2)，求原問(wèn)題的最優(yōu)解。,解:對(duì)偶問(wèn)題是,標(biāo)準(zhǔn)化,對(duì)偶性質(zhì),設(shè)對(duì)偶問(wèn)題最優(yōu)解為X(x1，x2，x3)T,由互補(bǔ)松弛性定理可知，X和Y滿(mǎn)足：,將Y帶入由方程可知，y3y50，y41。,y2=-20x50又y4=10x20,將x2，x5分別帶入原問(wèn)題約束方程中，得：,解方程組得：x1=-5,x3=-1,所以原問(wèn)題的最優(yōu)解為,X=(-5,0,-1)，最優(yōu)值z(mì)=-12,對(duì)偶性質(zhì),原問(wèn)題與對(duì)偶問(wèn)題解的對(duì)應(yīng)關(guān)系小結(jié),思考題,判斷下列結(jié)論是否正確，如果不正確，應(yīng)該怎樣改正？,1）任何線性規(guī)劃都存在一個(gè)對(duì)應(yīng)的對(duì)偶線性規(guī)劃.2）原問(wèn)題第i個(gè)約束是“”約束，則對(duì)偶變量yi0.3）互為對(duì)偶問(wèn)題，或者同時(shí)都有最優(yōu)解，或者同時(shí)都無(wú)最優(yōu)解.4）對(duì)偶問(wèn)題有可行解，則原問(wèn)題也有可行解.5）原問(wèn)題有多重解，對(duì)偶問(wèn)題也有多重解.6）對(duì)偶問(wèn)題有可行解，原問(wèn)題無(wú)可行解，則對(duì)偶問(wèn)題具有無(wú)界解.7）原問(wèn)題無(wú)最優(yōu)解，則對(duì)偶問(wèn)題無(wú)可行解.8）對(duì)偶問(wèn)題不可行，原問(wèn)題可能無(wú)界解.9）原問(wèn)題與對(duì)偶問(wèn)題都可行，則都有最優(yōu)解.10）原問(wèn)題具有無(wú)界解，則對(duì)偶問(wèn)題不可行.11）對(duì)偶問(wèn)題具有無(wú)界解，則原問(wèn)題無(wú)最優(yōu)解.12）若X*、Y*是原問(wèn)題與對(duì)偶問(wèn)題的最優(yōu)解，則X*=Y*.,對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋影子價(jià)格,1.影子價(jià)格的數(shù)學(xué)分析：,定義：在一對(duì)P和D中，若P的某個(gè)約束條件的右端項(xiàng)常數(shù)bi（第i種資源的擁有量）增加一個(gè)單位時(shí)，所引起目標(biāo)函數(shù)最優(yōu)值z(mì)*的改變量稱(chēng)為第i種資源的影子價(jià)格，其值等于D問(wèn)題中對(duì)偶變量yi*。,由對(duì)偶問(wèn)題得基本性質(zhì)可得：,對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋影子價(jià)格,2.影子價(jià)格的經(jīng)濟(jì)意義1）影子價(jià)格是一種邊際價(jià)格在其它條件不變的情況下，單位資源數(shù)量的變化所引起的目標(biāo)函數(shù)最優(yōu)值的變化。即對(duì)偶變量yi就是第i種資源的影子價(jià)格。即：,對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋影子價(jià)格,2）影子價(jià)格是一種機(jī)會(huì)成本影子價(jià)格是在資源最優(yōu)利用條件下對(duì)單位資源的估價(jià)，這種估價(jià)不是資源實(shí)際的市場(chǎng)價(jià)格。因此，從另一個(gè)角度說(shuō)，它是一種機(jī)會(huì)成本。,若第i種資源的單位市場(chǎng)價(jià)格為mi，則有當(dāng)yi*mi時(shí)，企業(yè)愿意購(gòu)進(jìn)這種資源，單位純利為yi*mi，則有利可圖；如果yi*mi則購(gòu)進(jìn)資源i，可獲單位純利yi*mi若yi*mi則轉(zhuǎn)讓資源i，可獲單位純利miyi,對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋影子價(jià)格,3）影子價(jià)格在資源利用中的應(yīng)用根據(jù)對(duì)偶理論的互補(bǔ)松弛性定理:Y*Xs=0,YsX*=0表明生產(chǎn)過(guò)程中如果某種資源bi未得到充分利用時(shí)，該種資源的影子價(jià)格為0；若當(dāng)資源資源的影子價(jià)格不為0時(shí)，表明該種資源在生產(chǎn)中已耗費(fèi)完。,對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋影子價(jià)格,4）影子價(jià)格對(duì)單純形表計(jì)算的解釋,單純形表中的檢驗(yàn)數(shù),其中cj表示第j種產(chǎn)品的價(jià)格;表示生產(chǎn)該種產(chǎn)品所消耗的各項(xiàng)資源的影子價(jià)格的總和,即產(chǎn)品的隱含成本。,當(dāng)產(chǎn)值大于隱含成本時(shí)，即，表明生產(chǎn)該項(xiàng)產(chǎn)品有利，可在計(jì)劃中安排；否則，用這些資源生產(chǎn)別的產(chǎn)品更有利，不在生產(chǎn)中安排該產(chǎn)品。,對(duì)偶單純形法,對(duì)偶單純形法是求解線性規(guī)劃的另一個(gè)基本方法。它是根據(jù)對(duì)偶原理和單純形法原理而設(shè)計(jì)出來(lái)的，因此稱(chēng)為對(duì)偶單純形法。不要簡(jiǎn)單理解為是求解對(duì)偶問(wèn)題的單純形法。,對(duì)偶單純形法原理,對(duì)偶單純形法基本思路：,找出一個(gè)對(duì)偶問(wèn)題的可行基，保持對(duì)偶問(wèn)題為可行解的條件下，判斷XB是否可行（XB為非負(fù)），若否，通過(guò)變換基解，直到找到原問(wèn)題基可行解（即XB為非負(fù)），這時(shí)原問(wèn)題與對(duì)偶問(wèn)題同時(shí)達(dá)到可行解，由定理4可得最優(yōu)解。,對(duì)偶單純形法,找出一個(gè)DP的可行基,LP是否可行（XB0）,保持DP為可行解情況下轉(zhuǎn)移到LP的另一個(gè)基本解,最優(yōu)解,是,否,循環(huán),結(jié)束,對(duì)偶單純形法,例2.9用對(duì)偶單純形法求解：,解:（1）將模型轉(zhuǎn)化為求最大化問(wèn)題，約束方程化為等式求出一組基本解，因?yàn)閷?duì)偶問(wèn)題可行，即全部檢驗(yàn)數(shù)0（求max問(wèn)題）。,對(duì)偶單純形法,對(duì)偶單純形法,對(duì)偶單純形法,原問(wèn)題的最優(yōu)解為：X*=（2,2,2,0,0,0），Z*=72其對(duì)偶問(wèn)題的最優(yōu)解為：Y*=（1/3,3,7/3），W*=72,對(duì)偶單純形法,對(duì)偶單純形法應(yīng)注意的問(wèn)題：,用對(duì)偶單純形法求解線性規(guī)劃是一種求解方法，而不是去求對(duì)偶問(wèn)題的最優(yōu)解,初始表中一定要滿(mǎn)足對(duì)偶問(wèn)題可行，也就是說(shuō)檢驗(yàn)數(shù)滿(mǎn)足最優(yōu)判別準(zhǔn)則,最小比值中的絕對(duì)值是使得比值非負(fù)，在極小化問(wèn)題j0，分母aij0這時(shí)必須取絕對(duì)值。在極大化問(wèn)題中，j0，分母aij0，總滿(mǎn)足非負(fù)，這時(shí)絕對(duì)值符號(hào)不起作用，可以去掉。如在本例中將目標(biāo)函數(shù)寫(xiě)成,這里j0在求k時(shí)就可以不帶絕對(duì)值符號(hào)。,對(duì)偶單純形法,對(duì)偶單純形法與普通單純形法的換基順序不一樣，普通單純形法是先確定進(jìn)基變量后確定出基變量，對(duì)偶單純形法是先確定出基變量后確定進(jìn)基變量；,普通單純形法的最小比值是其目的是保證下一個(gè)原問(wèn)題的基本解可行，對(duì)偶單純形法的最小比值是,其目的是保證下一個(gè)對(duì)偶問(wèn)題的基本解可行,對(duì)偶單純形法在確定出基變量時(shí)，若不遵循規(guī)則，任選一個(gè)小于零的bi對(duì)應(yīng)的基變量出基，不影響計(jì)算結(jié)果，只是迭代次數(shù)可能不一樣。,本章小結(jié),學(xué)習(xí)要點(diǎn)：1.線性規(guī)劃解的概念以及3個(gè)基本定理2.熟練掌握單純形法的解題思路及求解步驟,Chapter3運(yùn)輸規(guī)劃(TransportationProblem),運(yùn)輸規(guī)劃問(wèn)題的數(shù)學(xué)模型表上作業(yè)法運(yùn)輸問(wèn)題的應(yīng)用,本章主要內(nèi)容：,運(yùn)輸規(guī)劃問(wèn)題的數(shù)學(xué)模型,例3.1某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷(xiāo)地B1,B2,B3，各產(chǎn)地的產(chǎn)量、各銷(xiāo)地的銷(xiāo)量和各產(chǎn)地運(yùn)往各銷(xiāo)地每件物品的運(yùn)費(fèi)如下表所示，問(wèn)：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？,運(yùn)輸規(guī)劃問(wèn)題的數(shù)學(xué)模型,解：產(chǎn)銷(xiāo)平衡問(wèn)題：總產(chǎn)量=總銷(xiāo)量500設(shè)xij為從產(chǎn)地Ai運(yùn)往銷(xiāo)地Bj的運(yùn)輸量，得到下列運(yùn)輸量表：,MinC=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200 x21+x22+x23=300 x11+x21=150 x12+x22=150 x13+x23=200 xij0(i=1、2；j=1、2、3）,運(yùn)輸規(guī)劃問(wèn)題的數(shù)學(xué)模型,運(yùn)輸問(wèn)題的一般形式：產(chǎn)銷(xiāo)平衡,A1、A2、Am表示某物資的m個(gè)產(chǎn)地；B1、B2、Bn表示某物質(zhì)的n個(gè)銷(xiāo)地；ai表示產(chǎn)地Ai的產(chǎn)量；bj表示銷(xiāo)地Bj的銷(xiāo)量；cij表示把物資從產(chǎn)地Ai運(yùn)往銷(xiāo)地Bj的單位運(yùn)價(jià)。設(shè)xij為從產(chǎn)地Ai運(yùn)往銷(xiāo)地Bj的運(yùn)輸量，得到下列一般運(yùn)輸量問(wèn)題的模型：,運(yùn)輸規(guī)劃問(wèn)題的數(shù)學(xué)模型,變化：1）有時(shí)目標(biāo)函數(shù)求最大。如求利潤(rùn)最大或營(yíng)業(yè)額最大等；2）當(dāng)某些運(yùn)輸線路上的能力有限制時(shí)，在模型中直接加入約束條件（等式或不等式約束)；3）產(chǎn)銷(xiāo)不平衡時(shí)，可加入假想的產(chǎn)地（銷(xiāo)大于產(chǎn)時(shí)）或銷(xiāo)地（產(chǎn)大于銷(xiāo)時(shí)）。,定理:設(shè)有m個(gè)產(chǎn)地n個(gè)銷(xiāo)地且產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題，則基變量數(shù)為m+n-1。,表上作業(yè)法,表上作業(yè)法是一種求解運(yùn)輸問(wèn)題的特殊方法，其實(shí)質(zhì)是單純形法。,表上作業(yè)法,例3.2某運(yùn)輸資料如下表所示：,問(wèn)：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最小？,表上作業(yè)法,解：第1步求初始方案,方法1：最小元素法基本思想是就近供應(yīng)，即從運(yùn)價(jià)最小的地方開(kāi)始供應(yīng)（調(diào)運(yùn)），然后次小，直到最后供完為止。,3,11,3,10,1,9,2,7,4,10,5,8,3,4,1,6,3,3,表上作業(yè)法,總的運(yùn)輸費(fèi)(31)+(64)+(43)+(12)+(310)+(35)=86元,元素差額法對(duì)最小元素法進(jìn)行了改進(jìn)，考慮到產(chǎn)地到銷(xiāo)地的最小運(yùn)價(jià)和次小運(yùn)價(jià)之間的差額，如果差額很大，就選最小運(yùn)價(jià)先調(diào)運(yùn)，否則會(huì)增加總運(yùn)費(fèi)。例如下面兩種運(yùn)輸方案。,15,5,10,總運(yùn)費(fèi)是z=108+52+151=105,最小元素法：,表上作業(yè)法,5,15,10,總運(yùn)費(fèi)z=105+152+51=85,后一種方案考慮到C11與C21之間的差額是82=6，如果不先調(diào)運(yùn)x21，到后來(lái)就有可能x110，這樣會(huì)使總運(yùn)費(fèi)增加較大，從而先調(diào)運(yùn)x21，再是x22，其次是x12,用元素差額法求得的基本可行解更接近最優(yōu)解，所以也稱(chēng)為近似方案。,表上作業(yè)法,方法2：Vogel法,1）從運(yùn)價(jià)表中分別計(jì)算出各行和各列的最小運(yùn)費(fèi)和次最小運(yùn)費(fèi)的差額，并填入該表的最右列和最下行。,3,11,3,10,1,9,2,7,4,10,5,8,表上作業(yè)法,2）再?gòu)牟钪底畲蟮男谢蛄兄姓页鲎钚∵\(yùn)價(jià)確定供需關(guān)系和供需數(shù)量。當(dāng)產(chǎn)地或銷(xiāo)地中有一方數(shù)量供應(yīng)完畢或得到滿(mǎn)足時(shí)，劃去運(yùn)價(jià)表中對(duì)應(yīng)的行或列。重復(fù)1)和2)，直到找出初始解為至。,3,11,3,10,1,9,2,7,4,10,5,8,5,表上作業(yè)法,7,1,1,3,5,2,1,5,表上作業(yè)法,7,1,3,5,2,7,5,3,表上作業(yè)法,1,1,3,5,1,5,3,6,3,1,2,該方案的總運(yùn)費(fèi):(13)(46)(35)(210)(18)(35)85元,表上作業(yè)法,第2步最優(yōu)解的判別（檢驗(yàn)數(shù)的求法）,求出一組基可行解后，判斷是否為最優(yōu)解，仍然是用檢驗(yàn)數(shù)來(lái)判斷，記xij的檢驗(yàn)數(shù)為ij由第一章知，求最小值的運(yùn)輸問(wèn)題的最優(yōu)判別準(zhǔn)則是：,所有非基變量的檢驗(yàn)數(shù)都非負(fù)，則運(yùn)輸方案最優(yōu),求檢驗(yàn)數(shù)的方法有兩種：閉回路法位勢(shì)法（）,表上作業(yè)法,閉回路的概念,為一個(gè)閉回路，集合中的變量稱(chēng)為回路的頂點(diǎn)，相鄰兩個(gè)變量的連線為閉回路的邊。如下表,表上作業(yè)法,例下表中閉回路的變量集合是x11,x12,x42,x43,x23,x25,x35,x31共有8個(gè)頂點(diǎn)，這8個(gè)頂點(diǎn)間用水平或垂直線段連接起來(lái)，組成一條封閉的回路。,一條回路中的頂點(diǎn)數(shù)一定是偶數(shù)，回路遇到頂點(diǎn)必須轉(zhuǎn)90度與另一頂點(diǎn)連接，表33中的變量x32及x33不是閉回路的頂點(diǎn)，只是連線的交點(diǎn)。,表上作業(yè)法,閉回路,例如變量組不能構(gòu)成一條閉回路，但A中包含有閉回路,變量組變量數(shù)是奇數(shù)，顯然不是閉回路，也不含有閉回路；,表上作業(yè)法,用位勢(shì)法對(duì)初始方案進(jìn)行最優(yōu)性檢驗(yàn)：,1）由ij=Cij-（Ui+Vj）計(jì)算位勢(shì)Ui，Vj，因?qū)兞慷杂衖j=0，即Cij-（Ui+Vj）=0，令U1=0,2）再由ij=Cij-（Ui+Vj）計(jì)算非基變量的檢驗(yàn)數(shù)ij,3,11,3,10,1,9,2,7,4,10,5,8,4,3,6,3,1,3,0,-1,-5,3,10,2,9,（1）,（2）,（1）,（-1）,（10）,（12）,當(dāng)存在非基變量的檢驗(yàn)數(shù)kl0，說(shuō)明現(xiàn)行方案為最優(yōu)方案，否則目標(biāo)成本還可以進(jìn)一步減小。,表上作業(yè)法,當(dāng)存在非基變量的檢驗(yàn)數(shù)kl0且kl=minij時(shí)，令Xkl進(jìn)基。從表中知可選X24進(jìn)基。,第3步確定換入基的變量,第4步確定換出基的變量,以進(jìn)基變量xik為起點(diǎn)的閉回路中，標(biāo)有負(fù)號(hào)的最小運(yùn)量作為調(diào)整量，對(duì)應(yīng)的基變量為出基變量，并打上“”以示換出作為非基變量。,表上作業(yè)法,3,11,3,10,1,9,2,7,4,10,5,8,4,3,6,3,1,3,(),(),(),(),調(diào)整步驟為：在進(jìn)基變量的閉回路中標(biāo)有正號(hào)的變量加上調(diào)整量，標(biāo)有負(fù)號(hào)的變量減去調(diào)整量，其余變量不變，得到一組新的基可行解。然后求所有非基變量的檢驗(yàn)數(shù)重新檢驗(yàn)。,1,2,5,表上作業(yè)法,當(dāng)所有非基變量的檢驗(yàn)數(shù)均非負(fù)時(shí)，則當(dāng)前調(diào)運(yùn)方案即為最優(yōu)方案，如表此時(shí)最小總運(yùn)費(fèi)：Z=(13)(46)(35)(210)(18)(35)85元,3,11,3,10,1,9,2,7,4,10,5,8,5,3,6,3,1,2,0,-2,-5,3,10,3,9,（0）,（2）,（2）,（1）,（12）,（9）,表上作業(yè)法,表上作業(yè)法的計(jì)算步驟：,表上作業(yè)法,表上作業(yè)法計(jì)算中的問(wèn)題：,（1）若運(yùn)輸問(wèn)題的某一基可行解有多個(gè)非基變量的檢驗(yàn)數(shù)為負(fù)，在繼續(xù)迭代時(shí)，取它們中任一變量為換入變量均可使目標(biāo)函數(shù)值得到改善，但通常取ij0中最小者對(duì)應(yīng)的變量為換入變量。（2）無(wú)窮多最優(yōu)解產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題必定存最優(yōu)解。如果非基變量的ij0，則該問(wèn)題有無(wú)窮多最優(yōu)解。,表上作業(yè)法,退化解：表格中一般要有(m+n-1)個(gè)數(shù)字格。但有時(shí)在分配運(yùn)量時(shí)則需要同時(shí)劃去一行和一列，這時(shí)需要補(bǔ)一個(gè)0，以保證有(m+n-1)個(gè)數(shù)字格作為基變量。一般可在劃去的行和列的任意空格處加一個(gè)0即可。利用進(jìn)基變量的閉回路對(duì)解進(jìn)行調(diào)整時(shí)，標(biāo)有負(fù)號(hào)的最小運(yùn)量（超過(guò)2個(gè)最小值）作為調(diào)整量，選擇任意一個(gè)最小運(yùn)量對(duì)應(yīng)的基變量作為出基變量，并打上“”以示作為非基變量。,表上作業(yè)法,12,4,11,4,8,3,10,2,9,5,11,6,(0),(2),(9),(2),(1),(12),8,12,4,2,8,14,如下例中11檢驗(yàn)數(shù)是0，經(jīng)過(guò)調(diào)整，可得到另一個(gè)最優(yōu)解。,表上作業(yè)法,11,4,4,3,1,3,7,7,8,2,10,6,3,4,1,6,0,6,在x12、x22、x33、x34中任選一個(gè)變量作為基變量，例如選x34,例：用最小元素法求初始可行解,運(yùn)輸問(wèn)題的應(yīng)用,求極大值問(wèn)題目標(biāo)函數(shù)求利潤(rùn)最大或營(yíng)業(yè)額最大等問(wèn)題。,運(yùn)輸問(wèn)題的應(yīng)用,求解方法：將極大化問(wèn)題轉(zhuǎn)化為極小化問(wèn)題。設(shè)極大化問(wèn)題的運(yùn)價(jià)表為C，用一個(gè)較大的數(shù)M（Mmaxcij）去減每一個(gè)cij得到矩陣C，其中C=（Mcij）0,將C作為極小化問(wèn)題的運(yùn)價(jià)表，用表上用業(yè)法求出最優(yōu)解。,運(yùn)輸問(wèn)題的應(yīng)用,例3.3下列矩陣C是Ai（I=1，2，3）到Bj的噸公里利潤(rùn),運(yùn)輸部門(mén)如何安排運(yùn)輸方案使總利潤(rùn)最大.,運(yùn)輸問(wèn)題的應(yīng)用,得到新的最小化運(yùn)輸問(wèn)題，用表上作業(yè)法求解即可。,運(yùn)輸問(wèn)題的應(yīng)用,產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題當(dāng)總產(chǎn)量與總銷(xiāo)量不相等時(shí),稱(chēng)為不平衡運(yùn)輸問(wèn)題.這類(lèi)運(yùn)輸問(wèn)題在實(shí)際中常常碰到,它的求解方法是將不平衡問(wèn)題化為平衡問(wèn)題再按平衡問(wèn)題求解。,當(dāng)產(chǎn)大于銷(xiāo)時(shí)，即：,數(shù)學(xué)模型為：,運(yùn)輸問(wèn)題的應(yīng)用,由于總產(chǎn)量大于總銷(xiāo)量，必有部分產(chǎn)地的產(chǎn)量不能全部運(yùn)送完，必須就地庫(kù)存，即每個(gè)產(chǎn)地設(shè)一個(gè)倉(cāng)庫(kù)，假設(shè)該倉(cāng)庫(kù)為一個(gè)虛擬銷(xiāo)地Bn+1，bn+1作為一個(gè)虛設(shè)銷(xiāo)地Bn+1的銷(xiāo)量(即庫(kù)存量)。各產(chǎn)地Ai到Bn+1的運(yùn)價(jià)為零，即Ci,n+1=0,（i=1，m）。則平衡問(wèn)題的數(shù)學(xué)模型為：,具體求解時(shí),只在運(yùn)價(jià)表右端增加一列Bn+1，運(yùn)價(jià)為零,銷(xiāo)量為bn+1即可,運(yùn)輸問(wèn)題的應(yīng)用,當(dāng)銷(xiāo)大于產(chǎn)時(shí)，即：,數(shù)學(xué)模型為：,由于總銷(xiāo)量大于總產(chǎn)量,故一定有些需求地不完全滿(mǎn)足,這時(shí)虛設(shè)一個(gè)產(chǎn)地Am+1，產(chǎn)量為：,運(yùn)輸問(wèn)題的應(yīng)用,銷(xiāo)大于產(chǎn)化為平衡問(wèn)題的數(shù)學(xué)模型為：,具體計(jì)算時(shí)，在運(yùn)價(jià)表的下方增加一行Am+1，運(yùn)價(jià)為零。產(chǎn)量為am+1即可。,運(yùn)輸問(wèn)題的應(yīng)用,例3.4求下列表中極小化運(yùn)輸問(wèn)題的最優(yōu)解。,因?yàn)橛校?運(yùn)輸問(wèn)題的應(yīng)用,所以是一個(gè)產(chǎn)大于銷(xiāo)的運(yùn)輸問(wèn)題。表中A2不可達(dá)B1，用一個(gè)很大的正數(shù)M表示運(yùn)價(jià)C21。虛設(shè)一個(gè)銷(xiāo)量為b5=180-160=20，Ci5=0，i=1,2,3,4，表的右邊增添一列，得到新的運(yùn)價(jià)表。,運(yùn)輸問(wèn)題的應(yīng)用,下表為計(jì)算結(jié)果。可看出：產(chǎn)地A4還有20個(gè)單位沒(méi)有運(yùn)出。,運(yùn)輸問(wèn)題的應(yīng)用,3.生產(chǎn)與儲(chǔ)存問(wèn)題,例3.5某廠按合同規(guī)定須于當(dāng)年每個(gè)季度末分別提供10、15、25、20臺(tái)同一規(guī)格的柴油機(jī)。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺(tái)柴油機(jī)的成本如右表。如果生產(chǎn)出來(lái)的柴油機(jī)當(dāng)季不交貨，每臺(tái)每積壓一個(gè)季度需儲(chǔ)存、維護(hù)等費(fèi)用0.15萬(wàn)元。試求在完成合同的情況下，使該廠全年生產(chǎn)總費(fèi)用為最小的決策方案。,運(yùn)輸問(wèn)題的應(yīng)用,解：設(shè)xij為第i季度生產(chǎn)的第j季度交貨的柴油機(jī)數(shù)目，那么應(yīng)滿(mǎn)足：交貨：x11=10生產(chǎn)：x11+x12+x13+x1425x12+x22=15x22+x23+x2435x13+x23+x33=25x33+x3430 x14+x24+x34+x44=20 x4410,把第i季度生產(chǎn)的柴油機(jī)數(shù)目看作第i個(gè)生產(chǎn)廠的產(chǎn)量；把第j季度交貨的柴油機(jī)數(shù)目看作第j個(gè)銷(xiāo)售點(diǎn)的銷(xiāo)量；設(shè)cij是第i季度生產(chǎn)的第j季度交貨的每臺(tái)柴油機(jī)的實(shí)際成本，應(yīng)該等于該季度單位成本加上儲(chǔ)存、維護(hù)等費(fèi)用?？蓸?gòu)造下列產(chǎn)銷(xiāo)平衡問(wèn)題：,運(yùn)輸問(wèn)題的應(yīng)用,由于產(chǎn)大于銷(xiāo)，加上一個(gè)虛擬的銷(xiāo)地D，化為平衡問(wèn)題，即可應(yīng)用表上作業(yè)法求解。,運(yùn)輸問(wèn)題的應(yīng)用,該問(wèn)題的數(shù)學(xué)模型：Minf=10.8x11+10.95x12+11.1x13+11.25x14+11.1x22+11.25x23+11.4x24+11.0 x33+11.15x34+11.3x44,運(yùn)輸問(wèn)題的應(yīng)用,最優(yōu)生產(chǎn)決策如下表，最小費(fèi)用z773萬(wàn)元。,Chapter4整數(shù)規(guī)劃(IntegerProgramming),整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用分支定界法分配問(wèn)題與匈牙利法,本章主要內(nèi)容：,整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用,整數(shù)規(guī)劃（簡(jiǎn)稱(chēng)：IP）要求一部分或全部決策變量取整數(shù)值的規(guī)劃問(wèn)題稱(chēng)為整數(shù)規(guī)劃。不考慮整數(shù)條件，由余下的目標(biāo)函數(shù)和約束條件構(gòu)成的規(guī)劃問(wèn)題稱(chēng)為該整數(shù)規(guī)劃問(wèn)題的松弛問(wèn)題。若該松弛問(wèn)題是一個(gè)線性規(guī)劃，則稱(chēng)該整數(shù)規(guī)劃為整數(shù)線性規(guī)劃。,整數(shù)線性規(guī)劃數(shù)學(xué)模型的一般形式：,整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用,整數(shù)線性規(guī)劃問(wèn)題的種類(lèi)：,純整數(shù)線性規(guī)劃：指全部決策變量都必須取整數(shù)值的整數(shù)線性規(guī)劃?；旌险麛?shù)線性規(guī)劃：決策變量中有一部分必須取整數(shù)值，另一部分可以不取整數(shù)值的整數(shù)線性規(guī)劃。0-1型整數(shù)線性規(guī)劃：決策變量只能取值0或1的整數(shù)線性規(guī)劃。,整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用,整數(shù)規(guī)劃的典型例子,例4.1工廠A1和A2生產(chǎn)某種物資。由于該種物資供不應(yīng)求，故需要再建一家工廠。相應(yīng)的建廠方案有A3和A4兩個(gè)。這種物資的需求地有B1,B2,B3,B4四個(gè)。各工廠年生產(chǎn)能力、各地年需求量、各廠至各需求地的單位物資運(yùn)費(fèi)cij，見(jiàn)下表：,工廠A3或A4開(kāi)工后，每年的生產(chǎn)費(fèi)用估計(jì)分別為1200萬(wàn)或1500萬(wàn)元?，F(xiàn)要決定應(yīng)該建設(shè)工廠A3還是A4，才能使今后每年的總費(fèi)用最少。,整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用,解：這是一個(gè)物資運(yùn)輸問(wèn)題，特點(diǎn)是事先不能確定應(yīng)該建A3還是A4中哪一個(gè)，因而不知道新廠投產(chǎn)后的實(shí)際生產(chǎn)物資。為此，引入0-1變量：,再設(shè)xij為由Ai運(yùn)往Bj的物資數(shù)量，單位為千噸；z表示總費(fèi)用，單位萬(wàn)元。則該規(guī)劃問(wèn)題的數(shù)學(xué)模型可以表示為：,整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用,混合整數(shù)規(guī)劃問(wèn)題,整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用,例4.2現(xiàn)有資金總額為B?？晒┻x擇的投資項(xiàng)目有n個(gè)，項(xiàng)目j所需投資額和預(yù)期收益分別為aj和cj（j1,2,.,n），此外由于種種原因，有三個(gè)附加條件：若選擇項(xiàng)目1，就必須同時(shí)選擇項(xiàng)目2。反之不一定項(xiàng)目3和4中至少選擇一個(gè)；項(xiàng)目5,6,7中恰好選擇2個(gè)。應(yīng)該怎樣選擇投資項(xiàng)目，才能使總預(yù)期收益最大。,整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用,解：對(duì)每個(gè)投資項(xiàng)目都有被選擇和不被選擇兩種可能，因此分別用0和1表示，令xj表示第j個(gè)項(xiàng)目的決策選擇，記為：,投資問(wèn)題可以表示為：,整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用,例4.3指派問(wèn)題或分配問(wèn)題。人事部門(mén)欲安排四人到四個(gè)不同崗位工作，每個(gè)崗位一個(gè)人。經(jīng)考核四人在不同崗位的成績(jī)（百分制）如表所示，如何安排他們的工作使總成績(jī)最好。,整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用,設(shè),數(shù)學(xué)模型如下：,要求每人做一項(xiàng)工作，約束條件為：,整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用,每項(xiàng)工作只能安排一人，約束條件為：,變量約束：,整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用,整數(shù)規(guī)劃問(wèn)題解的特征：,整數(shù)規(guī)劃問(wèn)題的可行解集合是它松弛問(wèn)題可行解集合的一個(gè)子集，任意兩個(gè)可行解的凸組合不一定滿(mǎn)足整數(shù)約束條件，因而不一定仍為可行解。整數(shù)規(guī)劃問(wèn)題的可行解一定是它的松弛問(wèn)題的可行解（反之不一定），但其最優(yōu)解的目標(biāo)函數(shù)值不會(huì)優(yōu)于后者最優(yōu)解的目標(biāo)函數(shù)值。,整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用,例4.3設(shè)整數(shù)規(guī)劃問(wèn)題如下,首先不考慮整數(shù)約束，得到線性規(guī)劃問(wèn)題（一般稱(chēng)為松弛問(wèn)題）。,整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用,用圖解法求出最優(yōu)解為：x13/2,x2=10/3，且有Z=29/6,現(xiàn)求整數(shù)解(最優(yōu)解):如用舍入取整法可得到4個(gè)點(diǎn)即(1，3),(2，3),(1，4),(2，4)。顯然，它們都不可能是整數(shù)規(guī)劃的最優(yōu)解。,x1,x2,3,3,(3/2,10/3),按整數(shù)規(guī)劃約束條件，其可行解肯定在線性規(guī)劃問(wèn)題的可行域內(nèi)且為整數(shù)點(diǎn)。故整數(shù)規(guī)劃問(wèn)題的可行解集是一個(gè)有限集，如右圖所示。其中(2,2),(3,1)點(diǎn)的目標(biāo)函數(shù)值最大，即為Z=4。,整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用,整數(shù)規(guī)劃問(wèn)題的求解方法：,分支定界法和割平面法匈牙利法（指派問(wèn)題）,分支定界法,1）求整數(shù)規(guī)劃的松弛問(wèn)題最優(yōu)解；若松弛問(wèn)題的最優(yōu)解滿(mǎn)足整數(shù)要求，得到整數(shù)規(guī)劃的最優(yōu)解,否則轉(zhuǎn)下一步；2）分支與定界：任意選一個(gè)非整數(shù)解的變量xi，在松弛問(wèn)題中加上約束：xixi和xixi+1組成兩個(gè)新的松弛問(wèn)題，稱(chēng)為分枝。新的松弛問(wèn)題具有特征：當(dāng)原問(wèn)題是求最大值時(shí)，目標(biāo)值是分枝問(wèn)題的上界；當(dāng)原問(wèn)題是求最小值時(shí)，目標(biāo)值是分枝問(wèn)題的下界。檢查所有分枝的解及目標(biāo)函數(shù)值，若某分枝的解是整數(shù)并且目標(biāo)函數(shù)值大于（max）等于其它分枝的目標(biāo)值，則將其它分枝剪去不再計(jì)算，若還存在非整數(shù)解并且目標(biāo)值大于(max)整數(shù)解的目標(biāo)值，需要繼續(xù)分枝，再檢查，直到得到最優(yōu)解。,分支定界法的解題步驟：,分支定界法,例4.4用分枝定界法求解整數(shù)規(guī)劃問(wèn)題,解：首先去掉整數(shù)約束，變成一般線性規(guī)劃問(wèn)題(原整數(shù)規(guī)劃問(wèn)題的松馳問(wèn)題),LP,IP,分支定界法,用圖解法求松弛問(wèn)題的最優(yōu)解，如圖所示。,x1,x2,3,(18/11,40/11),2,1,1,2,3,x118/11,x2=40/11Z=218/11(19.8)即Z也是IP最小值的下限。,對(duì)于x118/111.64，取值x11，x12對(duì)于x2=40/113.64，取值x23，x24先將（LP）劃分為（LP1）和（LP2）,取x11,x12,分支定界法,分支：,分別求出（LP1）和（LP2）的最優(yōu)解。,分支定界法,先求LP1,如圖所示。此時(shí)在B點(diǎn)取得最優(yōu)解。x11,x2=3,Z(1)16找到整數(shù)解，問(wèn)題已探明，此枝停止計(jì)算。,x1,x2,3,3,(18/11,40/11),1,1,B,A,C,同理求LP2,如圖所示。在C點(diǎn)取得最優(yōu)解。即:x12,x2=10/3,Z(2)56/318.7Z(2)Z(1)16原問(wèn)題有比16更小的最優(yōu)解，但x2不是整數(shù)，故繼續(xù)分支。,分支定界法,在IP2中分別再加入條件：x23,x24得下式兩支：,分別求出LP21和LP22的最優(yōu)解,分支定界法,x1,x2,3,3,(18/11,40/11),1,1,B,A,C,D,先求LP21,如圖所示。此時(shí)D在點(diǎn)取得最優(yōu)解。即x112/52.4,x2=3,Z(21)-87/5-17.4Z(211)如對(duì)LP212繼續(xù)分解，其最小值也不會(huì)低于15.5，問(wèn)題探明,剪枝。,分支定界法,原整數(shù)規(guī)劃問(wèn)題的最優(yōu)解為:x1=2,x2=3,Z*=17以上的求解過(guò)程可以用一個(gè)樹(shù)形圖表示如右：,LP1x1=1,x2=3Z(1)16,LPx1=18/11,x2=40/11Z(0)19.8,LP2x1=2,x2=10/3Z(2)18.5,LP21x1=12/5,x2=3Z(21)17.4,LP22無(wú)可行解,LP211x1=2,x2=3Z(211)17,LP212x1=3,x2=5/2Z(212)15.5,x11,x12,x23,x24,x12,x13,分支定界法,例4.5用分枝定界法求解,解:先求對(duì)應(yīng)的松弛問(wèn)題（記為L(zhǎng)P0）,用圖解法得到最優(yōu)解X(3.57,7.14),Z0=35.7,如下圖所示。,分支定界法,10,10,松弛問(wèn)題LP0的最優(yōu)解X=(3.57,7.14),Z0=35.7,x1,x2,o,A,B,C,分支定界法,10,x2,o,A,B,C,LP1,LP2,3,4,LP1:X=(3,7.6),Z1=34.8,LP2:X=(4,6.5),Z2=35.5,分支定界法,10,x1,x2,o,A,B,C,LP1,LP21,3,4,LP21:X=(4.33,6),Z21=35.33,6,分支定界法,10,x1,x2,o,A,C,LP1,3,4,6,LP211:X=(4,6),Z211=34,LP212:X=(5,5),Z212=35,5,LP212,分支定界法,上述分枝過(guò)程可用下圖表示：,LP0:X=(3.57,7.14),Z0=35.7,LP1:X=(3,7.6)Z1=34.8,LP2:X=(4,6.5)Z2=35.5,x13,x14,LP21:X=(4.33,6)Z21=35.33,x26,LP211:X=(4,6)Z211=34,LP212:X=(5,5)Z212=35,x14,x15,LP22無(wú)可行解,x27,小結(jié),學(xué)習(xí)要點(diǎn)：掌握一般整數(shù)規(guī)劃問(wèn)題概念及模型結(jié)構(gòu)掌握分支定界法原理能夠用分支定界法求解一般整數(shù)規(guī)劃問(wèn)題,課后練習(xí)：,分配問(wèn)題與匈牙利法,指派問(wèn)題的數(shù)學(xué)模型的標(biāo)準(zhǔn)形式：,設(shè)n個(gè)人被分配去做n件工作，規(guī)定每個(gè)人只做一件工作，每件工作只有一個(gè)人去做。已知第i個(gè)人去做第j件工作的效率（時(shí)間或費(fèi)用）為Cij(i=1.2n;j=1.2n)并假設(shè)Cij0。問(wèn)應(yīng)如何分配才能使總效率（時(shí)間或費(fèi)用）最高？,設(shè)決策變量,分配問(wèn)題與匈牙利法,指派問(wèn)題的數(shù)學(xué)模型為：,分配問(wèn)題與匈牙利法,克尼格定理:如果從分配問(wèn)題效率矩陣aij的每一行元素中分別減去(或加上)一個(gè)常數(shù)ui，從每一列中分別減去(或加上)一個(gè)常數(shù)vj，得到一個(gè)新的效率矩陣bij，則以bij為效率矩陣的分配問(wèn)題與以aij為效率矩陣的分配問(wèn)題具有相同的最優(yōu)解。,分配問(wèn)題與匈牙利法,指派問(wèn)題的求解步驟：,1)變換指派問(wèn)題的系數(shù)矩陣(cij)為(bij)，使在(bij)的各行各列中都出現(xiàn)0元素，即從(cij)的每行元素都減去該行的最小元素；再?gòu)乃眯孪禂?shù)矩陣的每列元素中減去該列的最小元素。,2)進(jìn)行試指派，以尋求最優(yōu)解。在(bij)中找盡可能多的獨(dú)立0元素，若能找出n個(gè)獨(dú)立0元素，就以這n個(gè)獨(dú)立0元素對(duì)應(yīng)解矩陣(xij)中的元素為1，其余為0，這就得到最優(yōu)解。,分配問(wèn)題與匈牙利法,找獨(dú)立0元素，常用的步驟為：,從只有一個(gè)0元素的行開(kāi)始，給該行中的0元素加圈，記作。然后劃去所在列的其它0元素，記作；這表示該列所代表的任務(wù)已指派完，不必再考慮別人了。依次進(jìn)行到最后一行。從只有一個(gè)0元素的列開(kāi)始（畫(huà)的不計(jì)在內(nèi)），給該列中的0元素加圈，記作；然后劃去所在行的0元素，記作，表示此人已有任務(wù)，不再為其指派其他任務(wù)了。依次進(jìn)行到最后一列。若仍有沒(méi)有劃圈的0元素，且同行(列)的0元素至少有兩個(gè)，比較這行各0元素所在列中0元素的數(shù)目，選擇0元素少這個(gè)0元素加圈(表示選擇性多的要“禮讓”選擇性少的)。然后劃掉同行同列的其它0元素?？煞磸?fù)進(jìn)行，直到所有0元素都已圈出和劃掉為止。,分配問(wèn)題與匈牙利法,若元素的數(shù)目m等于矩陣的階數(shù)n（即：mn），那么這指派問(wèn)題