管理夢_定義課件

1、 趙鵬舉中原工學(xué)院管 理 運 籌 學(xué)1sfsf數(shù)學(xué)的魅力與實質(zhì)數(shù)學(xué)的本質(zhì)是處理抽象對象，是比語言更精煉、更嚴(yán)謹(jǐn)?shù)姆栂到y(tǒng)。是人類理性的集中體現(xiàn)。數(shù)學(xué)的方法是建立一個牢不可破的公理體系，并以演繹推理的方法去構(gòu)建和擴(kuò)展整個學(xué)科體系。2sfsf數(shù)學(xué)分支數(shù)學(xué)分支數(shù)學(xué)分支應(yīng)用 演繹方法 公理體系數(shù)學(xué)大廈3sfsf數(shù)學(xué)的魅力與實質(zhì)數(shù)學(xué)方法在自然科學(xué)體系中無處不在，并取得了光輝的成就。19世紀(jì)以后，數(shù)學(xué)被廣泛深入地應(yīng)用于社會科學(xué)領(lǐng)域。經(jīng)濟(jì)學(xué)、管理學(xué)領(lǐng)域的許多大師具有高超的數(shù)學(xué)技能。4sfsf數(shù)學(xué)的魅力與實質(zhì)本門課程不僅要學(xué)習(xí)一門課程，一套方法，更重要的是要學(xué)會理性分析問題的方法。培養(yǎng)邏輯思維能力和抽象思維能

2、力。數(shù)學(xué)在發(fā)展的過程中遇到過許多問題，而且也并非確切無疑，大家要敢于質(zhì)疑，敢于提問題。5sfsf數(shù)學(xué)的魅力與實質(zhì)一個例子： S=1-1+1-1+1請問S等于多少？6sfsf數(shù)學(xué)的魅力與實質(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。7sfsf數(shù)學(xué)的魅力與實質(zhì)事實上，這是一個爭論未定的題目，反映了人類對自然認(rèn)識的不足。無窮的概念存在許多不足之處，而且并非絕對精確。不同的學(xué)派對無窮有著不同的認(rèn)識。8sfsf考核方法平時成績占20%，每位同學(xué)的初始

3、成績都是60分（按100分為滿分計算）。每次作業(yè)交上加1分，不交不加不減，拷貝別人作業(yè)一次扣2分。上課主動回答問題每次加2分。提出有價值問題或發(fā)現(xiàn)老師錯誤每次加5分。9sfsf運籌學(xué)的體系和發(fā)展歷史定義運籌學(xué)是一門應(yīng)用于管理有組織系統(tǒng)的科學(xué)它為掌管這類系統(tǒng)的人提供決策目標(biāo)和數(shù)量分析的工具運籌學(xué)應(yīng)用分析、實驗、量化的方法，對經(jīng)濟(jì)管理系統(tǒng)中人、財、物等有限資源進(jìn)行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實現(xiàn)最有效的管理正式起源與二次世界大戰(zhàn)，被稱為Operations research,日本人翻譯為運做學(xué)，臺灣人翻譯為作業(yè)研究10sfsf運籌學(xué)的體系和發(fā)展歷史田忌賽馬萌芽在20世紀(jì)初，Lanch

4、ester戰(zhàn)斗方程。丹麥工程師愛爾朗研究電話通訊系統(tǒng)時提出了一些排隊論的公式。30年代，數(shù)學(xué)家列溫遜運用運籌思想分析商業(yè)廣告、顧客心理。11sfsf運籌學(xué)的體系和發(fā)展歷史二次世界大戰(zhàn)中，英美科學(xué)家研究如何有效運用雷達(dá)，研究船隊遇到襲擊如何減少損失，以及如何使用深水炸彈等緊迫問題。應(yīng)用：德國潛艇被摧毀數(shù)增加到400%，船只中彈數(shù)由47%減少到29%。結(jié)果：打贏了空戰(zhàn)和海戰(zhàn)，保證了二次世界大戰(zhàn)的最終勝利。12sfsf運籌學(xué)在現(xiàn)實生活中的例子企業(yè)安排生產(chǎn)計劃庫存管理公交系統(tǒng)優(yōu)化食堂窗口設(shè)置電腦游戲，帝國時代、魔獸爭霸等。13sfsf運籌學(xué)的學(xué)科體系規(guī)劃論：包括線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃等。194

5、7年，Danzig提出單純形法，隨后規(guī)劃方法得到了廣泛的應(yīng)用。圖論與網(wǎng)絡(luò)分析：圖是研究離散事物之間關(guān)系的一種分析模型。例：有甲、乙、丙、丁、戊、己6名同學(xué)參加ABCDEF六個項目的比賽，下表是各運動員報名參賽的項目，問6個項目順序如何安排，作到每名運動員不連續(xù)參加兩項比賽。14sfsf運籌學(xué)的學(xué)科體系A(chǔ)BCDEF甲*乙*丙*丁*戊*己*15sfsf運籌學(xué)的學(xué)科體系排隊論：研究公共服務(wù)系統(tǒng)的運行與優(yōu)化的數(shù)學(xué)理論方法。決策論：研究不確定情況以及風(fēng)險情況下的決策。存儲論：研究企業(yè)的庫存計劃，進(jìn)貨周期等。博弈論：研究競爭環(huán)境下決策者行為的數(shù)學(xué)方法。16sfsf運籌學(xué)的工作步驟提出和形成問題：弄清問題的

6、目標(biāo)，可能的約束，問題的可控變量，相關(guān)參數(shù)等。建立模型：把問題中的可控變量、參數(shù)、目標(biāo)、約束之間的關(guān)系用一定的模型表示出來。求解：用計算或?qū)嶒灧椒ㄇ蟪鰡栴}的解。解的檢驗：檢查求解過程，檢查解能否反映現(xiàn)實問題。解的實施：將解運用到實際問題中。17sfsf第一章 線性規(guī)劃18sfsf本章內(nèi)容線性規(guī)劃模型線性規(guī)劃問題的圖解法單純形法非標(biāo)準(zhǔn)形線性規(guī)劃的解法19sfsf線性規(guī)劃模型規(guī)劃問題：就是否合理利用有限資源的問題。線性規(guī)劃：線性的規(guī)劃問題。兩個意思： 1、目標(biāo)函數(shù)是線性的 2、約束條件是線性的 20sfsf線性規(guī)劃模型生產(chǎn)決策問題某汽車工廠生產(chǎn)大轎車和載重汽車兩種型號的汽車,已知每輛汽車所用的鋼材

7、都是2噸/輛，該工廠每年供應(yīng)的鋼材為1600噸；工廠的生產(chǎn)能力是每2.5小時可生產(chǎn)一輛載重汽車，每5小時可生產(chǎn)一輛大轎車，工廠全年的有效工時為2500小時；已知供應(yīng)給該廠大轎車用的座椅每年可裝配400輛。據(jù)市場調(diào)查，出售一輛大轎車可獲利4000元，出售一輛載重汽車可獲利3000元。如何安排生產(chǎn)才能使工廠獲利最大？21sfsf線性規(guī)劃模型建模型如下：設(shè)大轎車數(shù)量為x1,載重汽車數(shù)量為x2。s.t.是subject to 的簡寫，表示受限制于。22sfsf線性規(guī)劃模型某工廠在計劃期間內(nèi)生產(chǎn) 、兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及A、B兩種原材料的消耗，如下表所示： 設(shè)備11300臺時原料A2

