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

主要內(nèi)容整數(shù)規(guī)劃方法12023年2月4日整數(shù)規(guī)劃的一般模型；整數(shù)規(guī)劃解的求解方法；整數(shù)規(guī)劃的軟件求解方法；

0-1規(guī)劃的模型與求解方法；整數(shù)規(guī)劃的應(yīng)用案例分析。

如果生產(chǎn)某一類型汽車，則至少要生產(chǎn)80輛，那么最優(yōu)的生產(chǎn)計(jì)劃應(yīng)作何改變？汽車廠生產(chǎn)三種類型的汽車，已知各類型每輛車對(duì)鋼材、勞動(dòng)時(shí)間的需求，利潤(rùn)及工廠每月的現(xiàn)有量.

小型中型大型現(xiàn)有量鋼材（t）1.535600勞動(dòng)時(shí)間（h）28025040060000利潤(rùn)（萬(wàn)元）234

制訂月生產(chǎn)計(jì)劃，使工廠的利潤(rùn)最大.引例汽車生產(chǎn)計(jì)劃設(shè)每月生產(chǎn)小、中、大型汽車的數(shù)量分別為x1,x2,x3汽車廠生產(chǎn)計(jì)劃模型建立

小型中型大型現(xiàn)有量鋼材1.535600時(shí)間28025040060000利潤(rùn)234線性規(guī)劃模型(LP)模型求解

3）模型中增加條件：x1,x2,x3

均為整數(shù)，重新求解.

ObjectiveValue:632.2581VariableValueReducedCost

X164.5161290.000000

X2167.7419280.000000X30.0000000.946237RowSlackorSurplusDualPrice20.0000000.73118330.0000000.003226結(jié)果為小數(shù)，怎么辦？1）舍去小數(shù)：取x1=64，x2=167，算出目標(biāo)函數(shù)值z(mì)=629，與LP最優(yōu)值632.2581相差不大.2）試探：如取x1=65，x2=167；x1=64，x2=168等，計(jì)算函數(shù)值z(mì)，通過(guò)比較可能得到更優(yōu)的解.

但必須檢驗(yàn)它們是否滿足約束條件.為什么？IP可用LINGO直接求解整數(shù)規(guī)劃(IntegerProgramming,簡(jiǎn)記IP)IP的最優(yōu)解x1=64，x2=168，x3=0，最優(yōu)值z(mì)=632

Globaloptimalsolutionfound.

Objectivevalue:632.0000Extendedsolversteps:0Totalsolveriterations:3VariableValueReducedCost

X164.00000-2.000000

X2168.0000-3.000000

X30.000000-4.000000模型求解

IP結(jié)果輸出IP模型LINGO求解Model：max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3<600;280*x1+250*x2+400*x3<60000;@gin(x1);@gin(x2);@gin(x3);end其中3個(gè)子模型應(yīng)去掉，然后逐一求解，比較目標(biāo)函數(shù)值，再加上整數(shù)約束，得最優(yōu)解：方法1：分解為8個(gè)LP子模型汽車廠生產(chǎn)計(jì)劃

若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計(jì)劃.x1,x2,,x3=0或80x1=80，x2=150，x3=0，最優(yōu)值z(mì)=610LINGO中對(duì)0-1變量的限定：@bin(y1);@bin(y2);@bin(y3);方法2：引入0-1變量，化為整數(shù)規(guī)劃

M為大的正數(shù),本例可取1000ObjectiveValue:610.0000VariableValueReducedCost

X180.000000-2.000000

X2150.000000-3.000000

X30.000000-4.000000Y11.0000000.000000Y21.0000000.000000Y30.0000000.000000

若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計(jì)劃.x1=0或

80x2=0或

80x3=0或

80最優(yōu)解同前

IP模型LINGO求解Model：max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3<600;280*x1+250*x2+400*x3<60000;x1<1000*y1;x1>80*y1;%取M=1000x2<1000*y2;x2>80*y2;x2<1000*y2;x2>80*y2;@gin(x1);@gin(x2);@gin(x3);%整數(shù)約束@bin(y1);@bin(y2);@bin(y3);%0-1變量end102023年2月4日2.整數(shù)規(guī)劃模型的一般形式

一、整數(shù)規(guī)劃的一般模型問(wèn)題是如何求解整數(shù)規(guī)劃問(wèn)題呢？能否設(shè)想先略去決策變量整數(shù)約束，即變?yōu)榫€性規(guī)劃問(wèn)題求解，再對(duì)其最優(yōu)解進(jìn)行取整處理呢？實(shí)際上，可借鑒這種思想來(lái)解決整數(shù)規(guī)劃問(wèn)題．112023年2月4日1.整數(shù)規(guī)劃求解的總基本思想

