運(yùn)籌學(xué)-整數(shù)規(guī)劃

第四章整數(shù)規(guī)劃(IntegerProgramming,IP)整數(shù)規(guī)劃（IntegerProgramming）主要是指整數(shù)線性規(guī)劃。一個線性規(guī)劃問題，如果要求部分決策變量為整數(shù)，則構(gòu)成一個整數(shù)規(guī)劃問題。所有變量都要求為整數(shù)的稱為純整數(shù)規(guī)劃（PureInteger

Programming）或稱全整數(shù)規(guī)劃（AllintegerProgramming）；僅有一部分變量要求為整數(shù)的稱為混合整數(shù)規(guī)劃（MixedIntegerProgramming）；有的變量限制其取值只能為0或1，這類特殊的整數(shù)規(guī)劃稱為0－1規(guī)劃(0-1

IntegerProgramming)。整數(shù)規(guī)劃的有關(guān)概念一、整數(shù)規(guī)劃問題例4.1某工廠生產(chǎn)甲、乙兩種設(shè)備，已知生產(chǎn)這兩種設(shè)備需要消耗材料A、材料B，有關(guān)數(shù)據(jù)如下，問這兩種設(shè)備各生產(chǎn)多少使工廠利潤最大？設(shè)備材料甲乙資源限量材料A（kg）2314材料B（kg）10.54.5利潤（元/件）32第一節(jié)整數(shù)規(guī)劃問題及其數(shù)學(xué)模型解：設(shè)生產(chǎn)甲、乙這兩種設(shè)備的數(shù)量分別為x1、x2，由于是設(shè)備臺數(shù)，則其變量都要求為整數(shù)，建立模型如下：Maxz=3x1+2x22x1+3x2≤14x1+0.5x2≤4.5x1、x2≥0,且為整數(shù)要求該模型的解，不考慮整數(shù)約束條件，用單純形法對相應(yīng)線性規(guī)劃求解，其最優(yōu)解為：x1＝3.25x2＝2.5maxz＝14.75湊整得到的（4，2）不在可行域范圍內(nèi)。（3，2）點盡管在可行域內(nèi)，但沒有使目標(biāo)達(dá)到極大化。（4，1）使目標(biāo)函數(shù)達(dá)到最大，即z＝14。二、整數(shù)規(guī)劃數(shù)學(xué)模型的一般形式由上述例子可得出整數(shù)規(guī)劃數(shù)學(xué)模型的一般形式：

Maxz=CXAX=bX≥0,且為整數(shù)或部分為整數(shù)若稱該整數(shù)規(guī)劃問題為原問題，則線性規(guī)劃問題：

Maxz=CXAX=bX≥0為原問題對應(yīng)的松馳問題（LPRelaxation)。顯然，原問題與松弛問題有如下關(guān)系：松弛問題可行域包含原問題可行域；若兩者都有最優(yōu)解，則松弛問題最優(yōu)解大于原問題最優(yōu)解；若松弛問題最優(yōu)解為整數(shù)解，則該最優(yōu)解就是原問題最優(yōu)解。整數(shù)規(guī)劃常用的解法有分枝定界法和割平面法，它們適用于解純整數(shù)規(guī)劃問題和混合整數(shù)規(guī)劃問題。

一、分枝定界法（1）基本思想（2）基本原理二、割平面法（1）基本思想（2）基本原理三、整數(shù)規(guī)劃的計算機(jī)解法

計算機(jī)求解舉例第二節(jié)整數(shù)規(guī)劃的解法第三節(jié)0－1整數(shù)規(guī)劃

一、0－1整數(shù)規(guī)劃模型0－1整數(shù)規(guī)劃在實際中應(yīng)用較多。因為實際問題中經(jīng)常碰到大量的決策問題，要求回答“是－否”或“有－無”問題，這類問題可以借助整數(shù)規(guī)劃中的0－1整數(shù)變量，使許多復(fù)雜的、困難的問題相對變得簡單。0－1變量一般可表示為：0－1整數(shù)規(guī)劃的數(shù)學(xué)模型可表示為：第三節(jié)0－1整數(shù)規(guī)劃二、0－1整數(shù)規(guī)劃求解0－1整數(shù)規(guī)劃的求解方法有窮舉法、隱枚舉法和分枝定界法.隱枚舉法求解舉例解：（1）先用試探的方法找出一個初始可行解，如x1＝x2＝0，x3＝1。滿足約束條件，選其作為初始可行解，目標(biāo)函數(shù)z0＝2。（2）附加過濾條件以目標(biāo)函數(shù)作為過濾約束：4x1＋3x2＋2x3>=2原模型變?yōu)椋海?）求解求解過程如表4－6所示。點過濾條件約束z值④①②③