8、1400Kg原料B01250Kg已知 、兩種產(chǎn)品每單位分別可以獲利50元、100元，問工廠應(yīng)該如何安排生產(chǎn)才能使工廠獲利最多。23sfsf線性規(guī)劃模型設(shè)置變量：生產(chǎn) 產(chǎn)品x1個， 產(chǎn)品x2個目標(biāo)函數(shù)是利潤最大化：資源是有限的，第一個限制是設(shè)備臺時的限制：24sfsf線性規(guī)劃模型第二個限制是原材料A的限制：第三個限制是原材料B的限制：顯然，產(chǎn)量不可能為負(fù)數(shù)：25sfsf線性規(guī)劃模型建模型如下：設(shè)生產(chǎn) 產(chǎn)品x1件, 產(chǎn)品x2件。26sfsf線性規(guī)劃模型（1），（2）分別被稱為目標(biāo)函數(shù)和約束條件。目標(biāo)函數(shù)中變量的系數(shù)被稱為價值系數(shù)，約束條件不等號右端稱為資源向量或限定系數(shù)，約束條件左端變量的系數(shù)被稱

9、為技術(shù)系數(shù)。目標(biāo)函數(shù)和約束條件都是一次冪函數(shù)，或稱線性函數(shù)，因此這類規(guī)劃問題被稱為線性規(guī)劃問題。27sfsf線性規(guī)劃模型例3：生產(chǎn)卷煙的主要原材料包括煙葉和煙梗。國家規(guī)定每千克焦油含量不超過15mg，煙氣煙堿含量不超過1.4mg，現(xiàn)在知道每千克煙葉含焦油12mg，煙氣煙堿1.5mg，煙梗含焦油18mg，煙氣煙堿0.3mg，煙葉每千克50元，煙梗每千克20元，問如何搭配使生產(chǎn)成本最小。28sfsf線性規(guī)劃模型設(shè)每千克卷煙用煙葉x1千克，煙梗x2千克，模型如下：這是目標(biāo)函數(shù)一個求最小化的問題。29sfsf線性規(guī)劃的標(biāo)準(zhǔn)形為求解方便，一般線性規(guī)劃都可以轉(zhuǎn)化成如下標(biāo)準(zhǔn)形式：要求30sfsf線性規(guī)劃的標(biāo)

10、準(zhǔn)形目標(biāo)函數(shù)為求最小化時，等式兩端同乘以-1，變?yōu)榍笞畲蠡?。約束條件為=時，減一個剩余變量。資源變量為負(fù)數(shù)時，等式兩端同乘以-1。變量為0即可。如果bk的變化使得B-1 b + B-1 b0，這時最優(yōu)解的基就要發(fā)生變化，這種情況下用對偶單純形法繼續(xù)求出新的最優(yōu)解。140sfsf資源向量的靈敏度分析例：課本P6例1-1中，如果鋼材的供應(yīng)數(shù)量發(fā)生變化，請問1、鋼材供應(yīng)量在什么范圍內(nèi)變化時，最優(yōu)基不會發(fā)生改變？2、當(dāng)鋼材的供應(yīng)量增加到2200噸時，應(yīng)當(dāng)如何安排生產(chǎn)計劃？141sfsf資源向量的靈敏度分析如果例1-1中的鋼材供應(yīng)數(shù)量變?yōu)?600+ b1，最終解將變?yōu)椋?xB= B-1 b= B-1 (

11、b + b） = =142sfsf資源向量的靈敏度分析要保證最優(yōu)基不改變，要求b中所有向量大于等于0，即：從（1）式中可得： b1-400，從（2）式中可得： b1-600，從（3）式中可得： b1400，得到-400 b1400，也就是說，鋼材供應(yīng)量在1200到2000之間時，最優(yōu)基不發(fā)生變化。143sfsf資源向量的靈敏度分析資源向量在一定范圍內(nèi)變化時，最優(yōu)基雖然不會發(fā)生變化，但最優(yōu)解則會發(fā)生變化。最優(yōu)基不變時，可以直接將發(fā)生變化的資源向量代入B-1 b中，得到新的最優(yōu)解的值。例如，當(dāng)鋼材供應(yīng)量變?yōu)?000時，新的最優(yōu)解的求解如下：144sfsf資源向量的靈敏度分析145sfsf資源向量的

12、靈敏度分析當(dāng)鋼材的供應(yīng)量增加到2200噸時：資源向量出現(xiàn)負(fù)數(shù)，不再是可行解，需要繼續(xù)迭代，用對偶單純形法。146sfsf資源向量的靈敏度分析最終單純形表變?yōu)椋?x1 x2 x3 x4 x5x Cj zj 0 0 1 0.4 0 zj -cj 4 3 1 0.4 0 4 3 0 0 0 0 0 0.5 -0.4 1 0 1 1 -0.4 0 1 0 -0.5 0.4 0b3200147sfsf資源向量的靈敏度分析以主元素為中心進(jìn)行迭代運算： x1 x2 x3 x4 x5x Cj zj 2 0 0 1.2 0 zj -cj 6 3 2 1.2 0 4 3 0 0 0 1 0 0 0 1 2 1 0

13、 0.4 0 -2 0 1 -0.8 0b3000148sfsf趣味數(shù)學(xué)一個富有的律師擁有11輛古董汽車，每輛值5000美元。律師死時留下了一個奇怪的遺囑。他說他的11輛古董汽車分給他的三個兒子。把其中的一半分給長子，1/4分給次子，1/6分給小兒子。同時規(guī)定不能把車賣掉。律師去世后，兒子為了這個遺囑爭論不休，這時一個數(shù)學(xué)家開了一輛汽車來悼念老朋友。三個兒子把他們的難題告訴了數(shù)學(xué)家，數(shù)學(xué)家沉思片刻后說，我有辦法了。請問，他該怎么分配這些汽車？149sfsf約束方程系數(shù)矩陣的靈敏度分析從前邊的分析中，我們知道，單純形法的實質(zhì)是找到一個能得到最優(yōu)解的基xB ，在約束條件中用其系數(shù)矩陣左乘一個B-1

