数学建模网络优化.pdf

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

1、20112011甘肃农业大学第八届大学生数学建模竞赛甘肃农业大学第八届大学生数学建模竞赛承承诺诺书书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料） ，必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从 A/B/C/D

2、 中选择一项填写） ：A我们的参赛报名号为（如果赛区设置报名号的话） ：所属学校（请填写完整的全名） ：甘肃农业大学参赛队员 (打印并签名) ：1.周小雄2.崔起飞3.杨慧珍日期： 2012年 5 月 29日指导教师或指导教师组负责人(打印并签名)：赛区评阅编号（由赛区组委会评阅前进行编号）：摘要本文研究的是工程施工工期的优化问题，使用了网络优化模型，通过对网络关键路径的分析和改进，采用两种方法进行求解并比较结果，得到了工程最短工期和公司利润最大情况下的最优施工方案。对于问题一，根据各个任务之间的联系，绘制了双代号网络图，采用用点代表事件，点之间的有向线段代表任务，虚线段代表先决关系的虚工作，

3、虚工作的耗时为 0, 清楚的表示出了任务之间的施工进程。第二问求解时， 本文采用的方法一是建立工期最短的目标方程和以先行后继关系为约束的条件，将问题转换为最优解问题；方法二是通过求解工程各个事件的最早开始和最迟开始时间，得到最后一个事件的完成时间则为工程最短工期。两种方法求解出的结果相同，工程最短工期均为 64 周。在问题二的基础上，问题三需要在公司利润最大化的情况下缩短工期，方法一在问题二的基础上改变了目标函数为公司利润，以缩短关键路径为手段。在缩短关键路径时，涉及到关键路径可能改变问题，对此，本文将目标函数设置成总周期的减少除去额外费用， 这样避免了在求解过程中易出现的非关键路径的缩短而浪

4、费资源的情况，也解决了关键路径可能改变的问题，同样将问题转换为了最优解问题。在方法二中，先假设对关键路径进行缩短，关键路径不发生改变。再联系缩短任务耗时所需的成本分析工程该如何缩短工期，最终得到最优施工方案。将最优施工方案检验，发现缩短周期后关键路径并没有发生改变。两种方法求得的结果相同，公司最大利润为 8.7 万元，工程工期缩短到 54 周。整个问题最大的困难就是缩短时间可能发生的关键路径的改变从而引起的错误判断，本文模型最大的优势就是由于适当的设置了目标函数，从而避免了这个问题的发生。通过两种方法比较使用进行求解，以及不同方法的相互验证，确保了施工方案的最优化和公司利益的最大化。关键词：双

5、代号网络图、最优解、关键路径、最大获利1一、问题重述某市政府决定修建一个小型体育馆，通过竞标，一家本地建筑公司获得此项工程，并且希望尽快完成工程。表中列出了工程中的主要任务，时间以周计算。有些任务只有在某任务完成后才能进行。需要解决的问题是：问题一：绘制各任务间的关系图。问题二：工程最早完成时间。问题三：市政府希望能够提前完工，为此向建筑公司提出工期每缩短一周，则可支付 3 万元奖励。为缩短工期，建筑公司需要雇用更多的工人，并租借更多设备（表中额外支出部分） 。设计施工方案使建筑公司的获利最大。二、基本假设1. 题中所给的完成各项工程任务的时间是准确不变的，不受各种自然、非自然因素的影响。2.

6、 所有工程任务需要且必须在满足先决条件的情况下即可立即开始。3. 每周额外支出费用是指工期每缩短一周所支出的费用。4. 缩短施工时间的任务在除额外支出费用外的原来的总施工费用不变。5. 市政府希望尽早完成工程，建筑公司以在利益最大的情况下也以尽早完成工程为目标。三、符号说明与名词解释3.1 符号说明vi：表示第i个事件，i 1,2.13；xi：表示事件vi的开始时间，i 1,2.13；tij：是事件(vi,vj)间最长任务完成的时间，i, j 1,2.13；mi：完成任务i的最短完成时间，i 1,2.18；yi：任务i可能减少的完成时间，i 1,2.18；ci：任务i每缩短一周所需的额外费用，

