ch5 运输问题-2015

1、 Page 1 Chapter 5 运输与指派问题运输与指派问题T&A Problem 第第5章章 运输问题运输问题 1 运输问题的数学模型运输问题的数学模型 2 表上作业法表上作业法 3产销不平衡的运输问题及其应用产销不平衡的运输问题及其应用 4指派问题指派问题 Page 2 Chapter 5 运输与指派问题运输与指派问题T&A Problem n5.4 分配问题与匈牙利算法分配问题与匈牙利算法 5.4.1 分配问题的数学模型分配问题的数学模型 5.4.2 匈牙利算法匈牙利算法 Page 3 Chapter 5 运输与指派问题运输与指派问题T&A Problem 有

2、一份说明书有一份说明书, 要分别译成英、要分别译成英、日、德、俄四种文字日、德、俄四种文字, 交甲乙丙丁四交甲乙丙丁四个人去完成个人去完成. 因各人专长不同因各人专长不同, 他们他们完成翻译不同文字所需的时间如表完成翻译不同文字所需的时间如表所示所示. 应如何分配应如何分配, 使这四人分别完使这四人分别完成成 这四项任务总的时间最少这四项任务总的时间最少. 假定有假定有m项任务分配给项任务分配给m个人去完成个人去完成, 并指定每人完成其中一项并指定每人完成其中一项, 每项只交给其中一个人去完成每项只交给其中一个人去完成, 第第 i 个人做第个人做第 j 项工作的效率为项工作的效率为cij0，应

3、如何分配使总的应如何分配使总的效率最高效率最高. 5.4.1 指派问题的数学模型指派问题的数学模型指派问题指派问题(分配问题分配问题)效率矩阵：效率矩阵： 利用不同资源完成不同计划活动的效率通常可用利用不同资源完成不同计划活动的效率通常可用表格形式表示，表格中的数字组成效率矩阵表格形式表示，表格中的数字组成效率矩阵.例例效率矩阵效率矩阵 译成译成英文英文译成译成日文日文译成译成德文德文译城译城俄文俄文甲甲21097乙乙154148丙丙13141611丁丁415139工工作作人人 Page 4 Chapter 5 运输与指派问题运输与指派问题T&A Problem 人人工作工作a1a2a