14、 ，同時令非基變量為0，得到最優(yōu)解向量xB = B-1 b。從而我們可以得到如下結(jié)論，最終單純形表中xi的系數(shù)列向量pi 事實上就是其初始系數(shù)列向量pi左乘以B-1 ，既pi = B-1 pi 。根據(jù)以上分析，我們可以得到約束方程技術(shù)系數(shù)變化時靈敏度分析的方法。150sfsf約束方程系數(shù)矩陣的靈敏度分析例如，在例1-1中，列向量x4的系數(shù)列向量(用p4表示）在最終單純形表中為（用p4表示）：151sfsf約束方程系數(shù)矩陣的靈敏度分析根據(jù)以上分析我們可以得到系數(shù)矩陣靈敏度分析的思路。當(dāng)基變量系數(shù)列向量改變時，用初始系數(shù)列向量左乘以B-1 后代入原最終單純形表，在新的單純形表中繼續(xù)進(jìn)行運算，得到最

15、優(yōu)解。當(dāng)新加入決策變量時，意味著約束方程組中增加了列向量，將這個列向量左乘以B-1 后添加到原最終單純形表中，繼續(xù)運算得到最優(yōu)解。152sfsf約束方程系數(shù)矩陣的靈敏度分析在例1-1，為了增加安全性，當(dāng)每輛大轎車使用鋼材由2噸變?yōu)?噸時，求最優(yōu)解有什么變化？工廠具備了生產(chǎn)旅行車的技術(shù)，每輛旅行車用鋼材1.5噸，工時1.25小時，座椅0.25套，利潤為每輛3千元，問該不該投產(chǎn)，如果投產(chǎn)有利可圖，應(yīng)該如何安排新的生產(chǎn)計劃？153sfsf約束方程系數(shù)矩陣的靈敏度分析當(dāng)大轎車使用鋼材變?yōu)?噸時，x1在最終單純形表中的系數(shù)列向量變?yōu)椋?54sfsf約束方程系數(shù)矩陣的靈敏度分析最終單純形表變?yōu)椋?x1 x

16、2 x3 x4 x5x Cj zj zj -cj 4 3 0 0 0 0.5 0 0.5 -0.4 1 1 1 1 -0.4 00.5 0 -0.5 0.4 0b155sfsf約束方程系數(shù)矩陣的靈敏度分析由于x1對應(yīng)的列向量尚未化為單位向量，先進(jìn)行迭代運算： x1 x2 x3 x4 x5x Cj zj 0 0 2 -0.4 0 zj -cj 4 3 0 0 0 0 0 1 -0.8 1 0 1 2 -1.2 0 1 0 -1 0.8 0b 4 3 2 -0.4 01800156sfsf約束方程系數(shù)矩陣的靈敏度分析檢驗數(shù)仍然有負(fù)數(shù)，繼續(xù)迭代： x1 x2 x3 x4 x5x Cj zj 0.5

17、0 1.5 0 0 zj -cj 4 3 0 0 0 1 0 1 0 1 1.5 1 0.5 0 0 1.25 0 -1.25 1 0b 4.5 3 1.5 0 02400157sfsf約束方程系數(shù)矩陣的靈敏度分析第二問，新增加一種產(chǎn)品，模型中增加了一個新列，設(shè)新產(chǎn)品產(chǎn)量為x6，增加的系數(shù)列向量在最終單純形表中變?yōu)椋?58sfsf約束方程系數(shù)矩陣的靈敏度分析最終單純形表變?yōu)椋?x1 x2 x3 x4 x5 x6 x Cj zj 0 0 1 0.4 0 -1 zj -cj 4 3 0 0 0 3 0 0 1 -0.4 1 0.5 0 1 0.5 -0.4 0 1 1 0 -0.5 0.4 0 -

18、0.25b 4 3 1 0.4 0 22600159sfsf約束方程系數(shù)矩陣的靈敏度分析檢驗數(shù)中存在負(fù)數(shù)，繼續(xù)迭代： x1 x2 x3 x4 x5 x6 x Cj zj 0 0 2 -0.4 2 0 zj -cj 4 3 0 0 0 3 0 0 1 -0.8 2 1 0 1 0 0.4 -2 0 1 0 -0.25 0.2 0.5 0b 4 3 2 -0.4 2 33000160sfsf約束方程系數(shù)矩陣的靈敏度分析仍不是最優(yōu)解，繼續(xù)運算： x1 x2 x3 x4 x5 x6 x Cj zj 0 1 2 0 0 0 zj -cj 4 3 0 0 0 3 0 2 1 0 -2 1 0 2.5 0

19、1 -5 0 1 -0.5 -0.25 0 1.5 0b 4 4 2 0 0 33200161sfsf約束方程系數(shù)矩陣的靈敏度分析求得最優(yōu)解為： x1=200，x2=0，x3=0，x4=500，x5=0，x6=800，Z=3200?？梢?，生產(chǎn)旅行車是有利可圖的，新的生產(chǎn)方案為：生產(chǎn)大轎車200輛，生產(chǎn)旅行車800輛，剩余工時500小時，利潤為3200千元。 162sfsf靈敏度分析小結(jié)價值系數(shù)發(fā)生變化時： 1、如果是非基變量的系數(shù)發(fā)生變化，則只要該變量對應(yīng)的檢驗數(shù)zj-cj在cj變化后仍然大于等于0，則最優(yōu)解不發(fā)生任何變化。 2、如果是基變量的價值系數(shù)發(fā)生變化，則需要重新計算所有檢驗數(shù)，如果所

20、有檢驗數(shù)仍然保持大于等于0，則最優(yōu)基不變，但最優(yōu)解一般會發(fā)生變化。如果有檢驗數(shù)變?yōu)樨?fù)數(shù)，則在原最終單純形表中繼續(xù)迭代，求出最優(yōu)解。163sfsf靈敏度分析小結(jié)當(dāng)資源向量發(fā)生改變時，用公式xB = B-1 b + B-1 b= xB + B-1 b（其中b=(0, 0, bk,0)T ）計算新的b列的值，如果新的b列的值仍然全部大于等于0，則最優(yōu)基不變，但最優(yōu)解的值一般會發(fā)生變化。如果計算出來的新的b列的值出現(xiàn)負(fù)數(shù)，則說明該解是不可行解，用對偶單純形法繼續(xù)進(jìn)行迭代運算，求出新的最優(yōu)解。164sfsf靈敏度分析小結(jié)當(dāng)基變量技術(shù)系數(shù)發(fā)生變化時，求出用公式pi = B-1 pi求出發(fā)生變化的系數(shù)所在列

21、的數(shù)值，代替最終單純形表中原來的列。然后用高斯消元法將該列化為單位向量，計算新的檢驗數(shù)。 1、如果檢驗數(shù)不為負(fù)數(shù)，則最優(yōu)基不變。 2、如果新的檢驗數(shù)變?yōu)樨?fù)數(shù)，則最優(yōu)基將發(fā)生變化，用單純形法繼續(xù)迭代，求出新的最優(yōu)解。165sfsf趣味數(shù)學(xué)你作為幸運觀眾參加了一個節(jié)目，節(jié)目中你面對三個門，其中一個門后一輛汽車，另外兩個門后各有一只羊。主持人請你選擇一扇門，門后的物品將做為你的獎品。當(dāng)你選擇后，主持人先不打開門，而是打開一扇門后有羊的門，然后問你改變不改變你的選擇，請問，你該不該改變你的選擇？166sfsf作業(yè)某公司制作三種產(chǎn)品A、B、C，需要勞動力和原材料兩種資源，要求制訂生產(chǎn)計劃使總利潤最大化。

