《运筹学》第三章：运输问题培训课件

第三章运输问题

3.1供求平衡的运输规划问题3.2

供求不平衡运输问题的解法3.3运输问题的应用举例一、供求平衡运输问题供求平衡运输问题及其数学模型例3-1供求平衡运输问题数学模型表上作业法求初始基本可行解计算检验数及最优解检验调整求新解解的退化问题3.1供求平衡运输问题的数学模型例3-1设有三个电视机厂。生产同一种彩色电视机，日生产能力分别是：50，60，50，供应四个门市部，日销售量分别是：40，40，60，20台，从各分厂运往个门市部的运费如表1-23所示，试安排一个运费最低的运输计划。门市部工厂1234供应总计12397612359796711506050需求总计40406020

160供求平衡的运输问题：供：50+60+50=160需：40+40+60+20=160数学模型模型特点m+n个等式约束不是相互独立的，但是任意m+n-1个约束都是相互独立的；因为约束方程中，独立的方程的个数为m+n-1个，所以基本可行解中，基变量的个数为m+n-1个，非基变量的数量为系数矩阵的结构非常特殊，每列只有两个元素为1，其余均为0

表上作业法—运输问题的单纯形法求解步骤确定初始可行解求空格检验数，检验最优解调整（换基、求新解）可行解重复作上述2、3两步，直至求得最优解。确定初始可行解方法一：西北角法门市部工厂1234供应总计19129650273776036591150需求总计40406020确定初始可行解方法一：西北角法门市部工厂1234供应总计19129650401027377603030365911502030需求总计40406020初始基本可行解确定供应关系时，在运输表上每填上一个数字，就在表中划去一行或者一列，而运输表中共有m行n列，总共可以划n+m条线，但是当填上最后一个数字时，同时划去一行和一列，所以表中有数字的单元格的个数为m+n-1个，代表着m+n-1个基变量，这些基变量之间是线性无关的，因此构成了运输问题的基本可行解。用西北角法确定初始基本可行解，简单，但是离最优解较远，并不是一个好的寻找最优解的方法最小元素法，也称为最小费用法，其基本思想是“就近供应”，即从单位运价表中最小的运价开始确定供销关系，然后次小，一直到给出初始基本可行解为止。门市部工厂1234供应总计19129650302027377602040365911504010需求总计40406020确定初始可行解方法二：最小元素法门市部工厂1234供应总计19129650

401027377603030365911502030需求总计40406020计算检验数方法一：闭合回路法从空格出发，遇到数字格，折直角向前，直到回到出发点。

从每一空格出发，一定存在并可以找到唯一的闭回路门市部工厂1234供应总计19129650

401027377603030365911502030需求总计40406020计算检验数方法一：闭合回路法(+)(－)(－)(－)(+)(+)计算检验数（闭合回路法）对于空格（1，4）其它的空格门市部工厂1234供应总计19129650-7

-124010273776030-273036591150204030需求总计40406020计算检验数方法一：闭合回路法注意，检验数为零，不要忘记写了。非基变量的检验数为零?……计算检验数方法二：位势法

位势法门市部工厂1234

Ui191296U1401027377U23030365911U32030VjV1V2V3V4根据数字格（基变量所在的格）求U和V，然后对空格（非基变量所在的格）求检验数计算检验数方法二：位势法方程共有m+n-1个方程，但有m+n个变量，一般令。因此可求得这些变量。我们称分别为产地位势和销地位势。本例：解得：因而可计算得计算检验数方法二：位势法只对数字格（基变量所在的格）求U和V，对空格求检验数,检验数＝空格对应的运价－对应的U与V之和门市部工厂1234供应总计19129650-7

-124010273776030-273036591150204030需求总计40406020调整基本解（换基迭代）－－闭合回路法取负检验数中绝对值最大的空格作回路(入基变量)。从空格开始依次给回路顶点格标“+”和“－”找出“－”格中运量最小者（出基变量），作为调整量，将每个“+”格的运量加上该调整量，每个“－”格的运量减去该调整量。即得新的基本可行解。再计算空格检验数和调整基本解，直到检验数非负为止。门市部工厂1234供应总计19129650-7

