工程碩士運(yùn)籌學(xué)課件及重點(diǎn)

1、1,工程碩士運(yùn)籌學(xué),內(nèi)蒙古工業(yè)大學(xué)管理學(xué)院,課程內(nèi)容,緒論線性規(guī)劃基礎(chǔ)線性規(guī)劃的圖解法、用Excel解LP問題整數(shù)規(guī)劃運(yùn)輸問題目標(biāo)規(guī)劃圖論動(dòng)態(tài)規(guī)劃網(wǎng)絡(luò)計(jì)劃技術(shù),2,3,第0章,緒論Introductions to Operations Research,運(yùn)籌學(xué)的實(shí)用價(jià)值,4,,ZARA（全球1500家門店）、P&G（15億）,5,運(yùn)籌學(xué)學(xué)科特點(diǎn),1- 科學(xué)性它是在科學(xué)方法論的指導(dǎo)下通過一系列規(guī)范化步驟。,6,

2、運(yùn)籌學(xué)學(xué)科特點(diǎn),2- 實(shí)踐性運(yùn)籌學(xué)以實(shí)際問題為分析對(duì)象；分析結(jié)果必須用于指導(dǎo)實(shí)際系統(tǒng)的運(yùn)行。適應(yīng)性和魯棒性Robustness，原是統(tǒng)計(jì)學(xué)中的一個(gè)專門術(shù)語，20世紀(jì)70年代初開始在控制理論的研究中流行起來，用以表征控制系統(tǒng)對(duì)特性或參數(shù)擾動(dòng)的不敏感性。即當(dāng)應(yīng)用問題的背景受到一定程度的干擾時(shí)，最優(yōu)解能夠繼續(xù)正常運(yùn)行的程度。,7,運(yùn)籌學(xué)學(xué)科特點(diǎn),3- 系統(tǒng)性用系統(tǒng)的觀點(diǎn)來分析研究對(duì)象，通過協(xié)調(diào)各組成部分之間的關(guān)系和利害沖突，使整個(gè)系

3、統(tǒng)達(dá)到最優(yōu)狀態(tài)。實(shí)際問題的多目標(biāo)“天性”，各目標(biāo)沒有統(tǒng)一的度量標(biāo)準(zhǔn)。,8,運(yùn)籌學(xué)學(xué)科特點(diǎn),4- 優(yōu)化方案強(qiáng)調(diào)是最優(yōu)的解決方案，而不是任意的一個(gè)可行方案，或者只是對(duì)現(xiàn)狀的“改進(jìn)”方案；當(dāng)研究問題從數(shù)學(xué)分析上存在多個(gè)或無窮最優(yōu)解時(shí)，不刻意去搜索出所有最優(yōu)解，而是只需找出其中一個(gè)最優(yōu)解；當(dāng)研究問題過于復(fù)雜時(shí)，運(yùn)籌學(xué)更傾向于搜索出一個(gè)“效率解”。,9,運(yùn)籌學(xué)學(xué)科特點(diǎn),5- 綜合性運(yùn)籌學(xué)研究是一種綜合性的研究，它涉及問題的方方面面，應(yīng)

4、用多學(xué)科的知識(shí)，因此，要由一個(gè)各方面的專家組成的小組來完成。,運(yùn)籌學(xué)求解問題的一般思路,1. 明確問題，收集數(shù)據(jù)邊界、目標(biāo)量化、變量、參數(shù)、約束2. 建立模型，數(shù)學(xué)模型：模型檢驗(yàn)3. 選取方法，進(jìn)行求解：遺傳算法等4. 驗(yàn)證方案，實(shí)施方案5. 方案程序化，模塊化6. 方案實(shí)施，效果分析,10,運(yùn)籌學(xué)求解問題的一般思路,11,12,第1章,線性規(guī)劃基礎(chǔ)(Introduction to Linear Programming),

5、目標(biāo),1. 常見線性規(guī)劃問題的數(shù)學(xué)建模思路2. 建模的適用范圍3. “解”的概念4. 圖解法5. EXCEL求解一般線性規(guī)劃問題（練習(xí)）,13,14,線性規(guī)劃的定義,在滿足一組線性約束條件（等式或不等式）的前提下，使得某一個(gè)線性目標(biāo)函數(shù)取得極值（最大值或最小值）。這類問題的模型及其優(yōu)化求解技術(shù)，被統(tǒng)稱為線性規(guī)劃(Linear Programming, LP)。In mathematics, LP problems are o

6、ptimization problems in which the objective function and the constraints are all linear.,線性規(guī)劃數(shù)學(xué)模型,線性規(guī)劃問題的一般模型,15,線性規(guī)劃數(shù)學(xué)模型,模型特點(diǎn)1- 所有表達(dá)式均為線性表達(dá)式2-目標(biāo)為求目標(biāo)函數(shù)Z的最大值(max)或最小值(min)3- 約束條件為” ≥/≤/=”，沒有”>/<”！4- 通常要求決策變量取值非負(fù)

7、,16,17,應(yīng)用問題示例(1)-生產(chǎn)計(jì)劃,F公司每周根據(jù)原材料M1和M2的采購數(shù)量來安排其產(chǎn)品A、B和C的生產(chǎn)計(jì)劃。問：這3種產(chǎn)品各應(yīng)生產(chǎn)多少，能使F公司獲得最大的利潤(rùn)？,應(yīng)用問題示例(2)-生產(chǎn)計(jì)劃,A公司用M1,M2,M3和M4四種原材料，生產(chǎn)產(chǎn)品P1,P2和P3。這三種產(chǎn)品由這四種原材料混合而成（產(chǎn)品重量為四種原材料重量之和）。,18,應(yīng)用問題示例(2),原材料M3和M4采購量超過市場(chǎng)供應(yīng)總量的一半。采購預(yù)算費(fèi)用為25萬元人

8、民幣。問：根據(jù)產(chǎn)品的市場(chǎng)價(jià)格以及原材料價(jià)格，公司應(yīng)如何采購以獲得最多的利潤(rùn)？,19,應(yīng)用問題示例(2),建模思路1--,20,應(yīng)用問題示例(2),正確的建模方法--,21,應(yīng)用問題示例(2),22,應(yīng)用問題示例(3)-財(cái)務(wù)計(jì)劃,某集團(tuán)公司未來6年年初的現(xiàn)金需求（萬元）如下所示。為此，公司決定在今年年底一次性劃撥一筆資金，未來6年不再劃撥。,23,應(yīng)用問題示例(3),公司可以通過多種投資形式減少資金的需求：1- 銀行一年期的定期存款，

9、年利率為3%；2- 國債（只能在第1年年初購買；國債的實(shí)際購買價(jià)格要高于其票面價(jià)格，且只能在到期日按票面價(jià)格收回本金）問：集團(tuán)公司最少需要?jiǎng)潛芏嗌儋Y金，并如何投資，才能滿足未來6年的現(xiàn)金需求？,24,應(yīng)用問題示例(3),由于6年內(nèi)不再追加投資，因此6年內(nèi)的投資（銀行定期存款方式）必然不能超過當(dāng)年現(xiàn)金需求的余額。并且，由于投資總能夠獲得更多的回報(bào)（103%），所以投資等于當(dāng)年現(xiàn)金需求的余額！,25,應(yīng)用問題示例(3),采用表格形式更加

