运输问题应用举例.ppt

《运输问题应用举例.ppt》由会员分享，可在线阅读，更多相关《运输问题应用举例.ppt（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运输问题应用举例主要内容：不平衡运输问题 弹性需求问题 运输模型举例2021/9/241产销不平衡问题产销不平衡是最常见的现象，此类问题可以转化为产销平衡的模型，而后求解。运输问题产销平衡模型，实质上就是一个求解运输问题的标准型。解决的办法是：增加一个虚拟的产地或销地，从而变成标准型产销平衡问题。2021/9/242例题1 供大于求运输问题B B1 1 B B2 2 B B3 3产量产量 A A1 1 A A2 2 A A3 3 A A4 46 4 58 3 27 5 65 1 2707040 40 50502020销量销量30 40 3030 40 30 180180 100100运费及产销

2、量表2021/9/243 例1 解：引入虚拟销地B4，（或理解为仓库），就地“销售”，运费为零 B1 B2 B3 B4产量 A1 A2 A3 A4 6 4 5 0 8 3 2 0 7 5 6 0 5 1 2 07040 5020 销量 30 40 30 80 180 1802021/9/244.B1 B2 B3 B4产量A1A2A3A4 30 10 30 10 30 50 207040 5020 销量 30 40 30 80 180 180例1 求初始方案：用最小元素法，但零视为最大元素。（？）2021/9/245 例1 检验初始方案计算位势ui+vjB1 B2 B3 B4uiA1A2A3A4

3、 6 4 (3)0 (5)3 2 (-1)(6)(4)(3)0 (3)1 (0)(-3)3230vj 3 1 0 -32021/9/246 例1 计算检验数ij=(ui+vj)-cij,所有ij 0，已得最优解。B1 B2 B3 B4uiA1A2A3A4 (-2)(-3)（-1）(-1)(-1)(-3)（-2)(-2)(-3)vj 2021/9/247例题2：弹性需求问题设有三煤矿供应四地区，资料如下：运价 地区煤矿甲乙丙丁产量ABC161419131320221923171525505060605050最低需求最高需求30305050707070700 030301010不限不限2021/9

4、/248 例题2：解题思路：设法转化为标准型本题产量160万吨，最低需求110万吨，最高需求无限。实质上比较现实的最高需求210万吨产量大于最小需求；小于最大需求。而标准型是：产量=销量。处理办法：设想一个虚拟煤矿D，生产50万吨，但这个产量只能供应可有可无的最高需求部分，于是各地的需求也应分为两个部分：基本需求、机动需求虚拟产量的运输费用为零，但它对于基本需求来讲，运费为无穷大。2021/9/249例题2：建模1运价 地区煤矿甲甲1 1甲甲2 2乙乙丙丙丁丁1 1丁丁2 2产量产量A AB BC CD D161419M1614190131320M2219230171225M1712250 5

5、0 60 50 50需求量需求量302070301050 2102102021/9/2410例题2：最优解1甲甲1 1甲甲2 2乙乙丙丙丁丁1 1丁丁2 2产量产量A AB BC CD D30205020030103020 50 60 50 50需求量需求量302070301050 2102102021/9/2411运输模型的应用例题3：某机床厂定下一年合同分别于各季度末交货。已知各季度生产成本不同，允许存货，存储费0.12万元/台季，三、四季度可以加班生产，加班生产能力8台/季，加班费用3万元/台。季度季度正常生产能力正常生产能力单位成本（万元）单位成本（万元）交货台数交货台数1 12 23

6、 34 4303032322020282810.5510.5510.810.8111111.111.125253030151545452021/9/2412例3 分析：可用线性规划，但用运输问题更简单要决策的问题是各季度生产量和交货量设xij表示第i季度生产第j季度交货的台数因加班时间生产成本不同，故要区别开来，三四季度可加班，视同增加两个季度需求量合计115台，生产能力合计126台，供需不平衡，因此，增加一项闲置能力。2021/9/2413 例3 建模：.成本成本 交货交货生产生产 闲置闲置 1 2 3 4 能力能力产量产量1季度正常生产2季度正常生产3季度正常生产3季度加班生产4季度正常生

7、产4季度加班生产10.55 10.67 10.79 10.91 0 M 10.8 10.92 11.04 0 M M 11 11.12 0 M M 14 14.12 0 M M M 11.1 0 M M M 14.1 03032208 288需求量 25 30 15 45 11 1261262021/9/2414 例3 结果：.闲置 1 2 3 4 能力产量1季度正常生产2季度正常生产3季度正常生产3季度加班生产4季度正常生产4季度加班生产 25 5 30 2 10 10 8 28 5 3 30 32 20 8 28 8需求量 25 30 15 45 11 2021/9/2415例题4 航运调

8、度问题某航运公司承担六个城市A、B、C、D、E、F之间的四条航线，已知各航线的起点、终点及每天所需的航班数如下表。又知各城市之间的航行天数，假定船只型号相同，装卸货时间各一天，问该公司至少要配备多少条船才能满足需要？航线航线起点起点终点终点每天航班数每天航班数1234EBADDCFB32112021/9/2416 例4 城市之间航行天数表C CijijA AB BC CD DE EF FA A 0 1 214 7 7B B 1 0 313 8 8C C 2 3 015 5 5D D141315 01720E E 7 8 517 0 3F F 7 8 520 3 02021/9/2417例4 问

