4运输问题—数学模型及其解法4.1运输问题数学模型4.2运输问题的求解方法4.3对解进行检验及改进4.4运输问题的进一步讨论4.5应用问题举例P&T公司的配送问题案例CANNERY1BellinghamCANNERY2EugeneWAREHOUSE1SacramentoWAREHOUSE2SaltLakeCityWAREHOUSE3RapidCityWAREHOUSE4AlbuquerqueCANNERY3AlbertLeaFigure1LocationofthecanneriesandwarehousesfortheP&TCompanyproblem.运输数据CanneryOutputWarehouseAllocationBellingham75truckloadsSacramento80truckloadsEugene125truckloadsSaltLakeCity65truckloadsAlbertLea100truckloadsRapidCity70truckloadsTotal300truckloadsAlbuquerque85truckloadsTotal300truckloads目前的运输计划WarehouseFrom\ToSacramentoSaltLakeCityRapidCityAlbuquerqueCanneryBellingham75000Eugene565550AlbertLea001585卡车的运输成本WarehouseFrom\ToSacramentoSaltLakeCityRapidCityAlbuquerqueCanneryBellingham$464$513$654$867Eugene352416690791AlbertLea995682388685总的运输成本=75($464)+5($352)+65($416)+55($690)+15($388)+85($685)=$165,595运输问题的特点需求假设每一个出发地都有一个固定的供应量,所有的供应量都必须配送到目的地。每一个目的地都有一个固定得需求量,整个需求量都必须由出发地满足。可行解的特性当且仅当供应量的总和等于需求量的总和时,运输问题才有可行解。成本假设从任何一个出发地到任何一个目的地的货物配送成本和所配送的数量成线性比例关系。这个成本就等于配送的单位成本乘以所配送的数量。S1S2S3D4D2D1D37512510080657085SuppliesDemandsSourcesDestinations(Bellingham)(Eugene)(AlbertLea)(Sacramento)(SaltLakeCity)(RapidCity)(Albuquerque)464513654867352416690791995682685388网络表示4.1运输问题的一般数学模型有m个产地生产某种物资,有n个地区需要该类物资令a1,a2,…,am表示各产地产量,b1,b2,…,bn表示各销地的销量,ai=bj称为产销平衡设xij表示产地i运往销地j的物资量,wij表示对应的单位运费,则我们有运输问题的数学模型如下:0,,2,1,,2,1)(min1111ijjmiijnjiijminjijijxnjbxmiaxxcxf销量约束产地约束运输问题有mn个决策变量,m+n个约束条件。由于产销平衡条件,只有m+n–1个相互独立,因此,运输问题的基变量只有m+n–1个例1某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3,各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示,问:应如何调运可使总运输费用最小?B1B2B3产量A1646200A2655300销量150150200解:产销平衡问题:总产量=总销量设xij为从产地Ai运往销地Bj的运输量,得到下列运输量表:B1B2B3产量A1x11x12x13200A2x21x22x23300销量150150200Minf=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200x21+x22+x23=300x11+x21=150x12+x22=150x13+x23=200xij≥0(i=1、2;j=1、2、3)运输问题有有限最优解约束条件非常有规律,技术系数非0即1平衡运输问题数学模型特点111111111111111111m行n行每个变量Xij对应的矩阵列中,除第i个元素和第m+j个元素为1外,其余元素为零.每行有n个1,其余为0。所有结构的约束条件是等式约束各产地产量之和等于各销地销量之和运输问题的解解满足所有的约束条件;基变量对应的约束方程组的系数列向量线性无关;解中非零变量Xij的个数不能大于(m+n-1)个;为使迭代求解顺利进行,基变量的个数在迭代过程中保持为(m+n-1)个;基变量的个数远小于决策变量的个数.4.2运输问题的求解方法采用表上作业法,称为位势法运算中涉及两个表:运费表和产销平衡表(分配表)销地运费12n产地1c11c12c1n2c21c22c2nmcm1cm2cmn运费表分配表寻找初始可行解的方法1、西北角法从x11开始分配,从西北向东南方向逐个分配xij的分配公式列待分物资量列已分配的总量行尚余物资量行已分配的总量)()(minjjbiiaxjiij例2销地产量运费1234ai产地120113652591021031874115销量bj331212销地产量运量1234ai产地15210315销量bj331212例4.2.1西北角法销地产量运量1234ai产地13x125210315销量bj331212销地产量运量1234ai产地13252x2210315销量bj331212销地产量运量1234ai产地132521x2310315销量bj331212销地产量运量1234ai产地1325219103x3315销量bj331212销地产量运量1234ai产地13252191033x3315销量bj331212销地产量运量1234ai产地132521910331215销量bj3312123141205)(67ijijijxcxfnm个基变量有2、最低费用法采用最小费用优先分配的原则编号运费表{wij}分配表{xij}2011(3)6x135I5910210187411215331212编号运费表{wij}分配表{xij}20113655II5910210187(4)1x331215331212编号运费表{wij}分配表{xij}20113655III59(10)2334101874131215331212f(x)=121,费用比西北角法低843、运费差额法(沃格尔法-Volge)最小元素法初看十分合理。但是,有时按某一最小单位运价优先安排物品调运时,却可能导致对其它代销点配送时费用更高,从而使总费用增加。对每一个供销地或销售地,均可由它到各销售地到各供应地的单位运价中找出最小单位运价和次小单位运价,并称这两个单位运价之差为该供应地或销售地的罚数。若罚数的值不大,当不能按最小单位运价安排运输时造成的运费损失不大;反之,如果罚数的值很大,不按最小运价组织运输就会造成很大的损失,故应尽量按最小单位运价安排运输。采用最大差额费用(即利用每行或列中最小费用与次最小之间的差额中选最大)优先分配的原则。f(x)=98,比最低费用法又低了23编号运费表{wij}分配表{xij}20113635I5910233101874131513211331212编号运费表{wij}分配表{xij}20113635II59102737101874131513211331212编号运费表{wij}分配表{xij}20113635III591027371018741351513415331212编号运费表{wij}分配表{xij}201136855IV59102737101874133751513--5331212种某种物品先放在A1、A2和A3三个仓库中,再运往使用地B1、B2、B3和B4,其间的距离(或单位运价)如下表所示,各仓库的存量和使用地的需要量也都表示于下表中,试建立使总运输费用最小的运输问题数学模型。用前面讲的三种方法分别求可行解用上面的三种求下列运输问题的解销地产地B1B2B3B3产量A116A210A322销量81412144124112103985116表1用上面的三种求下列运输问题的解销地产地B1B2B3B3产量A18816A26410A381422销量81412144124112103985116用西北角法求的可行解表2412用上面的三种求下列运输问题的解销地产地B1B2B3B3产量A110616A28210A314822销量81412144124112103985116用最小元素法求的可行解表3用上面的三种求下列运输问题的解销地产地B1B2B3B3产量A112416A28210A314822销量81412144124112103985116用沃尔格法求的可行解表44.3对解的可行性进行检验运输表中的格子是空的,则代表是非基变量.若存在非基变量的检验数小于零,说明得到的解不是最优解!运输问题常用的解检验方法有2种:闭回路法;位势法销地产地B1B2B3B3产量A110616A28210A314822销量81412144124112103985116检验用最小元素法求的可行解(下表)是否最优表34.3.1利用闭回路法检验分配方案是否最优表3中的可行解用闭回路法计算的检验数销地产地B1B2B3B3产量A112A21-1A31012销量因X23的检验数小于0,表3的调运方案不是最优解4.3.2利用位势法检验分配方案是否最优思路:不采用单纯型法,如何获得xij的检验数找到原问题的基础可行解,保持互补松弛条件,求出对应对偶问题的解,若该对偶问题的解非可行,则原问题的解不是最优解;否则,达到最优解0,,2,1,,2,1)(min1111ijjmiijnjiijminjijijxnjbxmiaxxcxfnjmivucvuvbuavugjiijjinjjjmiii,,2,1,,,2,1,),(max11不限利用位势法检验分配方案是否最优平衡运输问题数学模型平衡运输问题的对偶问题3323132222121121112223222111131211232322222121131312121111vbxxvbxxvbxxuaxxxuaxxxxxxxxxcminccccc无限制321212332222221121331122111113322112211v,v,v,u,uvuvuvuvuvuvuvbvbvbuauamaxcccccc动输问题变量的检验数表示为:ijx)(,,,,,2121jiijijnmijijijijijijvucPvvvuuucYPczc设已得到运输问题的基可行解,其基变量是:1,,,,2211nmsxxxssjijiji由于基变量的检验数等于0,故对于这组基变量可写出议程组:ssssjijijijijijicvucvucvu22221111可以证明上面的方程有解,且由于对偶变量数比方程数多一个,故解不唯一.称上面方程的解为位势.对上面的方程组求解,然后计算运输问题的检验数,若有检验数小于零,则原运输问题的解不是最优解.4.3.3解的改进运输问题中,若某一非基变量的检验数小于零,说明这个非基变量作为基变量时,运输费用将更小.因而当前解不是最优
本文标题:运输问题模型与算法
链接地址:https://www.777doc.com/doc-239348 .html