运筹学演示课件ch3运输问题.pptVIP

运输问题的表示 网络图、线性规划模型、运输表 初始基础可行解 西北角法、最小元素法 非基变量的检验数 闭回路法、位势法 确定进基变量，调整运量，确定离基变量 ;一.运输问题的一般提法;典型范例 各工厂应分別运送多少数量至各配送中心，才能使总的运输成本最低？ 供给及需求单位：1卡车的量 单位运输成本：千元;2;运输问题线性规划模型;运输问题的表格表示;运输问题的一般提法是：;2.产销不平衡问题;二.运输问题的模型;将约束方程式展开可得;上述模型是一个线性规划问题。但是其结构很特殊，特点如下：;系数矩阵的特点:(1)约束条件的系数矩阵的元素只有两个:0,1.(2)元素 xij 对应于每一个变量在前m个约束方程中(第i个方程中)出现一次,在后n个约束方程中(第m+j 个方程中)也出现一次.(3)产销平衡问题为等式约束.(4)产销平衡问题中各产地产量之和与各销售地点的销量之和相等.;2.m+n个约束中有一个是多余的（因为其间含有一个平衡关系式 ） 所以R(A)=m+n-1，即解的mn个变量中基变量 为m+n-1个。;【证】因为产销平衡，即 ，将前m个约束方程两边相加得;中任意m+n阶子式等于零，取第一行到m+n－1行与 对应的列（共m+n-1列）组成的m+n－1阶子式;故r(A)=m+n－1所以运输问题有m+n－1个基变量。;三.运输问题的解法;运输单纯形法也称为表上作业法，是直接在运价表上求最优解的一种方法，它的步骤是：;左上角法(亦称西北角法)是优先从运价表的左上角的变量赋值，当行或列分配完毕后，再在表中余下部分的左上角赋值，依次类推，直到右下角元素分配完毕．当出现同时分配完一行和一列时，仍然应在打“×”的位置上选一个变量作基变量，以保证最后的基变量数等于m+n－1 ;最小元素法的思想是优先满足单位运价最小的业务，即最小运价Cij 对应的变量xij优先赋值， 然后再在剩下的运价中取最小运价对应的变量赋值并满足约束，依次下去，直到最后得到一个初始基可行解。 ;初始基础可行解—最小元素法（1）;最小元素法（2）;最小元素法（3）;最小元素法（4）;最小元素法（5）;最小元素法（6）;初始基础可行解—元素差额法 （Vogel近似法）;; Bj Ai; Bj Ai; Bj Ai;求出一组基可行解后，判断是否为最优解，仍然是用检验数来判断，记xij的检验数为σij由第一章知，求最小值的运输问题的最优判别准则是：;5;5;5;5;5;5;位势法求检验;设前m个约束对应的对偶变量为ui,i=1,2,…,m，后n个约束对应的对偶变量为vj,j=1,2,…,n则运输问题的对偶问题是;非基变量xij的检验数j—位势法求检验 (1);位势法求检验 (2);位势法求检验 (3);位势法求检验(4);位势法求检验(5);位势法求检验(6);位势法求检验(7);位势法求检验(8);位势法求检验(9);位势法求检验(10);位势法求检验(11);位势法求检验(12);位势法求检验(13);第三步，选择进基变量,确定离基变量;第三步，选择进基变量,确定离基变量;调整运量,重新计算检验数,确定进基、离基变量;调整运量, 重新计算检验数;小结： 运输问题的常用解法： 最小元素法（确定初始方案）→闭回路法（检验当前方案）→闭回路法（方案调整）; 例：某食品公司下设3个加工厂A1， A2，A3，和4个门市部B1， B2，B3，B4。各加工厂每天的产量、各门市部每天的销售量以及从各加工厂到各门市部的运价如下表所示。 问：该公司应如何调运，在满足各门市部销售需要的情况下，使得运费支出为最少？; 门市部加工厂;解：1.确定初始方案: (最小元素法基本思想：就近供应，即从单位运价表上最小的运价开始确定产销关系，以此类推，直到给出初始方案为止)①从运价表上找出最小运价C21=1， A2 先保证供应B1 ，X21=3，划去运价表上B1 列；②再从运价表上其余元素中找到最小的运价C23=2，加工厂A2 应供给B3， X23=1，划去A2行；③再从运价表上其余元素中找到最小的运价C13=3，所以A1先保证供应B3 ， B3 尚缺4单位，因此X13=4，划去B3 列。;以此类推，得到一初始方案（如下图）： X21=3，X32=6，X13=4，X23=1，X14=3，X34=3（有数格） X11=X31=X12=X22=X33=X24=0（空格）;2.检验（闭回路法:计算空格的检验数）;;;从σij 为最小负值的空格出发.对其闭回路上的奇数顶点运量增加θ,偶数顶点的运量减少θ(这才能保证新的平衡)，其