运输问题应用举例

OR1运输问题应用举例主要内容：不平衡运输问题弹性需求问题运输模型举例OR1产销不平衡问题产销不平衡是最常见的现象，此类问题可以转化为产销平衡的模型，而后求解。运输问题产销平衡模型，实质上就是一个求解运输问题的标准型。解决的办法是：增加一个虚拟的产地或销地，从而变成标准型——产销平衡问题。OR1例题1供大于求运输问题B1B2B3产量A1A2A3A464583275651270405020销量304030180100运费及产销量表OR1例1解：引入虚拟销地B4，（或理解为仓库），就地“销售”，运费为零B1B2B3B4产量A1A2A3A4645083207560512070405020销量30403080180180OR1.B1B2B3B4产量A1A2A3A43010301030502070405020销量30403080180180例1求初始方案：用最小元素法，但零视为最大元素。（？）OR1例1检验初始方案计算位势ui+vjB1B2B3B4uiA1A2A3A464(3)0(5)32(-1)(6)(4)(3)0(3)1(0)(-3)3230vj310-3OR1例1计算检验数σij=(ui+vj)-cij,所有σij≤0，已得最优解。B1B2B3B4uiA1A2A3A4(-2)(-3)（-1）(-1)(-1)(-3)（-2)(-2)(-3)vjOR1例题2：弹性需求问题设有三煤矿供应四地区，资料如下：运价地区煤矿甲乙丙丁产量ABC161419131320221923171525506050最低需求最高需求3050707003010不限OR1例题2：解题思路：设法转化为标准型本题产量160万吨，最低需求110万吨，最高需求无限。实质上比较现实的最高需求210万吨产量大于最小需求；小于最大需求。而标准型是：产量=销量。处理办法：设想一个虚拟煤矿D，生产50万吨，但这个产量只能供应可有可无的最高需求部分，于是各地的需求也应分为两个部分：基本需求、机动需求虚拟产量的运输费用为零，但它对于基本需求来讲，运费为无穷大。OR1例题2：建模1运价地区煤矿甲1甲2乙丙丁1丁2产量ABCD161419M1614190131320M2219230171225M171225050605050需求量302070301050210210OR1例题2：最优解1甲1甲2乙丙丁1丁2产量ABCD3020502003010302050605050需求量302070301050210210OR1运输模型的应用例题3：某机床厂定下一年合同分别于各季度末交货。已知各季度生产成本不同，允许存货，存储费0.12万元/台季，三、四季度可以加班生产，加班生产能力8台/季，加班费用3万元/台。季度正常生产能力单位成本（万元）交货台数12343032202810.5510.81111.125301545OR1例3分析：可用线性规划，但用运输问题更简单要决策的问题是各季度生产量和交货量设xij表示第i季度生产第j季度交货的台数因加班时间生产成本不同，故要区别开来，三四季度可加班，视同增加两个季度需求量合计115台，生产能力合计126台，供需不平衡，因此，增加一项闲置能力。OR1例3建模：.成本交货生产闲置1234能力产量1季度正常生产2季度正常生产3季度正常生产3季度加班生产4季度正常生产4季度加班生产10.5510.6710.7910.910M10.810.9211.040MM1111.120MM1414.120MMM11.10MMM14.103032208288需求量2530154511126126OR1例3结果：.闲置1234能力产量1季度正常生产2季度正常生产3季度正常生产3季度加班生产4季度正常生产4季度加班生产2553021010828533032208288需求量2530154511OR1例题4航运调度问题某航运公司承担六个城市A、B、C、D、E、F之间的四条航线，已知各航线的起点、终点及每天所需的航班数如下表。又知各城市之间的航行天数，假定船只型号相同，装卸货时间各一天，问该公司至少要配备多少条船才能满足需要？航线起点终点每天航班数1234EBADDCFB3211OR1例4城市之间航行天数表CijABCDEFA0121477B1031388C2301555D14131501720E7851703F7852030OR1例4问题分析问题要求的是在保证需要的前提下，至少需要多少船只。所需船只包括两个部分：载货船、空驶船。航线航行天数装卸天数合计航班数载货船数1234173713222219591532115710915OR1例4问题分析（续1）上表显示：载货船共需91条，此船何来？港口到达开出余缺ABCDEF012301120130-1-122-31ABCDEF1213调度中心若无空驶，则91条船刚好够用，但虚线箭头都是空驶。OR1例4问题分析（续2）所需91条货船要经调度而来，有的可在一个港口卸货后装运（如一条船从E到D后再起程赴B）。若港口没有空船，则要从其它港口调度而来。（规模效益）由上表可知：C、D、F港口有多余船只可供调出，而A、B、E港口则需要调入空船。问题的核心是：如何使空驶船的数量为最少？亦即如何按照最近原则调度船只。OR1例4问题分析（续3）为此建立运输问题数学模型。设xij表示每天从i港口调往j港口的空船数，则cijxij就表示ij航线上周转的船只数，∑cijxij表示各条线上周转的船只总数。ABE每天多余船只CDF214731385173221每天缺少船只113OR1例4解题结果上机求解：ABE每天多余船只CDF11111221每天缺少船只113空船总需求量2+5+13+17+3=40条空驶船40条+载重船91条=131条OR1例题5增产调度问题工厂市场A、B、C1、2、3、4100015001750900100019001500产量4250需求5300增产方案：加班生产，能力增长50%，费用增长50%新建D厂，产能2000，投资200万元新建E厂，产能2000，投资300万元新建F厂，产能2000，投资400万元如何增加生产能力？OR1例题5问题分析各工厂位于不同城市，原材料、劳动力、以及运输费各不相同（为什么只考虑可变费用？），计算不同方案对应不同市场的费用，将生产费用和运费统一考虑，从而决定产销方案。将四个方案，在可变成本的意义上，分别求其最优产销分配计划，比较优劣。再加入固定投资因素，进行综合比较。OR1图与网络的应用案例排座问题哈密顿（Hamilton）回路考试日程问题OR1有7个人围桌而坐，如果要求每次相邻的人都与以前完全不同，试问不同的就座方案共有多少种？用顶点表示人，用边表示两者相邻，因为最初任何两个人都允许相邻，所以任何两点都可以有边相连。例1：排座问题OR11237645OR11237645假定第一次就座方案是（1，2，3，4，5，6，7，1），那么第二次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边。OR11237645OR11237645假定第二次就座方案是（1，3，5，7，2，4，6，1），那么第三次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边。OR11237645OR11237645假定第三次就座方案是（1，4，7，3，6，2，5，1），那么第四次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边，只留下7点孤立点，所以该问题只有三个就座方案。OR11237645OR1哈密顿（Hamilton）回路是十九世纪英国数学家哈密顿提出，给出一个正12面体图形，共有20个顶点表示20个城市，要求从某个城市出发沿着棱线寻找一条经过每个城市一次而且仅一次，最后回到原处的周游世界线路（并不要求经过每条边）。例2：哈密顿（Hamilton）回路OR1例2：分析（1）OR1例2：分析（2）OR1例2：分析（3）OR1例2：分析（4）OR1例2：分析（5）OR1例2：分析（6）OR1例2：分析（7）OR1例2：分析（8）OR1例2：分析（9）OR1例2：分析（10）OR1例2：分析（11）OR1最优路线OR1一个班级的学生共计选修A、B、C、D、E、F六门课程，其中一部分人同时选修D、C、A，一部分人同时选修B、C、F，一部分人同时选修B、E，还有一部分人同时选修A、B，期终考试要求每天考一门课，六天内考完，为了减轻学生负担，要求每人都不会连续参加考试，试设计一个考试日程表。例3：考试日程问题OR1解：以每门课程为一个顶点，共同被选修的课程之间用边相连，得图，按题意，相邻顶点对应课程不能连续考试，不相邻顶点对应课程允许连续考试，因此，作图的补图，问题是在图中寻找一条哈密顿道路，如C—E—A—F—D—B，就是一个符合要求的考试课程表。例3：实例分析OR1AFEDCBOR1AFEDCBOR1AFEDCBOR1AFEDCB例3：分析（1）AFEDCB（1）（2）OR1AFEDCB例3：分析（2）AFEDCB（3）（4）OR1例3：分析（3）AFEDCB（5）