图论(组合优化实验)实验六

1、数学模型 实验六学号： 姓名： Email：1. 设备更新问题解：给出这个问题的网络表示：定义变量：在图中，横坐标表示决策年度，纵坐标表示机器年龄，K表示继续使用，R表示更新设备，S表示将剩余设备折旧，圆圈中的数为机龄，弧边的数字表示设备继续使用或更新所产生的价值（记为V），计算方法如下：模型分析：设，和表示某台k龄机器的年收入、运行费用和折旧现值，购买一台新机器的费用每年都是I，则每项决策所产生的价值为：为便于写程序，用A,B表示决策年度，用数字表示机龄，因此，第一年决策的节点就是A2，第二年只有两种可能，B3（第1年不更新）或B1（第1年更新），以此类推。在lingo中运行如下程序：set

2、s: 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,E6 D5,E1 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 -

3、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# 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

4、: bin(x);运行结果为：分析：A2B3C1D2E3F 即在今后的4年分别为继续使用、更新、继续使用、继续使用，最后折旧，可得最大利润为72.8万元。2. 运输问题解：（） 定义变量：设每单位运输费用为，运输量为。起点i的供应量为，终点j的需求量为，在程序中，用,代表A，两个煤矿，用，代表甲乙丙三个城市。（）分析模型：上题经协商后，甲乙丙三个城市分别最少获得煤炭量为万吨，万吨，万吨。这一模型的目标是确定未知量，在满足供应和需求的约束的情况下，使得运输总费用最小。由于在本题中，要将两个煤矿中的煤炭全部分配出去，总供应量全部用完，而需求量尽量满足，即总运费最低，可得模型如下：，在中运行程序如下

