整數(shù)規(guī)劃方法x

1、12022年3月22日 整數(shù)規(guī)劃的一般模型；整數(shù)規(guī)劃的一般模型； 整數(shù)規(guī)劃解的求解方法；整數(shù)規(guī)劃解的求解方法； 整數(shù)規(guī)劃的整數(shù)規(guī)劃的軟件求解方法；軟件求解方法； 0-10-1規(guī)劃的模型與求解方法；規(guī)劃的模型與求解方法； 整數(shù)規(guī)劃的應(yīng)用案例分析。整數(shù)規(guī)劃的應(yīng)用案例分析。 如果生產(chǎn)某一類型汽車，則至少要生產(chǎn)如果生產(chǎn)某一類型汽車，則至少要生產(chǎn)8080輛，輛， 那么最優(yōu)的生產(chǎn)計(jì)劃應(yīng)作何改變？那么最優(yōu)的生產(chǎn)計(jì)劃應(yīng)作何改變？汽車廠生產(chǎn)三種類型的汽車，已知各類型每輛車對汽車廠生產(chǎn)三種類型的汽車，已知各類型每輛車對鋼材、勞動時(shí)間的需求，利潤及工廠每月的現(xiàn)有量鋼材、勞動時(shí)間的需求，利潤及工廠每月的現(xiàn)有量. 小型

2、小型 中型中型 大型大型 現(xiàn)有量現(xiàn)有量鋼材（鋼材（t） 1.5 3 5 600勞動時(shí)間（勞動時(shí)間（h） 280 250 400 60000利潤（萬元）利潤（萬元） 2 3 4 制訂月生產(chǎn)計(jì)劃，使工廠的利潤最大制訂月生產(chǎn)計(jì)劃，使工廠的利潤最大.引例引例 汽車生產(chǎn)計(jì)劃汽車生產(chǎn)計(jì)劃設(shè)每月生產(chǎn)小、中、大型設(shè)每月生產(chǎn)小、中、大型汽車的數(shù)量分別為汽車的數(shù)量分別為x1, x2, x3321432maxxxxz600535 . 1t.s.321xxx60000400250280321xxx0,321xxx汽車廠生產(chǎn)計(jì)劃汽車廠生產(chǎn)計(jì)劃 模型建立模型建立 小型小型 中型中型 大型大型 現(xiàn)有量現(xiàn)有量鋼材鋼材 1.5

3、 3 5 600時(shí)間時(shí)間 280 250 400 60000利潤利潤 2 3 4 線性規(guī)劃線性規(guī)劃模型模型(LP)模型模型求解求解 3）模型中）模型中增加條件增加條件：x1, x2, x3 均為整數(shù)，重新求解均為整數(shù)，重新求解. . Objective Value: 632.2581 Variable Value Reduced Cost X1 64.516129 0.000000 X2 167.741928 0.000000 X3 0.000000 0.946237 Row Slack or Surplus Dual Price 2 0.000000 0.731183 3 0.000000

4、0.003226結(jié)果為小數(shù)，結(jié)果為小數(shù)，怎么辦？怎么辦？1）舍去小數(shù)舍去小數(shù)：?。喝1=64，x2=167，算出目標(biāo)函數(shù)值，算出目標(biāo)函數(shù)值 z=629，與，與LP最優(yōu)值最優(yōu)值632.2581相差不大相差不大.2）試探試探：如?。喝缛1=65，x2=167；x1=64，x2=168等，等，計(jì)算函數(shù)值計(jì)算函數(shù)值z，通過比較可能得到更優(yōu)的解，通過比較可能得到更優(yōu)的解. 但但必須檢驗(yàn)必須檢驗(yàn)它們是否滿足約束條件它們是否滿足約束條件. 為什么？為什么？IP可用可用LINGO直接求解直接求解整數(shù)規(guī)劃整數(shù)規(guī)劃( (Integer Programming, ,簡記簡記IP) )IP 的最優(yōu)解的最優(yōu)解x1=

