第四章整數(shù)規(guī)劃與分配問(wèn)題

1、第四章整數(shù)規(guī)劃與分配問(wèn)題§ 4.1整數(shù)規(guī)劃的特點(diǎn)及作用用單純形法求解線(xiàn)性規(guī)劃的結(jié)果往往得到分?jǐn)?shù)或小數(shù)解。但在很多實(shí)際問(wèn)題中，全 部或部分變量的取值必須是整數(shù)，如人或者機(jī)器設(shè)備不可分割。此外還有一些問(wèn)題，如 要不要在某地建設(shè)工廠(chǎng)，可選用一個(gè)邏輯變量x,令x 1表示在該地建廠(chǎng)，x 0表示不在該地建廠(chǎng)，邏輯變量也只允許取整數(shù)值的一類(lèi)變量。在一個(gè)整數(shù)規(guī)劃中要求全部變 量取整數(shù)值的，稱(chēng)純整數(shù)線(xiàn)性規(guī)劃或純整數(shù)規(guī)劃；只要求一部分變量取整數(shù)值的，稱(chēng)為 混合整數(shù)(線(xiàn)性)規(guī)劃；在純整數(shù)規(guī)劃問(wèn)題中，若所有變量只允許取0, 1兩個(gè)值，則稱(chēng)其為0-1規(guī)劃。有人認(rèn)為，對(duì)整數(shù)規(guī)劃問(wèn)題的求解可以先不考慮對(duì)變量的整數(shù)

2、約束，作為一般線(xiàn)性 規(guī)劃問(wèn)題來(lái)求解，當(dāng)解為非整數(shù)時(shí)可用四舍五入或湊整數(shù)尋找最優(yōu)解，其實(shí)這種方法是 不可行的，原因有以下兩點(diǎn)：一、用湊整的方法計(jì)算量很大，而況還不一定能找到最優(yōu)解。如某線(xiàn)性規(guī)劃問(wèn)題的最優(yōu)解為X1 X24.6 5.5 ,用湊整數(shù)的方法時(shí)需比較與士2的上述數(shù)值最接近的四種組合：(4,5),(5,5),(4,6),(5,6)如果問(wèn)題中有10個(gè)變量，就 要比較210 1024個(gè)整數(shù)解組合，而且最優(yōu)解還不一定在這些組合中。二、放松約束也無(wú)法求出其最優(yōu)解maxz 3x1 2x2f2x1 3x2 14s.t K 0.5x2 4.5如果不考慮整數(shù)約束，稱(chēng)為上述線(xiàn)性規(guī)劃問(wèn)題的松弛問(wèn)題，松弛問(wèn)題的最

3、優(yōu)解為:x1取整以后Xi3,X22是可行解，但Xi解，而x13,x2 2 對(duì)應(yīng)的目標(biāo)函數(shù)值z(mì)3.25, x22.53,x2 3;x1 4, x2 2; x1 4, x2 3都不是可行3x1 2x2 13卻不是最優(yōu)解，然而最優(yōu)解是Xi 4,X2 i,maX z 3Xi 2X2 i4 。直接對(duì)松弛問(wèn)題進(jìn)行求解都無(wú)法求得整數(shù)規(guī)劃問(wèn)題的最優(yōu)解， 這就需要對(duì)整數(shù)線(xiàn)性規(guī)劃問(wèn)題有特殊的求解方法。此外，整數(shù)線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型的研究有著重要的意義，很多管理問(wèn)題無(wú)法歸納為線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型，但卻可以設(shè)置邏輯變量建立起整數(shù)規(guī)劃問(wèn)題的數(shù)學(xué)模型。下面舉例說(shuō)明邏輯變量在解決問(wèn)題中的重要作用。1.m個(gè)約束條件中只有

4、k個(gè)起作用設(shè)m個(gè)約束條件可以表示為naijXjbi,(ii, 2,L , m)ji定義 yi假設(shè)第i個(gè)約束條件不起作用.假設(shè)第i個(gè)約束條件起作用'i 1,2,L ,m)又 M 為任意大的正數(shù)，則naijXj bi Myi(i i,2,L ,m)jiyi y2 Lym m kyi,y2,L ,ym 。或in因?yàn)槿?yi 0 ，則 aij Xjjin若yi 1,則 對(duì)為bijibi 條件起作用nM , aijxj R條件不起作用ji2.約束條件的右端項(xiàng)可能是r個(gè)值(%b2,L ,br)中的某一個(gè)，即定義iyi 0najXj 匕或2或L或br ji假定約束條件右端項(xiàng)為 bi 否則由此，上述約

