《图论(组合优化)实验资料》由会员分享，可在线阅读，更多相关《图论(组合优化)实验资料（45页珍藏版）》请在金锄头文库上搜索。
1、工程数学 4.图论(组合优化)实验 Gxxxxxxxxxxxxxxx xxxxxx工程数学Gxxxxxxxxx xxxxxxE-mail: xxxxxxxxxxxxxxx Tel: xxxxxxxxxx4 数学建模基础：1.2.3.4.4.1. 实验目的与要求l 学会用图论（组合优化）的方法或思想建模l 学会LINGO软件求解组合优化问题l 建立相应的数学模型，并对计算结果进行分析讨论4.2. 基本实验4.2.1. 设备更新问题某公司需要对一台已经使用了2年的机器确定今后4年（n=4）的最优更新策略。公司要求，用了6年的机器必须更新，购买一台新机器的价格是100万元，表4.1给出了该问题的数据
2、，请给出设备的更新策略。解：用图论知识来理解此题。设用A,B表示决策年度，用数字表示机龄，因此，第1年决策的节点就是A2，第2年只有两种可能，就是B3（第1年不更新）或B1(第1年更新)，以此类推。则得出Lingo的程序：sets: nodes/A2, B3, B1, C4, C2, C1, D5, D3, D2, 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,E
3、1 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 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#
4、 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);则得出程序运行结果：(取非零的x结果)分析结果：A2-B3-C4-D5-E1-F，得知设备应该是使用5年后再更新设备，为最优更新策略。4.2.2. 运输问题有甲、乙和丙三个城市，每年分别需要煤炭320万吨、250万吨和350万吨，由A, B两个煤矿负责供应。已知煤矿年产量A为400万吨，B为450万吨，从两煤矿至各城市煤炭运价如表4.2所示。由于需求大于
5、供应，经协商平衡，甲城市在必要时可少供应0-30万吨，乙城市需求量须全部满足，丙城市需求量不少于270万吨。试求将甲、乙两矿煤炭全部分配出去，满足上述条件又使总运费最低的调运方案。解：sets: From / A, B/: Capacity; To / C1, C2, C3/: Demand; Routes( From, To): D, x;endsets! The objective;OBJ min = sum(Routes: D * x);! The supply constraints;for (From(i): SUP sum (To(j): x(i,j) = Demand(j);!
6、Here are the parameters;data: Capacity = 400, 450 ; Demand = 320, 250, 380 ; D = 15, 18, 22, 21, 25, 16;Enddata程序运行结果如下：（1）甲甲乙丙丙销量A1515192222400B2121251616450CM0MM070运量2903025027080（2）甲甲乙丙丙销量VjA1515182222400-6B21212516164500CM0MM070-16产量2903025027080Ui2121241616（3）甲甲乙丙丙销量A1515192222400B2121251616450
7、CM0MM070运量2903025027080（4）甲甲乙丙丙销量VjA1515182222400-6B21212516164500CM30MM070-16产量2903025027080Ui2116241616结论：调整后最优方案的最低费用：150*15+250*18+140*21+270*16+40*16+30*0+40*0=14650万元4.2.3. 生产计划与库存管理(1)某公司生产一种除臭剂，它在1至4季度的生产成本、生产量及订货量表4.3所示。如果除臭剂在生产当季没有交货，保管在仓库里除臭剂每盒每季度还需1元钱的储存费用。如果某个季度的货物供应量不足，则允许延期交货，延期交货的罚金是
8、每盒每季度3元。请公司希望制定一个成本最低(包括储存费用和罚金)的除臭剂的生产计划，问各季度应生产多少?(2)如果产品不允许延期交货，则公司考虑工人加班，已知加班生产出产品的成本要比原成本高出20%，且每季度加班最多生产2万盒。问：在这种情况下，将如何安排生产，使总成本最少?解：(1) 设第一季度、第二季度、第三季度、第四季度生产量分别为a、b、c、d，a1为第一季度后剩余量，b1为第二季度后剩余量，c1为第三季度后剩余量，d1为第四季度后的剩余量。每季度的生产的除臭剂应该小于等于最大产量，大于等于订货量，第一个季度以为的季度中实际货物量应该等于上月的剩余量加该月的产量，以此类推，可以得出；L
9、INGO的程序：model:min=5*a+5*b+6*c+6*d+ya1+b1+c1+d1;a=10;a=14;b=20;c=8;d=13;d1=d+c1-8;end程序运行结果如下：第一个季度应生产14万盒，第二季度应该生产15万盒，第三季度应该生产15万盒，第四季度应该生产8万盒除臭剂。最低费用为288万元。（2）第1季度加班生产的产品为y1盒，第2季度加班生产的产品为y2盒，第3季度加班生产的产品为y3盒，第4季度加班生产的产品为y3盒，LINGO的程序：Model:min=8*a+9*y1+7*b+8*y2+7*c+8.2*y3+6*d+7.2*y4-78;a+y1+b+y2+c+y
10、3+d+y4=52;a=10;b=24;c=44;d=13;End Lingo程序运行结果：Lingo运行结果可得：安排生产：第一季度正常生产13万盒，不加班生产；第二季度正常生产15万，加班生产1万盒；第三季度正常生产15万，不加班生产；第四季度生产8万盒，不加班生产。总成本最少为292万元。4.2.4. 指派问题某公司需要把4项工作派给4名工人，每名工人完成每项工作的费用如表4.4所示，其中甲不能完成工作C，丙不能完成工作D。（1）确定每名工人完成工作的最优方案；（2）假设有另外一名工人（戊）能完成这4项工作，完成每项工作相应费用分别为60、45、30和80元。是否用这名新工人（戊）替换原
11、来的某位工人？（3）假设公司有了第5项工作（E），4名工人（甲、乙、丙、丁）完成工作E的费用分别为20、10、20和80元。这项新工作E比原有的四项工作（A，B，C，D）的某一项优先吗？解：根据题意分析方案。利用lingo的程序(不可能任务设成999，求min)sets: Flight/1.4/; Assign(Flight, Flight): c, x;endsetsdata: c = 50 50 999 20 70 40 20 30 90 30 50 999 70 20 60 70 ;enddatamin = sum(Assign: c*x);for(Flight(i): sum(Flig
12、ht(j): x(i,j) = 1; sum(Flight(j): x(j,i) = 1;);Lingo程序运行得： 最优方案：甲完成工作D， 乙完成C，丙完成B，丁完成A。总费用为140元（2） 根据题意增加一个工人（戊），设替换丙方案（且丁完成B任务）。Lingo的程序：sets: Flight/1.5/; Assign(Flight, Flight): c, x;endsetsdata: c = 50 50 999 20 999 70 40 20 30 999 90 30 50 999 999 70 20 60 70 999 60 45 30 80 999;enddatamin = sum(Assign: c*x);for(Flight(i): sum(Flight(j): x(i,j) = 1; sum(Flight(j): x(j,i) = 1;); Lingo程序运行得： 结论：1119-999=120, 费用减少120元。甲完成D，乙完成C，丙完成5（去掉），丁完成B，戊完成A。（3）Lingo的程序：