7、i 1,2.18；di：任务ei的持续时间，i 1,2.18；bi：任务ei的延缓时间，i 1,2.18；fi：任务ei可以缩短的最大工时，i 1,2.18；A：各个事件之间的结构矩阵；X：各个事件之间的关系矩阵；ESi：任务ei可以开始的最早时间，i 1,2.18；2EFi：任务ei可以完成的最早时间，i 1,2.18；LSi：任务ei在不增加耗时的情况下可以开始的最迟时间，i 1,2.18；LFi：任务ei在不增加耗时的情况下可以完成的最迟时间，i 1,2.18；：在不需要提前完工的前提下，最早完成此工程的时间；T ：在需要前提完工和公司获利最大的前提下，最早完成此工程的时间。3.2 名词

8、解释1. 关键路径：关键路径是指网络终端元素的元素的序列，该序列具有最长的总工期并决定了整个项目的最短完成时间。2. 直接前驱：每项任务对应的一组必须在该任务开始之前完成的任务。3. 直接后继：每项任务对应的一组必须在该任务完成之后才能开始的任务。4. 事件：事件的意义是表示以它为后继的任务已经完成，以它为前驱的任务可以开始。T四、问题分析4.1 问题一本文把所有任务按先决条件的相互关系绘制成双代号网络图， 以节点代表工程事件，以节点间的有向线段代表工程任务，绘制关系图。4.2 问题二根据题意， 本问是在不考虑缩短完成任务时间的情况下求解工程最短工期的问题，在第一问的基础上求解，即通过问题一转

9、换为求解此网络图关键路径的问题，关键路径上所有任务的时间总和就是此工程最早完工时间。可以采用线性规划和网络最短路径两种方法求解。4.2 问题三在第二问的基础上，第三问是一个计划网络优化问题。要想缩短工程工期，必须缩短关键路径上任务的耗时。 但是由于任务施工时间的缩短可能导致关键路径的改变，从而可能引发非关键路径缩短而浪费资源的问题，于是本文通过增加松驰变量来表示可能缩短的周数，以工程总时间的缩短为另一变量，通过设置目标函数为工 程 总 时 间 的 缩 短 奖 励 资 金任 务 缩 短 时 间 额 外 支 出 费 用，从而避免了此问题的发生。 依旧可通过两种方法的相互比较验证得到最优化的施工方案

10、。五、模型建立5.1 绘制工程双代号网络图本文重新把附录表一数据进行编码，将各任务用字母加下标代替，如附录表二所示，ei即表示第i个任务。据此我们需要绘出整个工程的计划网络图G。G是由一个非空有限集合V和V中某些有序对集合E构成的二元组，记为G (V , E)。其中V v1,v2.v13是图G的顶点集，即事件集合。E e1,e2.e18是图G的弧集，ei就表示第i个任务，即任务集合， 。3图中即用v1、v2、v3等表示事件，事件的意义表示前面的任务已经完成，后面的任务可以开始。任务用e1、e2、e3表示，标在箭线上（箭头的方向表示先决关系） ，同时任务相应的完成时间标也标在对应箭线上。事件v1

11、表示工程的开始，事件v13表示工程的结束，虚线表示工时为 0 的虚构的任务，仅用于表示各事件间的前行后继关系。我们在建立计划网络时遵循以下规则：（1）任何任务在网络中用唯一的箭线表示，任何任务其终点事件的编号必须大于其起点事件。（2）两个事件之间只能画一条箭线，表示一项任务。（3）任何计划网络图应有唯一的最初事件和唯一的最终事件。（4）计划网络图不允许出现回路。（5）计划网络图的画法一般是从左到右，从上到下，尽量作到清晰美观，避免箭头交叉。图一要求最早完成时间，即要求x13 x1时间最短，x13和x1分别表示工程开始时间和工程结束时间。5.2 问题二5.2.1 使用 Lingo 求解的数学模型