5、束條件可以表示成:aijxjb1y1b2y2Lbryrj1y1y2Lyr1 y1, y2,L , yr 0或13. 兩組條件中滿(mǎn)足其中一組若 x14 ，則 x2 1 ；否則（即 x1 4 時(shí)） ，x23最小，即：定義yi第i組條件不起作用 第i組條件起作用1,2)又 M 為任意大的正數(shù)，則問(wèn)題可表達(dá)為：x1 4 My1x21 My1x14 My2x23 My2y1 y21y1, y20,14. 用以表示含固定費(fèi)用的函數(shù)例如用Xj代表產(chǎn)品j的生產(chǎn)數(shù)量，其生產(chǎn)費(fèi)用函數(shù)通常可表示為:Cj(xj)KjcjXj0( Xj0)( Xj0)式中 K j 是同產(chǎn)量無(wú)關(guān)的生產(chǎn)準(zhǔn)備費(fèi)用。問(wèn)題的目標(biāo)是使所有產(chǎn)品的總

6、生產(chǎn)費(fèi)用為nmin zCj(Xj)j11Xj 0yj，那么XjMyjj 0Xj 0使問(wèn)題化為：nminzcjXjKjyjj10 s.tyjXjMyj0 或 1)j1,2,L ,n)（M 為充分大的正數(shù)）股整數(shù)規(guī)劃問(wèn)題建模:例 1 某飯店24小時(shí)中需要服務(wù)員數(shù)量如下：如果每個(gè)服務(wù)員連續(xù)工作8小時(shí)，試問(wèn)在2點(diǎn)、 6點(diǎn)、 10點(diǎn)、 14點(diǎn)、 18點(diǎn)、 22點(diǎn)鐘開(kāi)始上班的服務(wù)員為多少時(shí)，一天所需服務(wù)員人數(shù)最少？時(shí)間2-66-1010-1414-1818-2222-2最少服務(wù)員48107124設(shè)在2點(diǎn)、6點(diǎn)、10點(diǎn)、14點(diǎn)、18點(diǎn)、22點(diǎn)鐘開(kāi)始上班的服務(wù)員分別為 Xi,X2,X3,X4,X5,4,X64

7、810X47X4X512X5X64X4,X5X60整數(shù)min ZX1x2x3XiXiX2X2X3S.tX3X4X5X6則可建立整數(shù)規(guī)劃數(shù)學(xué)模型Xi, X2,X3 ,利用LINGO求解整數(shù)線(xiàn)性規(guī)劃問(wèn)題，得Min=x1+x2+x3+x4+x5+x6;x1+x6>=4;x1+x2>=8;x2+x3>=10;x3+x4>=7 ;x4+x5>=12;x5+x6>=4;gin(x1); gin(x2);gin(x3);gin(x4);gin(x5);gin(x6);Global optimal solution found.Objective value:26.0000

8、0Extended solver steps:0Total solver iterations:6VariableValueReduced CostX14.0000001.000000X24.0000001.000000X36.0000001.000000X41.0000001.000000X511.000001.000000X60.0000001.000000RowSlack or SurplusDual Price126.00000-1.00000020.0000000.00000030.0000000.00000040.0000000.00000050.0000000.00000060.

9、0000000.00000077.0000000.0000002.在高校籃球聯(lián)賽中，某學(xué)院男子籃球隊(duì)要從 8名隊(duì)員中選擇平均身高最高的出場(chǎng)陣容，隊(duì)員的號(hào)碼、身高及擅長(zhǎng)的位置如表所示:隊(duì)員號(hào)碼12345678身高（cm）1.921.901.881.861.851.831.801.78a®中鋒中鋒前鋒前鋒前鋒后衛(wèi)后衛(wèi)后衛(wèi)同時(shí)要求出場(chǎng)陣容滿(mǎn)足以下條件:(1)中鋒只能有一個(gè)上場(chǎng)；(2)至少有一名后衛(wèi)；(3)如果1號(hào)隊(duì)員和4號(hào)隊(duì)員都上場(chǎng)，則6號(hào)隊(duì)員不能上場(chǎng)；(4) 2號(hào)隊(duì)員和6號(hào)隊(duì)員必須保留一個(gè)不出場(chǎng)。寫(xiě)出該問(wèn)題的數(shù)學(xué)模型解：設(shè)Xj第j號(hào)隊(duì)員出場(chǎng)第j號(hào)隊(duì)員不出場(chǎng)(j 123,4,5,6,7,8

10、)則可建立整數(shù)規(guī)劃模型:maxZ1.92x1 1.90x21.88x31.86x4 1.85x5 1.83x6 1.80x7 1.78x8xx2x3x4xx2s.txx4x2x5x8乂6X7乂6乂6x8 121x1,x2,x3,x4,x5,x6,x7,x8利用LINGO進(jìn)行求解0 1規(guī)劃問(wèn)題，得Max=1.92*x1+1.9*x2+1.88*x3+1.86*x4+1.85*x5+1.83*x6+1.8*x7+1.78*x8 x1+x2+x3+x4+x5+x6+x7+x8=5;產(chǎn)數(shù)量，該廠(chǎng)才能有最大利潤(rùn)?x1+x2=1;x6+x7+x8>=1;x1+x4+x6<=2;x2+x6<