-124010273776030-273036591150204030需求总计40406020(－)(－)(+)(+)例3-1西北角法初始解的调整(－)调整的结果门市部工厂1234供应总计19129650

104027377602040365911501040需求总计40406020继续求检验数(闭合回路法或位势法)门市部工厂1234191296U1

104027377U220★40365911U31040V1V2V3V4门市部工厂1234供应总计19129650（5）

1040（12）273776020（-2）(-5)403659115010（-8）（0）40需求总计40406020继续求检验数门市部工厂1234供应总计19129650（5）

1040（12）273776020（-2）(-5)403659115010（-8）（0）40需求总计40406020调整门市部工厂1234供应总计19129650★203027377602040365911501040需求总计40406020调整后最优解（运费=980）门市部工厂1234供应总计1912965030

20

（3）（7）273776020（3）（3）4036591150（5）40（0）10需求总计40406020最优解无穷多和解的退化问题因为，因此最优解有无穷多个。如何求其它最优解？出现零的数字格，即为解的退化问题在求初始解时，若供求余量相等，则引进一个零数字格；在调整时，若有两个及以上相同最小运量的“－”格，调整后，将出现零数字格。如何添零数字格？（分两种情况考虑）1.确定初始解时的退化问题12345s1769355

282357635410695d23524初始解时的退化问题12345s17693552

3

2823576

05135410695

14d23524这个0，不能少，否则基本可行解的数量不足m+n-1个2.调整引起的退化问题12s1873026920d20302.调整引起的退化问题12s18730

20

1026920

(-4)

20d203012s18730

(4)

3026920

20

0d2030二、供求不平衡运输问题的解法供大于求的情况求大于供的情况都应化为供求平衡问题后再求解供大于求的情况数学模型M个供应单元N个需求单元特点与处理办法特点处理办法：设置一个虚销售点n+1，使且，因而化为平衡问题。结果求大于供数学模型M个供应单元N个需求单元特点与处理办法特点处理办法：增加一个虚产地m+1，使且，化为平衡问题。结果供求不平衡运输问题的例子B1B2B3B4供A110461012

A21034118求5485供求不平衡，供＜求，虚设一个供应地A3，令其提供虚的产量22－20＝2供求不平衡运输问题的例子B1B2B3B4供A110461012

A21034118A300002求5485由于从虚的供应地进行调运是无意义的，因此在使用最小元素法确定初始方案时，不考虑A3行供求不平衡运输问题的例子B1B2B3B4供UiA110461012u1345A21034118u244A300002u32求5485Vjv1v2v3v4供求不平衡运输问题的例子B1B2B3B4供UiA110461012U1=03-145A21034118U2=-22443A300002U3=-102540求5485VjV1=10V2=5V3=6V4=10(－)(－)(+)(+)供求不平衡运输问题的例子B1B2B3B4供UiA110461012U1=0341

5A21034118U2=-11082A300002U3=-102650求5485VjV1=10V2=4V3=5V4=10三、运输问题的应用举例例供求不平衡问题按最低需求量计算是供大于求，首先增加一个销地—将销地4增加一个分部按最高需求量计算是可能求大于供，增加一产地4。例3-2物资调度问题三个化肥厂，供应给四个地区，运价如表1-36所示，但第三化肥厂不能向第四个地区运送，求总运费最少的调运方案。1234s1231614191313202219231715M506050dmin3070010dmax507030不限化不平衡为平衡问题对第四需求点的最大供应量：160-100=60吨按最大需求计算，需求为：150+60=210吨因此设置虚的第四供应点，供应量：50吨1234s1231614191614191313202219231715M1715M5060504M0M0M050d302070301050初始可行解和检验数1234s116161322171750（2）（2）50(4)(-M)0214141319151560301020(-1)(-M)319192023MM5010（2）30104M0M0M050(M)(3)(M)(-1)50d302070301050第一次调整1234s116161322171750（2）（2）50(4)021