12、对于事件vi和vj( j i)有关系式xj xi tij就是指vi事件之后的vj事件的发生时间必需大于或等于vi事件的发生时间和事件vi与vj间的最长任务完成时间的和。由此可转化为数学规划问题4min x13 x1约束条件：xj xi tiji, j 1,2.13x 0, i 1,2.13i5.2.2 使用 MATLAB 求解的数学模型本问还可以采用另一种思路求解， 节点vi可以开始的最早时间是这个节点所有的紧前事件的最早开始时间加上其节点之间工程耗时的最大值， 故得到如下等式：ESj max ESi ei ji j（5.3）而节点vi的最迟开始时间，应该是其紧后工作的最早开始时间减去其事件之

13、间的工序耗时的最小值，即：LSi min LSj ei ji j（5.4）根据v1节点其最早开始时间为 0 的事实， 通过式 5.3 和 5.4 可以求出所有活动的最早开始时间和最迟开始时间，而只要到达v13节点，整个工程就完成了，故v13节点的最早开始时间和最迟开始时间相等，等于整个工程的完成时间，故得到目标方程：T ES13 LS13（5.5）5.3 问题三5.3.1 使用 Lingo 求解的数学模型增加了mi变量表示任务ei的最短完成时间，yi表示任务ei可能减少的时间以及ci表示任务ei缩短一周需要增加的费用，d表示优化后的完成周数。那么根据第一问的结果不优化前的最早完成时间为 64

14、周，我们设d为计划网络优化后的完成时间。于是总的获利可表示为3* (64 d ) ci* yi万元。目标为极大化3* (64 d ) ci* yi。事件vi与vj( j i)间的关系应是事件vj的开始时间减去事件vi的开始时间应大于原来两任务间最长任务的完成时间的tij的减去可能缩短的时间yi，即xj xi tij yi。同时，可能减少的时间yi应满足0 yi tij mi目标为极大化(3 * yi ciyi)。由此可得到相应的数学规划问题：5max(3 * yi ciyi)xj xi yi tijs.t.0 yi tij mi其中tij,i, j 1,2.13而xi, yi, mi,i 1,

15、2.185.3.2 使用关健路径求解的数学模型为了找到能使建筑公司获利的时间安排， 需要根据问题二中的关键活动和关键路径。关键路径的总耗时直接决定了整个工程项目的耗时， 如果要想缩短总工期的耗时，必须缩短关健路径上的工程事件的耗时。在考虑经济效益的方面，缩短时间的前提是获得更大的经济效益，所以只对额外支出费用小于等于 3 万元的项目进行增加额外支出来缩短时间。 从而可以实现在获得经济效益的同时而缩短工期。根据v13节点的最迟完成时间是工程完成时间的事实，分析可知，任务ei的延缓时间即为任务ei的最迟开始时间与最早开始时间的差值，即:bi LSi ESi (5.6)求得延缓时间后，通过分析同样可

16、以求得公司获利最大前提下各任务工期是怎样提前的，即确定fi。最后得到在公司获利最大前提下，完成此工程的时间为：T T fi（5.7）公司最大利润为：(3 fi)，i由分析确定 (5.8)六、模型求解6.1 问题二6.1.1 使用 Lingo 求解采用 Lingo9.0 软件进行规划求解。step1:将所有事件用(i, j)形式表示，与相应作业时间并同输入程序；step2:确定目标函数，min x13 x1;step3:编程求解（程序见附录） 。求得结果给出了各任务开工时间。其中，x1 0表示任务e1（工地布置）的开工时间是第 0周，x2 2表示任务e2的开工时间是第 2周，x5 26表示任务e

17、7,e1 0,e1 5的开工时间是第26周，等等。综合统计得下表。任务开工时间(周)6任务开工时间（周）e10218272637e8,e9,e11e13e12e16e17e18432852465463e2e3,e4,e14e5e7,e10,e15e6表一每个任务只要按要求得时间开工，则整个工程的最早完成时间为64周。6.1.2 使用 MATLAB 求解本问使用 MATLAB 求解的步骤如下建立各个几点的结构矩阵A，其元素aij表示节点i和节点j之间的工程项目。如果节点i和节点j之间没有工程项目，取aij的值为 0，否则取工程项目的耗时。于是得到了结构矩阵A：000000A 0000000200