5、64，x2=168，x3=0，最優(yōu)值最優(yōu)值z=632 Global optimal solution found. Objective value: 632.0000 Extended solver steps: 0 Total solver iterations: 3 Variable Value Reduced Cost X1 64.00000 -2.000000 X2 168.0000 -3.000000 X3 0.000000 -4.000000321432maxxxxz600535 . 1t.s.321xxx60000400250280321xxx為非負(fù)整數(shù)321,xxx模型求解模型

6、求解 IP 結(jié)果輸出結(jié)果輸出IP模型模型LINGO求解求解Model：max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3600;280*x1+250*x2+400*x360000;gin(x1);gin(x2);gin(x3);end其中其中3個(gè)個(gè)子模型應(yīng)子模型應(yīng)去掉，然后去掉，然后逐一求解，比較目標(biāo)函數(shù)值，逐一求解，比較目標(biāo)函數(shù)值，再加上整數(shù)約束，得最優(yōu)解：再加上整數(shù)約束，得最優(yōu)解：80, 0, 0321xxx0,80, 0321xxx80,80, 0321xxx0, 0,80321xxx0,80,80321xxx80, 0,80321xxx80,80,80321xxx0

7、,321xxx方法方法1：分解為：分解為8個(gè)個(gè)LP子模型子模型 汽車廠生產(chǎn)計(jì)劃汽車廠生產(chǎn)計(jì)劃 若生產(chǎn)某類汽車，則至少生產(chǎn)若生產(chǎn)某類汽車，則至少生產(chǎn)8080輛，求生產(chǎn)計(jì)劃輛，求生產(chǎn)計(jì)劃. .321432maxxxxz600535 . 1t.s.321xxx60000400250280321xxxx1, ,x2, x3=0 或或 80 x1=80，x2= 150，x3=0，最優(yōu)值，最優(yōu)值z=610LINGO中對中對0-1變量的限定：變量的限定： b i n ( y 1 ) ; b i n ( y 2 ) ; bin(y3);方法方法2：引入引入0-1變量，化為整數(shù)規(guī)劃變量，化為整數(shù)規(guī)劃 M為大的正

8、數(shù)為大的正數(shù), ,本例可取本例可取1000 Objective Value: 610.0000 Variable Value Reduced Cost X1 80.000000 -2.000000 X2 150.000000 -3.000000 X3 0.000000 -4.000000 Y1 1.000000 0.000000 Y2 1.000000 0.000000 Y3 0.000000 0.000000 若生產(chǎn)某類汽車，則至少生產(chǎn)若生產(chǎn)某類汽車，則至少生產(chǎn)8080輛，求生產(chǎn)計(jì)劃輛，求生產(chǎn)計(jì)劃. .x1=0 或 80 x2=0 或 80 x3=0 或 801 , 0,80,11111yy

9、xMyx1 , 0,80,22222yyxMyx1 , 0,80,33333yyxMyx最優(yōu)解同前最優(yōu)解同前 IP模型模型LINGO求解求解Model：max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3600;280*x1+250*x2+400*x360000;x180*y1; % 取取M=1000 x280*y2;x280*y2;gin(x1);gin(x2);gin(x3); % 整數(shù)約束整數(shù)約束bin(y1); bin(y2); bin(y3); % 0-1變量變量end102022年3月22日 2. 整數(shù)規(guī)劃模型的一般形式整數(shù)規(guī)劃模型的一般形式 問題是如何求解整數(shù)規(guī)

10、劃問題呢？問題是如何求解整數(shù)規(guī)劃問題呢？能否設(shè)想先略去決策變量整數(shù)約束，即變?yōu)榫€性能否設(shè)想先略去決策變量整數(shù)約束，即變?yōu)榫€性規(guī)劃問題求解，再對其最優(yōu)解進(jìn)行取整處理呢？規(guī)劃問題求解，再對其最優(yōu)解進(jìn)行取整處理呢？實(shí)際上，可借鑒這種思想來解決整數(shù)規(guī)劃問題實(shí)際上，可借鑒這種思想來解決整數(shù)規(guī)劃問題112022年3月22日 1 .整數(shù)規(guī)劃求解的總基本思想整數(shù)規(guī)劃求解的總基本思想 122022年3月22日固定資源分配問題固定資源分配問題問問題題分分析析與與準(zhǔn)準(zhǔn)備備 資源B1BjBm車間A1利潤：r11AirijAnrnm價(jià)格a1ajam總量X1XjXm 目標(biāo)目標(biāo)總利潤總利潤 各車間、各資源利潤各車間、各資源