5、：sets: From / A1, A2/: Capacity; To / B1, B2, B3/: Demand; Routes( From, To): c, x;endsets! The objective;OBJ min = sum(Routes: c * x);! The supply constraints;for(From(i): SUP sum(To(j): x(i,j) = Capacity(i);! The demand constraints;for(To(j): DEM sum(From(i): x(i,j) >= Demand(j);! Here are the

6、parameters;data: Capacity = 400, 450; Demand = 290, 250, 270; c = 15, 18, 22, 21, 25, 16;enddata运行结果：分析结果：从矿运到甲、乙、丙三个城市的煤炭量分别为：万吨、万吨、万吨；从矿运到甲、乙、丙三个城市的煤炭量分别为：万吨、万吨、万吨。此时总运费最低为万元。.生产计划与库存管理解：（）定义变量：假设将生产分为个阶段，（按季度分），每个阶段的生产量为（,），订货量为（,），成本为，其中成本由由第个阶段的生产成本与第时间段的储存成本之和和第时间段延期罚金之和构成，设为第个阶段生产在第阶段交货的交货量。其

7、中蓝色表示只供应本季度的，黑色表示存储供应，红色表示延期供应。建立模型：，其中（）在中运行如下程序：sets: season / 1.4/: a, b; Routes(season, season): c, x;endsetsobj min = sum(Routes: c * x);for(season(i): SUP sum(season(j): x(i,j) <= a(i);for(season(j): DEM sum(season(i): x(i,j) = b(j);data: a = 13, 15, 15, 13; b = 10, 14, 20, 8; c = 5, 6, 7,

8、8, 8, 5, 6, 7, 12, 9, 6, 7, 15, 12, 9, 6;Enddata可得结果：分析结果可得：第一季度生产万盒，其中万盒本季度使用，万盒第二季度使用；第二季度生产万盒，其中万盒本季度使用，万盒第三季度使用；第三季度生产万盒，全部本季度使用；第四季度生产万盒，其中万盒第三季度使用，万盒本季度使用。（）定义变量：假设将生产分为个阶段，（按季度分），每个阶段的生产量为（,），订货量为（,），成本为，其中成本由由第个阶段的生产成本与第时间段的储存成本之和构成，设为第个阶段生产在第阶段交货的交货量；为第个阶段加班生产在第阶段交货的交货量（,，,），表示加班成本，为本季度供应成本

9、的数学模型：，（其中）在中运行程序如下：sets: season / 1.4/: a, b; Routes(season, season)|&1 #le# &2 : c, x,e,y;endsetsobj min = sum(Routes: c * x + e * y);for(season(i): SUP sum(season(j) | i #le# j: x(i,j) <= a(i);for(season(j): DEM sum(season(i) | i #le# j: x(i,j)+y(i,j) ) = b(j);for(season(i): sum(season

10、(j) | i #le# j: y(i,j) <= 2);data: a = 13, 15, 15, 13; b = 10, 14, 20, 8; c = 5, 6, 7, 8, 5, 6, 7, 6, 7, 6; e=6,7,8,9, 6,7,8, 7.2,8.2, 7.2;Enddata运行结果：分析结果可得：第一季度生产万盒，其中万盒本季度使用，万盒第二季度使用；第二季度生产万盒，其中加班生产万盒，其中万盒本季度使用，万盒第三季度使用；第三季度生产万盒，全部本季度使用；第四季度生产万盒，全部本季度使用。总共费用292万元。4. 指派问题解：（1）设置变量：设决策变量为，当第i个人做

11、第j项工作时，决策变量=1；否则，决策变量=0.因此，将最优指派问题写成0-1规划问题。 根据题意可得每个人完成且完成一项工作，即可得目标函数和约束条件：Min s.t. (每个人做一项工作) （每项工作有一个人去做） ，i，j=1,2,n在lingo中运行如下程序：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(F

12、light(j): x(i,j) = 1; sum(Flight(j): x(j,i) = 1;);for(Assign:bin(x);运行结果如下：即工人甲完成工作D，工人乙完成工作C，工人丙完成工作B，工人丁完成工作A。（2）变量设置同（1），根据题意可得，每项工作都有人完成，但不一定每个人都有工作可做。 故可得数学模型：Min s.t. (每个人不一定都有工作做) （每项工作有一个人去做） ，i，j=1,2,n在lingo中运行程序如下：sets: person /jia, yi, bing, ding, wu/; work /A, B, C, D/; assign( person, w

13、ork) : t, x;endsetsdata: t = 50 50 999 20 70 40 20 30 90 30 50 999 70 20 60 70 60 45 30 80; enddataOBJ min = sum( assign: t * x);for( person(i): P sum( work(j): x(i,j) <= 1);for( work(j): S sum( person(i): x(i,j) = 1);for(Assign:bin(x);运行结果：分析：即工人甲完成工作D，工人乙完成工作C，工人丁完成工作B，工人戊完成工作A。即用该新工人代替原来的工人丙。（

14、3）变量设置同（1），根据题意可得，每个人都有工作可做，但不一定每项工作都有人做。故建立数学模型：Min s.t. (每个人都有工作做) （每项工作不一定有人做） ，i，j=1,2,n在lingo中运行程序如下：sets: person /jia, yi, bing, ding/; work /A, B, C, D, E/; assign( person, work) : t, x;endsetsdata: t = 50 50 999 20 20 70 40 20 30 10 90 30 50 999 20 70 20 60 70 80; enddataOBJ min = sum( assig

15、n: t * x);for( person(i): P sum( work(j): x(i,j) = 1);for( work(j): S sum( person(i): x(i,j) <= 1);for(Assign:bin(x);运行结果如下：分析：即工人甲完成工作D，工人乙完成工作C，工人丙完成工作E，工人丁完成工作B。即这项工作E比原有的工作A优先。5.油画制造解：(1).设置变量：设有A,B,C,D,E这五批油画，表示使用第i种颜料后再转使用第j种颜料所需要的清洗时间，（2）根据题意，可得其线性（整数）规划模型的目标函数和约束条件为： Min s.t. (每批颜料i都会且只会转

16、换为另一种颜料) （每批颜料中只有一种会转换为j颜料） ， 在lingo中运行程序如下：sets: pen/A B C D E /: u; link(pen, pen): w, x;endsetsdata: !to: A B C D E ; w = 0 11 7 13 11 !from A; 5 0 13 15 15 !from B; 13 15 0 23 11 !from C; 9 13 5 0 3 !from D; 3 7 7 7 0 ;!from E;enddatan=size(pen);min = sum(link: w * x);for(pen(k): sum(pen(i)| i #

17、ne# k: x(i,k)=1; sum(pen(j)| j #ne# k: x(k,j)=1; );for(link(i,j)|i #gt# 1 #and# j #gt# 1 #and# i #ne# j: u(i)-u(j)+n*x(i,j)<=n-1;);for(link: bin(x);运行结果：分析结果：应采用如下顺序绘制这些批次的油画：143521 此时可用最少清洗时间为41分钟，由于要加上一周的最后一批油画与下周的第一批油画之间所需的清洗时间，即21为5分钟，故周期洗时间为46分钟。6最优连线问题解：（1）设置变量：建立最优连线问题的线性（整数）规划模型，假设表示城市i到城

18、市j之间的距离，决策变量定义为（2）根据题意，可得其线性（整数）规划模型的目标函数和约束条件为： Min s.t. （城市1是生成树的根，且至少有一条线路离开这座城市） （除城市1外，其他城市只有一条线路进入） （保证得到的子图不构成圈） ， 根据以上目标函数及约束条件，可知得到的树是最优生成树。在lingo中运行如下程序：sets: city/A B C D E F G H I J/: u; link(city, city): w, x;endsetsdata: !to: A B C D E F G H I J; w = 0 122 9359 9999 9999 9999 9999 9999

19、 9999 9999 !from A; 122 0 9999 345 167 9999 9999 9999 9999 9999 !from B; 359 9999 0 9999 180 9999 9999 195 246 9999!from C; 9999 345 9999 0 443 415 9999 9999 9999 9999 !from D; 9999 167 180 443 0 92 9999 9999 9999 9999 !from E; 9999 9999 9999 415 92 0 213 9999 9999 9999 !from F; 9999 9999 9999 9999

20、9999 213 0 79 199 163 !from G; 9999 9999 195 9999 9999 9999 79 0 9999 9999 !from H; 9999 9999 246 9999 9999 9999 199 9999 0 215 !from I; 9999 9999 9999 9999 9999 9999 163 9999 215 0;!from J;enddatamin = sum(link: w * x);sum(city(j)|j #gt# 1: x(1,j) >= 1;for(city(j)|j #gt# 1: sum( city(i)| i #ne#

21、j: x(i, j) = 1;);n=size(city);for(link(i,j)|i #ne# j: u(i)-u(j)+ n*x(i,j)<= n-1);for(link: bin(x);运行结果如下：分析结果可得这10个城市的最优连线为：7.最大流问题解：首先将题中的网络图转变为单源单汇问题，图如下：设置变量：设S为顶点的源，t的顶点为汇，既非源又非汇的顶点称为中间点，图中边上的数据为容量记为即建立数学模型： Max s.t. 在lingo中运行程序如下：sets: nodes/s,1,2,3,4,5,6,7,8,t/; arcs(nodes, nodes)/ s,1 s,2

22、s,3 1,4 2,4 2,5 2,6 3,5 4,5 4,6 4,7 5,6 5,8 6,7 6,8 7,t 8,t/: c, f;endsetsdata: c = 100 100 100 20 10 20 50 15 20 10 10 30 30 50 20 100 100;enddatamax = flow;sum(arcs(i,j)|i #eq# 1: f(i,j) = flow;for(nodes(i) | i #ne# 1 #and# i #ne# size(nodes): sum(arcs(i,j): f(i,j) - sum(arcs(j,i):f(j,i)=0);for(ar

23、cs: bnd(0, f, c);运行结果如下：分析结果：（） 炼油厂1：F(1，4)=20 百万桶/天炼油厂2：F(2，4)+ F(2，5)+ F(2，6)=5+20+50=75百万桶/天炼油厂3：F(3，5)=15 百万桶/天要满足这个网络的最大流量，炼油厂1每天的产量应该是20百万桶/天；炼油厂2每天的产量应该是75百万桶/天；炼油厂3每天的产量应该是15百万桶/天.（） 终端7：F(4，7)+F(6，7)= 10+50=60百万桶/天终端8：F(5，8)+F(6，8)= 30+20=50百万桶/天要满足这个网络的最大流量，终端7每天的需求量为60百万桶/天；终端8每天的需求量为50百万

24、桶/天.（） 泵站4：F(1，4)+ F(2，4)=20+5=25 百万桶/天泵站5：F(2，5)+ F(3，5)+F(4，5)=20+15+5=40 百万桶/天泵站6: F(2,6)+F(4,6)+F(5,6)=50+10+10=70百万桶/天要满足这个网络的最大流量,4泵站每天的最大容量为25百万桶/天；5泵站每天的最大容量为40百万桶/天；泵站每天的最大容量为70百万桶/天。（4） 如果把网络中泵站6每天的最大容量限制为50百万桶，即注入的总和不能超过50百万桶，表示在图中的限制条件为：在原来的程序中，加入限制条件，由于程序中将S点当做第一个点，故程序为：sets: nodes/s,1,

25、2,3,4,5,6,7,8,t/; arcs(nodes, nodes)/ s,1 s,2 s,3 1,4 2,4 2,5 2,6 3,5 4,5 4,6 4,7 5,6 5,8 6,7 6,8 7,t 8,t/: c, f;endsetsdata: c = 100 100 100 20 10 20 50 15 20 10 10 30 30 50 20 100 100;enddatamax = flow;sum(arcs(i,j)|i #eq# 1: f(i,j) = flow;for(nodes(i) | i #ne# 1 #and# i #ne# size(nodes): sum(arcs

26、(i,j): f(i,j) - sum(arcs(j,i):f(j,i)=0); for(arcs: bnd(0, f, c);f(3,7)+f(5,7)+f(6,7)<50;运行结果：此时，相应的网络的最大容量为90百万桶。8.PERT/CPM问题解：（1）根据题意可得产品的计划网络图为：（2）根据计划评审与关键路径的数学模型，按照正推法和逆推法，以及事件的最早开始时间和最迟开始时间的计算公式编写相应的lingo程序，et是事件的最早开始时间，lt是事件的最迟开始时间，d是作业的持续时间，tf是作业的总时差，ff是作业的单时差。运行程序如下：sets: event/1.8/: et,

27、lt; active(event, event)/ ! A B C D E F G H ; 1,2 1,3 2,4 3,5 4,5 5,6 3,7 6,7 7,8 /: d, tf, ff;endsetsdata: d = 6 5 3 0 2 3 2 4 2;enddatan=size(event);et(1)=0; for(event(k) | k #gt# 1: et(k)=max(active(i,k): et(i)+d(i,k););lt(n)=et(n);for(event(k) | k #lt# n: lt(k)=min(active(k,j): et(j)-d(k,j););fo

28、r(active(i,j): tf(i,j)=lt(j)-et(i)-d(i,j); ff(i,j)=et(j)-et(i)-d(i,j););运行结果：分析，可以根据运行结果得到各项作业的最早和最迟开始时间：12345678最早开始时间/周065911141820最迟开始时间/周0611911141820根据以上表格可得，当该项工作的最早开始时间和最迟开始时间相等时，该路线即为关键路线：ACD E G H故完成新产品的最短时间为：6+3+2+3+4+2= 20 周（3）可以根据题意将（2）中的模型改为项目赶期优化模型。变量设置：设是时间i的开始时间，作业（i,j）的持续时间，是完成作业（i,j）的最短时间，是作业（i,j）可能减少的时间，因此对于每个作业有 且 设t是要求完成的天数，1为最事件，n为最终事件，故 得其数学模型： Min s.t. 在lingo中运行程序如下：sets: event/1.8/: x; active(event, event)/ ! A B C D E F G H ; 1,2 1,3 2,4 3,5 4,5 5,6 3,7 6,7 7,8 /: c, d, m, y;endsetsdata: c = 800 600 300 0 600 400 300 200 0