大学精品课件：运筹学（第三章）.ppt

1、第三章第三章运运 输输 问问 题题主要内容：主要内容：第一节第一节 运输问题及数学模型运输问题及数学模型第二节第二节 用表上作业法求解运输问题用表上作业法求解运输问题第三节第三节 运输问题的进一步讨论运输问题的进一步讨论第四节第四节 运输问题的应用举例运输问题的应用举例第一节第一节运输问题及其数学模型运输问题及其数学模型一、运输问题的一般提法一、运输问题的一般提法 运输问题是一种应用广泛的网络最优化模型，其主要目的是为物资调运输问题是一种应用广泛的网络最优化模型，其主要目的是为物资调 运、车辆调度选择最经济的运输路线。有些问题，比如有运、车辆调度选择最经济的运输路线。有些问题，比如有 m 台机

2、床加工台机床加工n 种零件的问题，工厂的合种零件的问题，工厂的合理布局问题等理布局问题等,虽要求与提法不同虽要求与提法不同,当变化也可以使用本模型求得最优解。当变化也可以使用本模型求得最优解。运输问题的一般提法是：运输问题的一般提法是：某种物资有某种物资有 m 个产地个产地iA，产量分别为，产量分别为),.,2,1(miai=，有有 n 个销个销 地地jB，销量（需求最）分别为销量（需求最）分别为),.,2,1(njbj=,已知已知iA到到jB价为价为),.,2,1;,.,2,1(nnmicij=，又假设产销是平衡的，即：又假设产销是平衡的，即：=njjmiiba11，问应如何安排运输可使总运

3、费最小？，问应如何安排运输可使总运费最小？但经过适但经过适的单位运的单位运二、运输问题的数学模型二、运输问题的数学模型假定假定ijx表示由表示由iA到到jB的运输量，则平衡条件下的运输问题可写出的运输量，则平衡条件下的运输问题可写出如下的线性规划模型：如下的线性规划模型：ijminjijxcz=11Mins.t),.,2,1(1miaxinjij=),.,2,1(1njbxjmiij=0ijx=nnmmnnnmmmnmmnmnmmmnmnnmnnnmnnbxxxxxxbxxxxxxxbxxxxxxxaxxxxxxaxxxxxxxaxxxxxxx1221111221222112111122211

4、121121111123122221111131221112110000000000000000000000约束方程即为：约束方程即为：三、运输问题数学模型的特点三、运输问题数学模型的特点1.1.平衡条件下的运输问题一定有最优解。平衡条件下的运输问题一定有最优解。2.2.运输问题的系数矩阵运输问题的系数矩阵mnnm)(111111111111111111mnmmnnxxxxxxxxx 212222111211系数矩阵的特点：系数矩阵的特点：（1）约束条件系数矩阵的元素为）约束条件系数矩阵的元素为0或或1；（2）约束条件系数矩阵的每一列有两个）约束条件系数矩阵的每一列有两个1元素，元素，对于变量

5、对于变量xij在第在第i个约束方程中出现一次，个约束方程中出现一次，在第在第m+j个方程中出现第二次；个方程中出现第二次；（3）系数矩阵的秩为）系数矩阵的秩为m+n-1。第二节第二节用表上作业法求解运输问题用表上作业法求解运输问题基本思路：基本思路：（1）找出基本可行解；）找出基本可行解；（2）检验是否为最优解。是，则停止，否，）检验是否为最优解。是，则停止，否，转入（转入（3）；）；（3）解的调整。得到一个新的基本可行解，）解的调整。得到一个新的基本可行解，重新回到步骤二。重新回到步骤二。所有步骤都在表上进行操作所有步骤都在表上进行操作销销地地 产产地地 B 1 B 2 B n 产产量量 C

6、 11 C 1 2 C 1 n A 1 x 11 x 1 2 x 1 n a 1 C 21 C 2 2 C 2 n A 2 x 21 x 2 2 x 2 n a 2 C m 1 C m 2 C m n A m x m1 x m 2 x m n a m 销销量量 b 1 b 2 b n 运输表运输表例子：例子：某部门有某部门有3 3个生产同类产品的工厂，生产的产品由个生产同类产品的工厂，生产的产品由4 4个个销售点出售，各工厂的生产量、各销售点的销售量（假定销售点出售，各工厂的生产量、各销售点的销售量（假定单位均为吨）以及各工厂到各销售点的单位运价（元单位均为吨）以及各工厂到各销售点的单位运价（

7、元/吨）吨）如下表，要求研究产品如何调运才能使总运费最小。如下表，要求研究产品如何调运才能使总运费最小。一、找出初始基可行解一、找出初始基可行解1.1.西北角法西北角法2.2.最小元素法最小元素法3.3.沃格尔法（差值法）沃格尔法（差值法）较差较差较好较好更好更好886481484+812+610+43+811+146=372（元）（元）西北角法西北角法每次找最左上角对应的元素每次找最左上角对应的元素1482108682+145+104+23+611+86=246（元）（元）最小元素法最小元素法每次找最小元素每次找最小元素148212882+145+124+411+29+86=244（元）（元

8、）行罚数行罚数列列罚罚数数25130110122212764沃格尔法沃格尔法每次找行罚数和列罚数中最大值所对应的行每次找行罚数和列罚数中最大值所对应的行或列中最小的元素或列中最小的元素二、解的最优性检验二、解的最优性检验1.1.闭回路法闭回路法2.2.对偶变量法（位势法）对偶变量法（位势法）（14）（8）（2）（10）（8）（6）闭回路法：闭回路法：（14）（8）（2）（10）（8）（6）11234411=15611431022=113411924=-121012存在小于存在小于0的检验数，故此基可行解不是最优解。的检验数，故此基可行解不是最优解。在运输问题中通常目标函数是求最小值，所以在运输

9、问题中通常目标函数是求最小值，所以当所有的检验数为正值时，得到最优解。当所有的检验数为正值时，得到最优解。注意：注意：对于每一个非基变量，在运输表中唯一对应一条对于每一个非基变量，在运输表中唯一对应一条这样的闭回路。这样的闭回路。对偶变量法（位势法）：对偶变量法（位势法）：=nnmmnnnmmmnmmnmnmmmnmnnmnnnmnnbxxxxxxbxxxxxxxbxxxxxxxaxxxxxxaxxxxxxxaxxxxxxx1221111221222112111122211121121111123122221111131221112110000000000000000000000ijminji

10、jxcz=11Min1u2umu1v2vnvijnmijijijijPvvvuuucYPc),(2121=)(jiijvuc=基变量的检验数为基变量的检验数为0，得到，得到m+n-1个方程，这些方程个方程，这些方程中共包含中共包含m+n个对偶变量，因此解的个数不唯一。个对偶变量，因此解的个数不唯一。把用这把用这m+n-1个方程求得的对偶变量的解带入到其它个方程求得的对偶变量的解带入到其它m*n-(m+n-1)个式子中，求出非基变量的检验数。个式子中，求出非基变量的检验数。当所有的检验数都当所有的检验数都0 0时，得到最优解。时，得到最优解。（14）（8）（2）（10）（8）（6）11-1210

11、12uivju1v4v3v2v1u2u3(4)(11)(0)(-5)(-1)(3)(10)130411=21001212=110)1(1022=存在小于存在小于0的检验数，故此基可行解不是最优解。的检验数，故此基可行解不是最优解。三、解的改进三、解的改进闭回路法闭回路法（14）（8）（2）（10）（8）（6）22,6min=+2+2-2-2（14）（8）（12）（8）（4）（2）四、重新进行最优性检验四、重新进行最优性检验（14）（8）（12）（8）（4）02（2）29121不存在小于不存在小于0的检验数，故此基可行解是最优解，的检验数，故此基可行解是最优解，得到最优运输方案。得到最优运输方案

12、。(存在无穷多最优调运方案存在无穷多最优调运方案)第三节第三节运输问题的进一步讨论运输问题的进一步讨论一、产销不平衡的运输问题一、产销不平衡的运输问题 表上作业法是以产销平衡为前提的。当实表上作业法是以产销平衡为前提的。当实际问题是产销不平衡的问题时，需要转化为产际问题是产销不平衡的问题时，需要转化为产销平衡的运输问题。销平衡的运输问题。ijminjijxcz=11Mins.t),.,2,1(1miaxinjij=),.,2,1(1njbxjmiij=0ijx1、产大于销，即、产大于销，即=njjmiiba11 此时增加一个假想的销地此时增加一个假想的销地n+1，该销地的销量，该销地的销量为为

13、 ，而各产地到假想销地的单位运价定为，而各产地到假想销地的单位运价定为0，就转化成产销平衡的运输问题。就转化成产销平衡的运输问题。=njjmiiba11=njjmiiba112、销大于产，即、销大于产，即=njjmiiba11ijminjijxcz=11Mins.t),.,2,1(1miaxinjij=),.,2,1(1njbxjmiij=0ijx 此时增加一个假想的产地此时增加一个假想的产地m+1，该产地的产量，该产地的产量为为 ，而假想产地到各销地的单位运价定为，而假想产地到各销地的单位运价定为0，就转化成产销平衡的运输问题。，就转化成产销平衡的运输问题。=miinjjab11=miinj

14、jab11例例1：某市有三个造纸厂某市有三个造纸厂A1,A2和和A3，其纸的产量分，其纸的产量分别为别为8，5和和9个单位。由各造纸厂到各用户的单个单位。由各造纸厂到各用户的单位运价如表所示，请确定总运费最少的调运方案。位运价如表所示，请确定总运费最少的调运方案。例例2：有三个产地有三个产地A1,A2,A3A1,A2,A3，生产同一种物品，使用，生产同一种物品，使用者分别为者分别为B1,B2,B3B1,B2,B3，各产地到各使用者的单位，各产地到各使用者的单位运价示与下表。运价示与下表。这这三个使用者的需求量分别为三个使用者的需求量分别为1010、4 4和和6 6个单位个单位。由于销售需要和客

15、观条件的限制，由于销售需要和客观条件的限制，产地产地A1A1至少至少要发出要发出6 6个单位的产品，但它最多只能生产个单位的产品，但它最多只能生产1111个个单位的产品；单位的产品；A2A2必须发出必须发出7 7个单位的产品；个单位的产品；A3A3至至少要发出少要发出4 4个单位的产品。个单位的产品。试根据以上条件用表试根据以上条件用表上作业法求解该运输问题的最优运输方案。上作业法求解该运输问题的最优运输方案。A3最多可能送出的产品数量：最多可能送出的产品数量：(10+4+6)-(6+7)=7 在以上讨论中，假定物品由产地直接运送到销在以上讨论中，假定物品由产地直接运送到销售目的地，不经中间转

16、运。但是，常常会遇到这种售目的地，不经中间转运。但是，常常会遇到这种情形：需先将物品由产地运列某个中间转运站情形：需先将物品由产地运列某个中间转运站(可可能是另外的产地、销地或中间转运仓库能是另外的产地、销地或中间转运仓库)，然后再，然后再转运到销售目的地。有时，经转运比直接运到目的转运到销售目的地。有时，经转运比直接运到目的地更为经济地更为经济(如下页图如下页图)。因此，在决定运输方案时。因此，在决定运输方案时有必要把转运也考虑进去。有必要把转运也考虑进去。二、有转运的运输问题二、有转运的运输问题ABC301010201042211建立一般意义上的数学模型，设：建立一般意义上的数学模型，设：

17、ai：第：第i个产地的产量个产地的产量(净供应量净供应量)；bj：第：第j个销地的销量个销地的销量(净需要量净需要量)；xij：由第：由第i个发送地运到第个发送地运到第j个接收地的物品数量；个接收地的物品数量；cij：由第：由第i个发送地到第个发送地到第j个接收地的单位运价，个接收地的单位运价，ti：第：第i个地点转运物品的数量；个地点转运物品的数量；ci：第：第i个地点转运单位物品的费用。个地点转运单位物品的费用。将产地和销地统一编号，并把产地排在前面。销地排在将产地和销地统一编号，并把产地排在前面。销地排在后面，则有：后面，则有：=nmiiinmjiinmijjijijtcxcz111mi

18、n令：iiitQx=jjjtQx=建立数学模型：建立数学模型：)(,.,2,1,0,.,2,1,.,.,.,2,1,.,.,.,2,1,.,.,.,2,1,.,.,1,121,1,121,1,1,21,1,1,21jinmjixnmmmitbxxxxxmjtxxxxxnmmmitxxxxxmitaxxxxxijjjjnmjjjjjjjjnmjjjjjjinmiiiiiiiiinmiiiiiii =注：所有注：所有i=j，cij=-ci 例：如图所示是一个运输系统，它包括二个产地（例：如图所示是一个运输系统，它包括二个产地（1和和2）、二）、二个销地个销地(4和和5)及一个中间转运站及一个中间转

19、运站(3)，各产地的产量和各销地的，各产地的产量和各销地的销量用相应节点处箭线旁的数字表示，节点联线上的数字表示销量用相应节点处箭线旁的数字表示，节点联线上的数字表示其间的其间的运输单价运输单价，节点旁的数字为该地的，节点旁的数字为该地的转运单价转运单价，试确定最，试确定最优运输方案。优运输方案。该运输问题的运输表该运输问题的运输表该运输问题的最优调运方案该运输问题的最优调运方案总运费：总运费：10*2+20*2+20*4+20*5+（50-30）*3=300第四节第四节运输问题的应用举例运输问题的应用举例 例例1：某厂按合同规定须于当年每个季度末分某厂按合同规定须于当年每个季度末分别提供别提

20、供15、20、25、20台同一规格的设备。已知该台同一规格的设备。已知该厂各季度的生产能力及生产每台设备的成本如下表。厂各季度的生产能力及生产每台设备的成本如下表。又知如果生产出来的设备当季度不交货，每台每季又知如果生产出来的设备当季度不交货，每台每季度的存储维护费为度的存储维护费为0.1万元。试安排全年生产计划，万元。试安排全年生产计划，使总费用最低。使总费用最低。解：解：设设xij（n=1,2,4；n=1,2,4）表示第）表示第i季季生产第生产第j季销售的设备数量，季销售的设备数量，xi5表示第表示第i季度实际生产季度实际生产数量与该季度生产能力之间的差值。列出如下产销数量与该季度生产能力

21、之间的差值。列出如下产销平衡运输表。平衡运输表。季度季度 季度季度 1 2 3 4 5(虚销地虚销地)产产量量 12.0 12.1 12.2 12.3 0 1 1 0 20 25 M 11.0 11.1 11.2 0 2 2 0 20 10 35 M M 11.5 11.6 0 3 15 20 30 M M M 12.5 0 4 15 20 销量销量 15 20 2 25 5 20 30 110 所有检验数都大于等于所有检验数都大于等于0，因此该解为最优解。，因此该解为最优解。求初始生产计划方案并进行检验：求初始生产计划方案并进行检验：10uivj12.012.10-1.1012.2-0.71

22、2.3（0）（0）（M-10.9）（0）（1.1）（0.7）（0.2）（注：其余空格检验数显然大于（注：其余空格检验数显然大于0，省略未写），省略未写）例例2:某航运公司承担六个港口城市某航运公司承担六个港口城市A,B,C,D,E,F间四条间四条航线的货物运输任务。已知航线的货物运输任务。已知（1）各航线的起点、终点、各航线的起点、终点、日航班数（下表左）；（日航班数（下表左）；（2）各城市间的航行时间（下表）各城市间的航行时间（下表右）右）；（；（3）所有航线都使用同一种船只，每次装船和）所有航线都使用同一种船只，每次装船和卸船时间均为卸船时间均为1天。天。问该公司至少应配备多少条船才能满足

23、所有航线运输的需要？问该公司至少应配备多少条船才能满足所有航线运输的需要？解：解：所需船只分成两部分所需船只分成两部分(1)载货航行需要的船只数：载货航行需要的船只数：3*19+2*5+9+15=91条条.(2)各港口间调度需要的船只数各港口间调度需要的船只数.各港口每天船只的余缺数为各港口每天船只的余缺数为:调度需要船只：调度需要船只：2+13+5+17+3=40至至 从从 A B E 产量产量 2 3 5 C 1 1 0 2 14 13 17 D （-2）2 2 7 8 3 F 1 1 销量销量 1 1 3 3 （0）（7）（7）（2）（0）（7）（9）(1)运输问题是一种特殊的线性规划模

24、型，因而求解结果也可能出现下运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之一：有唯一最优解，有无穷多最优解，无界解，无可列四种情况之一：有唯一最优解，有无穷多最优解，无界解，无可行解。行解。(2)在运输问题中，只要任意给出一组含（在运输问题中，只要任意给出一组含（m+n-1）个非零的）个非零的xij，且满足且满足 ，就可以作为一组基可行解。，就可以作为一组基可行解。(3)按最小元素法按最小元素法(或伏格尔法或伏格尔法)给出的初始基可行解，从每一空格出发给出的初始基可行解，从每一空格出发可以找出而且仅能找出唯一的闭回路。可以找出而且仅能找出唯一的闭回路。(4)如果运输问题单位运价表的某一行如果运输问题单位运价表的某一行(或某一列或某一列)元素分别加上一个常元素分别加上一个常数数k，最优调运方案将不会发生变化。，最优调运方案将不会发生变化。(5)如果运输问题单位运价表的某一行如果运输问题单位运价表的某一行(或某一列或某一列)元素分别乘上一个常元素分别乘上一个常数数k，最优调运方案将不会发生变化。，最优调运方案将不会发生变化。判断下列说法是否正确：判断下列说法是否正确：),.,2,1(1miaxinjij=),.,2,1(1njbxjmiij=