4、iamb1b2bjbmxi1 xi2 xij xi m-1 xim x1j xij x2j xm-1j xmj 指派问题的数学模型指派问题的数学模型: )1,(0, 1mjijijixij，项项任任务务个个人人去去完完成成第第，不不分分配配第第项项任任务务个个人人去去完完成成第第分分配配第第 ), 1,( 10mjixij 或或第第i人完成人完成一项工作一项工作第第j 项工作项工作由一人完成由一人完成 miijmjx1), 1( 1 mjijmix1), 1( 1 .ts11minmmijijijzc x Page 5 Chapter 5 运输与指派问题运输与指派问题T&A Probl

5、em 5.4.2 匈牙利算法匈牙利算法事实：事实：若效率矩阵的所有元素若效率矩阵的所有元素0ijc , 而其中存在一组位于不同行而其中存在一组位于不同行其余的其余的逻辑变量逻辑变量xij=0, 得到的就是问题的最优解得到的就是问题的最优解(最优分配方案最优分配方案).例例 601024570效率矩阵为效率矩阵为令令1322311 xxx问题：问题：如何产生并寻找这组位于不同行不同列的零元素？如何产生并寻找这组位于不同行不同列的零元素？不同列的零元素，不同列的零元素， 则只要令对应于这些零元素位置的逻辑变量则只要令对应于这些零元素位置的逻辑变量xij=1, ，其余，其余xij=011mmijij

6、ijzc x 最最优优值值 Page 6 Chapter 5 运输与指派问题运输与指派问题T&A Problem 匈牙利数学家克尼格匈牙利数学家克尼格(Knig)基础：基础：两个基本定理两个基本定理定理定理1 如果从分配问题效率矩阵如果从分配问题效率矩阵aij的每一行元素中分别的每一行元素中分别减去减去(或加上或加上)一个常数一个常数ui(被称为该行的位势被称为该行的位势), 从每一列分从每一列分别减去别减去(或加上或加上)一个常数一个常数vj(被称为该列的位势被称为该列的位势), 得到一个得到一个新的效率矩阵新的效率矩阵bij, 其中其中bij=aij-ui-vj , 则则bij的最

7、优解等价于的最优解等价于aij的最优解。的最优解。作用：作用： 构造含有零元素的等价效率矩阵。构造含有零元素的等价效率矩阵。 定理定理2 若矩阵若矩阵A的元素分成的元素分成“0”与非与非“0”两部分，则覆盖两部分，则覆盖“0”元素的元素的最少最少直线数等于位于不同行不同列的直线数等于位于不同行不同列的“0”元素元素的最大个数的最大个数.作用：作用：判别效率矩阵中有多少个不同行不同列的零元素。判别效率矩阵中有多少个不同行不同列的零元素。 Page 7 Chapter 5 运输与指派问题运输与指派问题T&A Problem 匈牙利算法的步骤：匈牙利算法的步骤：第一步：第一步： 找出效率矩阵

8、每行的最小元素找出效率矩阵每行的最小元素, ,并分别并分别从每行中减去从每行中减去最小元素最小元素. . 913154111614138144157910241142minmin 59110053241001157800500 541100032450115280产生含产生含零的等零的等价效率价效率矩阵矩阵 每行至少一个每行至少一个0元素元素每列也至少一个每列也至少一个0元素元素第二步：第二步：再找出矩阵每列的最小元素再找出矩阵每列的最小元素, ,再分别再分别从各列中减去从各列中减去. . Page 8 Chapter 5 运输与指派问题运输与指派问题T&A Problem 第三步第三

9、步 判定由前两步得到的效率矩阵中有多少个不同行不同列判定由前两步得到的效率矩阵中有多少个不同行不同列的零元素的零元素. . 按照以下准则进行：按照以下准则进行： (1) 从第一行开始从第一行开始, 若该行只有一个零元素若该行只有一个零元素, 就对这个就对这个零元素打上零元素打上( )号号, 对打对打( )号零元素所在列画一条直线号零元素所在列画一条直线. (2) 从第一列开始从第一列开始, 若该列只有一个零元素就对这个零若该列只有一个零元素就对这个零元素打上元素打上( )号号(同样不考虑已划去的零元素同样不考虑已划去的零元素), 对打对打( )号零号零元素所在行画一条直线元素所在行画一条直线.

10、 若该行没有零元素或有两个以上零元素若该行没有零元素或有两个以上零元素(已划去的不计已划去的不计在内在内), 则转下一行则转下一行, 依次进行到最后一行依次进行到最后一行. 若该列没有零元素或有两个以上零元素若该列没有零元素或有两个以上零元素(已划去的不已划去的不计在内计在内), 则转下一列则转下一列, 依次进行到最后一行依次进行到最后一行. (3) 重复重复(1)、(2)两个步骤两个步骤,直至不能进行为止，直至不能进行为止， 541100032450115280( )( )( ) Page 9 Chapter 5 运输与指派问题运输与指派问题T&A Problem 231 效率矩阵每

11、行效率矩阵每行(或每列或每列)都有一个打都有一个打( )号的零元素号的零元素, 令对应打令对应打( )号零元素的号零元素的xij=1, 就找到了问题的最优解就找到了问题的最优解.打打( )号的零元素个数小于号的零元素个数小于m, 但未被划去的零元素之间存在但未被划去的零元素之间存在闭回路闭回路, 打打( )号的零元素个数小于号的零元素个数小于m, 但矩阵中所有零元素被划去或打但矩阵中所有零元素被划去或打上上( )号号. 541100032450115280( )( )( ) (3) 重复重复(1)、(2)两个步骤两个步骤,直至不能进行为止，直至不能进行为止， 可能出现三种情况可能出现三种情况:

12、 然后对所有打然后对所有打( )号的零元素号的零元素, 或所在行或所在行, 或所在列，或所在列，画画一条直线一条直线.重复重复(1)、(2)两个步骤，直至不能进行为止。两个步骤，直至不能进行为止。这时可顺着闭回路的走向这时可顺着闭回路的走向, 对每个间隔的零元素打对每个间隔的零元素打( )号号, 此时转第四步。此时转第四步。 Page 10 Chapter 5 运输与指派问题运输与指派问题T&A Problem 第四步：第四步：为设法使每一行都有一个为设法使每一行都有一个打打( )号的零元素，需要继续号的零元素，需要继续按定理按定理1 1对矩阵进行变换：对矩阵进行变换： (1) 从矩阵

13、未被直线覆盖的数字中找出一个最小的数字从矩阵未被直线覆盖的数字中找出一个最小的数字k; (2) 对矩阵的每行对矩阵的每行, 当该行有直线覆盖时令当该行有直线覆盖时令ui=0, 无直线覆盖的无直线覆盖的令令ui=k . (3) 对矩阵的每列对矩阵的每列, 当该列有直线覆盖时令当该列有直线覆盖时令vj=-k, 无直线覆盖的无直线覆盖的令令vj=0. (4) 从原矩阵的每个元素从原矩阵的每个元素aij中分别减去中分别减去ui和和vj ,得到一个新的矩得到一个新的矩 阵阵, 转第五步。转第五步。第五步：第五步： 返回到第三步返回到第三步, ,反复进行反复进行, ,一直到矩阵的每一行都有一个一直到矩阵的

14、每一行都有一个打号的零元素为止打号的零元素为止, ,即找到了最优分配方案即找到了最优分配方案. . 541100032450115280( )( )( )20220022 321100054230113080( )( )( )( ) Page 11 Chapter 5 运输与指派问题运输与指派问题T&A Problem 说明：说明：1)第三步中的第二种结果第三步中的第二种结果2打打( )号的零元素个数小于号的零元素个数小于m, 但未被划去的零元素之间但未被划去的零元素之间存在闭回路存在闭回路, 这时可顺着闭回路的走向这时可顺着闭回路的走向, 对每个间隔的对每个间隔的零元素打一零元素打一