10、直觀展示出投資與回報(bào)。年末的收益可以作為下一年年初的投資。,26,應(yīng)用問題示例(3),27,應(yīng)用問題示例(3),完整問題模型如下：,28,,應(yīng)用問題示例(4)-生產(chǎn)計(jì)劃,N公司生產(chǎn)兩種產(chǎn)品P1和P2，這2種產(chǎn)品都是由組件C1, C2和C3各1件裝配而成。需求為1600件P1和1000件P2。共有100個(gè)正常工時(shí)和最多60個(gè)加班工時(shí)，每個(gè)加班工時(shí)將額外增加12元的運(yùn)營成本。問：如何安排生產(chǎn)和外購，才是最經(jīng)濟(jì)？,29,應(yīng)用問題示例

11、(4),根據(jù)問題描述，可以定義自行生產(chǎn)和外購的組件數(shù)量為決策變量。并且，外購組件的數(shù)量與生產(chǎn)能力也有關(guān)，因此需要定義實(shí)際加班工時(shí)為決策變量，即：,30,應(yīng)用問題示例(4),31,應(yīng)用問題示例(5)-運(yùn)輸與分銷,運(yùn)輸與分銷問題問：如何安排物流路線，實(shí)現(xiàn)總運(yùn)輸成本最小。,32,,應(yīng)用問題示例(5),定義決策變量為各條路線上的運(yùn)輸量，各變量對(duì)應(yīng)的路線如下所示。,33,,應(yīng)用問題示例(5),對(duì)于此類以圖形方式給出的物流問題，存在以下函數(shù)關(guān)系，

12、即圖中每個(gè)節(jié)點(diǎn)，都必須滿足“輸入=輸出”。,34,應(yīng)用問題示例(5),源頭節(jié)點(diǎn)“工廠1 ～ 3”，關(guān)系為“產(chǎn)量+運(yùn)入量=運(yùn)出量”。,35,應(yīng)用問題示例(5),中間節(jié)點(diǎn)“分銷中心”，關(guān)系為“運(yùn)入量=運(yùn)出量”。,36,應(yīng)用問題示例(5),終止節(jié)點(diǎn)“倉庫1 ～ 2”，關(guān)系為“運(yùn)入量=運(yùn)出量+需求量”。,37,應(yīng)用問題示例(6)-套裁下料問題,某建筑公司需要鋼管規(guī)格和數(shù)量分別為：3m的600根、4m的300根、5m的200根。如果只能選擇購入

13、長(zhǎng)度為11m的鋼管自行切割，M公司至少應(yīng)采購多少根11m的鋼管？,38,應(yīng)用問題示例(6),某建筑公司需要鋼管規(guī)格和數(shù)量分別為：3m的600根、4m的300根、5m的200根。如果只能選擇購入長(zhǎng)度為11m的鋼管自行切割，M公司至少應(yīng)采購多少根11m的鋼管？,39,,應(yīng)用問題示例(6),40,,應(yīng)用問題示例(6),思考題：如果目標(biāo)函數(shù)改為“如果購入這些長(zhǎng)度為11m的鋼管自行切割，RE公司應(yīng)如何切割廢料最少？”,41,42,線性規(guī)劃模型的

14、假設(shè)條件,比例性假定：要求目標(biāo)函數(shù)值、約束條件左端取值與決策變量的取值呈嚴(yán)格的比例關(guān)系。,線性規(guī)劃模型的假設(shè)條件,43,44,線性規(guī)劃問題的標(biāo)準(zhǔn)圖解法,對(duì)于只包含2個(gè)變量的線性規(guī)劃問題，可以通過標(biāo)準(zhǔn)圖解法來求解。其解題步驟為：,45,標(biāo)準(zhǔn)圖解法示例1,用標(biāo)準(zhǔn)圖解法求下面的線性規(guī)劃問題（例1-8）,,標(biāo)準(zhǔn)圖解法示例1,46,,,,,標(biāo)準(zhǔn)圖解法示例2,應(yīng)用標(biāo)準(zhǔn)圖解法求解線性規(guī)劃問題（例1-9）,47,,標(biāo)準(zhǔn)圖解法示例2,48,,,,,49,

15、線性規(guī)劃問題的重要推論,1- 如果線性規(guī)劃問題的可行域非空且有界，那么線性規(guī)劃問題一定有最優(yōu)解；2- 如果線性規(guī)劃問題的可行域無界，那么該問題可能有無界解；3- 如果線性規(guī)劃問題的最優(yōu)解在可行域的兩個(gè)頂點(diǎn)上同時(shí)得到，那么這兩個(gè)頂點(diǎn)連線上的所有點(diǎn)都是最優(yōu)解（有無窮多最優(yōu)解）；4- 如果線性規(guī)劃問題的可行域?yàn)榭?，意味著該線性規(guī)劃問題無可行解。,50,簡(jiǎn)化的圖解法,對(duì)于可行域?yàn)榉忾]凸多邊形的兩變量線性規(guī)劃問題，可以采用簡(jiǎn)化的圖解法求解：

16、只需要窮舉出可行域的所有頂點(diǎn)，計(jì)算每一個(gè)頂點(diǎn)的目標(biāo)函數(shù)值，就可以找出最優(yōu)解。,簡(jiǎn)化的圖解法示例1,線性規(guī)劃問題（例1-8）,51,,,52,Excel求解線性規(guī)劃問題,“規(guī)劃求解”工具主界面,,Excel求解LP問題示例1,線性規(guī)劃問題（例1-8）,53,練習(xí)題-圖解以下線性規(guī)劃問題,,54,,,55,,某手工作坊生產(chǎn)的竹制座椅中需要用到3種規(guī)格楠竹片，每張椅子需要長(zhǎng)度為60cm、40cm和 30cm 的楠竹片 2、 6和2 片。可以

17、在市場(chǎng)上采購這些規(guī)格的現(xiàn)貨，也可以將作坊倉庫中長(zhǎng)度為110cm的楠竹片切割成所需的規(guī)格，但每切割1次會(huì)發(fā)生1cm的長(zhǎng)度損耗。問：如果要制作100張竹制座椅，該作坊的倉庫中至少要有多少條長(zhǎng)度為110cm的楠竹片，才不用去市場(chǎng)上采購？試建立本問題的線性規(guī)劃模型。,56,,,57,,,58,59,第2章,整數(shù)規(guī)劃(Integer Linear Programming),基本概念,線性規(guī)劃模型中增加了決策變量的整數(shù)約束，這類數(shù)學(xué)規(guī)劃問題

18、被稱為整數(shù)規(guī)劃(Integer Linear Programming, ILP)問題。整數(shù)規(guī)劃模型雖然只是在線性規(guī)劃模型中增加了決策變量的整數(shù)約束，但是其求解過程卻變得非常復(fù)雜。（簡(jiǎn)單的四舍五入？？？）車輛調(diào)度、人員安排、產(chǎn)品產(chǎn)量,60,基本概念,根據(jù)全部還是部分決策變量必須滿足整數(shù)約束，整數(shù)規(guī)劃問題可分為兩類：純整數(shù)規(guī)劃（Pure Integer Programming, PIP）混合整數(shù)規(guī)劃（Mixed Integer P