9、题分析 问题要求的是在保证需要的前提下，至少需要多少船只。所需船只包括两个部分：载货船、空驶船。航线航行天数装卸天数合计航班数载货船数12341737132222195915321157109152021/9/2418例4 问题分析（续1）上表显示：载货船共需91条，此船何来？港口港口到达到达开出开出余缺余缺ABCDEF012301120130-1-1 2 2-3 1ABCDEF121 3调度中心 若无空驶，则91条船刚好够用，但虚线箭头都是空驶。2021/9/2419例4 问题分析（续2）所需91条货船要经调度而来，有的可在一个港口卸货后装运（如一条船从E到D后再起程赴B）。若港口没有空船，

10、则要从其它港口调度而来。（规模效益）由上表可知：C、D、F港口有多余船只可供调出，而A、B、E港口则需要调入空船。问题的核心是：如何使空驶船的数量为最少？亦即如何按照最近原则调度船只。2021/9/2420例4 问题分析（续3）为此建立运输问题数学模型。设xij表示每天从i港口调往j港口的空船数，则cijxij就表示 i j航线上周转的船只数，cijxij表示各条线上周转的船只总数。A AB BE E每天多余船只每天多余船只CDF 2 14 7 3 13 8 5 17 3221每天缺少船只 1 1 32021/9/2421例4 解题结果上机求解：ABE每天多余船只CDF1 1111221每天缺

11、少船只113空船总需求量2+5+13+17+3=40条空驶船40条+载重船91条=131条2021/9/2422例题5 增产调度问题工厂 市场A、B、C 1、2、3、4 1000 1500 1750 900 1000 1900 1500 产量 4250 需求 5300增产方案：加班生产，能力增长50%，费用增长50%新建D厂，产能2000，投资200万元新建E厂，产能2000，投资300万元新建F厂，产能2000，投资400万元如何增加生产能力？2021/9/2423例题5 问题分析各工厂位于不同城市，原材料、劳动力、以及运输费各不相同（为什么只考虑可变费用？），计算不同方案对应不同市场的费用

12、，将生产费用和运费统一考虑，从而决定产销方案。将四个方案，在可变成本的意义上，分别求其最优产销分配计划，比较优劣。再加入固定投资因素，进行综合比较。2021/9/2424图与网络的应用案例o排座问题o哈密顿（Hamilton）回路o考试日程问题2021/9/2425 有7个人围桌而坐，如果要求每次相邻的人都与以前完全不同，试问不同的就座方案共有多少种？用顶点表示人，用边表示两者相邻，因为最初任何两个人都允许相邻，所以任何两点都可以有边相连。例1：排座问题2021/9/242612376452021/9/24271237645 假定第一次就座方案是（1，2，3，4，5，6，7，1），那么第二次就

13、座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边。2021/9/242812376452021/9/24291237645 假定第二次就座方案是（1，3，5，7，2，4，6，1），那么第三次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边。2021/9/243012376452021/9/24311237645 假定第三次就座方案是（1，4，7，3，6，2，5，1），那么第四次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边，只留下7点孤立点，所以该问题只有三个就座方案。2021/9/243212376452021/9/2433 哈密顿（Hamilton）回路是十九

14、世纪英国数学家哈密顿提出，给出一个正12面体图形，共有20个顶点表示20个城市，要求从某个城市出发沿着棱线寻找一条经过每个城市一次而且仅一次，最后回到原处的周游世界线路（并不要求经过每条边）。例2：哈密顿（Hamilton）回路2021/9/2434例2：分析（1）2021/9/2435例2：分析（2）2021/9/2436例2：分析（3）2021/9/2437例2：分析（4）2021/9/2438例2：分析（5）2021/9/2439例2：分析（6）2021/9/2440例2：分析（7）2021/9/2441例2：分析（8）2021/9/2442例2：分析（9）2021/9/2443例2：分

15、析（10）2021/9/2444例2：分析（11）2021/9/2445最优路线2021/9/2446 一个班级的学生共计选修A、B、C、D、E、F六门课程，其中一部分人同时选修D、C、A，一部分人同时选修B、C、F，一部分人同时选修B、E，还有一部分人同时选修A、B，期终考试要求每天考一门课，六天内考完，为了减轻学生负担，要求每人都不会连续参加考试，试设计一个考试日程表。例3：考试日程问题2021/9/2447 解：以每门课程为一个顶点，共同被选修的课程之间用边相连，得图，按题意，相邻顶点对应课程不能连续考试，不相邻顶点对应课程允许连续考试，因此，作图的补图，问题是在图中寻找一条哈密顿道路，如CEAFDBCEAFDB，就是一个符合要求的考试课程表。例3：实例分析2021/9/2448AFEDCB2021/9/2449AFEDCB2021/9/2450AFEDCB2021/9/2451AFEDCB例3：分析（1）AFEDCB（1）（2）2021/9/2452AFEDCB例3：分析（2）AFEDCB（3）（4）2021/9/2453例3：分析（3）AFEDCB（5）2021/9/2454