18、00000000000160000000000000900000000000080000000000000100000000000000060000000000020000000000000090000000070003000000000000002000000000000009000000000103010建立关系矩阵X，其中的元素表示各个节点之间是否有项目连接：xij0,表 示 i, j之 间 无 项 目 连 接1,表 示 i, j之 间 有 项 目 连 接得到 13 个事件节点的关系矩阵：7000000X 00000001000000000000010000000000000100000

19、00000001000000000000011000000000000110000000000010000000000000010000000010001000000000000001000000000000001000000100101010根据结构矩阵和关系矩阵，结合公式（5.3）和（5.4） ，我们就可以得到各个节点时间的最早开始时间和最迟开始时间。程序见附录。各个节点事件的最早开始时间和最迟开始时间见下表：节点事件最早开始时间最迟开始时间时间差v102182726374328524654638021827373743525254546300001100240800v2v3v4v5v6v

20、7v8v9v10v11v12v1364表二640根据以上的结果可以得到节点事件v13的时间，即所有工程项目的完工的时间为 64 周。如果某项任务有正的延缓时间， 则该任务就有部分机动空间， 即稍微迟一点开始也不会使工程完成时间增加。然而，如果某项任务的延缓时间为0，则增加该任务的耗时将必然使工程完成时间增加。 因此， 关键路径由延缓时间为 0 的任务组成，即如下节点组成了关键路径：v1 v2 v3 v4 v6 v7 v9 v11 v12 v13关键路径所对应的关键活动为：e1 e2 e3 e5 e6 e9 e12 e17 e186.1.3 结果比较两种方法求解结果完全相同，最短工期为 64 周

21、，工程任务开工时间安排见表一。6.2 问题三6.2.1 使用 Lingo 求解对于第二问我们引入了一个参数mi， 用以表示任务ei的最短完成时间。mi的求解由原来的完成时间tij减去相应任务的最大缩短时间。Step1:根据任务作业时间tij和最大缩短时间计算最短完成时间mi；Step2:输入所有任务ei和对应tij及mi，任务ei以有向线段的方式输入，且保证j i；Step3:确定目标函数与约束条件；Step4: 运行程序求解（程序见附录） 。结果中的xi表示事件i的开始时间，tij表示优化后的任务作业时间，yi表示任务ei缩短的时间。最后的结果表明公司最大可获利 8.7 万元，工程可缩短到5

22、7 周完成。但由于任务e2的额外开支为 3 万元，正好等于缩短一周的收入，且任务e2在关键路径上，所以在用软件求解时未将其考虑为缩短时间的任务，于是分析得最好的结果是将任务e2的时间缩短到 13 周。综合得到表三计划：任务e2e3e5e6e7e11e17开始时间(周)完成时间(周)缩短时间(周)额外开支(万)2133915233123364788512791211132.63.41.50.81.84.8表三公司最大获利 8.7 万元，工程工期缩短至 54 周。6.2.2 使用 MATLAB 和关键路径求解通过对问题三的分析，可以得到需要对关键路径上的关键活动来缩短时间，使整体工期缩短，考虑到经

23、济效益，只对额外支出少于 3 万元的进行选择性的缩短。在对工程缩短时，考虑到关键路径可能发生改变，先假设工程时间缩短的同时，关键路径不发生改变。可以列如下表格进行计算：市政奖励-额最大缩短每周额外支出是否进行缩短周数关键活动外支出（万/时间单位（万）缩短（周）周）e1031212030-32.61.71.54.2-1.6-盈利-00.41.31.5-1.2-1.4-是是是是否-是-3121-3-缩短时间e2e3e5e6e9e12e17e18总计3*0+1*0.4+2*1.3+1*1.5+3*1.4=8.7 万元表四10 周通过列表计算，可以得到对大的缩短周期为 10 周，其中e2可以根据实际需