19、rogramming, MIP）根據(jù)整數(shù)變量取值的范圍，整數(shù)規(guī)劃問題還可分為：一般整數(shù)規(guī)劃-整數(shù)變量的取值可以是任意非負(fù)整數(shù)0-1整數(shù)規(guī)劃（Binary Integer Programming, BIP）-要求決策變量只能取值0或者1,61,基本概念,62,一般整數(shù)規(guī)劃問題的數(shù)學(xué)模型,,基本概念,63,0-1整數(shù)規(guī)劃問題的數(shù)學(xué)模型,,,應(yīng)用問題建模,設(shè)施布點(diǎn)問題某市在其5個(gè)規(guī)劃片區(qū)規(guī)劃消防站設(shè)點(diǎn)，要求任意一個(gè)片區(qū)發(fā)生火警時(shí)，本片

20、區(qū)或來自其它片區(qū)的消防車可以在15分鐘內(nèi)趕到。雖然在各片區(qū)各設(shè)一個(gè)消防站可以解決此問題，但為提高資源利用率，市政府提出消防站數(shù)量應(yīng)盡可能少。,64,應(yīng)用問題建模,背包問題（0-1）某家庭計(jì)劃自駕野外露營，出發(fā)前需考慮攜帶的物品，各物品的壓縮體積及重要程度如表所示。由于其自駕車最大容納的物品體積為650升，不可能所有物品都能裝入車中。問：應(yīng)選擇哪些物品出行？,65,應(yīng)用問題建模,指派問題有5項(xiàng)任務(wù)需要5個(gè)員工獨(dú)立完成，由于能力差異，

21、不同員工完成同一任務(wù)的執(zhí)行成本不同。下表給出了員工i完成任務(wù)j的執(zhí)行成本cij。問：如何指派任務(wù)可以最經(jīng)濟(jì)地完成各項(xiàng)任務(wù)。,66,應(yīng)用問題建模,將n項(xiàng)任務(wù)分配給n個(gè)人，約定每人只能完成一項(xiàng)工作，每項(xiàng)工作也只能由一個(gè)人來完成，但由于每個(gè)人能力各不相同，完成各項(xiàng)工作的收益和成本不同。根據(jù)不同的問題背景，可要求得到總利潤(rùn)最大或總成本最小的指派方案。這類問題在運(yùn)籌學(xué)中被稱為一種專門的問題：指派問題(Assignment Problem)。,6

22、7,應(yīng)用問題建模,68,定義0-1變量xij(i,j=1,…,n)表示第i個(gè)人是否被指派完成第j項(xiàng)任務(wù)（0代表不指派，1代表指派），則指派問題的數(shù)學(xué)模型為：,,應(yīng)用問題建模,含有互斥項(xiàng)目的計(jì)劃1. 如果攜帶食物，就必須同時(shí)攜帶野外廚具和洗漱用品；2. 通信設(shè)備和應(yīng)急醫(yī)療用品至少要攜帶1件；3. 帳篷和防曬防雨最多只能選擇1項(xiàng)；4. 野外廚具、攝影器材和通信設(shè)備最多選2項(xiàng)。,69,應(yīng)用問題建模,含有互斥約束條件的計(jì)劃某公司用兩種

23、原料E1和E2生產(chǎn)A、B兩種產(chǎn)品，生產(chǎn)過程均需經(jīng)過甲、乙兩道工序。甲、乙兩道工序又各可以采取2種生產(chǎn)工藝。甲工序可以混合使用甲1和甲2兩種工藝，而乙工序只能在乙1和乙2中選擇其中一種工藝。問：該公司應(yīng)如何安排生產(chǎn)可使利潤(rùn)最大？,70,,在建模中對(duì)互斥的約束處理時(shí)，可以引入Mi來實(shí)現(xiàn)使某個(gè)約束條件有效或者冗余，其中Mi為任意大的正數(shù)。,71,固定成本問題,某工廠用兩條生產(chǎn)線𝐿1和𝐿2生產(chǎn)兩種產(chǎn)品A和B。

24、這兩條生產(chǎn)線每個(gè)月的額定工時(shí)分別為600和800小時(shí)，生產(chǎn)線𝐿1的生產(chǎn)率為產(chǎn)品A 60件/小時(shí)或產(chǎn)品B 45件/小時(shí)，生產(chǎn)線𝐿2的生產(chǎn)率為產(chǎn)品A 35件/小時(shí)或產(chǎn)品B 40件/小時(shí)；產(chǎn)品A和B的單位售價(jià)分別為12元/件和16元/件，生產(chǎn)產(chǎn)品A和B的固定成本分別為60000元和80000元。問：應(yīng)如何安排生產(chǎn)可實(shí)現(xiàn)利潤(rùn)最大化？試建立本問題的混合整數(shù)規(guī)劃模,72,,1）決策變量的定義：因?yàn)楹泄潭ǔ杀镜膯栴}

25、，所以某產(chǎn)品的產(chǎn)量X和是否生產(chǎn)該產(chǎn)品的決策Y必須分別定義，而且它們必須是聯(lián)動(dòng)的，即如果某產(chǎn)品的產(chǎn)量X大于0，那么Y必須為1；而產(chǎn)品的產(chǎn)量X為0時(shí)，Y必須為0.否則，就有可能出現(xiàn)未生產(chǎn)產(chǎn)品X卻減去了固定成本的問題，或者生產(chǎn)了卻未減去固定成本的問題。這類問題必須引入任意大的正數(shù)M。,73,,2）正數(shù)M的引入X≤M?Y其中M為任意大的正數(shù)，即，只要Y=0，則X必須為0，Y=1時(shí)，X可以取任意正整數(shù)。,74,,所以，上題的決策變量定義如下：

26、,75,,,76,分枝定界法,分枝定界技術(shù)是一種求解優(yōu)化問題的通用思想，其邏輯思路是：把原始問題分解成若干個(gè)足夠小的可以直接求解的子問題，此為分枝過程(Branching)；對(duì)于每個(gè)子集及其對(duì)應(yīng)的子問題，考察其最優(yōu)解是否足夠好―是否可能包含原始問題的最優(yōu)解，此為定界過程(Bounding)；結(jié)束某些子問題的分枝過程，并根據(jù)定界過程的結(jié)果，放棄那些不可能包含原始問題最優(yōu)解的子集及子問題，此為剪枝過程(Fathoming)。,77,割

27、平面法,78,習(xí)題1,某大型社區(qū)臨街的中式快餐店每天的營業(yè)時(shí)間為8:00到24:00，根據(jù)社區(qū)居民對(duì)早餐、中餐、晚餐和夜宵的需求不同，一天中不同時(shí)段對(duì)服務(wù)員的需求如圖所示。,79,,該 店 的 員 工 分 為 兩 類 。 第 一 類 是 正 式 員 工 ， 分 別 在3個(gè)8小 時(shí) 時(shí) 段 上 班 ： 8:00 -16:00、12:00 - 20:00，以及 16:00- 24:00，其工作時(shí)薪為14元/小時(shí)，且規(guī)定各時(shí)段正式員工數(shù)量不能

