运筹学之4.2不平衡运输问题

1、退化问题的处理退化问题的处理v在确定初始基可行解的过程中，如果某一步中出现的在确定初始基可行解的过程中，如果某一步中出现的情况：情况：v产地的拥有量与销地的销量同时为产地的拥有量与销地的销量同时为0 0v只需划去其中的一行或一列只需划去其中的一行或一列；v因此某一调运线路的调运量为因此某一调运线路的调运量为0，v即相应的基变量为即相应的基变量为0 。v称为退化问题。称为退化问题。v为了说明这一点，试确定下列的初始解。为了说明这一点，试确定下列的初始解。退化问题实例退化问题实例67128724153562341873214321销量产量AAABBBB给定运输问题的数据表给定运输问题的数据表试确定

2、初始解试确定初始解3.3不平衡的运输问题不平衡的运输问题v所谓不平衡的运输问题是指总产量不等于总销量的运所谓不平衡的运输问题是指总产量不等于总销量的运 输问题。输问题。v前面几节所讨论的运输问题都要求总产量等于总销量，前面几节所讨论的运输问题都要求总产量等于总销量，因而也称为平衡的运输问题。因而也称为平衡的运输问题。v在实际问题中，产销量往往是不平衡的，为了利用作在实际问题中，产销量往往是不平衡的，为了利用作业法求解，就往往需要把不平衡的运输问题化成平衡业法求解，就往往需要把不平衡的运输问题化成平衡的运输问题。的运输问题。v其基本思路是引入松弛变量，相当于增加一个虚拟的其基本思路是引入松弛变量

