2022年网络优化作业 .pdf

《2022年网络优化作业 .pdf》由会员分享，可在线阅读，更多相关《2022年网络优化作业 .pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、作业土规 1101 班刘迈克 2011306200521 第一题：在个遥远的国家，Sark Mevo 所领导的政党最终击败了 Reguel Tekris王子领导的联合党派。Mevo希望巩固他在首都地区的席位。首都由14 个街区组成，这些街区将分组为多个选区。下图是首都地区的示意图。在图中用数字1 到 14 对这些街区进行了编号。每个街区中的另外两个数字是预计该街区会投票给Mevo的选民数和该街区的选民总数。所有选民都必须投票，且选举胜出方必须得到绝对多数选票。一个选区可以由多个相邻的街区组成，且选区内总选民数应在 30,000 到 100,000 之间。如果两个街区不相邻，例如12和 13，则

2、它们不能组成一个选区。如果某个街区选民人数不少于50,000，则允许此街区单独作为一个选区。但是由于Mevo本人就居住在街区 10 内，因此迫于舆论压力，他不能将这个街区单独作为一个选区。请设计出一个将首都划分为5 个选区的方案，以使Mevo得到的席位数最多。如果这样做有困难，可以尝试划分为6 个选区。名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 5 页 -解：（1）运用二部图的最大匹配。分别将街区划分为选票率大于0.5 的 x 和小于 0.5 的 y 两部分，然后将x、y 相邻的街区进行连线，寻找最大匹配，使得票概率最大，但是结果可能不太准确。（2）运用 0-1 规划划分不同

3、的选区，然后根据条件寻找最匹配区域。讨论该如何选区时，运用着色原理，考虑将 1 个、2 个或 3 个街区组成一个选区的可能性。同时，定义单个街区组成的选区为A型选区，两个相邻街区组成的选区为 B型选区，3 个两两相邻街区组成的选区为C型选区。假设划分为 6 个选区，根据整数规划，建立模型1461ixi 0 xi4 xiN xi 表示第 i 选区所含的街区数，运用MATLAB 程序：clc;clear;%清除 matlab 界面的数值,及其变量%x1,x2,x3,x4,x5,x6 表示 6 个席区for x1=1:3%表示为 x1 每个席区的街区数的取值范围,以下类同for x2=1:3 for

4、 x3=1:3 for x4=2:3 for x5=2:3 for x6=2:3 if x1+x2+x3+x4+x5+x6=14%每个席区所包含的街区的个数等于总街区数A=x1,x2,x3,x4,x5,x6;%输出解B=sort(A)end end end end end end end%由于 x1,x2,x3,x4,x5,x6 不存在有序性,故对于有序组只取其中一个即可得到结果：B=2 2 2 2 3 3，定义 Xi 为第 i 个选区所含街区数，Xi 为 1、2或 3，约束61ixi=14我们可以 6 个由不同型号选区组成的划分方案，即B B B B C C。程序：n=14;A=名师资料总结

5、-精品资料欢迎下载-名师精心整理-第 2 页，共 5 页 -0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 00 1 0 1 1 0 0 0 0 0 0 0 0 00 0 1 0 1 0 0 0 0 1 0 0 0 0 1 1 1 1 0 1 0 0 0 1 0 0 0 00 0 0 0 1 0 1 1 0 0 0 0 0 00 0 0 0 0 1 0 1 1 0 0 0 0 00 0 0 0 0 1 1 0 1 1 1 0 0 00 0 0 0 0 0 1 1 0 0 1 1 0 00 0 0 1 1 0 0 1 0 0 1 0 1

6、 00 0 0 0 0 0 0 1 1 1 0 1 1 00 0 0 0 0 0 0 0 1 0 1 0 0 10 0 0 0 0 0 0 0 0 1 1 0 0 10 0 0 0 0 0 0 0 0 0 0 1 1 0;D=A;P=30000 50000 20000 70000 20000 40000 30000 30000 40000 60000 10000 60000 40000 40000;Q=17500 15000 14200 42000 18000 9000 12000 10000 26000 34000 2500 27000 29000 15000;V=Q;U=P;for i=1