4x1＋3x2＋2x3≥2

（0，0，0）T

×

（0，0，1）T

√√√√2（0，1，0）T

√√×

（0，1，1）T

√√√√5

4x1＋3x2＋2x3≥5

（1，0，0）T

×

（1，0，1）T

√×

（1，1，0）T

√√√√7

4x1＋3x2＋2x3≥7

（1，1，1）T

√√√√9一、相互排斥的計劃(Mutuallyexclusiveplanning)例4.6某公司擬在市東、西、南三區(qū)中建立門市部，有例7個點Ai（i＝1，2，…，7）可供選擇，要求滿足以下條件：1)在東區(qū)，在A1，A2，A3三個點中至多選兩個；2)在西區(qū)，A4，A5兩個點中至少選一個；3)在南區(qū)，A6，A7兩個點為互斥點。4)選A2點必選A5點。若Ai點投資為bi萬元，每年可獲利潤為ci萬元，投資總額為B萬元，試建立利潤最大化的0－1規(guī)劃模型。第四節(jié)0－1整數(shù)規(guī)劃應(yīng)用(Applications)解：設(shè)決策變量為建立0－1規(guī)劃模型如下：例4.7某產(chǎn)品有A1和A2兩種型號，需要經(jīng)過B1、B2、B3三道工序，單位工時和利潤、各工序每周工時限制見表所示，問工廠如何安排生產(chǎn)，才能使總利潤最大？（B3工序有兩種加工方式B31和B32，產(chǎn)品為整數(shù)）。 二、互排斥的約束條件(Mutuallyexclusiveconstraints)

工序型號B1B2B3利潤（元/件）B31B32A1A20.30.70.20.10.30.50.20.42540每周工時(小時/月)250100150120解：設(shè)A1、A2產(chǎn)品的生產(chǎn)數(shù)量分別為x1、x2件，在不考慮B31和B32相互排斥的情況下，問題的數(shù)學(xué)模型為工序B3只能從兩種加工方式中選擇一種，那么約束條件（1）和（2）就成為相互排斥的約束條件。為了統(tǒng)一在一個問題中，引入0-1變量則數(shù)學(xué)模型為一般地，在建立數(shù)學(xué)模型時，若需從p個約束條件中選擇q個約束條件，則可以引入p個0-1變量那么約束條件組例4.8某公司制造小、中、大三種尺寸的容器，所需資源為金屬板、勞動力和機(jī)器設(shè)備，制造一個容器所需的各種資源的數(shù)量如下表所示：不考慮固定費用，小、中、大號容器每售出一個其利潤分別為4萬元、5萬元、6萬元，可使用的金屬板有500噸，勞動力有300人/月，機(jī)器有100臺/月，另外若生產(chǎn)，不管每種容器生產(chǎn)多少，都需要支付一筆固定費用：小號為100萬元，中號為150萬元，大號為200萬元。問如何制定生產(chǎn)計劃使獲得的利潤對大？三、固定成本問題(Fixedcostproblem)解：設(shè)x1、x2、x3分別為小號容器、中號容器、大號容器的生產(chǎn)數(shù)量。不考慮固定費用，則問題的數(shù)學(xué)模型為資源小號容器中號容器大號容器金屬板（噸）248勞動力（人/月）234機(jī)器設(shè)備（臺/月）123若考慮固定費用就必須引入0—1變量：則該問題的數(shù)學(xué)模型為例4.9某城市消防隊布點問題。該城市共有6個區(qū)，每個區(qū)都可以建消防站，市政府希望設(shè)置的消防站最少，但必須滿足在城市任何地區(qū)發(fā)生火警時，消防車要在15分鐘內(nèi)趕到現(xiàn)場。據(jù)實地測定，各區(qū)之間消防車行駛的時間見表4－9，請幫助該市制定一個布點最少的計劃。

地區(qū)1地區(qū)2地區(qū)3地區(qū)4地區(qū)5地區(qū)6地區(qū)101016282720地區(qū)210024321710地區(qū)316240122721地區(qū)428321201525地區(qū)527172715014地區(qū)620102125140四、布點問題(LocationProblem)表4－9消防車在各區(qū)間行駛時間表單位：min本問題的約束方程是要保證每個地區(qū)都有一個消防站在15分鐘行程內(nèi)。如地區(qū)1，由表4－9可知，在地區(qū)1及地區(qū)2內(nèi)設(shè)消防站都能達(dá)到此要求，即x1＋x2≥1因此本問題的數(shù)學(xué)模型為：

