《网络最优化的运输问题和分配问题》由会员分享，可在线阅读，更多相关《网络最优化的运输问题和分配问题（16页珍藏版）》请在金锄头文库上搜索。
1、网络最优化中的运输分配问题甘养于LINGO项目单位：13 统计二班摘要网络在各种实际背景问题中以各种各样的形式存在，交通、电子和通信网 络遍布日常生活的各个方面，所产生的网络优化也广泛用于解决不同领域中的各 种问题，如生产、分配、项目计划、厂址选择、资源管理和财务策划等，实际上， 网络规划为描述系统各组成部分之间的关系提供了非常有效的直观和概念上的 帮助，广泛用于科学、社会和经济活动的每个领域中。网络优化问题在处理管理问题时特别有用，由于许多网络优化问题实质上是 线性规划问题的特殊类型。运输问题是网络优化中典型的应用。运输问题是社会经济生活中经常出现的 优化问题，是特殊的线性规划问题，它是早期
2、的线性网络最优化的一个例子。运 输问题不仅代表了物资合理调运、车辆合理调度等问题，有些其他类型的问题经 过适当变换后也可以归结为运输问题，如指派问题、最短路问题、最小费用流问 题可转化为运输问题或转运问题。所以，我们小组一起研究分析了一些实际的应用如何以最优的的方式进行问 题的解决。基于LINGO算法，我们进行了区域划分方面的最优处理。关键词：网络优化；统计计算；运筹学；运输优化问题；LONGO软件；区 域划分最优化。目录一、运输问题 41、问题描述 42、数据准备 43、模型设计 54、补充说明 55、决策分析 76、分析结果 10二、分配问题 101、问题分析 102、数据准备 113、决
3、策分析 124、分析结果 15总结15四、附录161、参考文献162、人员分配16第一节运输问题一、问题描述例：区域划分问题例：某城区开办了三所中学，现需为每一所学校重新划定在这个城区内的服 务区域，在初步的计划中，这个城区被分成了拥有大致相同数量人口的九个区城 学区管理者认为划分入学区域界限的适当目标是W学生到手砭的平均路程最短， 在这个初步的计划之中，他们要确定为实现这一目标每一小区域内有多少学生手 安排到每一所学校中。问如何进行初步的划分?二、数据准备经过管理部门的统计和初步沟通，下表给出了每一所学校与每一个区域之间的近 似距离（单位；公里）。最右一列给出了明年每一个区域的高中学生数量（
4、这些数 字在未来几年之内估计会有缓慢的增长）。最下面的两行表示了每二所学校所能 够安排的最少和最多的学生数量。区域距离学校的距离学生数量1231234567892.2 1.92.51.4 1.31.70.51.81.11.2 0.32.00.90.71.01.11.60.62.7 0.71.51.8 1.20.81.5 1.70.7500400450400500450450400500最小招生数最大招生数1200 1100 1000180017001500三、模型设计设 x 为相应的分配学生数，由于每一所学校都有一个最大的和最小的学生容 ij量，因此数学模型为：艺Kcxij ijmin z =
5、 i=i j=1S.t. x = b（i=1,2,3,9）ij ij=1込 x min s （j=1,2,3）ijji=1区 x 0 且为整数 （i=1,2，9；j=1,2,3）ij其中，c表示区域i到学校j的单位距离；b （I）为各区域的高中学生数量；min ij与 max 表示学校最小和最大招生数。四、补充说明一般地，最优化问题可以叙述为：有某种物资需要调运，已知有找个地方可 以供应该种物资，有 n 个地方（简称销地）需要该种物资，又知这机个产地的可供 量（简称为产量）为ai（I=l,2,.机），n个销地的需求量（简称为销量）为与j 一 1,2, ，n）.从第I个产地到第j个销地的单位物资
6、运价为cij，在以上条 件下求总的运输方案使总的运费支出最小，若用ci歹代表从第i个产地调运给第j个销地的物资的单位数量，则问题的数 学模型为一个线性规划模型：min z = %丄 CijXiji=1js.t.(i=l,2, m)(j=l,2, n)厶 Xj bjXij 0i 1问题有解的相容性要求在模型中有込ai ybj.在产销平衡的条件下，此处i 1 j 1 相容性约束取等号，根据运输问题的数学模型可知，可用为最小费用流求解的方 法.对一般的转运问题，可把节点分成纯发点、纯收点及既可发又可收的转运点 三类，其运输问题模型的其他考虑还有：(1) 表示运输过程中损耗的增益系数，即上述中的中Xi
7、j变为aijXij。(2) 表示固定费用Fij的运输需求选择，即CijXij+YijFij,其中Yij=1,0表示 运输量发生与否。(3) 多目标化，如增加另一类目标要求总的运输时间为最短，即上述增加目标函 数为min z2 =込 工Tij (XijO其中ij)表示从第I个产地到第j个销地的时间函i 1 j数.(4) 某些运输需求的排他性选择，即 XijXkj=0 注意，可以通过 0-1 变量变为线 性约束，五、决策分析LINGO 的程序实现：model:!student entrance problem;sets:area/ 1.9/:b;school/1.3/:mins,maxs;link
8、s(area,school):c,x;endsetsdata: b=500,400,450,400,500,450,450,400,500; c=2.2,1.9,2.5,1.4,1.3,1.7,0.5,1.8 1.1,1.2,0.3,2.0,0.9,0.7,1.0,1.1,1.6,0.6,2.7,0.7,1.5,1.8,1.2,0.8,1.5,1.7,0.7; mins=1200,1100,1000; maxs=1800,1700,1500;enddata!the objective;!min=sum(area(i):sum(school(j):(c,j)*x(i,j); !the const
9、raints;for(area(i):sum(school(j):x(i,j)=b(i); for(school(j):mins(j)=sum(area(i):x(i,j); for(school(j):sum(area(i):x(i,j)=maxs(j); for(area(i):for(school(j):gin(x(i,j);endLINGO 运行结果：结果： Feasible solution found.Infeasibilities:0.000000Extended solver steps:Total solver iterations:19VariableValueB(2)40
10、0.0000B(3)450.0000B(4)400.0000B(5)500.0000B(6)450.0000B(7)450.0000B(8)400.0000B(9)500.0000MINS(1)1200.000MINS(2)1100.000MINS(3)1000.000MAXS(1)1800.000MAXS(2)1700.000MAXS(3)1500.000C(1,1)2.200000C(1,2)1.900000C(1,3)2.500000C(2,1)1.400000C(2,2)1.300000C(2,3)1.700000C(3,1)0.5000000C(3,2)1.800000C(3,3)1
11、.100000C(4,1)1.200000C(4,2)0.3000000C(4,3)2.000000C(5,1)0.9000000C(5,2)0.7000000C(5,3)1.000000C(6,1)1.100000C(6,2)1.600000C(6,3)0.6000000C(7,1)2.700000C(7,2)0.7000000C(7,3)1.500000C(8,1)1.800000C(8,2)1.200000C(8,3)0.8000000C(9,1)1.500000C(9,2)1.700000C(9,3)0.7000000X(1,1)0.000000X(1,2)0.000000X(1,3)500.0000X(2,1)0.000000X(2,2)0.000000X(2,3)400.0000X(3,1)0.000000X(3,2)350.0000X(3,3)100.0000X(4,1)0.000000X(4,2)400.0000X(4,3)0.000000X(5,1)0.000000X(5,2)500.0000X(5,3)0.000000X(6,1)450.0000X(6,2)0.000000X(6,3)0.000000X(7,1)450.0000X(7,2)0.000000X(7,
