數(shù)學(xué)實驗實驗報告

1、數(shù)學(xué)實驗實驗報告（2012年 4月8日）班級：數(shù)學(xué)系0902班學(xué)號 ：姓名：馬驍一、實驗問題1（指派問題）考慮指定n個人完成n項任務(wù)（每人單獨承擔(dān)一項任務(wù)），使所需的總完成時間（成本）盡可能短. 已知某指派問題的有關(guān)數(shù)據(jù)（每人完成各任務(wù)所需的時間）如下表所示，試建模并求解該指派問題。2（二次指派問題）某公司指派n個員工到n個城市工作（每個城市單獨一人），希望使所花費的總電話費用盡可能少。n個員工兩兩之間每個月通話的時間表示在下面的矩陣的上三角部分（因為通話的時間矩陣是對稱的，沒有必要寫出下三角部分），n個城市兩兩之間通話費率表示在下面的矩陣的下三角部分（同樣道理，因為通話的費率矩陣是對稱的，沒

2、有必要寫出上三角部分）. 試求解該二次指派問題。3、謝金星第四章課后習(xí)題第1或3題任選一題。二、問題的分析（涉及的理論知識、數(shù)學(xué)建模與求解的方法等）1)根據(jù)實際問題，建立數(shù)學(xué)優(yōu)化模型 2)根據(jù)優(yōu)化模型，利用LINGO 來求解模型。三、計算過程、結(jié)論和結(jié)果分析1. 模型：model:sets:m/1.4/;n/1.4/;link(m,n):a,x;endsetsmin=sum(link(i,j):x(i,j)*a(i,j);for(m(i):sum(n(j):a(i,j)=1);for(n(j):sum(m(i):a(i,j)=1);data:x=15 18 21 24 19 23 22 18

3、26 18 16 19 19 21 23 17;enddataend結(jié)果：Global optimal solution found. Objective value: 70.00000 Infeasibilities: 0. Total solver iterations: 7 Variable Value Reduced Cost A( 1, 1) 0. 0. A( 1, 2) 1. 0. A( 1, 3) 0. 5. A( 1, 4) 0. 10.00000 A( 2, 1) 1. 0. A( 2, 2) 0. 1. A( 2, 3) 0. 2. A( 2, 4) 0. 0. A( 3,

4、 1) 0. 11.00000 A( 3, 2) 0. 0. A( 3, 3) 1. 0. A( 3, 4) 0. 5. A( 4, 1) 0. 1. A( 4, 2) 0. 0. A( 4, 3) 0. 4. A( 4, 4) 1. 0. X( 1, 1) 15.00000 0. X( 1, 2) 18.00000 0. X( 1, 3) 21.00000 0. X( 1, 4) 24.00000 0. X( 2, 1) 19.00000 0. X( 2, 2) 23.00000 0. X( 2, 3) 22.00000 0. X( 2, 4) 18.00000 0. X( 3, 1) 26

5、.00000 0. X( 3, 2) 18.00000 0. X( 3, 3) 16.00000 0. X( 3, 4) 19.00000 0. X( 4, 1) 19.00000 0. X( 4, 2) 21.00000 0. X( 4, 3) 23.00000 0. X( 4, 4) 17.00000 0. Row Slack or Surplus Dual Price 1 70.00000 -1. 2 0. -14.00000 3 0. -18.00000 4 0. -14.00000 5 0. -17.00000 6 0. -1. 7 0. -4. 8 0. -2. 9 0. 0.第1

6、個人完成第2項，第2人完成第1項，第3人完成第3項，第4人完成第4項。最短時間為70. 2.模型： model:sets:pe/1,2,3,4,5/;ci/1,2,3,4,5/;lin(pe,ci):x;lin1(pe,pe):d;lin2(ci,ci):c;endsetsmin=sum(lin1(i,j):d(i,j)*sum(lin2(a,b):c(a,b)*x(a,i)*x(b,j);for(pe(m):sum(ci(n):x(m,n)=1);for(ci(n):sum(pe(m):x(m,n)=1);for(lin:bin(x);data:d=0 1 1 2 3 1 0 2 1 2 1

7、 2 0 1 2 2 1 1 0 1 3 2 2 1 0;c=0 5 2 4 1 5 0 3 0 2 2 3 0 0 0 4 0 0 0 5 1 2 0 5 0;enddata end 結(jié)果：Local optimal solution found. Objective value: 50.00000 Objective bound: 50.00000 Infeasibilities: 0. Extended solver steps: 18 Total solver iterations: 802 Variable Value Reduced Cost X( 1, 1) 0. 14.0000

8、0 X( 1, 2) 0. 0. X( 1, 3) 1. 5. X( 1, 4) 0. 0. X( 1, 5) 0. 6. X( 2, 1) 0. 16.00000 X( 2, 2) 0. 9. X( 2, 3) 0. 0. X( 2, 4) 1. 1. X( 2, 5) 0. 0. X( 3, 1) 0. 14.00000 X( 3, 2) 0. 6. X( 3, 3) 0. 0.E-08 X( 3, 4) 0. 0. X( 3, 5) 1. 0. X( 4, 1) 1. 7. X( 4, 2) 0. 0. X( 4, 3) 0. 5. X( 4, 4) 0. 6. X( 4, 5) 0.

9、14.00000 X( 5, 1) 0. 0. X( 5, 2) 1. 1. X( 5, 3) 0. 0. X( 5, 4) 0. 9. X( 5, 5) 0. 15.99998 D( 1, 1) 0. 0. D( 1, 2) 1. 0. D( 1, 3) 1. 0. D( 1, 4) 2. 0. D( 1, 5) 3. 0. D( 2, 1) 1. 0. D( 2, 2) 0. 0. D( 2, 3) 2. 0. D( 2, 4) 1. 0. D( 2, 5) 2. 0. D( 3, 1) 1. 0. D( 3, 2) 2. 0. D( 3, 3) 0. 0. D( 3, 4) 1. 0.

10、D( 3, 5) 2. 0. D( 4, 1) 2. 0. D( 4, 2) 1. 0. D( 4, 3) 1. 0. D( 4, 4) 0. 0. D( 4, 5) 1. 0. D( 5, 1) 3. 0. D( 5, 2) 2. 0. D( 5, 3) 2. 0. D( 5, 4) 1. 0. D( 5, 5) 0. 0. C( 1, 1) 0. 0. C( 1, 2) 5. 0. C( 1, 3) 2. 0. C( 1, 4) 4. 0. C( 1, 5) 1. 0. C( 2, 1) 5. 0. C( 2, 2) 0. 0. C( 2, 3) 3. 0. C( 2, 4) 0. 0.

11、C( 2, 5) 2. 0. C( 3, 1) 2. 0. C( 3, 2) 3. 0. C( 3, 3) 0. 0. C( 3, 4) 0. 0. C( 3, 5) 0. 0. C( 4, 1) 4. 0. C( 4, 2) 0. 0. C( 4, 3) 0. 0. C( 4, 4) 0. 0. C( 4, 5) 5. 0. C( 5, 1) 1. 0. C( 5, 2) 2. 0. C( 5, 3) 0. 0. C( 5, 4) 5. 0. C( 5, 5) 0. 0. Row Slack or Surplus Dual Price 1 50.00000 -1. 2 0. -10.0000

12、0 3 0. -6. 4 0. 8. 5 0. 0. 6 0. -0.E-05 7 0. -10.00000 8 0. -16.00000 9 0. -14.00000 10 0. -12.00000 11 0. -22.00000第一個人去第三個城市，第二個人去第四個城市，第三個人去第五個城市，第四個人去第一個城市，第五個人去第二個城市 ，最低費用50。 3. 模型：model: min=100*x1+100*x2+40*y1+40*y2+40*y3+40*y4+40*y5;x1+x2+y14;x1+x2+y1+y23;x1+x2+y1+y2+y34;x2+y1+y2+y3+y46;x1+y

13、2+y3+y4+y55;x1+x2+y3+y4+y56;x1+x2+y4+y58;x1+x2+y58;y1+y2+y3+y4+y53;gin(x1);gin(x2);gin(y1);gin(y2);gin(y3);gin(y4);gin(y5);endGlobal optimal solution found. Objective value: 820.0000 Objective bound: 820.0000 Infeasibilities: 0. Extended solver steps: 0 Total solver iterations: 46 Variable Value Red

14、uced Cost X1 3. 100.0000 X2 4. 100.0000 Y1 0. 40.00000 Y2 2. 40.00000 Y3 0. 40.00000 Y4 0. 40.00000 Y5 1. 40.00000 Row Slack or Surplus Dual Price 1 820.0000 -1. 2 3. 0. 3 6. 0. 4 5. 0. 5 0. 0. 6 1. 0. 7 2. 0. 8 0. 0. 9 0. 0. 10 0. 0.說明：該儲蓄雇用7名全時服務(wù)員，其中3名12：0013：00吃午餐，4名13：0014：00吃午餐；并在10：0014：00雇用2名

15、、13：0017：00雇用1名半時服務(wù)員，符合題目要求，且花費最少，為820元。第二問 y1+y2+y3+y4+y50;Global optimal solution found. Objective value: 560.0000 Objective bound: 560.0000 Infeasibilities: 0. Extended solver steps: 0 Total solver iterations: 2 Variable Value Reduced Cost X1 0. 100.0000 X2 0. 100.0000 Y1 6. 40.00000 Y2 0. 40.00000 Y3 0. 40.00000 Y4 0. 40.00000 Y5 8. 40.00000 Row Slack or Surplus Dual Price 1 560.0000 -1. 2 2. 0. 3 3. 0. 4 2. 0