第三章幾種特殊的線性規(guī)劃問題及其解法

1、 運(yùn)輸問題的表上作業(yè)法和指派問題運(yùn)輸問題的表上作業(yè)法和指派問題 的匈牙利解法。的匈牙利解法。 運(yùn)輸問題數(shù)學(xué)模型的特殊結(jié)構(gòu)，運(yùn)輸問題數(shù)學(xué)模型的特殊結(jié)構(gòu)， 0-1規(guī)劃及指派問題的特點(diǎn)。規(guī)劃及指派問題的特點(diǎn)。 整數(shù)規(guī)劃概念、模型及其解法，整數(shù)規(guī)劃概念、模型及其解法， 0-1變量的應(yīng)用。變量的應(yīng)用。 通過本章的學(xué)習(xí)，你應(yīng)該能夠：通過本章的學(xué)習(xí)，你應(yīng)該能夠： 某制藥集團(tuán)在全國(guó)設(shè)有某制藥集團(tuán)在全國(guó)設(shè)有3個(gè)某種中藥材的種植加個(gè)某種中藥材的種植加工基地，分別為工基地，分別為A1、A2、A3；每月藥材生產(chǎn)加工量分；每月藥材生產(chǎn)加工量分別為別為9、5和和7噸。該集團(tuán)每月從這些基地將加工好的噸。該集團(tuán)每月從這些基地

2、將加工好的藥材分別運(yùn)往全國(guó)藥材分別運(yùn)往全國(guó)4個(gè)不同的藥廠個(gè)不同的藥廠B1、B2、B3和和B4；4個(gè)藥廠每月藥材的需求量分別為個(gè)藥廠每月藥材的需求量分別為3、8、4和和6噸。已知噸。已知從每個(gè)基地到各藥廠每噸藥材的運(yùn)價(jià)如表從每個(gè)基地到各藥廠每噸藥材的運(yùn)價(jià)如表3-1所示，所示，則該集團(tuán)應(yīng)如何安排運(yùn)輸，使在滿足各藥廠需求的前則該集團(tuán)應(yīng)如何安排運(yùn)輸，使在滿足各藥廠需求的前提下總運(yùn)費(fèi)最少？提下總運(yùn)費(fèi)最少？ 單位（百元）單位（百元）藥藥 廠廠產(chǎn)量產(chǎn)量（噸）（噸）B1B2B3B4種種植植基基地地A1A2A32189341042725957需求量（噸）需求量（噸）384621屬于線性規(guī)劃問題，可以建立線性規(guī)劃

3、屬于線性規(guī)劃問題，可以建立線性規(guī)劃模型，并用單純形法求解。但使用單純表來計(jì)算模型，并用單純形法求解。但使用單純表來計(jì)算工作量非常大，所以對(duì)于特殊結(jié)構(gòu)的線性規(guī)劃模工作量非常大，所以對(duì)于特殊結(jié)構(gòu)的線性規(guī)劃模型，人們探討了更為型，人們探討了更為簡(jiǎn)便的求解方法簡(jiǎn)便的求解方法，從而大大，從而大大簡(jiǎn)化了計(jì)算。簡(jiǎn)化了計(jì)算。本章將介紹運(yùn)輸問題、本章將介紹運(yùn)輸問題、0-1規(guī)劃及指派問題等幾種規(guī)劃及指派問題等幾種特殊的線性規(guī)劃問題特殊的線性規(guī)劃問題及其對(duì)應(yīng)的及其對(duì)應(yīng)的特殊解法特殊解法。 生產(chǎn)1生產(chǎn)2生產(chǎn)3銷售銷售1銷售銷售4銷售銷售2銷售銷售3原材料1原材料2原材料3原材料4物流 單位（百元）單位（百元）藥藥 廠

4、廠產(chǎn)量產(chǎn)量（噸）（噸）B1B2B3B4種種植植基基地地A1A2A32189341042725957需求量（噸）需求量（噸）384621首先通過章前案例，分析運(yùn)輸問題的模型和特征。首先通過章前案例，分析運(yùn)輸問題的模型和特征。 2910713428425A1A2A3B1B2B3B4銷量銷量產(chǎn)量產(chǎn)量9573846x11x12x13x14x21x31x22x23x24x32x33x344 , 3 , 2 , 1; 3 , 2 , 106483759. .342414332313322212312111343332312423222114131211jixxxxxxxxxxxxxxxxxxxxxxxxx

5、tsij111213142122232431323334Min291073428425Zxxxxxxxxxxxx 某種物資需調(diào)運(yùn)。已知有某種物資需調(diào)運(yùn)。已知有m個(gè)產(chǎn)地，用個(gè)產(chǎn)地，用 表示，有表示，有n個(gè)銷地，用個(gè)銷地，用 表示，又知表示，又知m個(gè)產(chǎn)地的個(gè)產(chǎn)地的產(chǎn)量產(chǎn)量)分別為分別為 ，(可通寫為可通寫為ai )， n個(gè)銷地的個(gè)銷地的銷量分別為銷量分別為 ，（可通寫為，（可通寫為bj），從第），從第 i 個(gè)產(chǎn)個(gè)產(chǎn)地到第地到第 j 個(gè)銷地的單位物資運(yùn)價(jià)為個(gè)銷地的單位物資運(yùn)價(jià)為cij ，問如何調(diào)運(yùn)可使，問如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最少？總運(yùn)輸費(fèi)用最少？1,im1,jn12,ma aa12,nb bb銷銷

6、 地地產(chǎn)產(chǎn) 地地12n1m產(chǎn)產(chǎn) 量量銷銷 量量c11c12c1ncm1cm2cmnx11x12x1nxm1xm2xmna1amb1b2bn1111Min,1,2,1,2,0,1, 2,;1,2,mnijijijnijijmijjiijZc xxaimxbjnximjn minjjiba111 1 1 1 1 1 1 1 1111111111Amn行行111212122212nnmmmnx xxx xxxxx系數(shù)矩陣有系數(shù)矩陣有mn 列（變量）；列（變量）；m + n 行（約束方程）；行（約束方程）；但由于前但由于前m行之和等于后行之和等于后n行之和（平衡條件），故有行之和（平衡條件），故有m

7、+ n-1 行線性無關(guān)行線性無關(guān)m個(gè)產(chǎn)地、個(gè)產(chǎn)地、n個(gè)銷地產(chǎn)銷平衡運(yùn)輸問題特征：個(gè)銷地產(chǎn)銷平衡運(yùn)輸問題特征：一定有可行解，且有最優(yōu)解；一定有可行解，且有最優(yōu)解；當(dāng)產(chǎn)量與銷量均為整數(shù)時(shí)，一定有整數(shù)最優(yōu)解；當(dāng)產(chǎn)量與銷量均為整數(shù)時(shí)，一定有整數(shù)最優(yōu)解；有有m+n-1個(gè)基變量個(gè)基變量閉回路閉回路的定義：的定義： 一個(gè)閉回路是運(yùn)輸表中的一個(gè)變量序列，序列中任一個(gè)閉回路是運(yùn)輸表中的一個(gè)變量序列，序列中任何兩個(gè)相鄰變量處于同一行或者同一列，而任何三個(gè)何兩個(gè)相鄰變量處于同一行或者同一列，而任何三個(gè)相鄰的變量不會(huì)處于同一行或同一列；序列中的最后相鄰的變量不會(huì)處于同一行或同一列；序列中的最后一個(gè)變量與第一個(gè)變量位于

