第三章(运输问题.pptx

《第三章(运输问题.pptx》由会员分享，可在线阅读，更多相关《第三章(运输问题.pptx（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、物资运输问题某种物资有m个产地Ai，i=1,2,.,m，产量分别为ai个单位；有n个销地Bj，销量分别为bj个单位，j=1,2,.n，Ai与Bj之间的单位运价为Cij，问应如何安排运输方案，才能使总运费最少？设从产地Ai，运往销地Bj的销量为Xij，则目标为总运费最小第1页/共59页物资运输问题产地约束条件销地约束条件非负约束第2页/共59页物资运输问题 第3页/共59页物资运输问题产销平衡的运输问题第4页/共59页Proof:则取则取显然有显然有 ，又又所以所以 ，是问题的一个可行解。，是问题的一个可行解。又因为又因为 ，对于任一可行，对于任一可行解有目标函数值解有目标函数值 ，对于求极小化

2、问题，目标，对于求极小化问题，目标函数函数值有下界，则必有最优解。值有下界，则必有最优解。第5页/共59页物资运输问题某地区有两个煤矿A1 A2，所产的煤要运往三个城市B1 B2 B3，各产地的产量、销地的销量以及各产地到各销地的单位运费见下表，求使总运费最小的运输方案 B1B2B3产量产量A1907095200A2806575230销量销量100150180 x11x12x13x21x22x23第6页/共59页物资运输问题运输问题B1B2B3产量产量A1907095200A2806575230销量销量100150180 x11x12x13x21x22x23总运费为Z=32500元第7页/共5

3、9页物资运输问题求一个初始基本可行解是判断基本可行解是否最优结束不是求使目标得到改善的基本可行解第8页/共59页约束方程系数矩阵结构第9页/共59页约束方程系数矩阵结构第10页/共59页约束方程系数矩阵结构第11页/共59页基变量个数m+n-1A的增广矩阵的秩小于m+n第12页/共59页基变量个数m+n-1A的增广矩阵的秩等于m+n-1第13页/共59页第14页/共59页基变量的构成闭回路其中，（i1i2,.,is互不相同，j1j2,.,js互不相同）上述形式的变量的集合称为一个闭回路其中的变量称为闭回路的顶点第15页/共59页基变量的构成闭回路第16页/共59页定义定义 1 1凡是能排列成凡

4、是能排列成（其中（其中 互不相同，互不相同，互不相同）互不相同）形式的变量集合，称为一个闭回路，其中诸变量称为形式的变量集合，称为一个闭回路，其中诸变量称为这个闭回路的顶点这个闭回路的顶点.B1 B2 B3 B4 B5 A1 x11 x12 x13 x14 x15 A2 x21 x22 x23 x24 x25 A3 x31 x32 x33 x34 x35 A4 x41 x42 x43 x44 x45如：如：变量集合变量集合变量集合变量集合2、每一行（或列）若有闭回路的顶点，则有两个每一行（或列）若有闭回路的顶点，则有两个顶点；顶点；3、每两个顶点格子的连线都是水平的或垂直的；每两个顶点格子的连

5、线都是水平的或垂直的；4、闭回路中顶点的个数必为偶数闭回路中顶点的个数必为偶数.闭回路的几何特征：闭回路的几何特征：1、每一个顶点格子都是每一个顶点格子都是 90转角点；转角点；第17页/共59页基变量的构成对于闭回路线性相关其对应的列向量第18页/共59页基变量的构成若变量组中有一部分构成闭回路，则变量组线性相关。不包含任何闭回路的变量组中必有孤立点。孤立点是其所在行或所在列中包含在该变量组中的唯一向量。定理：r个变量对应的系数列向量线性无关的充要条件是变量组不包含闭回路。推论：m+n-1个变量构成基变量的充要条件是不含闭回路。第19页/共59页运输问题求解初始基本可行解的确定在供需表中任选

6、一个单元xij，尽量匹配产销，使一个约束方程得以满足，填入相应位置；调整Ai的拥有量及Bj的需求量，分别减去xij，得到调整后的拥有量ai和需求量bj；若ai=0，则划去对应的行（拥有的量全部运走），若bj=0则划去对应的列（需求的量全部运来），且每次只划去一行或一列（每次只去掉一个约束）；若平衡表中所有的行或列均被划去，则结束。否则，在剩下的平衡表中选下一个变量，转第20页/共59页运输问题求解B1BjBnA1:Aiai:Amb jb j=b j-x ij a i=a i-x ijx ijaib j第21页/共59页基变量的构成按照上述方法所产生的一组变量的取值将满足下面条件：a所得的变量均

7、为非负，且变量总数恰好为m+n-1个；b所有的约束条件均得到满足；c所得的变量不构成闭回路。因此所得的解一定是运输问题的基本可行解。在上面的方法中，xij的选取方法并没有加以限定，如果采取一定的规则来选取，则会产生不同的方法，若每次在调整后的供需表中选取最左上角的元素，则称为左上角方法（或称西北角法），若每次在调整后的供需表中选取对应单位运费最小的元素，则称为最小费用法。第22页/共59页西北角法运输问题某地区有两个煤矿A1 A2，所产的煤要运往三个城市B1 B2 B3，各产地的产量、销地的销量以及各产地到各销地的单位运费见下表，求使总运费最小的运输方案 B1B2B3产量产量A19070952

8、00A2806575230销量销量100150180第23页/共59页西北角法B1B2B3产量产量A1x11x12x13200A2x21x22x23230销量销量100150180调整量调整量100100调整量调整量0调整量调整量1000调整量调整量050调整量调整量50180调整量调整量00调整量调整量1800调整量调整量0Note:在填入一个数时，如果行和列同时饱和，在填入一个数时，如果行和列同时饱和，规定只划去一行或一列规定只划去一行或一列第24页/共59页最小费用法B1B2B3产量产量A1x11x12x13200A2x21x22x23230销量销量100150180调整量调整量1508

9、0调整量调整量0调整量调整量800调整量调整量100调整量调整量100100调整量调整量0调整量调整量1000调整量调整量0907095806575第25页/共59页关键关键1、填一个数字划去一行或一列填一个数字划去一行或一列 不产生闭回路；不产生闭回路；2、填一个数字填一个数字只只划去一行或一列划去一行或一列 填满填满m+n-1-1个数个数.BjAi B1 B2 ai A1 8 2 5 A2 3 1 4 bj 6 3 差额差额 6 2 差额差额 5 1315 BjAi B1 B2 ai A1 8 2 5 A2 3 1 4 bj 6 3 按最小元素法按最小元素法3423、Vogel 法法 (元

10、素差额法元素差额法)规则：计算各行各列的最小元素与次小元素的差额，规则：计算各行各列的最小元素与次小元素的差额，优先安排差额最大的所优先安排差额最大的所在行或列的单位运价最在行或列的单位运价最小的产地与销地之间的小的产地与销地之间的运输任务运输任务第26页/共59页 +-+-B1B2B3产量产量A1x11x12x13200A2x21x22x23230销量销量10015018090709580657510010050180最优性检验 21=C21-C11+C12-C22=80-90+70-65=-5 13=C13-C23+C22-C12=95-75+65-70=15第27页/共59页最优性检验：

11、闭回路法闭回路方法原理是通过寻找闭回路来找到非基变量的检验数。可以证明，如果对闭回路的方向不加区别，那么以每一个非基变量为起始顶点，以基变量为其它顶点的闭回路就存在而且唯一。如果规定作为起始顶点的非基变量为偶数次顶点，闭回路的其他顶点依次为第一个顶点、第二个顶点，那么就有：检验数=偶数点单位运费之和奇数点单位运费之和若所有非基变量检验数0，则最优。第28页/共59页最优性检验：位势法位势法其原理是利用约束条件的特殊性来找到非基变量的检验数。从约束条件中解出基变量（用非基变量表示基变量），代入目标后消去目标中的基变量，得到的非基变量的系数就是检验数。这一过程若用消元的方法加以实现，则产生位势法。

12、若所有非基变量检验数0，则最优。第29页/共59页最优性检验：位势法位势法第30页/共59页最优性检验：位势法位势法第31页/共59页最优性检验：位势法第32页/共59页B1B2B3产量A1x11x12x13200A2x21x22x23230销量100150180最优性检验：位势法（90）（70）9580（65）（75）第33页/共59页B1B2B3产量A1x11x12x13200A2x21x22x23230销量100150180最优性检验：位势法（90）（70）9580（65）（75）第34页/共59页B1B2B3产量A1x11x12x13200A2x21x22x23230销量1001501

13、80最优性检验：位势法（0）（-20）580（65）（75）第35页/共59页B1B2B3产量A1x11x12x13200A2x21x22x23230销量100150180最优性检验：位势法（0）（0）580（85）（75）第36页/共59页B1B2B3产量A1x11x12x13200A2x21x22x23230销量100150180最优性检验：位势法（0）（0）5-5（0）（-10）第37页/共59页B1B2B3产量A1x11x12x13200A2x21x22x23230销量100150180最优性检验：位势法（0）（0）15-5（0）（0）第38页/共59页位势法（对偶变量法）位势法（对偶

14、变量法）约束方程的系数矩阵的秩为约束方程的系数矩阵的秩为m+n-1约束方程的系数矩阵的秩为约束方程的系数矩阵的秩为m+n对任意的对任意的 a0，与原问题等价与原问题等价x0必为基变必为基变量量,x0=0第39页/共59页xj 的检验数的检验数 由于由于设：为基变量，由于基变量设：为基变量，由于基变量的检验数等于零的检验数等于零有解，不唯一有解，不唯一ui 称为行位势称为行位势，vj 称为行位势称为行位势第40页/共59页90709580657510010050180 +-+-B1B2B3产量产量A1x11x12x13200A2x21x22x23230销量销量100150180调整流量X21进基

15、，=minx11,x22=min100,50=50X22出基第41页/共59页调整流量调运量的调整步骤：闭回路上的奇数次顶点的调运量减去；闭回路上的偶数次顶点（包括起始变量）的调运量加上；非闭回路顶点的其他变量调运量不变；奇数点上被修改为0的变量为出基变量，在新的方案中不再标出其值。但若有两个为零的变量，则只取其一作为出基变量。第42页/共59页B1B2B3产量A1x11x12x13200A2x21x22x23230销量1001501809070958065755015050180调整流量22=C22-C21+C11-C12=65-80+90-70=513=C13-C23+C21-C11=95

16、-75+80-90=10第43页/共59页B1B2B3产量A1x11x12x13200A2x21x22x23230销量100150180最优性检验：位势法（0）（0）15(-5)0（0）第44页/共59页B1B2B3产量A1x11x12x13200A2x21x22x23230销量100150180最优性检验：位势法（0）（0）15(0)5（5）第45页/共59页B1B2B3产量A1x11x12x13200A2x21x22x23230销量100150180最优性检验：位势法（0）（0）10(0)5（0）第46页/共59页一、初始方案的确定一、初始方案的确定1、西北角法西北角法 BjAi B1 B

17、2 B3 B4 ai A110 5 2 3 70 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 15Ex.1 50 已知某商品有三个产地已知某商品有三个产地A1、A2、A3和四个销地和四个销地B1、B2、B3、B4 ，产量、销量及单位运价如表，产量、销量及单位运价如表.问应问应如何调运，在满足各销地需要的情况下，使总的运费如何调运，在满足各销地需要的情况下，使总的运费支出为最少？支出为最少？解：解：51010205规则规则:从运输表的西从运输表的西北角开始北角开始,优先安排优先安排编号小的产地和销地编号小的产地和销地的运输任务的运输任务.BjAi B1 B2

18、B3 B4 ai A110 5 2 3 50 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 15500第47页/共59页2、最小元素法最小元素法 BjAi B1 B2 B3 B4 ai A110 5 2 3 70 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 1540102551010 BjAi B1 B2 B3 B4 ai A1 1 5 3 2 60 A2 4 1 2 3 20 A3 5 6 1 4 10 bj 50 20 10 100010102050第48页/共59页二、最优性检验二、最优性检验 BjAi B1 B2 B

19、3 B4 ai A110 5 2 3 70 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 15401025510101、闭回路法闭回路法+1-1+1-1 BjAi B1 B2 B3 B4 A1 A2 A3检验数表检验数表-5-10666 BjAi B1 B2 B3 B4 A1 A2 A3 BjAi B1 B2 B3 B4 A1 A2 A3 BjAi B1 B2 B3 B4 A1 A2 A3第49页/共59页 BjAi B1 B2 B3 B4 ui A1 4010 25 5 2 5 3 A2 4 3 10 1 10 2 A3 10 5 6 3 4 vj BjAi

20、 B1 B2 B3 B4 A1 A2 A3检验数表检验数表-5-10666-2-120273见见 Ex.1最小元素法得到的初始基可行解最小元素法得到的初始基可行解10053-12-5第50页/共59页三、基可行解的改进三、基可行解的改进 BjAi B1 B2 B3 B4 ai A110 5 2 3 70 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 1540102551010 BjAi B1 B2 B3 B4 A1 A2 A3检验数表检验数表-5-10666选择进基变量选择进基变量则取非基变量则取非基变量 xst 为进基变量为进基变量确定出基变量确定出基变量调

21、整量调整量则基变量则基变量 xkl 出基（运量擦去）出基（运量擦去）调整方法：在该闭回路上，奇点运量加调整方法：在该闭回路上，奇点运量加 ，偶点减去，偶点减去 15301065420101-56520664565第51页/共59页产大于销的运输问题B1B2B3B4拥有量A125001540A202002060A300401050需求量25204045B1B2B3B4拥有量A1X11X12X13X14a1A2X21X22X23X24a2A3X31X32X33X44a3需求量b1b2b3b4第52页/共59页产大于销的运输问题虚拟销地n+1，销量第53页/共59页产大于销的运输问题B1B2B3B4拥有量A1569440A2948560A31075350需求量25204045B1B2B3B4B5A15694040A29485060A310753050需求量2520404520例 3-2第54页/共59页产大于销的运输问题B1B2B3B4B5拥有量A1250015040A20200202060A3004010050需求量2520404520第55页/共59页销大于产的运输问题虚拟产地n+1，产量允许缺货第56页/共59页销大于产的运输问题第57页/共59页销大于产的运输问题没有可行解第58页/共59页感谢您的观看！第59页/共59页