整數(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)計劃應(yīng)作何改變？汽車廠生產(chǎn)三種類型的汽車，已知各類型每輛車對鋼材、勞動時間的需求，利潤及工廠每月的現(xiàn)有量.

小型中型大型現(xiàn)有量鋼材（t）1.535600勞動時間（h）28025040060000利潤（萬元）234

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

小型中型大型現(xiàn)有量鋼材1.535600時間28025040060000利潤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=629，與LP最優(yōu)值632.2581相差不大.2）試探：如取x1=65，x2=167；x1=64，x2=168等，計算函數(shù)值z，通過比較可能得到更優(yōu)的解.

但必須檢驗它們是否滿足約束條件.為什么？IP可用LINGO直接求解整數(shù)規(guī)劃(IntegerProgramming,簡記IP)IP的最優(yōu)解x1=64，x2=168，x3=0，最優(yōu)值z=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個子模型應(yīng)去掉，然后逐一求解，比較目標(biāo)函數(shù)值，再加上整數(shù)約束，得最優(yōu)解：方法1：分解為8個LP子模型汽車廠生產(chǎn)計劃

若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計劃.x1,x2,,x3=0或80x1=80，x2=150，x3=0，最優(yōu)值z=610LINGO中對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)計劃.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ī)劃的一般模型問題是如何求解整數(shù)規(guī)劃問題呢？能否設(shè)想先略去決策變量整數(shù)約束，即變?yōu)榫€性規(guī)劃問題求解，再對其最優(yōu)解進(jìn)行取整處理呢？實際上，可借鑒這種思想來解決整數(shù)規(guī)劃問題．112023年2月4日1.整數(shù)規(guī)劃求解的總基本思想

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

固定資源分配問題資源B1…Bj…Bm車間A1利潤：r11……………Ai……rij………An…………rnm價格a1…aj…am總量X1…Xj…Xm

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

固定資源分配問題

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、指派（或分配）問題三、0-1整數(shù)規(guī)劃

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

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

匈牙利算法的基本思想

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

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

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

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

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