8、運(yùn)輸表的同一行或同一列。一個(gè)變量與第一個(gè)變量位于運(yùn)輸表的同一行或同一列。將序列中相鄰的兩個(gè)變量依次相連，并將最后一個(gè)變將序列中相鄰的兩個(gè)變量依次相連，并將最后一個(gè)變量與第一個(gè)變量相連，可形成一個(gè)閉合的回路，稱為量與第一個(gè)變量相連，可形成一個(gè)閉合的回路，稱為，序列中的變量稱為，序列中的變量稱為閉回路的頂點(diǎn)閉回路的頂點(diǎn)，相鄰兩個(gè)，相鄰兩個(gè)變量的連線稱為變量的連線稱為閉回路的邊閉回路的邊。設(shè)設(shè)m =4，n =5，則序列，則序列 形成形成41432321,xxxxx21x23x41x43圖圖3-1 閉回路示意圖（閉回路示意圖（a）x13x34x11x31x44x43設(shè)設(shè)m =4，n =5，則變量序列，

9、則變量序列 形成形成313444431311,xxxxxx圖圖3-1 閉回路示意圖（閉回路示意圖（b） 運(yùn)輸問題的運(yùn)輸問題的m + n - -1個(gè)變量構(gòu)成基變量的充要個(gè)變量構(gòu)成基變量的充要條件是它不包含任何閉回路。即所有頂點(diǎn)都是基變量的條件是它不包含任何閉回路。即所有頂點(diǎn)都是基變量的閉回路不存在。閉回路不存在。 如果以某一個(gè)非基變量為起點(diǎn)（第一個(gè)頂點(diǎn)），而如果以某一個(gè)非基變量為起點(diǎn)（第一個(gè)頂點(diǎn)），而其它頂點(diǎn)都是基變量，則一定能找到唯一一條閉回路。其它頂點(diǎn)都是基變量，則一定能找到唯一一條閉回路。表上作業(yè)法基本步驟類似于單純形法：表上作業(yè)法基本步驟類似于單純形法：1 1編制初始調(diào)運(yùn)方案（即確定初始

10、基本可行解）編制初始調(diào)運(yùn)方案（即確定初始基本可行解） 常用的方法有西北角法、常用的方法有西北角法、最小元素法最小元素法及及VogelVogel法。法。 2 2最優(yōu)性檢驗(yàn)（求出相應(yīng)的檢驗(yàn)數(shù)并檢驗(yàn)）最優(yōu)性檢驗(yàn)（求出相應(yīng)的檢驗(yàn)數(shù)并檢驗(yàn)） 常用方法有閉回路法和常用方法有閉回路法和位勢(shì)法位勢(shì)法。3 3解的改進(jìn)解的改進(jìn) 根據(jù)檢驗(yàn)數(shù)確定方案是否最優(yōu)，是則終止，否則采根據(jù)檢驗(yàn)數(shù)確定方案是否最優(yōu)，是則終止，否則采用用閉回路法閉回路法調(diào)整；再返回到第調(diào)整；再返回到第2 2步，直至最優(yōu)。步，直至最優(yōu)。1 1編制初始調(diào)運(yùn)方案編制初始調(diào)運(yùn)方案最小元素法最小元素法A1A2A3B1B2B3B4銷量銷量產(chǎn)量產(chǎn)量9573846

11、9222107584143302403204305405500這個(gè)初始方案的總運(yùn)費(fèi)是這個(gè)初始方案的總運(yùn)費(fèi)是5 59+49+47+37+31+21+22+32+34+44+42 =1002 =100（百元）（百元）其基變量個(gè)數(shù)應(yīng)為其基變量個(gè)數(shù)應(yīng)為4+3-1=64+3-1=6（個(gè)）（個(gè)）得到初始方案后，應(yīng)檢查最終數(shù)字格得到初始方案后，應(yīng)檢查最終數(shù)字格的個(gè)數(shù)是否恰好為的個(gè)數(shù)是否恰好為m+n- -1，如果數(shù)字格的個(gè)，如果數(shù)字格的個(gè)數(shù)不行于數(shù)不行于m+n- -1 ，則后面的計(jì)算無法進(jìn)行。，則后面的計(jì)算無法進(jìn)行。A1A2A3B1B2B3B4銷量銷量產(chǎn)量產(chǎn)量95738469222107584143出現(xiàn)退化的