minz＝x1＋x2＋x3＋x4＋x5＋x6x1＋x2≥1x1＋x2＋x6≥1x3＋x4≥1x3＋x4＋x5≥1x4＋x5＋x6≥1x2＋x5＋x6≥1xi＝1或0（i＝1，…，6）解：引入0－1變量xi作決策變量，令資金預(yù)算（Capitalbudgetingproblem）冰冷電冰箱公司正在考慮4種投資方案，有關(guān)數(shù)據(jù)如下表。問題：選擇投資項目使總現(xiàn)值最大。五、其他案例（數(shù)據(jù)、模型與決策）冰冷電冰箱公司各投資項目現(xiàn)值估算、資金需求和4年內(nèi)的資產(chǎn)（單位：千美元）項目工廠擴(kuò)張倉庫擴(kuò)張新機(jī)器新產(chǎn)品研究總可用資金現(xiàn)值第1年資金第2年資金第3年資金第4年資金9015202015401015205101043715101010——40504035引入4個0-1變量：P=1，工廠擴(kuò)建通過；P=0，則不選工廠擴(kuò)建；W=1，倉庫擴(kuò)建通過；P=0，則不選倉庫擴(kuò)建；M=1，機(jī)器更新通過；P=0，則不選機(jī)器更新；R=1，新產(chǎn)品研究通過；P=0，則不選新產(chǎn)品研究；則問題的0-1規(guī)劃數(shù)學(xué)模型為：

MaxZ=90P+40W+10M+37R15P+10W+10M+15R≤4020P+15W+10R≤5020P+20W+10R≤4015P+5W+4M+10R≤50P，W，M，R=0，1案例固定成本（Fixedcostproblem）生產(chǎn)三種產(chǎn)品需要用三種原料，生產(chǎn)這些產(chǎn)品需要配置成本，若不需要，則無配置成本。有關(guān)數(shù)據(jù)如下表。問題：各產(chǎn)品應(yīng)生產(chǎn)多少總利潤最大。生產(chǎn)數(shù)據(jù)表添加劑溶劑清潔劑原料數(shù)量原料1原料2原料30.40.60.50.20.30.60.10.320521單位利潤($)403050配置費用($)20050400最大產(chǎn)量(t)502540設(shè)：F=添加劑生產(chǎn)量；S=溶劑生產(chǎn)量；C=清潔劑生產(chǎn)量；引入3個0-1變量：若生產(chǎn)添加劑，SF=1，否則SF=0；若生產(chǎn)溶劑，SS=1，否則SS=0；若生產(chǎn)清潔劑，SC=1，否則SC=0；則問題的0-1規(guī)劃數(shù)學(xué)模型為：

MaxZ=40F+30S+50C–200SF–50SS–400SC0.4F+0.5S+0.6C≤200.2S+0.1C≤50.6F+0.3S+0.3C≤21F-50SF≤0S-25SS≤0C-40SC≤0F,S,C≥0,SF,SS,SC=0,1案例分銷系統(tǒng)設(shè)計(Distributionsystemdesignproblem)馬丁貝克公司在圣路易斯經(jīng)營一家生產(chǎn)量為30000件產(chǎn)品的工廠。產(chǎn)品被運(yùn)輸?shù)轿挥诓ㄊ款D、亞特蘭大和休斯敦的地區(qū)分銷中心。由于預(yù)期將有需求增長,公司計劃在底特律、托來多、丹佛和堪薩斯中一個或多個城市建立新工廠以增加生產(chǎn)力。有關(guān)數(shù)據(jù)如下表。問題：各選擇哪個或哪些工廠使總成本最小。生產(chǎn)數(shù)據(jù)表分銷中心生產(chǎn)地1波士頓2亞特蘭大3休斯敦生產(chǎn)能力（千件）年固定成本(千$)1底特律2托來多3丹佛4堪薩斯5圣路易斯54910823744345231020304030175300375500需求量(千件)302020在不考慮固定成本和生產(chǎn)地選擇的情況下，此問題是一個運(yùn)輸問題.若用xij表示從產(chǎn)地i到分銷中心j的運(yùn)量,則其數(shù)學(xué)模型為：Minf=5x11+2x12+3x13+4x21+3x22+4x23+…+4x52+3x53x11+x12+x13≤10x21+x22+x23≤20x31+x32+x33≤30x41+x42+x43≤40x51+x52+x53≤30x11+x21+x31+x41+x51=30x12+x22+x32+x42+x52=20x13+x23+x33+x43+x53=20xij≥0,所有i,j若考慮固定成本和生產(chǎn)地的選擇需要引入0-1變量.若在底特律建立工廠,y1=1,否則y1=0;若在托來多建立工廠,y2=1,否則y2=0;若在丹佛建立工廠,y3=1,否則y3=0;若在堪薩斯建立工廠,y4=1,否則y4=0;若用xij表示從產(chǎn)地i到分銷中心j的運(yùn)量,則其數(shù)學(xué)模型為：minf=5x11+2x12+3x13+…+4x52+3x53+175y1+300y2+375y3+500y4x11+x12+x13-10y1≤0x21+x22+x23-20y2≤0x31+x32+x33-30y3≤0x41+x42+x43-40y4≤0x51+x52+x53≤30x11+x21+x31+x41+x51=30x12+x22+x32+x42+x52=20x13+x23+x33+x43+x53=20xij≥0,所有i,j;y1,y2,y3,y4=0,1案例銀行選址（Locationproblem）俄亥俄州信托投資公司的遠(yuǎn)期計劃正在考慮在俄亥俄州東北部20個郡的地區(qū)開展業(yè)務(wù).該投資公司目前在這20個郡還沒有主營業(yè)處.根據(jù)該州法律:如果一個銀行在任一個郡建立主營業(yè)處,即可在該郡及所有毗鄰郡建設(shè)分行.該計劃的第一步是：投資公司需要確定為了在這20個郡完全營業(yè)一共要建立的主營業(yè)處的最小數(shù)目.2019181787645911101314315122161