28、少于3人；第二類是鐘點(diǎn)工，可在8:00到24:00的任意時(shí)間工作，其工作時(shí)薪為12元/小時(shí)。問：應(yīng)如何雇用正式員工和鐘點(diǎn)工，可在人力資源成本最小的基礎(chǔ)上滿足需求？試建立本問題的整數(shù)規(guī)劃模型。,80,,,81,,,82,習(xí)題2,某公司計(jì)劃在東、西、南三個(gè)地區(qū)建立銷售網(wǎng)點(diǎn)，總共有7個(gè)備選地點(diǎn)𝐴𝑖 (𝑖 = 1, · · · , 7)可供選擇。現(xiàn)要求所設(shè)立的銷售網(wǎng)

29、點(diǎn)必須滿足以下條件：? 在東部地區(qū)，𝐴1, 𝐴2, 𝐴3三個(gè)備選地點(diǎn)中至多選擇兩個(gè)地點(diǎn)設(shè)立銷售網(wǎng)點(diǎn)；? 在西部地區(qū)，𝐴4, 𝐴5兩個(gè)備選地點(diǎn)中至少選擇一個(gè)地點(diǎn)設(shè)立銷售網(wǎng)點(diǎn)；? 在南部地區(qū)，𝐴6, 𝐴7兩個(gè)備選地點(diǎn)只能選一個(gè)設(shè)立銷售網(wǎng)點(diǎn)；? 出于市場(chǎng)環(huán)境的考慮，如果方案中選擇了𝐴2地點(diǎn)，必須選擇在

30、9860;5同時(shí)設(shè)立銷售網(wǎng)點(diǎn)。若在備選地點(diǎn)𝐴𝑖設(shè)立銷售網(wǎng)點(diǎn)需要投資𝑏𝑖萬元，每年可獲得利潤(rùn)𝑐𝑖萬元。問：如果總投資預(yù)算為B萬元，在哪些備選地點(diǎn)設(shè)立網(wǎng)點(diǎn)可獲得最多的利潤(rùn)？試建立本問題的數(shù)學(xué)模型。,83,,,84,習(xí)題3,某短途航空公司有10條聯(lián)飛路線，可經(jīng)停9個(gè)城市，下表給出了這10條飛行路線經(jīng)停的城市和飛行總小時(shí)數(shù)（單位：小時(shí)）。試從這1

31、0條路線中選擇3條路線，既能夠滿足飛行總時(shí)間最少的要求，又能夠經(jīng)停9個(gè)城市至少1次。給出本問題的0-1整數(shù)規(guī)劃模型。,85,,,86,,則其目標(biāo)函數(shù)為：Min（Z）=？,87,,,88,習(xí)題4,某小提琴手作坊根據(jù)顧客提出的定制需求生產(chǎn)小提琴，價(jià)格和固定成本因定制需求而異。由于作坊的熟練技師有限(12人)，該手工作坊只能挑選部分訂單，甚至只能部分完成訂單所要求的數(shù)量。目前，作坊收到來自3家交響樂隊(duì)的小提琴訂單，下表給出了與此訂單相關(guān)的

32、制作成本和價(jià)格（單位：元）。問：各訂單各應(yīng)接受多少臺(tái)，可獲得最多的利潤(rùn)？試建立本問題的整數(shù)規(guī)劃模型。,89,,,90,,,91,習(xí)題5,某工廠生產(chǎn)A和B兩種型號(hào)的產(chǎn)品，其生產(chǎn)過程須經(jīng)過甲、乙、丙三個(gè)流水線車間加工，其中，乙車間有兩條加工效率不同的流水線乙1和乙2。已知乙車間的兩條流水線只能任選一條使用，問：如何安排生產(chǎn)可獲得最大的利潤(rùn)。建立本問題的整數(shù)規(guī)劃模型。,92,,,93,94,第5章,運(yùn)輸問題(Transportation

33、 Problems),基本概念,將某種物資從若干個(gè)產(chǎn)地運(yùn)輸?shù)搅硗馊舾蓚€(gè)銷地，要求總運(yùn)費(fèi)最小的問題，這一類問題及其衍生問題統(tǒng)稱為運(yùn)輸問題(Transportation Problem)。,95,引例,FreshFruit公司旗下有3個(gè)蘋果種植基地，預(yù)計(jì)年產(chǎn)量分別為75、125和100噸，近期該公司與4個(gè)不同地區(qū)的客戶簽訂了今年的蘋果供應(yīng)合同，其銷量分別80、65、70和85噸。由于交通條件差異，從3個(gè)基地到4個(gè)客戶所在地的單位運(yùn)費(fèi)不同，其

34、運(yùn)價(jià)表如表所示。,96,運(yùn)輸問題的數(shù)學(xué)模型,97,運(yùn)輸問題通常為：從m個(gè)產(chǎn)地向n個(gè)銷地運(yùn)輸某種物資，產(chǎn)地i到銷地j的單位運(yùn)費(fèi)是cij（呈比例關(guān)系），產(chǎn)地i的產(chǎn)量是ai，銷地j的銷量是bj，要求找到使得總運(yùn)費(fèi)最小的運(yùn)輸方案。當(dāng)問題滿足總產(chǎn)量與總銷量相等，這類問題稱為標(biāo)準(zhǔn)運(yùn)輸問題，或者產(chǎn)銷平衡運(yùn)輸問題。,運(yùn)輸問題的數(shù)學(xué)模型,標(biāo)準(zhǔn)運(yùn)輸問題的數(shù)學(xué)模型為：,98,標(biāo)準(zhǔn)運(yùn)輸問題的表上作業(yè)法,作為一種特殊的線性規(guī)劃問題，標(biāo)準(zhǔn)運(yùn)輸問題模型并不包含天

35、然的基變量和初始基本可行解，求解時(shí)需要在每個(gè)等式中引入人工變量，計(jì)算較為煩瑣。對(duì)于標(biāo)準(zhǔn)運(yùn)輸問題，在某種特殊形式的表格上來應(yīng)用單純形法，可使求解過程大大簡(jiǎn)化，這種方法叫作運(yùn)輸問題的表上作業(yè)法。需特別強(qiáng)調(diào)的是，用表上作業(yè)法求解運(yùn)輸問題，產(chǎn)銷平衡是一個(gè)基本前提。,99,標(biāo)準(zhǔn)運(yùn)輸問題的表上作業(yè)法,解題步驟：1- 初始化 給出初始基本可行方案；2- 迭代第1步基本可行方案的最優(yōu)判定，判斷當(dāng)前基本可行方案是否最優(yōu)。如果不是，進(jìn)入第2步；

36、第2步基本可行方案的改進(jìn)，然后返回第1步；,100,標(biāo)準(zhǔn)運(yùn)輸問題的表上作業(yè)法,運(yùn)輸問題作業(yè)表/產(chǎn)銷平衡表,101,標(biāo)準(zhǔn)運(yùn)輸問題的表上作業(yè)法,102,西北角法從作業(yè)表的西北角往東南角逐步填寫運(yùn)輸量。,西北角法示例1,103,,西北角法示例1,104,,,,,,標(biāo)準(zhǔn)運(yùn)輸問題的表上作業(yè)法,105,最小元素法按照單位運(yùn)費(fèi)由低到高的次序來選擇每次迭代中指派運(yùn)輸量的單元格。,最小元素法示例1,106,,最小元素法示例1,107,產(chǎn)銷不平衡的