15、( )号号, 然后对所有打然后对所有打( )号的零元素号的零元素, 或所在或所在行行, 或所在列画一条直线或所在列画一条直线. 000000 000000( )( )( ) 000000( )( )( )或或 000000( )( )( ) 000000( )( )( ) 000000( )( )或或( ) Page 12 Chapter 5 运输与指派问题运输与指派问题T&A Problem 0405802304502100例例( )( )( )( ) 0405802304500100( )(1)(2) 0405802304502100( )( )( )( )( )( ) 04058

16、02304500100( )( )( )( ) 0405802304500100( )( )( )( )得到得到答案答案 0405802304500100( )( )( )( ) Page 13 Chapter 5 运输与指派问题运输与指派问题T&A Problem 说明：说明：2.分配问题中如果人数和任务数不相等时的处理方法分配问题中如果人数和任务数不相等时的处理方法.(2) 人数人数任务数任务数 工作工作 人人IIIIII13252746336345355652 仍规定每人完成一项工作仍规定每人完成一项工作, 每项工作只交给一个人去完成每项工作只交给一个人去完成 增添两项假想的工作

17、任务增添两项假想的工作任务, 每每个人完成这两项任务时间为零个人完成这两项任务时间为零.IVV0000000000 工作工作 人人IIIIIIIV13252274633363540000 Page 14 Chapter 5 运输与指派问题运输与指派问题T&A Problem 0025600535003630064700523min00000min00223 0003300312001400042400300( )( )( )( )( )3.目标函数为目标函数为 的处理方法的处理方法. mimjijijxaz11max mimjijijxaz11max mimjijijxaz11)(mi

18、n 9131541611141381441579102min 620110523711103108min010015161510 610110423701103008 Page 15 Chapter 5 运输与指派问题运输与指派问题T&A Problem 人们在从事生产活动中，不人们在从事生产活动中，不可避免地要进行物资调运工可避免地要进行物资调运工作。如某时期内将生产基地作。如某时期内将生产基地的煤、钢铁、粮食等各类物的煤、钢铁、粮食等各类物资，分别运到需要这些物资资，分别运到需要这些物资的地区，根据各地的的地区，根据各地的生产量生产量和和需要量需要量及各地之间的及各地之间的运输运输

19、费用费用，如何制定一个运输方，如何制定一个运输方案，使总的运输费用最小。案，使总的运输费用最小。这样的问题称为这样的问题称为运输问题运输问题。5.1 运输模型运输模型 Model of Transportation Problems5.1.1 数学模型数学模型产地销地 A1 10 A2 8 A3 5 B4 3 B3 8 B2 7 B1 5354231682329图图5.1 Page 16 Chapter 5 运输与指派问题运输与指派问题T&A Problem 【例【例5.1】现有】现有A1，A2，A3三个产粮区，可供应三个产粮区，可供应 粮食分别为粮食分别为10，8，5（万吨），现将粮

20、食运往（万吨），现将粮食运往B1，B2，B3，B4四个地区，其需四个地区，其需要量分别为要量分别为5，7，8，3（万吨）。产粮地到需求地的运价（元（万吨）。产粮地到需求地的运价（元/吨）如表吨）如表51所示，问如何安排一个运输计划，使总的运输费所示，问如何安排一个运输计划，使总的运输费用最少。用最少。地区地区产粮区产粮区B1B2B3B4产量产量A1326310A253828A341295需要量需要量578323运价表（元运价表（元/T）表表515.1 运输模型运输模型 Model of Transportation Problems Page 17 Chapter 5 运输与指派问题运输与指派

21、问题T&A Problem 设设xij(i=1,2,3；j=1,2,3,4)为为i个产粮地运往第个产粮地运往第j个需求地的运量，个需求地的运量，这样得到下列运输问题的数学模型：这样得到下列运输问题的数学模型：34333231242322211413121192428353623minxxxxxxxxxxxxZ5810343332312423222114131211xxxxxxxxxxxx3875342414332313322212312111xxxxxxxxxxxx运量应大于或等于零（非负要求），即运量应大于或等于零（非负要求），即 4,3,2, 13,2, 1,0jixij；5.1

22、运输模型运输模型 Model of Transportation Problems Page 18 Chapter 5 运输与指派问题运输与指派问题T&A Problem 有些问题表面上与运输问题没有多大关系，也可以建立与有些问题表面上与运输问题没有多大关系，也可以建立与运输问题形式相同的数学模型运输问题形式相同的数学模型例如例如 【例【例5.2】有三台机床加工三种零件，计划第】有三台机床加工三种零件，计划第i台的生产任务台的生产任务为为a i (i=1,2,3)个零件，第个零件，第j种零件的需要量为种零件的需要量为bj (j=1,2,3)，第，第i台台机床加工第机床加工第j种零件需要

23、的时间为种零件需要的时间为cij ，如表，如表52所示。问如何安所示。问如何安排生产任务使总的加工时间最少？排生产任务使总的加工时间最少？ 零件零件机床机床B1B2B3生产任务生产任务A152350A264160A373440需要量需要量703050150表表525.1 运输模型运输模型 Model of Transportation Problems Page 19 Chapter 5 运输与指派问题运输与指派问题T&A Problem 【解】【解】 设设 xi j (i=1,2,3；j=1,2,3,)为第为第i台机床加工第台机床加工第j种零件的种零件的数量，则此问题的数学模型为数量

24、，则此问题的数学模型为3 , 2 , 13 , 2 , 1, 050307040605043746325min332313322212312111333231232221131211333231232221131211jixxxxxxxxxxxxxxxxxxxxxxxxxxxxZij；5.1 运输模型运输模型 Model of Transportation Problems Page 20 Chapter 5 运输与指派问题运输与指派问题T&A Problem 运输问题的一般数学模型运输问题的一般数学模型12n1a12a2mamb1b2bn产地产地销地销地产量产量销量销量表表1 产销平

25、衡表产销平衡表表表2 单位运价表单位运价表12 n1c11c12 c1n2c21c22 c2nmcm1cm2 cmn产地产地销地销地 Page 21 Chapter 5 运输与指派问题运输与指派问题T&A Problem 产地产地销地销地a1a2aiamb1b2bjbnxij :表示从第表示从第i个产个产地调运给第地调运给第j个销地个销地的物资的单位数量的物资的单位数量xi1 xi2 xij xi n-1 xin x1j xij x2j xm-1j xmj minjijijxcz11min . .tsmiaxinjij, 2 , 1,1 njbxjmiij, 2 , 1,1 0 ijx

26、1. 有有m+n个约束条件，个约束条件，mn个变量个变量2. 运输问题存在可行解，也一定存在最优解运输问题存在可行解，也一定存在最优解 3. 当供应量和需求量都是整数时，则一定存在整数最优解当供应量和需求量都是整数时，则一定存在整数最优解 Page 22 Chapter 5 运输与指派问题运输与指派问题T&A Problem 系数矩阵系数矩阵mnmmnnxxxxxxxxx212222111211 行行m 行行n jmiijeeP 0110miaxinjij, 2 , 1,1 njbxjmiij, 2 , 1,1 111111111111111111若若系数矩阵和增广矩阵的秩是否相等？系

27、数矩阵和增广矩阵的秩是否相等？iminjjab 11 Page 23 Chapter 5 运输与指派问题运输与指派问题T&A Problem 行降秩，取第一行到行降秩，取第一行到m+n1行与行与对应的列（共对应的列（共m+n-1列）组成的列）组成的m+n1阶子式阶子式1, 1121121,nmnnnxxxxxx，m 行行n 行行5.1 运输模型运输模型 Model of Transportation Problems111212122212111111111111111111nnmmmnxxxxxxxxxA Page 24 Chapter 5 运输与指派问题运输与指派问题T&A

28、 Problem 0111111111故故r(A)=m+n1，所以运输问题有，所以运输问题有m+n1个基变量。个基变量。5.1 运输模型运输模型 Model of Transportation Problems基变量的个数基变量的个数=(m+n-1)若若系数矩阵和增广矩阵系数矩阵和增广矩阵的秩的秩=(m+n-1)iminjjab 11 Page 25 Chapter 5 运输与指派问题运输与指派问题T&A Problem 为了在为了在mn个变量中找出个变量中找出m+n1个变量作为一组基变量，就个变量作为一组基变量，就是要在是要在A中找出中找出m+n-1个线性无关的列向量，下面引用闭回个

29、线性无关的列向量，下面引用闭回路的概念寻找这些基变量。路的概念寻找这些基变量。 1 11 22 22 311212,( ,)s ssi ji ji ji ji ji jssxxxxxxi iijjj称称集集合合；互互不不相相同同为一个闭回路，集合中的变量称为回路的顶点，相邻两个变为一个闭回路，集合中的变量称为回路的顶点，相邻两个变量的连线为闭回路的边。量的连线为闭回路的边。 Page 26 Chapter 5 运输与指派问题运输与指派问题T&A Problem 闭回路集合中的变量称为回路的顶点，相邻两个变量的连线闭回路集合中的变量称为回路的顶点，相邻两个变量的连线为闭回路的边。在表为闭

30、回路的边。在表53及表及表54中的变量组构成两个闭回中的变量组构成两个闭回路。路。 x25 x23 B1B2B3B4B5A1 A2 A3 x35A4 x43 x11x12x31 x42表表53表表53中闭回路的变量集中闭回路的变量集合是合是x11, x12, x42, x 43, x 23, x 25, x 35, x 31共有共有8个顶点，个顶点， 这这8个顶点间用水平或垂直个顶点间用水平或垂直线段连接起来，组成一条线段连接起来，组成一条封闭的回路。封闭的回路。 5.1 运输模型运输模型 Model of Transportation Problems Page 27 Chapter 5 运

31、输与指派问题运输与指派问题T&A Problem x11x12x32x33x41 B1B2B3A1 A2 A3 A4 x43表表54 一条回路中的顶点数一定是一条回路中的顶点数一定是偶数，回路遇到顶点必须转偶数，回路遇到顶点必须转90度度与另一顶点连接，表与另一顶点连接，表53中的变中的变量量x 32及及x33不是回闭路的顶点，不是回闭路的顶点，只是连线的交点。只是连线的交点。 表表54中闭回路是中闭回路是123233434111,xxxxxx;,121131352521xxxxxxA ;,2111123233xxxxxB 例如变量组例如变量组A不能组成一条闭回路，但不能组成一条闭回路

32、，但A中包含有闭回路中包含有闭回路 ;,31352521xxxxB的变量数是奇数，显然不是闭回路，也不含有闭回路；的变量数是奇数，显然不是闭回路，也不含有闭回路； 5.1 运输模型运输模型 Model of Transportation Problems Page 28 Chapter 5 运输与指派问题运输与指派问题T&A Problem 333211122321,xxxxxxC C是一条闭回路，若把是一条闭回路，若把C重新写成重新写成 就不难看出就不难看出C仍是一条闭回路。仍是一条闭回路。 111232332321,xxxxxxC 【定理【定理5.2】 若变量组若变量组B 包含有闭

33、回路包含有闭回路 ，则，则B中的变量对应的列向量线性相关。中的变量对应的列向量线性相关。12111,jijijisxxxC【证】由线性代数知，向量组中部分向量组线性相关则该向量组【证】由线性代数知，向量组中部分向量组线性相关则该向量组线性相关，显然，将线性相关，显然，将C中列向量分别乘以正负号线性组合后等于中列向量分别乘以正负号线性组合后等于零，即零，即1 11 22 210si ji ji ji jPPPP因而因而C中的列向量线性相关，所以中的列向量线性相关，所以B中列向量线性相关。中列向量线性相关。5.1 运输模型运输模型 Model of Transportation Problems

34、Page 29 Chapter 5 运输与指派问题运输与指派问题T&A Problem 由定理由定理2可知，当一个变量组中不包含有闭回路，则这些变量对应可知，当一个变量组中不包含有闭回路，则这些变量对应的系数向量线性无关。的系数向量线性无关。求运输问题的一组基变量，就是要找到求运输问题的一组基变量，就是要找到m+n1个变量，使得它们个变量，使得它们对应的系数列向量线性无关，由定理对应的系数列向量线性无关，由定理2，找这样的一组变量是很容，找这样的一组变量是很容易的，只要易的，只要m+n1个变量中不包含闭回路，就可得到一组基变量。个变量中不包含闭回路，就可得到一组基变量。因而有：因而有：

35、【定理【定理3】m+n1个变量组构成基变量的充要条件是它不包含个变量组构成基变量的充要条件是它不包含任何闭回路。任何闭回路。定理定理3告诉了一个求基变量的简单方法，同时也可以判断一组变量告诉了一个求基变量的简单方法，同时也可以判断一组变量是否可以作为某个运输问题的基变量。这种方法是直接在运价表是否可以作为某个运输问题的基变量。这种方法是直接在运价表中进行的，不需要在系数矩阵中进行的，不需要在系数矩阵A中去寻找，从而给运输问题求初始中去寻找，从而给运输问题求初始基可行解带来极大的方便。基可行解带来极大的方便。5.1 运输模型运输模型 Model of Transportation Problem

36、s Page 30 Chapter 5 运输与指派问题运输与指派问题T&A Problem 表表5-5 BjAiB1B2B3B4aiA1c11 c12c13c14 a1x11x12x13x14A2c21c22 c23c24a2x21x22x23x24A3c31c32c2c34a3x31x32x33x34bjb1b2b3b45.1 运输模型运输模型 Model of Transportation Problems例如，例如，m=3,n=4，将运量，将运量xij与运价与运价Cij放在同一张表中，如表放在同一张表中，如表5-5所示。所示。 Page 31 Chapter 5 运输与指派问题运

37、输与指派问题T&A Problem 这个运输问题的基变量数目是这个运输问题的基变量数目是3+41=6。变量组中。变量组中有有7个变量，显然不能构成一组基变量，又如个变量，显然不能构成一组基变量，又如中有中有6个变量，但包含有一条闭回路个变量，但包含有一条闭回路故不能构成一组基变量。变量组故不能构成一组基变量。变量组有有6个变量且不含有任何闭回路，故可以构成此问题的个变量且不含有任何闭回路，故可以构成此问题的一组基变量。一组基变量。22121324323111,xxxxxxx,342413322221xxxxxx24343222,xxxx343332222111,xxxxxx5.1 运输

38、模型运输模型 Model of Transportation Problems Page 32 Chapter 5 运输与指派问题运输与指派问题T&A Problem 本节介绍了具有本节介绍了具有m个产地个产地n个销地的平衡运输问题时：个销地的平衡运输问题时：1.具有具有m+n1个基变量个基变量2. 闭回路的概念闭回路的概念3.怎样判断怎样判断m+n1个变量是否构成一组基变量个变量是否构成一组基变量5.1 运输模型运输模型 Model of Transportation Problems下一节：运输单纯形法下一节：运输单纯形法作业：教材作业：教材P124 T 5，6 建立数学模型建立数

39、学模型 Page 33 Chapter 5 运输与指派问题运输与指派问题T&A Problem 5.2 运输单纯形法运输单纯形法 Transportation Simplex Method Page 34 Chapter 5 运输与指派问题运输与指派问题T&A Problem 表上作业法表上作业法表上作业法的基本思想：表上作业法的基本思想： 先找一个初始方案先找一个初始方案; 根据判断准根据判断准则判断是否最优则判断是否最优, 若不是，则对初始方案进行调整、改进、若不是，则对初始方案进行调整、改进、直至找到最优方案直至找到最优方案.步骤：步骤：分析实际问题列出产销平衡表及单位运

40、价表分析实际问题列出产销平衡表及单位运价表确定初始调运方案确定初始调运方案(最小元素法或最小元素法或vogel法法)求检验数求检验数(闭回路法或位势法闭回路法或位势法)所有检验数所有检验数0得到最优方案得到最优方案算出总的运价算出总的运价找出绝对值最大的负检验数用找出绝对值最大的负检验数用闭回路调整得出新的调整方案闭回路调整得出新的调整方案是是否否运输单纯形法也称为表上作业法，直接在运价表上求最优解运输单纯形法也称为表上作业法，直接在运价表上求最优解 Page 35 Chapter 5 运输与指派问题运输与指派问题T&A Problem 5.2.1初始基可行解初始基可行解1. 最小元素

41、法最小元素法 最小元素法的思想是就近优先运送，即最小运价最小元素法的思想是就近优先运送，即最小运价Cij对应的变量对应的变量xij优先赋值优先赋值然后再在剩下的运价中取最小运价对应的变量赋值并满足约束，然后再在剩下的运价中取最小运价对应的变量赋值并满足约束，依次下去，直到最后得到一个初始基可行解。依次下去，直到最后得到一个初始基可行解。jiijbax,min5.2 运输单纯形法运输单纯形法 Transportation Simplex Method Page 36 Chapter 5 运输与指派问题运输与指派问题T&A Problem 例例1 某食品公司经销的主要产品之一是糖果某食品公

42、司经销的主要产品之一是糖果, ,已知信息如下表已知信息如下表B1B2B3B4生产量生产量A13113107A219284A3741059销售量销售量3656门门加加运价运价市市部部工工厂厂(元元/t) 问该公司应如何调问该公司应如何调运运, ,在满足各门市部销在满足各门市部销售需要的情况下售需要的情况下, ,使总使总的运费支出最少？的运费支出最少？ 表表1 产销平衡表产销平衡表表表2 单位运价表单位运价表解：解： B1B2B3B4产产量量A17A24A39销量销量3656产地产地销地销地 B1B2B3B4A1311310A21928A374105产地产地销地销地2- 初始方案的确定初始方案的确

43、定 Page 37 Chapter 5 运输与指派问题运输与指派问题T&A Problem 确定初始方案确定初始方案1)最小元素法最小元素法(就近供应就近供应) 从单位运价表中最小的运价处开始确定供销关系，从单位运价表中最小的运价处开始确定供销关系，依次类推，直到给出全部方案为止。依次类推，直到给出全部方案为止。 B1B2B3B4产产量量A17A24A39销量销量3656产地产地销地销地 B1B2B3B4A1311310A21928A374105产地产地销地销地 3 1 6 4 3 3说明：说明： 1) 在调运方案表中在调运方案表中, 称填写数字处为称填写数字处为有数字的格有数字的格,