22、三種產(chǎn)品所需的資源和產(chǎn)生的利潤如下表所示：ABC資源勞動力63545原材料34530利潤315167sfsf作業(yè)1、請建立模型，解決最優(yōu)生產(chǎn)計劃問題。2、求出使得最優(yōu)解不變的產(chǎn)品A的單位利潤變動范圍，問A產(chǎn)品的利潤變?yōu)?時最優(yōu)解變不變？3、假定原材料的市場價格是10元每單位，可以購買15個單位，問以10元的價格采購15單位原材料是否合算？4、請問原材料的供應(yīng)在什么范圍內(nèi)變化時，不必改變生產(chǎn)計劃？168sfsf作業(yè)5、廠家研制出了一種新產(chǎn)品D，生產(chǎn)一單位D需要勞動力4單位，原材料3單位，而每單位的新產(chǎn)品D的利潤為3元。請問：生產(chǎn)計劃是否需要修改？為什么？該如何修改？169sfsf第三章 運 輸

23、問 題170sfsf主要內(nèi)容運輸問題的背景運輸問題的模型運輸問題的表上作業(yè)法運輸問題的應(yīng)用171sfsf運輸問題的背景在經(jīng)濟(jì)建設(shè)中，經(jīng)常碰到大宗物資調(diào)運問題，如煤炭、鋼鐵、糧食等等。主產(chǎn)區(qū)和主銷區(qū)往往不同，需要大規(guī)模的調(diào)運，將物資從產(chǎn)地供應(yīng)到銷地。大型企業(yè)有多個生產(chǎn)基地，銷售遍及全國乃至全世界，如何分配供應(yīng)計劃使經(jīng)濟(jì)效益最好。172sfsf運輸問題模型運輸問題 解決把某種產(chǎn)品從若干個產(chǎn)地調(diào)運到若干個銷地，在每個產(chǎn)地的供應(yīng)量與每個銷地的需求量已知，且各地運輸單價已知的前提下，如何確定一個使總的運輸費用最小的方案。173sfsf運輸問題模型例1. 某公司從兩個產(chǎn)地A1 , A2 ,將貨物運往三個銷

24、地B1 , B2 , B3 ,各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地的每件貨物的運費如下表。問題：應(yīng)如何調(diào)運，才能使得總運輸費用最?。?74sfsf運輸問題模型這是一個產(chǎn)銷平衡的運輸問題把A1， A2的產(chǎn)量全部分配給B1， B2， B3，銷地運費單價產(chǎn)地A1 6 4 6 200A2 6 5 5 300銷 量 150 150 200 B1 B2 B3 產(chǎn)量（件）單 位 運 價 表175sfsf運輸問題模型設(shè)決策變量xij: 產(chǎn)地Ai調(diào)運到Bj的運輸量（i=1,2;j=1,2,3) 銷地運費量產(chǎn)地A1 x11 x12 x13 200A2 x21 x22 x23 300銷 量 150 150

25、200 500 B1 B2 B3 產(chǎn)量（件）產(chǎn)銷平衡表176sfsf運輸問題模型線性規(guī)劃模型177sfsf運輸問題模型一般線性規(guī)劃模型Ai表示某種物資的第i個產(chǎn)地Bj表示某種物資的第j個銷地si表示產(chǎn)地Ai的產(chǎn)量dj表示銷地Bj的銷量cij表示把物資從產(chǎn)地Ai運到銷地Bj的單位運價決策變量xij表示產(chǎn)地Ai調(diào)運到銷地Bj的運輸量178sfsf運輸問題模型xj 0, (i=1,2,m; j=1,2,n)179sfsf運輸問題模型其他的運輸問題模型產(chǎn)銷平衡的運輸問題: 當(dāng) 時求目標(biāo)函數(shù)最大的運輸問題考慮利潤最大、營業(yè)額最大具有能力限制的運輸問題運輸線路的能力限制產(chǎn)銷不平衡的運輸問題產(chǎn)大于銷：假設(shè)銷

26、地銷大于產(chǎn)：假設(shè)產(chǎn)地180sfsf運輸問題模型從模型中看，運輸問題屬于線性規(guī)劃問題的一種。其特殊之處在于：約束條件系數(shù)矩陣全部為0-1元素，而且結(jié)構(gòu)比較松散。系數(shù)矩陣中對應(yīng)xij的系數(shù)向量，其分量中除第i個和第m+j個為1以外，其余的都為0。以例1的模型為例，考察其約束條件系數(shù)矩陣：181sfsf運輸問題模型182sfsf表上作業(yè)法分 析 實 際 問題列出產(chǎn)銷平衡表確定初始調(diào)運方案 西 北 角 法最小元素法求檢驗數(shù)（閉回路法或位勢法）所有檢驗數(shù)0得到最優(yōu)方案算出總的運價 找 出 絕對值最大的負(fù)檢驗數(shù) 用閉回路調(diào)整得出新的調(diào)運方案是否183sfsf表上作業(yè)法表上作業(yè)法解決運輸問題的單純形法針對運

27、輸問題變量多，結(jié)構(gòu)獨特的特點，簡化了運算假設(shè)問題為產(chǎn)銷平衡的運輸問題求解步驟1. 找出初始的基可行解運輸問題有m+n-1個基變量在（mn）產(chǎn)銷平衡表上給出m+n-1個數(shù)字格其相應(yīng)的調(diào)運量就是基變量，格子中填寫的值為基變量的值184sfsf表上作業(yè)法2. 求各非基變量的檢驗數(shù) 在表上計算除了m+n-1個數(shù)字格以外的空格的檢驗數(shù)判別是否達(dá)到最優(yōu)解如已是最優(yōu)解, 則停止計算, 否則轉(zhuǎn)下步3. 確定進(jìn)基變量和出基變量找出新的基可行解在表上用閉回路法調(diào)整4. 重復(fù)第2、3步驟，直至得到最優(yōu)解185sfsf表上作業(yè)法 產(chǎn)銷平衡表B1 B2 Bj Bn 產(chǎn)量限制c1n銷地產(chǎn)地A1 A2 Am c11銷量限制

28、c12c1jx11s1 s2 si Ai sm c21c22c23c24ci1ci2cijcincm1cm2cmjcmnd1 d2 dj dn x12x1nx21x22x2nxm1xm2xmn186sfsf表上作業(yè)法確定初始基可行解西北角法最小元素法西北角法從左上角的變量x11 開始分配運輸量，并使x11的取值盡可能大依次類推，直至給出全部方案為止例2. 喜慶食品公司有三個生產(chǎn)面包的分廠A1, A2, A3,有四個銷售公司B1, B2, B3, B4,其各分廠每日的產(chǎn)量、各銷售公司每日的銷量以及各分廠到各187sfsf表上作業(yè)法銷地運費單價產(chǎn)地A1 3 11 3 10 7A2 1 9 2 8

29、4銷量(噸) 3 6 5 6B1 B2 B3 B4 產(chǎn)量（噸）2020A3 7 4 10 5 9銷售公司的單位運價如下表。產(chǎn)量與銷量的單位為噸，運價的單位為百元/噸。問該公司應(yīng)如何調(diào)運產(chǎn)品在滿足各銷點需求量的前提下，使總運費最少？ 188sfsf表上作業(yè)法可行方案為: x11 = 3, x12 =4, x22 = 2, x23 = 2, x33 = 3, x34 = 6, minf = 135 3 銷地產(chǎn)地A1 A2 B1 B2 B3 B4 產(chǎn)量（噸）A3 311310192874105銷量(噸) 3 6 5 6749 0 4 4 0 2 2 0 2 2 3 0 3 0 6 6 0 0 189