24、要选择是否缩短，不影响盈利。体育馆建设的项目最早可以再 54 周完成。考虑到在对工程项目进行缩短的过程中，可能影响到关键路径的改变。需要对缩短后的关键路径进行验算。缩短时间后的结构矩阵A：10000000A 00000002000000000000013000000000000080000000000008000000000000080000000000000050000000000020000000000000090000000070003000000000000002000000000000006000000000103010将得到的新矩阵带入到 6.1.2 中的程序中得到的节点事件最早开

25、始时间最迟开始时间v1时间差00008002008000021523233136254539475354表五021523313136454547475354v2v3v4v5v6v7v8v9v10v11v12v1311通过新的结构矩阵进行计算，可以得出总的工期为 54 周，与表格计算的结果一致。得出的关键路径为：v1 v2 v3 v4 v6 v7 v9 v11 v12 v13关键活动为：e1 e2 e3 e5 e6 e9 e12 e17 e18说明，经过对某些工程缩短后，仍然是关键路径，在缩短的过程中没有发生关键路径变化， 即在工期缩短的过程中， 每一周的时间缩短， 都直接使整个工期缩短。 。由

26、表四的结果，可知延缓时间为 0 的任务下标为：1，2，3，5，6，9，12，17，18，加快这些任务可以使得总工程能提前完成。但由题可知任务 9 提前一周完工的额外开支为 4.2 万元，大于奖励3 万元，故不加快任务9。而任务2 提前一周完工的额外开支为 3 万元， 等于奖励 3 万元， 若是出于考虑到实际生活中要临时雇用更多的工人及租用设备等问题，则不加快任务 2；若只考虑让完工时间最短，则加快任务 2。由于任务 1，12，18 的最大缩短时间为 0，故这两项任务也不能加快。综上所述，可以加快的任务有：e2,e3,e5,e6,e17。其中从不同的角度出发，任务e2可加快，也可不加快。经计算得

27、在不加快任务e2的前提下：T 64 1 2 1 3 57周。在加快任务e2的前提下：T 64 3 1 2 1 3 54周。两种情况下可获得的额外利润都为:3 2.6 2*3 1.7 3 1.5 3*3 1.6 8.7万元。6.2.3 结果比较两种方法求解出的结果完全相同，公司最大可获利 8.7 万元，工期缩短为54 周，工程任务安排见表三。七、模型的评价和改进本文是工程施工工期的优化问题，采用了网络模型进行优化，使用了两种求解方法解出了模型的最优解，通过比较得到了最优施工方案。本文使用模型简单高效，求解方法合理。采用两种方法比较使用，相互验证，也保证了结果的最优性。不过，对于工程来说，很多重要

28、因素例如非关键任务的最早开工时间、最迟开工时间等并未给出，由此，进一步的优化可将非关键任务完成后的人员、资源转投入其余未完工的任务中，由此可加快项目进程。12八八、参考文献参考文献1 姜启源，谢金星， 大学数学实验（第二版） ，清华大学出版社，北京，20102 韩中庚， 数学建模方法及其应用 ，高等教育出版社，北京，20063 运筹学教材编写组， 运筹学（第三版） ，清华大学出版社，北京，20074 魏宏博， 惠晓滨， 张凤鸣，一种求双代号网络图关键线路的简便矩阵算法 ，计算机工程与设计 ，第 25 卷，第 7 期，2004 年 7 月附录本问题数据附表：表格： 体育馆施工数据任务描述耗时先决

29、任务最大缩短时间每周额外支出单位（万）1工地布置2没有02场地平整161333打地基9212.64通路及其他道路网络8221.25底层施工10321.76主场地施工64,511.57划分更衣室2410.88看台电气布置2609顶部施工94,624.210照明系统5412.111安装阶梯看台3611.812封顶29013更衣室17014建造售票处7222.215第二通路44,1421.216信号设施38,11,141617草坪与附属运动设施91231.618交付使用1170重新编号后的数据表：任务描述工地布置e1表格： 体育馆施工数据耗时先决任务最大缩短时间201698e1每周额外支出单位（万）