44、 它对应运它对应运输问题解中的输问题解中的基变量取值基变量取值; 称不填数字处为称不填数字处为空格空格, 它对应解中的它对应解中的非非基变量基变量. 因运输问题中基变量数一般为因运输问题中基变量数一般为m+n-1,故调运方案中有数故调运方案中有数字的格也为字的格也为m+n-1. Page 38 Chapter 5 运输与指派问题运输与指派问题T&A Problem 2) 当选定最小元素后当选定最小元素后, , 发现该元素所在行的产地产量发现该元素所在行的产地产量等于所在列的销地的销量等于所在列的销地的销量, , 这时在产销平衡表上填一个数这时在产销平衡表上填一个数, ,运价表上就要同时

45、划去一行和一列，为了使调运方案中的运价表上就要同时划去一行和一列，为了使调运方案中的有数字格仍为有数字格仍为m+n-1个个，需要在同时划去的该行或该列的，需要在同时划去的该行或该列的任一空格位置补填一个任一空格位置补填一个0 0。 表表1 产销平衡表产销平衡表表表2 单位运价表单位运价表 B1B2B3B4产产量量A17A24A39销量销量3656产地产地销地销地 B1B2B3B4A131145A27738A312106产地产地销地销地 3 60000 Page 39 Chapter 5 运输与指派问题运输与指派问题T&A Problem 2)Vogel法法基本步骤：基本步骤：1)从运价