30、sfsf表上作業(yè)法最小元素法西北角法是對西北角的變量分配運輸量最小元素法是就近供應(yīng), 對單位運價最小的變量分配運輸量用最小元素法求的初始基可行解比西北角法的總運費要小通常迭代的次數(shù)可能會少190sfsf表上作業(yè)法可行方案為: x13 = 4, x14 =3, x21 = 3, x23 = 1, x32 = 6, x34 = 3, minf = 86銷地產(chǎn)地A1 A2 B1 B2 B3 B4 產(chǎn)量（噸）A3 311310192874105銷量(噸) 3 6 5 6749 3 0 1 1 4 0 4 0 6 3 0 3 3 0 3 3 0 0 191sfsf表上作業(yè)法注意當(dāng)取定xij 的值之后,會

31、出現(xiàn)Ai 的產(chǎn)量與 Bj 的銷量都為零的情況,只能劃去Ai 行或 Bj列,不能同時劃去用最小元素法時,可能會出現(xiàn)只剩一行或一列的所有格均未填數(shù)或未劃掉的情況,此時在這一行或這一列中除去已填上的數(shù)外均填上零,不能將空格劃掉這樣可保證填過數(shù)或行的格為m+n-1個,即基變量的個數(shù)為m+n-1個192sfsf表上作業(yè)法最優(yōu)解的判定檢驗已得到的運輸方案是否為最優(yōu)方案閉回路法位勢法閉回路法閉回路的構(gòu)成在已給出的調(diào)運方案的運輸表上，從代表非基變量的一個空格出發(fā)沿水平或垂直方向前進(jìn)，只有碰到代表基變量的有數(shù)字的格才能向左或右轉(zhuǎn)直到回到出發(fā)的空格193sfsf表上作業(yè)法銷地產(chǎn)地A1 A2 B1 B2 B3 B4

32、 產(chǎn)量（噸）A3 311310192874105銷量(噸) 3 6 5 6749 3 4 1 6 3 3 1 x11 為非基變量的閉回路194sfsf表上作業(yè)法檢驗數(shù)的計算：從（A1，B1）出發(fā)，增加一單位調(diào)運量（從A1運到B1），為保持產(chǎn)銷平衡，依次做調(diào)整：在（A1，B3）處減少1噸，（A2，B3）處增加1噸，（A2，B1）處減少1噸。調(diào)整方案使運費增加：1*3+（-1）*3+1*2+（-1）*1=1，可見這樣調(diào)整將每單位增加運費1，將1填入（A1，B1）。195sfsf 所有非基變量的閉回路及檢驗數(shù)表上作業(yè)法空 格閉 回 路檢 驗 數(shù)x11 x11 - x13 - x23 - x21 -

33、x11 x12 - x14 - x34 - x32 - x12 x12 x22 x24 x31 x33 x22 -x23 -x13 - x14 - x34 - x32 - x22 x24 - x23 - x33 - x14 - x24 x31 -x34 -x14 - x13 - x23 - x21 - x31 x33 - x34 - x14 - x13 - x33 121-11012196sfsf表上作業(yè)法閉回路法在以空格為始點和終點，其他頂點均為數(shù)字點的閉回路上將該空格的運輸量調(diào)整為1，則其他頂點在保持供銷平衡的基礎(chǔ)上，運輸量增加或減少1計算出該回路的總費用的變化值該變化值作為該非基變量的檢

34、驗數(shù)若所有檢驗數(shù)都大于零，則原基可行解為最優(yōu)解否則進(jìn)一步迭代找出最優(yōu)解用閉回路法求檢驗數(shù)要對每一個空格找一條閉回路當(dāng)產(chǎn)銷點多時，較繁雜197sfsf表上作業(yè)法位勢法將運輸表上的每一行賦予值ui ,每一列賦予值vj xij為基變量，則滿足cij - ui - vj = 0 令u1 =0，可先計算出ui 和vj 的值xij為非基變量，則利用ui 和vj 的值，計算出其檢驗數(shù) ij = cij - ui - vj 若所有檢驗數(shù)ij 均大于零，則原基可行解為最優(yōu)解否則進(jìn)一步迭代找出最優(yōu)解198sfsf表上作業(yè)法例1中檢驗數(shù)的計算：令u1=0，將基變量的檢驗數(shù)列出：由基變量x14 ，有c14 (u1+

35、v4 )=0由基變量x13 ，有c13 (u1+ v3 )=0由基變量x21 ，有c21 (u2+ v1 )=0由基變量x23 ，有c23 (u2+ v3 )=0由基變量x32 ，有c32 (u3+ v2 )=0由基變量x34 ，有c34 (u3+ v4 )=0199sfsf表上作業(yè)法即：8(u1+v4)=0，5(u1+v3)=0 1(u2+v1)=0，4(u2+v3)=0 3(u3+v2)=0，10(u3+v4)=0又知u1=0，所以得到： u1=0，u2=-1， u3=-5，v1=2,v2=9,v3=3, v4=10。因非基變量的檢驗數(shù)ij = cij - ui - vj ，已知所有ui

36、、vj的值，可以在表格中計算所有非基變量的檢驗數(shù)。200sfsf銷地產(chǎn)地A1 (1) (2) 4 3 0 A2 3 (1) 1 (-1) -12 9 3 10 B1 B2 B3 B4 ui A3 (10) 6 (12) 3 -5311310192874105vj表上作業(yè)法201sfsf表上作業(yè)法改進(jìn)運輸方案的方法閉回路調(diào)整法選最小的負(fù)檢驗數(shù)，以它對應(yīng)的非基變量為進(jìn)基變量找出以該非基變量空格xij 為出發(fā)點的閉回路盡量增加xij 的運輸量將該回路中的偶數(shù)頂點調(diào)運量的最小值取為xij 的運輸量將所有回路中的偶數(shù)頂點的調(diào)運量減去該值，而奇數(shù)頂點加上該值，得到新的調(diào)運方案202sfsf銷地產(chǎn)地A1 (

37、1) (2) 4 3 0 A2 3 (1) 1 (-1) -12 9 3 10 B1 B2 B3 B4 ui A3 (10) 6 (12) 3 -5311310192874105vj表上作業(yè)法203sfsf表上作業(yè)法銷地產(chǎn)地A1 4（+1） 3（-1） 7A2 3 1（-1） （+1） 4銷 量 3 6 5 6B1 B2 B3 B4 產(chǎn) 量A3 6 3 9204sfsf表上作業(yè)法調(diào)整后的運輸方案如下銷地產(chǎn)地A1 5 2 7A2 3 1 4銷 量 3 6 5 6B1 B2 B3 B4 產(chǎn) 量A3 6 3 9運輸量205sfsf表上作業(yè)法用位勢法再計算出檢驗數(shù)如下表：所有檢驗數(shù)都大于零，最小費用為