11、;=1;bin(x1); bin(x2); bin(x3); bin(x4); bin(x5); bin(x6); bin(x7); bin(x8);Global optimal solution found.Objective value:9.310000Extended solver steps:0Total solver iterations:0VariableValueReduced CostX11.000000-1.920000X20.000000-1.900000X31.000000-1.880000X41.000000-1.860000X51.000000-1.850000X60

12、.000000-1.830000X71.000000-1.800000X80.000000-1.7800003.某工廠(chǎng)生產(chǎn)A1、4兩種產(chǎn)品，產(chǎn)品分別由Bi、B2兩種部件組裝而成，每件產(chǎn)品所用部件數(shù)和有關(guān)部件的產(chǎn)量限額以及產(chǎn)品利潤(rùn)由下表所示。問(wèn)怎樣安排Ai、A2的生7''部件 產(chǎn)品-BiB2利潤(rùn)(元)Ai6115A24320部件的最大產(chǎn)量2510解：設(shè)生產(chǎn)A、A2分別為xv x2件，則maxZ 15x1 20x26x1 4x2 25s.t x1 3x2 10x1 ,x2 0, 整數(shù)很容易用 LINGO10.0 求出它的最優(yōu)解。Max=15*x1+20*x2;6*x1+4*x2&l

13、t;=20;x1+3*x2<=10;gin(x1);gin(x2);下料問(wèn)題也是典型的整數(shù)規(guī)劃問(wèn)題下面講指派問(wèn)題§ 4.2 分配問(wèn)題(指派問(wèn)題)與匈牙利法2-1問(wèn)題的提出與數(shù)學(xué)模型分配問(wèn)題也稱(chēng)指派問(wèn)題(Assignment Problem)，是一種特殊的整數(shù)規(guī)劃問(wèn)題，假定 有m項(xiàng)任務(wù)分配給m個(gè)人去完成，并指定每人完成其中一項(xiàng)，每項(xiàng)只交給其中一個(gè)人去例：有m個(gè)人，去完成m項(xiàng)任務(wù)，不同的人完成不同的任務(wù)效率如下表:B1B2LBmAa11a12La1mA2a21a22L92mLLLLLAmam1am2La mm如何分配任務(wù)，使花費(fèi)的總時(shí)間最少?&1&2LWma21a2

14、2 L92m稱(chēng)為分配問(wèn)題的效率矩陣。LLLLamiam2Lamm(i,j 1,2,L ,m)K1分配第i個(gè)人去完成第j項(xiàng)任務(wù)Xj0不分配第i個(gè)人去完成第j項(xiàng)任務(wù)則分配問(wèn)題的數(shù)學(xué)模型一般可以寫(xiě)為:m m min zaij xji 1 j 1 mXij1 (i 1,2,L ,m)j 1 ms.tXij1 (j 1,2,L ,m)i 1xijOS； 1 (i, j 1,2,L , m)2-2匈牙利法理論上，這也是運(yùn)輸問(wèn)題，但是它比運(yùn)輸問(wèn)題更特殊，可以用更特殊的方法加以解 決?？梢杂们蠼膺\(yùn)輸問(wèn)題的表上作業(yè)法求解分配問(wèn)題，但通常更有效的是用匈牙利方法 求解。解分配問(wèn)題的匈牙利方法是從這樣一個(gè)明顯的事實(shí)出

15、發(fā)的：如果效率矩陣的所有元素A 0,而其中存在一組位于不同行不同列的零元素，則只要令對(duì)應(yīng)于這些元素位置m m的Xij 1其余的Xij 0 ,則zajXj就是問(wèn)題的最優(yōu)解。如效率矩陣為：1 1 j 1014939200232303801214010000010010000就是指派問(wèn)題的最優(yōu)解。01但問(wèn)題是如何產(chǎn)生并尋找這些位于不同行不同列的零元素。匈牙利數(shù)學(xué)家克尼格 （Konig）證明了下面兩個(gè)基本定理，為解決以上問(wèn)題奠定了基礎(chǔ)。因此，基于這兩個(gè) 定理基礎(chǔ)上所建立的求解分配問(wèn)題的計(jì)算方法被稱(chēng)為匈牙利法。Ui定理1如果從分配問(wèn)題的效率矩陣（aj）中的某一行分別減去（或加上）一個(gè)常數(shù) （被稱(chēng)為該行的

