2014年研究生数学建模答案范本


    


    数 学 建 模






    题目: A
    队号: 2014045A







    2014年5月25
    题目A:通信网络设计问题

    文研究通信网络铺设线路遇总铺设成网络结点链路性问题建模建立某通信公司建立80结点铺设线路提出优铺设方案
    问题1网络设计常见成低化问题通简化问题转寻找权值生成树问题利避圈法破圈法生成树(结果见8页图2)终求省铺设费29478万元通仿真计算该方案性检验结果表明意条链路破坏时够保证通信畅通结点数低结点数5375网络链路太稳定通模拟结点出现障发现22号结点出现障够保证通信畅通结点数结点数46(结果见14页表2)见利生成树模型涉网络铺线优点成低缺点保证结点通信畅通性低
    问题2根邻接矩阵计算达矩阵根达矩阵链路连通性关系结点出现障时生成树分解干组联通子树然保证90结点通信畅通条件分解图进行连接修复结点出现障时保证通信畅通90%建立01整数规划规划模型(12页)考虑整数规划模型求解复杂性设计贪婪算法中17结点出现障结点具体连接方法见(详见14页表2)结点出现障网络身保持90%需连链路表2中未进行考虑表2知贪婪算法结果保证925%结点通信畅通
    问题3求意条链路破坏时保证90结点通信畅通分两种情况进行考虑果意条链路破坏90%结点保持通信畅通链路需追加链接(详15页见表3)外链路破坏保证90%结点通信畅通需追加链接加边加边时允许某结点连2条边需原生成树某结点连两条样边(复制某生成树某两结点间破坏边形成回路)该链路然总铺设费省方案果允许意结点连两条边破坏边整树分二需计算两组结点间短距离连条新短路性90情况总铺设费方案(详17页见表4)
    问题四综合考虑网络性铺设费根问题2问题3结果结点出现障需加边链路破坏需加边全部加问题1 生成树性相高铺线模型(见19页图8)该模型意结点出现障结点保持畅通性低90%(详18页见表5)考虑该模型成高需增加铺设费75075万元次移成高边(处移图8中条边71-76)成更低稳定性友模型模型(见20页图9)时需增加成5032万元意结点出现障结点保持畅通性低90%(详21页见表6)边类似结果分见表7方案合理

    关键词:生成树破圈法网络模型图
    问题重述
    着科学技术进步计算机网络技术取快速发展成信息交流手段渗透社会方面发展断推动类社会逐渐走信息时代网络技术发展生活社会生产力提高提供巨贡献时存着许安全隐患信息漏洞出现网络OpenSSL心血漏洞等工作生活造成影响
    系统性重整体指标通信网络例外通信网络性仅通信设备链路关网络结构关网络结构复杂变通信网络性分析直棘手问题
    某通信公司拟建具80结点通信网络需结点间铺设线路进行数传输结合结点间距离铺设线路单位费见附件1文需具体完成问题:
    问题1:通信网络总铺设费省请建立问题数学模型设计求解算法出铺设方案讨方案性
    问题2:考虑通信网络结点性求意结点出现障时结点间然够保持通信畅通性达90请建立问题数学模型设计求解算法出总铺设费少铺设方案
    问题3:考虑通信网络链路性求意条链路破坏时够保持通信畅通结点够达90请建立问题数学模型设计求解算法出总铺设费少铺设方案
    问题4:综合考虑网络性铺设费试确定合理铺设方案
    二模型假设
    1假设结点结点间连接存先序均直线连接
    2假设考虑结点
    3假设考虑线路铺设费线路连通影响
    4假设通信网络中结点间距离固定变数
    5假设链路结点障正常两种状态
    6假设网络中链路障概率统计独立
    7考虑网络线路结点容量问题
    三定义符号说明
    :链路权值结点间距离×结点间铺设线路单位费
    :结点数
    :结点名
    :边
    :树
    四问题分析
    计算机网络通信现代流行尖端新颖通信技术手段现代信息技术发展极致发展现已进入智化宽带化综合化阶段发展前景广泛[1]保证网络通信安全前提网络性系统中较重整体指标网络性评估网络性相关研究基础目前网络性研究领域热点基性网络设计针网络性网络构建费等网络设计目标提供种优化方案供网络理者参考[2]
    问题重述知题属网络路线优化问题网络通信时数需结点间传输需结点间铺设线路理位置距离等素 结点间架设网线费 公司想结点间网络畅通费降低 应该样设计结点间线路文关键
    线路建设中仅需考虑成问题考虑方案性保证意结点链路出现障时通信畅通参考附件1结点间距离铺设线路单位费面问题进行分析:
    问题1:网络设计方案中常见问题成低化结合附件1中出结点间距离铺设线路单位费链路权值问题简化寻找生成树问题棵生成树代价树边代价时颗生成树总权值题中省总铺设费条产生回路边连接网络中顶点构造生成树[3]
    问题2:题1结知生成树网络连通基础考虑少总铺设费意结点线路出现障时种解决方案优解通信网络中仅需考虑铺设费问题考虑性问题问题二中求结点性90基础求解少总铺设费问题存两需考虑素:性达90时优先考虑省总铺设费二性达90情况优先考虑提高性计算少铺设费时间问题算法复杂性文前者素建立模型求解
    问题3:连通性定义性定义见题2题做定义直接运题2连通性性定义运MATLAB破坏意条链路时结点间连接关系根题1知:生成生成树已网络总铺设费省方案现考虑意条链路破坏时网络性达90基础省铺设费问题
    问题4:述三题解决方案知综合考虑网络性铺设费三方面着手:意结点出现障时网络性二意条链路破坏时网络性三总铺设费
    五模型建立求解
    51 问题1模型建立求解
    511 模型建立
    建模准确性面引入生成树概念般设V{ν1ν2ν3…νp}P点集合E{e1e2e3…eq}q条边集合中
    νi νj ∈V
    VE组成图形称图记果G0包含G 中顶点回路连通子图G0G棵生成树Gn顶点生成树n顶点n1条边图生成树中条边权值生成树生成树
    根生成树定义性质结(设图G1图G生成树)
    (1)G1中条边权值
    (2)G1中n 顶点n1条边
    (3)G1必须连通回路
    连通带权图里找时满足述三条件图找该图生成树
    研究方便题中通信网络简化结点结点间连线计结点文中律连线做链路生成树模型中链路权值F详见附件1结点编号
    假该公司建立部分结点位置简化图1示顶点代表结点编号边代表架设网线链路样构成带权连通图 费问题转化求带权连通图生成树问题








    图1 部分结点通信网络简化图
    512 模型求解
    常生成树算法—破圈法避圈法题采两种方法分模型求解
    (1)避圈法
    避圈法计算步骤:
    Step1:网络中选点vi令
    Step2:连接边中选取边 妨设边(vivj)该边必优化路线中条
    Step3:重新修正集合组成元素集合中增加顶点显然集合中减少该顶点
    Step4:果(空集)停止已找优化路线否返回第2 步
    面该网络中结点简单说明通信网络避圈法求解生成树方法通信网络铺设优方案问题避圈法求解程:
    ① 假设结点开始
    ② 链接中79种情况计算较出结点结点间铺设费费连接起标记部分树边
    ③ 重新修正集合
    ④ 前回第二步时通计算发现连接156条边中结点结点间铺设费费连接起程中没重复次第二步通计算铺设费较出边连接成生成树实现通信网络总铺设费省铺设方案铺设费29478百元中生成树图图2结点间铺设费表1
    (2)破圈法
    破圈法相避圈法思路简单谓破圈法取圈掉圈权值边反复执行步骤直没圈止[4]通前文知已通信网络建立连通图时问题简化破圈法求解生成树问题
    Step1:网络图中找圈 掉圈中长条边
    Step2:检查网络图中否圈果重复第1步否停止表明已找优路线
    结点数较MATLAB编程实现具体说明终输出结果避圈法样
    通两种方法均网络线路铺设生成树
    表1:结点间链路铺设费
    序号
    链接
    费百元
    序号
    链接
    费百元
    序号
    链接
    费百元
    1
    1–34
    154
    28
    40–63
    558
    55
    33–73
    230
    2
    26–34
    545
    29
    63–79
    300
    56
    51–30
    279
    3
    34–61
    273
    30
    35–27
    320
    57
    30–31
    43
    4
    61–50
    532
    31
    27–3
    160
    58
    31–59
    231
    5
    50–32
    132
    32
    3–7
    348
    59
    59–60
    1729
    6
    61–70
    115
    33
    7–13
    102
    60
    59–48
    783
    7
    70–36
    160
    34
    27–42
    420
    61
    30–38
    217
    8
    36–8
    468
    35
    42–53
    148
    62
    38–4
    303
    9
    8–14
    901
    36
    53–22
    432
    63
    4–58
    141
    10
    70–62
    84
    37
    53–37
    752
    64
    22–45
    308
    11
    70–66
    426
    38
    22–56
    254
    65
    45–76
    420
    12
    66–67
    98
    39
    22–54
    72
    66
    76–77
    288
    13
    62–47
    372
    40
    22–16
    198
    67
    77–23
    230
    14
    47–69
    690
    41
    16–52
    140
    68
    23–6
    145
    15
    47–2
    198
    42
    16–55
    320
    69
    23–75
    336
    16
    2–29
    483
    43
    55–25
    792
    70
    23–64
    387
    17
    2–19
    114
    44
    52–21
    468
    71
    64–57
    703
    18
    19–28
    368
    45
    52–43
    555
    72
    77–71
    195
    19
    19–49
    345
    46
    43–9
    420
    73
    71–72
    534
    20
    2–5
    336
    47
    52–18
    284
    74
    71–74
    187
    21
    5–78
    342
    48
    18–51
    302
    75
    74–17
    77
    22
    5–35
    101
    49
    51–12
    100
    76
    17–10
    157
    23
    35–20
    489
    50
    12–68
    300
    77
    10–44
    36
    24
    20–80
    1914
    51
    12–46
    207
    78
    44–15
    510
    25
    20–24
    586
    52
    46–65
    636
    79
    71–11
    472
    26
    24–39
    484
    53
    46–33
    80



    27
    35–40
    348
    54
    33–41
    811




    52 方案性
    根生成树特点网络连接特性两方面考虑方案性网络中连通性树生成法性
    网络连接性说(详见题2)意结点出现障破坏题2 MATLAB程序运行破坏结点性结果知(附件2)网络性04625高性意条链路破坏时网络性05375题2 MATLAB程序运行破坏链路性结果知(附件3)高性09875
    方案方法分析避圈算法空图出发逐步加边生成树似求解算法然数生成树问题求优解相部分求似优解具体应时定方便作种树算法概括理定意义破圈法图出发逐步边破圈生成树适合图工作图较时时子图工作破圈法实方便
    综合两方面说方案中生成树两种算法适题计算复杂度方面需改进实际生活中网络连通种较适方案






    图2 生成树图




    52 问题2模型建立求解
    521 模型建立
    (1)连通性
    A达矩阵
    判断网络链路否连通引入布尔代数布尔矩阵达矩阵概念
    定义1 二阶布尔代数元素元素阶矩阵中称布尔矩阵定阶布尔矩阵规定矩阵合成运算取运算
    1)
    2)
    3)
    4)
    式中表示元素取运算
    定义2 图中矩阵

    称达矩阵
    布尔矩阵定义:矩阵中元素属01矩阵题1邻接矩阵概念知图邻接矩阵达矩阵种典型布尔矩阵
    定理 令
    B求达矩阵新算法
    ①达矩阵常求法

    中阶单位阵简单图邻接矩阵中

    简单图
    ②新算法(布尔代数算达矩阵)
    根定理



    采逐次方法

    令达矩阵少步数[5]
    C达矩阵连通性
    达矩阵表明图中意两结点间否少存条链结点处否回路通达矩阵判断链路间 连通性例已知邻接矩阵


    述布尔矩阵求达矩阵新算法知需求步求达矩阵时进行3步达矩阵


    根达矩阵知互相连通互连通连通中链路权值F详见附件1
    根题意意结点出现障需查点间连通性令邻接矩阵中意结点出现障邻接矩阵中第行第列均定0时新邻接矩阵通新邻接矩阵布尔代数求达矩阵通达矩阵判断出结点连通性具体算法MATLAB实现
    (2)连通性
    分析问题2前考虑问题中性方便准确定义连通性:生成树中意结点者链路损坏剩余拥结点树结点数生成树总结点数衡量生成树连通性

    文中生成树方法时连通性通信网络性
    设点数
    时意结点链路发生障碍性90
    时意结点链路发生障碍性等90
    例:6结点生成树中结点链接发生障碍形状变化分图3图4具体种情况:
    A断结点1:1结点出现障形成2354连通结点孤立6结点时两结点间通信畅通性型
    B断链路12:链路12发生障碍形成236154两连通结点性


    图3

    图4
    出连通性基础根连通性定义性定义运MATLAB程序直接计算结点出现障时连通性通信网络链接性详细运算结果见附件2

    522 模型求解
    问题分析题1优解基础考虑意结点出现障问题根通信网络结点特性结点出现障该结点算性范围相连通结点连通性受破坏性降低障点外链路均已优解提高网络性需意结点破坏(网络结点连通性状态详见附件2)统计破坏结点性90结点生成树状态互连通生成树分组进行步建模面例子说明图5示

    图5
    破坏结点1网络性90生成树总铺设费省方案省破坏结点2性90需MATLAB编程计算出结点2破坏结点连通性根连通性分1组2组等根分组建立数学模型
    (1)01整数规划
    破坏结点性90通建立模型性90总铺设费少铺设方案
    互连通结点分形(137)组命名阿拉伯数字123等模型中表示考虑组组间存连接连接问题定义

    建立01整数规划模型
    目标函数

    中第组结点间链路铺设费总组组间铺设费表示第组第组间否存链路定义:

    实现目标规划文中实现01整数规划编程程中排时成圈情况






    中表示第组结点数
    01整数规划中成圈隐含条件LINGOMATLAB软件难计算采述贪婪算法进行建模求解
    (2)贪婪算法模型
    意破坏结点时生成树分组编号连线均成中初始选组均结点设第组第组间短铺设费链接第组总铺设费第组结点数规定初始组结点数结点数
    性90基础意结点出现障MATLAB编程详细分组情况(见附件2)选择连线均成组计算组组连线均成选择相连连线均成组令计算组性性90停止运算性90继续计算组剩余组连线均成直计算性90计算停止具体算法程:


    例图64组初始组(编号1)(连线均成组)分计算三组连线均成出(编号2)组连通连线均成计算性性90停止连通组否计算组(时编号12组重新组组)两组连线均成4组连线均成性90停止连通组否继续组连通

    图6
    文中结点数较算法相复杂运MATLAB方法计算结果表2示
    表2 结点出现障解决情况
    出现障结点
    出现障系统性
    重新连接结点
    连接系统性
    成百元
    未接入结点
    2
    07500
    47连4940连66
    09750
    24192
    229
    5
    07250
    40连66
    09750
    44917
    578
    16
    07000
    71连76
    09625
    16766
    16{2555}
    18
    07875
    46连71
    09875
    12708
    18
    22
    04625
    2连1055连62
    09625
    24532
    225456
    27
    05750
    3连742连10
    09875
    13524
    27
    35
    06250
    2连10
    09000
    34954
    35{20293480}{406379}
    42
    05625
    2连10
    09875
    13316
    42
    45
    08000
    23连54
    09875
    24958
    45
    47
    08125
    40连66
    09750
    49095
    4769
    51
    08000
    46连7131连33
    09875
    10127
    51
    52
    07375
    46连71
    09500
    13312
    5221{943}
    53
    05375
    2连10
    09750
    13736
    3753
    62
    08375
    66连40
    09875
    50781
    62
    70
    08500
    40连6661连68
    09500
    4066
    {81436}70
    76
    08125
    23连54
    09875
    25266
    76
    77
    08250
    2连10
    09250
    4041
    {623576475}77

    53 问题3模型建立求解
    根链路情况现分两种情况讨铺设方案中允许出现两结点间重复铺路需破坏链路铺设条链路保证性达90基础总铺设费省允许出现两结点间重复铺路需考虑组间短距离着手面两方面分讨
    (1)允许结点间重复铺路
    根网络连接特性发现条链路破坏生成树(代表结点数)条链路会影响生成树连通性影响性提高网络性兼顾铺设费基础链路破坏性达90情况铺设费然省(加边)需考虑链路破坏性90情况(加边)
    通分析知题意条链路破坏题1生成树方案基础生成树中点间铺设费已值需性90链路间铺设条链路样保证意条链路破坏性90情况总铺设达少例图7生成树中链路12破坏性9012间铺设条链路(见红色虚线边)


    图7

    通MATLAB编程意条链路破坏性统计出性90链路铺设条相链路
    (2)允许结点间重复铺路
    题1生成树基础允许结点间重复铺路链路破坏 生成树分干组组总铺设费已省铺设方案里需保证性90考虑组组短距离题中MATLAB程序分组情况性统计性90解决方案总费少铺设方案表4示:
    表3系统出现障性高90情况
    破坏链路
    链路破坏系统性
    剩余结点
    铺设费(百元)
    系统性
    3051
    09
    430313848585960
    26098
    09
    7177
    09
    10111517447174
    27310
    09
    1251
    09125
    12334146686573
    27114
    09125
    6170
    0925
    12632346150
    27727
    0925
    1246
    09375
    3341466573
    27514
    09375
    2377
    09375
    623576475
    27677
    09375
    7174
    09375
    1015174474
    28511
    09375
    1774
    095
    10151744
    28698
    095
    2035
    095
    20243980
    26005
    095
    3031
    095
    31485960
    26692
    095
    3038
    09624
    43858
    28817
    09624
    219
    09625
    192849
    28651
    09625
    327
    09625
    3713
    28868
    09625
    1017
    09625
    101544
    28775
    09625
    3159
    09625
    485960
    26735
    09625
    3346
    09625
    334173
    28357
    09625
    3461
    09625
    12634
    28506
    09625
    3540
    09625
    406379
    28272
    09625
    3670
    09625
    81436
    27949
    09625
    37
    0975
    713
    29028
    0975
    438
    0975
    458
    29034
    0975
    836
    0975
    814
    28109
    0975
    1044
    0975
    1544
    28932
    0975
    1655
    0975
    2555
    28366
    0975
    2024
    0975
    2439
    28408
    0975
    2364
    0975
    5764
    28388
    0975
    4063
    0975
    6379
    28620
    0975
    4352
    0975
    943
    28503
    0975
    5061
    0975
    3250
    28814
    0975
    6670
    0975
    6667
    28954
    0975
    134
    09875
    1
    29324
    09875
    229
    09875
    29
    28995
    09875
    458
    09875
    58
    29337
    09875
    578
    09875
    78
    29136
    09875
    623
    09875
    6
    29333
    09875
    713
    09875
    13
    29376
    09875
    814
    09875
    14
    28577
    09875
    943
    09875
    9
    29058
    09875
    1171
    09875
    11
    29006
    09875
    1268
    09875
    68
    29178
    09875
    1544
    09875
    15
    28968
    09875
    1928
    09875
    28
    29110
    09875
    1949
    09875
    49
    29133
    09875
    2080
    09875
    80
    27564
    09875
    2152
    09875
    21
    29010
    09875
    2254
    09875
    54
    29406
    09875
    2256
    09875
    56
    29224
    09875
    2375
    09875
    75
    29142
    09875
    2439
    09875
    39
    28994
    09875
    2555
    09875
    25
    28686
    09875
    2634
    09875
    26
    28933
    09875
    3250
    09875
    32
    29346
    09875
    3341
    09875
    41
    28667
    09875
    3373
    09875
    73
    29248
    09875
    3753
    09875
    37
    28726
    09875
    4665
    09875
    65
    28842
    09875
    4769
    09875
    69
    28788
    09875
    4859
    09875
    48
    28695
    09875
    5764
    09875
    57
    28775
    09875
    5960
    09875
    60
    27749
    09875
    6379
    09875
    79
    29178
    09875
    6667
    09875
    67
    29380
    09875
    7172
    09875
    72
    28944
    09875
    表4 链路出现障系统性低90情况
    破坏链路
    链路破坏系统性
    连接
    铺设费(百元)
    系统性
    2253
    05375
    2连10
    29516
    1
    4253
    05625
    2连10
    29800
    1
    2742
    0575
    2连10
    29528
    1
    2735
    0625
    2连10
    29628
    1
    1622
    07
    55连62
    29805
    1
    535
    0725
    40连66
    29812
    1
    1652
    07375
    46连7161连68
    29866
    1
    25
    075
    40连66
    29577
    1
    1852
    07875
    46连7161连68
    29722
    1
    1851
    08
    46连7161连68
    29704
    1
    2245
    08
    23连54
    29635
    1
    247
    08125
    47连49
    29640
    1
    4576
    08125
    23连54
    29523
    1
    7677
    0825
    23连54
    29655
    1
    4762
    08375
    40连66
    29541
    1
    6270
    085
    40连66
    29829
    1

    54 问题4模型建立求解
    基述问题4提出三方面建立数学模型:
    意条链路破坏保证性达90题1基础需连接链路令{}中代表第条边
    意结点障保证性达90题1基础需连接链路令{}
    时题1中生成树中加时网络性低09875方面性高外方面增加75075百元费符合量减少铺设费原
    设定合理性定义方案合理
    保证性90情况减少总铺设费切断铺设成高链路7176链路切断时时意链路破坏够保证通信畅通结点少095(详见表5)增加5032百元时考虑性相较高新增线路铺设费相题1 原费相增加少方案合理 意结点障够保证通信畅通结点少09(详见表6)增加5032百元方案合理
    表5 结点出现障加条边网络性
    结点
    网络性
    结点
    网络性
    结点
    网络性
    结点
    网络性
    1
    09875
    21
    09875
    41
    09875
    61
    0925
    2
    0975
    22
    0975
    42
    09875
    62
    09875
    3
    09625
    23
    09375
    43
    0975
    63
    0975
    4
    0975
    24
    0975
    44
    0975
    64
    0975
    5
    0975
    25
    09875
    45
    09875
    65
    09875
    6
    09875
    26
    09875
    46
    0975
    66
    0975
    7
    0975
    27
    09875
    47
    0975
    67
    09875
    8
    0975
    28
    09875
    48
    09875
    68
    09875
    9
    09875
    29
    09875
    49
    09875
    69
    09875
    10
    09625
    30
    095
    50
    0975
    70
    09625
    11
    09875
    31
    095
    51
    09875
    71
    09625
    12
    09875
    32
    09875
    52
    095
    72
    09875
    13
    09875
    33
    09625
    53
    0975
    73
    09875
    14
    09875
    34
    09625
    54
    09875
    74
    09875
    15
    09875
    35
    09
    55
    0975
    75
    09875
    16
    09875
    36
    09625
    56
    09875
    76
    09875
    17
    09875
    37
    09875
    57
    09875
    77
    09875
    18
    09875
    38
    09625
    58
    09875
    78
    09875
    19
    0975
    39
    09875
    59
    09625
    79
    09875
    20
    095
    40
    09625
    60
    09875
    80
    09875







    图8 结点出现障需加边链路破坏需加边全部加问题1 生成树性相高铺线模型





    图9 次移成高边(处移图8中条边71-76)成更低稳定性友模型模型

    表6 结点出现障网络性
    障点
    网络性
    障点
    网络性
    障点
    网络性
    障点
    网络性
    1
    09
    21
    0975
    41
    09875
    61
    09875
    2
    0925
    22
    0975
    42
    09875
    62
    09875
    3
    09375
    23
    0975
    43
    09875
    63
    09875
    4
    095
    24
    0975
    44
    09875
    64
    09875
    5
    095
    25
    0975
    45
    09875
    65
    09875
    6
    095
    26
    0975
    46
    09875
    66
    09875
    7
    095
    27
    0975
    47
    09875
    67
    09875
    8
    09625
    28
    0975
    48
    09875
    68
    09875
    9
    09625
    29
    0975
    49
    09875
    69
    09875
    10
    09625
    30
    0975
    50
    09875
    70
    09875
    11
    09625
    31
    0975
    51
    09875
    71
    09875
    12
    09625
    32
    0975
    52
    09875
    72
    09875
    13
    09625
    33
    0975
    53
    09875
    73
    09875
    14
    09625
    34
    0975
    54
    09875
    74
    09875
    15
    09625
    35
    0975
    55
    09875
    75
    09875
    16
    09625
    36
    09875
    56
    09875
    76
    09875
    17
    09625
    37
    09875
    57
    09875
    77
    09875
    18
    0975
    38
    09875
    58
    09875
    78
    09875
    19
    0975
    39
    09875
    59
    09875
    79
    09875
    20
    0975
    40
    09875
    60
    09875
    80
    09875
    表7 移成长边测切断条边模型稳定性
    切断条边
    切断边网络性
    切断条边
    切断边网络性
    切断条边
    切断边网络性
    10—17
    1
    23—77
    1
    4—58
    09875
    10—44
    0975
    24—39
    09875
    46—65
    1
    11—71
    09875
    2—47
    1
    47—49
    1
    12—46
    1
    2—5
    1
    47—62
    1
    12—51
    1
    25—55
    09875
    47—69
    1
    12—68
    1
    26—34
    09875
    48—59
    1
    1—34
    09875
    27—35
    1
    50—61
    0975
    15—44
    09875
    27—42
    1
    55—62
    1
    16—22
    1
    30—31
    1
    57—64
    09875
    16—52
    1
    30—38
    09625
    5—78
    09875
    16—52
    1
    30—51
    1
    59—60
    09875
    17—74
    1
    31—33
    1
    61—68
    1
    18—51
    1
    31—59
    09625
    61—70
    1
    18—52
    1
    32—50
    09875
    6—23
    09875
    18—52
    1
    3—27
    1
    62—70
    1
    19—28
    09875
    33—41
    09875
    63—79
    09875
    19—49
    1
    33—46
    1
    66—67
    09875
    20—24
    0975
    33—73
    09875
    66—70
    1
    20—35
    095
    34—61
    09625
    67—66
    09875
    20—80
    09875
    35—40
    1
    7—13
    09875
    2—10
    1
    36—46
    1
    71—72
    09875
    21—52
    9875
    36—70
    1
    71—74
    1
    2—19
    1
    3—7
    0975
    71—76
    1
    22—45
    1
    3—74
    1
    71—77
    1
    22—53
    1
    37—53
    09875
    7—3
    0975
    22—54
    1
    40—46
    1
    8—14
    09875
    22—56
    09875
    40—63
    0975
    8—36
    1
    2—29
    09875
    42—53
    1
    9—43
    09875
    23—64
    1
    43—52
    0975
    45—76
    1
    23—75
    1
    4—38
    0975
     
     

    六模型优缺点改进
    优点:文中运达矩阵判断连通性通定义性01整数规划贪婪算法分析结点者链路破坏情况结点间然够保持畅通性未达90总费省方案模型题网络适应性良解均似优点
    缺点:计算量较算法复杂
    改进:破坏意结点链路网络性动筛选出性<90情况进行步运算
    参考文献
    [1] 徐星 浅议计算机网络通信技术特点发展前景[J] 线互联科技 2013 03 38
    [2] 章筠 计算机网络性分析设计[D] 杭州 浙江学 2012
    [3] 董跃华 李云浩 姜东 破圈法实现普里姆算法[J] 江西理工学学报 2008 29(4) 2022
    [4] Lin WMTsay MT Wu SW Application of geographic information system for substain and feeder planning[J]International Journal of Electrical Power and Energy SystemIEEEMar 1996175183
    [5] 杨秀文 严尚安 张洁 鹏 达矩阵新求法[J] 电子科技学学报 2000 29(6) 666668









    附录

    附录1:邻接矩阵计算达矩阵程序
    function ykedajz(linjiejuzhenN)
    linjiejuzhen表示邻接矩阵N表示迭代次数
    clearclc
    linjiejuzhen[0 1 0 0 1 11 0 1 0 0 00 1 0 0 0 00 0 0 0 1 01 0 0 1 0 01 0 0 0 0 0]
    kedajuzhenlinjiejuzhen+eye(size(linjiejuzhen))
    Nkedajuzheneye(size(linjiejuzhen))
    N200
    for i1N
    Nkedajuzhen01Nkedajuzhen>0
    tempNkedajuzhen>0
    Nkedajuzhen Nkedajuzhen*kedajuzhen
    Nkedajuzhen01Nkedajuzhen>0
    ttttabs(Nkedajuzhen01temp)
    ibianshui1
    if sum(sum(tttt))<01breakend
    NkedajuzhenNkedajuzhen
    Nkedajuzhen01Nkedajuzhen01
    end
    yNkedajuzhen01

    附录2:根达矩阵生成树分成干组走通组间走通子树(组)

    function [zuidazudsjiedianzu]fenzu(kedajuzhen)
    nlength(kedajuzhen)达矩阵行数结点数
    index1n初始点
    flagones(1n)
    for i1n
    temp[]
    for j1n
    if kedajuzhen(ij)>0&flag(j)>0
    temp[tempij]flag(j)0
    end
    end
    jiedianzu0{i}unique(temp)
    end
    zushu0zuidazuds0
    for i1length(jiedianzu0)
    if length(jiedianzu0{i})>0
    zushuzushu+1
    jiedianzu{zushu}jiedianzu0{i}
    end
    if length(jiedianzu0{i})>zuidazuds
    zuidazudslength(jiedianzu0{i})
    end
    end

    附录3:切断意条边计算网络性

    clearclc
    load data1mat
    该文件切断条边网络性计算程序
    linjiejuzhen[0 1 0 0 1 11 0 1 0 0 00 1 0 0 0 00 0 0 0 1 01 0 0 1 0 01 0 0 0 0 0]
    linjiejuzhen(15)0linjiejuzhen(51)0
    linjiejuzhen(1)0linjiejuzhen(1)0破坏结点1
    linjiejuzhen(5)0linjiejuzhen(5)0破坏结点1
    N40000设置迭代次数
    nlength(mintrM)总结点数
    for i01n
    for j01n
    linjiejuzhenmintrM
    clc
    if linjiejuzhen(i0j0)>0
    linjiejuzhen(i0j0)0
    linjiejuzhen(j0i0)0
    [iiiijjj]find(mintrMlinjiejuzhen>0)
    fprintf('切断边dd计算系统性:'i0j0)
    kedajuzhenkedajz(linjiejuzhenN)根邻接矩阵计算达矩阵
    [zuidazudsjiedianzu]fenzu(kedajuzhen)jiedianzu中元素已分组组连通组间联通
    disp('网络度:')
    kekaoduzuidazudsn
    for i1length(jiedianzu)
    fprintf('第d组结点组结点连通组间连通'i)
    eval(['zu_'num2str(i)'jiedianzu{i}'])
    end
    disp('-----统计结果请ENTER键继续------')pause
    end
    end
    end

    附录4:破坏结点计算网络性

    clearclc
    load data1mat
    该文件坏点网络性计算程序
    linjiejuzhen[0 1 0 0 1 11 0 1 0 0 00 1 0 0 0 00 0 0 0 1 01 0 0 1 0 01 0 0 0 0 0]
    linjiejuzhen(15)0linjiejuzhen(51)0
    linjiejuzhen(1)0linjiejuzhen(1)0破坏结点1
    linjiejuzhen(5)0linjiejuzhen(5)0破坏结点1
    N40000设置迭代次数
    nlength(mintrM)总结点数
    for i01n
    linjiejuzhenmintrM
    clc
    linjiejuzhen(i0)0
    linjiejuzhen(i0)0
    [iiiijjj]find(mintrMlinjiejuzhen>0)
    fprintf('破坏dd计算系统性:'i0)
    kedajuzhenkedajz(linjiejuzhenN)根邻接矩阵计算达矩阵
    [zuidazudsjiedianzu]fenzu(kedajuzhen)jiedianzu中元素已分组组连通组间联通
    disp('网络度:')
    kekaoduzuidazudsn
    for i1length(jiedianzu)
    fprintf('第d组结点组结点连通组间连通'i)
    eval(['zu_'num2str(i)'jiedianzu{i}'])
    end
    disp('-----统计结果请ENTER键继续------')pause
    end

    附录5:条边截断性低90计算加边保网络性达90

    clearclc
    load data1mat
    该文件坏点网络连接计算程序
    linjiejuzhen[0 1 0 0 1 11 0 1 0 0 00 1 0 0 0 00 0 0 0 1 01 0 0 1 0 01 0 0 0 0 0]
    linjiejuzhen(15)0linjiejuzhen(51)0
    linjiejuzhen(1)0linjiejuzhen(1)0破坏结点1
    linjiejuzhen(5)0linjiejuzhen(5)0破坏结点1
    N40000设置迭代次数
    nlength(mintrM)总结点数
    for i01n
    fflag0
    for i01length(Bianji)
    linjiejuzhenmintrM
    clc
    linjiejuzhen(Bianji(i01)Bianji(i02))0
    linjiejuzhen(Bianji(i02)Bianji(i01))0
    [iiiijjj]find(mintrMlinjiejuzhen>0)
    fprintf('破坏边dd计算系统性:'Bianji(i01)Bianji(i02))
    kedajuzhenkedajz(linjiejuzhenN)根邻接矩阵计算达矩阵
    [zuidazudsjiedianzu]fenzu(kedajuzhen)jiedianzu中元素已分组组连通组间联通
    disp('网络度:')
    kekaoduzuidazudsn
    if kekaodu<09
    fflag1
    end
    计算结算结点破坏新铺线
    linjiezhen_zulinjiejuzhen(zu_3zu_3)第3组邻接矩阵
    feiyong_zufeiyong(zu_3zu_3)第i3组已单位铺线费
    cilinjiezhen_zu*feiyong_zu 第i3组已铺线费
    feiyong_zufeiyong(zu_2zu_3)zu_2zu_3两组点间连线费矩阵
    sijmin(min(feiyong_zu))zu_2zu_3两组点间连线费
    [node1node2]find(sijfeiyong_zu)两组点间连线费结点
    zu_2zu_3两组点间连线均费avgsij(c2+c3+s23)(d2+d3)中d2d3表示组结点数

    disp('-----统计结果请ENTER键继续------')pause
    结点i0破坏必须重结点集删i0
    z0zilianjieidian[]
    if fflag>0
    feiyong00feiyongttt0feiyong00(Bianji(i01)Bianji(i02))
    feiyong00(Bianji(i01)Bianji(i02))99999999999999
    feiyong00(Bianji(i02)Bianji(i01))99999999999999
    feiyong_zufeiyong00(jiedianzu{1}jiedianzu{2})zu_2zu_3两组点间连线费矩阵
    sijmin(min(feiyong_zu))zu_0zu_0两组点间连线费
    [node1node2]find(sijfeiyong00)zu_0zu_i两组点间连线费结点
    z0zilianjieidian[node1node2]
    zu_0zu_i两组点间连线费应结点
    disp('')
    fprintf('破坏边dd连接系统性:'Bianji(i01)Bianji(i02))
    100
    fprintf('破坏边dd连接联网成:'Bianji(i01)Bianji(i02))
    clwcbdisitance+sijttt0
    fprintf('破坏边dd重新连接结点:'Bianji(i01)Bianji(i02))
    z0zilianjieidianz0zilianjieidian
    pause
    end
    end for 破坏结点i0

    附录6:结点破坏性低90计算加边保证网络性90
    clearclc
    load data1mat
    该文件坏点网络连接计算程序
    linjiejuzhen[0 1 0 0 1 11 0 1 0 0 00 1 0 0 0 00 0 0 0 1 01 0 0 1 0 01 0 0 0 0 0]
    linjiejuzhen(15)0linjiejuzhen(51)0
    linjiejuzhen(1)0linjiejuzhen(1)0破坏结点1
    linjiejuzhen(5)0linjiejuzhen(5)0破坏结点1
    N40000设置迭代次数
    nlength(mintrM)总结点数
    for i01n
    fflag0
    for i01n
    linjiejuzhenmintrM
    clc
    linjiejuzhen(i0)0
    linjiejuzhen(i0)0
    [iiiijjj]find(mintrMlinjiejuzhen>0)
    fprintf('破坏dd计算系统性:'i0)
    kedajuzhenkedajz(linjiejuzhenN)根邻接矩阵计算达矩阵
    [zuidazudsjiedianzu]fenzu(kedajuzhen)jiedianzu中元素已分组组连通组间联通
    disp('网络度:')
    kekaoduzuidazudsn
    if kekaodu<09
    fflag1
    end
    for i1length(jiedianzu)
    fprintf('第d组结点组结点连通组间连通'i)
    eval(['zu_'num2str(i)'jiedianzu{i}'])
    end
    计算结算结点破坏新铺线
    linjiezhen_zulinjiejuzhen(zu_3zu_3)第3组邻接矩阵
    feiyong_zufeiyong(zu_3zu_3)第i3组已单位铺线费
    cilinjiezhen_zu*feiyong_zu 第i3组已铺线费
    feiyong_zufeiyong(zu_2zu_3)zu_2zu_3两组点间连线费矩阵
    sijmin(min(feiyong_zu))zu_2zu_3两组点间连线费
    [node1node2]find(sijfeiyong_zu)两组点间连线费结点
    zu_2zu_3两组点间连线均费avgsij(c2+c3+s23)(d2+d3)中d2d3表示组结点数

    disp('-----统计结果请ENTER键继续------')pause
    结点i0破坏必须重结点集删i0
    if fflag>0

    if length(jiedianzu{i0zu})0
    jiedianzu(i0zu)[]
    end
    jiedianzujiedianzu
    计算结点组均成

    c[]avgc[]计算结点组均成
    for i1length(jiedianzu)
    if length(jiedianzu{i})0
    c(i)99999999999 第i3组已铺线费
    avgc(i)999999999 第i组已均结点铺线费
    else
    zu_ijiedianzu{i}
    linjiezhen_zulinjiejuzhen(zu_izu_i)第3组邻接矩阵
    feiyong_zufeiyong(zu_izu_i)第i组已单位铺线费
    c(i)sum(sum(linjiezhen_zu*feiyong_zu))2 第i3组已铺线费
    avgc(i)c(i)length(zu_i) 第i组已均结点铺线费
    end
    end
    选取初始结点z0求成低结点数组10%
    [tempindex0]sort(avgc)
    jiedianzu00jiedianzuc00
    for i1length(jiedianzu00)
    if length(jiedianzu{index0(i)})>n*010
    z0jiedianzu{index0(i)}已入网中结点
    jiedianzu00(index0(i))[]jiedianzu00中移已入网中结点
    c(index0(i))[]成c中移已入网中结点成
    c0c0+c(index0(i))已入网中结点总成
    break
    end
    riwangzuxu[riwangzuxuindex0(i)]
    end
    iter0
    lianxian[]
    while length(z0) iteriter+1
    fprintf('第d次迭代-------'iter)
    计算z0组组间短距离sij连接结点
    s[]
    z0zilianjieidian[]
    重新计算jiedianzu00中
    for i1length(jiedianzu00)
    feiyong_zufeiyong(z0jiedianzu00{i})zu_2zu_3两组点间连线费矩阵
    sijmin(min(feiyong_zu))zu_0zu_0两组点间连线费
    s(i)sijzu_0zu_i两组点间连线费
    [node1node2]find(sijfeiyong_zu)zu_0zu_i两组点间连线费结点

    z0zilianjieidian[z0zilianjieidianz0(node1(1))jiedianzu00{i}(node2(1))]
    zu_0zu_i两组点间连线费应结点
    end
    计算联入结点均总成
    avgs[]
    for i1length(jiedianzu00)
    avgs(i)(s(i)+c(i))length(jiedianzu00{i})计算新连入结点均成
    if abs(prod(jiedianzu00{i}i0))0
    avgs(i)9999999999999
    end
    end
    minavgsavgs(1)t01
    for i1length(jiedianzu00)
    if minavgs>avgs(i)
    minavgsavgs(i)t0i选t0组联入z0时新连入结点均成低
    end
    end
    z0[z0jiedianzu00{t0}]t0组合z0组
    lianxian[lianxian z0zilianjieidian(t0)]
    jiedianzu00(t0)[]删t0组
    c0c0+c(t0)+s(t0)计算入网总成余组成重新计算c
    c(t0)[]
    disp('')
    fprintf('破坏结点d连接系统性:'i0)
    kkdlength(z0)n
    fprintf('破坏结点d连接联网成:'i0)
    clwcbc0
    fprintf('破坏结点d重新连接结点:'i0)
    lianxianlianxian
    end
    pause
    end
    end for 破坏结点i0

    附录7:问题四求解程序

    clearclc
    global linjiejuzhen00
    load data1mat
    linjiejuzhen00mintrM

    kedajuzhenkedajz(linjiejuzhen00N)
    [zuidazudsjiedianzu]fenzu(kedajuzhen)
    linjiejuzhen_jianbian
    linjiejuzhenlinjiejuzhen00
    N40000设置迭代次数
    nlength(mintrM)总结点数
    fidfopen('wenti44txt''w')
    for i01n
    for j01n
    linjiejuzhenlinjiejuzhen00
    clc
    if linjiejuzhen(i0j0)>0
    linjiejuzhen(i0j0)0
    linjiejuzhen(j0i0)0
    fprintf(fid'\n')
    fprintf(fid'切断边dd计算系统性:\n'i0j0)
    fprintf('切断边dd计算系统性:'i0j0)
    kedajuzhenkedajz(linjiejuzhenN)根邻接矩阵计算达矩阵
    [zuidazudsjiedianzu]fenzu(kedajuzhen)jiedianzu中元素已分组组连通组间联通
    disp('网络度:')
    kekaoduzuidazudsn
    fprintf(fid'网络度:d\n'kekaodu)
    for i1length(jiedianzu)
    fprintf('第d组结点组结点连通组间连通'i)
    eval(['zu_'num2str(i)'jiedianzu{i}'])
    end
    disp('-----统计结果请ENTER键继续------')pause
    end
    end
    end
    fclose(fid)



    文档香网(httpswwwxiangdangnet)户传

    《香当网》用户分享的内容,不代表《香当网》观点或立场,请自行判断内容的真实性和可靠性!
    该内容是文档的文本内容,更好的格式请下载文档

    下载文档到电脑,查找使用更方便

    文档的实际排版效果,会与网站的显示效果略有不同!!

    需要 2 香币 [ 分享文档获得香币 ]

    下载文档

    相关文档

    数学建模

    钢管下料问题   队员:周安伟(15895144205)       余乐洲(15189304964)       蔡佳斌 摘要: 在钢材买卖过程中,零售商的刚才都是固定钢管原材料...

    9年前   
    7880    0

    数学建模论文

    舰艇会和问题数学建模论文姓名:班级:学号:舰艇会和问题摘要:当舰艇执行完任务会合航母时,需要采取合适的航行方向与航母会和,可以用坐标系解决这类问题。现代战争中,航空母舰被视为一个国家海军力量的...

    3年前   
    945    0

    学习数学建模的心得

    学习数学建模的心得  通过对专题七的学习,我知道了数学探究与数学建模在中学中学习的重要性,知道了什么是数学建模,数学建模就是把一个具体的实际问题转化为一个数学问题,然后用数学方法去解决它,之后...

    10年前   
    544    0

    投资问题数学建模

    数学模型第一次讨论作业问题:某部门现有资金10万元,五年内有以下投资项目供选择:项目A:从第一年到第四年每年初投资,次年末收回本金且获利15%;项目B:第三年初投资,第五年末收回本金且获利25...

    3年前   
    1268    0

    房地产数学建模

    房地产问题分析 摘要房地产行业与百姓的生活息息相关。近年来,由于房地产价格的不断攀升,房地产行业已经引起了社会的广泛关注。本文分别就影响房地产价格的因素和未来房地产价格的趋势进行了细致的分析研...

    3年前   
    543    0

    数学建模电梯调度问题

    高峰期电梯调度优化方案摘要:本文首先建立一个电梯调度的模型评价指标体系,选取了乘客关注的等待时间、电梯的总运送时间和影响能量节约效果的电梯停靠次数、电梯行进总时间四个指标。利用这四个指标来综合...

    7个月前   
    191    0

    数学建模实践报告

    数学建模实践报告 一、实践目的 数学建模主要是将显示对象的信息加以翻译与归纳的产物。通过对数学模型的假设、求解、验证,得到数学上的解答,在经过翻译回到现实对象,给出分析与决策的结果。...

    4个月前   
    238    0

    数学建模问题分析

    1、      给出一个所感兴趣的建模的实际问题:上班高峰车辆拥堵情况 (1)      写出问题的实际背景:**发展迅速,人们生活水平提高,私家车越来越多。上班高峰期车辆拥堵严重,通过调查...

    11年前   
    11948    0

    关于人口问题数学建模

    中国人口增长预测摘要:本文通过对题目中所给数据和参考资料以及网站上获得的数据进行分析,利用多种模型对数据规律进行归纳提炼.首先我们建立了,Malthus微分方程,通过求借建立了我国人口增长的指...

    2年前   
    728    0

    关于生产最优化的数学建模

    关于生产最优化的数学模型摘要在现代化生产过程中,生产部门面临的突出问题之一,便是如何选取合理的生产率.生产率过高,导致产品大量积压,使流动资金不能及时回笼;生产率过低,产品不能满足市场需要,使...

    1年前   
    359    0

    数学建模2016A题

    承诺书参赛队员 (打印并签名) : 题目 系泊系统的设计问题分析摘 要本文主要研究在风力和海水的作用下,钢管与浮标的受力平衡问题。根据钢桶和...

    4个月前   
    240    0

    数学建模基础练习一及参考答案

    数学建模基础练习一及参考答案练习1 matlab练习一、矩阵及数组操作:1.利用基本矩阵产生3×3和15×8的单位矩阵、全1矩阵、全0矩阵、均匀分布随机矩阵([-1,1]之间)、正态分布矩阵...

    3年前   
    1182    0

    关于数学建模论文的致谢词

    关于数学建模论文的致谢词  数学建模论文的致谢词如下文  从爱中学会了爱,将爱升华为大爱,一种对生命的关怀、对天下的博爱!问好作者!  掩卷时分,已是夜阑人静,老和山下的求是园里已难得见到几处...

    8年前   
    615    0

    2017年如何撰写数学建模论文

    如何撰写数学建模论文  当我们完成一个数学建模的全过程后,就应该把所作的工作进行小结,写成论文。撰写数学建模论文和参加大学生数学建模时完成答卷,在许多方面是类似的。事实上数学建模竞赛也包含了学...

    7年前   
    625    0

    数学建模大赛活动策划书

    数学建模大赛活动策划书  一、活动引言:  创新意识、团队精神、重在参与、公平竞争。  通过竞赛,更好地发展数学建模,扩大数学建模的影响力,活跃校园学习气氛,进一步推进长沙理工校园学风建设,促...

    12年前   
    659    0

    最佳旅游线路数学建模

    最佳云南旅游路线设计 摘 要 本文主要研究最佳旅游路线的设计问题。在满足相关约束条件的情况下,花最少的钱游览尽可能多的景点是我们追求的目标。基于对此的研究,建立数学模型,设计出最佳的旅游路...

    5年前   
    1457    0

    数学建模心得体会

    数学模型主要是将现实对象的信息加以翻译,归纳的产物。通过对数学模型的假设、求解、验证,得到数学上的解答,再经过翻译回到现实对象,给出分析、决策的结果。其实,数学建模对我们来说并不陌生,在我们的...

    6年前   
    23606    0

    数学建模贷款月还款问题

     数学建模一周论文论文题目:贷款月还款问题队长1: 学号:电话:队员2: ...

    3年前   
    633    0

    数学建模汽车生产计划

    汽车生产计划问题:汽车厂生产三种类型汽车,一直各类型每辆车对应的钢材,劳动时间要求是。利润及工厂每月现有量。小型汽车中型汽车大型汽车现有量钢材(吨)1.555600时间(小时)28025040...

    1年前   
    316    0

    了解数学建模论文的致谢词

    了解数学建模论文的致谢词  数学建模论文的致谢词如下文  从爱中学会了爱,将爱升华为大爱,一种对生命的关怀、对天下的博爱!问好作者!  掩卷时分,已是夜阑人静,老和山下的求是园里已难得见到几处...

    11年前   
    595    0

    文档贡献者

    文***享

    贡献于2020-12-25

    下载需要 2 香币 [香币充值 ]
    亲,您也可以通过 分享原创文档 来获得香币奖励!
    下载文档

    该用户的其他文档