《一类运输问题的非线性规划模型(共10页).doc》由会员分享，可在线阅读，更多相关《一类运输问题的非线性规划模型(共10页).doc（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上一类运输问题的非线性规划模型摘要 经典的运输问题是已知各条路径长度和目的地的需求量, 求最优的运输路径, 这只需要建立线性规划模型就可以解决了. 但实践中遇到的情况常常不是那么简单, 一是路费并不与路线长度成简单线性关系, 再就是目的地的需求量不是已知, 还有货物的价格等等因素都增加了问题的复杂性. 本文就以钢管定购和运输问题为例,禅述了一类复杂运输问题的解决方案.关键词 数学模型, 非线性规划, 最省路径1 问题简述要铺设一条A1A2A15的输送天然气的主管道, 如Error! Reference source not found.所示. 附近有7个钢厂S1, S2
2、, S7可以生产这种主管道钢管. 图中粗线表示铁路, 单细线表示公路, 双线表示要铺设的管道(假设沿管道或者原来有公路, 或者建有施工公路), 圆圈表示火车站, 每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km).为方便计, 1km主管道钢管称为1单位钢管.一个钢厂如果承担制造这种钢管, 至少需要生产500个单位.钢厂Si在指定期限内能生产该钢管的最大数量为si个单位, 钢管出厂销价1单位钢管为Pi万元, 如Error! Reference source not found.表1 钢厂产量及单价i1234567si80080010002000200020003000Pi1601551551
3、601551501601单位钢管的铁路运价如Error! Reference source not found. 表2 铁路运价里程300301350351400401450451500运价(万元)2023262932里程5016006017007018008019009011000运价(万元)37445055601000km以上每增加1至100km运价增加5万元.公路运输费用为1单位钢管每公里0.1万元.钢管可由铁路、公路运往铺设地点(不只是运到A1, A2, A15,而是管道全线).1. 请制定一个主管道钢管的订购和运输计划,使总费用最小(给出总费用).2. 如果要铺设的管道不是一条线,
4、而一个树形图, 铁路、公路和管道构成网络, 请就这种更一般的情形给出一种解决办法, 并对Error! Reference source not found.按问题Error! Reference source not found.的要求给出模型和结果.图 1 钢管运输路线图(1)图 2 钢管运输路线图(2)2 问题分析为了求出定购计划, 首先应该知道从各钢厂到各铺设路段运送单位钢管所需费用最小的路径. 为此, 我们定义：定义 使得从钢厂Si运送单位钢管到铺设端点Aj的费用最小的路径称为从Si到Aj的最省路径.如果可以预先知道运往各铺设端点的钢管量, 那么原问题就是一个纯粹的运输问题, 而运输问
5、题已经有着比较成熟的解法Error! Reference source not found. 然而我们遇到的并非如此简单. 各铺设端点只有一个相当大的取值范围（而不是一个确定的值）, 确定这些值只能由运输和铺设的限制条件以及费用极小来决定.由于需铺设的总长度是相当长的, 而一根钢管的长度相对来说就小得多, 所以可以认为：从铺设端点运送钢管到铺设地点时, 钢管是连续不断、均匀地卸下的.基于以上原因, 我们决定, 首先求出各钢厂到各铺设端点的最省路径, 然后根据限制条件和费用极小建立连续型规划模型, 最后求出整个购运计划.3 模型假设1. 施工公路与普通公路路况一样.2. 在实际运输时, 经过的路
6、径不会出现这样的情况：公路夹于两段铁路之间, 或铁路夹于两段公路之间.3. 在实际运输时, 总是这样来运输的: 先运往铺设端点(指A1, A2, .)再运到铺设地点.4. 铺设是均匀、连续的, 卸货也是均匀、连续的.在后面的论述中, 我们总是假设所有的钢管量以km为单位, 所有的费用以万元为单位.4 模型建立首先, 我们针对Error! Reference source not found.建立数学模型.4 1 最省路径容易知道, 要使总费用最小, 所走的路径就应该是最省路径. 所以我们首先求出各条最省路径.对于在一般赋权图中求最短路径问题已有许多成熟的方法, 可以运用到这里. 但由于铁路费用
7、比较特殊（单位路长费用不是定值）, 所以必须做些特殊处理. 经过观察我们发现, Error! Reference source not found.中所有铁路及火车站构成一颗树, 要把钢管从任一钢厂运至铺设地点上都必须至少经过一个交接点(Bi), 再根据假设2, 每一次运输只能经过一个交接点. 这样, 在一次运输中, 经过的铁路将是连接出发点(钢厂)和交接点的那条通路. 不妨把它们直接用铁路连起来. 这样我们可以按照如下方法构造新图：1. 在Error! Reference source not found.中将所有的钢厂与交接点全部用铁路连接起来, 铁路长度与Error! Reference
8、 source not found.中相应的铁路总长度一样. 如果某个点既是钢厂又是交接点, 则把它们拆成两个点, 一个代表钢厂, 一个代表交接点, 它们之间的铁路长度赋值为0. 2. 略去Error! Reference source not found.中的铁路及火车站(除交接点外).这样就得到一个新图, 重新摆放各点的位置后的形状如Error! Reference source not found.图 3 与Error! Reference source not found.等效的简化图我们给Error! Reference source not found.的所有边都赋予边权, 它们的
9、值是运送单位钢管经过该边的费用(而不是路的长度).在此必须说明的是, 在假设2的前提下, Error! Reference source not found.与Error! Reference source not found.是等效的. 等效的意思是指：在Error! Reference source not found.中从任何一个钢厂走到任何一个铺设点, 不管所走的是哪一条路, 在Error! Reference source not found.中都有唯一的路径与之相对应, 并且费用相等. 这样, Error! Reference source not found.中的所有的边权值都可
10、以从Error! Reference source not found.及铁路、公路运价求出. 譬如, S1B1=160, B1A2=0.3, A1A2=10.4. 由于篇幅关系, 在此不再一一给出.Error! Reference source not found.是一个典型的赋权图, 可用Dijkstra算法2、逐次逼近法3等算法求出从Si到Aj的最省路径和相应费用, 在此我们采用逐次逼近法. 为节省篇幅, 结果在此将不给出, 读者可自行计算, 程序可参见Error! Reference source not found.2 目标函数(费用表达式)设从钢厂Si运往铺设端点Aj的钢管量为xi
11、j, 那么, 购买费用为用wij表示从Si到Aj的最省路径相应的费用, 则运输过程中的费用为因为钢管运到铺设端点Aj后, 还要运往铺设地点. 在Error! Reference source not found.中, 铺设端点的度最大为2, 所以每个端点运送的方向最多有2个, 可设Aj向左运送的钢管量为Lj, 向右运送的钢管量为Rj, 显然有(1)再由假设Error! Reference source not found., 卸货是均匀的, 当从铺设端点Aj向左运输钢管走了t km时, 剩余在车上的钢管量为Ljt, 所以将钢管运至Aj后再向左运输需要的费用其中e是运输1单位钢管每公里的公路运费
12、.同理, 将钢管运至Aj后再向右运输需要的费用因此这期间的总费用为购买费用、从钢厂运往铺设端点的费用、从铺设端点运至铺设地点的费用构成了全部费用的总和.所以, 总费用为 (2)43 约束条件根据需铺设的钢管总长度为5171, 而且运输量总是非负的, 所以(3)再根据假设4, 铺设是均匀的(不重叠不遗漏), 所以有 (4)其中表示从到需要铺设钢管的长度.由于钢厂Si的产量上限为si, 所以 (5)而每个钢厂都有自己的产量下限. 如果生产, 则必须不小于500, 否则就不生产, 产量为0. 即 (6)为了方便求解, 我们将上式改写成如下等价形式(在产量非负的条件下): (7)44 数学模型由(1)
13、、（2）、（3）、（4）、（5）、（6）、（7）可以得到一个连续非线性规划模型:S. T. , R15=0, L1=0. xij0, i=1,7, j=1,15.这就是我们所要建立的钢管购运计划数学模型.5 模型求解这是一个非线性规划模型. 由于模型中变量太多, 人工求解很难进行. 我们使用数学软件LINGO6.0, 成功地求解了这个模型, 从而得到了完整的购运计划. 首先是去钢厂购买钢管的计划, Error! Reference source not found.列出了具体的购买方案, 所花费用=; 然后是将钢管运至铺设端点, 运输方案也在Error! Reference source no
14、t found.中给出, 运输费=.55; 最后是把钢管从铺设端点运到铺设地点,Error! Reference source not found.给出了运输方法, 运输费. 这样总费用就是. 表 3 在Error! Reference source not found.中从钢厂购买钢管然后运到铺设端点的计划钢厂购买量购买费用运输路径(在Error! Reference source not found.中)运量xij单价运费S1800.0S1B6B5B4A5334.538.012711.0S1B6B5A6200.020.54100.0S1B7A7265.53.1823.05S2800.0S2
15、B8B3B1A2179.0205.336748.7S2B3A4134.1171.623011.56S2B8B7B6B5B4A5186.9111.020745.90S2B8A8300.071.221360.00S31000.0S3B9B8B7B6B5B4A5 A4333.9181.660636.24S3B9B8B7B6B5B4A52.1121.0254.10S3B9A9664.048.232004.80S40.00无0.00.0S51015.0S5B11B10B9B8B3B2 A3508.0225.2.60S5B11B10B9B8B7B6B5B4A592.0146.013432.00S5B11A
16、11415.033.013695.0S61556.0S6B15B13B10A10351.062.021762.00S6B15B13B12A1286.045.03870.00S6B15B13A13333.026.28724.60S6A14621.011.06831.00S6B15B16A15165.028.04620.00S70.00无0.00.0合计5171.0 = 5171.0=.55表 4 从铺设端点到铺设地点的计划j12345678Lj0.0104.0226.0468.0606.0184.5189.5125.0Rj0.075.0282.00.09.515.576.0175.0费用0.08
17、22.056530.010951.218366.31251714.0252084.31252312.5j9101112131415合计Lj505.0321.0270.075.0199.0286.0165.0Rj159.030.0145.011.0134.0335.00.0费用14015.35197.054696.25287.32877.859701.051361.2580916.456 模型强化如果要铺设的管道不是一条线, 而是一个树形图, 铁路、公路和管道构成网络, 我们的方法同样是适用的, 因为在求最省路径时, 我们并不排除铁路、公路和管道构成网络的情形.实际上, Error! Refer
18、ence source not found.与Error! Reference source not found.的差别主要是铺设端点的度数不同. 因此, 只要对第一个模型稍作修改, 就可以解决这种更一般的情形了.对Error! Reference source not found.运用相同的方法进行改造, 得到的新图如Error! Reference source not found.所示, 其中的边权可以根据Error! Reference source not found.求出.图 4 与Error! Reference source not found.等效的简化图在Error! Re
19、ference source not found.中, 铺设路径上的结点的最大度数为3, 从结点运往铺设地点的方向数最多有3个, 分别用D1j, D2j, D3j表示从Aj运往三个方向的运量, 各方向的取法如下(其中的方向都是指在图4中的方向): i) 如果结点Aj的度为1, 说明从该结点运出的方向只有一个, D1j就是这个方向上的运量, 并且令D2j=0, D3j=0. 这样的结点有A1, A15, A16, A18, A21.ii) 如果结点Aj的度为2, 说明从该结点运出的方向有两个, D1j表示向左方向的运量, D2j表示向右方向的运量, 并且令D3j=0. 这样的结点有A2, A3,
20、 A4, A5, A6, A7, A8, A10, A12, A13, A14, A19, A20.iii) 如果结点Aj的度为3, 则D1j表示向左方向的运量, D2j表示向右方向的运量, D3j表示向下的运量. 这样的结点有A9, A11, A17.用类似于前面建立模型的方法对问题三建立模型如下: S.T. , , xij0, i=1,7, j=1,21.求解以上模型得到Error! Reference source not found.、Error! Reference source not found.的购买和运输计划. 由此可知=, =.55, =86087.15, 总费用=.70.
21、表 5 在Error! Reference source not found.中从钢厂购买钢管然后运到铺设端点的计划钢厂购买量购买费用运输路径(在Error! Reference source not found.中)运量xij单价运费S1800.0S1B6B5B4A5334.538.012711.0S1B6B5A6200.020.54100.0S1B7A7265.53.1823.05S2800.0S2B8B3B1A2179.0205.336748.7S2 B8B3B2A3321.0190.261054.20S2B8A8300.071.221360.00S31000.0S3 B9B8B3B2A
22、380.0200.216016.00S3 B9B8B7 B6B5B4A5214.0121.025894.00S3B9A9664.048.232004.80S3A1642.044.01848.00S40.00无0.00.0S51613S5 B11B10B9B8B3B2A3107.0225.224096.40S5 B11B10B9B8B7 B6B5A5A4468.0206.696688.80S5 B11B10B9B8B7 B6B5A567.0146.09782.00S5 B11B10A10351.057.020007.00S5B11A11415.033.013695.00S5A17205.032.
23、06560.00S61690.0S6 B13B18B12A1286.045.03870.00S6B13A13333.016.25394.6S6A14621.011.06831.00S6B15B16A15165.028.04620.00S6B13A1865.037.02405.00S6B15B13B18A1970.044.03080.00S6A20250.010.02500.00S6A21100.00.00.0S70.00无0.00.0合计5903 = 5903=.55表 6 从铺设端点到铺设地点的计划j1234567891011D1j0.0104.0226.0468.0606.0184.518
24、9.5125.0505.0321.0270.0D2j0.075.0282.00.09.515.576.0175.0159.030.0145.0D3j0.00.00.00.00.00.00.00.00.00.00.0费用0.0822.05653010951.218366.31251714.0252084.31252312.514015.35197.054696.25j12131415161718192021合计D1j75.0199.0286.0165.042.010.065.060.0250.0100.0D2j11.0134.0335.00.00.065.00.010.00.00.0D3j0.0
25、0.00.00.00.0130.00.00.00.00.0费用287.32877.859701.051361.2588.21061.25211.25185312550086087.157 模型评价本文所讨论的问题用线性规划来求解是无法得到满意结果的, 这主要是因为钢管从铺设端点运往铺设地点时的运费不与路长成线性关系, 为此我们建立二次规划模型, 为的是真实反映实际操作中的各种条件限制和费用, 结果是合理可用的. 虽然我们求解的只是一个特定的实际问题, 但其中的方法具有一般性, 容易推文到类似的问题中. 如果只是运输路线图的不同, 则只需修改相应数据就可以了.参考文献1. 张莹. 运筹学基础,
26、清华大学出版社, 1999.1: 52-53.2. 戴一奇等. 图论与代数结构, 清华大学出版社, 1995.8.3. 胡运权. 运筹学教程, 清华大学出版社, 1998.6: 238-239.4. 楼世博, 金晓龙, 李鸿祥. 图论及其应用, 人民邮电出版社, 1982.7: 437-439.A Continuum and Nonlinear Programming Model of Transport ProblemHe Dengxu1 Cao Dunqian1 Mo Yongxiang2 Song Xueqiang1(1. Dept. of Math. and Computer Scie
27、nces, Guangxi University for Nationalities, Nanning, , China2. Dept. of Computing Science and Applied Physics , Guilin University of Electronic Technology, Guilin, , China)Abstract: The classical problem of transport is asked to find the shortest path in base of knowing all kind paths lengths and de
28、mand at destination. It only needs to set up linear programming model, but in practice all kind of factors such as cost of transport nonlinear with lengths of paths, not knowing demand and cost of goods, augment complexities of the problem. In this paper, we expound a approach how to solve a complex problem of transport through the problem of order and transport of steel and tube.Keyword: mathematical model, nonlinear programming, shortest path专心-专注-专业