运筹学运输问题补例3

1、运筹学运输问题补例3 运筹学运输问题补例 一、运输问题是特殊的象形规划问题，其特殊性表现 1、产销平衡运输问题总是存在可行解。 xij?aibjd?0,i?1,2,m;j?1,2,n;d?ai?bj就是一个。 i?1j?1mn2、由于0?xij?minai,bj，目标函数有下界，故产销平衡运输问题必有最有解。 3、求解过程要求每步得到的解x?xij是基可行解，意味着：解x必须满足模型中所有约束条件；基变量对应的约束方程组的系数列向量线性无关；解中非零变量xij的个数不能大于m?n?1个；为使迭代顺利进行，基变量的个数在迭代过程中保持为m?n?1个。 二、表上作业法：简单有效，其实质是单纯形法

2、1、找出初始基本可行解（初始运输方案），常用最小元素法、西北角法、伏格尔法。 2、求各非基变量的检验数，即在表上计算空格的检验数，判别是否达到最优解。 3、确定换入变量和换出变量，找出新的基可行解。在表上用闭回路法调整。 4、重复步骤2、3，直到得到最优解为止。 三、例1 运输表 销地b1 b2b3b4产量产地 91072a19 1342a25 8 42a357 销量 342186 1、最小元素法 运输表 销地b1b2b3b4产量 产地 9102a14795 l31342a25 32l4 834a35742 销量342186 l5l2l1 第 1 页 （共 22 页） ? 2、西北角法 运输表

3、销地l2l4产地a1a2a3销量b1b2b3b4产量3218628l3934314l5104266725957213l1 3、伏格尔法：每次都考虑最小运价与次最小运价的差额，差额越大的行或列，就最应该采用最小运价调运。当l1列销量满足时，就划掉第一列，继续用该方法做下去。 运输表销地产地b1b2b3b4产量行差额521111222l5l4a1a2a3销量32185381934110444l32156725l23957213l1列差额2 3、解的最优性检验-闭回路法 运输表与检验数销地产地a1a2a3销量b1b2b3b4产量-4218310-2+4-9423725695

4、721374442-4=2-1+2-7，-1=3-9+7-2，2=4-2+4-9+7-2，7=8-4+9-7+2-1，3=5-7+9-4第 2 页 （共 22 页） 运输表与检验数销地产地a1a2a3销量b1b2b3b4产量-4218310-2+4-9423725695721374442-4=2-1+2-7，-1=3-9+7-2，2=4-2+4-9+7-2，7=8-4+9-7+2-1，3=5-7+9-44、解的最优性检验-位势法 由基变量xij的系数cij的m?n?1个方程ui?vj?cij与取定某一个ui,vj的值，其它ui,vj的值就惟一确定了。对于非基变量xij

5、，其检验数?ij?cij?ui?vj。 ?运输表与检验数表1销地产地a1a2a3销量b1b2b3b4产量-421-1934832104243725695721783运输表与检验数表2销地产地a1a2a3销量b1b2b3b4产量ui500-4=2-(1+5)29313=10-(5+2)10422723=5-(2+0)957217=8-(1+0)8-1=3-(4+0)2=4-(2+0)453vj184462第 3 页 （共 22 页） 5、解的改进 如果某一个调运方案的所有空格的检验数都不小于0，则该调运方案是最优方案。 调整的方法：从检验数是负值（有多个取绝对值最大的一个）的空格出发。 运输表改

6、进1 销地b1b2b3b4产量 产地 534191072a19 3-4 313422a2550-12 83442a35 773 销量342186 =min4,3=3,x11=3,x14=4-3=1,x24=2+3=5,x21=3-3=0 运输表改进2 销地b1b2b3b4产量 产地 0539101672a1 93 021345a25 4-152 83442a357113 销量342186 =min,5=3,x22=5,x12=5-5=0,x14=1+5=6,x24=5-5=0 运输表最优方案销地产地a1a2a3销量b1b2b3b4产量351121830539348334104246137256

7、95721 四、例2 两个水厂a1,a2将自来水供应三个小区b1,b2,b3，每天个水厂的供应量与各小区的需求量 第 4 页 （共 22 页） 以及各水厂调运到各小区的供水单价见下表。应如何安排供水方案，使总水费最小？ b1 a1 a2 10 7 160 b2 6 5 90 b3 4 6 120 供应量/ t 170 200 370 需求量/ t 解 第一，分别用三种方法求出初始方案 1、最小元素法的基本思想是“就近供应”。每次总选择剩余运价中最小的点作为数字格。 最小元素法构造方案销地运价产地a1a2销量b1b2b3产量501101601079090l26512046l1170l3200 1203702、西北角法：与最小元素法不同的是，不考虑运价的大小，而是直接人为地每次读从左上决的位置确定数字格及其值。与最优方案差距大，但有规律，实现简单，易编程。 西北角法构造方案销地运价产地a1a2销量b1b2b3产量1601071080906512