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

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

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

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

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

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

小型中型大型現(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結果為小數(shù)，怎么辦？1）舍去小數(shù)：取x1=64，x2=167，算出目標函數(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結果輸出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個子模型應去掉，然后逐一求解，比較目標函數(shù)值，再加上整數(shù)約束，得最優(yōu)解：方法1：分解為8個LP子模型汽車廠生產計劃

若生產某類汽車，則至少生產80輛，求生產計劃.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

若生產某類汽車，則至少生產80輛，求生產計劃.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ù)約束，即變?yōu)榫€性規(guī)劃問題求解，再對其最優(yōu)解進行取整處理呢？實際上，可借鑒這種思想來解決整數(shù)規(guī)劃問題．112023年2月4日1.整數(shù)規(guī)劃求解的總基本思想

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

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

目標總利潤各車間、各資源利潤資源分配量決策變量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ī)劃

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

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

匈牙利算法的基本思想

因為每個指派問題都有一個相應的效益矩陣，通過初等變換修改效益矩陣的行或列，使得在每一行或列中至少有一個零元素，直到在不同行不同列中都至少有一個零元素為止。從而得到與這些零元素相對應的一個完全分配方案，這個方案對原問題而言是一個最優(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;開放時間內須有且僅有一名學生值班;規(guī)定大學生每周值班不少于8小時;研究生每周值班不少于7小時;每名學生每周值班不超3次;每次值班不少于2小時;每天安排值班的學生不超過3人，且其中必須有一名研究生.試為該實驗室安排一張人員的值班表，使總支付的報酬這最少。四、案例分析:兼職值班員問題

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

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