运筹学模型(9)

运筹学模型理论

元 , x4D 0元 第四年：x4A 45000第五年：x5D 0元

由此求出第五年末该部门所拥有的资金的本利总额为：143750元，即部门赢利43.75% 。

二、 运输问题模型

1.运输问题模型概述

运输问题是一类特殊的线性规划模型，该模型的建立最初用于解决一个部门的运输网络所要求的最经济的运输路线和产品的调配问题，并取得了成功。然而，在实际问题的应用中，除运输问题外，许多非运输问题的实际问题一样可以建立其相应的运输问题模型，并由此而求出其最优解。下面以“产销平衡模型”对运输问题进行一下简单的概括和描述：

某产品的生产有m个产地Ai i 1,2, ,m，其生产量分别为

ai, i 1,2, ,m，而该产品的销售有n个销地Bj, j 1,2, ,n，其需要量分别为bj, j 1,2, ,n，已知该产品从产地Ai i 1,2, ,m到销地Bj, j 1,2, ,n的单位运价为cij i 1,2, ,m; j 1,2, ,n，试建立该运输问题的线性规划模型。

解：假设从产地Ai i 1,2, ,m到销地Bj j 1,2, ,n的运输量为xij，因从产地Ai到销地Bj的单位运价为cij i 1,2, ,m; j 1,2, ,n，我们可把运输量xij（ i 1,2, ,m; j 1,2, ,n）汇总于产销平衡表中，而把单位运价

cij i 1,2, ,m; j 1,2, ,n汇总于单位运价表中（见下表）。

运筹学模型理论

则在该产销平衡表表中，第j列的物理含义为：从各产地Ai i 1,2, ,m发往销地j的部分运输量x1j,x2j, xmj的和应等于销量bj，第i行的物理含义类同。

min z c11x11 c12x12 cm1xm1 cm2xm2 cmnxmn cijxij

i 1j 1

mn

x

i 1n

m

ij

bj j 1,2, ,n

x

j 1

ij

ai i 1,2, ,m

xij 0

当然，在实际问题的应用中，常出现产销不平衡的情形，此时，需要把产销不平衡问题转化为产销平衡问题来进行讨论。例当产量

a

i 1

m

i

大于销量

ni

jj 1

b

j 1

n

i

时，

只需增加一个虚拟的销地j n 1，而该销地的需要量为

a b

i 1

m

即可。销

运筹学模型理论

量大于产量的情形类同。 2. 应用实例

运输问题模型的应用比较广泛，并不完全局限于运输问题，下面我们举例说明之。

例1.生产时序的安排 1) 问题的提出

北方飞机公司为全球各航空公司制造商用飞机。其生产过程之最后阶段为生产喷射引擎，然后装置于（一极速工作）制妥的机体，该公司有若干近期必须交付使用的飞机的合同，现须安排今后四个月飞机喷射引擎的生产计划，并须于每月末分别提供10、15、25、20台引擎。已知该公司各月的生产能力和生产每台引擎的成本如下表所示（单位：百万元），又如果生产出来的引擎当月不能交货的，每台引擎每积压一个月需存储和维护费用0.015百万元，试在完成合约的情况下，制定一引擎数量的生产安排方案，以使该公司今后四个月的生产费用最小。

2初看之下，这是一个与运输问题模型毫无关系的问题，如何用运输问题模型求出其最优解，这种素质和能力是因人而异的。用运输问题模型求该问题最优解的关键在于怎样建立该问题的产销平衡表及元素xij和单位运价表及元素cij。为

j 1

i 1

b

n

i

a

m

i

此，我们假设xij表示第i月生产并用于第j月交货的引擎数，因公司必须完成合同，则xij应满足：

10 x11

x x 15 1222

25 x13 x23 x33

x14 x24 x34 x44 20

又每月生产的用于当月和以后各月交货的引擎数不可能超过该公司的实际生产能力，故xij还应满足：

x11 x12 x13 x14 25 x x x 35 222324

30 x33 x34

10 x44 下面再构造“单位运价表”，它应等价于这里的“成本费用表”。因第i月生产并用于第j月交货的引擎数的实际成本cij应该是其生产单位成本再加上存

储、维护费用，从而我们可得其“成本费用表”如下：