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

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

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