整數(shù)規(guī)劃模型

1、第5章 整數(shù)規(guī)劃（ILP、IP）模型,5.1 投資決策問題 5.2 背包問題 5.3 合理下料問題 5.4 生產(chǎn)組織與計劃問題 5.5 工廠選址問題 5.6 設(shè)備購置和安裝問題,5.1 投資決策問題,問題,某市在“十五” 期間有 b 億元資金可用于 n 個項目的投資。若對第 i 個項目投資，需資金 bi 億元，可獲利 ci 億元，試確定一個投資方案，使該市利稅收入最多。建數(shù)學(xué)模型,建模,令 若對第 i 個項目投資， 否則，,對第 i 個項目投資, 可獲利 ci 億元， 利稅達(dá)最大,對第 i 個項目投資, 需資金 bi 億元， 共有b 億元資金,ILP,0-1規(guī)劃,5.2 背包問題,問題,設(shè)有一

2、個容積為 b 的背包，有 n 個體積分別為 bi ，價值分別為 ci 的物品可以裝入背包，問應(yīng)選擇哪幾件物品裝入背包，才能得到最大的使用價值。建數(shù)學(xué)模型,建模,令 若裝第 i 件物品， 否則，,裝第 i 件物品，價值ci 使價值達(dá)最大,裝第 i 件物品，體積為 bi 共有容積為 b,ILP,與投資決策問題模型相同,0-1規(guī)劃,5.3 合理下料問題,問題,設(shè)要利用某類鋼板下m 種零件的毛料。已知在一塊鋼板上，已設(shè)計出 n 種不同的下料方案，設(shè)在第 j 種下料方案中，可下得第 i 種零件的個數(shù)為 aij ，第 i 種零件的需要量為 bi 。問應(yīng)如何下料，才能既滿足需要，又使所用鋼板總數(shù)最少。,建模

3、,鋼板總數(shù)達(dá)最小,第 i 種零件總數(shù)不少于bi,純整數(shù)規(guī)劃,設(shè)采用第 j 種方案下料的鋼板數(shù)為xj,5.4 生產(chǎn)組織與計劃問題,問題,某工廠用 m 臺機(jī)床：A1,A2,Am，加工 n 種零件：B1,B2,Bn 。在一個生產(chǎn)周期內(nèi)，已知第 i 臺機(jī)床Ai 只能工作ai 個機(jī)時。工廠必須完成加工零件Bj 的數(shù)量為bj 個。機(jī)床Ai 加工一個零件Bj 所需的機(jī)時和成本分別為 tij（機(jī)時/個）和cij（元/個）。問在這個生產(chǎn)周期，應(yīng)如何安排機(jī)床的生產(chǎn)任務(wù)，才能既完成加工任務(wù)，又使總的加工成本最小。,建模,機(jī)床Ai 加工各零件的機(jī)時 不超過Ai能工作的機(jī)時,各機(jī)床加工零件Bj 的數(shù)目 不少于Bj的需要

4、數(shù)量,純整數(shù)規(guī)劃,設(shè)機(jī)床Ai在一生產(chǎn)周期內(nèi)加工零件Bj的個數(shù)為xij,5.5 工廠選址問題,問題,設(shè)有 n 個需求點，有 m 個可供選擇的建廠地址。每個地址至多可建一個工廠。在 i 地址建立工廠的生產(chǎn)能力為Di,在 i 地址經(jīng)營工廠，單位時間的固定成本為ai （元）,需求點 j 的需求量為bj，從廠址i 到需求點 j 的單位運費為cij（元/t）。問應(yīng)如何選擇廠址和安排運輸計劃，才能得到經(jīng)濟(jì)上花費最少的方案。,建模,i 地址建工廠的生產(chǎn)能力Di,需求點 j 的需求量為bj,混合型整數(shù)規(guī)劃,設(shè)單位時間內(nèi)， 從廠址i 運往需求點 j 物資數(shù)量為xij 噸,5.6 設(shè)備購置和安裝問題,問題,某工廠需