38、85元銷地產(chǎn)地A1 (0) (2) 5 2 0 A2 3 (2) （1） 1 -23 9 3 10 B1 B2 B3 B4 ui A3 (9) 6 (12) 3 -5311310192874105vj206sfsf表上作業(yè)法如何找多個最優(yōu)方案識別是否有最優(yōu)方案的方法與單純形法一樣只需檢查最優(yōu)方案中是否存在非基變量的檢驗數(shù)為零將檢驗數(shù)為零的非基變量進(jìn)入基，對運輸方案進(jìn)行調(diào)整，就可得到另一個最優(yōu)方案見下例207sfsf表上作業(yè)法由前面的表中可知： x11的檢驗數(shù)11 =0令x11進(jìn)入基，調(diào)整的運輸方案為另一個最優(yōu)方案 銷地產(chǎn)地A1 （+2） 5 2（-2） 7 A2 3（-2） 1（+2） 4 B

39、1 B2 B3 B4 產(chǎn) 量 A3 6 3 9 銷 量 3 6 5 6208sfsf表上作業(yè)法此時的最小運費仍為85銷地產(chǎn)地A1 2 5 7 A2 1 3 4 B1 B2 B3 B4 產(chǎn) 量 A3 6 3 9 銷 量 3 6 5 6209sfsf產(chǎn)銷不平衡的運輸問題對于產(chǎn)大于銷的運輸問題，可以用增加一個虛擬銷地的方法轉(zhuǎn)化為產(chǎn)銷平衡的運輸問題，任何一個產(chǎn)地運往虛擬銷地的運費均設(shè)為0。對于銷大于產(chǎn)的運輸問題，可以用增加一個虛擬產(chǎn)地的方法轉(zhuǎn)化為產(chǎn)銷平衡的運輸問題，虛擬產(chǎn)地運往任何一個銷地的運費均設(shè)為0。210sfsf產(chǎn)銷不平衡的運輸問題例2：某產(chǎn)品的供求表如下，請給出最佳調(diào)運方案。銷地運費單價產(chǎn)地A

40、1 3 11 3 10 7A2 1 9 2 8 7銷量(噸) 3 6 5 6B1 B2 B3 B4 產(chǎn)量（噸）2320A3 7 4 10 5 9211sfsf產(chǎn)銷不平衡的運輸問題首先轉(zhuǎn)化為產(chǎn)銷平衡的運輸問題：B1 B2 B3 B4 B5 產(chǎn)量銷地運費單價產(chǎn)地A1 3 11 3 10 0 7A2 1 9 2 8 0 7銷量(噸) 3 6 5 6 32323A3 7 4 10 5 0 9212sfsf產(chǎn)銷不平衡的運輸問題用最小元素法求出初始可行解：B1 B2 B3 B4 B5 產(chǎn)量銷地運費單價產(chǎn)地A1 1 3 3 7A2 3 4 7銷量(噸) 3 6 5 6 32323A3 6 3 9213sfs

41、f產(chǎn)銷不平衡的運輸問題用位勢法求出非基變量的檢驗數(shù)得：B1 B2 B3 B4 B5 產(chǎn)量銷地運費單價產(chǎn)地A1 （1） （2） 1 3 3 7A2 3 （1） 4 （-1） （0） 7銷量(噸) 3 6 5 6 32323A3 （10） 6 （12） 3 （5） 9214sfsf產(chǎn)銷不平衡的運輸問題檢驗數(shù)存在負(fù)數(shù)，用閉回路法調(diào)整：B1 B2 B3 B4 B5 產(chǎn)量銷地運費單價產(chǎn)地A1 1（+3） 3（-3） 3 7A2 3 4（-3） （+3） 7銷量(噸) 3 6 5 6 32323A3 6 3 9215sfsf產(chǎn)銷不平衡的運輸問題調(diào)整后的運輸方案為：B1 B2 B3 B4 B5 產(chǎn)量銷地運費

42、單價產(chǎn)地A1 （1） （3） 4 （1） 3 7A2 3 （2） 1 3 （1） 7銷量(噸) 3 6 5 6 32323A3 （9） 6 （11） 3 （4） 9216sfsf產(chǎn)銷不平衡的運輸問題運輸費用為：80最優(yōu)方案為: x13 = 4, x15 =3, x21 = 3, x23 = 1, x24 = 3 ，x32 = 6, x34 = 3。217sfsf產(chǎn)銷不平衡的運輸問題思考題： 產(chǎn)銷不平衡的運輸問題轉(zhuǎn)化為產(chǎn)銷平衡的運輸問題后，虛擬產(chǎn)地運出的產(chǎn)品或運往虛擬銷地的產(chǎn)品的單位運輸費用均設(shè)為0，為什么？如果設(shè)為M行不行？設(shè)為任意數(shù)值行不行？為什么？218sfsf運輸問題作業(yè)1、求解運輸問題

43、：B1 B2 B3 產(chǎn)量（噸）銷地運費單價產(chǎn)地A1 20 16 24 300A2 10 10 8 500銷量(噸) 200 400 300 900900A3 80 18 10 100219sfsf運輸問題作業(yè)1、求解運輸問題：B1 B2 B3 產(chǎn)量銷地運費單價產(chǎn)地A1 10 16 32 15A2 14 22 40 7銷量 12 8 20 A3 22 24 34 16220sfsf第四章 整數(shù)規(guī)劃221sfsf主要內(nèi)容整數(shù)規(guī)劃的特點整數(shù)規(guī)劃的圖解法整數(shù)規(guī)劃的計算機(jī)解法整數(shù)規(guī)劃的分枝定界法整數(shù)規(guī)劃的應(yīng)用222sfsf整數(shù)規(guī)劃的特點問題的提出在一般的線性規(guī)劃中，最優(yōu)解往往是分?jǐn)?shù)或小數(shù)在許多實際問題中

44、，要求全部或部分變量的取值必須是整數(shù)安排上班的人數(shù)裁剪鋼材的根數(shù)生產(chǎn)機(jī)器的臺數(shù)分類純整數(shù)規(guī)劃：所有變量為非負(fù)整數(shù)01 規(guī)劃：所有變量取值為0、1混合整數(shù)規(guī)劃：部分變量為非負(fù)整數(shù)223sfsf整數(shù)規(guī)劃的特點求解方法四舍五入法或湊整法變量取值很大時，此方法得到的解與最優(yōu)解差別不大但當(dāng)問題規(guī)模較大時，計算工作量很大如,最優(yōu)解為(4.6, 5.5)；10個變量要比較 次，最優(yōu)解不一定在這些組合中224sfsf整數(shù)規(guī)劃的特點比較(4,3),(4,2),(3,3)不是可行解(3,2)是可行解,不是最優(yōu)解z=13最優(yōu)解(4,1), z=14123 x112302x1 +3 x2 =14 x24x1 + 0.

45、5x2 =4.5456756789(3.25,2.5)225sfsf整數(shù)規(guī)劃的特點常用方法二變量的圖解法分枝定界方法割平面法分配問題的匈牙利方法0-1型整數(shù)規(guī)劃的隱枚舉法226sfsf整數(shù)規(guī)劃的特點例1. 有一份說明書,要分別翻譯成英、日、德、俄四種文字，交甲、乙、丙、丁四個人去完成。因各個的專長不同，所需時間如表所示。問應(yīng)如何分配，使這四個人分別完成這四項任務(wù)總的時間最小？人工作英文日文德文俄文甲 乙 丙 丁2 10 9 715 4 14 813 14 16 11 4 15 13 9227sfsf整數(shù)規(guī)劃的特點引入0-1邏輯變量1， 分配第i個人完成第j項任務(wù)0， 不分配第i個人完成第j項任

