整數(shù)規(guī)劃案例

整數(shù)規(guī)劃案例目錄TOC\o"1-5"\h\z\o"CurrentDocument"例1固定費(fèi)用問題 1\o"CurrentDocument"例2選擇性約束條件 1\o"CurrentDocument"例3可行域描述問題 2\o"CurrentDocument"例4最優(yōu)分配問題 2\o"CurrentDocument"例5選址問題 2\o"CurrentDocument"例6排序問題 3\o"CurrentDocument"例7利潤分段線性問題 5\o"CurrentDocument"例8可靠性問題 5\o"CurrentDocument"例9裝配線平衡問題 6\o"CurrentDocument"例10貨物列車編組計(jì)劃問題 7例1固定費(fèi)用問題工廠準(zhǔn)備生產(chǎn)Al、A2、A3三種產(chǎn)品。若Aj產(chǎn)品投產(chǎn)，無論產(chǎn)量大與小，都需要一筆固定費(fèi)用dj（例如裝夾具的設(shè)計(jì)制作費(fèi)用）。而每生產(chǎn)一件產(chǎn)品，其利潤為cj,試問固定費(fèi)用這個(gè)因素如何體現(xiàn)在模型中而使總利潤最大?（其它約束條件暫不列入）解設(shè)產(chǎn)品Aj的產(chǎn)量為xj,又設(shè)0一1變量yi=l（當(dāng)xj>0）,0（否則）于是，目標(biāo)函數(shù)為max仁clxl+c2x2+c3x3?dlyl-d2y2?d3y3例2選擇性約束條件某工廠生產(chǎn)第j種產(chǎn)品的數(shù)量為Xj,j=l,2,3。其使用的材料在材料甲及乙中選擇一種。材料消耗的約束條件分別為2x1+5x24-6x3W180及4x1+3x2+7x3^240（其它資源約束未列出），試問這類選擇性約束條件如何體現(xiàn)在模型中？解引進(jìn)0一1變量y：y=0（選擇材料甲），0（否則）。這樣，“或此或彼”相互排斥的約束條件就可化成下列兩個(gè)約束條件：2xl+5x2+6x3W180+My,4x1+3x2+7x3W240+M（1-y）,其中M是充分大的正數(shù)。可以看出，當(dāng)y=0時(shí)，第二個(gè)約束變成4xl+3x2+7x3W240+M,由于M是充分大的正數(shù)，所以這個(gè)約束條件自動滿足而不起作用，而第一個(gè)約束為2xl+5x2+6x3W180，這意味著選擇材料甲；反之，當(dāng)y=l時(shí)，第二個(gè)約束起作用，第一個(gè)約束變?yōu)?xl+5x2+6x3W180+M不起作用，這意味著選擇材料乙。因此，借助0一1變量，材料選擇的兩種可能性就同時(shí)包括在一個(gè)模型中了。一般地，假定在某種情況下要在P個(gè)約束條件中至少要選擇q個(gè)約束條件得到滿足，那么，我們引進(jìn)P個(gè)0-1變量yi,則選擇性的約束條件問題就化為.……例3可行域描述問題如何把圖中的陰影部分所表示的可行域用聯(lián)立的線性約束條件來描述?例4最優(yōu)分配問題現(xiàn)有四部車床Ai(1=1,...,4)和四個(gè)零件Bj(j=l,...,4)，車床Ai加工零件Bj所需時(shí)間ti(j小時(shí))由下表給出。問如何安排生產(chǎn)計(jì)劃，使每部車床加工一個(gè)零件、一個(gè)零件由一部車床加工,且全部零件加工完成的時(shí)間最早(假定四部車床同時(shí)開始加工)。試建立整數(shù)規(guī)劃模型。 B1 B2 B3B4A13541A27213A33451A46752例5選址問題現(xiàn)準(zhǔn)備從Al、A2、A3三個(gè)地點(diǎn)選擇二處開設(shè)工廠，它們每月的產(chǎn)量ai(i=l,2,3)分別至多為70、80和90個(gè)單位，每月的經(jīng)營費(fèi)用di(與產(chǎn)量無關(guān))分別為100、90和120o有三家客戶Bl、B2和B3,他們每月的需求量bj(j=l,2,3)分別為40、80和45個(gè)單位。Ai至Bj的單位運(yùn)價(jià)cij如表，問如何選址，使每月經(jīng)營和運(yùn)輸費(fèi)用最低?試建立整數(shù)規(guī)劃模型。解設(shè)yi=l（選地點(diǎn)Ai開設(shè)工廠），0（否則），又設(shè)xij為在地點(diǎn)Ai處開設(shè)工廠時(shí)從Ai至客戶Bj的運(yùn)量。顯然，有yl+y2++y3=2。若在Ai處不開設(shè)工廠，則Ai至Bj的運(yùn)量應(yīng)為零；若在Ai處開設(shè)工廠，貝U每個(gè)月Ai至Bj的運(yùn)量之和不超過Ai處開設(shè)工廠的產(chǎn)量ai,寫成約束條件就成為：xil+xi2+xi3Waiyi,i=l,2,3。又客戶Bj的需求量必須得到滿足，所以有xlj+x2j+x3j=bj,j=l,2,3o每月的費(fèi)用f為：則本問題的數(shù)學(xué)模型為：例6排序問題用編號為1號、2號、3號、4號的四種機(jī)床生產(chǎn)三種產(chǎn)品1號、2號、3號。這三種產(chǎn)品的工藝路線及工序加工時(shí)間如下表所示。工藝路線j號機(jī)床加工時(shí)間（小時(shí)）12341al a3 -?a4i號產(chǎn)品2bl土b43c2=3一臺機(jī)床一次只能加工一個(gè)產(chǎn)品?，F(xiàn)要求2號產(chǎn)品從開始加工到完成，經(jīng)歷時(shí)間不得超過d小時(shí)。問如何確定各種產(chǎn)品在機(jī)床上的加工順序，使在最短時(shí)間內(nèi)制成全部產(chǎn)品。試建立整數(shù)規(guī)劃模型。解設(shè)xij為I號產(chǎn)品在機(jī)床j上開始加工的時(shí)間（從零基準(zhǔn)點(diǎn)算起，以小時(shí)計(jì)）。第一組約束條件為要求三種產(chǎn)品都應(yīng)按照工藝路線的規(guī)定順序來進(jìn)行加工。例如對1”產(chǎn)品來說，首先是在1”機(jī)床上加工，然后依次在3”和4”機(jī)床上加工，因此有：類似地,對2”和3”產(chǎn)品，有:zli+口1Wz13, zl3+口3Wzl.,z21+61W衛(wèi)z2,zz2+62Wz24,z32+龜Wz33。第二組約束條件為一族選擇性的約束條件，以保證一臺機(jī)床一次只能加工一個(gè)產(chǎn)品。例如，對于機(jī)床1”來說，或者1。產(chǎn)品先于2”產(chǎn)品加工，或者2”產(chǎn)品先于1”產(chǎn)品加工，即應(yīng)有t或zll+口iWz2L或z21+61Wzll。引進(jìn)。一1變量y。，上述選擇性約束條件就成為：zll+口1WZ21+坷1,'z21+61Wzll+M（l—yl）類似地，借助于O—1變量弛、y。和弘，對2”、3o和4。機(jī)床有；z22+62Wz32+Mj,2 'z32+f2Wz22+M（l一弛）zl3+口3Wz33+My3z33+f?Wzl3+M（l—y3）zl'+口4Wz2'+M負(fù)z2'+以Wzl.+M（1一執(zhí)），其中8—0,1,一2,3,4o2”產(chǎn)品從10機(jī)床對它開始加工（在zoo時(shí)刻）到4”機(jī)床將其加工完畢（在z"+64時(shí)刻），其經(jīng)歷時(shí)間有約束：z2‘+6'—z21W：do三個(gè)產(chǎn)品都完工的時(shí)間y為：y=max（z…+口"z24+64,z33+c3},我們將它化為線性約束條件yNzl'+口'；yNz2'+機(jī)； y\z33+f3。.