5、要 m 種設(shè)備：A1,A2,Am，設(shè)Ai的單價為 pi元，該廠已有第 i 種設(shè)備ai臺。今有資金M元，可用于購置這些設(shè)備。該廠有n 處可安裝這些設(shè)備，Bj處最多能安裝 bj臺，將一臺設(shè)備Ai安裝在Bj處，經(jīng)濟(jì)效益為cij元，問應(yīng)如何購置和安裝這些設(shè)備，才能使總的經(jīng)濟(jì)效益最高。,建模,安裝的設(shè)備Ai數(shù)不超過 已有的和購置的臺數(shù)和,Bj處最多能安裝 bj臺,純整數(shù)規(guī)劃,設(shè)備Ai安裝在Bj處的臺數(shù)為xij ，yi 表示購置Ai的臺數(shù),有資金M元,整數(shù)規(guī)劃模型例題,例1 汽車廠生產(chǎn)計劃 例2 混合泳接力隊的選拔 例3 選課策略,如果生產(chǎn)某一類型汽車，則至少要生產(chǎn)80輛， 那么最優(yōu)的生產(chǎn)計劃應(yīng)作何改變？

6、,例1 汽車廠生產(chǎn)計劃,汽車廠生產(chǎn)三種類型的汽車，已知各類型每輛車對鋼材、勞動時間的需求，利潤及工廠每月的現(xiàn)有量。,制訂月生產(chǎn)計劃，使工廠的利潤最大。,設(shè)每月生產(chǎn)小、中、大型汽車的數(shù)量分別為x1, x2, x3,汽車廠生產(chǎn)計劃,模型建立,線性規(guī)劃模型(LP),模型求解,3） 模型中增加條件：x1, x2, x3 均為整數(shù)，重新求解。,OBJECTIVE FUNCTION VALUE 1) 632.2581 VARIABLE VALUE REDUCED COST X1 64.516129 0.000000 X2 167.741928 0.000000 X3 0.000000 0.946237 R

7、OW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 0.731183 3) 0.000000 0.003226,結(jié)果為小數(shù)，怎么辦？,1）舍去小數(shù)：取x1=64，x2=167，算出目標(biāo)函數(shù)值z=629，與LP最優(yōu)值632.2581相差不大。,2）試探：如取x1=65，x2=167；x1=64，x2=168等，計算函數(shù)值z，通過比較可能得到更優(yōu)的解。,但必須檢驗它們是否滿足約束條件。為什么？,IP可用LINDO直接求解,整數(shù)規(guī)劃(Integer Programming,簡記IP),“gin 3”表示“前3個變量為整數(shù)”，等價于： gin x1 gin x2 g

8、in x3,IP 的最優(yōu)解x1=64，x2=168，x3=0，最優(yōu)值z=632,max 2x1+3x2+4x3 st 1.5x1+3x2+5x3600 280 x1+250 x2+400 x360000 end gin 3,OBJECTIVE FUNCTION VALUE 1) 632.0000 VARIABLE VALUE REDUCED COST X1 64.000000 -2.000000 X2 168.000000 -3.000000 X3 0.000000 -4.000000,模型求解,IP 結(jié)果輸出,其中3個子模型應(yīng)去掉，然后逐一求解，比較目標(biāo)函數(shù)值，再加上整數(shù)約束，得最優(yōu)解：,方

9、法1：分解為8個LP子模型,汽車廠生產(chǎn)計劃,若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計劃。,x1,x2, x3=0 或 80,x1=80，x2= 150，x3=0，最優(yōu)值z=610,LINDO中對0-1變量的限定： int y1 int y2 int y3,方法2：引入0-1變量，化為整數(shù)規(guī)劃,M為大的正數(shù)，可取1000,OBJECTIVE FUNCTION VALUE 1) 610.0000 VARIABLE VALUE REDUCED COST X1 80.000000 -2.000000 X2 150.000000 -3.000000 X3 0.000000 -4.000000 Y1 1

