《運籌學》課件精簡版

1、1版權所有 肖智 重慶大學經(jīng)濟與工商管理學院n主講：經(jīng)濟與工商管理學院主講：經(jīng)濟與工商管理學院 肖肖 智智3 3運籌決策運籌決策2版權所有 肖智 重慶大學經(jīng)濟與工商管理學院 一、本章的目的：一、本章的目的： 了解運籌決策概念、作用，掌握運籌決策分析的了解運籌決策概念、作用，掌握運籌決策分析的基本思路與分析方法，理解其重要作用與應用。基本思路與分析方法，理解其重要作用與應用。二、主要內容：二、主要內容： 1 1、網(wǎng)絡規(guī)劃決策、網(wǎng)絡規(guī)劃決策 2 2、線性規(guī)劃決策、線性規(guī)劃決策 3 3、運輸決策、運輸決策 4 4、指派決策、指派決策三、本講的重點與難點：三、本講的重點與難點： 1 1、重點：掌握運籌

2、決策分析基本思路與方法。、重點：掌握運籌決策分析基本思路與方法。 2 2、難點：分析、建模。、難點：分析、建模。四、具體內容：四、具體內容：3 3運籌決策運籌決策3版權所有 肖智 重慶大學經(jīng)濟與工商管理學院（一）網(wǎng)絡規(guī)劃決策（一）網(wǎng)絡規(guī)劃決策1 1、本節(jié)的目的：、本節(jié)的目的： 理解網(wǎng)絡規(guī)劃基本概念、特征、應用，掌理解網(wǎng)絡規(guī)劃基本概念、特征、應用，掌握最小樹與最短路等典型問題的網(wǎng)絡模型建立握最小樹與最短路等典型問題的網(wǎng)絡模型建立、分析思路、求解方法，了解最小樹與最短路、分析思路、求解方法，了解最小樹與最短路等典型問題的應用。等典型問題的應用。2 2、主要內容：、主要內容： 1 1）網(wǎng)絡規(guī)劃概述）

3、網(wǎng)絡規(guī)劃概述 2 2）最小樹問題）最小樹問題 3 3）最短路問題）最短路問題3 3、本講的重點與難點：、本講的重點與難點： 1 1）重點：掌握網(wǎng)絡模型基本要素、特征，網(wǎng)）重點：掌握網(wǎng)絡模型基本要素、特征，網(wǎng)3 3運籌決策運籌決策4版權所有 肖智 重慶大學經(jīng)濟與工商管理學院絡模型建立，求解思路與方法，其作用與應用絡模型建立，求解思路與方法，其作用與應用 2 2）難點：模型建立、分析思路網(wǎng)絡規(guī)劃問題）難點：模型建立、分析思路網(wǎng)絡規(guī)劃問題4 4、網(wǎng)絡規(guī)劃概述、網(wǎng)絡規(guī)劃概述1 1）基本概念）基本概念（1 1）圖：由點和邊組成的集合。）圖：由點和邊組成的集合。 常記為：常記為：G=(V,E)G=(V,E

4、)；其中：；其中：V=v1,v2,vnV=v1,v2,vn表表示點的集合示點的集合,E=e1,e2,em,E=e1,e2,em表示邊的集合。表示邊的集合。 如下圖如下圖3.1-13.1-1為無向圖，圖為無向圖，圖3.1-23.1-2為有向圖。為有向圖。 圖圖3.1-1 3.1-1 圖圖3.1-2 3.1-2 v1e2e1v2v3v1e2e3e1v2v33 3運籌決策運籌決策5版權所有 肖智 重慶大學經(jīng)濟與工商管理學院（2 2）網(wǎng)絡）網(wǎng)絡: :帶有某種數(shù)量指標的圖帶有某種數(shù)量指標的圖( (即即: :賦權圖賦權圖) )稱為網(wǎng)稱為網(wǎng)絡如下圖絡如下圖3.1-33.1-3為無向網(wǎng)絡，圖為無向網(wǎng)絡，圖3.

5、1-43.1-4為有向網(wǎng)絡。為有向網(wǎng)絡。 圖圖3.1-3 3.1-3 圖圖3.1-43.1-4（3 3）鏈）鏈: :無向圖無向圖G=(V,E)G=(V,E)中與邊依次交替出現(xiàn)的序列中與邊依次交替出現(xiàn)的序列vvi0i0,e,ei1i1,v,vi1i1,e,ei2i2,v,vi2i2,v,vik-1ik-1,e,eikik,v,vikik , , 且且e eit it=(v=(vit-1it-1,v,vit it), ),t=1,kt=1,k，則稱這個點邊序列為連接，則稱這個點邊序列為連接v vi0i0到到v vikik的一條的一條鏈，鏈長為鏈，鏈長為k k。（4 4）圈）圈: :鏈鏈vvi0i0

6、,e,ei1i1,v,vi1i1,e,ei2i2,v,vi2i2,v,vik-1ik-1,e,eikik,v,vikik 中當中當v vi0i0=v=vikik時時, , 該鏈稱為圈。如下圖該鏈稱為圈。如下圖3.1-53.1-5中中vv1 1,e,e1 1,v,v2 2,e,e3 3,v,v3 3,e,e2 2,v,v1 1 為圈。為圈。v153v2v3v1328v2v33 3運籌決策運籌決策6版權所有 肖智 重慶大學經(jīng)濟與工商管理學院 圖圖3.1-5 3.1-5 圖圖3.1-63.1-6（5 5）路）路: :有向圖中當鏈有向圖中當鏈( (圈圈) )上的邊方向相同時上的邊方向相同時, ,稱為路

7、稱為路( (回路回路) )。如圖。如圖3.1-63.1-6中中vv1 1,e,e3 3,v,v4 4,e,e4 4,v,v2 2,e,e7 7,v,v5 5 為路；為路； vv3 3,e,e5 5,v,v4 4,e,e6 6,v,v5 5,e,e8 8,v,v3 3 為回路。為回路。（6 6）連通圖）連通圖: :圖中任意兩點間至少有一條鏈相連，稱圖中任意兩點間至少有一條鏈相連，稱此圖為連通圖。如圖此圖為連通圖。如圖3.1-53.1-5、圖、圖3.1-63.1-6。（7 7）網(wǎng)絡模型）網(wǎng)絡模型: :對所關心的問題確定研究對象以及這對所關心的問題確定研究對象以及這些對象之間某種性質的聯(lián)系，并用網(wǎng)絡