46、務(wù)228sfsf整數(shù)規(guī)劃的圖解法基本思想在可行域中尋找使目標(biāo)值達(dá)到最大的整數(shù)解不使用四舍五入或截尾取整法例2. 某公司擬用集裝箱托運甲、乙兩種貨物，每件貨物的體積、重量、利潤及托運限制如下表體積（立方英尺）利潤（百元）甲乙托運限制1952731 365 （立方英尺）440140（百千克）23貨物重量（百千克）229sfsf整數(shù)規(guī)劃的圖解法 甲種貨物至多托運4件，問兩種貨物各托運多少件可 使獲利最大？這是一個整數(shù)規(guī)劃問題模型為 max z = 2x1 + 3x2 195x1 + 273x2 1 365 4x1 + 40 x2 140 x1 4 x1 ，x2 0，且為整數(shù)230sfsf整數(shù)規(guī)劃的圖

47、解法用圖解法解該整數(shù)規(guī)劃問題2x1 + 3x2 = 14123 x1123 x2442x1 + 3x2 = 6*2x1 + 3x2 = 14.66該問題的線性規(guī)劃的最優(yōu)解為 x1= 2.44, x2 = 3.26,目標(biāo)函數(shù)的最優(yōu)值為14.66該解不是整數(shù)規(guī)劃的可行解平移目標(biāo)函數(shù)等直線,相交于整數(shù)規(guī)劃的可行點x1= 2, x2 = 4,目標(biāo)函數(shù)的最優(yōu)值為14*231sfsf整數(shù)規(guī)劃的圖解法用四舍五入或截尾法得到的線性規(guī)劃的整數(shù)解不是整數(shù)規(guī)劃的最優(yōu)解或可行解如,x1= 2, x2 = 3,目標(biāo)函數(shù)值為13,不是最優(yōu)解x1= 3, x2 = 3,或x1= 2, x2 = 4; x1= 3, x2 =

48、 4,都不是整數(shù)規(guī)劃的可行解性質(zhì)整數(shù)規(guī)劃的最大目標(biāo)值不會超過線性規(guī)劃的最大目標(biāo)值即整數(shù)規(guī)劃的最小目標(biāo)值不會小于線性規(guī)劃的最小目標(biāo)值232sfsf分枝定界法意義和作用求解整數(shù)線性規(guī)劃的有效方法既能解決純整數(shù)規(guī)劃,又能解決混合整數(shù)規(guī)劃大多數(shù)軟件都是基于該方法實施思路先求出相應(yīng)線性規(guī)劃的最優(yōu)解定界:若該解不符合整數(shù)條件,求出整數(shù)規(guī)劃的上下界分枝:把線性規(guī)劃的可行域分成子區(qū)域，再求解這些子區(qū)域上的線性規(guī)劃問題不斷縮小整數(shù)規(guī)劃上下界的距離,最后求出最優(yōu)解233sfsf分枝定界法分枝定界過程不斷縮小最優(yōu)目標(biāo)函數(shù)值 的上界 和下界 的距離通過分枝使得上界 越來越小，而下界 越來越大最優(yōu)解的存在性當(dāng) 時，整數(shù)

49、規(guī)劃的最優(yōu)解已求出即，最優(yōu)解為其目標(biāo)值取此下界的對應(yīng)的線性規(guī)劃的整數(shù)可行解234sfsf分枝定界法例3. 用分枝定界方法求解例2.的整數(shù)規(guī)劃 max z = 2x1 + 3x2 195x1 + 273x2 1 365 4x1 + 40 x2 140 x1 4 x1 ，x2 0，且為整數(shù)235sfsf分枝定界法先求出相應(yīng)的線性規(guī)劃1的解 線性規(guī)劃1.max z = 2x1 + 3x2 195x1 + 273x2 1 365 4x1 + 40 x2 140 x1 4 x1 ，x2 0236sfsf分枝定界法最優(yōu)解為 x1= 2.44, x2 = 3.26目標(biāo)函數(shù)的最優(yōu)值為z1= 14.66x1=

50、2.44, x2 = 3.26 不是整數(shù)規(guī)劃的最優(yōu)解確定整數(shù)規(guī)劃最優(yōu)目標(biāo)值 的初始上界 和下界由性質(zhì)1.知,用觀察法求出該整數(shù)規(guī)劃的一個可行解,將其目標(biāo)值 作為用截尾法對線性規(guī)劃的最優(yōu)解進(jìn)行處理得到x1= 2, x2 =3是整數(shù)規(guī)劃的可行解令其目標(biāo)值為 ,即237sfsf分枝定界法分枝:將線性規(guī)劃1分為兩枝任取x1= 2.44, x2 = 3.26 中的一個或選取最遠(yuǎn)離整數(shù)的那一個,如, x1= 2.44如x1取整數(shù),則可在 x1 2 或 x1 3中取值將線性規(guī)劃1分成兩枝: 線性規(guī)劃2和線性規(guī)劃3 max z = 2x1 + 3x2 195x1 + 273x2 1 365 4x1 + 40

51、x2 140 x1 4 x1 2 x1 ，x2 0 max z = 2x1 + 3x2 195x1 + 273x2 1 365 4x1 + 40 x2 140 x1 4 x1 3 x1 ，x2 0238sfsf分枝定界法求解線性規(guī)劃2最優(yōu)解為x1= 2, x2 = 3.30目標(biāo)函數(shù)的最優(yōu)值為z2= 13.90 max z = 2x1 + 3x2 195x1 + 273x2 1 365 4x1 + 40 x2 140 x1 4 x1 2 x1 ，x2 0239sfsf分枝定界法求解線性規(guī)劃3最優(yōu)解為x1= 3, x2 = 2.86目標(biāo)函數(shù)的最優(yōu)值為z3= 14.58 max z = 2x1 +

52、3x2 195x1 + 273x2 1 365 4x1 + 40 x2 140 x1 4 x1 3 x1 ，x2 0240sfsf分枝定界法修改整數(shù)規(guī)劃最優(yōu)目標(biāo)值的 上界和下界將 , 修改為定下界:用截尾法分別求出線性規(guī)劃2和3的整數(shù)規(guī)劃的可行解 x1= 2, x2 = 3,和 x1= 3, x2 = 2其目標(biāo)值分別為13和12令在線性規(guī)劃2和3中,選擇上界最大的線性規(guī)劃3進(jìn)行分枝線性規(guī)劃3的最優(yōu)解為x1= 3, x2 = 2.86將x2 = 2.86分成x2 2 和 x2 3兩種情況將線性規(guī)劃3分成兩枝: 線性規(guī)劃4和線性規(guī)劃5241sfsf分枝定界法求解線性規(guī)劃4最優(yōu)解為x1= 4, x2