3、，相当于增加一个虚拟的产地或销地。产地或销地。v1.供过于求，总产量大于总销量，供过于求，总产量大于总销量，njjmiiba11由于总产量大于总销量，某些产地的产量调运不出去，即调由于总产量大于总销量，某些产地的产量调运不出去，即调运量小于其产量；由此可以建立供过于求的数学模型。运量小于其产量；由此可以建立供过于求的数学模型。0), 2 , 1(), 2 , 1(min1111ijmijijnjiijminjijijxnjbxmiaxxcz1B2BnB1A2AmA销量产量11c12cnc121c22cnc21mc2mcmnc1b2bnb1a2ama虚拟销虚拟销地地 由于产品供大于求，应考虑把多

4、余的物资就由于产品供大于求，应考虑把多余的物资就地贮存，即增加一个虚拟销地地贮存，即增加一个虚拟销地B n+1njjmiinbab111|在这个意义下化为平衡运输问题在这个意义下化为平衡运输问题0)1(nic虚拟销地虚拟销地B n+1的总销量为的总销量为 令令x i (n+1)是从产地是从产地Ai到虚拟销地到虚拟销地B n+1的调运量，的调运量，它相当于产地它相当于产地Ai的贮存量，不需花运费，因而运价为的贮存量，不需花运费，因而运价为0：供大于供大于求运输求运输问题的问题的模型模型 minjijijxcz111min0) 1, 2 , 1(), 2 , 1(111ijmijijnjiijxn

5、jbxmiaxminjjinnibabc111)1(, 0其中1B2BnB1A2AmA销量产量11c12cnc121c22cnc21mc2mcmnc1b2bnb1a2ama1nB0001nb供不应供不应求的运求的运输问题输问题2.当供不应求时，总产量小于总销量，当供不应求时，总产量小于总销量，minjjiba11 由于总产量小于总销量，某些销地的需求得不到由于总产量小于总销量，某些销地的需求得不到满足，即调入量小于其销量；由此可以建立供不应满足，即调入量小于其销量；由此可以建立供不应求的数学模型。求的数学模型。1B2BnB1A2AmA销量产量11c12cnc121c22cnc21mc2mcmn

6、c1b2bnb1a2ama供不应求的运输供不应求的运输问题的数学模型问题的数学模型0), 2 , 1(), 2 , 1(min1111ijmijijnjiijminjijijxnjbxmiaxxcz1B2BnB1A2AmA销量产量11c12cnc121c22cnc21mc2mcmnc1b2bnb1a2ama虚拟产地虚拟产地由于供不应求，则应设想一个虚拟产由于供不应求，则应设想一个虚拟产Am+1，并让虚拟产地并让虚拟产地A m+1来供给销地来供给销地Bj所需物资差额。所需物资差额。Mcjm )1(miinjjmaba111其中是一个充分大的正数。其中是一个充分大的正数。 由于销地实际上不能从虚拟

7、产地由于销地实际上不能从虚拟产地A m+1得到得到供应，故其运价是高额的，令供应，故其运价是高额的，令|虚拟产地虚拟产地A m+1的产量为的产量为供不应求供不应求运输问题运输问题模型模型0), 2 , 1() 1, 2 , 1(min111111ijmijijnjiijminjijijxnjbxmiaxxczmiinjjmjmabaMc111)1(,其中1B2BnB1A2AmA销量产量11c12cnc121c22cnc21mc2mcmnc1b2bnb1a2ama1mAMMM1ma练习题练习题1、 销地产地B1B2B3B4A126456207A28.89.19.09.45A32028453572

8、346 销地产地B1B2B3B4B5A1264562007A28.89.19.09.405A3202845350723464 销地产地B1B2B3B4B5A12327A2325A343723464 销地产地B1B2B3B4B5A12327A2325A316723464练习题练习题2、B1，B2，B3三个工厂所用热水由三个工厂所用热水由A1，A2供应，各厂的供应，各厂的需求量、锅炉房的供应量及输送热水的单位费用见下需求量、锅炉房的供应量及输送热水的单位费用见下表。由于供小于求，决定：保证表。由于供小于求，决定：保证B1的需求，的需求，B2的供应的供应量最多可减少量最多可减少90，B3的供应量不能

9、少于的供应量不能少于180，应如何按，应如何按排给三个厂的供热水方案，在保证各厂基本需求的情排给三个厂的供热水方案，在保证各厂基本需求的情况下，使输送总费用最低。况下，使输送总费用最低。 销地产地B1B2B3供应量供应量A1768280A2859270需求量需求量100320260 销地产地B1B2B2B3B3供应量供应量A176688280A285599270A3MM0M0130需求量需求量1002309018080 销地产地B1B2B3供应量供应量A1768280A2859270需求量需求量100320260 销地产地B1B2B2B3B3供应量供应量A1100180280A20230402

10、70A35080130需求量需求量1002309018080 销地产地B1B2B2B3B3供应量供应量A176688280A285599270A3MM0M0130需求量需求量1002309018080例例1v设有三个煤矿供应四个电厂的发电用煤。假定各个设有三个煤矿供应四个电厂的发电用煤。假定各个煤矿的年产量、各个电厂的备用煤量以及单位运价煤矿的年产量、各个电厂的备用煤量以及单位运价如表如表4-17所示。试求运费最省的煤炭调拔方案。所示。试求运费最省的煤炭调拔方案。表表4-17 电厂电厂煤矿煤矿产量产量A1613221750B1413191560C192023-50最低需要量最低需要量30700

11、10最高需求量最高需求量507030不限不限解题分析解题分析1v这是一个产销不平衡的运输问题，总产量这是一个产销不平衡的运输问题，总产量160个单位，个单位，v四个电厂的年最低需求为四个电厂的年最低需求为110个单位。小于产量个单位。小于产量160。v根据现有产量，第四个电厂每年最多能再多获得根据现有产量，第四个电厂每年最多能再多获得50个单位的供个单位的供应量，因此，最高需求为应量，因此，最高需求为210个单位，大于产量个单位，大于产量160。v为了求得平衡，增加一个假想的煤矿为了求得平衡，增加一个假想的煤矿D，其年产量为，其年产量为50个单位。个单位。 电厂电厂煤矿煤矿产量产量A16132

12、21750B1413191560C192023-50最低需要量最低需要量3070010最高需求量最高需求量507030不限不限解题分析解题分析2v由于各电厂的需求有两个部分，由于各电厂的需求有两个部分，v如电厂，其最低需求如电厂，其最低需求30个单位不能由虚拟产地个单位不能由虚拟产地D供应，如要供应，如要供应，其运价是一个任意大的正数供应，其运价是一个任意大的正数M；v而另一部分而另一部分20个单位个单位可以满足也可以不满足可以满足也可以不满足，因此可由虚拟产，因此可由虚拟产地地D供应，其运价为供应，其运价为0；v其它电厂的需求量也可类似处理。其它电厂的需求量也可类似处理。v从而可得到一个平衡

13、的运输问题（单位运价表与产销平衡表从而可得到一个平衡的运输问题（单位运价表与产销平衡表） 电厂电厂煤矿煤矿产量产量A1613221750B1413191560C192023-50最低需要量最低需要量3070010最高需求量最高需求量507030不限不限5010307020305000050232019196015151913141450171722131616 销量产量产地销地MMMDMMCBA|利用表上作业法可以求得上述问题的最优方案。利用表上作业法可以求得上述问题的最优方案。 电厂电厂煤矿煤矿产量产量A1613221750B1413191560C192023-50最低需要量最低需要量307

14、0010最高需求量最高需求量507030不限不限5010307020305020305002030603010205050 销量产量产地销地DCBA5010307020305000050232019196015151913141450171722131616 销量产量产地销地MMMDMMCBA例例4饮料厂生产一种水果饮料，已知全年每季度的订货数量见下表，饮料厂生产一种水果饮料，已知全年每季度的订货数量见下表，如果生产出的饮料本季度不交货，每保存一个季度，每罐饮料的如果生产出的饮料本季度不交货，每保存一个季度，每罐饮料的存储费为存储费为0.1元，要求在完成定货供应的情况下，制订饮料厂全元，要求在

15、完成定货供应的情况下，制订饮料厂全年生产总费用最低的生产方案。年生产总费用最低的生产方案。一季度一季度二季度二季度三季度三季度四季度四季度生产能力（万罐）生产能力（万罐）50645620生产成本生产成本(元元/罐罐)8.89.19.09.4订货数量（万罐）订货数量（万罐）20284535解解:由于每个季度生产出的饮料不一定当寄交货由于每个季度生产出的饮料不一定当寄交货,设设xij为第为第i季度生产第季度生产第j季度交货的饮料数量季度交货的饮料数量,应满足订货要求应满足订货要求:3545282044342414332313221211xxxxxxxxxx生产能力生产能力:205664454434

16、3324232214131211xxxxxxxxxx第第i季度生产第季度生产第j季度交货的饮料的实际成本季度交货的饮料的实际成本cij=生生产成本产成本+存储费存储费, 当当ij时时, 取取cij=M.一一二二三三四虚拟交货虚拟交货生产量生产量一一8.88.99.09.1050二二M9.19.29.3064三三MM9.09.1056四四MMM9.4020销量销量20284535628.8一季度一季度二季度二季度三季度三季度四季度四季度生产能力（万罐）生产能力（万罐）50645620生产成本生产成本(元元/罐罐)8.89.19.09.4订货数量（万罐）订货数量（万罐）20284535一一二二三三

17、四虚拟交货虚拟交货生产量生产量一一2028250二二224264三三213556四四2020销量销量20284535628.8总费用最低的生产方案总费用最低的生产方案:练习题练习题3、 对偶问题的经济意义对偶问题的经济意义 01111ijmijijnjiijminjijijxbxaxxczminnjjmiiba11 01111ijmijijnjiijminjijijxbxaxxczmininjijax1011jiijijnjmiiijjv ,ucuvuavb zmaxui为第为第i产地单位物资的价格。产地单位物资的价格。vj为第为第j销地单位物资的价格。销地单位物资的价格。如该公司欲自己将该种

18、物资运至各地销如该公司欲自己将该种物资运至各地销售，其差价不能超过两地之间的运价售，其差价不能超过两地之间的运价（否则买主将在（否则买主将在i地购买自己运至地购买自己运至j地），地），在此条件下，希望获利为最大。在此条件下，希望获利为最大。运输悖论运输悖论v在运输问题中，有一种奇怪现象v“多运了物资，运费反而下降”，v这种称为“运输悖论”的现象是与不平衡运输问题有关的。v考虑下面的运输问题（表4-19）v请读者分析一下：v在什么情况下才会出现“运输悖论”呢？v表表4-191181211415109184126541158181613229167141361514432154321AAAABBBBBn这是一个产销平衡问题，利用表上作业法可得它的一个最优解，基变量取值为10, 5, 1, 5, 8, 6, 4, 74542353324222113xxxxxxxx11812114151056151886477432154321AAAABBBBB对应的运费是444n表表4-19118