8、圖及其圖解的些對象之間某種性質的聯(lián)系，并用網(wǎng)絡圖及其圖解的形式表示出來，這就形式表示出來，這就 是對問題建立網(wǎng)絡模型。是對問題建立網(wǎng)絡模型。v1e1v2v3v1v2v5v4v3v4e2e3e4e5e1e2e3e4e5e6e7e83 3運籌決策運籌決策7版權所有 肖智 重慶大學經(jīng)濟與工商管理學院 2 2）網(wǎng)絡基本特征）網(wǎng)絡基本特征：（1 1）三要素）三要素點、邊、權。點、邊、權。（2 2）一般將研究）一般將研究“對象對象”作為作為“點點”，“對象對象”之間之間關系作為關系作為“邊邊”，“對象對象”之間關系程度作為之間關系程度作為“權權”5 5、網(wǎng)絡規(guī)劃應用：、網(wǎng)絡規(guī)劃應用：例例3.1.13.1.

9、1：節(jié)目排序問題：節(jié)目排序問題 一場文藝演出共有一場文藝演出共有8 8個節(jié)目，全體演員中有個節(jié)目，全體演員中有1010人人須參加兩個以上的節(jié)目，如下表須參加兩個以上的節(jié)目，如下表3.1-13.1-1中中 符符號所示。號所示。若節(jié)目主辦者希望首尾兩個節(jié)目為若節(jié)目主辦者希望首尾兩個節(jié)目為A A和和HH，或為，或為H H和和A A，還希望每個演員不連續(xù)參加兩個節(jié)目的演出，則應，還希望每個演員不連續(xù)參加兩個節(jié)目的演出，則應如何安排節(jié)目表。如何安排節(jié)目表。3 3運籌決策運籌決策8版權所有 肖智 重慶大學經(jīng)濟與工商管理學院表表3.1-13.1-1 演員演員節(jié)目節(jié)目1 12 23 34 45 56 67 7

10、8 89 91010A A B B C C DD E E F F GG HH 3 3運籌決策運籌決策9版權所有 肖智 重慶大學經(jīng)濟與工商管理學院分析：分析： 把節(jié)目作為研究對象，用點表示。如果兩個節(jié)目把節(jié)目作為研究對象，用點表示。如果兩個節(jié)目無同一名演員參加，這說明二者可以緊排在一起，則無同一名演員參加，這說明二者可以緊排在一起，則給相應的兩點間連結一條邊，得到下列圖給相應的兩點間連結一條邊，得到下列圖3.1-73.1-7。這。這就是本例的網(wǎng)絡模型。于是問題歸結為：從圖中找出就是本例的網(wǎng)絡模型。于是問題歸結為：從圖中找出一條從一條從A A到到HH或從或從HH到到A A且通過所有結點的鏈，且每一

11、且通過所有結點的鏈，且每一個點只通過一次。個點只通過一次。不難看出，這樣的路有四條：不難看出，這樣的路有四條： AFBCGDEH AFBCGDEH HEDGCBFA HEDGCBFA AFGCBDEH AFGCBDEH HEDBCGFA HEDBCGFA則文藝演出的節(jié)目表可按上面任一順序安排。則文藝演出的節(jié)目表可按上面任一順序安排。 3 3運籌決策運籌決策10版權所有 肖智 重慶大學經(jīng)濟與工商管理學院圖圖3.1-73.1-7HAGFEDCB3 3運籌決策運籌決策11版權所有 肖智 重慶大學經(jīng)濟與工商管理學院例例3.1.23.1.2：電話線架設問題：電話線架設問題 某地某地7 7個村鎮(zhèn)之間的現(xiàn)有

12、交通道路如下圖個村鎮(zhèn)之間的現(xiàn)有交通道路如下圖3.1-83.1-8所示，邊旁數(shù)字為各村鎮(zhèn)之間道路的長度?，F(xiàn)要沿交所示，邊旁數(shù)字為各村鎮(zhèn)之間道路的長度?，F(xiàn)要沿交通道路架設電話線，使各村之間均能通話。應如何架通道路架設電話線，使各村之間均能通話。應如何架線使總長最短線使總長最短? ? 圖圖3.1-8 3.1-8 14237569 96 62 21 13 37 78 85 59 97 72 29 94 43 3運籌決策運籌決策12版權所有 肖智 重慶大學經(jīng)濟與工商管理學院例例3.1.33.1.3：醫(yī)院選址問題：醫(yī)院選址問題 已知某地區(qū)的交通網(wǎng)絡如圖已知某地區(qū)的交通網(wǎng)絡如圖3.1-93.1-9所示，其點

13、代所示，其點代表居民小區(qū)，邊表示公路，邊旁的數(shù)字表示小區(qū)間公表居民小區(qū)，邊表示公路，邊旁的數(shù)字表示小區(qū)間公路距離。問試：區(qū)中心醫(yī)院應建在哪個小區(qū)，可使離路距離。問試：區(qū)中心醫(yī)院應建在哪個小區(qū)，可使離醫(yī)院最遠的小區(qū)居民就診時所走的路程最近？醫(yī)院最遠的小區(qū)居民就診時所走的路程最近？ 圖圖3.1-93.1-914237569 96 62 21 13 37 78 85 59 97 72 29 94 46 63 33 3運籌決策運籌決策13版權所有 肖智 重慶大學經(jīng)濟與工商管理學院 分析：分析： 可以化為一系列求最短路問題?？梢曰癁橐幌盗星笞疃搪穯栴}。 先求出先求出1 1到其它各點的最短路長到其它各點的

14、最短路長d d1i1i, , 令令 D(1)=max(dD(1)=max(d1212，,d,d1717) ) 表示若醫(yī)院建在表示若醫(yī)院建在1 1，則離醫(yī)院最遠的小區(qū)距離為，則離醫(yī)院最遠的小區(qū)距離為D(1)D(1) 再依次計算再依次計算2 2，3 3，7 7到其余各點的最短路，類似到其余各點的最短路，類似求出求出D(2)D(2)，D(3)D(3)，D(7)D(7)。 D(i)D(i)（i i1 1，7 7）中最小者即為所求。）中最小者即為所求。3 3運籌決策運籌決策14版權所有 肖智 重慶大學經(jīng)濟與工商管理學院 6 6、最小樹問題、最小樹問題1 1）最小樹問題）最小樹問題（1 1）什么是樹？）什