46、表上分别找出每行与每列的最小的两个元素之差从运价表上分别找出每行与每列的最小的两个元素之差;2)再从再从差值最大差值最大的行或列中找出的行或列中找出最小运价最小运价确定供需关系和供确定供需关系和供应数量应数量.3)当产地或销地中有一方数量上供应完毕或得到满足时，划当产地或销地中有一方数量上供应完毕或得到满足时，划去运价表中对应的行或列，在重复上述步骤去运价表中对应的行或列，在重复上述步骤. Page 40 Chapter 5 运输与指派问题运输与指派问题T&A Problem B1B2B3B4产产量量A17A24A39销量销量3656产地产地销地销地 B1B2B3B4A1311310A

47、21928A374105产地产地销地销地 2 16 5 3 3两最小元素之差两最小元素之差(1) (2) (3) (4)011两两最最小小元元素素之之差差(1)(2)(3)(4)2513012213012127612108(5)(5)2 Page 41 Chapter 5 运输与指派问题运输与指派问题T&A Problem 2-2 最优性检验与方案的调整最优性检验与方案的调整1)闭回路法闭回路法调运方案中由一个空格和若干个有数字格的水平调运方案中由一个空格和若干个有数字格的水平和垂直连线包围成的封闭回路和垂直连线包围成的封闭回路闭回路：闭回路：1)1)构建闭回路构建闭回路; ;求解检验