12、情況：出現(xiàn)退化的情況：30004052.2.最優(yōu)性檢驗(yàn)最優(yōu)性檢驗(yàn)位勢(shì)法位勢(shì)法又稱又稱U-V法。產(chǎn)銷平衡運(yùn)輸問題的對(duì)偶問題為：法。產(chǎn)銷平衡運(yùn)輸問題的對(duì)偶問題為：11maxs.t.(1,;1, )mniiijijijijYaub vuvcim jn對(duì)偶問題對(duì)偶問題原問題原問題變量變量ui供應(yīng)約束方程供應(yīng)約束方程變量變量vj需求約束方程需求約束方程m個(gè)個(gè)n個(gè)個(gè)行位勢(shì)行位勢(shì)列位勢(shì)列位勢(shì)xij檢驗(yàn)數(shù)計(jì)算公式：檢驗(yàn)數(shù)計(jì)算公式：njmivucjiijij, 2 , 1;, 2 , 1)(（3-1） 對(duì)于基變量對(duì)于基變量xij，則有，則有 ，于是：，于是：0ijnjmicvuijji, 2 , 1;, 2 ,

13、 1（3-2） 令令u1= 0，由（，由（3-2）確定其他的）確定其他的ui，vj ；再利用再利用（3-1）計(jì)算其它非基變量（空格）的檢驗(yàn)數(shù)：計(jì)算其它非基變量（空格）的檢驗(yàn)數(shù)：A1A2A3B1B2B3B4列位勢(shì)列位勢(shì)行位勢(shì)行位勢(shì)9222107584143u1=0342345v2 =9v4 =7u3=-5u2=-5v3 =7v1 =6（-4）（3）（-1）（7）（3）（2）初始基可行解不是最優(yōu)解，需進(jìn)行基可行解的改進(jìn)初始基可行解不是最優(yōu)解，需進(jìn)行基可行解的改進(jìn)3 3解的改進(jìn)解的改進(jìn)閉回路法閉回路法 對(duì)運(yùn)輸方案進(jìn)行調(diào)整，從絕對(duì)值最大的負(fù)檢驗(yàn)數(shù)對(duì)對(duì)運(yùn)輸方案進(jìn)行調(diào)整，從絕對(duì)值最大的負(fù)檢驗(yàn)數(shù)對(duì)應(yīng)的空格（

14、進(jìn)基變量）出發(fā)，構(gòu)造一條其它頂點(diǎn)均為數(shù)應(yīng)的空格（進(jìn)基變量）出發(fā)，構(gòu)造一條其它頂點(diǎn)均為數(shù)字格的閉回路，在保持產(chǎn)銷平衡的前提下，使進(jìn)基變量字格的閉回路，在保持產(chǎn)銷平衡的前提下，使進(jìn)基變量取值盡可能大，同時(shí)調(diào)整閉回路上其它頂點(diǎn)（基變量）取值盡可能大，同時(shí)調(diào)整閉回路上其它頂點(diǎn)（基變量）的值，以實(shí)現(xiàn)解的改進(jìn)的值，以實(shí)現(xiàn)解的改進(jìn) 。 閉回路法閉回路法： 找出從進(jìn)基變量出發(fā)的唯一一條閉回路，從出發(fā)點(diǎn)找出從進(jìn)基變量出發(fā)的唯一一條閉回路，從出發(fā)點(diǎn)開始，沿閉回路各頂點(diǎn)依次交替標(biāo)開始，沿閉回路各頂點(diǎn)依次交替標(biāo)“+”+”、“-”-”號(hào)；號(hào)； 所有被標(biāo)所有被標(biāo)“-”-”號(hào)格子中基變量號(hào)格子中基變量xij 取值最小者作為

15、出取值最小者作為出基變量，其值作為調(diào)整量基變量，其值作為調(diào)整量 ： -min的取值號(hào)的閉回路頂點(diǎn)上所有標(biāo)ijx閉回路法閉回路法： 對(duì)于閉回路各頂點(diǎn)，將所有帶對(duì)于閉回路各頂點(diǎn)，將所有帶“+”+”號(hào)格子在原取號(hào)格子在原取值上加值上加，帶，帶“-”-”號(hào)的格子原取值上減號(hào)的格子原取值上減；出基變；出基變量取值由量取值由變?yōu)樽優(yōu)? 0，就得到一個(gè)新的調(diào)運(yùn)方案。（不，就得到一個(gè)新的調(diào)運(yùn)方案。（不是閉回路頂點(diǎn)的基變量取值不變）。重新求檢驗(yàn)數(shù)并是閉回路頂點(diǎn)的基變量取值不變）。重新求檢驗(yàn)數(shù)并重復(fù)上述步驟，直至最優(yōu)。重復(fù)上述步驟，直至最優(yōu)。 A1A2A3B1B2B3B4列位勢(shì)列位勢(shì)行位勢(shì)行位勢(shì)922210758

16、4143342345（-4）+ +- -+ +- -343,min進(jìn)基變量進(jìn)基變量x11= = =3， x14= =4- -= =1x24= =2+ += =5x21= =3- -= =0出基變量出基變量A1A2A3B1B2B3B4列位勢(shì)列位勢(shì)行位勢(shì)行位勢(shì)9222107584143345315u1=0v2 =9v4 =7u3=-5u2=-5v3 =7v1 =2（3）（-1）（11）（3）（2）（4）+ +- -+ +- -A1A2A3B1B2B3B4列位勢(shì)列位勢(shì)行位勢(shì)行位勢(shì)9222107584143340365u1=0v2 =8v4 =7u3=-4u2=-5v3 =6v1 =2（4）（10）（

17、2）（3）（4）（1）調(diào)整后得到最優(yōu)解；調(diào)整后得到最優(yōu)解；最小總運(yùn)費(fèi)：最小總運(yùn)費(fèi)：11142232333,6,5,3,4,xxxxx3 32+62+67+57+53+33+34+44+42 =832 =83（百元）。（百元）。 某制藥公司在全國(guó)設(shè)有某制藥公司在全國(guó)設(shè)有4個(gè)藥廠，其中某種藥品個(gè)藥廠，其中某種藥品的日產(chǎn)量為：藥廠的日產(chǎn)量為：藥廠A1 600箱，藥廠箱，藥廠A2 400箱，藥廠箱，藥廠A3 300箱，藥廠箱，藥廠A4 500箱。這些藥廠每天將這些藥分別運(yùn)箱。這些藥廠每天將這些藥分別運(yùn)往往4個(gè)地區(qū)的經(jīng)銷部門，各經(jīng)銷部門每天的需求量為：個(gè)地區(qū)的經(jīng)銷部門，各經(jīng)銷部門每天的需求量為：B1在在

18、200到到600箱之間，箱之間，B2為在為在500到到700箱之間，箱之間， B3和和B4分別為分別為350箱和箱和450箱。從各藥廠到各經(jīng)銷部門每箱箱。從各藥廠到各經(jīng)銷部門每箱藥品的單位運(yùn)價(jià)如表藥品的單位運(yùn)價(jià)如表3-13所示，問該制藥公司應(yīng)如何所示，問該制藥公司應(yīng)如何調(diào)運(yùn)，使在滿足銷售的同時(shí)總運(yùn)費(fèi)最少？調(diào)運(yùn)，使在滿足銷售的同時(shí)總運(yùn)費(fèi)最少？ （單位：元（單位：元/箱）箱）藥廠藥廠經(jīng)經(jīng) 銷銷 部部 門門B1B2B3B4A1A2A3A45103494682741038211不滿足不滿足 稱為不平衡型運(yùn)輸問題；有稱為不平衡型運(yùn)輸問題；有11mnijijabnjjmiiba11njjmiiba11以以

19、“供大于銷供大于銷”為例，為例，“供大于銷供大于銷”“供小于銷供小于銷”1111Min,1,2,s.t.,1,2,0(1,2,;1,2, )mnijijijnijijmijjiijZc xxa imxbjnxim jn 其模型為：其模型為：在模型的產(chǎn)量限制約束（前在模型的產(chǎn)量限制約束（前m個(gè)不等式）中引入個(gè)不等式）中引入m個(gè)個(gè)松弛變量松弛變量xi n+1 i = 1, 2, , m，使約束變?yōu)榈仁剑?，使約束變?yōu)榈仁剑?1(1,2,)niji nijxxaim 增加虛擬銷地增加虛擬銷地Bn+1，Bn+1的需求量為總供給與總需求的差，的需求量為總供給與總需求的差，即即 ； 顯然，顯然，111mnn

