工程碩士運籌學課件及重點

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

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

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

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

5、目標,1. 常見線性規(guī)劃問題的數學建模思路2. 建模的適用范圍3. “解”的概念4. 圖解法5. EXCEL求解一般線性規(guī)劃問題（練習）,13,14,線性規(guī)劃的定義,在滿足一組線性約束條件（等式或不等式）的前提下，使得某一個線性目標函數取得極值（最大值或最小值）。這類問題的模型及其優(yōu)化求解技術，被統(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ī)劃數學模型,線性規(guī)劃問題的一般模型,15,線性規(guī)劃數學模型,模型特點1- 所有表達式均為線性表達式2-目標為求目標函數Z的最大值(max)或最小值(min)3- 約束條件為” ≥/≤/=”，沒有”>/<”！4- 通常要求決策變量取值非負

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

24、這兩條生產線每個月的額定工時分別為600和800小時，生產線𝐿1的生產率為產品A 60件/小時或產品B 45件/小時，生產線𝐿2的生產率為產品A 35件/小時或產品B 40件/小時；產品A和B的單位售價分別為12元/件和16元/件，生產產品A和B的固定成本分別為60000元和80000元。問：應如何安排生產可實現利潤最大化？試建立本問題的混合整數規(guī)劃模,72,,1）決策變量的定義：因為含有固定成本的問題

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

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

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

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

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

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

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

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

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

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

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

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

37、運輸問題示例,108,轉運問題,(1) 確定標準運輸問題中的產地和銷地：轉運點既是產地，又是銷地。也就是說，標準運輸問題中的產地為原始轉運問題中的產地和所有的轉運點，銷地為原始問題中的銷地和所有的轉運點。(2) 確定各產地的產量和銷地的銷量：將原始轉運問題中產地的產量和銷地的銷量直接移植入標準運輸問題；轉運點的產量和銷量相同，數值都為經過該轉運點的最大可能轉運量。,109,轉運問題,(3) 確定各產地與銷地之間的單位運輸費用：將原始問

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

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

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

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

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

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

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

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

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

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

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

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

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

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

52、132,,6.1.2 目標規(guī)劃的基本概念,對于單一的目標，達成函數依決策者的期望分三種情況：超過目標值，則達成函數為 ?？衫斫鉃橄Ｍ姓?，不希望有負偏差。不超過目標值，則達成函數為 ?？衫斫鉃橄Ｍ胸撈睿幌Ｍ姓?。恰好等于目標值，則有 ，亦即正、負偏差量都要盡可能地小。結合柔性約束與達成函數，就可以寫出每個目標的目標表達式。,133

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

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

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

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

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

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

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

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

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

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

63、R1 為可行域尋找滿足P2 級目標的解空間R2，依次類推，直至在RL-1 內尋找PL 級目標的解空間RL，其中目標規(guī)劃的最終求解結果通常只能稱為滿意解即只能保證優(yōu)先級較高的目標得以實現或部分實現，不保證優(yōu)先級低的目標能實現。,147,,6.2兩變量目標規(guī)劃問題的圖解法,步驟第1 步 在坐標平面第一象限表示出由剛性約束所確定的可行域，以此可行域為初始解空間R0；第2 步 選定P1優(yōu)先級的目標，進入第3步；第3 步 在Rl-1

64、 中找到滿足Pl級目標的解空間進入第4步Rl；第4 步 當所有優(yōu)先級的目標都處理完時，求解結束，問題的滿意解就是目前得到的解空間；或者，如果Rl 為一個點，求解結束，問題的滿意解就是該點的坐標。如果上述條件皆不滿足，則轉到下一個優(yōu)先級，返回第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兩變量目標規(guī)劃問題的圖解法,應用圖解法求解只有兩個決策變量、且一個優(yōu)先級 Pl下有多個目標的目標規(guī)劃模型時，確定 Pl優(yōu)先級的解空間 Rl的過程就會變得比較復雜，見例6-7(略)。,167,6.4 用Excel求解目標規(guī)劃問題,掌握了序貫解法的原理，理解將目標規(guī)劃問題轉化為一系列線性規(guī)劃問題的方式，再進一步用Excel規(guī)劃求解工具完成。略。,168,169,第9章,網絡計劃技術(Ne

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

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

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

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