运筹学3运输问题课件.ppt

《运筹学3运输问题课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、关于退化问题1、初始解退化即所求初始基变量的个数少于m+n1。必须补足基变量的个数，否则不能正常解出m+n个ui和vj（如填写一个数字同时满足了一厂一商，则需在同行或同列中填写一个数字0，以保证恰好有m+n-1个数字），基可行解中不能有某个基变量独占一行一列2、迭代过程中出现退化闭合回路中偶数次基变量同时有多个达到最小，变换后，有多个原基变量变为0，选运费最大者为退基变量，其余保留在新的基解中1供大于求供不应求增加虚拟销地增加虚拟产地产销平衡的运输问题对应的运距（或运价）？转化3.3运输问题的推广一、产销不平衡的运输问题2例2供大于求的运输问题运费

2、及产销量表B1B2B3产量A1A2A3A464583275651270405020销量3040301801003例2解：引入虚拟销地B4，（或理解为仓库），就地“销售”，运费为零B1B2B3B4产量A1A2A3A4645083207560512070405020销量304030801801804例2求初始方案：用最小元素法，但零视为最大元素。（？）B1B2B3B4产量A1A2A3A4645083207560512070405020销量30403080180180/2020/3010/1010/1060/3030/30/5056/304/1050/30

3、83/102/3007560/5051/2020102330-33例2检验所以，此方案为最优方案。其调运费用为：30×6+10×4+10×3+30×2+20×1=3306例题3：弹性需求问题（P96）设有三个化肥厂供应四个地区，资料如下：运价地区化肥厂甲乙丙丁产量ABC1614191313202219231715-506050最低需求最高需求3050707003010不限7例题3：解题思路：设法转化为标准型本题产量160万吨，最低需求110万吨，最高需求无限。实质上比较现实的最高需求为210万吨（根据现有产量）产量大于最低需求；小于最高需求。而标准型

4、是：产量=销量。处理办法：设想一个虚拟化肥厂D，其年产量50万吨，但这个产量只能供应可有可无的最高需求部分，于是各地的需求也应分为两个部分：基本需求、机动需求虚拟产量的运输费用为零，但它对于基本需求来讲，运费为无穷大。8例题3：建模1运价地区煤矿甲1甲2乙丙丁1丁2产量ABCD161419M1614190131320M22192301715MM1715M050605050需求量30207030105021021091运价地区煤矿甲1甲2乙丙丁1丁2产量ABCD161419M1614190131320M22192301715MM1715M0506050

5、50需求量3020703010502102103020203050201030202030200例题3：求解（Vogel法）10161419M1614190131320M22192301715MM1715M050605050302070301050/50/20/30/0/20/30/2077/307128678-88/10得最优调运方案：C供应甲50、A和B供应乙70、B供应丁40（万t），不供应丙。最低调运费用为：50×19+70×13+40×15=2460（万元）例题3：检验11特点:调运的物资不是由产地直接运送到销地，而是经过若干中转站送达。求

6、解思路：转化成一个等价的产销平衡运输问题，再用表上作业法求出最优调运方案。如何转化？二、转运问题12第一步，将产地、转运点、销地重新编排，转运点既作为产地又作为销地；第二步，各地之间的运距（或运价）在原问题运距（运价）表基础上进行扩展：从一地运往自身的单位运距（运价）记为零，不存在运输线路的则记为M（一个足够大的正数）；13第三步，由于经过转运点的物资量既是该点作为销地的需求量，又是该点作为产地时的供应量，但事先又无法获取该数量的确切值，因此通常将调运总量作为该数值的上界。对于产地和销地也作类似的处理。（参见P98例4）14三、运输模型的应用例题4：

7、某机床厂定下一年合同分别于各季度末交货。已知各季度生产成本不同，允许存货，存储费0.12万元/台季，三、四季度可以加班生产，加班生产能力8台/季，加班费用3万元/台季度正常生产能力单位成本（万元）交货台数12343032202810.5510.81111.12530154515例4分析：可用线性规划，但用运输问题更简单要决策的问题是各季度生产量和交货量设xij表示第i季度生产第j季度交货的台数因加班时间生产成本不同，故要区别开来，三四季度可加班，视同增加两个季度需求量合计115台，生产能力合计126台，供需不平衡，因此，增加一虚拟季度交货。16例4建

8、模：.成本交货生产虚拟1234季度产量1季度正常生产2季度正常生产3季度正常生产3季度加班生产4季度正常生产