11、利潤資源分配量資源分配量決策變量決策變量142022年3月22日 3、整數(shù)規(guī)劃的、整數(shù)規(guī)劃的LINGO解法解法152022年3月22日11min(1,2,)0,(1,2, )njjjnijjijjjzc xa xb imxxjn為整數(shù)162022年3月22日 1、0-1整數(shù)規(guī)劃的模型整數(shù)規(guī)劃的模型172022年3月22日 2、指派（或分配）問題、指派（或分配）問題 在生產(chǎn)管理上，總希望把人員最佳分派，在生產(chǎn)管理上，總希望把人員最佳分派，以發(fā)揮其最大工作效率，創(chuàng)造最大的價(jià)值。以發(fā)揮其最大工作效率，創(chuàng)造最大的價(jià)值。 例如：某部門有例如：某部門有n項(xiàng)任務(wù)，正好需要項(xiàng)任務(wù)，正好需要n個(gè)個(gè)人去完成，由于

12、任務(wù)的性質(zhì)和各人的專長不人去完成，由于任務(wù)的性質(zhì)和各人的專長不同，如果分配每個(gè)人僅能完成一項(xiàng)任務(wù)。同，如果分配每個(gè)人僅能完成一項(xiàng)任務(wù)。 如何分派使完成如何分派使完成n項(xiàng)任務(wù)的總效益為最高項(xiàng)任務(wù)的總效益為最高（效益量化），這是典型的分配問題。（效益量化），這是典型的分配問題。182022年3月22日 現(xiàn)在不妨設(shè)有現(xiàn)在不妨設(shè)有4 4個(gè)人，各有能力去完成個(gè)人，各有能力去完成4 4項(xiàng)科項(xiàng)科研任務(wù)中的任一項(xiàng)，由于研任務(wù)中的任一項(xiàng)，由于4 4個(gè)人的能力和經(jīng)驗(yàn)不個(gè)人的能力和經(jīng)驗(yàn)不同，所需完成各項(xiàng)任務(wù)的時(shí)間如右表：同，所需完成各項(xiàng)任務(wù)的時(shí)間如右表： 項(xiàng)項(xiàng)目目人人員員ABCD甲甲乙乙丙丙丁丁2109715414

13、813141611415139問如何分配何問如何分配何人去完成何項(xiàng)人去完成何項(xiàng)目使完成目使完成4 4項(xiàng)項(xiàng)任務(wù)所需總時(shí)任務(wù)所需總時(shí)間最少？間最少？192022年3月22日每每個(gè)個(gè)人人去去完完成成一一項(xiàng)項(xiàng)任任務(wù)務(wù)的的約約束束為為 111144434241343332312423222114131211xxxxxxxxxxxxxxxx 202022年3月22日目目標(biāo)標(biāo)函函數(shù)數(shù)： 444342413433323124232221141312119118713161491514410413152minxxxxxxxxxxxxxxxxz 212022年3月22日 )4, 3 ,2, 1,(1034,2,

14、1, 14, 3 ,2, 1, 14141jiorxjxixijijiijj 故故模模型型為為：ijijijxcz4141min 222022年3月22日指派問題的一般模型：指派問題的一般模型：232022年3月22日 ), 2, 1,(10, 2, 1, 1, 2, 1, 111njixnjxnixijniijnjij或指派問題的一般模型：指派問題的一般模型：242022年3月22日 匈牙利算法的基本思想匈牙利算法的基本思想 因?yàn)槊總€(gè)指派問題都有一個(gè)相應(yīng)的效因?yàn)槊總€(gè)指派問題都有一個(gè)相應(yīng)的效益矩陣，通過初等變換修改效益矩陣的行益矩陣，通過初等變換修改效益矩陣的行或列，使得在每一行或列中至少有一