7、:nfor j=1:nif (D(i,j)&(30000=(U(i)+U(j)&(U(i)+U(j)0.5)=1 B=i,j;C=sort(B)disp(*);endendend可得出所有能获得优势席位的B型选区组合情况，如下表所示：B 型选区号1 2 3 4 5 6 7 所含街区号（1，5）（3，4）（3，5）（4，5）（5，10）（7，9）（8，9）B 型选区号8 9 10 11 12 13 所含街区号（9，11）（9，12）（10，11）（10，13）（11，13）（13，14）不能组成优势席位 B型选区的街区输出，为 2号和6号街区，即 2号和6号只能组成名师资料总结-精品资料欢迎下载

8、-名师精心整理-第 3 页，共 5 页 -为C 型选区。2号街区组成的 C型选区（1，2，5）和（2，3，5）这两种情况，由6号街区组成的 C型选区只有（6，7，8）这一种情况。因此两个 C型选区的组成为（1，2，5）+（6，7，8）或（2，3，5）+（6，7，8）这两种可能方案。MODEL:SETS:JIEQU/S3,S4,S9,S10,S11,S12,S13,S14/;!定义去除选定的六个点外的剩于的街区的编号，并且按照升序排列;PAIRS(JIEQU,JIEQU)|&2#GT#&1:LINGJIE,MATCH;!街区 I到街区I,且 I大于 J,LINGJIE 表示当街区 I到街区 J相

9、邻，且街区I和街区 J的人数在 30000在100000 且街区 I和街区 J的预计选 mevo的总人数与街区I和街区 J的总人数之比大于0.5 这三个条件满足时 LINGJIE(I,J)为1，否则为 A（I,J)为0.此矩阵为上三角的0-1矩阵;ENDSETSDATA:LINGJIE=1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 0 0 0 1;ENDDATAobjective MAX=SUM(PAIRS(I,J):LINGJIE(I,J)*MATCH(I,J);!每队存在，且满足邻接条件时，相乘为了 1，若 4队同时存在，则相加为4;FOR

10、(JIEQU(I):SUM(PAIRS(J,K)|J#EQ#I#OR#K#EQ#I:MATCH(J,K)=1);FOR(PAIRS(I,J):BIN(MATCH(I,J);END 运用 LINGO软件求解，搜索到存在与（1，2，5）+（6，7，8）匹配的 4 个 B型选区，并在这 4 个选区都能获得席位，即得到的最优解获得5 个席位.选区型号 B B B B C C 所含街区号（3，4）（9，12）（10，11）（13，14）（1，2，5）（6，7，8）最优解可能不唯一，讨论（2，3，5）+（6，7，8）的 C型选区组合情况，在表 5 中删除含有这 6 个街区的 B型选区号，结果如下表所示：B

11、型选区号1 2 3 4 5 6 所含街区号（9，11）（9，12）（10，11）（10，13）（11，13）（13，14）分析表 9 可知，没有其它任何街区与1 号街区形成 B型选区。因此该方案不可行，最优解唯一。名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 5 页 -划分为 5 个选区的模型必须含有4 个由 3 个 C街区组成的选区，因此 5 个选区的模型在现有的条件下不成立，固不于考虑。第二题：如图在每一段容量不同的情况下得到最优的敷设。电缆沟用图表示，每根电缆的敷设用节点表示。在一个田字型的电缆沟里面，敷设从A 到 B 的 6 条电缆，依次并排敷设。分别在以下情况下敷设1

12、.每一段容量为3；2.A 相连的两端容量为3，其余容量为2；由于电缆较粗，在敷设中要减少交叉和转弯次数，试找到交叉和转弯次数最少的敷设方案。解：首先对每个节点标号125，按顺序编号，如图所示，方框代表各个节点：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 若是两点之间相差正负1 或者正负 5，则说明这两点在同一行或者同一列上，若是不满足以上条件说明存在转弯情况，每三个点判断是否存在转弯情况。例如节点 13，如果与周围相邻的四个节点8、12、14、18 相差分别为正负 1 或者正负 5，则存在交叉现象；3、4、5 每三个节点考虑转弯问题。1、每一段容量为 3。要求减少交叉次数和转弯次数，有两种方法从A到 B：（1）节点：5432161116.（2）节点：510152019181716.A 名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 5 页 -