53、 = 2目標(biāo)函數(shù)的最優(yōu)值為z4= 14 max z = 2x1 + 3x2 195x1 + 273x2 1 365 4x1 + 40 x2 140 x1 4 x1 3 x2 2 x1 ，x2 0242sfsf分枝定界法求解線性規(guī)劃5無可行解 max z = 2x1 + 3x2 195x1 + 273x2 1 365 4x1 + 40 x2 140 x1 4 x1 3 x2 3 x1 ，x2 0243sfsf分枝定界法進(jìn)一步修改整數(shù)規(guī)劃最優(yōu)目標(biāo)值 的上界和下界將 的值修改為線性規(guī)劃2的整數(shù)可行解為x1= 2, x2 = 3,目標(biāo)值為13線性規(guī)劃4的整數(shù)可行解為,目標(biāo)值為14令此時, 且線性規(guī)劃4

54、的目標(biāo)值為14,最優(yōu)解為x1= 4,x2 = 2244sfsf分枝定界法線性規(guī)劃1 z1= 14.66 x1= 2.44, x2 = 3.26線性規(guī)劃2 z2= 13.90 x1= 2 x2 = 3.30 x1 2線性規(guī)劃3 z3= 14.58 x1= 3 x2 = 2.86x1 3線性規(guī)劃4 z4= 14 x1 = 4 x2 = 2線性規(guī)劃5無可行解x2 2x2 3245sfsf分枝定界法求解步驟第一步：求解問題BB沒有可行解，則A也沒有可行解，求解過程停止B有最優(yōu)解，且符合A的整數(shù)條件，則B的最優(yōu)解即為A的最優(yōu)解B有最優(yōu)解，但不符合A的整數(shù)條件，記其目標(biāo)值為z1AB整數(shù)規(guī)劃問題線性規(guī)劃問題

55、246sfsf分枝定界法第二步：確定A的最優(yōu)目標(biāo)值 的上、下界上界用觀察法找出A的一個整數(shù)可行解，其目標(biāo)值作為 的下界第三步：最優(yōu)性判斷如果 ，則終止，否則，轉(zhuǎn)下步第四步：構(gòu)造分枝條件在B的最優(yōu)解中選一個最遠(yuǎn)離整數(shù)要求的變量，設(shè)為 xj= bj ,令bj為bj的下整數(shù)兩個約束條件為247sfsf分枝定界法第五步：求解分枝B1、 B2修改問題A的最優(yōu)目標(biāo)值 的上、下界取B1、 B2最優(yōu)目標(biāo)值的最大值為新的上界 的值用觀察法求出B1、 B2問題中的各一個整數(shù)解，選其中最大的為新的下界 的值第六步：比較與剪枝將各分枝最優(yōu)目標(biāo)值中小于 的分枝剪去返回第三步248sfsf整數(shù)規(guī)劃的應(yīng)用分配或指派問題(A

56、ssignment problem) 問題現(xiàn)有n項任務(wù)分配給n個人去完成,并指定每人完成其中的一項,每項只交給一個人去完成,應(yīng)任何分配使總的效率為最高模型引入0-1邏輯變量1， 分配第i個人完成第j項任務(wù)0， 不分配第i個人完成第j項任務(wù)249sfsf整數(shù)規(guī)劃的應(yīng)用250sfsf第五章 圖與網(wǎng)絡(luò)模型251sfsf主要內(nèi)容引言圖與網(wǎng)絡(luò)的基本概念甘特圖最短路問題最小樹問題中國郵遞員問題最大流問題最小費用最大流問題252sfsf引言起源18世紀(jì)，多數(shù)問題圍繞著游戲而產(chǎn)生1736年，歐拉解決了有名的哥尼斯堡七橋問題一筆畫問題ABDCBACD253sfsf引言一筆畫問題254sfsf引言著名的問題Ham

57、ilton 問題1859年，Hamilton發(fā)明了一種游戲在一個實心的12面體的20個頂點上標(biāo)上世界上有名的城市的名字要求游戲者從某一城市出發(fā)，遍及各城市一次且僅一次，最后回到出發(fā)點255sfsf引言四色猜想問題在一個平面或球面上的任何地圖上只能用四種顏色著色使得任何兩個相鄰的國家都具有不同的顏色兩個國家相鄰是指具有一段公共的邊界1976年，三位美國人，用1200個小時證明了該猜想，但不理想256sfsf引言基爾霍夫用圖代替電網(wǎng)絡(luò)并發(fā)展了樹的理論凱萊應(yīng)用圖論解決了化學(xué)的分子結(jié)構(gòu)問題中國郵遞員問題發(fā)展階段第一階段：18世紀(jì)中葉19世紀(jì)中葉圖論的萌芽時期第二階段：19世紀(jì)中葉20世紀(jì)中葉圖論的大量

58、問題出現(xiàn)第三階段：20世紀(jì)中葉以后飛速發(fā)展時期257sfsf基本概念圖（無向圖）表明研究對象和這些對象之間的相互聯(lián)系用點表示研究對象，記為V用邊表示研究對象之間的相互關(guān)系，記為E圖可用點邊的集合表示為 G =（V，E）有向圖表明從點v1到v2 之間的關(guān)系可用弧 表示D =（V，A）如，家譜圖258sfsf基本概念鏈無向圖G中點邊交錯的序列( v1 ,e1,v2 ,e2, vk ,ek vk+1 )vi vj , ei=vi , vi+1 圈在一條鏈中.若v1 = vk+1 連通圖若圖G中任意兩個不同點之間至少存在一條鏈v1v2v5v4v3e1e7e8e2e3e4e5e6e9v6v7259sfs

59、f基本概念路有向圖D中點邊交錯的序列( v1 ,a1,v2 ,a2, vk ,ak vk+1 )ai aj , ai=vi , vi+1 回路v1 = vk+1的路賦權(quán)圖無向圖G中的每一條邊對應(yīng)了一個數(shù)值wij 有向圖D中的每一條弧對應(yīng)了一個數(shù)值cijv1v2v5v4v3a1a7a2a3a4a5a6260sfsf基本概念網(wǎng)絡(luò)賦權(quán)圖D中, 指定發(fā)點、收點。其余點為中間點賦權(quán)數(shù)cij為容量261sfsf甘特圖甘特圖（Gantt chart ）又叫橫道圖、條狀圖(Bar chart)。它是以圖示的方式通過活動列表和時間刻度形象地表示出任何特定項目的活動順序與持續(xù)時間。它是在第一次世界大戰(zhàn)時期發(fā)明的，

60、以亨利L甘特先生的名字命名，他制定了一個完整地用條形圖表進(jìn)度的標(biāo)志系統(tǒng)。甘特圖內(nèi)在思想簡單，基本是一條線條圖，橫軸表示時間，縱軸表示活動（項目），線條表示在整個期間上計劃和實際的活動完成情況。它直觀地表明任務(wù)計劃在什么時候進(jìn)行，及實際進(jìn)展與計劃要求的對比。管理者由此極為便利地弄清一項任務(wù)（項目）還剩下哪些工作要做，并可評估工作進(jìn)度。262sfsf甘特圖甘特圖是基于作業(yè)排序的目的，將活動與時間聯(lián)系起來的最早嘗試之一，該圖能幫助企業(yè)描述對諸如工作中心、超時工作等資源的使用圖。當(dāng)用于負(fù)荷時，甘特圖可以顯示幾個部門、機(jī)器或設(shè)備的運行和閑置情況。這表示了該系統(tǒng)的有關(guān)工作負(fù)荷狀況，這樣可使管理人員了解何種