昏9拳上所述，得整數(shù)規(guī)劃模型如下例7利潤分段線性問題某廠生產(chǎn)甲、乙兩種產(chǎn)品，需經(jīng)過金工和裝配兩個(gè)車間加工，有關(guān)數(shù)據(jù)如表工時(shí)定額(小時(shí)/件)—產(chǎn)—-品總有效工時(shí)田乙車問金工43480裝配25500售價(jià)(兀/件)300520產(chǎn)品乙無論生產(chǎn)批量大小，每件產(chǎn)品生產(chǎn)成本總為400元。試根據(jù)產(chǎn)品甲生產(chǎn)成本的下列兩種情況分別建立整數(shù)規(guī)劃模型：(1)產(chǎn)品甲的生產(chǎn)成本分段線性：第1件至第30件，每件成本為200元；第31件至第70件，每件成本為190元；從第71件開始，每件成本為195元。(2)產(chǎn)品甲的產(chǎn)量不超過40件時(shí)，每件成本為200元，但若超過40件，則甲的全部產(chǎn)品每件成本都為195元。例8可靠性問題某種儀表由三個(gè)部件串聯(lián)而成。j號部件的可靠性由所組裝的元件個(gè)數(shù)決定每個(gè)j號元件的重量和成本由表給出。元件個(gè)數(shù)ij號部件可靠性12310.60.750.720.750.850.830.80.90.85元件成本重量1號303j號2號4043號506設(shè)計(jì)過程中，該儀表對三個(gè)部件的總重量限制為25,總成本限制為240,問j號部件如何選擇j號元件的個(gè)數(shù)，使儀表的可靠性最大？例9裝配線平衡問題若某工廠的產(chǎn)品的裝配線由6道工序組成，各工序的加工時(shí)間及工序的前后順序如表工序加工時(shí)間緊前工1325322461,3r\524634若這條裝配線設(shè)若干個(gè)工作站。被裝配的產(chǎn)品在這些編了號的工作站上流水移動時(shí)，每個(gè)工作站都要完成一道或幾道工序。假設(shè)每個(gè)工作站加工每個(gè)被裝配的產(chǎn)品時(shí)至多耗時(shí)10分鐘，問最少應(yīng)設(shè)立幾個(gè)工作站?每個(gè)工作站完成哪些工序？解顯然，需要的工作站不會多于4個(gè)。這是因?yàn)橛杀?—7可以觀察到一個(gè)解：工序1、3在一個(gè)站上完成，而工序4、5和6各在一個(gè)工作站上進(jìn)行，此時(shí)只需4個(gè)工作站。fl,在裝配線上有工作站-『，刪』一.{-『=1,…，4[0,否則，因此，為使工作站數(shù)實(shí)現(xiàn)最少.目標(biāo)函數(shù)為：min廠=硼1+叫2+叫3+硼I。接下來我們來分析約束條件：第一組約束條件：對工序i來說，它應(yīng)恰在某一個(gè)工作站上完成，為此有矗l+0i2+83+z"=1, i=l,???,6；第二組約束條件：對工作站—『來說，在該站上完成的各道工序所需時(shí)間的總和不得超過10分鐘，因此有：321J+5x2j+2x3』+6x,j+8站』+3XsiW10,第三組約束條件：工作站歹若設(shè)立，則在此站上完成的工序不會超過6道若不設(shè)立，那么就不能將任何工序分派給該站（換句話說，若叫J=0，則所有的z；j=0），從而有：'zlj+z2J+z3j+z',+z5J+z6jW6w』， ，=1,...,4；最后我們來考慮關(guān)于各道工序前后順序這組約束條件：首先考慮工序2應(yīng)當(dāng)在工序3之前完成這個(gè)要求。若工序3在最后一個(gè)工作站4上完成，那顯然沒有什么問題，因?yàn)樗泄ば蚨家诖苏厩巴瓿苫蚓驮诖苏旧贤瓿?。若工?分配在工作站3上完成，則工序2就不能分配在工作站4上完成，而必須分配在工作站1、2或3上完成，由此可得它說明，若x33=l,則x21,x22,x23中必有一個(gè)變量取值為1,以保證工序2在工序3之前完成。類似地，若工序3分配在工作站2或1上完成，就應(yīng)分別有：例10貨物列車編組計(jì)劃問題某鐵路線路有五個(gè)貨物列車編組站Al、A2、A3、A4和A5。編組站Ai發(fā)往前方各編組站Aj的車輛數(shù)aij（或稱為車流量）己知，如圖4—3所示。若始發(fā)站Ai至到達(dá)站Aj開行直達(dá)列車（