北工大数学建模作业4--已通过考核

1、数学模型图论（组合优化）实验 基本实验1.设备更新问题某公司需要对一台已经使用了2年的机器确定今后4年(n=4)的最优更新策略.公司要求，用了6年的机器必须更新，购买一台新机器的价格是100万元，表4.1给出了该问题的数据，请给出设备的更新策略。解：根据题意可以设a, b, c, d为判断年度，用数字表示机器已经使用的时间，则有第1年：机器使用的情况可以表示为a2；第2年：若第1年机器不更新则情况表示成b3，若第一年机器更新则第二年应表示成b1；使用Lingo软件进行计算并取最优解，编程如下：model:sets: Nodes/a2, b3, b1, c4, c2, c1, d5, d3, d

2、2, d1, e6, e4, e3, e2, e1, f/; arcs (nodes, nodes)/ a2, b3 a2, b1 b3, c4 b3, c1 b1, c2 b1, c1 c4, d5 c4, d1 c2, d3 c2, d1 c1, d2 c1, d1 d5,e1 d5,e6 d3,e4 d3,e1 d2,e3 d2,e1 d1,e2 d1,e1 e6,f e4, f e3, f e2,f e1,f /: c, x;endsetsdata: c = 17.3 -20.2 15.7 -30.2 18.4 -0.2 13.8 -50.2 17.3 -20.2 18.4 -0.2