30、32.61.2e2e3e4场地平整打地基通路及其他道路网络312e2e213e5e6e7e8e9e10底层施工主场地施工划分更衣室看台电气布置顶部施工照明系统安装阶梯看台封顶更衣室建造售票处第二通路信号设施草坪与附属运动设施交付使用106229532174391e3e4，e5e4e6e4，e6e4e6e9e7e2e4，e14e14e8，e11，e12e17211021100221301.71.50.84.22.11.82.21.261.6e11e12e13e14e15e16e17e18表二问题二 MATLAB 程序代码：%A为结构矩阵A=0 2 0 0 0 0 0 0 0 0 0 0 0; 0

31、 0 16 0 0 0 0 0 0 0 0 0 0; 0 0 0 9 8 0 0 0 0 7 0 0 0; 0 0 0 0 0 10 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 2 0 0 0 0 5; 0 0 0 0 0 0 6 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 9 3 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 1; 0 0 0 0 0 0 0 0 0 0 2 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 3; 0 0 0 0 0 0 0 0 0 0 0 9 0; 0 0 0 0 0 0 0 0 0 0 0 0 1;14

32、0 0 0 0 0 0 0 0 0 0 0 0 0;%X为关系矩阵X=0 1 0 0 0 0 0 0 0 0 0 0 0; 0 0 1 0 0 0 0 0 0 0 0 0 0; 0 0 0 1 1 0 0 0 0 1 0 0 0; 0 0 0 0 0 1 0 0 0 0 0 0 0; 0 0 0 0 0 1 1 1 0 0 0 0 1; 0 0 0 0 0 0 1 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 1 1 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 1; 0 0 0 0 0 0 0 0 0 0 1 0 0; 0 0 0 0 0 0 0 0 0 0 0

33、0 1; 0 0 0 0 0 0 0 0 0 0 0 1 0; 0 0 0 0 0 0 0 0 0 0 0 0 1; 0 0 0 0 0 0 0 0 0 0 0 0 0;%ES最早开始时间矩阵ES=zeros(13,1);for inum=2:13 t=0;for jnum=1:inumif X(jnum,inum)=0if tLS(jnum,1)-A(inum,jnum); t=LS(jnum,1)-A(inum,jnum);endendend LS(inum,1)=t;end15%S为寻找关键路径S=find(LS-ES)=0);问题二的LINGO程序：model:sets:events/