37、運(yùn)輸問題示例,108,轉(zhuǎn)運(yùn)問題,(1) 確定標(biāo)準(zhǔn)運(yùn)輸問題中的產(chǎn)地和銷地：轉(zhuǎn)運(yùn)點(diǎn)既是產(chǎn)地，又是銷地。也就是說，標(biāo)準(zhǔn)運(yùn)輸問題中的產(chǎn)地為原始轉(zhuǎn)運(yùn)問題中的產(chǎn)地和所有的轉(zhuǎn)運(yùn)點(diǎn)，銷地為原始問題中的銷地和所有的轉(zhuǎn)運(yùn)點(diǎn)。(2) 確定各產(chǎn)地的產(chǎn)量和銷地的銷量：將原始轉(zhuǎn)運(yùn)問題中產(chǎn)地的產(chǎn)量和銷地的銷量直接移植入標(biāo)準(zhǔn)運(yùn)輸問題；轉(zhuǎn)運(yùn)點(diǎn)的產(chǎn)量和銷量相同，數(shù)值都為經(jīng)過該轉(zhuǎn)運(yùn)點(diǎn)的最大可能轉(zhuǎn)運(yùn)量。,109,轉(zhuǎn)運(yùn)問題,(3) 確定各產(chǎn)地與銷地之間的單位運(yùn)輸費(fèi)用：將原始問

38、題中已知的兩地之間的單位運(yùn)輸費(fèi)用移植入標(biāo)準(zhǔn)運(yùn)輸問題；各轉(zhuǎn)運(yùn)點(diǎn)到其自身的單位運(yùn)輸費(fèi)用為0；對(duì)于原始轉(zhuǎn)運(yùn)問題中不存在的運(yùn)輸路線，單位運(yùn)費(fèi)為無窮大，用任意大的正數(shù)𝑀表示。,110,轉(zhuǎn)運(yùn)問題示例1,111,其它問題,一些應(yīng)用問題雖然與物資運(yùn)輸、分銷沒有任何聯(lián)系，但是由于其問題背景與運(yùn)輸問題有相似的形式，亦可將其抽象并建模為廣義的產(chǎn)銷平衡運(yùn)輸問題，從而采用運(yùn)輸問題的表上作業(yè)法進(jìn)行求解。,112,習(xí)題1,求解如下運(yùn)輸問題：,113,

39、習(xí)題2,求解如下運(yùn)輸問題：,114,習(xí)題3,某水產(chǎn)品銷售公司每天從3個(gè)水產(chǎn)品養(yǎng)殖廠采購新鮮產(chǎn)品運(yùn)往4個(gè)批發(fā)市場(chǎng)。3個(gè)養(yǎng)殖廠每天提供的水產(chǎn)品數(shù)量為2500、3000、4500公斤，4個(gè)批發(fā)市場(chǎng)每日的需求量分別為2000、2500、3000、2500 公斤。根據(jù)表5所示3個(gè)養(yǎng)殖廠的采購成本價(jià)和4個(gè)批發(fā)市場(chǎng)的價(jià)格（單位：元/千克），公司應(yīng)如何安排運(yùn)輸可使得總利潤(rùn)最大？,115,習(xí)題4,有3個(gè) 牧 業(yè) 基 地 向4個(gè) 城 市 提 供 鮮 奶 ，

40、4個(gè) 城 市 每 日 的 鮮 奶 需 求 量為16、30、24和30千升，3個(gè)基地的每日鮮奶供應(yīng)量分別為30、40和50千升。已知運(yùn)送每千升鮮奶的費(fèi)用如表所示（單位：千元）。試確定最經(jīng)濟(jì)的鮮奶運(yùn)輸方案，且求出最小總運(yùn)費(fèi)。,116,習(xí)題5,假定習(xí)題3中城市A每天最低需求和總需求量分別為14和24千升，城市C每天最低需求和總需求量分別為25和40千升，其它城市需求量無變化，在最低需求必須滿足的前提下，求解該問題，且求出最小總運(yùn)費(fèi)。,117,

41、習(xí)題6,某干果公司從3個(gè)水果生產(chǎn)基地進(jìn)貨，在4個(gè)加工廠將水果加工成干果。假定3個(gè)水果基地的產(chǎn)量、4個(gè)加工廠的需求量，以及單位水果的運(yùn)價(jià)如表所示。在最低需求必須滿足的前提下，求總成本最低的運(yùn)輸方案。,118,習(xí)題7,已知2個(gè)供應(yīng)方A1、A2以及3個(gè)需求方B1、B2、B3的運(yùn)輸問題的運(yùn)價(jià)表如表所示。由于違約成本比較低，供應(yīng)方A1、A2在運(yùn)輸成本較高的情景下可選擇違約；同樣，由于缺貨損失比較低，需求方B1、B2、B3也可以在運(yùn)輸成本較低的情景

42、下選擇違約。問：根據(jù)表所示的缺貨成本、違約成本，以及運(yùn)輸成本，如何安排運(yùn)輸可使得總運(yùn)營成本最低？,119,第6章 目標(biāo)規(guī)劃,(Goal Programming),120,目標(biāo)規(guī)劃的提出,用線性規(guī)劃來解決實(shí)際問題時(shí)，除了要滿足比例性、可加性、可分性和確定性四個(gè)假設(shè)之外，通常還假設(shè)實(shí)際問題的求解目標(biāo)是單一的，而且其約束條件是可以嚴(yán)格滿足的。 線性規(guī)劃的弊端：現(xiàn)實(shí)決策問題通常都有多重的、可能相互沖突的目標(biāo)其約束條件也不一定必須

43、全部嚴(yán)格滿足 目標(biāo)規(guī)劃(Goal Programming)的提出，正是為了消除或至少部分填補(bǔ)這種方法與實(shí)際應(yīng)用之間的空白。,121,6.1.1 引例-目標(biāo)規(guī)劃的數(shù)學(xué)模型,在例1-1中，F(xiàn)公司每周需要根據(jù)下表確定產(chǎn)品A、B、C的產(chǎn)量，以獲取最大的利潤(rùn)其線性規(guī)劃數(shù)學(xué)模型為：本問題的求解目標(biāo)是唯一的———利潤(rùn)最大化。,122,,6.1.1 引例,但現(xiàn)實(shí)問題往往會(huì)有多個(gè)目標(biāo)，比如把上面這個(gè)例子變成：例6-1

44、在滿足例1-1資源約束的前提下，按優(yōu)先次序滿足以下的目標(biāo)：利潤(rùn)最好不少于200元；產(chǎn)品B為產(chǎn)品A的補(bǔ)充件，其產(chǎn)量最好低于產(chǎn)品A的一半；產(chǎn)品C為戰(zhàn)略性產(chǎn)品，其產(chǎn)量最好不低于5件；原材料M2最好全部使用完且不超量；原材料M1比較稀缺，最好至少有10千克的剩余。問：F公司應(yīng)如何安排生產(chǎn)計(jì)劃，能夠盡可能達(dá)成以上的經(jīng)營目標(biāo)？,123,6.1.1 引例,問題的線性規(guī)劃模型變?yōu)橐韵虏坏仁浇M符合上述不等式組的解，就是本問題