16、位勢(shì)），從某一列分別減去（或加上）一個(gè)常數(shù) vj （稱(chēng)為該列的位勢(shì)） 得到一個(gè)新的效率矩陣（bj）,若其中bj aj Ui vj,則以（bj）為效率矩陣分配問(wèn)題的最 優(yōu)解等價(jià)于以（aj）為效率矩陣分配問(wèn)題的最優(yōu)解。證明：mbj%j 1m(aj Ui vj)xj j 1所以ajXj i 1majXji 1m Ui i 1 jmUi i 1xij1vj1minmvj1mxij i 1（后兩項(xiàng)是常數(shù)）mb. xij ij j 1m mminaj xji 1 j 1例：現(xiàn)有四人每人都能完成四項(xiàng)工作中的一項(xiàng)，但由于各自對(duì)不同工作的熟練程度或 技術(shù)專(zhuān)長(zhǎng)的不同，完成每項(xiàng)工作花費(fèi)的時(shí)間也不同。如下表BB2B3

17、B4Ai314105A21041210A39141513A4781190”元素匈牙利方法的步驟：1 .變換效率矩陣，使變換后的效率矩陣每行、每列至少有一個(gè)310(aij)9714414810121511510139349706001105178644264220600110513420042(bj)02.試求最優(yōu)解（通過(guò)標(biāo)注零的方法）所以可以求得0 0 0 10 10 0(Xj),min z 5 4 9 11 2910 0 00 0 10A B4,A2 B2A Bi,A4 B3例：有一份說(shuō)明書(shū)，要分別譯成英、日、德、俄四種文字，交甲、乙、丙、丁四個(gè) 人去完成。因各人專(zhuān)長(zhǎng)不同，他們完成翻譯不同文

18、字所需的時(shí)間如下表，應(yīng)如何分配， 使這四個(gè)人分別完成這四項(xiàng)任務(wù)的總時(shí)間為最短。甲乙丙丁譯成英文21097譯成日文154148譯成彳思義13141611譯成俄文415139列均減去該列的最小值，使每行每列至少有一1 .每一行均減去該行的最小值, 個(gè)零元素（變換效率矩陣）215134104141591416137811924114011208031171059554050112080311250454052 .試求最優(yōu)解*011208*031125*0454053 .作覆蓋所有零元素的最少直線(xiàn)集合(D(2)(3)(4)對(duì)沒(méi)有0*的行打，對(duì)打了，的行上0元素所在的列打， 對(duì)打了，的列上0所在的行打V

19、 對(duì)打了，的行上0元素所在的列打，直至打不出新的行和新的列這樣就得到能夠覆蓋所有零元素的對(duì)沒(méi)有打，的行劃?rùn)M線(xiàn)，對(duì)打了，的列劃豎線(xiàn), 最少直線(xiàn)組合。定理2若矩陣A可分為“ 0”與非“ 0”兩部分，則覆蓋“ 0”元素的最少直線(xiàn)數(shù)等 于位于不同行不同列的“ 0”元素的最大個(gè)數(shù)。恰好等于我們標(biāo)出 0*的個(gè)數(shù)。證明：已知矩陣中有若干個(gè)0元素，設(shè)覆蓋全部0元素最少需要m條直線(xiàn)，又設(shè)位 于不同行不同列的0有M個(gè)，因覆蓋每個(gè)0至少用一條直線(xiàn)，故有m M卜面要證明Mm,假定覆蓋所有0元素的m條直線(xiàn)有行（用ii,i2,L ,ir表示）c列（用ji, j2,L , jc表示），m r c;顯然在每一行上至少存在一個(gè)

20、不在ji, j2,L , jc列上的0元素；設(shè)某一行上這些不在j1, j2,L , jc列上的0元素下標(biāo)的集合為§ laii 0,l ji，j2，L,jJ對(duì)ii,i2,L ,ir行分別有集合Si1,Si2,L ,Sr ,從這些集合中任取k個(gè)（k r）,其集合中 的不同元素個(gè)數(shù)必不少于k,否則這k行的直線(xiàn)可用少于k條列線(xiàn)代替，與m是覆蓋0 元素的最少直線(xiàn)的假定矛盾。由此可知，在r條行線(xiàn)上存在不少于r個(gè)位于不同的列，且這些0不位于ji,j2,L , jcccJ|7J477jc列上。同理可以證明在c條列線(xiàn)上存在不少于c個(gè)位于不同行的 0,且這些0不位于ii,i2,L ,ir行上。若上述兩部

21、分0的個(gè)數(shù)總和為S ,則S m,又顯然S M ,故有M m從而有M m ,定理得證4.繼續(xù)變換效率矩陣，試求最優(yōu)解，回到第二步。從未被直線(xiàn)覆蓋的所有元素中找出一個(gè)最小元素 k,然后將效率矩陣未劃?rùn)M線(xiàn)的行均減去這個(gè)最小元素，劃豎線(xiàn)的列均加上這個(gè)最小元素 再試求最優(yōu)解，繼續(xù)。最優(yōu)解為（面）0 0 100 10 00 0 0 110 0 0*0 6 0313 05 4*43 0 0*0923min z 9 4 11 4 28,或者 min z 2411 45222 28例：求下列指派問(wèn)題的最優(yōu)解人（工件）B1B2B3B4B5A1127979A289666A3717121412A415146610A5