15、個(gè)零或列，使得在每一行或列中至少有一個(gè)零元素，直到在不同行不同列中都至少有一元素，直到在不同行不同列中都至少有一個(gè)零元素為止。從而得到與這些零元素相個(gè)零元素為止。從而得到與這些零元素相對應(yīng)的一個(gè)完全分配方案，這個(gè)方案對原對應(yīng)的一個(gè)完全分配方案，這個(gè)方案對原問題而言是一個(gè)最優(yōu)的分配方案。問題而言是一個(gè)最優(yōu)的分配方案。252022年3月22日 用用LINGO求解求解0-1規(guī)劃模型規(guī)劃模型 4、0-1規(guī)劃的規(guī)劃的LINGO解法解法MODEL:MODEL: sets: sets: row/1.m/:b; arrange/1.n/:c,x; link(row,arrange):a; endsets da

16、ta: b=b(1),b(2),b(m); c=c(1),c(2),c(n); a=a(1,1),a(1,2),a(1,n), a(2,1),a(2,2),a(2,n), . . . . a(m,1),a(m,2),a(m,n); enddata OBJ min=sum(arrange(j):c(j)*x(j); for(row(i):sum(arrange(j):a(i,j)*x(j)=b(i);); for(arrange(j):x(j)=0;); for(arrange(j):BIN(x(j);); END 11min(1,2,)01(1,2, )njjjnijjijjzc xa xb

17、imxorjn262022年3月22日 1. 問題的提出問題的提出272022年3月22日實(shí)驗(yàn)室開放時(shí)間為上午實(shí)驗(yàn)室開放時(shí)間為上午8:008:00至晚上至晚上10:00;10:00;開放時(shí)間內(nèi)須有且僅有一名學(xué)生值班開放時(shí)間內(nèi)須有且僅有一名學(xué)生值班; ;規(guī)定大學(xué)生每周值班不少于規(guī)定大學(xué)生每周值班不少于8 8小時(shí)小時(shí); ;研究生每周值班不少于研究生每周值班不少于7 7小時(shí)小時(shí); ;每名學(xué)生每周值班不超每名學(xué)生每周值班不超3 3次次; ;每次值班不少于每次值班不少于2 2小時(shí)小時(shí); ;每天安排值班的學(xué)生不超過每天安排值班的學(xué)生不超過3 3人，且其中必須人，且其中必須有一名研究生有一名研究生. . 試

18、為該實(shí)驗(yàn)室安排一張人員的值班表，使總試為該實(shí)驗(yàn)室安排一張人員的值班表，使總支付的報(bào)酬這最少。支付的報(bào)酬這最少。 1. 問題的提出問題的提出282022年3月22日問題的分析問題的分析目標(biāo)目標(biāo) 總報(bào)酬總報(bào)酬 每人報(bào)酬每人報(bào)酬 每人值班時(shí)長每人值班時(shí)長每人每天值班時(shí)長每人每天值班時(shí)長 值班時(shí)刻表值班時(shí)刻表292022年3月22日 2. 模型的建立與求解模型的建立與求解302022年3月22日目標(biāo)目標(biāo)總報(bào)酬總報(bào)酬每人報(bào)酬每人報(bào)酬每人值班時(shí)長每人值班時(shí)長每人每天每人每天值班時(shí)長值班時(shí)長值班時(shí)刻表值班時(shí)刻表6711miniijijzc x312022年3月22日實(shí)驗(yàn)室開放時(shí)間為上午實(shí)驗(yàn)室開放時(shí)間為上午8:008:00至晚上至晚上10:00;10:00;開放時(shí)間內(nèi)須有且僅有一名學(xué)生值班開放時(shí)間內(nèi)須有且僅有一名學(xué)生值班;6114(1,2,7)ijixj322022年3月22日規(guī)定大學(xué)生每周值班不少于規(guī)定大學(xué)生每周值班不少于8小時(shí)小時(shí);718(1,2,3,4)ijjxi332022年3月22日717(5 6)ij