单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,*,商店 1 2 3,,需求,量（件/周） 50 60 30,工厂 1 2 3,,供应量（件/周） 50 70 20,运输问题的一般描述 模型的一般形式,,引例,,这里有三家工厂，都将产品运往三个不同的商店（见下图）每个工厂以产品件数表示出每周生产能力见下表1每家商店平均需求量见下表2线性规划,Linear Programming（LP）,特殊线性规划——,运输问题,工厂1,工厂3,工厂2,商店1,商店3,商店2,表1,表2,,1,,但是，由于运货距离不同，各个工厂运往各商店的货物的运输费用是不同的费用如下表，我们的问题是确定由哪家工厂运送多少件产品到哪家商店能否列出线性最优化模型？,,决策存在什么样的约束条件？,,模型评价涉及什么样的准则？,,有那些决策变量？,线性规划,Linear Programming（LP）,特殊线性规划——,运输问题,由工厂,每件产品运往各商店的费用（元）,,1 2 3,1 3 2 3,,2 10 5 8,,3 1 3 10,,2,,模型建立,,决策变量,——有待确定的是从每家工厂i（i=1，2，3）运输多少件产品到每家商店j（j=1，2，3）去。
因此，方便的办法是用双下标来表示决策变量即,Xij,目标函数,——利用运输费用表中的数据，我们希望其值为最小的是：,,Min Z =由工厂1运出产品的总费用----,3X,11,+ 2X,12,+ 3X,13,,+由工厂2运出产品的总费用----,10X,21,+ 5X,22,+ 8X,23,,+由工厂3运出产品的总费用----,X,31,+ 3X,32,+10X,33,,即：Min Z =,3X,11,+ 2X,12,+ 3X,13,+ 10X,21,+ 5X,22,+ 8X,23,+ X,31,+ 3X,32,+10X,33,,约束条件,——需要把决策变量的约束条件当作方案生成源对工厂1必须有,X,11,+X,12,+X,13,≤50,（对工厂1的供应约束）,,对工厂2必须有,X,21,+X,22,+X,23,≤70,（对工厂2的供应约束）,,对工厂3必须有,X,31,+X,32,+X,33,≤20,（对工厂3的供应约束）,线性规划,Linear Programming（LP）,特殊线性规划——,运输问题,,3,,——对每家商店来说，也需要一个逻辑关系式来说明每个星期运到的产品总数应等于每周的需求量。
对商店1必须有,X,11,+X,21,+X,31,=50,,对商店2必须有,X,12,+X,22,+X,32,=60,,对商店3必须有,X,13,+X,23,+X,33,=30,,于是，用于解此问题的线性最优化模型是：,,Min Z =,3X,11,+ 2X,12,+ 3X,13,+ 10X,21,+ 5X,22,+ 8X,23,+ X,31,+ 3X,32,+10X,33,,,X,11,+X,12,+X,13,≤50,,X,21,+X,22,+X,23,≤70,,X,31,+X,32,+X,33,≤20,,X,11,+,,X,21,+,,X,31,,,=,,50 X,ij,≥0 且为整数,,X,12,+ X,22,+,,X,32,,,=,,60 i=1，2，3,,X,13,+,,X,23,+,,X,33,,=,,30 j=1，2，3,线性规划,Linear Programming（LP）,特殊线性规划——,运输问题,s. t.,,4,,运输问题模型分析,,一般形式：,,某种物资有m个产地A,i,，产量（供应量）是a,i,（i=1，2，…，m），有n个销地B,j,，销量（需求量）是b,j,（j=1，2，…，n）。
从运到的单位运价为c,ij,（i=1，2，…，m；j=1，2，…，n），如何安排运输可使总运费最小？,线性规划,Linear Programming（LP）,特殊线性规划——,运输问题,产大于销,——, a,i,≥, b,j,,Min Z=,,C,ij,X,ij,, x,ij,≤,a,i,,（i=1，2，…，m）,,, x,ij,,=,b,j,,（j=1，2，…，n）,,,x,ij,≥,0,（i=1，2，…，m；,,j=1，2，…，n）,销大于产,——, a,i,≤, b,j,,Min Z=,,C,ij,X,ij,, x,ij,=,a,i,,（i=1，2，…，m）,,, x,ij,≤,b,j,,（j=1，2，…，n）,,,x,ij,≥,0,（i=1，2，…，m；,,j=1，2，…，n）,,5,,产销平衡,——, a,i,= b,j,,,,,,,,注意！这种模型具有特殊的形式：所有决策变量的约束条件，其系数均等于1；而且，每个决策变量仅出现于两个约束条件之中这些特性表明，解这类线性最优化模型的单纯形法中有一种特殊的方法可用来解这个问题——这是解这类模型的特别有效的一种方法。
而且上述特性还表明，可以给这类线性最优化模型以一种象网络模型式的形象化的说明线性规划,Linear Programming（LP）,特殊线性规划——,运输问题,Min Z=, ,C,ij,X,ij,, x,ij,,=,a,i,,（i=1，2，…，m）,,, x,ij,,=,b,j,,（j=1，2，…，n）,,,x,ij,≥,0,（i=1，2，…，m；j=1，2，…，n）,j,j,i,i,,6,,运输问题的求解方法,,求解此问题的一个十分有效的方法是,表上作业法：,,,（1）,产销平衡问题——总产量等于总销量的运输问题,,a、建立作业表,,b、确定初始调运方案（最小元素法）,,c、现行方案的最优性检验（位势法）,,d、现行方案的调整（闭回路法）,线性规划,Linear Programming（LP）,特殊线性规划——,运输问题,,7,,例1——,,甲（B,1,）、乙（B,2,）、丙（B,3,）、丁（B,4,）三城市所需煤炭由三个煤矿A,1,、A,2,、A,3,供应，有关数据如表，表中数字为单位运费（万元／万吨），请制订使总运费最小的调运计划产地 A,1,,A,2,,A,3,,销量,,B,1,B,2,B,3,B,4,产量,3 7 6 4,5,2 4 3 2,2,4 3 8 5,3,3 3 2 2,线性规划,Linear Programming（LP）,特殊线性规划——,运输问题,,8,,a、建立平衡调运作业表,3,7,6,4,2,4,3,2,4,3,8,5,A,1,,A,2,,A,3,B,1,B,2,B,3,B,4,产量,销量,3,3,2,2,5,2,3,3,运价,X,ij,调运量，当其,,为非基变量时,,不予填写,,ij,检验数，当,,其为基变量,,的检验数时,,不予填写,线性规划,Linear Programming（LP）,特殊线性规划——,运输问题,,9,,b、确定初始调运方案（最小元素法）,3,7,6,4,2,4,3,2,4,3,8,5,A,1,,A,2,,A,3,B,1,B,2,B,3,B,4,产量,销量,3,3,2,2,5,2,3,3,运价,X,ij,调运量，当其,,为非基变量时,,不予填写,,ij,检验数，当,,其为基变量,,的检验数时,,不予填写,2,,1,,,,,1,,4,,,3,,,0,,,,,2,,2,,2,,,,线性规划,Linear Programming（LP）,特殊线性规划——,运输问题,,10,,c、现行方案的最优性检验（位势法）,,1,0,2,2,2,3,3,7,6,4,2,4,3,2,4,3,8,5,A,1,,A,2,,A,3,B,1,B,2,B,3,B,4,U,i,V,j,,,,,,,,由,,ij,=C,ij,-（,U,i,+V,j,）,,计算位势U,i,， V,j,，,,因对基变量而言有,,,ij,=0，,即,,C,ij,-（,U,i,+V,j,） = 0,,令U,1,=0,0,3,7,6,4,-1,-4,再由,,ij,=C,ij,-（,U,i,+,,V,j,）计算非基变,,量的检验数,ij,-2,-2,-1,5,6,5,当存在非基变量的检验数,,kl,< 0,且,kl,=min{,ij,},时，令X,kl,进基。
从表中知可选X,23,进基线性规划,Linear Programming（LP）,特殊线性规划——,运输问题,,11,,d、现行方案的调整（闭回路法）,,1,0,2,2,2,3,3,7,6,4,2,4,3,2,4,3,8,5,A,1,,A,2,,A,3,B,1,B,2,B,3,B,4,U,i,V,j,,,,,,,,0,3,7,6,4,-1,-4,-2,-2,-1,5,6,5,调整量,,= {从,进基,,变量,X,23,出发的,闭回,,路中偶拐点上,基,变,,量的最小值}=2调整步骤为闭回路,,上奇拐点变量的值,,+,,,偶拐点变量的值,,-,,2,,3,0,线性规划,Linear Programming（LP）,特殊线性规划——,运输问题,,12,,d、现行方案的调整（闭回路法）,,1,0,2,2,2,2,3,3,7,6,4,2,4,3,2,4,3,8,5,A,1,,A,2,,A,3,B,1,B,2,B,3,B,4,U,i,V,j,,,,,,,,重复步骤C、,检验,,当前调运方案（基,,可行解）的最优性,,如非最优方案，则,,擦去U,i,、V,j,和,,ij,然,,后重新计算3,0,0,3,7,-1,4,4,-4,2,-2,-1,5,8,5,0,,线性规划,Linear Programming（LP）,特殊线性规划——,运输问题,,13,,d、现行方案的调整（闭回路法）,,1,0,2,2,,0,2,3,3,7,6,4,2,4,3,2,4,3,8,5,A,1,,A,2,,A,3,B,1,B,2,B,3,B,4,U,i,V,j,,,,,,,,重复步骤C、,检验,,当前调运方案（基,,可行解）的最优性,,如非最优方案，则,,擦去U,i,、V,j,和,,ij,然,,后重新计算。
3,0,3,7,4,-3,-4,6,0,2,1,5,6,5,当所有非基变量的,,检验数均非负时，,,则当前调运方案即,,为最优方案，如表,,此时最小总运费,,min Z =9+0+8+0+,,6+9 = 32,线性规划,Linear Programming（LP）,特殊线性规划——,运输问题,,14,,（2）,产销不平衡问题——总产量小于总销量的运输问题,,例2—有三个化肥厂供应四个地区的农用化肥等量化肥在这些地区使用效果相同相关数据如下表，试分析总运费最节省的化肥调运方案A,1,,A,2,,A,3,,最低需求（万吨）,,最高需求（万吨）,,B,1,B,2,B,3,B,4,产量（万吨）,16 13 22 17,50,14 13 19 15,60,19 20 23 ---,50,30 70 0 10,,50 70 30 不限,线性规划,Linear Programming（LP）,特殊线性规划——,运输问题,化肥厂,需求地区,运价：万元/万吨,,15,,分析：,,这是一个产销不平衡的运输问题，总产量为160万吨，四个地区的最低需求为110万吨，最高需求为无限。
根据现有产量，地区B,4,每年最多能分配到60万吨，这样最高总需求为210万吨，大于产量为了求得平衡，在产销平衡表中增加一个虚拟的化肥厂D ，其年产量为50万吨由于各个地区的需要量包含两部分，如地区B,1,，其中30万吨是最低需求，故不能由虚拟的化肥厂D供给，令其相应的运输价格为M（任意大正数），而另一部分20万吨满足或不满足均可，因此可以由虚拟的化肥厂D供给，并令其相应的运输价格为0（没有发生的运输）对凡是需求分两种情况的地区，实际上可按照两个地区看待这样可以建立这个问题的产销平衡表——,线性规划,Linear Programming（LP）,特殊线性规划——,运输问题,,16,,例2 产销平衡表,线性规划,Linear Programming（LP）,特殊线性规划——,运输问题,A,1,,A,2,,A,3,,D,B,',1,B,'',1,B,2,B,3,B,',4,B,'',4,产量,销量,17,17,14,14,13,19,15,,15,19,19,20,23,M,M,M,0,,M,0,M,0,50,60,50,50,30,20,70,30,10,50,16,16,22,13,20,,30,,,,,,20,,,,,,30,50,,20,,,,,,20,,40,,,,30,,,10,10,,,,,,,0,,30,20,,,20,,,,17,,产销平衡表,线性规划,Linear Programming（LP）,特殊线性规划——,运输问题,A,1,,A,2,,A,3,,D,B,',1,B,'',1,B,2,B,3,B,',4,B,'',4,U,i,V,j,13,,50,14,30,13,20,19,0,15,10,23,30,M,20,0,20,0,30,,,,,,,,,,,0,13,0,14,19,15,4,-4+M,4-M,-4+M,2,20-M,3,2,21-M,18-M,19-M,1,19-M,3,M-19,2M-18,2M-17,M-23,2M-19,16,22,17,17,14,15,19,19,20,M,M,M,0,M,16,0,,30,20,20,30,,18,,产销平衡表,线性规划,Linear Programming（LP）,特殊线性规划——,运输问题,A,1,,A,2,,A,3,,D,B,',1,B,'',1,B,2,B,3,B,',4,B,'',4,U,i,V,j,50,14,30,14,0,13,20,,15,10,23,30,M,20,0,20,0,30,,,,,,,,,,,0,0,-14+M,-14,14,14,13,37-M,15,14,2,2,-15+M,2,3,-18+,M,1,19-M,19-M,21-M,-1,M,1+M,-23+M,-1+M,10,20,0,,50,20,16,13,22,17,17,19,15,19,19,20,M,M,M,0,M,16,,19,,产销平衡表,线性规划,Linear Programming（LP）,特殊线性规划——,运输问题,A,1,,A,2,,A,3,,D,B,',1,B,'',1,B,2,B,3,B,',4,B,'',4,U,i,V,j,16,13,50,22,17,17,14,10,14,20,13,20,19,,15,10,15,19,20,19,20,23,30,M,M,0,M,0,,M,0,M,0,50,,,,,,,,,,,16,0,0,5,5-M,14,14,13,18,15,-5+,M,2,2,4,2,22-,M,1,20-M,0,2,-20+M,-19+2M,-19+M,-18+M,-23+M,-20+2M,10,20,,0,,20,,产销平衡表,线性规划,Linear Programming（LP）,特殊线性规划——,运输问题,A,1,,A,2,,A,3,,D,B,',1,B,'',1,B,2,B,3,B,',4,B,'',4,U,i,V,j,16,13,50,22,17,17,14,10,14,20,13,20,19,,15,10,15,0,19,20,19,20,23,30,M,M,,M,0,,M,0,M,0,50,,,,,,,,,,,16,0,0,6,0,14,14,13,17,15,15,2,2,5,2,2,2,-1,1,-21+,M,-21+M,-14+M,-14,-13+M,-17,-15+M,10,,10,30,20,40,,21,,产销平衡表,线性规划,Linear Programming（LP）,特殊线性规划——,运输问题,A,1,,A,2,,A,3,,D,B,',1,B,'',1,B,2,B,3,B,',4,B,'',4,U,i,V,j,13,50,,14,20,13,20,,15,10,15,10,19,30,23,20,,,0,10,0,40,,,,,,,,,,,0,0,8,-15,11,14,13,15,15,15,5,2,7,2,2,3,4,-3,-1,M-23,M-23,M+4,1,M+2,M,,30,0,30,20,20,16,22,17,17,14,19,19,20,M,M,M,0,M,M,16,,22,,产销平衡表,线性规划,Linear Programming（LP）,特殊线性规划——,运输问题,A,1,,A,2,,A,3,,D,B,',1,B,'',1,B,2,B,3,B,',4,B,'',4,U,i,V,j,16,13,50,22,17,17,14,,14,,13,20,19,,15,10,15,30,19,30,19,20,20,23,0,M,M,,M,0,,M,0,30,M,0,20,,,,,,,,,,,16,0,0,8,-15,11,11,13,15,15,15,5,5,7,2,2,3,3,4,-1,M-23,M-23,M+4,4,M+2,M,20,30,,30,20,0,,23,,产销平衡表,线性规划,Linear Programming（LP）,特殊线性规划——,运输问题,A,1,,A,2,,A,3,,D,B,',1,B,'',1,B,2,B,3,B,',4,B,'',4,U,i,V,j,13,50,,,13,20,,15,10,15,30,19,30,19,20,20,0,,,,0,30,0,20,,,,,,,,,,,0,0,7,-15,12,12,13,15,15,15,4,4,7,2,2,2,2,4,1,M-22,M-22,M+3,3,M+2,M,16,22,17,17,14,14,19,23,M,M,M,0,M,M,16,,24,,产销平衡表,线性规划,Linear Programming（LP）,特殊线性规划——,运输问题,A,1,,A,2,,A,3,,D,16,13,50,22,17,17,14,,14,,13,20,19,,15,10,15,30,19,30,19,20,20,0,23,,M,M,,M,0,,M,0,30,M,0,20,50,60,50,50,30,20,70,30,10,50,16,B,',1,B,'',1,B,2,B,3,B,',4,B,'',4,产量,,销量,,25,,。