48、数的方法：求解检验数的方法： 令某非基变量取值为令某非基变量取值为1 1，通过变化原基，通过变化原基变量的值找出一个新的可行解，将其同原来的基可行解目变量的值找出一个新的可行解，将其同原来的基可行解目标函数值的变化比较。标函数值的变化比较。基本步骤：基本步骤：2)2)求空格对应的检验数求空格对应的检验数) )根据检验数判定最优性根据检验数判定最优性, ,若不是最优解若不是最优解, ,改进方案改进方案. . Page 42 Chapter 5 运输与指派问题运输与指派问题T&A Problem (A1, B1)的检验数的检验数 B1B2B3B4A1311310A21928A374105产

49、地产地销地销地3-3+2-1=1 B1B2B3B4A1A2A3产地产地销地销地1检验数表检验数表 B1B2B3B4产量产量A1437A2314A3639销量销量3656产地产地销地销地(-1)(+1)(-1)(+1) B1B2B3B4产量产量A1437A2314A3639销量销量3656产地产地销地销地(-1)(+1)(-1)(+1)(A2, B2)的检验数的检验数(-1)(+1)9-2+3-10+5-4=12 B1B2B3B4产量产量A1437A2314A3639销量销量3656产地产地销地销地(-1)(+1)(+1)(-1)(+1)(-1)(A3, B1)的检验数的检验数7-1+2-3+1