22、4107106* *12797950202702028966623*00043*000717121412*010575*0835315146610980*041180*044107106063620414*0最優(yōu)解（Xj）min z兩點(diǎn)說(shuō)明0010010000601000000106000016 32或 min z 76764222 321.分配問(wèn)題中如果人數(shù)和工作任務(wù)數(shù)不相等時(shí)的處理方法。舉例來(lái)說(shuō)，如果人員數(shù) 大于任務(wù)數(shù)，可以增加虛的任務(wù)，使總的任務(wù)數(shù)與總的人員數(shù)相等，不過(guò)每個(gè)人完成虛任務(wù)的時(shí)間為0, 數(shù)等于任務(wù)總數(shù)。如：效益當(dāng)然也為0;當(dāng)人員數(shù)小于任務(wù)數(shù)，可增加虛的人員，使人員總37365

23、5min z61642722453466487320000008000000InmIVVVI136260027144003365800464370055243006576200*04*03225*0531602312442651*0000*0000000*002.如果把效率矩陣改為效益矩陣, 即可。把求指派問(wèn)題的最小值化為求指派問(wèn)題的最大值m如 max zi 1ma xij人jj 1等價(jià)于min zm(aij )xij,由于（aj）為負(fù)，不容易比較，現(xiàn)在將每一個(gè)數(shù)都加上M ,等價(jià)于min wm(Mj 1aij ）xj, Mmax aj化為一般的最小化指派問(wèn)題。虛人員完成各任務(wù)的效率與效益均為

24、0,這時(shí)可能有的任務(wù)無(wú)法落實(shí)。例：一個(gè)公司要分派5個(gè)推銷(xiāo)員去5個(gè)地區(qū)推銷(xiāo)某種產(chǎn)品，5個(gè)推銷(xiāo)員在各個(gè)地區(qū)推銷(xiāo)這種產(chǎn)品的預(yù)期利潤(rùn)如下表所示。若每個(gè)推銷(xiāo)員只能去一個(gè)地區(qū)，應(yīng)如何分派這5個(gè)推銷(xiāo)員才能使公司的利潤(rùn)最大？ABCDE甲1 15110121 1012乙1112999丙1020151712丁1 18 11791 913戊713101312maxaj 20510810898111111(20 a。)1005382311117053531033310053801995050*5210032*100237*0169 4*600 00*05 030*10 010*10 0 215*01672*822 0

25、013 7 10 780 0 10 0(Xj)0 0 0 0 10 0 0 ,maxz 12 9 20 18 13 72例：某車(chē)隊(duì)有5輛汽車(chē)，將駛往3個(gè)目的地運(yùn)貨。一地的貨物只需一輛車(chē)送，其運(yùn) 費(fèi)(元)如下表：(1)試求最優(yōu)指派的調(diào)運(yùn)方案(2)若表中數(shù)字表示所得利潤(rùn)，則應(yīng)如何指派？(3)若車(chē)2載不下A地所需貨物，車(chē)5爬不上通往B地必經(jīng)之路上的坡，對(duì)(1) (2)的最優(yōu)解有什么影響？汽車(chē)1叱2叱3汽車(chē)4叱5A10121411P 13B1320231521C861075相應(yīng)的作業(yè)P125, 4.3 (a) (b)P125 4.5提示以后讓學(xué)生自己完成要真正弄懂(a)將最后一列先減去一個(gè)數(shù)如30,使

26、E列占優(yōu)勢(shì)，這就保證了任務(wù)E必須能完成,252931427然后再增加一個(gè)虛的人393826203,再增加一行0也無(wú)妨3427284022442362315(b)取每列的最小值，放至最后一行，作為第 5個(gè)人，然后在任務(wù)分派時(shí)將第 5 個(gè)人的任務(wù)再還原。ABCDE甲2529314237乙3938262033丙3427284032丁244236：2345戊2427262032(c)將不能完成任務(wù)的人、任務(wù)對(duì)應(yīng)時(shí)間放至 M 100,然后再?gòu)谋?、丁行的最小值?至下一行，分配完任務(wù)以后，與(b) 一樣進(jìn)行還原。ABCDE甲2529 11004237 I乙100381002033丙34272840100丁