20、ijijbabmininbx11110(1, 2,)i ncim 松弛變量松弛變量 x i n+1可以視為從產(chǎn)地可以視為從產(chǎn)地 A i 運(yùn)往銷地運(yùn)往銷地B n+1 的運(yùn)輸量，由于實(shí)際并不運(yùn)送，它們的運(yùn)費(fèi)為的運(yùn)輸量，由于實(shí)際并不運(yùn)送，它們的運(yùn)費(fèi)為 對(duì)于對(duì)于“供小于銷供小于銷”問題可采用類似處理方式，即問題可采用類似處理方式，即增加虛擬產(chǎn)地增加虛擬產(chǎn)地。這個(gè)運(yùn)輸問題就轉(zhuǎn)化成了一個(gè)這個(gè)運(yùn)輸問題就轉(zhuǎn)化成了一個(gè)產(chǎn)銷平衡的問題產(chǎn)銷平衡的問題。 各藥廠該藥品的總產(chǎn)量為各藥廠該藥品的總產(chǎn)量為1800箱；箱； 4個(gè)經(jīng)銷部總的最低需求量為個(gè)經(jīng)銷部總的最低需求量為1500箱，這時(shí)屬于箱，這時(shí)屬于“供大于銷供大于銷”

21、，需要增加虛擬銷地以保持平衡；，需要增加虛擬銷地以保持平衡； 總的總的最高需求量是最高需求量是2100箱，這時(shí)屬于箱，這時(shí)屬于“供小于銷供小于銷”，需要增加虛擬產(chǎn)地以保持平衡；需要增加虛擬產(chǎn)地以保持平衡； 各經(jīng)銷部最低需求部分不能由虛擬產(chǎn)地供應(yīng)。各經(jīng)銷部最低需求部分不能由虛擬產(chǎn)地供應(yīng)。 經(jīng)銷部經(jīng)銷部藥廠藥廠B11B12B21B22B3B4供應(yīng)量供應(yīng)量A1559923600 x11x12x13x14x15x16A210104478400 x21x22x23x24x25x26A3336642300 x31x32x33x34x35x36A444881011500 x41x42x43x44x45x46

22、A5M0M0MM300 x51x52x53x54x55x56需求量需求量200400500200350450 人們探討某些線性規(guī)劃問題，有時(shí)必人們探討某些線性規(guī)劃問題，有時(shí)必須把全部或部分決策變量限制為非負(fù)整數(shù)須把全部或部分決策變量限制為非負(fù)整數(shù)（人數(shù)、車輛數(shù)、醫(yī)療器械臺(tái)數(shù)等）。這樣（人數(shù)、車輛數(shù)、醫(yī)療器械臺(tái)數(shù)等）。這樣的線性規(guī)劃問題，通常稱為整數(shù)規(guī)劃。作為的線性規(guī)劃問題，通常稱為整數(shù)規(guī)劃。作為線性規(guī)劃的特殊情況，整數(shù)規(guī)劃也有最小化線性規(guī)劃的特殊情況，整數(shù)規(guī)劃也有最小化和最大化之別。和最大化之別。 整數(shù)規(guī)劃還可以分成整數(shù)規(guī)劃還可以分成純整數(shù)規(guī)劃純整數(shù)規(guī)劃和和混整數(shù)規(guī)混整數(shù)規(guī)劃劃。二者的區(qū)別在于

23、：前者的決策變量必定。二者的區(qū)別在于：前者的決策變量必定。而后者的決策變量。而后者的決策變量。整整數(shù)規(guī)劃解法有分支定界法和割平面法數(shù)規(guī)劃解法有分支定界法和割平面法 在純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃中，常會(huì)有一在純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃中，常會(huì)有一些變量取值只能為些變量取值只能為0或或1（稱為（稱為0-1變量），如果變量），如果模型中所有變量都是模型中所有變量都是0-1變量，則稱之為變量，則稱之為0-1規(guī)劃規(guī)劃 某集團(tuán)公司正在考慮企業(yè)擴(kuò)張計(jì)劃某集團(tuán)公司正在考慮企業(yè)擴(kuò)張計(jì)劃, ,并準(zhǔn)備從幾并準(zhǔn)備從幾個(gè)備選方案中選擇一個(gè)或若干個(gè)付諸實(shí)施。備選方案包個(gè)備選方案中選擇一個(gè)或若干個(gè)付諸實(shí)施。備選方案包括：收購(gòu)一

24、個(gè)醫(yī)藥行業(yè)上市公司進(jìn)入醫(yī)藥領(lǐng)域；進(jìn)軍服括：收購(gòu)一個(gè)醫(yī)藥行業(yè)上市公司進(jìn)入醫(yī)藥領(lǐng)域；進(jìn)軍服裝及配飾生產(chǎn)、銷售行業(yè)；向裝及配飾生產(chǎn)、銷售行業(yè)；向ITIT行業(yè)擴(kuò)張；進(jìn)入旅游行行業(yè)擴(kuò)張；進(jìn)入旅游行業(yè)；進(jìn)入食品及飲料行業(yè)。由于各行業(yè)不同特點(diǎn)及多種業(yè)；進(jìn)入食品及飲料行業(yè)。由于各行業(yè)不同特點(diǎn)及多種因素的限制，進(jìn)入不同行業(yè)的投資周期有所不同，一般因素的限制，進(jìn)入不同行業(yè)的投資周期有所不同，一般需要需要3-53-5年時(shí)間。投資不同行業(yè)的每年所需投資額和年時(shí)間。投資不同行業(yè)的每年所需投資額和1010年年后各行業(yè)的凈收益現(xiàn)值如下表所示：后各行業(yè)的凈收益現(xiàn)值如下表所示：表表 3 3- -1 15 5 某集團(tuán)未來戰(zhàn)略發(fā)展

25、某集團(tuán)未來戰(zhàn)略發(fā)展計(jì)劃計(jì)劃投資與收益預(yù)算投資與收益預(yù)算 預(yù)計(jì)預(yù)計(jì)每年每年投資額投資額（百萬元）（百萬元） 備選方案?jìng)溥x方案 預(yù)計(jì)預(yù)計(jì) 1010 年后年后凈收益凈收益現(xiàn)值（百萬元）現(xiàn)值（百萬元） 1 2 3 4 5 1醫(yī)藥醫(yī)藥 140 120 60 40 - - - - 2服裝服裝 120 60 80 30 30 - - 3ITIT 160 30 60 60 50 50 4旅游旅游 80 50 50 30 30 30 5食品食品 100 40 60 40 40 20 每年可用資金（百萬元）每年可用資金（百萬元） 200 200 150 120 100 如果僅從收益角度考慮投資計(jì)劃，則該集團(tuán)應(yīng)選擇

