运输问题模型

4.3运输问题模型问题模型概述运输问题是一类特殊的线性规划模型，该模型最初用于解决部门的运输网络所要求的最经济的运输路线和产品的调配问题，并取得了成功．在实际应用中，除运输问题外，许多非运输问题一样可以建立其相应的运输问题模型，并由此求出其最优解．下面以“产销平衡模型”对运输问题进行简单的概述和描述．某产品的生产有个产地，其生产量分别为，而该产品的销售有个销地，其需要量分别为已知该产品从产地到销地的单位运价为，试建立该运输问题的线性规划模型．m),2,1(miAi),2,1(miain),2,1(niBj),2,1(njbj),2,1(miAi),2,1(niBj),2,1,,2,1(njmicij假设从产地到销地的运输量为，因为从产地到销地的单位运价为，所以可把运输量汇总于产销平衡表中（如表4－7），而把单位运价汇总于单位运价表中（如表4－8）．),2,1(niBi),2,1(miAiijxiAjB),2,1,,2,1(njmicij),2,1,,2,1(njmixij),2,1,,2,1(njmicij销地产地12…n产量12m销量11x12xnx121x22xnx21mx2mxmnx1b2bnb21a2ama表4－7产销平衡表在该表中，第列的物理含义为：从各产地发往销地的部分运输量，，…，的和对应等于销量．第行的物理含义类同．j),2,1(miAijx1jx2mjxjbi销地产地12…n12m11c21c1mc12c22c2mcnc1nc2mnc表4－8单位运价表模型建立minjijijmnmnmmxcxcxcxcxcz112112121111min),,2,1(1njbxmijij),,2,1(1miaxnjiij0ijx在实际中，常出现产销不平衡的情形，此时需要把产销不平衡问题转化为产销平衡问题来进行讨论．如当产量大于销量时，只需增加一个虚似的销地，而该销地的需要量为即可.销量大于产量的情形类同.miia1njjb11njnjimiiba11应用实例1生产时序的安排北方飞机公司制造商用飞机，其生产过程的最后阶段为生产喷射引擎，然后装置于(一极速工作)机体，该公司有若干近期必须交付使用飞机的合同，现要安排今后四个月飞机喷射引擎的生产计划，必须在每月末分别提供10，15，25，20台引擎．已知该公司各月的生产能力和生产每台引擎的成本如表4－9所示(单位：百万元)，且如果生产出来的引擎当月不能交货，则每台引擎每积压一个月需存储费和维护费用0.015百万元，试在完成合约的情况下，制定一引擎数量的生产安排方案，以使该公司今后四个月的生产费用最小．月份合约数生产能力单位成本存储和维护费110251.080.015215351.110.015325301.100.015420101.13表4－9生产成本表模型建立与求解求该问题最优解的关键:建立该问题的产销平衡表及元素和单位运价表及元素．为此，假设表示第月生产并用于第月交货的引擎数，因公司必须完成合同，则应满足ijxijcijxijijx2025151044342414332313221211xxxxxxxxxx又每月生产用于当月和以后各月交货的引擎不可能超过该公司的实际生产能力，故还应满足1030352544343324232214131211xxxxxxxxxx构造“单位运价表”，它应等价于这里的“成本费用表”.销地月123411.081.0951.1101.12521.1101.1251.14031.1001.11541.130表4－10成本费用表由于这是产销不平衡问题，故增加一虚拟的销地，使之能构造为产销平衡模型，并把“产销平衡表和单位运价表”合二为一，如表4－11所示。销地月1234D产量(ai)11.081.0951.1101.1250252M1.1101.1251.1400353MM1.1001.1150304MMM1.130010销量（bj）1015252030表4－11产销平衡表和单位运价表模型建立与求解4141minijijijxcz04141ijijijjiijxbxax最优解为:10,10,20,5,15,10443433231211xxxxxx最小生产费用为:3.77min4141ijijijxcz2航运公司的船只配备问题某航运公司承担六个港口城市A.B.C.D.E.F的四条固定航线的物资运输任务，已知各条航线的起点城市．终点城市及每天的航班数如表4－13所示。航线起点城市终点城市每天航班数1ED32BC23AF14DB1表4－13某航运公司的航线情况假定各条航线使用相同型号的船只，且各城市间的航程天数如表4－14所示。ABCDEFA0121477B1031388C2301555D14131501720E7851703F7852030表4－14各城市间的航程天数若每条船只每次装．卸货的时间各需要一天，则航运公司至少应配备多少条船只才能满足所有航线的运营要求？模型分析、变量假设航线装货天数航程天数卸货天数小计航班数周转数11171193572131521031719194113115115合计91表4－15各航线所需的最少在航船只数建立调度所需船只数情形所对应的产销平衡表、单位运价表:1)对象：每个港口城市；产销平衡表中的产地：到达船只数大于需求船只数的港口城市；产销平衡表中的销地：到达船只数小于需求船只数的港口城市；容易得到：每个港口城市的到达船只数和需求船只数，如表4－16所示．港口城市每天到达每天需求余缺数A01－1B12－1C202D312E03－3F101表4－16港口城市的到达船数和需求船只数用表示从港调拔到港的船只数，则可以给出该问题的产销平衡表，如表4－17所示．ijxij销地产地ABE“产量”C2D2F1“销量”11311x21x12x22x13x23x31x32x33x表4－17产销平衡表该问题的单位运价表的元素视为各港口之间的船只航行天数，于是可给出该问题的单位运价表，如表4－18所示ABEC235D141317F783表4－18单位运价表模型建立求解333312121111minxcxcxcz03131ijjiijijijxaxbx最优解为:其余为01,1,1,231232213xxxx船只调度最小数为:477117113152min3131232322221313xcxcxcxczijx不考虑维修、储备等情况下，至少应配备138条船只。