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

退化问题的处理在确定初始基可行解的过程中，如果某一步中出现的情况：产地的拥有量与销地的销量同时为0只需划去其中的一行或一列；因此某一调运线路的调运量为0，即相应的基变量为0。称为退化问题。为了说明这一点，试确定下列的初始解。退化问题实例67128724153562341873214321销量产量AAABBBB给定运输问题的数据表试确定初始解3.3不平衡的运输问题所谓不平衡的运输问题是指总产量不等于总销量的运输问题。前面几节所讨论的运输问题都要求总产量等于总销量，因而也称为平衡的运输问题。在实际问题中，产销量往往是不平衡的，为了利用作业法求解，就往往需要把不平衡的运输问题化成平衡的运输问题。其基本思路是引入松弛变量，相当于增加一个虚拟的产地或销地。1.供过于求，总产量大于总销量，njjmiiba11由于总产量大于总销量，某些产地的产量调运不出去，即调运量小于其产量；由此可以建立供过于求的数学模型。0),,2,1(),,2,1(min1111ijmijijnjiijminjijijxnjbxmiaxxcz1B2BnB1A2AmA销量产量11c12cnc121c22cnc21mc2mcmnc1b2bnb1a2ama虚拟销地由于产品供大于求，应考虑把多余的物资就地贮存，即增加一个虚拟销地Bn+1njjmiinbab111在这个意义下化为平衡运输问题0)1(nic虚拟销地Bn+1的总销量为令xi(n+1)是从产地Ai到虚拟销地Bn+1的调运量，它相当于产地Ai的贮存量，不需花运费，因而运价为0：供大于求运输问题的模型minjijijxcz111min0)1,,2,1(),,2,1(111ijmijijnjiijxnjbxmiaxminjjinnibabc111)1(,0其中1B2BnB1A2AmA销量产量11c12cnc121c22cnc21mc2mcmnc1b2bnb1a2ama1nB0001nb供不应求的运输问题2.当供不应求时，总产量小于总销量，minjjiba11由于总产量小于总销量，某些销地的需求得不到满足，即调入量小于其销量；由此可以建立供不应求的数学模型。1B2BnB1A2AmA销量产量11c12cnc121c22cnc21mc2mcmnc1b2bnb1a2ama供不应求的运输问题的数学模型0),,2,1(),,2,1(min1111ijmijijnjiijminjijijxnjbxmiaxxcz1B2BnB1A2AmA销量产量11c12cnc121c22cnc21mc2mcmnc1b2bnb1a2ama虚拟产地由于供不应求，则应设想一个虚拟产Am+1，并让虚拟产地Am+1来供给销地Bj所需物资差额。Mcjm)1(miinjjmaba111其中Ｍ是一个充分大的正数。由于销地实际上不能从虚拟产地Am+1得到供应，故其运价是高额的，令虚拟产地Am+1的产量为供不应求运输问题模型0),,2,1()1,,2,1(min111111ijmijijnjiijminjijijxnjbxmiaxxczmiinjjmjmabaMc111)1(,其中1B2BnB1A2AmA销量产量11c12cnc121c22cnc21mc2mcmnc1b2bnb1a2ama1mAMMM1ma练习题1、销地产地B1B2B3B4A126456207A28.89.19.09.45A32028453572346销地产地B1B2B3B4B5A1264562007A28.89.19.09.405A3202845350723464销地产地B1B2B3B4B5A12327A2325A343723464销地产地B1B2B3B4B5A12327A2325A316723464练习题2、B1，B2，B3三个工厂所用热水由A1，A2供应，各厂的需求量、锅炉房的供应量及输送热水的单位费用见下表。由于供小于求，决定：保证B1的需求，B2的供应量最多可减少90，B3的供应量不能少于180，应如何按排给三个厂的供热水方案，在保证各厂基本需求的情况下，使输送总费用最低。销地产地B1B2B3供应量A1768280A2859270需求量100320260销地产地B1B2B’2B3B’3供应量A176688280A285599270A3MM0M0130需求量1002309018080销地产地B1B2B3供应量A1768280A2859270需求量100320260销地产地B1B2B’2B3B’3供应量A1100180280A2023040270A35080130需求量1002309018080销地产地B1B2B’2B3B’3供应量A176688280A285599270A3MM0M0130需求量1002309018080例1设有三个煤矿供应四个电厂的发电用煤。假定各个煤矿的年产量、各个电厂的备用煤量以及单位运价如表4-17所示。试求运费最省的煤炭调拔方案。表4-17电厂煤矿ⅠⅡⅢⅣ产量A1613221750B1413191560C192023-50最低需要量3070010最高需求量507030不限解题分析1这是一个产销不平衡的运输问题，总产量160个单位，四个电厂的年最低需求为110个单位。小于产量160。根据现有产量，第四个电厂每年最多能再多获得50个单位的供应量，因此，最高需求为210个单位，大于产量160。为了求得平衡，增加一个假想的煤矿D，其年产量为50个单位。电厂煤矿ⅠⅡⅢⅣ产量A1613221750B1413191560C192023-50最低需要量3070010最高需求量507030不限解题分析2由于各电厂的需求有两个部分，如电厂Ｉ，其最低需求30个单位不能由虚拟产地D供应，如要供应，其运价是一个任意大的正数M；而另一部分20个单位可以满足也可以不满足，因此可由虚拟产地D供应，其运价为0；其它电厂的需求量也可类似处理。从而可得到一个平衡的运输问题（单位运价表与产销平衡表）电厂煤矿ⅠⅡⅢⅣ产量A1613221750B1413191560C192023-50最低需要量3070010最高需求量507030不限5010307020305000050232019196015151913141450171722131616''''''销量产量ⅣⅣⅢⅡⅠⅠ产地销地MMMDMMCBA利用表上作业法可以求得上述问题的最优方案。电厂煤矿ⅠⅡⅢⅣ产量A1613221750B1413191560C192023-50最低需要量3070010最高需求量507030不限5010307020305020305002030603010205050''''''销量产量ⅣⅣⅢⅡⅠⅠ产地销地DCBA5010307020305000050232019196015151913141450171722131616''''''销量产量ⅣⅣⅢⅡⅠⅠ产地销地MMMDMMCBA例4饮料厂生产一种水果饮料，已知全年每季度的订货数量见下表，如果生产出的饮料本季度不交货，每保存一个季度，每罐饮料的存储费为0.1元，要求在完成定货供应的情况下，制订饮料厂全年生产总费用最低的生产方案。一季度二季度三季度四季度生产能力（万罐）50645620生产成本(元/罐)8.89.19.09.4订货数量（万罐）20284535解:由于每个季度生产出的饮料不一定当寄交货,设xij为第i季度生产第j季度交货的饮料数量,应满足订货要求:3545282044342414332313221211xxxxxxxxxx生产能力:2056644544343324232214131211xxxxxxxxxx第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一二三四虚拟交货生产量一2028250二224264三213556四2020销量20284535628.8总费用最低的生产方案:练习题3、对偶问题的经济意义01111ijmijijnjiijminjijijxbxaxxczminnjjmiiba1101111ijmijijnjiijminjijijxbxaxxczmininjijax1011jiijijnjmiiijjv,ucuvuavb'zmaxui为第i产地单位物资的价格。vj为第j销地单位物资的价格。如该公司欲自己将该种物资运至各地销售，其差价不能超过两地之间的运价（否则买主将在i地购买自己运至j地），在此条件下，希望获利为最大。运输悖论在运输问题中，有一种奇怪现象“多运了物资，运费反而下降”，这种称为“运输悖论”的现象是与不平衡运输问题有关的。考虑下面的运输问题（表4-19）请读者分析一下：在什么情况下才会出现“运输悖论”呢？表4-191181211415109184126541158181613229167141361514432154321AAAABBBBB这是一个产销平衡问题，利用表上作业法可得它的一个最优解，基变量取值为10,5,1,5,8,6,4,74542353324222113xxxxxxxx11812114151056151886477432154321AAAABBBBB对应的运费是444表4-191181211415109184126541158181613229167141361514432154321AAAABBBBB如果允许产地多运出一些物资，销地可以多运进物资。如给出下述方案：,15,11,8,6,4,12'42'35'24'22'21'13xxxxxx即产地A1、A3都多运出了5个单位物资，销地B2多运进了5个单位物资。这个方案对应总运费是409。1181211415109184126541158181613229167141361514432154321AAAABBBBB118125114151516115188645757432154321AAAABBBBB