50、0-5=1010112-1单位运价表单位运价表 Page 43 Chapter 5 运输与指派问题运输与指派问题T&A Problem 根据检验数判定最优性：根据检验数判定最优性：若检验数表中所有数字若检验数表中所有数字0, 给定的方案是最优方案；给定的方案是最优方案；若检验数表中有数字若检验数表中有数字0, 给定的方案可改进；给定的方案可改进；改进方案的方法：改进方案的方法： 从检验数为负值的格出发从检验数为负值的格出发(若有两个以上若有两个以上负检验数时负检验数时, 从绝对值最大的负检验数出发从绝对值最大的负检验数出发), 作一条除该作一条除该空格外其余顶点均为有数字格组成的闭回路

51、空格外其余顶点均为有数字格组成的闭回路. 在这条闭回在这条闭回路上路上, 按上面讲的方法对运量作最大可能的调整按上面讲的方法对运量作最大可能的调整. B1B2B3B4产量产量A1437A2314A3639销量销量3656产地产地销地销地(+1)(-1)(+1)(-1) B1B2B3B4产量产量A1527A2314A3639销量销量3656产地产地销地销地后面的过程略后面的过程略 Page 44 Chapter 5 运输与指派问题运输与指派问题T&A Problem 说明：说明： 若在闭回路调整中若在闭回路调整中,在需要减少运量的地方有两个以在需要减少运量的地方有两个以上相等的最小数，这