45、的解。經(jīng)過計(jì)算，該不等式組無解。而在實(shí)際背景下，該問題顯然是有解的。,124,,,,,,,,,資源約束,,五個(gè)目標(biāo),6.1.1 引例,實(shí)際上，本問題前3 個(gè)優(yōu)先級(jí)的目標(biāo)是可以完全達(dá)成的，第(4)、(5) 個(gè)目標(biāo)雖然無法完全達(dá)成，但是是允許妥協(xié)的———只需要在前幾個(gè)目標(biāo)達(dá)成的基礎(chǔ)上，盡可能滿足即可。問題出在建模的方式上以上模型將5 個(gè)原本有優(yōu)先次序的、允許妥協(xié)的目標(biāo)變成了必須同時(shí)嚴(yán)格滿足的目標(biāo)。因此，一個(gè)在現(xiàn)實(shí)中有解的多目標(biāo)決策問題

46、，以線性規(guī)劃的思路建?？赡芫蜔o解了。目標(biāo)規(guī)劃的提出，正是針對(duì)這類線性規(guī)劃無法解決的實(shí)際問題。,125,6.1.2 目標(biāo)規(guī)劃的基本概念,目標(biāo)規(guī)劃問題是這樣一類問題：在滿足剛性約束的前提下，求解一組決策變量的取值，使得不同優(yōu)先級(jí)別目標(biāo)的實(shí)現(xiàn)值與目標(biāo)值之間的偏差盡可能小的線性規(guī)劃問題。概念實(shí)現(xiàn)值與目標(biāo)值、偏差變量剛性約束與柔性約束達(dá)成函數(shù)優(yōu)先級(jí)與權(quán)重,126,6.1.2 目標(biāo)規(guī)劃的基本概念,1、目標(biāo)值、實(shí)現(xiàn)值與偏差變量在目標(biāo)規(guī)

47、劃中，描述各個(gè)目標(biāo)的數(shù)學(xué)表達(dá)式稱為目標(biāo)表達(dá)式。對(duì)某個(gè)目標(biāo)表達(dá)式期望的取值水平（不論是不超過、不少于還是等于），稱為該目標(biāo)的目標(biāo)值。當(dāng)決策變量xj 的取值確定以后，某個(gè)目標(biāo)表達(dá)式的實(shí)際取值稱為該目標(biāo)的實(shí)現(xiàn)值，又稱為決策值。例如，例6-1中第(1) 個(gè)目標(biāo)的目標(biāo)表達(dá)式為5x1 +4x2 + 2x3，對(duì)此目標(biāo)的期望值為200，則其目標(biāo)值為200；第(2) 個(gè)目標(biāo)的目標(biāo)表達(dá)式可寫為x1 ? 2x2，此時(shí)目標(biāo)值為0。第(3) 個(gè)目標(biāo)的

48、表達(dá)式x3，目標(biāo)值為5。,127,6.1.2 目標(biāo)規(guī)劃的基本概念,實(shí)現(xiàn)值與目標(biāo)值之間可能會(huì)存在差異，這種差異的大小在決策（確定決策變量取值）前是無法預(yù)知的，是隨決策變量變化而變化的，因此稱實(shí)現(xiàn)值與目標(biāo)值之間的差異為偏差變量。因建模的需要以及適應(yīng)線性規(guī)劃中對(duì)變量的非負(fù)要求，偏差變量又分為正偏差量，代表實(shí)現(xiàn)值超過目標(biāo)值的偏差，記為d+負(fù)偏差量，代表實(shí)現(xiàn)值未達(dá)到目標(biāo)值的偏差，記為d-滿足非負(fù)：滿足互斥：,128,,,6.1.2 目標(biāo)

49、規(guī)劃的基本概念,例如，例6-1中，如果某個(gè)滿足了約束條件式(6-1) 的決策為x1 = 25; x2 = 13; x3 = 5;則第(1) 個(gè)目標(biāo)，其實(shí)現(xiàn)值為5x1 + 4x2 + 2x3 = 187，未達(dá)到目標(biāo)值200，如果用 表示該目標(biāo)的正負(fù)偏差量，有對(duì)于第(2) 個(gè)目標(biāo)，其實(shí)現(xiàn)值為x1 ? 2x2 = ?1，目標(biāo)值為0，有同理，對(duì)于第(3) 個(gè)目標(biāo)，因?yàn)閷?shí)現(xiàn)值等于目標(biāo)值5，有,129,,,,,6.1.

50、2 目標(biāo)規(guī)劃的基本概念,2、 剛性約束、柔性約束與達(dá)成函數(shù)在目標(biāo)規(guī)劃中，必須嚴(yán)格滿足的約束條件稱為剛性約束或硬目標(biāo)。剛性約束中不含偏差變量。目標(biāo)規(guī)劃中，不滿足剛性約束的解為非可行解。與剛性約束相對(duì)，目標(biāo)規(guī)劃中允許某些目標(biāo)的決策值與目標(biāo)值存在偏差，這類目標(biāo)稱為軟目標(biāo)，其所對(duì)應(yīng)的約束條件稱為柔性約束。此即柔性約束的表達(dá)式。,130,,6.1.2 目標(biāo)規(guī)劃的基本概念,例如，對(duì)例6-1中的第(1)個(gè)目標(biāo)，其柔性約束為：同理，對(duì)

51、于第(2)、(3)個(gè)目標(biāo)，其柔性約束分別為：,131,,,6.1.2 目標(biāo)規(guī)劃的基本概念,對(duì)每個(gè)目標(biāo)，決策者會(huì)表達(dá)出對(duì)決策值與目標(biāo)值之間關(guān)系的期望———超過、不超過或恰好等于。但僅從柔性約束本身，無法判斷決策者究竟是期望達(dá)到哪一種。在此引入一個(gè)稱為達(dá)成函數(shù)的表達(dá)式來表示決策者的期望。由目標(biāo)規(guī)劃問題的定義可知，對(duì)于任一目標(biāo)，決策者的期望是使決策值與目標(biāo)值的偏差盡可能小，因此達(dá)成函數(shù)是僅含偏差變量，且目標(biāo)是使偏差變量取最小值的目標(biāo)函數(shù),

52、132,,6.1.2 目標(biāo)規(guī)劃的基本概念,對(duì)于單一的目標(biāo)，達(dá)成函數(shù)依決策者的期望分三種情況：超過目標(biāo)值，則達(dá)成函數(shù)為 。可理解為希望有正偏差，不希望有負(fù)偏差。不超過目標(biāo)值，則達(dá)成函數(shù)為 ?？衫斫鉃橄Ｍ胸?fù)偏差，不希望有正偏差。恰好等于目標(biāo)值，則有 ，亦即正、負(fù)偏差量都要盡可能地小。結(jié)合柔性約束與達(dá)成函數(shù)，就可以寫出每個(gè)目標(biāo)的目標(biāo)表達(dá)式。,133

53、,,,,6.1.2 目標(biāo)規(guī)劃的基本概念,例如，第(1)個(gè)目標(biāo)的達(dá)成函數(shù)為利潤(rùn)最好不少于200：第(2)個(gè)目標(biāo)的表達(dá)式為產(chǎn)品B產(chǎn)量最好低于產(chǎn)品A一半：第(4)個(gè)目標(biāo)的表達(dá)式為原材料M2最好全部使用完且不超量：,134,,,,,6.1.2 目標(biāo)規(guī)劃的基本概念,3、優(yōu)先級(jí)與權(quán)重以上的分析只針對(duì)單一目標(biāo)，當(dāng)問題中有多個(gè)主次不同的目標(biāo)，且各個(gè)目標(biāo)之間可能存在矛盾時(shí)，就需要以某種方式將各個(gè)目標(biāo)的達(dá)成函數(shù)合并成一個(gè)單一的達(dá)成函數(shù)。