27、10042 I362345 I戊3427282345這樣即可達(dá)到目的§4.3分枝定界法在線(xiàn)性規(guī)劃問(wèn)題中，變量x是在一個(gè)連續(xù)的范圍內(nèi)取值，因此可行解個(gè)數(shù)無(wú)限多。 但在整數(shù)規(guī)劃問(wèn)題中變量只能取離散的整數(shù)值，可行解的總數(shù)是有限的。從有限多的可 行解中尋找最優(yōu)解的最直觀(guān)、最簡(jiǎn)單的方法是枚舉法，但方法不可行。分枝定界法 （branch and bound method）就是為求解同整數(shù)規(guī)劃具有類(lèi)似性質(zhì)的一大類(lèi)問(wèn)題而設(shè)計(jì) 的一種較好的方法。第一步：尋找替代問(wèn)題并求解。方法是放寬約束條件，去掉整數(shù)約束。如果非整數(shù)線(xiàn)性規(guī)劃問(wèn)題的最優(yōu)解就是整數(shù), 則已求得整數(shù)問(wèn)題的最優(yōu)解；否則，這個(gè)最優(yōu)解是原整數(shù)線(xiàn)性

28、規(guī)劃問(wèn)題最優(yōu)解的一個(gè)上 界（求最大值）或者下界（求最小值）。max z 3x1 2x22x1 3x2 14 st x1 0.5x2 4.5放松約束條件，求解如下問(wèn)題maxz 3x1 2x22x1 3x2 14s.t 2x1 x2 9(LP1)x1,x2 0,整數(shù),x2 0基解x1x2x3x4x3142310x492101z032001x35021-1x19/211/201/2z-27/201/20-3/2x25/2011/2-1/2x113/410-1/43/4z-59/400-1/4-5/4基解x1x2x3x4xsx25/2011/2-1/20x113/410-1/43/40x-1/200-

29、"21/21z-59/400-1/4-5/402x1 3x2 142x1 x2 9(LP13)st12x2 3x1,x2 0x1,x2 0一.135(LP1)取優(yōu)斛 x1, x2 ,max z42max z3x12x22x1 3x2 142x1x29(LP12)st12x22594maxz 3x1 2x2X2X1x327/210100110 01/2-1/200 1-1-2z-29/20 0 0 -3/2-1/2(LP12)最優(yōu)解 x1 7,x2 2,maxz 2max z 3x1 2x22xi 3x2 142x1 x2 9 (LP121)s.t x2 2xi 3x1, x2 029

30、2max z 3x1 2x22xi 3x2 142x1 x2 9(LP122)s.t x2 2x14x1, x2 0基解XiX2X3X4X5X6X2 xi x3 x627/21-1/2010010010001/2-1/2001-1-2000-1/21/21z-29/2000-3/2 -1/2 0X2 xi x3 x4232101001001000001010-3-2001-1-2z-130000-2-3(LP121)最優(yōu)解為 x1 3,x22,max z 13, z 13基解X1X2X3X4X5X6X2 xi x3 %27/21-4010-110010001/2-1/2001-1-200000

31、1z-29/2000 -3/2 -1/20X2 xi x3 x627/21-1/2010010010001/2-1/2001-1-20001/2-1/21z-29/2000 -3/2 -1/20X2 xiX3 X614310100101020000-101-30-400-11-2一 z 一-14000-20-1(LP122)最優(yōu)解為 x14,x2 1,maxz 14, z 14基解Xx2x3x4x5x25/2011/2-1/20x113/410-1/43/40*5-30-1001z-59/400-1/4-5/40x25/2011/2-1/20x113/410-1/43/40x5-1/2001/

32、2-"21z-59/400-1/4-5/40x230100-1x15/2101/203/2x4100-11-2z-54/400-3/20-5/2527(LP13)最優(yōu)解xi ,X2 3,maxz 13.5 14 ,盡管不是整數(shù)解，但它的目標(biāo)函數(shù)的最大 22值小于14,不必分枝，因此該整數(shù)線(xiàn)性規(guī)劃問(wèn)題的最優(yōu)解為：x1 4,x2 1,maxz 14故，最優(yōu)解求得：x1 4,x2 1,maxz 14這一個(gè)比較簡(jiǎn)單的整數(shù)線(xiàn)性規(guī)劃問(wèn)題，分解為求解四個(gè)非整數(shù)線(xiàn)性規(guī)劃問(wèn)題，有些 求解更為復(fù)雜。希望同學(xué)們要注意到這一點(diǎn)，理解這種原理，求解這樣方法。作業(yè)：P127, 4.8 (b)§ 4.4

33、 割平面法這是求解整數(shù)規(guī)劃問(wèn)題最早提出的一種方法，1958年由高莫瑞（Gomory）提出。它的基本思想是在整數(shù)規(guī)劃問(wèn)題的松弛問(wèn)題中依次引進(jìn)線(xiàn)性約束事件（Gomory約束或割平面），使問(wèn)題的可行域逐步縮小。但每次切割只割去問(wèn)題的部分非整數(shù)解，直到使問(wèn) 題的目標(biāo)函數(shù)值達(dá)到最優(yōu)的整數(shù)點(diǎn)成為縮小后可行域的一個(gè)頂點(diǎn)，這樣就可以用求解線(xiàn)性規(guī)劃問(wèn)題的方法找出這個(gè)最優(yōu)解。第一步：把問(wèn)題中所有約束條件的系數(shù)均化為整數(shù)，若不考慮變量的整數(shù)性約束， 可得到該問(wèn)題的松弛問(wèn)題并求解得最后一個(gè)單純形表maxz 3x1 2x22x1 3x2 14st 2x1 x2 9 X1,X2 0基解X1X2X3X4X5X2X15/21