26、哪些行如果僅從收益角度考慮投資計(jì)劃，則該集團(tuán)應(yīng)選擇哪些行業(yè)投資？業(yè)投資？5 , 4 , 3 , 2 , 10, 1jjjxj個(gè)方案不投資第個(gè)方案投資第Z為為10年后總的凈收益現(xiàn)值，該問題的數(shù)學(xué)模型為年后總的凈收益現(xiàn)值，該問題的數(shù)學(xué)模型為12345Max14012016080100Zxxxxx10100203050120403050301504030603040200605060806020040503060120. .5435432543215432154321或jxxxxxxxxxxxxxxxxxxxxxxxts0-1規(guī)劃的標(biāo)準(zhǔn)型規(guī)劃的標(biāo)準(zhǔn)型11Max(1, 2,)s.t.0,1.(1, 2

27、, )njjjnijjijjYc xa xbimxjn對(duì)于對(duì)于0-1規(guī)劃的求解可采用隱枚舉法規(guī)劃的求解可采用隱枚舉法進(jìn)一步考慮如下問題進(jìn)一步考慮如下問題: :集團(tuán)在綜合考慮多種因素的情況下，集團(tuán)在綜合考慮多種因素的情況下，決定不能同時(shí)對(duì)服裝行業(yè)與食品行業(yè)進(jìn)行投資，并且如決定不能同時(shí)對(duì)服裝行業(yè)與食品行業(yè)進(jìn)行投資，并且如果決定投資旅游行業(yè)，則必須首先進(jìn)入果決定投資旅游行業(yè)，則必須首先進(jìn)入ITIT行業(yè)。行業(yè)。 0-1變量可以很方便地將諸如選擇與放棄、開與關(guān)、變量可以很方便地將諸如選擇與放棄、開與關(guān)、有與無、是與否等二選一決策轉(zhuǎn)化為數(shù)量關(guān)系有與無、是與否等二選一決策轉(zhuǎn)化為數(shù)量關(guān)系 如何在模型中表示從方

28、案如何在模型中表示從方案2 2和方案和方案5 5中最多中最多選擇一個(gè)進(jìn)行投資，以及若不選方案選擇一個(gè)進(jìn)行投資，以及若不選方案3 3，也不，也不能選方案能選方案4 4？1.從方案從方案2和和5中最多選一個(gè)投資，即二者互斥中最多選一個(gè)投資，即二者互斥20212未投資方案投資方案x50515未投資方案投資方案x 方案方案2和和5不能同時(shí)選擇，即不能同時(shí)選擇，即x2和和x5不能同時(shí)取不能同時(shí)取1，可用不等式可用不等式 表示，在模型中增加該約束表示，在模型中增加該約束152 xx 一般地，表示從一般地，表示從n個(gè)決策方案中選一個(gè)個(gè)決策方案中選一個(gè)(最多選一最多選一個(gè)個(gè))，可通過在模型中相應(yīng)增加如下線性約

29、束實(shí)現(xiàn)：，可通過在模型中相應(yīng)增加如下線性約束實(shí)現(xiàn)：11njjx11njjx2.方案方案4的選擇以方案的選擇以方案3的選擇為前提，即相依決策的選擇為前提，即相依決策 投資了方案投資了方案3才能進(jìn)一步?jīng)Q定是否投資方案才能進(jìn)一步?jīng)Q定是否投資方案4；否；否則，未投資方案則，未投資方案3也一定不會(huì)投資方案也一定不會(huì)投資方案4?？赏ㄟ^在模。可通過在模型中增加約束型中增加約束 實(shí)現(xiàn)實(shí)現(xiàn))0(4334xxxx 一般地，決策一般地，決策i以決策以決策j為前提時(shí)，可表示為為前提時(shí)，可表示為決策決策i與決策與決策j完全一致時(shí)，可表示為完全一致時(shí)，可表示為jixx jixx 考慮了以上兩種情況后，原模型變?yōu)槿缦滦问剑?/p>

30、考慮了以上兩種情況后，原模型變?yōu)槿缦滦问剑?234512345123451234523453452534Max14012016080100120603050402006080605060200403060304015030503040120.5030201001001jZxxxxxxxxxxxxxxxxxxxxxxxxs txxxxxxxx 或或 某藥品廠新近開發(fā)了兩種新藥某藥品廠新近開發(fā)了兩種新藥A和和B。藥廠現(xiàn)有三。藥廠現(xiàn)有三個(gè)車間個(gè)車間1、2和和3，可供生產(chǎn)兩種新藥的生產(chǎn)能力分別為每，可供生產(chǎn)兩種新藥的生產(chǎn)能力分別為每周周4、12和和18小時(shí)。生產(chǎn)每件藥品小時(shí)。生產(chǎn)每件藥品A需要車間需要

31、車間1生產(chǎn)能力生產(chǎn)能力1小時(shí)和車間小時(shí)和車間3生產(chǎn)能力生產(chǎn)能力3小時(shí)；生產(chǎn)每件藥品小時(shí)；生產(chǎn)每件藥品B需要車間需要車間2和車間和車間3生產(chǎn)能力各生產(chǎn)能力各2小時(shí)。預(yù)計(jì)藥品小時(shí)。預(yù)計(jì)藥品A、B的單位利潤(rùn)分的單位利潤(rùn)分別為別為300元元/件和件和500元元/件，工廠每周生產(chǎn)一批藥品，對(duì)于件，工廠每周生產(chǎn)一批藥品，對(duì)于每一種藥品，如果在開始生產(chǎn)前要為安裝設(shè)備支出一次每一種藥品，如果在開始生產(chǎn)前要為安裝設(shè)備支出一次性的準(zhǔn)備成本，分別為性的準(zhǔn)備成本，分別為700元和元和1300元，應(yīng)如何安排一周元，應(yīng)如何安排一周的生產(chǎn)使新藥品獲利最大？的生產(chǎn)使新藥品獲利最大？ 是否可以直接將藥品生產(chǎn)的準(zhǔn)備成本直接從是否

32、可以直接將藥品生產(chǎn)的準(zhǔn)備成本直接從新藥的總利潤(rùn)中減掉？新藥的總利潤(rùn)中減掉？ 設(shè)藥品設(shè)藥品A、B每周的產(chǎn)量分別為每周的產(chǎn)量分別為x1和和x2，顯然它們，顯然它們應(yīng)為非負(fù)整數(shù)，應(yīng)為非負(fù)整數(shù)，Z為兩種新藥的總利潤(rùn)為兩種新藥的總利潤(rùn) 若某種藥品最終并未生產(chǎn)，則不需要花費(fèi)準(zhǔn)備費(fèi)若某種藥品最終并未生產(chǎn)，則不需要花費(fèi)準(zhǔn)備費(fèi)用，故直接減掉其準(zhǔn)備成本是錯(cuò)誤的，可引入如下邏用，故直接減掉其準(zhǔn)備成本是錯(cuò)誤的，可引入如下邏輯變量：輯變量：2 , 10, 1jjjyj的生產(chǎn)進(jìn)行準(zhǔn)備未對(duì)藥品的生產(chǎn)進(jìn)行了準(zhǔn)備對(duì)藥品目標(biāo)函數(shù)寫成：目標(biāo)函數(shù)寫成：1212Max3005007001300Zxxyy 表示僅當(dāng)準(zhǔn)備費(fèi)用實(shí)際發(fā)生時(shí)，才