3、12.2 -70.2 15.7 -30.2 17.3 -20.2 18.4 -0.2 5 30 50 60 80; enddatan = size (nodes);max = sum(arcs: c * x);sum (arcs (i,j)| i #eq# 1 : x(i,j) = 1;for (nodes (i)| i #ne# 1 #and# i #ne# n: sum(arcs(i,j): x(i,j) - sum(arcs(j,i): x(j,i)=0);sum (arcs (j,i)| i #eq# n : x(j,i) = 1;for (arcs: bin(x);End得到结果如下

4、：Global optimal solution found. Objective value: 139.0000 Objective bound: 139.0000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 0 Variable Value Reduced Cost N 16.00000 0.000000 C (a2, b3) 17.30000 0.000000 C (a2, b1) -20.20000 0.000000 C (b3, c4) 15.70000 0.000000 C

5、(b3, c1) -30.20000 0.000000 C (b1, c2) 18.40000 0.000000 C (b1, c1) -0.2000000 0.000000 C (c4, d5) 13.80000 0.000000 C (c4, d1) -50.20000 0.000000 C (c2, d3) 17.30000 0.000000 C (c2, d1) -20.20000 0.000000 C (c1, d2) 18.40000 0.000000 C (c1, d1) -0.2000000 0.000000 C (d5, e1) 12.20000 0.000000 C (d5

6、, e6) -70.20000 0.000000 C (d3, e4) 15.70000 0.000000 C (d3, e1) -30.20000 0.000000 C (d2, e3) 17.30000 0.000000 C (d2, e1) -20.20000 0.000000 C (d1, e2) 18.40000 0.000000 C (d1, e1) -0.2000000 0.000000 C (e6, f) 5.000000 0.000000 C (e4, f) 30.00000 0.000000 C (e3, f) 50.00000 0.000000 C (e2, f) 60.

7、00000 0.000000 C (e1, f) 80.00000 0.000000 X (a2, b3) 1.000000 -17.30000 X (a2, b1) 0.000000 20.20000 X (b3, c4) 1.000000 -15.70000 X (b3, c1) 0.000000 30.20000 X (b1, c2) 0.000000 -18.40000 X (B1, c1) 0.000000 0.2000000 X (c4, d5) 1.000000 -13.80000 X (c4, d1) 0.000000 50.20000 X (c2, d3) 0.000000

8、-17.30000 X (c2, d1) 0.000000 20.20000 X (c1, d2) 0.000000 -18.40000 X (c1, d1) 0.000000 0.2000000 X (d5, e1) 1.000000 -12.20000 X (d5, e6) 0.000000 70.20000 X (d3, e4) 0.000000 -15.70000 X (d3, e1) 0.000000 30.20000 X (d2, e3) 0.000000 -17.30000 X (d2, e1) 0.000000 20.20000 X (d1, e2) 0.000000 -18.

9、40000 X (d1, e1) 0.000000 0.2000000 X (e6, f) 0.000000 -5.000000 X (e4, f) 0.000000 -30.00000 X (e3, f) 0.000000 -50.00000 X (e2, f) 0.000000 -60.00000 X (e1, f) 1.000000 -80.00000Row Slack or Surplus Dual Price 1 0.000000 0.000000 2 139.0000 1.000000 3 0.000000 0.000000 4 0.000000 0.000000 5 0.0000

10、00 0.000000 6 0.000000 0.000000 7 0.000000 0.000000 8 0.000000 0.000000 9 0.000000 0.000000 10 0.000000 0.000000 11 0.000000 0.000000 12 0.000000 0.000000 13 0.000000 0.000000 14 0.000000 0.000000 15 0.000000 0.000000 16 0.000000 0.000000 17 0.000000 0.000000 18 0.000000 0.000000分析结果容易得出最佳的路径为a2-b3-

11、c4-d5-e1-f，因此得出结论，设备的最优更新策略应该是使用5年。2. 运输问题有甲、乙和丙三个城市，每年分别需要煤炭320万吨、250万吨和350万吨，由A, B两个煤矿负责供应.已知煤矿年产量A为400万吨，B为450万吨，从两煤矿至各城市煤炭运价如表4.2所示.由于需求大于供应，经协商平衡，甲城市在必要时可少供应0-30万吨，乙城市需求量须全部满足，丙城市需求量不少于270万吨。试求将甲、乙两矿煤炭全部分配出去，满足上述条件又使总运费最低的调运方案。解：根据题意认为该问题是一个运输线性规划的典型问题。设甲、乙、丙三个城市的煤炭获取量（Customer）1, 2, 3；A、B两个煤矿的

12、煤炭贮存（Warehouse）表达为A, B；煤矿与各城市之间的煤炭运价为P，用x表示决策点。使用Lingo软件进行计算并取最优解，编程如下：Model:!2 Warehouse, 3 Customer Transportation Problem;sets: Warehouse / A, B/: Supply; Customer / 1, 2, 3/: Gain; Routes (Warehouse, Customer): c, x;Endsets! The objective;OBJ min = sum (Routes: c * x);! The supply constraints;fo

13、r (Warehouse (i): SUPsum (Customer (j): x (i,j) <= Supply(i);! The demand constraints;sum (warehouse (i): x (i, 1) >290;sum (warehouse (i): x (i, 1) <320;sum (warehouse (i): x (i, 2) =250;sum (warehouse (i): x (i, 3) >270;sum (warehouse (i): x (i, 3) >350;! Here are the parameters;dat

14、a: Supply = 400, 450; Gain = 320, 250, 380; c = 15, 18, 22,21, 25, 16;Enddataend 得到如下结果：Global optimal solution found. Objective value: 14650.00 Infeasibilities: 0.000000 Total solver iterations: 4Variable Value Reduced CostSUPPLY (A) 400.0000 0.000000SUPPLY (B) 450.0000 0.000000GAIN (1) 250.0000 0.

15、000000GAIN (2) 290.0000 0.000000GAIN (3) 310.0000 0.000000C (A, 1) 15.00000 0.000000C (A, 2) 18.00000 0.000000C (A, 3) 22.00000 0.000000C (B, 1) 21.00000 0.000000C (B, 2) 25.00000 0.000000C (B, 3) 16.00000 0.000000X (A, 1) 150.0000 0.000000X (A, 2) 250.0000 0.000000X (A, 3) 0.000000 12.00000X (B, 1)

16、 140.0000 0.000000X (B, 2) 0.000000 1.000000X (B, 3) 310.0000 0.000000因此得到结论：由A矿向甲乙丙三座城市的送矿量（万吨）为150、250、0；由B矿向甲乙丙三座城市的送矿量（万吨）为140、0、310，此时总运输费最小，为14650万元。3、生产计划与库存管理(1)某公司生产一种除臭剂，它在1至4季度的生产成本、生产量及订货量表4.3所示.如果除臭剂在生产当季没有交货，保管在仓库里除臭剂每盒每季度还需1元钱的储存费用。如果某个季度的货物供应量不足，则允许延期交货，延期交货的罚金是每盒每季度3元。请公司希望制定一个成本最低(

17、包括储存费用和罚金)的除臭剂的生产计划，问各季度应生产多少?(2)如果产品不允许延期交货，则公司考虑工人加班，已知加班生产出产品的成本要比原成本高出20%，且每季度加班最多生产2万盒.问:在这种情况下，将如何安排生产，使总成本最少?解：（1） 根据题意，将此问题转化为运输问题，将每季度的生产量看作是供方，将每季度的订货量看作是需求方，将不属于本季度供货的量视为其他季度运输过来的，那么具体思路作图如下：红色字样为第一季度运输每件费用，5+166+36+3×25+1×255+35+1×35+1×25+15季度2订货量季度3订货量季度4订货量季度1生产量季度2

18、生产量季度3生产量季度4生产量季度1订货量6+3×36+3×26+3×166+1红色字样为季度1生产向4个季度的运送量；绿色字样为季度2生产向4个季度的运送量；蓝色字样为季度2生产向4个季度的运送量；黑色字样为季度2生产向4个季度的运送量。列出配送供需表格：季度1需求季度2需求季度3需求季度4需求季度1配送单价（万元/万盒）5666季度2配送单价（万元/万盒）8567季度3配送单价（万元/万盒）12967季度4配送单价（万元/万盒）151296设Cij为从季度生产Ai到季度需求Bj的配送单价，Xij为从季度生产Ai到季度需求Bj的运输量，因此总的费用为：i=1mj

19、=1ncij xij第i个季度的运出量应该小于或等于该季度的生产量：j=1mxijai第j个季度的运入量应该等于该季度的需求量：i=1mxijbj根据此模型写出Lingo程序并求出最优解：Model:!4 Warehouse, 4 Customer Transportation Problem;sets: Warehouse /1.4/: a; Customer /1.4/: b; Routes (Warehouse, Customer): c, x;Endsets! Here are the parameters;data: a= 13, 15, 15, 13; b= 10, 14, 20,

20、 8; c = 5, 6, 7, 8, 8, 5, 6, 7, 12, 9, 6, 7, 15, 12, 9, 6;Enddata! The objective;OBJ min = sum (Routes: c * x);! The supply constraints;for (Warehouse (i): SUP sum (Customer (j): X (i,j)<= a(i);! The demand constraints;for (Customer (j): DEM sum (Warehouse (i): X (i,j)= b(j);end 得到如下结果：Global opt

21、imal solution found. Objective value: 294.0000 Infeasibilities: 0.000000 Total solver iterations: 7Variable Value Reduced CostA (1) 13.00000 0.000000A (2) 15.00000 0.000000A (3) 15.00000 0.000000A (4) 13.00000 0.000000B (1) 10.00000 0.000000B (2) 14.00000 0.000000B (3) 20.00000 0.000000B (4) 8.00000

22、0 0.000000C (1, 1) 5.000000 0.000000C (1, 2) 6.000000 0.000000C (1, 3) 7.000000 0.000000C (1, 4) 8.000000 0.000000C (2, 1) 8.000000 0.000000C (2, 2) 5.000000 0.000000C (2, 3) 6.000000 0.000000C (2, 4) 7.000000 0.000000C (3, 1) 12.00000 0.000000C (3, 2) 9.000000 0.000000C (3, 3) 6.000000 0.000000C (3

23、, 4) 7.000000 0.000000C (4, 1) 15.00000 0.000000C (4, 2) 12.00000 0.000000C (4, 3) 9.000000 0.000000C (4, 4) 6.000000 0.000000X (1, 1) 10.00000 0.000000X (1, 2) 3.000000 0.000000X (1, 3) 0.000000 0.000000X (1, 4) 0.000000 4.000000X (2, 1) 0.000000 4.000000X (2, 2) 11.00000 0.000000X (2, 3) 4.000000

24、0.000000X (2, 4) 0.000000 4.000000X (3, 1) 0.000000 8.000000X (3, 2) 0.000000 4.000000X (3, 3) 15.00000 0.000000X (3, 4) 0.000000 4.000000X (4, 1) 0.000000 8.000000X (4, 2) 0.000000 4.000000X (4, 3) 1.000000 0.000000X (4, 4) 8.000000 0.000000Row Slack or Surplus Dual PriceOBJ 294.0000 -1.000000SUP (

25、1) 0.000000 2.000000SUP (2) 0.000000 3.000000SUP (3) 0.000000 3.000000SUP (4) 4.000000 0.000000DEM (1) 0.000000 -7.000000DEM (2) 0.000000 -8.000000DEM (3) 0.000000 -9.000000DEM (4) 0.000000 -6.000000分析结果易知，最佳的方案为：第一季度生产14万盒，给出10万盒满足第一季度要求，库存3万盒，不拖欠；第二季度生产15万盒，给出11万盒，连同第一季度库存3万盒加起来为14万盒满足第二季度要求，库存4万盒

26、，不拖欠；第三季度生产15万盒，全部给出，连同第二季度库存4万盒加起来19万盒，拖欠1万盒；第四季度生产9万盒，还清第三季度拖欠1万盒，剩下8万盒满足第四季度需求。此方案下总成本最小，为294万元。（2） 分析题目，可以将工人加班的费用视为除本季生产外为接下来其他季度供应货物的费用。参考如下配送供需表格：季度1需求季度2需求季度3需求季度4需求季度1配送单价（万元/万盒）5666季度2配送单价（万元/万盒）-566季度3配送单价（万元/万盒）-67.2季度4配送单价（万元/万盒）-6对于Lingo程序的改变，只需将每季度生产量扩充为+2万盒即可，对于表格中午单价的位置，使用极大数105来表示无

27、穷大，根据此模型写出Lingo程序并求出最优解：Model:!4 Warehouse, 4 Customer Transportation Problem;sets: Warehouse /1.4/: a; Customer /1.4/: b; Routes (Warehouse, Customer): c, x;Endsets! Here are the parameters;data: a= 15, 17, 17, 15; b= 10, 14, 20, 8; c = 5, 6, 6, 6, 100000, 5, 6, 6, 1000000, 1000000, 6, 7.2, 1000000

28、, 1000000, 1000000, 6;Enddata! The objective;OBJ min = sum (Routes: c * x);! The supply constraints;for (Warehouse (i): SUP sum (Customer (j): X (i,j)<= a(i);! The demand constraints;for (Customer (j): DEM sum (Warehouse (i): x (i,j)= b(j);end 得到如下结果： Global optimal solution found. Objective valu

29、e: 288.0000 Infeasibilities: 0.000000 Total solver iterations: 8Variable Value Reduced CostA (1) 15.00000 0.000000A (2) 17.00000 0.000000A (3) 17.00000 0.000000A (4) 15.00000 0.000000B (1) 10.00000 0.000000B (2) 14.00000 0.000000B (3) 20.00000 0.000000B (4) 8.000000 0.000000C (1, 1) 5.000000 0.00000

30、0C (1, 2) 6.000000 0.000000C (1, 3) 6.000000 0.000000C (1, 4) 6.000000 0.000000C (2, 1) 100000.0 0.000000C (2, 2) 5.000000 0.000000C (2, 3) 6.000000 0.000000C (2, 4) 6.000000 0.000000C (3, 1) 1000000 0.000000C (3, 2) 1000000 0.000000C (3, 3) 6.000000 0.000000C (3, 4) 7.200000 0.000000C (4, 1) 100000

31、0 0.000000C (4, 2) 1000000 0.000000C (4, 3) 1000000 0.000000C (4, 4) 6.000000 0.000000X (1, 1) 10.00000 0.000000X (1, 2) 0.000000 1.000000X (1, 3) 0.000000 0.000000X (1, 4) 5.000000 0.000000X (2, 1) 0.000000 99995.00X (2, 2) 14.00000 0.000000X (2, 3) 3.000000 0.000000X (2, 4) 0.000000 0.000000X (3,

32、1) 0.000000 999995.0X (3, 2) 0.000000 999995.0X (3, 3) 17.00000 0.000000X (3, 4) 0.000000 1.200000X (4, 1) 0.000000 999995.0X (4, 2) 0.000000 999995.0X (4, 3) 0.000000 999994.0X (4, 4) 3.000000 0.000000Row Slack or Surplus Dual PriceOBJ 288.0000 -1.000000SUP (1) 0.000000 0.000000SUP (2) 0.000000 0.0

33、00000SUP (3) 0.000000 0.000000SUP (4) 12.00000 0.000000DEM( 1) 0.000000 -5.000000DEM( 2) 0.000000 -5.000000DEM( 3) 0.000000 -6.000000DEM( 4) 0.000000 -6.000000分析结果，得到最优生产方案：第一季度生产15万盒（2万盒为加班产出），10万盒给出，满足第一季度需求，剩下5万盒库存至第四季度；第二季度生产17万盒（2万盒为加班产出），14万盒给出，满足第二季度需求，剩下3万盒库存至第三季度；第三季度生产17万盒（2万盒为加班产出），连同第二季度

34、库存共计20万盒给出，满足第三季度需求；第四季度生产3万，盒连同第一季度库存5万盒共计8万盒给出，满足第四季度要求。此时可以将成本控制到最少288万元。4. 指派问题某公司需要把4项工作派给4名工人，每名工人完成每项工作的费用如表4.4所示，其中工人甲不能完成工作C，工人丙不能完成工作D。(1) 确定每名工人完成工作的最优方案；(2) 假设有另外一名工人（戊）能完成这4项工作，完成每项工作相应费用分别为60、45、30和80元。是否用这名新工人（戊）替换原来的某位工人？(3) 假设公司有了第5项工作(E)，4名工人（甲、乙、丙、丁）完成工作E的费用分别为20、10、20和80元。这项新工作E比

35、原有的四项工作(A, B, C, D)的某一项优先吗？解：（1）根据题意，此题属于最优指派问题，引入如下变量：设变量为Xij,表示第i个人做第j项工作时，Xij=1，否则Xij=0。因此，相应的线性规划问题为：min=i=1nj=1ncijxij限制条件为：j=1nxij=1i=1, 2, , n, （每个人做一项工作）i=1nxij=1j=1,2, n （每项工作有一个人去做）xij=0或1 i, j=1, 2, , n对于不能工作的情况取一个极大数代替之即可。根据此模型写出Lingo程序并求出最优解：model: !4个工人，4个工作的分配问题;sets: Workers/w1.w4/;

36、Jobs/j1.j4/; links (workers, jobs): cost, volume;endsets !目标函数; min=sum (links: cost*volume); !每个工人只能有一份工作; for (workers (I) : sum (jobs (J): volume (I, J) =1; ); !每份工作只能有一个工人; for (jobs (J) : sum (workers(I): volume(I,J)=1; );data: cost= 50 50 100000 20 70 40 20 30 90 30 50 100000 70 20 60 70;endda

37、taend得到如下结果：Objective value: 140.0000Infeasibilities: 0.000000Total solver iterations: 8Variable Value Reduced CostCOST (W1, J1) 50.00000 0.000000COST (W1, J2) 50.00000 0.000000COST (W1, J3) 100000.0 0.000000COST (W1, J4) 20.00000 0.000000COST (W2, J1) 70.00000 0.000000COST (W2, J2) 40.00000 0.00000

38、0COST (W2, J3) 20.00000 0.000000COST (W2, J4) 30.00000 0.000000COST (W3, J1) 90.00000 0.000000COST (W3, J2) 30.00000 0.000000COST (W3, J3) 50.00000 0.000000COST (W3, J4) 100000.0 0.000000COST (W4, J1) 70.00000 0.000000COST (W4, J2) 20.00000 0.000000COST (W4, J3) 60.00000 0.000000COST (W4, J4) 70.000

39、00 0.000000VOLUME (W1, J1) 0.000000 0.000000VOLUME (W1, J2) 0.000000 50.00000VOLUME (W1, J3) 0.000000 99990.00VOLUME (W1, J4) 1.000000 0.000000VOLUME (W2, J1) 0.000000 10.00000VOLUME (W2, J2) 0.000000 30.00000VOLUME (W2, J3) 1.000000 0.000000VOLUME (W2, J4) 0.000000 0.000000VOLUME (W3, J1) 0.000000 10.00000VOLUME (W3