15、么是樹？ 無圈連通圖。無圈連通圖。（2 2）什么是最小樹？）什么是最小樹？ 權重之和最小的樹。權重之和最小的樹。（3 3）最小樹問題：）最小樹問題：例例3.2.13.2.1：以例：以例3.1.23.1.2為例，電話線架設問題為例，電話線架設問題 某地某地7 7個村鎮(zhèn)之間的現(xiàn)有交通道路如下圖個村鎮(zhèn)之間的現(xiàn)有交通道路如下圖3.2-13.2-1所示，邊旁數(shù)字為各村鎮(zhèn)之間道路的長度?，F(xiàn)要沿交所示，邊旁數(shù)字為各村鎮(zhèn)之間道路的長度?，F(xiàn)要沿交通道路架設電話線，使各村之間均能通話。應如何架通道路架設電話線，使各村之間均能通話。應如何架線使總長最短線使總長最短? ? 3 3運籌決策運籌決策15版權所有 肖智 重

16、慶大學經(jīng)濟與工商管理學院 圖圖3.2-13.2-1例例3.2.23.2.2： 某公司擬鋪設海上油管，要求將海上六口油井連某公司擬鋪設海上油管，要求將海上六口油井連通，僅通，僅1 1 號油井與海岸相連，距離為號油井與海岸相連，距離為5 5海里。已知，海里。已知，海上六口油井間的距離如下表海上六口油井間的距離如下表3.2-13.2-1。試問，應如何。試問，應如何鋪設油管使鋪設油管的總長最短？鋪設油管使鋪設油管的總長最短？14237569 96 62 21 13 37 78 85 59 97 72 29 94 43 3運籌決策運籌決策16版權所有 肖智 重慶大學經(jīng)濟與工商管理學院 表表3.2-1 3

17、.2-1 單位：海里單位：海里2 2、最小樹問題求解、最小樹問題求解1 1）破圈法：）破圈法：（1 1）適用于網(wǎng)絡圖已存在的問題；）適用于網(wǎng)絡圖已存在的問題；（2 2）基本思路：對網(wǎng)絡圖中每一個圈都破掉其最長）基本思路：對網(wǎng)絡圖中每一個圈都破掉其最長 邊邊, , 直至網(wǎng)絡圖中不存在圈為止。直至網(wǎng)絡圖中不存在圈為止。（3 3）例）例: :以例以例3.2-13.2-1為例，步驟如下圖為例，步驟如下圖3.2-2 3.2-2 從從 到到 2 2 3 3 4 4 5 5 6 6 1 1 8 8 13 13 9 9 16 16 20 20 2 2 10 10 7 7 12 12 15 15 3 3 18

18、18 11 11 6 6 4 4 9 9 17 17 5 5 19 193 3運籌決策運籌決策17版權所有 肖智 重慶大學經(jīng)濟與工商管理學院 圖圖3.2-2 3.2-2 2 2）避圈法：）避圈法：（1 1）適用于網(wǎng)絡圖不存在的問題；）適用于網(wǎng)絡圖不存在的問題；（2 2）基本思路：對網(wǎng)絡圖中在不構成圈的條件下，）基本思路：對網(wǎng)絡圖中在不構成圈的條件下， 每次連接距離最短的邊，直至網(wǎng)絡圖中各點連每次連接距離最短的邊，直至網(wǎng)絡圖中各點連 通為止。通為止。14237569 96 62 21 13 37 78 85 59 97 72 29 94 4最短距離為最短距離為:17:17海里海里3 3運籌決策運

19、籌決策18版權所有 肖智 重慶大學經(jīng)濟與工商管理學院 （3 3）以例）以例2.2-22.2-2為例為例, ,具體步驟如下表具體步驟如下表3.2-23.2-2和圖和圖3.2-3 3.2-3 表表3.2-2 3.2-2 單位：海里單位：海里 圖圖3.2-33.2-3從從 到到2 23 34 45 56 61 12 23 34 45 58 89 913131616202010107 712121515181811116 69 9171719191236457 76 68 89 91010海岸海岸5 5最短距離為最短距離為: :4545海里海里3 3運籌決策運籌決策19版權所有 肖智 重慶大學經(jīng)濟與工

20、商管理學院 7 7、最短路問題、最短路問題1 1）最短路問題）最短路問題（1 1）什么是最短路？）什么是最短路？ 在一網(wǎng)絡中，求給定一初始點在一網(wǎng)絡中，求給定一初始點v vs s到一終點到一終點v vt t的一條的一條路長最短的路（即路的各邊權數(shù)之和最?。?。路長最短的路（即路的各邊權數(shù)之和最?。?（2 2）最短路問題：）最短路問題： 例例3.3.13.3.1： 某企業(yè)擬鋪設一條從某企業(yè)擬鋪設一條從A A地到地到F F地的輸油管道，可供地的輸油管道，可供選擇路線及各點間的距離如下圖選擇路線及各點間的距離如下圖3.3-1 3.3-1 ；試問：應如；試問：應如何選擇路線使總距離最短？何選擇路線使總

21、距離最短？ 3 3運籌決策運籌決策20版權所有 肖智 重慶大學經(jīng)濟與工商管理學院圖圖3.3-13.3-1A AB B1 1B B2 2C C1 1C C2 2C C3 3C C4 4DD1 1DD2 2DD3 3E E1 1E E2 2F F4 45 52 23 36 68 87 77 75 58 84 45 53 34 44 44 43 35 56 62 21 13 34 43 33 3運籌決策運籌決策21版權所有 肖智 重慶大學經(jīng)濟與工商管理學院例例3.3-23.3-2：設備更新問題：設備更新問題 某公司擬對一臺設備制定某公司擬對一臺設備制定5 5年期的設備更新計劃年期的設備更新計劃使總的