33、從總利潤(rùn)中扣除；表示僅當(dāng)準(zhǔn)備費(fèi)用實(shí)際發(fā)生時(shí)，才從總利潤(rùn)中扣除；邏輯變量與實(shí)際產(chǎn)量的關(guān)系可用如下約束表示：邏輯變量與實(shí)際產(chǎn)量的關(guān)系可用如下約束表示：2 , 1jMyxjj 其中其中M為任意大的正數(shù)，上式表示僅當(dāng)相應(yīng)準(zhǔn)備為任意大的正數(shù)，上式表示僅當(dāng)相應(yīng)準(zhǔn)備（費(fèi)用）發(fā)生時(shí)才允許生產(chǎn)新藥（產(chǎn)量大于零）（費(fèi)用）發(fā)生時(shí)才允許生產(chǎn)新藥（產(chǎn)量大于零）該問題建立的模型如下：該問題建立的模型如下：1212121211221212Max300500700130042123218.(),01,0,ZxxyyxxxxxMys txMyMyyxx 為為任任意意大大正正數(shù)數(shù)或或且且均均為為整整數(shù)數(shù)（2）假如兩種藥品可相互替

34、代，因此管理層決定不同時(shí)）假如兩種藥品可相互替代，因此管理層決定不同時(shí)生產(chǎn)兩種藥品，即最多只選擇利潤(rùn)最大的一種生產(chǎn)，應(yīng)生產(chǎn)兩種藥品，即最多只選擇利潤(rùn)最大的一種生產(chǎn)，應(yīng)如何考慮？（如何考慮？（3）工廠最近又新建了一個(gè)車間）工廠最近又新建了一個(gè)車間4，可替代，可替代車間車間3對(duì)兩種藥品進(jìn)行加工，生產(chǎn)每件藥品對(duì)兩種藥品進(jìn)行加工，生產(chǎn)每件藥品A和藥品和藥品B需需要車間要車間4的生產(chǎn)能力分別為的生產(chǎn)能力分別為2小時(shí)和小時(shí)和4小時(shí)，車間小時(shí)，車間4的可用的可用能力為能力為28小時(shí)。但是，為了方便管理，管理層決定只選小時(shí)。但是，為了方便管理，管理層決定只選擇車間擇車間3和車間和車間4其中之一生產(chǎn)新藥品，但要

35、選取能獲得其中之一生產(chǎn)新藥品，但要選取能獲得產(chǎn)品組合最大利潤(rùn)的那一車間生產(chǎn)，應(yīng)如何考慮？產(chǎn)品組合最大利潤(rùn)的那一車間生產(chǎn)，應(yīng)如何考慮？2 , 10,0,0, 1jxjxjyjjj即不允許不能生產(chǎn)藥品即允許可以生產(chǎn)藥品問題（問題（2）：）：要求要求x1或或x2至少一個(gè)為至少一個(gè)為0； 如果如果x1和和x2均為均為0-1變量，可以用變量，可以用x1+x21，來表示，來表示上述約束；上述約束； 本例中決策變量本例中決策變量x1和和x2非非0-1變量，故不能直接用變量，故不能直接用x1+x21表示，需要對(duì)每個(gè)決策變量引入邏輯變量表示，需要對(duì)每個(gè)決策變量引入邏輯變量邏輯變量用于控制決策變量是否取邏輯變量用

36、于控制決策變量是否取0，問題模型為：，問題模型為：121212121122121212Max300500700130042123218.()1,01,0,ZxxyyxxxxxMys txMyMyyyyxx 為為任任意意大大正正數(shù)數(shù)或或且且均均為為整整數(shù)數(shù)問題（問題（3）：為討論方便暫不考慮存在固定費(fèi)用和產(chǎn)）：為討論方便暫不考慮存在固定費(fèi)用和產(chǎn)品競(jìng)爭(zhēng)的情況，按問題要求模型可寫成：品競(jìng)爭(zhēng)的情況，按問題要求模型可寫成：1212121212Max3005004212.32182428,0,Zxxxxs txxxxxx 或或且且均均為為整整數(shù)數(shù) 模型中第三個(gè)約束條件顯然不符合線性規(guī)劃或整數(shù)模型中第三個(gè)約

37、束條件顯然不符合線性規(guī)劃或整數(shù)規(guī)劃的要求。因此，考慮引入規(guī)劃的要求。因此，考慮引入0-1邏輯變量邏輯變量生產(chǎn)選擇車間生產(chǎn)選擇車間3041y將模型第三個(gè)約束替換為：將模型第三個(gè)約束替換為：)2()1 (2842) 1 (18232121yMxxMyxx也可以同時(shí)引入兩個(gè)也可以同時(shí)引入兩個(gè)0-1邏輯變量邏輯變量y1、y2：12842182321221121yyMyxxMyxx1212121212Max30050042123218.2428(1)01,0,ZxxxxxxMys txxMyyMxx 或或?yàn)闉槿稳我庖獯蟠笳龜?shù)數(shù)且且均均為為整整數(shù)數(shù)本問題最終模型為：本問題最終模型為： 有有n項(xiàng)不同的任務(wù)

38、，需要項(xiàng)不同的任務(wù)，需要n個(gè)人分別完成其中的一個(gè)人分別完成其中的一項(xiàng)，但由于任務(wù)的性質(zhì)和各人的專長(zhǎng)不同，因此各人項(xiàng)，但由于任務(wù)的性質(zhì)和各人的專長(zhǎng)不同，因此各人去完成不同任務(wù)的效率（或花費(fèi)的時(shí)間、費(fèi)用）也有去完成不同任務(wù)的效率（或花費(fèi)的時(shí)間、費(fèi)用）也有所不同，假設(shè)第所不同，假設(shè)第 i 個(gè)人完成個(gè)人完成 j 項(xiàng)任務(wù)的效率為項(xiàng)任務(wù)的效率為cij。于。于是產(chǎn)生了一個(gè)問題，應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù)，是產(chǎn)生了一個(gè)問題，應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù)，使完成使完成n項(xiàng)任務(wù)的總效率最高（或所需時(shí)間、費(fèi)用最項(xiàng)任務(wù)的總效率最高（或所需時(shí)間、費(fèi)用最少），這類問題就是指派問題。少），這類問題就是指派問題。標(biāo)準(zhǔn)的指派問題

39、需要滿足以下假設(shè)：標(biāo)準(zhǔn)的指派問題需要滿足以下假設(shè)： 被指派者的數(shù)量與任務(wù)的數(shù)量相同；被指派者的數(shù)量與任務(wù)的數(shù)量相同； 每一項(xiàng)任務(wù)只能由一個(gè)人來完成；每一項(xiàng)任務(wù)只能由一個(gè)人來完成； 每一個(gè)指派者只能完成一項(xiàng)任務(wù)；每一個(gè)指派者只能完成一項(xiàng)任務(wù)； 每一個(gè)指派者和每一項(xiàng)任務(wù)的組合都會(huì)有每一個(gè)指派者和每一項(xiàng)任務(wù)的組合都會(huì)有一個(gè)相關(guān)的成本（收益）；一個(gè)相關(guān)的成本（收益）； 目標(biāo)是確定怎樣的指派能使總成本達(dá)最小目標(biāo)是確定怎樣的指派能使總成本達(dá)最小（或總效率最高）。（或總效率最高）。例例3-4 某醫(yī)院四名化驗(yàn)員（甲、乙、丙、丁）完成四項(xiàng)某醫(yī)院四名化驗(yàn)員（甲、乙、丙、丁）完成四項(xiàng)化驗(yàn)任務(wù)（化驗(yàn)任務(wù)（A、B、C、

