3.3 产销不平衡.ppt

第三章　运输问题 运筹帷幄，决胜千里 ?史记《张良传》 当产大于销时： 只要增加一个假想的销地j=n+1(实际上是贮存)，该销地总需要量为 在单位运价表中从各产地到假想销地的单位运价为0；就转化成一个产销平衡的运输问题。 解：增加一个虚设的销地运输费用为0 例3.4:某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？ 解：增加一个虚设的产地运输费用为0 解：这是一个产销不平衡的运输问题，总产量是160万吨，四个地区的最低需求为110万吨，最高需求为无限。根据现有产量，第四个地区每年最多能分配到60万吨，这样最高需求为210万吨，大于产量。为了求得平衡，在产销平衡表中增加一个假想的化肥厂D，其年产量为50万吨。 由于各地区的需求量包含两部分，如地区1，其中最低是30，故不能由假想D共给，令相应运价为M,而另一部分20万吨满足不满足都可以，所以可以由假想D供给。 根据表上作业法计算，可以求得这个问题的最优方案是： * 在实际中遇到的运输问题常常不是产销平衡的，而是下列的一般运输问题模型 m n Min f = ? ? cij xij （3-1） i=1 j=1 n s.t.? xij ?ai i = 1,2,…,m （3-2） j=1 m ?xij ?(=,?)bj j = 1,2,…,n (3-3） i=1 xij ?0 (i=1,2,…,m;j=1,2,…,n)（3-4） §3.3 产销不平衡问题的处理 对此，可以通过增加虚设产地或销地（加、减松弛变量）把问题转换成产销平衡问题，下面分别来讨论。? 1.产量大于销量的情况 m n 考虑 ?ai ?bj 的运输问题，得到的数学模 i=1 j=1 型为 m n Min f = ? ? cij xij i=1 j=1 n s.t. ? xij ?ai i = 1,2,…,m j=1 m ?xij =bj j = 1,2,…,n i=1 xij≥0(i=1,2,…,m;j=1,2,…,n) ? 只要在模型中的产量限制约束（前m个不等式约束）中引入m个松弛变量xin+1 i= 1,2,…,m 即可，变为： n ?xij+xin+1=ai i=1,2,…m j=1 然后，需设一个销地b n+1,它的销量为： m n bn+1= ?ai- ?bj i=1 j=1? ? 这里，松弛变量 x i n+1 可以视为从产地 A i 运往销地 B n+1 的运输量，由于实际并不运送，它们的运费为 c i n+1 = 0 i = 1,2,…,m。于是，这个运输问题就转化成了一个产销平衡的问题。 例3.3:某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？ 2.销量大于产量的情况 m n 考虑?ai?dj的运输问题，得到的数学模型为 i=1 j=1 m n Min f = ? ? cij xij i=1 j=1 n s.t.? xij =ai i = 1,2,…,m j=1 m ?xij ? bj j = 1,2,…,n i=1 xij≥0(i=1,2,…,m;j=1,2,…,n) ? 只要在模型中的产量限制约束（后n个不等式约束）中引入n个松弛变量xm+1j j = 1,2,…,n即可，变为： m ?xij+xm+1j=bj j=1,2,…n i=1 然后，需设一个产地A m+1,它的销量为： n m am+1= ?bj- ?ai