22、支付費用最少。相關信息如下表使總的支付費用最少。相關信息如下表3.3-1 3.3-1 ： 表表3.3-13.3-1購置年限購置年限 2000 2000 2001 2001 2002 2002 2003 2003 2004 2004購置費用購置費用 15 15 16 16 17 17 18 18 19 19使用年數(shù)使用年數(shù) 0-1 0-1 1-2 1-2 2-3 2-3 3-4 3-4 4-5 4-5維修費用維修費用 2 2 6 6 12 12 20 20 38 383 3運籌決策運籌決策22版權所有 肖智 重慶大學經(jīng)濟與工商管理學院 2 2）最短路問題求解）最短路問題求解（1 1）窮舉法：）窮

23、舉法：適用于路不多的簡單問題；適用于路不多的簡單問題；求出每條路長，比較各條路長求一路長最短的路。求出每條路長，比較各條路長求一路長最短的路。例例3.3-3:3.3-3:求如下網(wǎng)絡圖求如下網(wǎng)絡圖3.3-23.3-2中點中點1 1到點到點6 6最短路。最短路。 圖圖3.3-23.3-21236459 92 23 36 69 95 54 46 63 3運籌決策運籌決策23版權所有 肖智 重慶大學經(jīng)濟與工商管理學院求解步驟如下圖求解步驟如下圖3.3-33.3-3： 圖圖3.3-33.3-3 1236459 92 23 36 69 95 54 46 6序號序號 路路 路長路長 最短路最短路 1 1-2

24、-4-6 161 1-2-4-6 162 1-2-4-5-6 232 1-2-4-5-6 23 3 1-3-5-6 173 1-3-5-6 175 1-3-2-4-6 15 1-3-2-4-65 1-3-2-4-6 15 1-3-2-4-64 1-3-2-4-5-6 224 1-3-2-4-5-6 223 3運籌決策運籌決策24版權所有 肖智 重慶大學經(jīng)濟與工商管理學院（2 2）標號法：）標號法： 例例3.3-43.3-4：以例：以例3.3-13.3-1為例，解題步驟如下圖為例，解題步驟如下圖2.3-42.3-4 圖圖3.3-4 3.3-4 A AB B1 1B B2 2C C1 1C C2

25、2C C3 3C C4 4DD1 1DD2 2DD3 3E E1 1E E2 2F F4 45 52 23 36 68 87 77 75 58 84 45 53 34 44 44 43 35 56 62 21 13 34 43 30 04 45 56 6121210107 7111112121414141414141717最短路為：最短路為：ABAB1 1C C2 2DD2 2E E2 2F F；路長為：；路長為：17173 3運籌決策運籌決策25版權所有 肖智 重慶大學經(jīng)濟與工商管理學院例例3.3-53.3-5：以例：以例3.3-23.3-2為例為例 解：解：1 1）根據(jù)題意建立網(wǎng)絡模型如下

26、圖）根據(jù)題意建立網(wǎng)絡模型如下圖3.3-53.3-5 圖圖3.3-5 3.3-5 3 3運籌決策運籌決策26版權所有 肖智 重慶大學經(jīng)濟與工商管理學院 2 2）應用標號法對結點標號，步驟如下圖）應用標號法對結點標號，步驟如下圖3.3-63.3-6。 圖圖3.3-63.3-6 0 017172323353548486060最短路為：最短路為：0-2-50-2-5；路長為：；路長為：6060；答：該設備先使用；答：該設備先使用2 2年后，更新再使用年后，更新再使用3 3年。年。3 3運籌決策運籌決策27版權所有 肖智 重慶大學經(jīng)濟與工商管理學院（二）線性規(guī)劃決策（二）線性規(guī)劃決策1 1、本章的目的：

27、、本章的目的： 理解線性規(guī)劃基本概念、特征、應用，掌握生產理解線性規(guī)劃基本概念、特征、應用，掌握生產計劃、合理下料等典型問題的數(shù)學模型建立、分析思計劃、合理下料等典型問題的數(shù)學模型建立、分析思路、求解方法，了解這類典型問題的重要作用與應用路、求解方法，了解這類典型問題的重要作用與應用2 2、主要內容：、主要內容： 1 1）線性規(guī)劃概述）線性規(guī)劃概述 2 2）生產計劃與合理下料問題）生產計劃與合理下料問題 3 3）案例討論）案例討論3 3、本講的重點與難點：、本講的重點與難點： 1 1）重點：掌握數(shù)學模型基本要素、特征，數(shù)學模）重點：掌握數(shù)學模型基本要素、特征，數(shù)學模型型 建立，求解思路與方法，

28、其作用與應用。建立，求解思路與方法，其作用與應用。 2 2）難點：模型建立、分析思路）難點：模型建立、分析思路3 3運籌決策運籌決策28版權所有 肖智 重慶大學經(jīng)濟與工商管理學院 4 4、線性規(guī)劃問題、線性規(guī)劃問題1 1）線性規(guī)劃概述）線性規(guī)劃概述（1 1）什么是線性規(guī)劃？）什么是線性規(guī)劃？ 線性規(guī)劃是求一個線性函數(shù)在滿足一組線性等式線性規(guī)劃是求一個線性函數(shù)在滿足一組線性等式 或不等式方程條件下的極值問題的統(tǒng)稱?；虿坏仁椒匠虠l件下的極值問題的統(tǒng)稱。（2 2）線性規(guī)劃問題的組成）線性規(guī)劃問題的組成決策變量構成反映決策者目標的線性目標函數(shù)決策變量構成反映決策者目標的線性目標函數(shù)決策變量的線性等式或

29、不等式構成的約束方程決策變量的線性等式或不等式構成的約束方程限制決策變量取值范圍的非負約束限制決策變量取值范圍的非負約束（3 3）線性規(guī)劃的基本特征：）線性規(guī)劃的基本特征： 目標函數(shù)是線性的目標函數(shù)是線性的 約束條件是線性的約束條件是線性的3 3運籌決策運籌決策29版權所有 肖智 重慶大學經(jīng)濟與工商管理學院 （4 4）線性規(guī)劃基本模型）線性規(guī)劃基本模型 （2.2.12.2.1）（5 5）線性規(guī)劃模型的三要素：）線性規(guī)劃模型的三要素： 決策變量、目標、約束。決策變量、目標、約束。（6 6）建立模型的基本步驟：）建立模型的基本步驟： 根據(jù)問題確定目標；根據(jù)問題確定目標；njxmibxaxcZjnj