34、3/4011/2-1/2010-1/43/40z-59/400 -1/4-5/40X5-1/200 -1/2-1/21 111（增加割平聞X3 x4 ） 222若第一步得到整數(shù)解，求解到此結(jié)束，否則轉(zhuǎn)第二步。第二步；找出非整數(shù)解變量中非整數(shù)部分最大的一個(gè)基變量，它們對(duì)應(yīng)的方程為bilXl bi2X2 LbinXnbi0設(shè) fjbbj, j 0,1,2,L ,n ,那么，有bilXi fi1X1 兒風(fēng)fi2X2 LbinXnfB甌1從而有fi1X1fi2X2 LfinXnfi0稱(chēng)為割平面引入松弛變量Xn i ,儲(chǔ)Xifi2X2 LfXn Xni解加入到單純形表中去，利用對(duì)偶單純形方法進(jìn)行換基迭代

35、，得到基解XiX2X3X4X5X6X22010-110X17/21001-1/20X310011-20z-29/2000-1-1/20X6-1/20000-"21盡管得到最優(yōu)解，仍不是整數(shù)解，增加割平面 繼續(xù)使用對(duì)偶單純形方法進(jìn)行換基迭代，得到:基bX1X2X3X4X5X6X21010-102Xi410010-1X3300110-4X5100001-2z-14000-10-1最優(yōu)解，并且為整數(shù)最優(yōu)解。因此得到原整數(shù)線(xiàn)性規(guī)劃問(wèn)題的最優(yōu)解為:x1 4, x2 1,maxz 14這就是割平面法?？梢?jiàn)，割平面方法比分枝定界方法來(lái)得快。§ 5應(yīng)用舉例例3東方大學(xué)計(jì)算機(jī)實(shí)驗(yàn)室聘用 4名

36、大學(xué)生（代號(hào)1, 2, 3, 4）和2名研究生（代號(hào)5, 6） 值班答疑，已知每人從周一至周五每天最多可安排的值班時(shí)間及每人每小時(shí)值班的報(bào)酬如下表:星期一星期二星期三星期四星期五110.0606072 110.0 10r 606039.94830549.855604510.830480611.306063該實(shí)驗(yàn)室開(kāi)放時(shí)間為上午8: 00至晚上10: 00,開(kāi)放時(shí)間內(nèi)須有且僅須有一名學(xué)生值班，規(guī)定3人，且其中必須有一名研究生。試為該實(shí)驗(yàn)室安排大學(xué)生每周值班不少于 8小時(shí)，研究生每周不少于 7小時(shí)，每名學(xué)生每周值班不超過(guò)3次，每次值一張人員安排的值班表，使總的支付報(bào)酬為最少!1,學(xué)生i在周j值班解

37、：設(shè)xj為學(xué)生i在時(shí)間星期j的值班時(shí)間,yjij 0,否則min z 10x11 10x219.9x31 9.8x4110.8x51 11.3x6110X2 10x229.9x32 9.8x4210.8x52 11.3x6210X3 10x239.9x33 9.8x4310.8x53 11.3x6310X4 10x249.9x34 9.8x4410.8x54 11.3x6410。10x259.9x35 9.8x4510.8%5 11.3x65班不少于2小時(shí)，每天安排值班的學(xué)生不超過(guò)%2yj0,(i 1,2,3,4,5,6; j 1,2,3,4,5)%aj yj0,(i 1,2,3,4,5,6;

38、j 1,2,3,4,5)xi1xi2xi1xi2xi 3Xi4xi 3xi4x5 8,(ix5 7,(i1,2,3,4)5,6)st x1jx2 jx3jx4j x5j x6j 14,(j 1,2,3,4,5)yi1%2yi3y yi5 3,(i1,234,5,6)y1jy2j y3j y4j y5j y6j3,(j 1,2,3,4,5)y5jy6j1,(j 1,2,3,4,5)xj0,yj0或 1 ,(i1,2,3,4,5,6; j 1,2,3,4,5)min=10*x11+9.9*x31+9.8*x41+10.8*x51+10*x22+9.9*x32+9.8*x42+11.3*x62+10

