550 全国大学生数学建模竞赛优秀论文汇编 经过这一变换,问题大大简化,下面将原问题用纯数学语言做一个描述 3.3问题的数学描述 常量:R:第i个工厂的钢管单价,L;:第i个工厂的产量上限 变量表:S,SAQa,A,AAQ min(cl+c2+ c3) cl=∑s,×R c2=∑∑sAQn×SAPn c3=∑∑(AAQ4×(AQ2+1)2) j1k-1 S=∑SAQ1 SA 1AQi AAQi= Pr S4<=L S;=0orS;>=500 4问题的求解 上面的数学描述中,最难处理的是S=0orS1>=500这个条件,求解过程分为三步 A.假设工厂的产量只有上限,下面的三个流网络模型都是针对这种情况的 B.假设工厂的产量有上下限,“产量有下限的模型”一节讨论这种情况 C.工厂的产量∈0,[500,Li],“基于分支定界搜索的求解过程”一节讨论这种情况 4.1线性费用流网络模型 下面建立一个线性费用流网络的模型(图1): 图中边上的(A,B),A表示边的流量限制,B表示边的单位流量的费用,下同 1)网络有一个源点 Source,从 Source到每个S点有一条边,边的流量限制为Si的最大 产量Li,单位费用为S生产钢管的单价R 2)从S到A有一条边,边的流量限制为+∞,单位费用为SAP,即从S到A,运输 单位长度钢管的费用 3)对于每一条要铺设的管道P,设其长度为Len,两端点为A,A,则P对应着Lemn个 点,分别表示要铺设的一个单位长度的钢管(如图中Pn,P12,P3),从A,到这Len个点各 有一条边,边的流量限制为1,单位费用分别为1,2,3…,Ln,从Ak到这Len个点也各有 条边,边的流量限制为1,单位费用分别为Le,Len-1,…3,2,1. 4)从3)中的点(代表每单位长度的钢管的点)到图的汇点 Target各有一条边,流量限
钢的订购和运输解答模型 551 Source层 (L4R1) (+∞,SAP) A层 (1,D(1,2.(1,3) P层@@@@ Target层 图1线性费用流网络模型一 制为1,单位费用为0 这种流网络模型最简单,效率也较低.设铺设的管道共有T公里,显然T1>>n与 m.网络中的点数大约为T个,边数大约为3×T,最大流量为T1.标准的网络流算法的 时间复杂度为O(V3× MarLo),因此,这个模型的复杂度为O(Tl4).对于题中的数据, Tl大约在5000左右,T≈1015,不可承受 4.2线性费用流网络模型二(图2) Source层 (Li Ri (+∞,SAP) A层 (1,D(1,2)(1,3) P层 Target层 图2线性费用流网络模型二