52、样调整时原先空格处填上了这个最小上相等的最小数，这样调整时原先空格处填上了这个最小数，把最小数的格之一变为空格，其余均补添数，把最小数的格之一变为空格，其余均补添0，补填，补填0的的格当作有数字格看待，格当作有数字格看待，使方案中有数字的格仍为使方案中有数字的格仍为m+n-1个个.缺点：缺点： 当一个运输问题的产地和销地数很多时当一个运输问题的产地和销地数很多时, ,计算检验数的计算检验数的工作量太繁重工作量太繁重. Page 45 Chapter 5 运输与指派问题运输与指派问题T&A Problem 2)位势法位势法 B1B2B3B4A1A2A3产地产地销地销地316433用最小元

53、素法确定的初始调运方案用最小元素法确定的初始调运方案第一步第一步单位运价表单位运价表 B1B2B3B4A1311310A21928A374105产地产地销地销地 仿照初始调运方案表仿照初始调运方案表作一新表作一新表, 将初始调运方案表将初始调运方案表中有数字格的地方换成单位中有数字格的地方换成单位运价表中对应的运价运价表中对应的运价. B1B2B3B4A1310A212A345产地产地销地销地第二步第二步 在新表的右面和下面增在新表的右面和下面增加一行和一列加一行和一列, ,并填上一些数字并填上一些数字, ,使表中的各个数刚好等于它所使表中的各个数刚好等于它所在行和列的这些新填写的数字在行和列

54、的这些新填写的数字之和之和. B1B2B3B4A1310A212A345产地产地销地销地ui10-4vj1829第第i行的位势行的位势第第j列的位势列的位势 Page 46 Chapter 5 运输与指派问题运输与指派问题T&A Problem B1B2B3B4A1310A212A345产地产地销地销地ui10-4vj1829位势的求法位势的求法 可先任意决定其中的一个可先任意决定其中的一个, 然后推然后推导出其他位势的数值导出其他位势的数值先令先令u1=1，因为因为u1+ v4 =10, 所以所以v4 =9因为因为u1+ v3 =3, 所以所以v3 =2因为因为u3+ v4 =5,

55、所以所以u3 =-4因为因为u2+ v3 =2, 所以所以u2 =0因为因为u2+ v1 =1, 所以所以v1 =1因为因为u3+ v2 =4, 所以所以v2 =8 Page 47 Chapter 5 运输与指派问题运输与指派问题T&A Problem 第三步第三步 求各空格的检验数求各空格的检验数 B1B2B3B4uiA13101A2120A345-4vj1829产地产地销地销地(-1)(+1)(+1)(-1)(+1)(-1)表示表示(A3, B1)的检验数的检验数31 1231053131 c )()()()()(123231414331vuvuvuvuvuc )(1331vuc )(jiijijvuc 一般地一般地 Page 48 Chapter 5 运输与指派问题运输与指派问题T&A Problem B1B2B3B4A1310A212A345产地产地销地销地ui10-4vj1829 B1B2B3B4A1311310A21928A374105产地产地销地销地行列位势行列位势相加填入相加填入相应空格相应空格