10、.000000 0.000000 Y2 1.000000 0.000000 Y3 0.000000 0.000000,若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計劃。,x1=0 或 80,最優(yōu)解同前,NLP雖然可用現(xiàn)成的數(shù)學(xué)軟件求解(如LINGO, MATLAB)，但是其結(jié)果常依賴于初值的選擇。,方法3：化為非線性規(guī)劃,非線性規(guī)劃（Non- Linear Programming，簡記NLP）,實踐表明，本例僅當(dāng)初值非常接近上面方法算出的最優(yōu)解時，才能得到正確的結(jié)果。,若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計劃。,x1=0 或 80,丁的蛙泳成績退步到115”2；戊的自由泳成績進(jìn)步到57”5,

11、組成接力隊的方案是否應(yīng)該調(diào)整？,如何選拔隊員組成4100米混合泳接力隊?,例2 混合泳接力隊的選拔,5名候選人的百米成績,窮舉法：組成接力隊的方案共有5!=120種。,目標(biāo)函數(shù),若選擇隊員i參加泳姿j 的比賽，記xij=1, 否則記xij=0,0-1規(guī)劃模型,cij(秒)隊員i 第j 種泳姿的百米成績,約束條件,每人最多入選泳姿之一,每種泳姿有且只有1人,模型求解,最優(yōu)解：x14 = x21 = x32 = x43 = 1, 其它變量為0; 成績?yōu)?53.2(秒)=413”2,MIN 66.8x11+75.6x12+87x13+58.6x14 + +67.4x51+71 x52+83.8x53

12、+62.4x54 SUBJECT TO x11+x12+x13+x14 =1 x41+x42+x43+x44 =1 x11+x21+x31+x41+x51 =1 x14+x24+x34+x44+x54 =1 END INT 20,輸入LINDO求解,甲 自由泳、乙 蝶泳、丙 仰泳、丁 蛙泳.,丁蛙泳c43 =69.675.2，戊自由泳c54=62.4 57.5, 方案是否調(diào)整？,敏感性分析？,乙 蝶泳、丙 仰泳、丁 蛙泳、戊 自由泳,IP規(guī)劃一般沒有與LP規(guī)劃相類似的理論，LINDO輸出的敏感性分析結(jié)果通常是沒有意義的。,最優(yōu)解：x21 = x32 = x43 = x51 = 1, 成績?yōu)?1

13、7”7,c43, c54 的新數(shù)據(jù)重新輸入模型，用LINDO求解,指派(Assignment)問題：每項任務(wù)有且只有一人承擔(dān)，每人只能承擔(dān)一項，效益不同，怎樣分派使總效益最大.,討論,為了選修課程門數(shù)最少，應(yīng)學(xué)習(xí)哪些課程 ？,例3 選課策略,要求至少選兩門數(shù)學(xué)課、三門運籌學(xué)課和兩門計算機(jī)課,選修課程最少，且學(xué)分盡量多，應(yīng)學(xué)習(xí)哪些課程 ？,0-1規(guī)劃模型,決策變量,目標(biāo)函數(shù),xi=1 選修課號i 的課程（xi=0 不選）,選修課程總數(shù)最少,約束條件,最少2門數(shù)學(xué)課，3門運籌學(xué)課， 2門計算機(jī)課。,先修課程要求,最優(yōu)解： x1 = x2 = x3 = x6 = x7 = x9 =1, 其它為0；6門課程，總學(xué)分21,0-1規(guī)劃模型,約束條件,x3=1必有x1 = x2 =1,模型求解（LINDO）,學(xué)分最多,多目標(biāo)優(yōu)化的處理方法：化成單目標(biāo)優(yōu)化。,兩目標(biāo)(多目標(biāo))規(guī)劃,討論：選修課程最少，學(xué)分盡量多，應(yīng)學(xué)習(xí)哪些課程？,課程最少,以學(xué)分最多為目標(biāo)，不管課程多少。,以課程最少為目標(biāo)，不管學(xué)分多少。,多目標(biāo)規(guī)劃,在課程最少的前提下以學(xué)分最多為目標(biāo)。,最優(yōu)解： x1 = x2 = x3 = x5 = x7