若在第i郡建立主營業(yè)處,則xi=1,否則xi=0這樣,目標(biāo)函數(shù)為:

minz=x1+x2+…+x20

每個郡要滿足一個約束條件:該郡或與該郡相毗鄰的郡中至少有一個需要建立主營業(yè)處.例如第10個郡有:x3+x9+x8+x11x10+x12+x13≥1因此,該問題的數(shù)學(xué)模型為:minz=x1+x2+…+x20x1+x2+x12+x16≥1(第1個郡)x1+x2+x3+x12+x16≥1(第2個郡)x2+x3+x4+x9+x10+x12+x13≥1(第3個郡)

......x11+x14+x19+x20≥1(第20個郡)

xi=0,1I=1,2,

…,20案例產(chǎn)品設(shè)計和市場份額的優(yōu)化（Productdesignandmarketshareoptimizationproblem）顧客面包皮奶酪調(diào)味品香腸口味顧客對現(xiàn)有品牌的效用薄厚意大利混合細(xì)滑橙塊果醬清談中等辣安東尼奧國王123456781111713212952752081719961582061112471714171191614316161730216231726714203025162614292515223016271162951223308101910122019352493683397079594758567258457158決策變量:xij=1,表示賽倫pizza在屬性j上選擇i,否則xij=0yk=1,顧客i選擇賽倫pizza,否則yk=0這樣,目標(biāo)函數(shù)為:選擇賽倫pizza的顧客數(shù)最大,即

maxz=y1+y2+y3+y4+y5+y6+y7+y8約束條件:(1)若果顧客i選擇賽倫,則他認(rèn)為賽倫的效用比他目前中意的品牌的效用還要大.例如第1個顧客,目前中意的pizza是安東尼奧,效用為52,因此:

11x11+2x21+6x12+7x22+3x13+17x23+26x14+27x24+8x34≥1+52y1(2)賽倫在每中屬性中只能選擇一種,即

x11+x21=1x12+x22=1x13+x23=1x14+x24+x34=1因此,該問題的數(shù)學(xué)模型為：

maxz=y1+y2+y3+y4+y5+y6+y7+y811x11+2x21+6x12+7x22+3x13+17x23+26x14+27x24+8x34≥1+52y111x11+7x21+15x12+17x22+16x13+26x23+14x14+1x24+10x34≥1+58y27x11+5x21+8x12+14x22+16x13+7x23+29x14+16x24+19x34≥1+56y313x11+20x21+20x12+17x22+17x13+14x23+25x14+29x24+10x34≥1+83y42x11+8x21+6x12+11x22+30x13+20x23+15x14+5x24+12x34≥1+58y512x11+17x21+11x12+9x22+2x13+30x23+22x14+12x24+20x34≥1+70y69x11+19x21+12x12+16x22+16x13+25x23+30x14+23x24+19x34≥1+79y75x11+9x21+4x12+14x22+23x13+16x23+16