30、ijijnjjj,.,2 , 1,0,.,2 , 1),(max(min)113 3運籌決策運籌決策30版權所有 肖智 重慶大學經(jīng)濟與工商管理學院 根據(jù)目標設計決策變量；根據(jù)目標設計決策變量； 根據(jù)目標與決策變量設計目標函數(shù)；根據(jù)目標與決策變量設計目標函數(shù)； 根據(jù)影響目標因素的關系與限制設計約束條件。根據(jù)影響目標因素的關系與限制設計約束條件。（7 7）線性規(guī)劃基本求解方法）線性規(guī)劃基本求解方法 圖解法圖解法a.a.適用于兩個變量的線性規(guī)劃問題。適用于兩個變量的線性規(guī)劃問題。b.b.應用舉例應用舉例單純形法單純形法 適用于一般線性規(guī)劃問題。適用于一般線性規(guī)劃問題。計算機解法計算機解法a.a.適用

31、于一般線性規(guī)劃問題。適用于一般線性規(guī)劃問題。b.b.應用舉例應用舉例（8 8）線性規(guī)劃應用舉例）線性規(guī)劃應用舉例3 3運籌決策運籌決策31版權所有 肖智 重慶大學經(jīng)濟與工商管理學院 3 3運籌決策運籌決策32版權所有 肖智 重慶大學經(jīng)濟與工商管理學院合理下料問題合理下料問題 某鋼管廠有一批某鋼管廠有一批1010米長的鋼管，一顧客需要米長的鋼管，一顧客需要3 3米米長的鋼管長的鋼管6060根，根，4 4米長的鋼管米長的鋼管9090根，試問：應如何下根，試問：應如何下料，使鋼管總消耗最少？料，使鋼管總消耗最少？運輸問題運輸問題 某企業(yè)有某企業(yè)有A A1 1、A A2 2、A A3 3三個分廠生產同

32、一種產品，三個分廠生產同一種產品，其產量分別是其產量分別是5555、4545、6060個單位?，F(xiàn)擬將該企業(yè)的個單位?，F(xiàn)擬將該企業(yè)的產品運往產品運往B B1 1、B B2 2、B B3 3、B B4 4 四個銷地進行銷售，這四四個銷地進行銷售，這四個銷地銷量分別為個銷地銷量分別為2020、3030、5050、6060個單位。已知：個單位。已知：產地到銷地的單位運費如表產地到銷地的單位運費如表3.4-23.4-2所示的運費表。試所示的運費表。試問：應如何調度運輸使總運費最少？問：應如何調度運輸使總運費最少？ 3 3運籌決策運籌決策33版權所有 肖智 重慶大學經(jīng)濟與工商管理學院表表3.4-2 3.4

33、-2 運輸信息表運輸信息表運價運價, 銷地銷地 運量運量產地產地 B B1 1B B2 2B B3 3B B4 4產產量量A A1 11435 5555A A2 221634545A A3 315316060銷量銷量20305060 160 160 1601603 3運籌決策運籌決策34版權所有 肖智 重慶大學經(jīng)濟與工商管理學院 指派問題指派問題 某企業(yè)一部門有某企業(yè)一部門有A A1 1、A A2 2、A A3 3、A A4 4四個人，該部門四個人，該部門有有B B1 1、B B2 2、B B3 3、B B4 4 四項工作需要做，要求每人只能四項工作需要做，要求每人只能做一項工作做一項工作,

34、,每項工作只能一人去做。已知：每人做每每項工作只能一人去做。已知：每人做每項工作的單位消耗如下表項工作的單位消耗如下表 3.4-3 3.4-3 所示。試問：應如何所示。試問：應如何分配工作使總消耗最少？分配工作使總消耗最少？表表3.4-3 3.4-3 單耗信息表單耗信息表單耗單耗 工作工作人人 B1 B2 B3 B4A162 15 A2312 816 A32 9 713 A45 11 9123 3運籌決策運籌決策35版權所有 肖智 重慶大學經(jīng)濟與工商管理學院人需求問題人需求問題 某郵局從星期一到星期日，每天需要工作人員數(shù)某郵局從星期一到星期日，每天需要工作人員數(shù)見下表見下表3.4-43.4-4

35、。郵局規(guī)定每位工作人員連續(xù)工作。郵局規(guī)定每位工作人員連續(xù)工作5 5天，天，休息休息2 2天。試問：該郵局應如何雇傭工作人員使所雇天。試問：該郵局應如何雇傭工作人員使所雇傭總人數(shù)最少？傭總人數(shù)最少？表表3.4-4 3.4-4 郵局需要工作人員表郵局需要工作人員表星星 期期 一一二二三三四四五五六六日日需要工作人員數(shù)需要工作人員數(shù) 17171313151519191414161611113 3運籌決策運籌決策36版權所有 肖智 重慶大學經(jīng)濟與工商管理學院 投資問題投資問題 假定某單位擬在以后假定某單位擬在以后4 4年內對某項目依次投資年內對某項目依次投資300300萬，萬，500500萬，萬，90

36、0900萬，萬，600600萬元，為籌措這筆資金，萬元，為籌措這筆資金，該單位打算出售長期債券。長期債券的市場年利率四該單位打算出售長期債券。長期債券的市場年利率四年中依次為年中依次為6.56.5，5 5，6.56.5，5.55.5，可連續(xù)付，可連續(xù)付 1010年利息后還本。與此同時，有短期存款年利率分別年利息后還本。與此同時，有短期存款年利率分別為為5.55.5，5.55.5，4.54.5。問最佳投資策略是什么？。問最佳投資策略是什么？即每年出售多少長期債券和用多少作為短期存款，使即每年出售多少長期債券和用多少作為短期存款，使最后付出成本最?。孔詈蟾冻龀杀咀钚。? 3運籌決策運籌決策37版權

37、所有 肖智 重慶大學經(jīng)濟與工商管理學院生產進度問題生產進度問題 某工廠生產的一種產品需求有季節(jié)性，只能在某工廠生產的一種產品需求有季節(jié)性，只能在4 4個月內銷售，生產也要在這個月內銷售，生產也要在這 4 4個月內進行?？梢栽谡齻€月內進行。可以在正常工作時間生產，也可以因生產能力的限制而在加班常工作時間生產，也可以因生產能力的限制而在加班時間生產。某個月產品產量可以大于當月的銷售量而時間生產。某個月產品產量可以大于當月的銷售量而將多余的產品存貯，但要在當月付出存貯費。第將多余的產品存貯，但要在當月付出存貯費。第 4 4月月末要將產品全部售完，以免存貯到第末要將產品全部售完，以免存貯到第 2 2年

38、。產品在正年。產品在正常工作時間生產，每月最多能生產常工作時間生產，每月最多能生產100100單位，單位成單位，單位成本為本為1515元。在加班時間生產，每月最多能生產元。在加班時間生產，每月最多能生產3030單單位，單位成本為位，單位成本為2020元。每月生產量及其平均單位成元。每月生產量及其平均單位成本不一定要相等。存貯費每月每單位本不一定要相等。存貯費每月每單位0.20.2元。元。4 4個月個月的需求量分別為的需求量分別為3 3運籌決策運籌決策38版權所有 肖智 重慶大學經(jīng)濟與工商管理學院5050、130130、150150及及 100100單位。試建立模型以確定每單位。試建立模型以確定

39、每月正常時間及加班時間各生產多少產品，使總成本最月正常時間及加班時間各生產多少產品，使總成本最小小工廠選址問題工廠選址問題有有A A、B B、C C三個原料產地，其原料要在工廠加工三個原料產地，其原料要在工廠加工制成成品，再在銷售地出售。制成成品，再在銷售地出售。A A、B B兩地又是銷售地兩地又是銷售地已知有關數(shù)據(jù)見下表已知有關數(shù)據(jù)見下表3.4-53.4-5。4 4噸原料制成噸原料制成1 1噸成品。噸成品。 A A、B B間距離間距離150150公里，公里，B B、C C間距離間距離200200公里，公里，C C、A A間距離間距離100100公里。原料運費公里。原料運費300300元元/

40、/萬噸萬噸. .公里，成品公里，成品運費運費250250元元/ /萬噸萬噸. .公里。如在公里。如在B B地設廠，每年生產成地設廠，每年生產成品不能超過品不能超過5 5萬噸，在萬噸，在A A、B B兩地設廠，生產規(guī)模不受兩地設廠，生產規(guī)模不受限制。試建立數(shù)學模型，使決策人能夠決定在哪幾個限制。試建立數(shù)學模型，使決策人能夠決定在哪幾個地點設廠，生產能力多大，以達到總費用（為簡化問地點設廠，生產能力多大，以達到總費用（為簡化問題，這里只包括產品加工費、原料及成品運費）最小題，這里只包括產品加工費、原料及成品運費）最小3 3運籌決策運籌決策39版權所有 肖智 重慶大學經(jīng)濟與工商管理學院表表3.4-5

41、 3.4-5 城市間汽車運輸問題城市間汽車運輸問題 某汽車運輸公司經(jīng)營某汽車運輸公司經(jīng)營A A、B B、C C三個城市之間的貨三個城市之間的貨物運輸業(yè)務，任意兩個城市之間有公路連通，貨運量物運輸業(yè)務，任意兩個城市之間有公路連通，貨運量及每車的利潤分別如下表及每車的利潤分別如下表3.4-63.4-6和表和表3.4-73.4-7所示。該所示。該公司有汽車公司有汽車250250輛，每周每輛汽車最多在兩個城市間輛，每周每輛汽車最多在兩個城市間單單程運行單單程運行 4 4 次，由于技術上及業(yè)務上的原因，全次，由于技術上及業(yè)務上的原因，全部汽車每周末必須停在部汽車每周末必須停在 A A 城。汽車回空沒有利

42、潤，城。汽車回空沒有利潤，地地點點每年原料產量每年原料產量（萬噸）（萬噸）每年成品銷售量每年成品銷售量（萬噸）（萬噸）每萬噸成品所需加每萬噸成品所需加工費（萬元）工費（萬元）A AB BC C3030262624247 713130 05.55.54 43 33 3運籌決策運籌決策40版權所有 肖智 重慶大學經(jīng)濟與工商管理學院也不計成本。試建立獲得最大利潤的數(shù)學模型。也不計成本。試建立獲得最大利潤的數(shù)學模型。表表3.4-6 3.4-6 每周貨運量（車）每周貨運量（車） 表表3.4-7 3.4-7 每周利潤（元）每周利潤（元） 發(fā)站發(fā)站 到站到站A AB BC CA AB BC C5050100

43、100150150150150200200300300發(fā)站發(fā)站 到站到站A AB BC CA AB BC C1001005005001501501001002502502002003 3運籌決策運籌決策41版權所有 肖智 重慶大學經(jīng)濟與工商管理學院生產計劃問題：生產計劃問題：a.a.問題：問題： 某公司擬使用三種原材料生產某公司擬使用三種原材料生產A A、B B兩種產品。生兩種產品。生產產1 1件件A A產品所需原材料產品所需原材料1 1、2 2分別是分別是2 2噸、噸、1 1噸噸, ,生產生產1 1件件B B產品所需原材料產品所需原材料1 1、2 2、3 3分別是分別是1 1噸、噸、2 2噸

44、、噸、 3 3噸。噸。產品產品A A、B B的單位銷售收益分別為的單位銷售收益分別為3 3元和元和2 2元。公司對元。公司對三種原材料三種原材料1 1、2 2、3 3的擁有量分別是的擁有量分別是6 6噸、噸、8 8噸、噸、6 6噸。噸。若生產出的產品能全部銷售，問如何制定生產計劃使若生產出的產品能全部銷售，問如何制定生產計劃使總銷售收益最大？總銷售收益最大？b.b.建立數(shù)學模型：建立數(shù)學模型：a a）建?；舅枷耄海┙；舅枷耄?按三要素進行分析，從分析目標函數(shù)的構成人手按三要素進行分析，從分析目標函數(shù)的構成人手3 3運籌決策運籌決策42版權所有 肖智 重慶大學經(jīng)濟與工商管理學院根據(jù)要求的問

45、題，確定（假設）決策變量、構建目標根據(jù)要求的問題，確定（假設）決策變量、構建目標函數(shù)和約束條件。函數(shù)和約束條件。 b b）分析）分析（a a）目標：總銷售收益最大）目標：總銷售收益最大 （b b）銷售收益的構成：單位銷售收益）銷售收益的構成：單位銷售收益銷量銷量 （c c）已知：產品）已知：產品A A、B B單位銷售收益分別為：單位銷售收益分別為：3 3元元 和和2 2元元 c c）建模）建模（a a）假設：產品）假設：產品A A的銷量為的銷量為x x1 1、產品、產品B B的銷量為的銷量為x x2 2 （b b）目標函數(shù)：）目標函數(shù)：Z=3 xZ=3 x1 1 +2x +2x2 2（c c）

46、約束條件：）約束條件： 資源約束信息：資源約束信息： 3 3運籌決策運籌決策43版權所有 肖智 重慶大學經(jīng)濟與工商管理學院 資源限制信息表資源限制信息表 資源約束：資源約束： （3.4-13.4-1） A B資源總量資源總量資源資源1 1 2 1 6資源資源2 2 1 2 8資源資源3 3 0 3 663826222121xxxxx3 3運籌決策運籌決策44版權所有 肖智 重慶大學經(jīng)濟與工商管理學院 數(shù)學模型：數(shù)學模型： （3.4-23.4-2）d.d.求解：求解：a a）計算機解法）計算機解法b b）圖解法）圖解法121212212max322628360,0zxxxxxxxxx3 3運籌決

47、策運籌決策45版權所有 肖智 重慶大學經(jīng)濟與工商管理學院（a a）適用范圍）適用范圍: :兩個變量的線性規(guī)劃問題。兩個變量的線性規(guī)劃問題。（b b）基本思想及步驟：）基本思想及步驟：第一步：根據(jù)約束條件畫出可行域第一步：根據(jù)約束條件畫出可行域K K。第二步：在目標函數(shù)族中任選一條目標函數(shù)直第二步：在目標函數(shù)族中任選一條目標函數(shù)直 線線L L。第三步：將第三步：將L L沿目標函數(shù)增加（減少）的方向沿目標函數(shù)增加（減少）的方向 平行移動直到剛要離開可行域平行移動直到剛要離開可行域K K為止。為止。e.e.用圖解法求生產計劃問題（用圖解法求生產計劃問題（3.4-23.4-2）。）。3 3運籌決策運籌

48、決策46版權所有 肖智 重慶大學經(jīng)濟與工商管理學院 （三）運輸決策（三）運輸決策1 1、本節(jié)的目的：、本節(jié)的目的： 理解運輸決策問題的特征、應用，掌握運輸決策典理解運輸決策問題的特征、應用，掌握運輸決策典型問題的數(shù)學模型建立、分析思路、求解方法，了解這型問題的數(shù)學模型建立、分析思路、求解方法，了解這類典型問題的重要作用與應用類典型問題的重要作用與應用2 2、主要內容：、主要內容： 1 1）運輸決策問題）運輸決策問題 2 2）運輸決策問題求解）運輸決策問題求解 3 3）不平衡運輸決策問題）不平衡運輸決策問題3 3、本節(jié)的重點與難點：、本節(jié)的重點與難點： 1 1）重點：掌握運輸決策問題模型基本要素

49、、特征，）重點：掌握運輸決策問題模型基本要素、特征， 模型建立，求解思路與方法，其作用與應用。模型建立，求解思路與方法，其作用與應用。 2 2）難點：模型建立、分析思路）難點：模型建立、分析思路3 3運籌決策運籌決策47版權所有 肖智 重慶大學經(jīng)濟與工商管理學院4 4、運輸決策問題運輸決策問題1 1）例）例1 1 運輸問題運輸問題 某企業(yè)有某企業(yè)有A1A1、A2A2、A3A3三個分廠生產同一種產三個分廠生產同一種產品，其產量分別是品，其產量分別是5555、4545、6060個單位?，F(xiàn)擬將該個單位?，F(xiàn)擬將該企業(yè)的產品運往企業(yè)的產品運往B1B1、B2B2、B3B3、B4 B4 四個銷地進行四個銷地

50、進行銷售，這四個銷地銷量分別為銷售，這四個銷地銷量分別為2020、3030、5050、6060個個單位。已知：產地到銷地的單位運費如表單位。已知：產地到銷地的單位運費如表3-5-13-5-1所示所示的運費表。試問：應如何調度運輸使總運費最少？的運費表。試問：應如何調度運輸使總運費最少？ 3 3運籌決策運籌決策48版權所有 肖智 重慶大學經(jīng)濟與工商管理學院表表3-5-1 3-5-1 運輸信息表運輸信息表運價, 銷地 運量產地 B1B2B3B4產產量量A11435 5555A221634545A315316060銷量銷量20305060 160 160 1601603 3運籌決策運籌決策49版權所

51、有 肖智 重慶大學經(jīng)濟與工商管理學院2 2）運輸問題模型）運輸問題模型（1 1）數(shù)學模型）數(shù)學模型：例例1 1對應的對應的數(shù)學模型數(shù)學模型（3-5-13-5-1）4,3,2,1;3,2,106050302060455535362534min342414332313322212312111343332312423222114131211343332312423222114131211jixxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxZij，3 3運籌決策運籌決策50版權所有 肖智 重慶大學經(jīng)濟與工商管理學院 一般數(shù)學模型一般數(shù)學模型（3-5-23-5-2）1 11 2

52、1 31 42 12 22 32 43 13 23 33 443526353C Xxxxxxxxxxxxx 設（2 2）圖表模型）圖表模型例例1 1對應的圖表對應的圖表模型模型 njmixnjbxmiaxxcZijmijijnjiijminjijij,.,2,1;,.,2,1;0,.,2,1;,.,2,1;min11110;1, 2,3;1, 2,3, 4;ijxij3 3運籌決策運籌決策51版權所有 肖智 重慶大學經(jīng)濟與工商管理學院表表3-5-3 3-5-3 運輸信息表運輸信息表運價, 銷地 量產地B1B2B3B4產量產量A1x111x124x133x145 55 55A2x212x221x

53、236x2434545A3x311x325x333x3416060銷量銷量20305060 160 160 160 160 0;1,2,;1,2, ;ijxim jn3 3運籌決策運籌決策52版權所有 肖智 重慶大學經(jīng)濟與工商管理學院表表3-5-3 3-5-3 運輸信息表運輸信息表0;1,2,3;1,2,3,4;ijxij運價, 銷地 運量產地B1B2Bn產量產量A1x11c c1111x12c c1212x1nc c1n1na a1 1. .: : : : : : : : : : : : :Amxmnc cm1m1xm2c cm2m2xmnc cmnmna amm銷量銷量b1b2bn a a

54、i ibbj j ij ijij ij3 3運籌決策運籌決策53版權所有 肖智 重慶大學經(jīng)濟與工商管理學院 （3 3）基本特征：）基本特征： 特殊線性規(guī)劃問題；特殊線性規(guī)劃問題；約束條件分別為各產（銷）地的運出（接收）約束條件分別為各產（銷）地的運出（接收） 量等于其生產（銷量）量；量等于其生產（銷量）量；2 2）運輸問題）運輸問題的求解方法的求解方法（1 1）主要主要求解方法：求解方法： 計算機計算機方法；方法； 單純形法單純形法； 表上作業(yè)法表上作業(yè)法； 圖上作業(yè)法；圖上作業(yè)法；（2 2）表上作業(yè)法）表上作業(yè)法 什么什么是表上作業(yè)法？是表上作業(yè)法？3 3運籌決策運籌決策54版權所有 肖智

55、重慶大學經(jīng)濟與工商管理學院 表上作業(yè)法是單純形法在求解運輸問題時的一種簡表上作業(yè)法是單純形法在求解運輸問題時的一種簡化方法，其本質是單純形法。化方法，其本質是單純形法。（2 2）表上作業(yè)法的基本步驟：）表上作業(yè)法的基本步驟： 找找一初始的調運方案（初始基可行解）；一初始的調運方案（初始基可行解）； （必須滿足（必須滿足：a.a.產銷產銷平衡平衡, , b.b.數(shù)字數(shù)字格（基變量）格（基變量）的的個數(shù)個數(shù)為為: :產地數(shù)產地數(shù)+ +銷地數(shù)銷地數(shù)-1-1；常用最小元素法尋找）；常用最小元素法尋找） 判斷判斷：計算表（產銷平衡表）上空格（非基變量：計算表（產銷平衡表）上空格（非基變量）的的檢驗數(shù)，判

56、斷該方案是否為最優(yōu)方案（最優(yōu)解）檢驗數(shù)，判斷該方案是否為最優(yōu)方案（最優(yōu)解）, ,若是若是最優(yōu)方案，則停止計算；否則最優(yōu)方案，則停止計算；否則轉。轉。（因運輸問題為極小化問題，故最優(yōu)性條件為：因運輸問題為極小化問題，故最優(yōu)性條件為：檢驗檢驗數(shù)數(shù) 0 0；常用位勢法或閉合回路法計算檢驗數(shù)）；常用位勢法或閉合回路法計算檢驗數(shù)） 調整調整：確定某個空格和某個數(shù)字格的轉換：確定某個空格和某個數(shù)字格的轉換，3 3運籌決策運籌決策55版權所有 肖智 重慶大學經(jīng)濟與工商管理學院找出新的調運方案找出新的調運方案( (基可行解基可行解); );轉。轉。( (常用閉合回路常用閉合回路法進行調整法進行調整) )（3

57、3）應用舉例：（以例）應用舉例：（以例1 1為例為例） 用用最小元素法找一初始的調運方案；見最小元素法找一初始的調運方案；見表表3-5-43-5-4表表3-5-4 3-5-4 運輸問題求解表運輸問題求解表運價運價,量量 銷地銷地產地產地 B1 B2 B3 B4產量產量 A1143555 A2216345 A3153160 銷量銷量20305060 160 160 20203030606035350 015153053053 3運籌決策運籌決策56版權所有 肖智 重慶大學經(jīng)濟與工商管理學院判斷判斷: :用位勢法計算空格用位勢法計算空格( (非基變量非基變量) )檢驗數(shù)檢驗數(shù): :a. a. 應用

58、應用C Cij ij= =U Ui i+V+Vj j 計算數(shù)字格計算數(shù)字格( (基變量基變量) )的位勢的位勢U Ui i、V Vj j， 并令：并令： U U1 1=0=0；b.b. 應用應用 ij ij= =C Cij ij-( -(U Ui i+V+Vj j ) )計算空格計算空格( (非基變量非基變量) )的檢驗數(shù)的檢驗數(shù) ij ij; ; c. c. 若所有空格若所有空格( (非基變量非基變量) )的檢驗數(shù)的檢驗數(shù) klkl00，則停止計算，則停止計算, , 輸出最優(yōu)方案；否則轉。具體結果見下表輸出最優(yōu)方案；否則轉。具體結果見下表3-5-5:3-5-5:調整調整: :（用閉合回路法）

59、（用閉合回路法） a.a. 從某個檢驗數(shù)從某個檢驗數(shù) klkl00的空格的空格( (非基變量非基變量) )出發(fā)；根據(jù)出發(fā)；根據(jù)“遇見空格直行遇見空格直行”的原則做閉合回路的原則做閉合回路L L； b.b. 在閉合回路在閉合回路L L的奇拐點中找出最小運量，記為的奇拐點中找出最小運量，記為d;d;X X0 0=(20,0,35,0;0,30,15,0;0,0,0,60)=(20,0,35,0;0,30,15,0;0,0,0,60)T T; ; 對應的目標值為對應的目標值為Z Z0 0=305=3053 3運籌決策運籌決策57版權所有 肖智 重慶大學經(jīng)濟與工商管理學院表表3-5-5 3-5-5 運

60、輸問題求解續(xù)表運輸問題求解續(xù)表 c. c. 將閉合回路將閉合回路L L的每個奇拐點的運量都減去的每個奇拐點的運量都減去d d，每個，每個偶拐點的運量都加上偶拐點的運量都加上d d；得一新的調運方案；轉。；得一新的調運方案；轉。具體結果見下表具體結果見下表3-5-5:3-5-5:運價運價,量量 銷地銷地產地產地 B1 B2 B3 B4產量產量 A1143555 A2216345 A3153160 銷量銷量20305060 160 160 V V1 1= V= V2 2= V= V3 3= V= V4 4= =0 0U U1 1= = U U2 2= = U U3 3= = 3 31 13 30