54、目標(biāo)規(guī)劃通過引入優(yōu)先級(jí)來為不同目標(biāo)的達(dá)成函數(shù)加權(quán)。具體為，在合并達(dá)成函數(shù)時(shí)，將目標(biāo)按重要程度進(jìn)行優(yōu)先級(jí)排序，第1 優(yōu)先級(jí)目標(biāo)的達(dá)成函數(shù)乘以優(yōu)先因子P1，第2 優(yōu)先級(jí)目標(biāo)的達(dá)成函數(shù)乘以P2，依次類推，第L 優(yōu)先級(jí)目標(biāo)的達(dá)成函數(shù)乘以優(yōu)先因子PL，且規(guī)定由此保證優(yōu)先實(shí)現(xiàn)P1 級(jí)的目標(biāo)，在此基礎(chǔ)上再考慮P2 級(jí)目標(biāo)的實(shí)現(xiàn)，然后依次類推。,135,,,6.1.2 目標(biāo)規(guī)劃的基本概念,某些實(shí)際問題中同一優(yōu)先級(jí)下可能有多個(gè)目標(biāo)，這些目標(biāo)的重要程

55、度還可以有差異，只不過這種差異不是數(shù)量級(jí)上的，目標(biāo)規(guī)劃用權(quán)重來區(qū)分這種差異。在建模時(shí)，可以根據(jù)決策者的需求，對(duì)該優(yōu)先級(jí)Pl 下某個(gè)目標(biāo)k的達(dá)成函數(shù)以權(quán)系數(shù)wlk 加權(quán)后再相加。注意：優(yōu)先級(jí)的劃分，以及同一優(yōu)先級(jí)下多個(gè)目標(biāo)的權(quán)重的設(shè)定，沒有普適性的規(guī)則，而應(yīng)根據(jù)決策者的需求和偏好來確定。 ------------主觀性在不同的問題背景或決策者偏好下，同一個(gè)目標(biāo)的優(yōu)先級(jí)或其在某個(gè)優(yōu)先級(jí)中的權(quán)系數(shù)都可能有不同的設(shè)定。,136

56、,6.1.2 目標(biāo)規(guī)劃的基本概念,根據(jù)上述概念，可以寫出例6-1的目標(biāo)規(guī)劃模型。整個(gè)問題的達(dá)成函數(shù)可以寫為上式所示的“和”的形式，也可以寫為“集合”的形式：,137,,,6.1.3 目標(biāo)規(guī)劃模型及建模步驟,目標(biāo)規(guī)劃問題的數(shù)學(xué)模型的一般形式為：自上而下分別是達(dá)成函數(shù)、剛性約束、柔性約束和所有變量的非負(fù)約束,138,,,,,,6.1.3 目標(biāo)規(guī)劃模型及建模步驟,建模步驟：第1步 設(shè)定問題的決策變量；

57、第2步 列出問題的剛性約束；第3步 根據(jù)決策者的需求和偏好，設(shè)定各個(gè)目標(biāo)的優(yōu)先級(jí)，當(dāng)有多個(gè)目標(biāo)同屬于一個(gè)優(yōu)先級(jí)下時(shí)，還需根據(jù)約定設(shè)定各個(gè)目標(biāo)的權(quán)重；然后，寫出各個(gè)目標(biāo)的柔性約束和各優(yōu)先級(jí)的達(dá)成函數(shù)；第4步 用優(yōu)先因子和權(quán)系數(shù)為各個(gè)目標(biāo)的達(dá)成函數(shù)加權(quán)，寫出整個(gè)問題的達(dá)成函數(shù)。第5步 寫出決策變量與偏差變量的非負(fù)約束。,139,,例6-2 在例6-1中，假定不要求嚴(yán)格滿足資源約束，且各優(yōu)先級(jí)的目標(biāo)依次如下：利潤(rùn)最好不少于180元；

58、產(chǎn)品A的產(chǎn)量最好不多于25件、產(chǎn)品B的產(chǎn)量最好不少于15件、產(chǎn)品C的產(chǎn)量最好不少于5件，且根據(jù)單位產(chǎn)品的利潤(rùn)確定權(quán)系數(shù)；原材料M2最好全部使用完，不足時(shí)可購入，原材料M1比較稀缺，最好至少有10千克的剩余。問：F公司應(yīng)如何安排生產(chǎn)計(jì)劃，能夠盡可能達(dá)成以上的經(jīng)營目標(biāo)？,140,,解：用x1，x2 和x3 表示產(chǎn)品A，B 和C 的產(chǎn)量。,141,,例6-3 電子產(chǎn)品生產(chǎn)企業(yè)HF公司通過采購半成品生產(chǎn)A、B、C三種型號(hào)的手機(jī)。這三種手

59、機(jī)在同一流水線上生產(chǎn)，每件的生產(chǎn)工時(shí)消耗分別為5分鐘，7分鐘，12分鐘，利潤(rùn)分別為每臺(tái)140元，210元，384元。生產(chǎn)線正常運(yùn)轉(zhuǎn)時(shí)間為250小時(shí)/月，加班滿負(fù)荷運(yùn)轉(zhuǎn)時(shí)最多有400小時(shí)/月。HF公司的決策者提出的月經(jīng)營目標(biāo)按優(yōu)先級(jí)排序?yàn)椋罕M可能充分利用生產(chǎn)線的正常工時(shí)，工時(shí)不夠用時(shí)可以加班；希望A、B、C的產(chǎn)量至少達(dá)到700，750，500臺(tái)，根據(jù)單位工時(shí)的利潤(rùn)比例設(shè)定權(quán)系數(shù)；加班工時(shí)最好不超過40小時(shí)/月； 希望A、B、C的

60、產(chǎn)量盡可能超過月銷售量預(yù)測(cè)的最低水平800，900，550臺(tái)，根據(jù)單位工時(shí)的利潤(rùn)比例設(shè)定權(quán)系數(shù)。問：各產(chǎn)品應(yīng)生產(chǎn)多少才能達(dá)成上述經(jīng)營目標(biāo)？建立本問題的其目標(biāo)規(guī)劃模型。,142,,解：設(shè)A、B、C 的產(chǎn)量分別為x1, x2, x3。,143,,例6-4 SD 公司下屬三個(gè)工廠生產(chǎn)某種產(chǎn)品來滿足四個(gè)地區(qū)的需求，各工廠的產(chǎn)量、各地的需求量以及從各工廠到四地的單位產(chǎn)品運(yùn)輸費(fèi)用如下表所示。如果僅要求運(yùn)輸費(fèi)用最小，在將該問題轉(zhuǎn)化為產(chǎn)銷

61、平衡問題后，用運(yùn)輸問題表上作業(yè)法求解得最低總運(yùn)費(fèi)為2750 元。但是考慮到各地的不同情況和運(yùn)輸中可能存在的問題，該公司在確定最后運(yùn)輸方案時(shí)還需考慮其它幾個(gè)目標(biāo)，按重要程度依次為：P1 ：地區(qū)3 為重點(diǎn)銷售地區(qū)，其需求應(yīng)優(yōu)先全部滿足；P2 ：用于供應(yīng)地區(qū)2 的產(chǎn)品中，工廠1 的產(chǎn)品不少于80 件；P3 ：為平衡各地需求，每個(gè)地區(qū)用戶需求的滿足率應(yīng)不低于90%；P4 ：由于交通條件的限制，應(yīng)盡量避免從工廠2 運(yùn)輸至地區(qū)2；P5 ：