34、1.13/:x;operate(events,events)/1 2,2 3,3 4,3 5,3 10,4 6,5 6,5 7,5 8,5 13,6 7,79,7 10,8 13,9 11,10 13,11 12,12 13/:t;endsetsdata:t=2 16 9 8 7 10 0 0 2 5 6 9 3 1 2 3 9 1;enddatamin=x(13)-x(1);for(operate(i,j):x(j)x(i)+t(i,j);End问题三 Lingo 程序：model:sets:events/1.13/:x;operate(events,events)/1 2,2 3,3 4,

35、3 5,3 10,4 6,5 6,5 7,5 8,5 13,6 7,79,7 10,8 13,9 11,10 13,11 12,12 13/:t,m,c,y;endsetsdata:t=2 16 9 8 7 10 0 0 2 5 6 9 3 1 2 3 9 1;c=0 3.0 2.6 1.2 2.2 1.7 0 0 0.8 2.1 1.5 4.2 1.8 0 0 0.6 1.6 0;m=2 13 8 6 5 8 0 0 1 4 5 7 2 1 2 2 6 1;enddatamax=3*(64-d)-sum(operate:c*y);for(operate(i,j):x(j)-x(i)+y(i,

36、j)t(i,j);n=size(events);x(n)-x(1)d;for(operate:bnd(0,y,t-m);End求解结果： Global optimal solution found. Objective value: 8.700000 Total solver iterations: 0 Variable Value Reduced Cost16 D 57.00000 0.000000 N 13.00000 0.000000 X( 1) 0.000000 0.000000 X( 2) 2.000000 0.000000 X( 3) 18.00000 0.000000 X( 4)

37、 26.00000 0.000000 X( 5) 26.00000 0.000000 X( 6) 34.00000 0.000000 X( 7) 39.00000 0.000000 X( 8) X( 9) X( 10) X( 11) X( 12) X( 13) T( 1, 2) T( 2, 3) T( 3, 4) T( 3, 5) T( 3, 10) T( 4, 6) T( 5, 6) T( 5, 7) T( 5, 8) T( 5, 13) T( 6, 7) T( 7, 9) T( 7, 10) T( 8, 13) T( 9, 11) T( 10, 13) T( 11, 12) T( 12,

38、13) M( 1, 2) M( 2, 3) M( 3, 4) M( 3, 5) M( 3, 10) M( 4, 6) M( 5, 6) M( 5, 7) M( 5, 8) M( 5, 13) M( 6, 7) 42.00000 50.00000 56.00000 57.00000 7.000000 5.000000 3.000000 1.000000 2.000000 3.000000 9.000000 1.000000 5.000000 4.00000017 28.00000 0.000000 48.00000 0.000000 0.000000 0.000000 0.000000 0.00

39、0000 2.000000 0.000000 16.00000 0.000000 9.000000 0.000000 8.000000 0.000000 0.000000 10.00000 0.000000 0.000000 0.000000 0.000000 0.000000 2.000000 0.000000 0.000000 6.000000 0.000000 9.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 2.000000 0.000000 13.00000 0.000000 8.00000

40、0 0.000000 6.000000 0.000000 0.000000 8.000000 0.000000 0.000000 0.000000 0.000000 0.000000 1.000000 0.000000 0.000000 5.000000 0.000000 M( 7, 9) 7.000000 0.000000 M( 7, 10) 2.000000 0.000000 M( 8, 13) 1.000000 0.000000 M( 9, 11) 2.000000 0.000000 M( 10, 13) 2.000000 0.000000 M( 11, 12) 6.000000 0.0

41、00000 M( 12, 13) 1.000000 0.000000 C( 1, 2) 0.000000 0.000000 C( 2, 3) 3.000000 0.000000 C( 3, 4) C( 3, 5) C( 3, 10) C( 4, 6) C( 5, 6) C( 5, 7) C( 5, 8) C( 5, 13) C( 6, 7) C( 7, 9) C( 7, 10) C( 8, 13) C( 9, 11) C( 10, 13) C( 11, 12) C( 12, 13) Y( 1, 2) Y( 2, 3) Y( 3, 4) Y( 3, 5) Y( 3, 10) Y( 4, 6) Y

42、( 5, 6) Y( 5, 7) Y( 5, 8) Y( 5, 13) Y( 6, 7) Y( 7, 9) Y( 7, 10) Y( 8, 13) Y( 9, 11) Y( 10, 13) Y( 11, 12) Y( 12, 13) 2.600000 1.200000 2.200000 1.700000 0.000000 0.000000 0.8000000 2.100000 1.500000 4.200000 1.800000 0.000000 0.000000 6.000000 1.600000 0.000000 0.000000 0.000000 1.000000 -0.4000000

43、0.000000 0.000000 2.000000 0.000000 0.000000 0.000000 0.000000 1.000000 0.000000 0.000000 0.000000 0.000000 0.000000 3.000000 0.00000018 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 -3.000000 0.000000

44、1.200000 2.200000 -1.300000 0.000000 0.000000 0.8000000 2.100000 -1.500000 1.200000 1.800000 0.000000 6.000000 -1.400000 -3.000000 -3.000000 Row Slack or Surplus Dual Price 1 8.700000 1.000000 2 0.000000 -3.000000 3 0.000000 -3.000000 4 0.000000 -3.000000 5 0.000000 0.000000 6 17.00000 0.000000 7 0.

45、000000 -3.000000 8 8.000000 0.000000 9 13.00000 0.000000 10 0.000000 11 26.00000 12 0.000000 13 0.000000 14 0.000000 15 28.00000 16 0.000000 17 12.00000 18 0.000000 19 0.000000 20 0.000000 21 0.00000019 0.000000 0.000000 -3.000000 -3.000000 0.000000 0.000000 -3.000000 0.000000 -3.000000 -3.000000 0.000000 3.000000