二、整數(shù)規(guī)劃求解方法整數(shù)規(guī)劃模型示例122023年2月4日固定資源分配問(wèn)題問(wèn)題分析與準(zhǔn)備

固定資源分配問(wèn)題資源B1…Bj…Bm車間A1利潤(rùn)：r11……………Ai……rij………An…………rnm價(jià)格a1…aj…am總量X1…Xj…Xm

目標(biāo)總利潤(rùn)各車間、各資源利潤(rùn)資源分配量決策變量142023年2月4日

固定資源分配問(wèn)題

3、整數(shù)規(guī)劃的LINGO解法二、整數(shù)規(guī)劃的求解方法152023年2月4日162023年2月4日

1、0-1整數(shù)規(guī)劃的模型三、0-1整數(shù)規(guī)劃172023年2月4日

2、指派（或分配）問(wèn)題三、0-1整數(shù)規(guī)劃

在生產(chǎn)管理上，總希望把人員最佳分派，以發(fā)揮其最大工作效率，創(chuàng)造最大的價(jià)值。例如：某部門(mén)有n項(xiàng)任務(wù)，正好需要n個(gè)人去完成，由于任務(wù)的性質(zhì)和各人的專長(zhǎng)不同，如果分配每個(gè)人僅能完成一項(xiàng)任務(wù)。如何分派使完成n項(xiàng)任務(wù)的總效益為最高（效益量化），這是典型的分配問(wèn)題。2.指派（或分配）問(wèn)題182023年2月4日

現(xiàn)在不妨設(shè)有4個(gè)人，各有能力去完成4項(xiàng)科研任務(wù)中的任一項(xiàng)，由于4個(gè)人的能力和經(jīng)驗(yàn)不同，所需完成各項(xiàng)任務(wù)的時(shí)間如右表：?jiǎn)柸绾畏峙浜稳巳ネ瓿珊雾?xiàng)目使完成4項(xiàng)任務(wù)所需總時(shí)間最少？192023年2月4日2.指派（或分配）問(wèn)題202023年2月4日2.指派（或分配）問(wèn)題212023年2月4日2.指派（或分配）問(wèn)題222023年2月4日2.指派（或分配）問(wèn)題指派問(wèn)題的一般模型：232023年2月4日2.指派（或分配）問(wèn)題指派問(wèn)題的一般模型：242023年2月4日

匈牙利算法的基本思想

因?yàn)槊總€(gè)指派問(wèn)題都有一個(gè)相應(yīng)的效益矩陣，通過(guò)初等變換修改效益矩陣的行或列，使得在每一行或列中至少有一個(gè)零元素，直到在不同行不同列中都至少有一個(gè)零元素為止。從而得到與這些零元素相對(duì)應(yīng)的一個(gè)完全分配方案，這個(gè)方案對(duì)原問(wèn)題而言是一個(gè)最優(yōu)的分配方案。3.指派問(wèn)題的匈牙利算法252023年2月4日

用LINGO求解0-1規(guī)劃模型4、0-1規(guī)劃的LINGO解法262023年2月4日四、案例分析:兼職值班員問(wèn)題

1.問(wèn)題的提出272023年2月4日實(shí)驗(yàn)室開(kāi)放時(shí)間為上午8:00至晚上10:00;開(kāi)放時(shí)間內(nèi)須有且僅有一名學(xué)生值班;規(guī)定大學(xué)生每周值班不少于8小時(shí);研究生每周值班不少于7小時(shí);每名學(xué)生每周值班不超3次;每次值班不少于2小時(shí);每天安排值班的學(xué)生不超過(guò)3人，且其中必須有一名研究生.試為該實(shí)驗(yàn)室安排一張人員的值班表，使總支付的報(bào)酬這最少。四、案例分析:兼職值班員問(wèn)題

1.問(wèn)題的提出282023年2月4日四、案例分析:兼職值班員問(wèn)題問(wèn)題的分析目標(biāo)總報(bào)酬每人報(bào)酬每人值班時(shí)長(zhǎng)每人每天值班時(shí)長(zhǎng)值班時(shí)刻表292023年2月4日四、案例分析:兼職值班員問(wèn)題

2.模型的建立與求解302023年2月4日四、案例分析:兼職值班員問(wèn)題目標(biāo)總報(bào)酬每人報(bào)酬每人值班時(shí)長(zhǎng)每人每天值班時(shí)長(zhǎng)值班時(shí)刻表312023年2月4日四、案例分析:兼職值班員問(wèn)題實(shí)驗(yàn)室開(kāi)放時(shí)間為上午8:00至晚上10:00;開(kāi)放時(shí)間內(nèi)須有且僅有一名學(xué)生值班;322023年2月4日四、案例分析:兼職值班員問(wèn)題規(guī)定大學(xué)生每周值班不少于8小時(shí);332023年2月4日四、案例分析:兼職值班員問(wèn)題研