62、盡可能減少總運(yùn)費(fèi)。,144,145,,6.2 兩變量目標(biāo)規(guī)劃問題的圖解法,146,6.2兩變量目標(biāo)規(guī)劃問題的圖解法,目標(biāo)規(guī)劃模型中對(duì)目標(biāo)進(jìn)行了優(yōu)先級(jí)的區(qū)分，這決定了其求解過程是一個(gè)分級(jí)進(jìn)行的過程：對(duì)于有L 個(gè)優(yōu)先級(jí)的目標(biāo)規(guī)劃問題，先在可行域內(nèi)尋找滿足P1級(jí)目標(biāo)的解然后在保證P1級(jí)目標(biāo)不被打破的前提下，再尋找滿足P2級(jí)目標(biāo)的解依次類推如果用解空間的概念，求解過程又可以表述為：在可行域R0 內(nèi)找到滿足P1 級(jí)目標(biāo)的解空間R1，再以

63、R1 為可行域?qū)ふ覞M足P2 級(jí)目標(biāo)的解空間R2，依次類推，直至在RL-1 內(nèi)尋找PL 級(jí)目標(biāo)的解空間RL，其中目標(biāo)規(guī)劃的最終求解結(jié)果通常只能稱為滿意解即只能保證優(yōu)先級(jí)較高的目標(biāo)得以實(shí)現(xiàn)或部分實(shí)現(xiàn)，不保證優(yōu)先級(jí)低的目標(biāo)能實(shí)現(xiàn)。,147,,6.2兩變量目標(biāo)規(guī)劃問題的圖解法,步驟第1 步 在坐標(biāo)平面第一象限表示出由剛性約束所確定的可行域，以此可行域?yàn)槌跏冀饪臻gR0；第2 步 選定P1優(yōu)先級(jí)的目標(biāo)，進(jìn)入第3步；第3 步 在Rl-1

64、 中找到滿足Pl級(jí)目標(biāo)的解空間進(jìn)入第4步Rl；第4 步 當(dāng)所有優(yōu)先級(jí)的目標(biāo)都處理完時(shí)，求解結(jié)束，問題的滿意解就是目前得到的解空間；或者，如果Rl 為一個(gè)點(diǎn)，求解結(jié)束，問題的滿意解就是該點(diǎn)的坐標(biāo)。如果上述條件皆不滿足，則轉(zhuǎn)到下一個(gè)優(yōu)先級(jí)，返回第3 步。,148,圖解法示例,例6-5 用圖解法求解,149,,150,151,152,153,154,155,156,157,158,圖解法示例,例6-6 用圖解法求解,159,,160,16

65、1,162,163,164,165,166,6.2兩變量目標(biāo)規(guī)劃問題的圖解法,應(yīng)用圖解法求解只有兩個(gè)決策變量、且一個(gè)優(yōu)先級(jí) Pl下有多個(gè)目標(biāo)的目標(biāo)規(guī)劃模型時(shí)，確定 Pl優(yōu)先級(jí)的解空間 Rl的過程就會(huì)變得比較復(fù)雜，見例6-7(略)。,167,6.4 用Excel求解目標(biāo)規(guī)劃問題,掌握了序貫解法的原理，理解將目標(biāo)規(guī)劃問題轉(zhuǎn)化為一系列線性規(guī)劃問題的方式，再進(jìn)一步用Excel規(guī)劃求解工具完成。略。,168,169,第9章,網(wǎng)絡(luò)計(jì)劃技術(shù)(Ne

66、twork Planning Technique),基本概念,網(wǎng)絡(luò)計(jì)劃技術(shù)（項(xiàng)目進(jìn)度管理）它利用網(wǎng)絡(luò)圖的形式直觀表現(xiàn)出工程項(xiàng)目中各項(xiàng)任務(wù)之間的相互關(guān)系，從而找出決定項(xiàng)目總工期的關(guān)鍵路線和關(guān)鍵工序。進(jìn)而，在一定工期、成本、資源等約束條件下通過各種技術(shù)手段獲得最佳的計(jì)劃安排，以達(dá)到縮短工期、提高工效、降低成本的目的。,170,引例,171,16分鐘,引例,172,20分鐘,發(fā)展歷程,網(wǎng)絡(luò)計(jì)劃技術(shù)根據(jù)起源可以分為關(guān)鍵路徑法（CPM-Cri

67、tical Path Method-Walker and Kelly）和計(jì)劃評(píng)審技術(shù)（PERT-Program Evaluation and Review Technic-U.S. Navy）兩個(gè)源頭。關(guān)鍵路徑法強(qiáng)調(diào)/要求所研究項(xiàng)目中每項(xiàng)任務(wù)的執(zhí)行時(shí)間必須是明確的，而計(jì)劃評(píng)審技術(shù)中每項(xiàng)任務(wù)的執(zhí)行時(shí)間可以是一個(gè)估計(jì)值/不確定值。因此，關(guān)鍵路徑法主要應(yīng)用于一些有前期經(jīng)驗(yàn)的工程項(xiàng)目，而計(jì)劃評(píng)審技術(shù)更多應(yīng)用于研究與開發(fā)項(xiàng)目的計(jì)劃管理。19

68、62,錢學(xué)森-華羅庚-“統(tǒng)籌法”,173,基本流程,1-闡明問題，將項(xiàng)目分解為若干個(gè)可以獨(dú)立的工作單元，并明確各個(gè)工作單元的相關(guān)屬性（資源使用、時(shí)間消耗、成本計(jì)算等），以及工作單元之間的邏輯先后關(guān)系。2-根據(jù)分解后的工作單元，以及工作單元之間的邏輯先后關(guān)系，繪制網(wǎng)絡(luò)圖。,174,基本流程,3-應(yīng)用關(guān)鍵路徑法計(jì)算得到整個(gè)項(xiàng)目的最短完成時(shí)間，項(xiàng)目中每項(xiàng)工序的最遲開始時(shí)間、最早可能開始時(shí)間等時(shí)間參數(shù)，整個(gè)項(xiàng)目的關(guān)鍵路徑以及關(guān)鍵路徑上的各項(xiàng)

69、關(guān)鍵工序。4-根據(jù)具體應(yīng)用，對(duì)關(guān)鍵路徑上的關(guān)鍵工序進(jìn)行資源的合理安排和優(yōu)化。,175,雙代號(hào)網(wǎng)絡(luò)圖的繪制方法,工作單元用有向箭線來表示，箭線的方向表示工序進(jìn)行的方向：箭線的箭尾表示該工序的開始，箭線的箭頭表示該工序的結(jié)束。工序的名稱或者代號(hào)標(biāo)注在箭線的上方，工序所花費(fèi)的時(shí)間標(biāo)注在箭線的下方。,176,,雙代號(hào)網(wǎng)絡(luò)圖的繪制方法,多條箭線指向該節(jié)點(diǎn)代表著多條箭線所指的工序都完成之后，該節(jié)點(diǎn)之后的工序才可以開始E的緊后工序F，同理，C、