40、D）所消耗時(shí)間見表）所消耗時(shí)間見表3-16。 問哪問哪個(gè)化驗(yàn)員承擔(dān)哪項(xiàng)化驗(yàn)任務(wù)，可使所需總時(shí)間最少？個(gè)化驗(yàn)員承擔(dān)哪項(xiàng)化驗(yàn)任務(wù)，可使所需總時(shí)間最少？化驗(yàn)員化驗(yàn)員完成任務(wù)所需時(shí)間完成任務(wù)所需時(shí)間 單位（分鐘）單位（分鐘）ABCD甲甲215134乙乙1041415丙丙9141613丁丁78119 這是一個(gè)標(biāo)準(zhǔn)指派問題，令這是一個(gè)標(biāo)準(zhǔn)指派問題，令i = =1、2、3、4分別表示分別表示化驗(yàn)員甲、乙、丙、丁，化驗(yàn)員甲、乙、丙、丁，j = =1、2、3、4分別表示分別表示A，B，C，D 4 4項(xiàng)任務(wù)，并定義項(xiàng)任務(wù)，并定義0-1變量變量xij：)4 , 3 , 2 , 1,(01jijijixij項(xiàng)任務(wù)名化

41、驗(yàn)員承擔(dān)第不安排第項(xiàng)任務(wù)名化驗(yàn)員承擔(dān)第安排第 用用Z表示表示完成全部任務(wù)的總時(shí)間，完成全部任務(wù)的總時(shí)間，則問題的數(shù)學(xué)則問題的數(shù)學(xué)模型為：模型為：44114141Min1 (1,2,3,4).1 (1,2,3,4)01 ( ,1,2,3,4)ijijijijjijiijZc xxis txjxi j 或或其中其中9118713161491514410413152)(ijc 由于目標(biāo)函數(shù)是求由于目標(biāo)函數(shù)是求Z的最小值，所以本問題也稱的最小值，所以本問題也稱為極小化指派問題為極小化指派問題一般地，標(biāo)準(zhǔn)的極小化指派問題的數(shù)學(xué)模型是：一般地，標(biāo)準(zhǔn)的極小化指派問題的數(shù)學(xué)模型是：1111Min1(1,2,

42、).1(1,2, )01 ( ,1,2, )nnijijijnijjnijiijZc xxins txjnxi jn 或或nnnnnnijccccccccccC212222111211)(其中其中稱為指派問題的稱為指派問題的 極小化指派問題可以看成是有極小化指派問題可以看成是有n個(gè)產(chǎn)個(gè)產(chǎn)地地n個(gè)銷地，各產(chǎn)地供應(yīng)量和各銷地需求個(gè)銷地，各產(chǎn)地供應(yīng)量和各銷地需求量均為量均為1，運(yùn)量為，運(yùn)量為0或或1的特殊運(yùn)輸問題。的特殊運(yùn)輸問題。 指派問題可行解可以指派問題可行解可以用一個(gè)用一個(gè)n階矩陣表示，如階矩陣表示，如例例3-4的一個(gè)可行解為：的一個(gè)可行解為：1000010000010010X 該矩陣代表的指

43、派方式為：該矩陣代表的指派方式為：甲甲B、乙、乙A、丙丙C、丁、丁D，對(duì)應(yīng)總時(shí)間為：，對(duì)應(yīng)總時(shí)間為：50分鐘分鐘 求解最小化指派問題：即找出效率矩陣求解最小化指派問題：即找出效率矩陣C中位于中位于不同行、不同列的不同行、不同列的n個(gè)元素，使其和最小。個(gè)元素，使其和最小。 若從指派問題效率矩陣若從指派問題效率矩陣 的每一行的每一行元素中分別減去元素中分別減去(或加上或加上)一個(gè)常數(shù)一個(gè)常數(shù)ui，從每一列，從每一列分別減去分別減去(或加上或加上)一個(gè)常數(shù)一個(gè)常數(shù)vj，得到一個(gè)新的效率矩陣，得到一個(gè)新的效率矩陣 ，其中其中 。則分別以。則分別以C和和B作為效率矩作為效率矩陣的兩個(gè)指派問題具有相同的最

44、優(yōu)解。陣的兩個(gè)指派問題具有相同的最優(yōu)解。0),(ijijccC)(ijbB 0,ijjiijijbvucb 若矩陣若矩陣C的元素可分為的元素可分為“0”與與“非非0”兩部分，兩部分，則覆蓋則覆蓋“0”元素的最少直線數(shù)等于位于不同行不同列的元素的最少直線數(shù)等于位于不同行不同列的“0”元素（稱為獨(dú)立元素（稱為獨(dú)立0元素）的最大個(gè)數(shù)。元素）的最大個(gè)數(shù)。第一步：第一步：從效率矩陣的每一行都減去該行的最小元素，從效率矩陣的每一行都減去該行的最小元素， 每一列減去該列的最小元素每一列減去該列的最小元素, ,得到每行每列都得到每行每列都 含含0 0元素的新矩陣元素的新矩陣只要找到新矩陣中位于不同行不同列只要

45、找到新矩陣中位于不同行不同列的的n個(gè)零元素，令對(duì)應(yīng)解矩陣相應(yīng)位置元素為個(gè)零元素，令對(duì)應(yīng)解矩陣相應(yīng)位置元素為1（其余（其余元素均為元素均為0），即找到了最優(yōu)解。），即找到了最優(yōu)解。)(ijbB 9118713161491514410413152)(ijc例例3-4-2-4-9-724104750111006211130-4 -200102350960607130例例3-400102350960607130第二步第二步 在最終得到的矩陣中尋找位于不同行、不同在最終得到的矩陣中尋找位于不同行、不同列的列的0 0元素，先從含元素，先從含0 0元素最少的行或列開始；直到所元素最少的行或列開始；直到所有的

46、有的“0”0”元素均被畫圈或劃掉為止。若矩陣中圈元素均被畫圈或劃掉為止。若矩陣中圈“0”0”的個(gè)數(shù)等于矩陣的階數(shù)，則對(duì)應(yīng)的指派方案最優(yōu)。的個(gè)數(shù)等于矩陣的階數(shù)，則對(duì)應(yīng)的指派方案最優(yōu)。00010100*10000010X 最最優(yōu)優(yōu)解解 該問題最優(yōu)指派為：該問題最優(yōu)指派為：甲甲D、乙、乙B、丙、丙A、丁丁C，對(duì)應(yīng)總時(shí)間為：，對(duì)應(yīng)總時(shí)間為：28分鐘分鐘36644433367257104)(ijc-4-2-3-3-10231100013501260第三步第三步 作最少的直線覆蓋作最少的直線覆蓋“0”元素元素： （1 1）無）無 的行打的行打，打，打行上行上 0 0 列打列打 ，打，打列列 上上 行打行打

47、 ，打，打行上行上 0 0 列打列打 00若矩陣中圈若矩陣中圈“0”0”的個(gè)數(shù)小于矩陣的階數(shù)的個(gè)數(shù)小于矩陣的階數(shù)n ，則需要，則需要轉(zhuǎn)入第三步。例如轉(zhuǎn)入第三步。例如第三步第三步 （2 2）對(duì)無）對(duì)無行及打行及打列畫線列畫線0231100013501260-1-1+10232100102400150-1-1-1+1+10122200201300040第四步第四步 直線未覆蓋的元素，找出最小值，未被直線覆直線未覆蓋的元素，找出最小值，未被直線覆 蓋的行減去這個(gè)最小值，被直線覆蓋的列加上這蓋的行減去這個(gè)最小值，被直線覆蓋的列加上這 個(gè)最小值，得到新的矩陣，返回第二步個(gè)最小值，得到新的矩陣，返回第二步

48、（一）極大化指派問題（一）極大化指派問題 指派問題若要求目標(biāo)函數(shù)取最大值，則稱為極大指派問題若要求目標(biāo)函數(shù)取最大值，則稱為極大化指派問題。極大化指派問題，需要轉(zhuǎn)化為極小化問化指派問題。極大化指派問題，需要轉(zhuǎn)化為極小化問題解決，并保證新的效率矩陣非負(fù)。題解決，并保證新的效率矩陣非負(fù)。找出效率矩陣找出效率矩陣(cij)中的最大元素中的最大元素 ，令令bij =M- -cij（稱（稱bij為為cij的縮減矩陣）；求解以的縮減矩陣）；求解以(bij)為效為效率矩陣的極小化指派問題。率矩陣的極小化指派問題。ijjicM,max 極大化指派問題效率矩陣為極大化指派問題效率矩陣為13791111141341

49、28711691715C第一步：第一步：首先找出效率矩陣首先找出效率矩陣C 中的最大元素中的最大元素17max,ijjicM第二步：第二步：計(jì)算其縮減矩陣計(jì)算其縮減矩陣41086634135910611802137911111413412871169171517171717171717171717171717171717)(ijbB第三步：第三步：求以求以B作為效率矩陣的極小化指派問題，其作為效率矩陣的極小化指派問題，其最優(yōu)解即原始極大化問題的最優(yōu)解。最優(yōu)解即原始極大化問題的最優(yōu)解。 醫(yī)用物資倉(cāng)庫的設(shè)立問題醫(yī)用物資倉(cāng)庫的設(shè)立問題 新興醫(yī)藥批發(fā)公司正考慮選擇四個(gè)城市：北京、新興醫(yī)藥批發(fā)公司正考慮

50、選擇四個(gè)城市：北京、上海、廣州和武漢設(shè)立倉(cāng)庫的計(jì)劃，當(dāng)然每個(gè)城市最多上海、廣州和武漢設(shè)立倉(cāng)庫的計(jì)劃，當(dāng)然每個(gè)城市最多只能建一個(gè)倉(cāng)庫。這些倉(cāng)庫建成后負(fù)責(zé)向華北、華中和只能建一個(gè)倉(cāng)庫。這些倉(cāng)庫建成后負(fù)責(zé)向華北、華中和華南三個(gè)地區(qū)發(fā)運(yùn)藥品和衛(wèi)生材料等醫(yī)用物資。在不同華南三個(gè)地區(qū)發(fā)運(yùn)藥品和衛(wèi)生材料等醫(yī)用物資。在不同城市設(shè)立倉(cāng)庫每月的運(yùn)營(yíng)成本及醫(yī)用物資的處理量會(huì)有城市設(shè)立倉(cāng)庫每月的運(yùn)營(yíng)成本及醫(yī)用物資的處理量會(huì)有所不同，由于與目的地距離不同，從不同城市的倉(cāng)庫向所不同，由于與目的地距離不同，從不同城市的倉(cāng)庫向不同地區(qū)發(fā)運(yùn)物資的運(yùn)輸成本也不相同。不同地區(qū)發(fā)運(yùn)物資的運(yùn)輸成本也不相同。表3-17 倉(cāng)庫發(fā)貨及運(yùn)營(yíng)相

51、關(guān)數(shù)據(jù) 單位：千元 華北地區(qū) 華中地區(qū) 華南地區(qū) 處理能力（件） 運(yùn)行成本 北京 0.20 0.40 0.50 1000 45 上海 0.30 0.25 0.45 1100 60 廣州 0.60 0.40 0.25 1300 70 武漢 0.30 0.15 0.35 900 40 需求量（件） 600 600 800 每個(gè)倉(cāng)庫向不同地區(qū)發(fā)運(yùn)物資的單位運(yùn)費(fèi)（千元每個(gè)倉(cāng)庫向不同地區(qū)發(fā)運(yùn)物資的單位運(yùn)費(fèi)（千元/ /噸）、噸）、每個(gè)倉(cāng)庫每月可處理的物資量及運(yùn)營(yíng)成本、各地區(qū)的月每個(gè)倉(cāng)庫每月可處理的物資量及運(yùn)營(yíng)成本、各地區(qū)的月平均需求見表平均需求見表3-173-17： 公司要求這些倉(cāng)庫建成后必須能保證各地醫(yī)

52、用公司要求這些倉(cāng)庫建成后必須能保證各地醫(yī)用物資的需求量，但又希望盡量控制總費(fèi)用，所以應(yīng)物資的需求量，但又希望盡量控制總費(fèi)用，所以應(yīng)選擇最為合適的地點(diǎn)進(jìn)行建設(shè)。此外，公司對(duì)倉(cāng)庫選擇最為合適的地點(diǎn)進(jìn)行建設(shè)。此外，公司對(duì)倉(cāng)庫設(shè)立的地理位置還有一些附帶的特殊要求，包括：設(shè)立的地理位置還有一些附帶的特殊要求，包括：如果在上海設(shè)立倉(cāng)庫，則必須先在武漢設(shè)立倉(cāng)庫；如果在上海設(shè)立倉(cāng)庫，則必須先在武漢設(shè)立倉(cāng)庫；武漢和廣州不能同時(shí)設(shè)立倉(cāng)庫；四個(gè)城市最多武漢和廣州不能同時(shí)設(shè)立倉(cāng)庫；四個(gè)城市最多設(shè)立兩個(gè)倉(cāng)庫。請(qǐng)協(xié)助該公司確定倉(cāng)庫的選址地點(diǎn)設(shè)立兩個(gè)倉(cāng)庫。請(qǐng)協(xié)助該公司確定倉(cāng)庫的選址地點(diǎn)并最佳發(fā)貨方案。并最佳發(fā)貨方案。4 , 3 , 2 , 101jiixi設(shè)立倉(cāng)庫未在城市設(shè)立倉(cāng)庫在城市設(shè)設(shè)1112132122233132334142431234Min0.20.40.50.30