《第04章运输问题课件》由会员分享，可在线阅读，更多相关《第04章运输问题课件（112页珍藏版）》请在金锄头文库上搜索。
1、Page1of9第第4 4章章 运输问题运输问题Page2of9运输问题与有关概念运输问题与有关概念运输问题的求解运输问题的求解表上作业法表上作业法运输问题应用运输问题应用建模建模本章内容重点本章内容重点Page3of94.1 4.1 运输问题模型及有关概念运输问题模型及有关概念 4.1.1 4.1.1 问题的提出问题的提出 一一般般的的运运输输问问题题就就是是要要解解决决把把某某种种产产品品从从若若干干个个产产地地调调运运到到若若干干个个销销地地，在在每每个个产产地地的的供供应应量量与与每每个个销销地地的的需需求求量量已已知知，并并知知道道各各地地之之间间的的运运输输单单价价的的前前提提下下
2、，如如何何确确定定一一个个使使得得总总的的运运输输费费用用最最小小的的方方案。案。Page4of9 例例4.14.1:某公司从三个产地某公司从三个产地A A1 1、A A2 2， A A3 3将将物品运往四个销地物品运往四个销地B B1 1、B B2 2、B B3 3、 B B4 4 ，各产地，各产地的产量、各销地的销量和各产地运往各销地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？运可使总运输费用最小？Page5of9 解：解： 产销平衡问题：产销平衡问题： 总产量总产量 = = 总销量总销量 设设 x
3、 xijij 为从产地为从产地A Ai i运往销地运往销地B Bj j的运输量，的运输量，得到下列运输量表：得到下列运输量表： Page6of9产量产量( 3个个)销量（销量（4个）个）Page7of9系数矩阵Page8of9 模型系数矩阵特征模型系数矩阵特征 1.1.共有共有m m+ +n(3+4)n(3+4)行，分别表示各行，分别表示各产地和销地；产地和销地；m m n(3*4)n(3*4)列，分别表列，分别表示各决策变量；示各决策变量； 2.2.每列只有两个每列只有两个 1 1，其余为，其余为 0 0，分别表示只有一个产地和一个销地分别表示只有一个产地和一个销地被使用。被使用。Page9
4、of9 一般运输问题的提法：一般运输问题的提法： 假假设设 A A1 1, , A A2 2, , ,A Am m 表表示示某某物物资资的的m m个个产产地地；B B1 1, ,B B2 2, , ,B Bn n 表表示示某某物物资资的的n n个个销销地地；s si i表表示示产产地地 A Ai i 的的产产量量；d dj j 表表示示销销地地 B Bj j 的的销销量量；c cijij 表表示示把把物物资资从从产产地地 A Ai i 运运往往销销地地 B Bj j 的的单单位位运运价价（表（表4-34-3）。如果）。如果 s1+s2+sm=d1+d2+dn则则称称该该运运输输问问题题为为产产
5、销销平平衡衡问问题题；否否则则，称称产产销销不平衡。不平衡。4.1.2 4.1.2 一般运输问题的线性规划模型及求解思路一般运输问题的线性规划模型及求解思路Page10of9表表4-2 4-2 运输问题数据表运输问题数据表 销地产地B1 B2 Bn产量A1 A2 Amc11 c12 c1nc21 c22 c2n cm1 cm2 cmns1 s2 sm销量d1 d2 dn 设设 x xijij 为为从从产产地地 A Ai i 运运往往销销地地 B Bj j 的的运运输输量量，根根据据这这个个运运输输问问题题的的要要求求，可可以以建建立立运输变量表（表运输变量表（表 4-34-3）。）。产销平衡产
6、销平衡Page11of9表表4-3 4-3 运输问题变量表运输问题变量表 销地产地B1 B2 Bn产量A1 A2 Amx11 x12 x1nx21 x22 x2n xm1 xm2 xmns1 s2 sm销量d1 d2 dn产销平衡产销平衡m nMinf= cij xij i=1 j=1 ns.t. xij =si i=1,2,m (4-5) j =1m xij =dj j=1,2,n(4-6)i =1 xij 0 (i=1,2,m;j=1,2,n) 对于对于产销平衡产销平衡问题，可得到下列运输问题的问题，可得到下列运输问题的模型：模型：Page13of9在实际问题建模时，还会出现如下一些变化：
7、在实际问题建模时，还会出现如下一些变化： （1 1）有有时时目目标标函函数数求求最最大大，如如求求利利润润最最大或营业额最大等；大或营业额最大等； （2 2）当当某某些些运运输输线线路路上上的的能能力力有有限限制制时时，模模型型中中可可直直接接加加入入（等等式式或或不不等等式式） 约束；约束； (3)(3)产产销销不不平平衡衡的的情情况况。当当销销量量大大于于产产量量时时可可加加入入一一个个虚虚设设的的产产地地去去生生产产不不足足的的物物资资，这这相相当当于于在在式式（4-24-2）每每一一式式中中加加上上 1 1 个个松松弛弛变变量量，共共 m m 个个；当当产产量量大大于于销销量量时时可可
8、加加入入一一个个虚虚设设的的销销地地去去消消化化多多余余的的物物资资，这这相相当当于于在在式式（4-34-3）每每一一式式中中加加上上 1 1 个松弛变量，共个松弛变量，共 n n 个。个。Page15of9运运输输问问题题是是一一种种特特殊殊的的线线性性规规划划问问题题，在在求求解解时时依依然然可可以以采采用用单单纯纯形形法法的的思思路路，如如图图4-14-1所示所示。由由于于运运输输规规划划系系数数矩矩阵阵的的特特殊殊性性，如如果果直直接接使使用用线线性性规规划划单单纯纯形形法法求求解解计计算算，则则无无法法利利用用这这些些有有利利条条件件。人人们们在在分分析析运运输输规规划划系系数数矩矩
9、阵阵特特征征的的基基础础上上建建立立了了针针对对运运输输问题的表上作业法。问题的表上作业法。下下面面主主要要讨讨论论基基本本可可行行解解、检检验验数数以以及及基基的转换的转换等问题。等问题。 续下页续下页Page16of9基本可行解基本可行解是否最优解是否最优解结束结束换基换基是是否否图图4-1 4-1 运输问题的求解思路运输问题的求解思路返回返回转转2828页页Page17of9 考考虑虑产产销销平平衡衡问问题题，由由于于我我们们关关心心的的量量均均在在表表4-24-2与与表表4-34-3中中，因因此此考考虑虑把把表表4-4-2 2与表与表4-34-3合成一个表合成一个表, , 如下表如下表
10、4-44-4 ( (下页）下页）4.1.3 4.1.3 运输问题求解的有关概念运输问题求解的有关概念( (产销平衡产销平衡) )Page18of9 销地产地B1B2Bn产量A1 c11 x11c12 x12c1n x1na1 A2 c21 x21c22 x22c2n x2na2 Amcm1 xm1cm2 xm2cmn xmnam销量b1b2bn 销地产地B1B2Bn产量A1 c11 x11c12 x12c1n x1na1 A2 c21 x21c22 x22c2n x2na2 Amcm1 xm1cm2 xm2cmn xmnam销量b1b2bn 销地产地B1B2Bn产量A1 c c1111 x x
11、1111c12 x12c1n x1ns1 A2 c21 x21c22 x22c2n x2ns2 Amcm1 xm1cm2 xm2cmn xmnsm销量d1d2dn表表4-4 4-4 运输问题求解作业数据表运输问题求解作业数据表平衡平衡转31Page19of9 中任意中任意m+nm+n阶子式等于零，取第一行到阶子式等于零，取第一行到m+nm+n1 1行与行与对应的列（共对应的列（共m+nm+n-1-1列）组成的列）组成的m+nm+n1 1阶子式。阶子式。m m个个n n个个m*nPage20of9故故r r( (A A)=)=m+nm+n1 1所以运输问题有所以运输问题有m+nm+n1 1个基变
12、量。个基变量。Page21of9 运输问题的基变量共有运输问题的基变量共有 m m + + n n -1 -1 个，个，A A的秩为的秩为 m m + + n n -1 -1。 怎样找这怎样找这m m + + n n -1 -1 个基变量呢？个基变量呢？m m + + n n -1 -1 个基变量个基变量 不含闭回路。不含闭回路。 运输问题的基变量运输问题的基变量Page22of9 定义定义4.1 4.1 在表在表4-44-4的决策变量格中，凡的决策变量格中，凡是能够排列成下列形式的是能够排列成下列形式的 xab ,xac ,xdc ,xde ,xst ,xsb(4-7) 或或 xab ,xc
13、b ,xcd ,xed ,xst ,xat(4-8) 其其中中，a a, ,d d, , ,s s 各各不不相相同同；b b, ,c c, , ,t t 各各不不相相同同，我我们们称称之之为为变变量量集集合合的的一一个个闭闭回回路路，并并将将式式（4-74-7）、式式（4-84-8）中中的的变变量量称称为为这这个个闭回路的顶点闭回路的顶点。闭回路闭回路Page23of9例如，例如，x13,x16,x36,x34,x24,x23；x23,x53,x55,x45,x41,x21；x11,x14,x34,x31等都是闭回路。等都是闭回路。 若把闭回路的各变量格看作节点，若把闭回路的各变量格看作节点，
14、在表中可以画出如下形式的闭回路：在表中可以画出如下形式的闭回路：闭回路示意图闭回路示意图Page24of9销地B1B2B3B4B5B6产量A1x11x12x13x14x15x16a1A2x21x22x23x24x25x26a2A3x31x32x33x34x35x36a3A4x41x42x43x44x45x46a4A5x51x52x53x54x55x56a5销量b1b2b3b4b5b6平衡Page25of9 根根据据定定义义可可以以看看出出闭闭回回路路的的一一些些明显特点：明显特点： (1)(1)闭闭回回路路均均为为一一封封闭闭折折线线，它它的的每一条边，或为水平的，或为垂直的；每一条边，或为水
15、平的，或为垂直的； (2)(2)闭闭回回路路的的每每一一条条边边（水水平平的的或或垂垂直直的的）均均有有且且仅仅有有两两个个闭闭回回路路的的顶顶点（变量格）。点（变量格）。 Page26of9 (1) (1) 设设 xab , xac , xdc , xde , xst , xsb是是一一个个闭闭回回路路，那那么么该该闭闭回回路路中中变变量量所所对对应应的的系系数数列列向向量量 pab , pac ,pdc , pde , pst , psb线性相关线性相关； (2) (2) 若若变变量量组组 xab , xcd , xef , xst 中中包包含含一一个个部部分分组组构构成成闭闭回回路路，那
16、那么么该该变变量量组组所所对对应应的的系系数数列列向向量量 pab , pcd,pef , pst ,线性相关线性相关。 关于闭回路有如下的一些重要结论：关于闭回路有如下的一些重要结论：Page27of9销地B1B2B3B4产量A1x11x12x13x14a1A2x21x22x23x24a2A3x31x32x33x34a3A4x41x42x43x44a4A5x51x52x53x54a5销量b1b2b3b4平衡显然显然不是个闭回路不是个闭回路，但是但是其部分其部分却构一个闭回路却构一个闭回路定定理理4.14.1 变变量量组组 xab , xcd , xef , xst , 所所对对应应的的系系数
17、数列列向向量量 pab , pcd , pef ,pst 线线性性无无关关的的充充分分必必要要条条件件是是这这个个变变量量组组中中不不包包含闭回路含闭回路。推推论论 产产销销平平衡衡运运输输问问题题的的 m m + + n n -1 -1 个个变变量量构构成成基基变变量量的的充充分分必必要要条条件件是是它它不不含含闭回路。闭回路。4.24.2运输问题求解运输问题求解表上作业法表上作业法适用的范围：适用的范围：产销平衡产销平衡表上作业法：表上作业法：和单纯形法完全类似：和单纯形法完全类似： 1.1.确定一个初始基本可行解确定一个初始基本可行解 2.根根据据最最优优性性判判别别准准则则来来检检查查
18、这这个个基基本本可可行解是不是最优的？行解是不是最优的？ 如果是，则计算结束；如果是，则计算结束； 3. 3. 如果不是，则进行换基。如果不是，则进行换基。Page30of9 根根据据上上面面的的讨讨论论，要要求求得得运运输输问问题题的的初初始始基基本本可可行行解解，必必须须保保证证找找到到 m m + + n n 1 1 个不包含闭回路的基变量个不包含闭回路的基变量。 一般的方法步骤如下：一般的方法步骤如下： 一、初始基本可行解的确定一、初始基本可行解的确定Page31of9 (1)(1)在在运运输输问问题题求求解解作作业业数数据据表表中中任任选选一一个个单单元元格格 xij ( ( A A
19、i i 行行 B Bj j 列列交交叉叉位位置置上上的的格格),),令令 xij=minai,bj 即即从从 A Ai i 向向 B Bj j 运运最最大大量量( (使使行行或或列列在在允允许许的的范范围围内内尽尽量量饱饱和和，即即使使一一个个约约束束方程得以满足方程得以满足),),填入填入 xij的相应位置；的相应位置； Page32of9 (2)(2)从从 aiai 和和 bjbj 中中分分别别减减去去 xijxij 的的值值，修修正正为为新新的的aiai 和和 bj bj 即即调调整整 AiAi 的的拥拥有有量量及及 BjBj 的需求量；的需求量； (3)(3)若若 aiai = = 0
20、 0，则则划划去去对对应应的的行行（已已经经把把拥拥有有的的量量全全部部运运走走），若若 bjbj = = 0 0 则则划划去去对对应应的的列列（已已经经把把需需要要的的量量全全部部运运来来），且且每每次次只只划划去去一一行行或或一一列列（即即每每次次要要去去掉掉且且只只去去掉掉一一个个约束）；约束）；Page33of9(4)(4)当当最最终终的的运运输输量量选选定定时时，其其所所在在行行、列列同同时时满满足足，此此时时要要同同时时划划去去一一行行和和一一列列。这这样样，运运输输平平衡衡表表中中所所有有的的行行与与列列均均被被划划去去，则则得得到到了了一一个个初初始始基基本本可可行行解。解。
21、否否则则在在剩剩下下的的运运输输平平衡衡表表中中选选下下一一个变量，返回个变量，返回(1)(1)。Page34of9上述计算过程可用流程图描述如下（图上述计算过程可用流程图描述如下（图4-4-2 2）取未划去的单元格取未划去的单元格x xijij , ,令令x xijij = min = min a ai i , , b bj j a ai i = = a ai i - - x xijijb bj j = = b bj j - - x xijija ai i = = 0?0?划去第划去第i i行行划去第划去第j j列列是否 b bj j = 0 = 0否所所有有行行列列是是否否均均被被划划去去
22、是找到初始基找到初始基本可行解本可行解图图4-2 4-2 求运输问题的初始基本可行解过程求运输问题的初始基本可行解过程注：为了方便，这注：为了方便，这里总记剩余的产量里总记剩余的产量和销量为和销量为ai, bjPage35of9B1B2B3B4产量A13113107A219284A3741059销量365620（产销平衡）453152Page36of9Page37of9 按照上述方法所产生的一组变量的按照上述方法所产生的一组变量的取值将满足下面条件：取值将满足下面条件： (1)(1)所得的变量均为非负，且变量总所得的变量均为非负，且变量总数恰好为数恰好为 m m + + n n 1 1 个；个
23、； (2)(2)所有的约束条件均得到满足；所有的约束条件均得到满足； (3)(3)所得的变量不构成闭回路。所得的变量不构成闭回路。Page38of9 在在上上面面的的方方法法中中，x xijij 的的选选取取方方法法并并没没有有给给予予限限制制，若若采采取取不不同同的的规规则则来来选选取取 x xijij ，则则得得到到不不同同的的方方法法，较较常常用用的的方方法法有有西西北北角角法法和和最最小小元元素素法法。下下面面分别举例予以说明分别举例予以说明。Page39of9 西北角法西北角法：从西北角（左上角）格：从西北角（左上角）格开始，在格内的右下角标上允许取得的开始，在格内的右下角标上允许取
24、得的最大数。然后按行（列）标下一格的数。最大数。然后按行（列）标下一格的数。若某行（列）的产量（销量）已满足，若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解行下去，直至得到一个基本可行解。1.1.西北角法西北角法例Page40of9 （2 2）最小元素法：最小元素法：从运价最小的从运价最小的格开始，在格内的右下角标上允许取格开始，在格内的右下角标上允许取得的最大数。然后按运价从小到大顺得的最大数。然后按运价从小到大顺序填数。若某行（列）的产量（销量）序填数。若某行（列）的产量（销量）已满足，则把该行（列）的其
25、他格划已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基去。如此进行下去，直至得到一个基本可行解。本可行解。2.2.最小元素法最小元素法：表1Page42of9B1B2B3B4产量A13113107A219284A3741059销量365620（产销平衡）342236西北角法：初始基本可行解西北角法：初始基本可行解Page43of9Page44of9B1B2B3B4产量A13113107A219284A3741059销量365620（产销平衡）314633最小元素法：初始基本可行解最小元素法：初始基本可行解Page45of9Page46of9 注注: :应用西北角法和最小元素法，
26、每次填应用西北角法和最小元素法，每次填完数，都只划去一行或一列，只有完数，都只划去一行或一列，只有最后一个最后一个元例外元例外（同时划去一行和一列）。（同时划去一行和一列）。 当填上一个数后当填上一个数后行、列同时饱和时行、列同时饱和时，也，也应任意划去一行（列），在保留的列（行）应任意划去一行（列），在保留的列（行）中没被划去的格内标一个中没被划去的格内标一个0 0（目的是保证有目的是保证有m+n-1m+n-1个基变量个基变量）, ,然后划去该列（行）。然后划去该列（行）。（具体做法，见下例（具体做法，见下例4.34.3）Page47of9例4.3B1B2B3B4产量A1385975A229
27、4860A3637560销量35405565195（平衡）Page48of9B1B2B3B4产量A1385975A2294860A3637560销量35405565195（平衡）西北角法：西北角法：3540055560Page49of9B1B2B3B4产量产量A13358405975A22904558560A363756060销量销量35405565195（平衡）（平衡）西北角法西北角法Page50of9例，用最小元素法例，用最小元素法B1B2B3B4产量A1385975A2264890A3657530销量35405565195（平衡）Page51of9B1B2B3B4产量A1385975A2
28、264890A3657530销量35405565195（平衡）355503045Page52of9B1B2B3B4产量A13810596575A223560455890A365307530销量35405565195（平衡）Page53of9 由由于于目目标标要要求求极极小小，因因此此，当当所所有有的的检检验验数数都都大大于于或或等等于于零零时时该该调调运运方方案案就就是是最最优优方方案案；否否则则就就不不是是最最优优，需需要要进进行行调调整整。下下面面介介绍绍两两种种求求检检验验数数的的方方法法: : 闭回路法闭回路法和和位势法位势法二、基本可行解的最优性检验二、基本可行解的最优性检验 Pag
29、e54of9 为为了了方方便便，我我们们以以表表1给给出出的的初初始始基基本本可可行行解解方方案案为为例例，考考察察初初始始方方案案的的任任意意一一个个非非基基变变量量，比比如如x24。根根据据初初始始方方案案，产产地地A2的的产产品品是是不不运运往往销销地地B4的的。如如果果现现在在改改变变初初始始方方案案，把把A2的的产产品品运运送送1个个单单位位给给B4，那那么么为为了了保保持持产产销销平平衡衡，就就必必须须使使x14或或x34减减少少1个个单单位位；而而如如果果x14减减少少1个个单单位位，第第1行行的的运运输输量量就就必必须须增增加加1个个单单位位，例例如如x13增增加加1个个单单位
30、位，那那么么为为了了保保持持产产销销平平衡衡，就就必必须须使使x23减减少少1个单位。个单位。 1 1、闭回路法、闭回路法Page55of9 这这个个过过程程就就是是寻寻找找一一个个以以非非基基变变量量x24为为起起始始顶顶点点的的闭闭回回路路x24，x14，x13，x23，这这个个闭闭回回路路的的其其他他顶顶点点均均为为基基变变量量(对对应应着着填填上上数数字字的的格格)。容容易易计计算算出出上上述述调调整整使使总总的的运运输输费费用用发发生生的的变变化化为为810+32-1，即即总总的的运运费费减减少少1个个单单位位，这这就就说说明明原原始始方方案案不不是是最最优优方方案案，可可以以进进行
31、行调调整整以以得得到到更更好好的方案。的方案。Page56of9 可以证明，如果对闭回路的方向不可以证明，如果对闭回路的方向不加区别（即只要起点及其他所有顶点完加区别（即只要起点及其他所有顶点完全相同，而不区别行进方向），那么以全相同，而不区别行进方向），那么以每一个非基量为起始顶点的闭回路就存每一个非基量为起始顶点的闭回路就存在而且唯一。因此，在而且唯一。因此，对每一个非基变量对每一个非基变量可以找到而且只能找到唯一的一个闭回可以找到而且只能找到唯一的一个闭回路。路。 表表4-104-10中中用用虚虚线线画画出出以以非非基基变变量量 x x2222 为起始顶点的闭回路。为起始顶点的闭回路。P
32、age57of9表表4-10 4-10 以非基变量以非基变量 x x2222 为起始顶点的闭回路为起始顶点的闭回路销地销地产地产地B1B2B3B4产量产量3 11 3 410 371 39 2 18 47 4 610 5 39销量销量365620(产销平衡产销平衡)A1A2A312-1Page58of9 可可以以计计算算出出以以非非基基变变量量 x x2222 为为起起始始顶顶点点的的闭闭回回路路调调整整使使总总的的运运输输费费用发生的变化为用发生的变化为 92+310+541 即即总总的的运运费费增增加加 1 1 个个单单位位，这这就就说说明这个调整不能改善目标值。明这个调整不能改善目标值。
33、 从从上上面面的的讨讨论论可可以以看看出出，当当某某个个非非基基变变量量增增加加一一个个单单位位时时，有有若若干干个个基变量的取值受其影响。基变量的取值受其影响。Page59of9 这这样样，利利用用单单位位产产品品变变化化（运运输输的的单单位位费费用用）可可计计算算出出它它们们对对目目标标函函数数的的综综合合影影响响，其其作作用用与与线线性性规规划划单单纯纯形形方方法法中中的的检检验验数数完完全全相相同同。故故也也称称这这个个综综合合影影响响为为该该非非基基变变量量对对应应的的检检验验数数。上上面面计计算算的的两两个个非非基基变变量量的的检检验验数数为为 2424 = = -1-1， 222
34、2 = = 1 1。闭闭回回路路方方法法原原理理就就是是通通过过寻寻找找闭闭回回路路来来找找到到非非基基变变量量的的检检验数。验数。 Page60of9 如如果果规规定定作作为为起起始始顶顶点点的的非非基基变变量量为为第第 1 1 个个顶顶点点，闭闭回回路路的的其其他他顶顶点点依依次次为为第第 2 2 个个顶顶点点、第第 3 3 个个顶顶点点那那么就有么就有 ijij = = ( (闭闭回回路路上上的的奇奇数数次次顶顶点点单单位位运运费费之之和和) ) - - ( (闭闭回回路路上上的的偶偶数数次次顶顶点点单单位位运费之和运费之和) ) 其中其中 ij ij 为非基变量的下角指标为非基变量的下
35、角指标。Page61of9 按按上上述述作作法法，可可计计算算出出表表1 1的的所所有有非非基基变变量量的的检检验验数数，把把它它们们填填入入相相应应位位置置的的方方括括号号内内，如图如图4-114-11所示。所示。 销地产地B1B2B3B4产量A13 1 1 11 2 2 3 410 37A21 39 1 1 2 18 -1-1 4A37 1010 4 610 1212 5 39销量365620(产销平衡)表表4-11 4-11 初始基本可行解及检验数初始基本可行解及检验数Page62of9 闭闭回回路路法法的的主主要要缺缺点点是是：当当变变量量个个数数较较多多时时，寻寻找找闭闭回回路路以以
36、及及计计算算两两方方面都会产生困难。面都会产生困难。位势：设对应位势：设对应基变量基变量xij的的 m +n -1个个 c cij ，存在，存在ui,vj满足满足 ui+vj=cij，i=1,2,m;j=1,2,n. 称称这这些些 ui,vj为为该该基基本本可可行行解解对对应应的的位势。位势。 2.2.位势法位势法Page64of9由于有由于有m+ n个变量个变量（ui,vj ），）， m+n-1个方程（基变量个数），个方程（基变量个数）， 故有一个自由变量，位势不唯一故有一个自由变量，位势不唯一。 利用位势求检验数：利用位势求检验数： ij=cij-ui-vji=1,m;j=1,nPage6
37、5of9前例，位势法求检验数：前例，位势法求检验数：step 1step 1 从任意基变量对应的从任意基变量对应的 cij开始开始, ,任取任取 ui 或或 vj ，然后利用公式，然后利用公式 cij= ui+vj依次找出依次找出 m+n个个 ui,vj从从c14=10开始开始 step 2step 2 计算非基变量的检验数计算非基变量的检验数 ij= cij-ui-vj；填入圆圈内；填入圆圈内Page66of9vjuiB1B2B3B4产量产量A13113107A219284A3741059销量销量365643136355-24-304121-11012令令u1=5Page67of967vju
38、iB1B2B3B4产量产量A13113107A219284A3741059销量销量36564313631003-12-59121-11012令令u1=0时，所以任选时，所以任选u1对检验数没影响对检验数没影响Page68of9 当当非非基基变变量量的的检检验验数数出出现现负负值值时时，则则表表明明当当前前的的基基本本可可行行解解不不是是最最优优解解。在在这这种种情情况况下下，应应该该对对基基本本可可行行解解进进行行调调整整，即即找找到到一一个个新新的的基基本本可可行行解解使使目目标标函函数数值值下下降降，这这一一过过程程通通常常称称为为换换基基( (或主元变换或主元变换) )过程过程。三、求新
39、的基本可行解三、求新的基本可行解Page69of9 （1 1）选负检验数中最小者选负检验数中最小者 rk，那么，那么 xrk 为主元，作为进基变量（上页图中为主元，作为进基变量（上页图中 x24 ）; ; （2 2）以以 xrk 为起点找一条闭回路，除为起点找一条闭回路，除 xrk 外其余顶点必须为基变量格（上页图中外其余顶点必须为基变量格（上页图中的回路）的回路）; ; 在运输问题的表上作业法中，换基的过在运输问题的表上作业法中，换基的过程是如下进行：程是如下进行：Page70of9 （3 3）为闭回路的每一个顶点标号，为闭回路的每一个顶点标号， x xrkrk 为为 1 1，沿一个方向（顺
40、时针或逆时针）依，沿一个方向（顺时针或逆时针）依次给各顶点标号；次给各顶点标号； （4 4）求求 =Minxij xij对应闭回路上的对应闭回路上的偶数标号格偶数标号格=xpq 那么那么确定确定xpq为出基变量，为出基变量， 为调整量；为调整量；Page71of9 （5 5）对闭回路的各奇标号顶点调整对闭回路的各奇标号顶点调整为：为：xij+ ，对各偶标号顶点，对各偶标号顶点 调整为：调整为：xij- ，特别，特别 xpq- =0，xpq变为非基变为非基变量。变量。 重复重复(2)(2)、(3)(3)步，直到所有检验数步，直到所有检验数均非负，得到最优解均非负，得到最优解。Page72of9
41、销地产地B1B2B3B4产量A13 1111 223 4 410 3 37A21 3 39 112 1 18-1-14A37 10104 6 61012125 3 39销量365620(产销平衡)表表4-11 4-11 初始基本可行解及检验数初始基本可行解及检验数Page73of9选择选择，则调整为，则调整为Page74of93310009-2-5221912Page75of9 ij0，得到，得到最优解最优解 x13=5,x14=2,x21=3,x24=1, x32=6,x34=3,其余其余xij=0; ; 最优值最优值： f*=35+102+13+81+46+53=85注意：注意：非基变量的
42、检验数有一个为零，所以非基变量的检验数有一个为零，所以该运输问题有无穷多个最优解。该运输问题有无穷多个最优解。Page76of9Page77of9Page78of9033-210-592021912Page79of9 ij0，得到，得到最优解最优解 x11=2,x13=5,x21=1,x24=3, x32=6,x34=3,其余其余xij=0; ;最优值最优值： f*=32+35+11+83+46+53=85Page80of9作业作业：习题习题2,3(1)2,3(1)Page81of9 我们已经介绍过，可以通过增加虚设产我们已经介绍过，可以通过增加虚设产地或销地（加、减松弛变量）把问题转换成地或
43、销地（加、减松弛变量）把问题转换成产销平衡问题，下面分别来讨论。产销平衡问题，下面分别来讨论。 1.1.产量大于销量的情况产量大于销量的情况mn考虑考虑 si dj 的运输问题，得到的数学模的运输问题，得到的数学模i=1j=1型为型为 四、产销不平衡问题的处理四、产销不平衡问题的处理（如何转化为产销平衡）（如何转化为产销平衡）Page82of9m nMinf= cij xiji=1j=1ns.t. xijsii=1,2,mj=1 m xij=dj j=1,2,ni=1 xij0(i=1,2,m;j=1,2,n)Page83of9 只只要要在在模模型型中中的的产产量量限限制制约约束束（前前m m
44、个个不不等等式式约约束束）中中引引入入m m个个松松弛弛变变量量xin+1i=1,2,m 即可，变为：即可，变为： n xij+xin+1=sii=1,2,，mj=1然后，需设一个销地然后，需设一个销地B n+1, ,它的销量为：它的销量为：m ndn+1= si- dji=1j=1Page84of9 这这里里，松松弛弛变变量量 x i n+1可可以以视视为为从从产产地地 A i运运往往销销地地 Bn+1的的运运输输量量，由由于于实实际际并并不运送，它们的运费为不运送，它们的运费为 c i n+1=0i =1,2,m。于于是是，这这个个运运输输问问题就转化成了一个产销平衡的问题题就转化成了一个
45、产销平衡的问题。Page85of9销产B1B2BnBn+1产量A1x11x12x1nx1n+1s1A2x21x22x2nx2n+1s2 Amxm1xm2xmnxmn+1sm销量d1d2dndn+1平衡平衡假想销地假想销地Page86of9销产B1B2BnBn+1产量A1c11c12c1n0s1A2c21c22c2n0s2 Amcm1cm2cmn0sm销量d1d2dndn+1就地储存，不运输，所以运费为就地储存，不运输，所以运费为0Page87of9 例例4.3:4.3:某公司从两个产地某公司从两个产地A A1 1、A A2 2将将物品运往三个销地物品运往三个销地B B1 1、B B2 2、B
46、B3 3，各产地，各产地的产量、各销地的销量和各产地运往各的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？应如何调运可使总运输费用最小？Page88of9 解：解：首先判断产销是否平衡？首先判断产销是否平衡？显然产显然产销不平衡，销不平衡，产量产量 销量，销量，增加一个虚设的销增加一个虚设的销地运输费用地运输费用为为0 0平衡平衡Page89of9 2.销量大于产量的情况销量大于产量的情况m n考虑考虑 si dj的运输问题，得到的数学模型为的运输问题，得到的数学模型为i=1j=1 m nMinf = cij
47、xiji=1j=1n s.t. xij=sii=1,2,mj=1m xijdjj=1,2,ni=1xij0(i=1,2,m;j=1,2,n)Page90of9 只只要要在在模模型型中中的的产产量量限限制制约约束束（后后n个个不不等等式式约约束束）中中引引入入n个个松松弛弛变变量量xm+1j j =1,2,n即可，变为：即可，变为：m xij+xm+1j=djj=1,2,，mi=1然后，需设一个产地然后，需设一个产地A m+1,它的销量为：它的销量为：n m sm+1= dj- sij=1 i=1Page91of9 这这里里，松松弛弛变变量量x m+1j可可以以视视为为从从产产地地A m+1运运
48、往往销销地地Bj的的运运输输量量，由由于于实实际际并并不不运运送送，它它们们的的运运费费为为c m+1j=0j=1,2,n。于于是是，这这个个运运输输问问题题就就转转化化成成了一个产销平衡的问题。了一个产销平衡的问题。Page92of9销产B1B2Bn产量A1x11x12x1ns1A2x21x22x2ns2Amxm1xm2xmnsmAm+1xm+11xm+12xm+1nsm+1销量d1d2dn平衡平衡假想有一个产地，生产不足的产品假想有一个产地，生产不足的产品Page93of9销产B1B2Bn产量A1c11c12c1ns1A2c21c22c2ns2Amcm1cm2cmnsmAm+1000sm+
49、1销量d1d2dn平衡平衡由于实际并不生产、运输，所以运费为由于实际并不生产、运输，所以运费为0Page94of9 例例4.4:4.4:某公司从两个产地某公司从两个产地A A1 1、A A2 2将物品将物品运往三个销地运往三个销地B B1 1、B B2 2、B B3 3，各产地的产量、各，各产地的产量、各销地的销量和各产地运往各销地每件物品的销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运运费如下表所示，问：应如何调运可使总运输费用最小？输费用最小？Page95of9 解：解：首先判断产销是否平衡？首先判断产销是否平衡？显然产销显然产销不平衡，不平衡，产量产量 销量
50、，销量，增加一个虚设的产增加一个虚设的产地运输费用为地运输费用为0 0平衡平衡Page96of94.34.3运输问题的应用运输问题的应用例例4.6 4.6 有有A1A1，A2A2，A3A3三个产地，三个产地， B1B1， B2 B3B2 B3，B4B4，B5B5销地，其中销地，其中B2B2销地的销地的115115单位必须满单位必须满足，其他条件如下表：足，其他条件如下表：B1B1B2B2B3B3B4B4B5B5产量A1A1101520204050A2A22040153030100A3A33035405525130需求25115603070产销不平衡产销不平衡产量产量销量销量Page97of9解
51、：由于产量小于销量，因此设一虚设产地解：由于产量小于销量，因此设一虚设产地A4，产量为产量为（25+115+60+30+70）-（50+100+130）=20又因为其中又因为其中B2地区的地区的115单位必须满足，即不单位必须满足，即不能有物资从能有物资从A4运往运往B2地区，于是地区，于是取相应的费用为取相应的费用为M（M为一个充分大的正数），为一个充分大的正数），以保证在求最小运以保证在求最小运输费用的前提下，该变量的值为零。输费用的前提下，该变量的值为零。Page98of9B1B1B2B2B3B3B4B4B5B5产量A1A1101520204050A2A22040153030100A3A
52、33035405525130A4A40M00020需求25115603070平衡建立产销平衡的运输费用表为建立产销平衡的运输费用表为 例例4.7:4.7:石家庄北方研究院有一、二、三，三石家庄北方研究院有一、二、三，三个区。每年分别需要用煤个区。每年分别需要用煤30003000、10001000、2000t2000t，由河北临城、山西盂县两处煤矿负责供应，价格、由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供应能力分别为质量相同。供应能力分别为15001500、4000t4000t，运价，运价如下表。由于需大于供，经院研究决定一区供应如下表。由于需大于供，经院研究决定一区供应量可减少量
53、可减少0 0300t300t，二区必须满足需求量，三区，二区必须满足需求量，三区供应量不少于供应量不少于1700t1700t，试求总费用为最低的调运，试求总费用为最低的调运方案。方案。Page100of9 解解:根据题意，作出产销平衡与运价表：根据题意，作出产销平衡与运价表：取取M代表一个很大的正数，其作用是强迫相代表一个很大的正数，其作用是强迫相应的应的x31、x33、x34取值为取值为0。Page101of9 例例4.8:4.8:设有设有A A、B B、C C三个化肥厂供应三个化肥厂供应1 1、2 2、3 3、4 4四个地区的农用化肥。假设效果相同，有四个地区的农用化肥。假设效果相同，有关
54、数据如下表。试求总费用为关数据如下表。试求总费用为最低最低的化肥调拨的化肥调拨方案。方案。Page102of9 解：根据题意，作出产销平衡与运价表解：根据题意，作出产销平衡与运价表: :最最低要求必须满足，因此把相应的虚设产地运费取低要求必须满足，因此把相应的虚设产地运费取为为 M M ，而最高要求与最低要求的差允许按需要，而最高要求与最低要求的差允许按需要安排，因此把相应的虚设产地运费取为安排，因此把相应的虚设产地运费取为 0 0 。对。对应应 4 4”的销量的销量 50 50 是考虑问题本身适当取的数据，是考虑问题本身适当取的数据，根据产销平衡要求确定根据产销平衡要求确定 D D的产量为的
55、产量为 5050。例例4.9:4.9:某厂按合同规定须于当年每个季度末分别某厂按合同规定须于当年每个季度末分别提供提供1010、1515、2525、2020台同一规格的柴油机。已知台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本该厂各季度的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每如右表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用台每积压一个季度需储存、维护等费用0.150.15万元。万元。试求在完成合同的情况下，使该厂全年生产总费试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。用为最小的决策方案。 生产与
56、储存问题生产与储存问题交货：交货：生产：生产：x11 = 10 x11+x12+x13+x14 25x12+x22 = 15 x22+x23+x24 35x13+x23+x33 = 25 x33+x34 30x14+x24+x34+x44 = 20 x4410解：解： 设设 x xij ij 为第为第 i i 季度生产的第季度生产的第 j j 季度交季度交货的柴油机数目，那么应满足：货的柴油机数目，那么应满足： 把第把第 i i 季度生产的柴油机数目看作第季度生产的柴油机数目看作第 i i 个个生产厂的产量；把第生产厂的产量；把第 j j 季度交货的柴油机数目季度交货的柴油机数目看作第看作第
57、j j 个销售点的销量；成本加储存、维护个销售点的销量；成本加储存、维护等费用看作运费。等费用看作运费。可构造下列产销平衡问题：可构造下列产销平衡问题：目标函数：目标函数：Minf=10.8x11+10.95x12+11.1x13+11.25x14+11.1x22+11.25x23+11.4x24+11.0x33+11.15x34+11.3x44 Page106of9 转运问题转运问题: :原运输问题上增加若干转运站。原运输问题上增加若干转运站。运输方式有：产地运输方式有：产地 转运站、转运站转运站、转运站 销销地、产地地、产地 产地、产地产地、产地 销地、销地销地、销地 转转运站、销地运站、
58、销地 产地等产地等。Page107of9 例例4.7:4.7:腾飞电子仪器公司在大连和广州有两个腾飞电子仪器公司在大连和广州有两个分厂生产同一种仪器，大连分厂每月生产分厂生产同一种仪器，大连分厂每月生产450450台台, ,广广州分厂每月生产州分厂每月生产600600台。该公司在上海和天津有两台。该公司在上海和天津有两个销售公司负责对南京、济南、南昌、青岛四个城个销售公司负责对南京、济南、南昌、青岛四个城市的仪器供应。另外因为大连距离青岛较近，公司市的仪器供应。另外因为大连距离青岛较近，公司同意大连分厂向青岛直接供货，运输费用如下图，同意大连分厂向青岛直接供货，运输费用如下图，单位是百元。问应
59、该如何调运仪器，可使总运输费单位是百元。问应该如何调运仪器，可使总运输费用最低？用最低？Page108of9图中图中 1 1广州、广州、2 2大连、大连、3 3上海、上海、4 4天津天津 5 5南京、南京、6 6济南、济南、7 7南昌、南昌、8 8青岛青岛450Page109of9 解：设解：设 x xijij 为从为从 i i 到到 j j 的运输量，的运输量，可得到有下列特点的线性规划模型：可得到有下列特点的线性规划模型： 目标函数：目标函数：Min Min f f = = 所有可能的运输费所有可能的运输费用（运输单价与运输量乘积之和）用（运输单价与运输量乘积之和） 约束条件：对产地（发点
60、）约束条件：对产地（发点） i i ： 输出量输出量 - - 输入量输入量 = = 产量产量 对转运站（中转点）：对转运站（中转点）： 输入量输入量 - - 输出量输出量 = 0= 0 对销地（收点）对销地（收点） j j ： 输入量输入量 - - 输出量输出量 = = 销量销量Page110of9约束条件：约束条件：s.t.x13+x14600(广州分厂供应量限制）广州分厂供应量限制）x23+x24+x28450(大连分厂供应量限制）大连分厂供应量限制）-x13-x23+x35+x36+x37+x38=0（上海销售公司，转运站）（上海销售公司，转运站）目标函数：目标函数：Minf=2x13+
61、3x14+3x23+x24+4x28+2x35+6x36+3x37+6x38+4x45+4x46+6x47+5x48Page111of9-x14- x24 + x45 + x46+ x47 + x48 = 0 （天津销售公司，转运站）（天津销售公司，转运站）x35+ x45 = 200 （南京的销量）（南京的销量）x36+ x46 = 150 （济南的销量）（济南的销量）x37+ x47 = 350 （南昌的销量）（南昌的销量）x38+ x48 + x28 = 300 （南京的销量）（南京的销量）xij 0 , i,j = 1,2,3,4,5,6,7,8可求得结果：可求得结果：x13=550,x14=0x23=0,x24=150,x28=300x35=200,x36=0,x37=350,x38=0x45=0,x46=150,x47=0,x48=0Page112of9作业：作业： 习题习题
