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

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

3、 3 5 600時間時間 280 250 400 60000利潤利潤 2 3 4 線性規劃線性規劃模型模型(LP)模型模型求解求解 3）模型中）模型中增加條件增加條件：x1, x2, x3 均為整數，重新求解均為整數，重新求解. . 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結果為小數，結果為小數，怎么辦？怎么辦？1）舍去小數舍去小數：取：取x1=64，x2=167，算出目標函數值，算出目標函數值 z=629，與，與LP最優值最優值632.2581相差不大相差不大.2）試探試探：如取：如取x1=65，x2=167；x1=64，x2=168等，等，計算函數值計算函數值z，通過比較可能得到更優的解，通過比較可能得到更優的解. 但但必須檢驗必須檢驗它們是否滿足約束條件它們是否滿足約束條件. 為什么？為什么？IP可用可用LINGO直接求解直接求解整數規劃整數規劃( (Integer Programming, ,簡記簡記IP) )IP 的最優解的最優解x1=

5、64，x2=168，x3=0，最優值最優值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為非負整數321,xxx模型求解模型

6、求解 IP 結果輸出結果輸出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個個子模型應子模型應去掉，然后去掉，然后逐一求解，比較目標函數值，逐一求解，比較目標函數值，再加上整數約束，得最優解：再加上整數約束，得最優解：80, 0, 0321xxx0,80, 0321xxx80,80, 0321xxx0, 0,80321xxx0,80,80321xxx80, 0,80321xxx80,80,80321xxx0

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

8、數為大的正數, ,本例可取本例可取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 若生產某類汽車，則至少生產若生產某類汽車，則至少生產8080輛，求生產計劃輛，求生產計劃. .x1=0 或 80 x2=0 或 80 x3=0 或 801 , 0,80,11111yy

9、xMyx1 , 0,80,22222yyxMyx1 , 0,80,33333yyxMyx最優解同前最優解同前 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); % 整數約束整數約束bin(y1); bin(y2); bin(y3); % 0-1變量變量end102022年3月22日 2. 整數規劃模型的一般形式整數規劃模型的一般形式 問題是如何求解整數規

10、劃問題呢？問題是如何求解整數規劃問題呢？能否設想先略去決策變量整數約束，即變為線性能否設想先略去決策變量整數約束，即變為線性規劃問題求解，再對其最優解進行取整處理呢？規劃問題求解，再對其最優解進行取整處理呢？實際上，可借鑒這種思想來解決整數規劃問題實際上，可借鑒這種思想來解決整數規劃問題112022年3月22日 1 .整數規劃求解的總基本思想整數規劃求解的總基本思想 122022年3月22日固定資源分配問題固定資源分配問題問問題題分分析析與與準準備備 資源B1BjBm車間A1利潤：r11AirijAnrnm價格a1ajam總量X1XjXm 目標目標總利潤總利潤 各車間、各資源利潤各車間、各資源

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

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

13、813141611415139問如何分配何問如何分配何人去完成何項人去完成何項目使完成目使完成4 4項項任務所需總時任務所需總時間最少？間最少？192022年3月22日每每個個人人去去完完成成一一項項任任務務的的約約束束為為 111144434241343332312423222114131211xxxxxxxxxxxxxxxx 202022年3月22日目目標標函函數數： 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日 匈牙利算法的基本思想匈牙利算法的基本思想 因為每個指派問題都有一個相應的效因為每個指派問題都有一個相應的效益矩陣，通過初等變換修改效益矩陣的行益矩陣，通過初等變換修改效益矩陣的行或列，使得在每一行或列中至少有一

15、個零或列，使得在每一行或列中至少有一個零元素，直到在不同行不同列中都至少有一元素，直到在不同行不同列中都至少有一個零元素為止。從而得到與這些零元素相個零元素為止。從而得到與這些零元素相對應的一個完全分配方案，這個方案對原對應的一個完全分配方案，這個方案對原問題而言是一個最優的分配方案。問題而言是一個最優的分配方案。252022年3月22日 用用LINGO求解求解0-1規劃模型規劃模型 4、0-1規劃的規劃的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日實驗室開放時間為上午實驗室開放時間為上午8:008:00至晚上至晚上10:00;10:00;開放時間內須有且僅有一名學生值班開放時間內須有且僅有一名學生值班; ;規定大學生每周值班不少于規定大學生每周值班不少于8 8小時小時; ;研究生每周值班不少于研究生每周值班不少于7 7小時小時; ;每名學生每周值班不超每名學生每周值班不超3 3次次; ;每次值班不少于每次值班不少于2 2小時小時; ;每天安排值班的學生不超過每天安排值班的學生不超過3 3人，且其中必須人，且其中必須有一名研究生有一名研究生. . 試

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