39、*x13+9. 9*x33+9.8*x43+10.8*x53+10*x24+10.8*x54+11.3*x64+10*x15+9.9*x35+9.8*x45+11.3*x 65;x11-2*y11>0;x13-2*y13>0;x15-2*y15>0;x22-2*y22>0;x24-2*y24>0;x31-2*y31>0;x32-2*y32>0;x33-2*y33>0;x35-2*y35>0;x41-2*y41>0;x42-2*y42>0;x43-2*y43>0;x45-2*y45>0;x51-2*y51>0;x

40、53-2*y53>0;x54-2*y54>0;x62-2*y62>0;x64-2*y64>0;x65-2*y65>0;x11-6*y11<0;x13-6*y13<0;x15-7*y15<0;x22-6*y22<0;x24-6*y24<0;x31-4*y31<0;x32-8*y32<0;x33-3*y33<0;x35-5*y35<0;x41-5*y41<0;x42-5*y42<0;x43-6*y43<0;x45-4*y45<0;x51-3*y51<0;x53-4*y53<0;x

41、54-8*y54<0;x62-6*y62<0;x64-6*y64<0;x65-3*y65<0;x11+x13+x15>8;x22+x24>8;x31+x32+x33+x35>8;x41+x42+x43+x45>8;x51+x53+x54>7;x62+x64+x65>7;x11+x31+x41+x51=14;x22+x32+x42+x62=14;x13+x33+x43+x53=14;x24+x54+x64=14;x15+x35+x45+x65=14;y11+y13+y15<3;y22+y24<3;y31+y32+y33+y3

42、5<3;y41+y42+y43+y45<3;y51+y53+y54<3;y62+y64+x65<3;y11+y31+y41+y51<3;y22+y32+y42+y62<3;y13+y33+y43+y53<3;y24+y54+y64<3;y15+y35+y45+y65<3;y51>1;y62>1;y53>1;y54+y64>1;y65>1;gin(x11);gin(x13); gin(x15);gin(x22); gin(x24);gin(x31) gin(x41) gin(x51) gin(x62) bin(y

43、11) bin(y22) bin(y33) bin(y41)bin(y51) bin(y62)gin(x32); gin(x33);gin(x35);gin(x42); gin(x43); gin(x45);gin(x53); gin(x54);gin(x64); gin(x65);bin(y13); bin(y15);bin(y24); bin(y31); bin(y32);bin(y35);bin(y42); bin(y43); bin(y45);bin(y53); bin(y54);最優(yōu)結(jié)果為支付報(bào)酬為每周bin(y64); bin(y65);例4 紅星日用化工廠(chǎng)為發(fā)運(yùn)產(chǎn)品，下一年需 6

44、種不同容積的包裝箱，每種包裝箱的需 求量及生產(chǎn)一個(gè)包裝箱的可變費(fèi)用如下表包裝箱代號(hào)123456容積（m3）0.080.10.120.150.200.25需求量（個(gè)）500550700900450400口艾費(fèi)用（兀/個(gè)）5.08.010.012.116.318.2由于生產(chǎn)不同規(guī)格的包裝箱需要專(zhuān)門(mén)設(shè)備、材料等，生產(chǎn)每一種容積的包裝箱的固定費(fèi) 用為1200元，又若某一種容積的包裝箱數(shù)量不夠時(shí)可用比它容積大的代替。試問(wèn)該化 工廠(chǎng)應(yīng)訂做哪幾種代號(hào)的包裝箱各多少個(gè)，使費(fèi)用最節(jié)??？解：設(shè)為,（j 1,2,3, 4,5,6）為代號(hào)j的包裝箱的數(shù)量訂做第j種包裝箱 否則j123,4,5,6min z 1200(

45、 yi y 坐 y y y6)5xi 8x210x3 12.1x4 16.3x5 18.2x6X1 x2 x3 x4 x5 x63500x6400xx6850x4x5x61750stx3x4x5x62450x2x3x4xsx63000xj 9999yj 0,( j 1,2,3,4,5,6)xj 0, yj 0或 1,(j 123,4,5,6)x1 500, x2 0,x3 1250, x4 900, x5 0,x6 850min z 46160元Min =1200*y1+1200*y2+1200*y3+1200*y4+1200*y5+1200*y6+5*x1+8*x2+ 10*x3+12.1*

46、x4+16.3*x5+18.2*x6;x6>=400;x5+x6>=850;x4+x5+x6>=1750;x3+x4+x5+x6>=2450;x2+x3+x4+x5+x6>=3000;x1+x2+x3+x4+x5+x6>=3500;x1-10000*y1<=0;x2-10000*y2<=0;x3-10000*y3<=0;x4-10000*y4<=0;x5-10000*y5<=0;x6-10000*y6<=0;gin (x1);gin (x2);gin (x3);gin (x4);gin (x5);gin (x6);bin (y1);bin (y2);bin (y3);bin (y4);bin (y5);bin (y6);例5春江市計(jì)劃為新建的 5個(gè)居民區(qū)中的兩個(gè)分別各設(shè)立一所小學(xué)，下表給出