运筹学课件(简化)

第一部分运筹学

一、什么是运筹学？

实例：一公司有：

三个工厂：A、B、Co各工厂分别有140吨、120吨、50吨产品待运；

三个仓库：甲、乙、丙。甲库可存货60吨，乙库可存货100吨，丙库可存货150吨;

任一工厂到仓库的路程如表：

工厂

仓库、逢BC

甲9126

乙613.54.5

丙1.539

问：如何调运货物才能使总的吨公里最小？

直观思路：1、距离最短A一丙。（140吨）；2,B-丙。（10吨）；依此类推。

可得调运方案：

^工厂存货量

ABC

仓库

甲6060

乙5050100

丙14010150

供应量14012050总和=310

总吨公里数=140*1.5+60*12+50*13.5+10*3+50*4.5=I860,

最佳方案:

工厂存货量

ABC

仓库

甲105060

乙100100

丙30120150

供应量14012050总和=310

总吨公里数=1395。

对该问题如果利用数学符号（即建立数学模型）来表示，可如下讨论：

设工厂A向仓库甲、乙、丙的调运吨数分别为X”、/2、xl3,工厂B向仓库甲、乙、

丙的调运吨数分别为X2I、/2、乙3,工厂C向仓库甲、乙、丙的调运吨数分别为与1、与2、

七3,则调运货物的总吨公里数（相当于运输费用）为

z=9X]]+6匹2+L5XQ+12X2I+13.5X22+3X33+6X3I+4.5x32+9x33

现在需要求该函数的最小值，而限制条件为:

+x12+x13=140

x2]+x22+尤23=120

知+》32+X33=50

X”+x2i+》3i=60

占2+X22+*32=10°

*3+X23+》33=150

、X]”$2，X”，X21，X22，％23，X31，X32，X33—°

运筹学：以系统为研究对象，把系统的功能和特点用模型表示，通过对模型的定量分

析，从总体上寻求最优策略，为决策和揭露新问题提供数量根据，并以研究结果的应用为H

的，保证系统高效运行。

运筹学建立模型的最终目的是实现系统的最优化，帮助管理者作出正确的决策，使系统

正常有效地运行。这里的最优化是指在一定条件下求最优解（可以是求最大值，也可以是求

最小值）。

运筹学研究系统的基本方法由以下5个阶段构成：

第一阶段：观察所要研究的系统，确定存在的问题、影响问题的因素、约束、假设以及

准备优化的目标。

第二阶段：对系统进行描述一一建立模型。

模型的复杂程度视具体问题而定，过份简单则不能准确反映系统的实质，过份复杂则造

成求解的困难。模型是所研究系统的一个理想（简化的）表达形式。一个现实系统的性质可

能受到许多因素的影响，但是一般只有一小部分因素真正支配着系统的特性。建模时应该抓

住这些支配系统的因素，从现实系统中抽象出一个“假想的现实系统”，然后把这些因素之

间的关系确定下来，并简化成一个适合于分析的形式，这种形式就是模型。

第三阶段：根据实际条件对模型进行检验。

模型一旦确定，就应该根据实际条件对模型的正确性、可靠性进行分析检验。一般可按

照下述三种情况之一处理：（1）给出有关方程的统一的精确解法；（2）如果没有统一解法，

则可以代入具体数据进行测算，分析测算结果是否和实际情况相符；（3）如果该模型不能用

任何正规的数学方法处理，则可以用类比方法进行模拟处理。

第四阶段：分析模型。按优化目标的要求选取最优解，即在模型规定的约束条件下求出

符合目标函数要求的最优条件组合。

这一阶段还需要检验在这些约束条件下最优解的敏感程度，即弄清楚当约束条件之一稍

有变化时最优解会不会改变。经过检验，就可以知道最优解对各个约束条件的依赖程度。

第五阶段：贯彻执行.

二、规划问题的几个基本概念：

决策变量：规划问题需要求解的一组变量，这组变量的每一组定值就对应规划问题的

一个具体实施方案。如上例中的/;

目标函数：规划问题一定有一个要求目标，并且这个要求目标可以表示为决策变量的

函数，问题的解决归结为寻求一组决策变量的值，使目标函数实现最大或最小；如上例中的

函数z；

约束条件：每一个规划问题中，决策变量都要满足一定的约束条件，这些条件可用包

含决策变量的等式或不等式表示；

可行域：由约束条件所确定的决策变量的集合，可行域中的每一组决策变量的取值称

为可行解，如上例中的第一个调运方案；

最优解：使目标函数达到最值的可行解，如上例中的最佳方案。

分类：线性规划和非线性规划

单目标规划和多目标规划

注意：

1、规划问题类似于高等数学中的多元函数的最值问题，如：

例：求函数z=，+3xy+6)，的最值，其中x+yW10,x+3y<l,x20,yN0

决策变量：x,y

目标函数：z=x2+3xy+6y

约束条件：x+y<10,x+3y<l,x>O,y>0

Y

可行域：由不等式x+y<10,-+y<8,x>0,y>0所确定的平面区域

显然，可行域中的任何一个点(x,y),都满足约束条件，都是可行解，而要求的最值点

应该是可行域中的最优解。

2、优化问题中目标函数和决策变量必不可少，约束条件对于实际问题一般情况下也一

定存在，但是在利用软件求解时，没有目标函数也可以给出结果，但是这时的结果一般只是

一个可行解，并不是最优解。

三、线性规划：

1、线性规划的特征：目标函数和约束条件都是决策变量的线性函数。

2、一般形式：

max(min)z=gc/,

j=i

Z%尤j<（二,2）2i=1,2,…，m

j=i

xj>0j-1,2,•­•,??

注意：1>规划问题的理论求解方法很多，但是这里我们将不考虑具体理论方法，只需

要掌握软件求解即可。

2>实际解决问题时，对于规划问题一定要对目标函数，以及每一个约束条件给于详细

的解释，不要不加解释只是纯粹的罗列公式。

例1资源最优利用问题

某厂生产甲、乙两种产品，需要煤、电力、水泥三种资源。生产每种产品Ikt需要各种

资源的数量、各种资源的限量以及生产每种产品（kt）的利润（千元）如表所示。问在这种

条件下，应该安排生产甲、乙产品各多少，才能使该厂获得最大利润？

\产品

单位消耗\

甲乙资源限量

煤218

电力127

水泥039

产品利润45

解：（1）问题中待确定的变量一一决策变量：甲、乙两种产品的生产量七，与

（2）决策变量所受的约束。问题中受到限制的是煤、电力、水泥的数量。于是有：

煤的总需求量不能超过供应量：2.YI+X2<8

电力的总需求量不能超过供应量：士+2X247

水泥的总需求量不能超过供应量：3^49

此外，甲、乙两种产品的生产量应该取非负值：X,>0,x2>0

（3）建立目标函数。在三种资源供应量的限制下，合理安排两种产品的产量，使得总

利润

z=4*+5X2

达到最大。

（4）资源最优利用问题的数学模型：求七，X2的值，使

Z=4出|+5X2

达到最大，并满足：

2X1+x2<8

x,+2X2<7

3X2<9

Xf,x2>0

例2物资调运问题

设有两个仓库ApA?,分别储存水泥23t和27%有三个工地B『B2，B3各需水泥17318t

和15t（总存货量等于总需求量）。己知各仓库到各工地的单位运费如表所示，问应如何调运，

使运费最省？

\工地

运费\

B,B2B3

A.3113

192

A2

数学模型：求变量与（从仓库A,运往工地号的水泥数量）的值，使目标函数:

z=]+6X12+9X]3+6X21+1lx22+6x23

达到最小，并满足：

xn+xI2+x13=23

x2]+x22+x23=27

X”+x21=17

X|2+X22=18

XI3+工23=15

与NO,/=1,2;J=1,2,3

例3生产安排问题

某车间的车工分i、n两级，各级车工每人每天的加工能力、成品合格率及日工资数如

表所示

级别加工能力（个/人•天）成品合格率（％）工资（元/天）

I240975.6

II16095.53.6

工厂要求每天至少加工配件2400个，车工每出一个废品，工厂要损失2元，现有I级

车工8人，n级车工12人，且工厂要求至少安排6个II级车工。试安排车工工作，使工厂

每天支出费用最小。

解：（1）决策变量：安排I、II两级车工的人数为占，x2

（2）分析约束条件：

车工人数限制：%,<8,6<x2<12

每天加工的配件总数限制：240J,+160X2>2400即3x,+2x2>30

特殊约束：X,>0,乙20且为整数

（3）目标函数：这个问题的目标是使工厂每天的总费用最小。包括车工的工资和因为

出废品而造成的损失。

每个I级车工每天的费用：工资：5.6废品损失：2x（240x3%）共计：20

同理每个H级车工每天的总费用为：18

工厂每天的总费用为：z=20x1+18x2。

(4)数学模型：求求匹，々的值，使.

Z=20戈1+18X2

达到最大，并满足：

X148

x2>6

x2<12

3X[+2X2>30

X1,x2>0且为整数

四、整数规划：

1、整数规划：决策变量只能取整数值。

整数规划对应的线性规划：去掉整数规划中的整数限制，得到的一般线性规划。

2、常见基本模型：

(1)最优生产计划问题

一家玩具公司制造三种玩具，每•种要求不同的制造技术，高级的•种每台需要17小

时加工装配劳动力，8小时检验，利润30元。中级的每台需要2小时加工装配劳动力，半

小时检验，利润5元。低级的每台需要半小时加工装配劳动力，10分钟检验，利润0.6元。

可供利用的加工劳动力为500小时，检验100小时，同时，据市场预测，对高级玩具需求量

不超过10台，中级不超过30分，低级不超过100台。该公司应如何安排生产计划才能使利

润最大？

(2)工厂选址问题

有〃个城市，每日需要某种物资的数量分别是4,电,…,4,先在计划要在其中选取加个

城市，建造，〃座生产这种物资的工厂。假设已知若在城市/建厂，II产量最多为鸟，而建设

费用为人。设城市i到城市/的单位运价为0,问这加个工厂应该设在何处，才能使得既满

足需要又能使总费用最省？

解：设变量为=1|在城]严,，从城市i到城市j•运送的物资数量为％.，则可以建

[0否则

立如下数学模型：

Minz='t'tcijxij+XfJyj

1=1j=\j=\

使得：

(3)背包问题

一个背包的容积为V。现有〃中物品可装，而每种物品都只能整件装入；物品，的重量

为叼，体积为5。问如何配装，使得既不超过背包的容积，又使装的总重量最大？

解：设x.=P物品里装入，则可以建立如下数学模型：

'[0否则

n

Maxz=Z（OjXj

j=i

使得：

tv；-v

＜7=1

Xj=0或Lj=1,2，…,n

（4）指派问题

设有〃项任务，恰好有〃个人可以分别完成其中一项，但由于各人能力不同，由不同的

人去完成不同的工作所耗用的时间不同，具体所耗用的时间可用如下效率矩阵。表示，问指

派那个人完成那项任务，总耗时最少？

效率矩阵：第i个人完成第，项任务所耗时与

CllC\2…C\n

C_C2IC22…C2n

%…Gm.

解：设局=P当分配第i个竺产j项工作时，则可以建立如下数学模型:

10否则

Mm•

足

满

3、整数规划的求解：

几个结论：

1＞整数规划无法直接求解，往往先转化为对应的线性规划求解，但是对应的线性规

划的解一般不是整数规划的最优解；

2＞对求最大的整数规划，整数规划的最优目标函数值不大于其对应的线性规划的最

优目标函数值；

3＞对求最小的整数规划，整数规划的最优目标函数值不小于其对应的线性规划的最

优目标函数值；

4＞如果将线性规划的可行域分为若干子域，则在每个子域上求得的最优值不优于整

个可行域上的最优值。

求解方法：分枝定界解法步骤

Stepl:设原整数规划为A,对应的线性规划为A，；

Step2:如果A，没有可行解，则A也无可行解；

Step3:如果A，有最优解，则进一步检查是否符合整数条件:

符合：则该解就是A的最优解，程序停止；

不符合：任选一个不符合整数条件的变量勺=鸟，将A分解为四，当两个

问题：

AA

Bi：xjAbi][x.<[^]+l

Step4:分别求身,耳的最优解；

Step5:比较尚未分解的两个问题的最优解，注意其中最大的一个，若该最优值对

应的解以符合整数条件，则该解就是A的最优解，停止；若该最优值对应的解不符合

整数条件，则重复3继续分解。

例：问题A：

maxz=3玉+2x2

2玉+3九2414

<2xl+x2<9

Xi，xNO,且为整数

解：(1)求解A对应的线性规划A的最优解

xl=3.25,x2=2.5,max=14.75

(2)因为不满足整数条件，故可以按照变量再将问题分解为

maxz3匹+2X2maxz=+2x2

X

2玉+32<142xl+3X2<14

2x+x<92%j+x<9

用：l2B2:2

xl<3x1>4

x„x2NO且为整数和/NO且为整数

(3)不考虑整数条件，求解以上两个问题的对应线性规划禺，不得最优解:

B；：%,=3,X2=8/3,maxz=14.33

B'2：X,=4,X2=l,maxz=14.00

其中B'2已经是整数解，故不必继续分解.但是B'2所对应的目标函数值不一定是原问题

A的最优解，这是因为皆还没有得到整数解，由与所确定的原整数规划A的最优值的上界

是14.33,而由提所确定的最优值为14.00,故原问题A的最优解的目标函数值可能在14.00

和14.33之间，故仍需对用进行分解.

(4)考虑劣中非整数解/将问题分解为：

maxz=3匹+2x2maxz=3匹+2x2

X

2xl+3/<142x1+32<14

21]+x2<92x,<9

G:,%)<3。2：<王<3

x2<2x2>3

X,,X2。旦为整数

2XpX2NO且为整数

(5)不考虑整数条件,求解以上两个问题的对应线性规划C：,得最优解：

C；：X[=3,0=2,maxz=13.00

C'2：x,-2.5,x2-3,maxz=13.50

其中C；已是整数解,所以不必继续分解.仍未得到整数解，故仍可对c2继续分解.

比较已经得到的整数解对应的目标函数值以及尚未分解的目标函数值13.50,山于

益所对应的目标函数值最大，故对继续分解已无意义(因为。2的后继问题所对应的最优

目标函数值的上界是13.50,小于14.00).所以原问题的最优解为

X]=4,x2=1,maxz=14.00.

五、0一1规划

0-1规划是一种特殊的整数规划问题，它的全部决策变量只取0或1两个值，对它的

求解可以利用整数规划的方法，也可以利用完全枚举法(n个变量的可能情况为2n种)。

注意：1、在实际问题中，决策变量往往只有两种可能或两种状态，如，对某个建设项

目投资或不投资，对某种货物购进或不购进，在某地建厂或不建厂。此时可以引入0—1变

量，建立数学模型。

2、在实际的数学建模竞赛题目中，往往决策变量中的几个属于0—1变量，而其余仍是

普通变量，这是就不能用以上方法解决。而需要具体问题具体对待。

六、非线性规划：目标函数和约束条件中至少有一个是非线性的。

例1某城市要选定一个运输服务中心的位置，为该城后有固定位置的m个用户提供服

务，其中k(k<m)个用户要求其距离不超过d.。如何确定服务中心的位置，才能使其服务时

总的费用最小？

解设服务中心的坐标是(x,y),第i个用户的坐标已知为(ai,bj,j表示服务中心

到第i个用户的单位运价，进一步假设运输路线不受道路的影响，则可以得到以下非线性规

划模型：

mingcjJ(x-aj2+(y-bj2

i=l

(x-aj2+(y-bj)2<d2i=l,…,k

例2在传送网络上，从n个电站向负载输送能量。设p,为第i个电站产生的能量，

Fj(pj)为第i个电站产生能量Pi所需成本，i=l,…,n,L(p「p2,…,pQ为传递过程中所

造成的能量损耗，D为总的需求量。试确定一个最经济的产生能量方案，使需求得到满足。

解最经济的产生能量方案需使总的成本最低，于是该问题中的决策变量为P,

i=I,---,n,则可得以下非线性规划模型：

min^FJpJ

i=l

EP-L(P|，P2,…，Pn)=D

i=l

例3设国民经济由n个部门组成，分别编号为1,2,…，n。已知各部门间的直接消耗

系数矩阵为

auai2…a；

3a”,,,a*

A=(a)=

ijnxn«••«••・•••••

_anlan2ann_

其中ajj表示第j部门生产价值为一单位的产品直接消耗第i部门的产品的价值，

uJ

l<i,j<n=第i个部门的生产函数为

Xj=fi(l,,k,)i=l,…,n

其中：Xj为第i个部门的总产品价值；

I为投入到第i个部门的资金总额;

1,为投入到第i个部门的劳力数。

问题是如何在给定总资金K与总劳力L的前提下，对每个部门进行最佳的资金及劳力投入分

配，以使国民收入最大。

解国民经济的各部门的总产品应该由两部分构成，•部分产品用来供给其它部门供其

它部门消耗，另一部分作为该部门的最终产品。因而该部门的总产品价值也对应的应该由两

部分构成。国民收入应该指国民经济的各个组成部门生产的最终产品的总价值之和。对每个

部门而言，最终产品总价值可以通过总产品价值减去其它部门消耗该部门的产品价值求得。

于是可设第i个部门的最终产品价值为丫厂则有

xi=Eaijxj+yii=L…,n

j=i

以矩阵形式表示为

X=AX+Y,即（I-A）X=Y

其中I为n阶单位矩阵，X=（x-x2,…，x“）T,Y=（力广2,…，yj，于是可得如下的

非线性规划模型：

max^yj

i=l

（I-A）X=Y

Xi=fi（L，kj）i=l,…,n

与

WK

Xj>0,Yj>0,lj>0,kj>0i=n

第二部分赛题选讲

钢管订购和运输

要铺设一条a…fAs的输送天然气的主管道，如图一所示（见下页）。经

筛选后可以生产这种主管道钢管的钢厂有S1,S2,…s,。图中粗线表示铁路，单细线表示公

路，双细线表示要铺设的管道（假设沿管道或者原来有公路，或者建有施工公路），圆圈表示

火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程（单位km）。

为方便计，1km主管道钢管称为1单位钢管。

一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂S,在指定期限内能

生产该钢管的最大数量为>个单位，钢管出厂销价1单位钢管为p,万元，如下表：

i1234567

Si80080010002000200020003000

Pi160155155160155150160

1单位钢管的铁路运价如下表:

里程（km）W300301〜350351〜400401〜450451〜500

运价（万元）2023262932

里程（km）501〜600601〜700701〜800801〜900901〜1000

运价（万元）3744505560

1000km以上每增加1至100km运价增加5万元。

公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。

钢管可由铁路、公路运往铺设地点（不只是运到点A"/!?，…，45,而是管道全线）。

（1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用）。

（2）请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大,

哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结

果。

（3）如果要铺设的管道不是一条线，而是个树形图，铁路、公路和管道构成网络，

请就这种更一般的情形给出一种解决办法，并对图二按（1）的要求给出模型和结果。

29030

'SI

S4

16(1

S332020

16120

5269070i

30'

69070

1200170S6<415

110

720500

52OJ88、62

420414

462

202S510'

70

1100SI

4210220

20,A12

480411

1953

31前。。

30(

1150,10A8

5

600'

10

45i194205

80A6

45图一

75i彳706

244

3

104301

A\

41

钢管购运和管道铺设方案一

摘要：本文解决的是一个钢管购运和管道铺设方案设计问题，目的是使总费用最

小。首先利用动态规划方法求解所有钢厂到各管道节点的最小运费表，并通过分

析得出从管道两边节点向中间铺路的方法可以减少铺设费用，以所有钢厂到各管

道节点并向不同方向铺设的钢管数量为变量，导出总费用的表达式，把问题化为

以总费用为目标函数的非线形规划，用Matlab对此进行求解。然后通过钢厂钢

管销价和产量上限的微小变化及在新的条件下的求解，分析对总费用和购运计划

的影响。最后把模型推广到树形管道，通过变换把它化为多条线形管道，用同样

方法求解。由于计算中变量个数的增加使计算复杂度提高，我们提供了一些优化

策略。在本文的末尾，我们讨论了模型的优缺点和实际应用中的改进方向。

本文利用以上算法较好的解决了问题，得到了问题的最优解。对于问题一,

解得最小总费用为127.86亿元，购运和铺设方案见表二。对于问题二，分析得

出S6厂的钢管价格变化对总费用影响最大，S1厂的产量上限变化对总费用影响

最大。对于问题三，解得最小总费用为140.66亿元，购运和铺设方案见表六。

问题重述

要铺设一条线形的天然气的运输管道，钢管由7个钢厂提供，可以由公路、

铁路运往铺设地点。钢厂提供的钢管量不能超过它的产量上限，且或者大于500

或者为0。公路、铁路运输费用的计算公式已经给定。在此条件下求出定购运输

计划，使总费用最小。并分析钢厂钢管销价和产量上限变化对购运计划和总费用

的影响。以及推广模型以解决铺设树形管道这种更一般的情形。

模型的假设

1.公路运输费用为1单位钢管每公里0.1万元，不足整公里按整公里计算。

2.购买和运输钢管都是整单位（即为整公里）。

3.沿管道或者原来有公路或者建有施工公路。

4.一个钢厂如果承担制造钢管，至少要生产500个单位。

5.钢管可由铁路、公路运往铺设地点。

6.把“钢厂钢管的销价和产量上限变化对总费用和运购计划的影响”理解为在

最优解附近的微小变化对总费用和运购计划的影响。销价最小变化是1万元,

产量上限的最小变化是1个单位。

三.问题分析

铺设一个天然气运输管道（线形或树形），总费用包括购买钢管的费用，运

费和铺设时的运费。购买钢管的费用由钢厂的钢管销价和向这个厂订购的钢管数

量决定。运费由钢厂向铺设起始点运输的钢管数量和它到此起始点的运输道路决

定（由于通过铁路和公路运输，所以并不仅仅由路程决定）。一般情况下铁路运

输比公路运输要节省费用（只有在200公里以内，公路运输比铁路运输要节省）。

对于铺设费用，在假设一的前提下，由一头出发，铺设x公里的费用的计算是：

0.1*[x+（x-l）+（x-2）+...+2+l]=0.05*x*（x+l）,通过比较可以发现:铺设一段管道，

从两头往中间铺比从一端向另一端铺要节省费用。再由假设三，铺设时沿管道走

的是公路，所以当管道段较长时，两头铺所节省的费用是比较可观的。比如问题

一中，所有管道段都从一头铺的铺设总费用为：0.05Z[DyX（Dx.y+l）]=12.29

亿元。而在最优的铺设方法下（即两头向中间铺的路程相同），铺设总费用为：

0.05^2x[^x（^+l）]=6.16亿元，最优解中的铺设费用应在这两者之间。

因为铺设费用的表达式是二次式，所以求解总费用是一个非线性规划问题。

四.符号说明

Pi：钢厂S的钢管销售价格

si：指定期限内钢厂Si能生产钢管的最大数量

Lij：从Si运到Aj,且向左边铺路的钢管数量

Ri」：从S运到Aj,且向右边铺路的钢管数量

Ti：从Si运出的钢管总量，要求Ti<=Si，且R=0或Ti>=500

Fi,j：一单位钢管从Si运到Aj的最少费用

Dx.y：相邻两点Ax.Ay之间的路程

G：购买钢管的费用

C2：把钢管运送到所有Aj的总运费

C3：从冉开始铺设钢管过程中的公路运费

C：总费用，C=Ci+c2+c3

ki：S厂钢管价格对总费用的边际影响

mi：S厂钢管产量上限对总费用的边际影响

五.模型的建立与求解

（-）问题--的订购和运输计划求解：

1.模型一的建立：

由定义得：

15

从Si运出的钢管总量：Ti=X（L,」+Rij）

7

购买钢管的费用：C1=^（Ti*Pi）

157

把钢管运送到所有Aj的总运费：C2=，£心」+九）*凡]

j=\i=\

77

从Aj向左铺设的钢管量Lj=£L,j；向右铺设的钢管量&=£氏3

i=li=l

15

铺设钢管过程中的公路运费：C3=0.1*£[LJ*（Lj+l）/2+Rj*（均+1）/2]

j=l

目标函数（总费用）为：

nnn（Ci+C2+C3）

s.t.Tj<Si，且Ti=O或Ti>500（i=l,2,...7）

对相邻两点Ax,Ay有Rx+Ly=Dx.y（x,y=l,2,...15）

问题即转化为对以Lj,Ri,j为变量的非线形规划的求解。

2.先求出从S运送单位钢管到Aj的最少费用E,j,这是一个类似求最短轨道的

动态规划问题，可以仿照Dijkstra算法，特殊的是边的权以路程表示，而阶

段指标是运费。求解结果列表如下：

表一：最小运费表（问题一）单位（万元）

SISS3SSS

245s67

Ai170.7215.7230.7260.7255.7265.7275.7

160.3205.3220.3250.3245.3255.3265.3

A2

140.2190.2200.2235.2225.2235.2245.2

A3

A498.6171.6181.6216.6206.6216.6226.6

A538111121156146156166

、620.595.5105.5140.5130.5140.5150.5

3.18696131121131141

A7

As21.271.286.2116.2111.2121.2131.2

A964.2114.248.284.279.284.299.2

AJO921428262576277

An961468651335166

A121061569661514556

A13121.2171.2111.276.271.226.238.2

A1412817811883731126

A151421921329787282

3.用Matlab编程序求解目标函数，得到最优解为127.54亿元，此时从Si,S?

S7运出的钢管数量为：

T,=800,T2=800,T3=1000,T4=0,T5=1336,T6=990,T7=245

但是由于T7=245<500,而题目中要求“一个钢厂如果承担制造钢管，至少

需要生产500个单位”，所以此解不符合条件。

4.再分两部分进行第二步求解，一是在增加约束T7=0的情况下，二是在增加约

束T7>=500的情况下分别计算。对于第一种情况，在实际计算中我们发现，

只要把S7销售钢管的价格P7变的很高（比如1000万元），那么在最后的结果

中肯定不会出现有S7提供钢管的情况，这样求得的结果与增加约束17=0相

同。由Matlab解得总费用为127.86亿元。对于第二种情况，求得的结果是

127.97亿元。并且在两种情况下所有的Ti都满足条件，故不需要再继续求解。

最优解是第一种情况，即当T7=。时。

补充：如果在计算中，第二步求解得到的解仍然有Ti不满足条件，再对此Ti分几部分

进行下一步求解，依次类推。

最优解对应的钢管购运计划如下表：

表二：钢管购运和铺设计划（问题一）

SiSSS

23s45s6s7

左右左右左右左右左右左右左右

Ai00000000000000

75

A2001040000000000

A3002260000002820000

A4370950336000000000

A52980000000308100000

As18415000000000000

19076000000000000

A7

As001251750000000000

A9000050515900000000

A1000000000321300000

An000000002701450000

A120000000000751100

A13000000000019913400

A14000000000028633500

A150000000000165000

Ti80080010000136612050

说明：

1）表中表示从S,订购并运输到出的钢管数量，以及这些钢管向左和向右铺设的数量。

2）虽然表中有从Si运到灯的钢管向左和向右的分配量，实际上只要所有的钢管运到Aj

后，向左和向右的铺设量与钢管的来源无关。

在上表的方案下，第一问的总费用最小为127.86亿元。

钢管购运和管道铺设方案二

1、符号说明：

5,.：钢厂S,在指定期限内钢管的最大产量；

%：到A,之间铺设管道的里程数；

C,：单位钢管从钢厂S,运到4所需最小订购和运输费用；

X”钢厂S,是否承担制造这种钢管；

为：钢厂S,运到4点的钢管数量，不含路过&的部分；

Z,：运到A,的所有钢管沿4A*铺设的数量；

Z,：运到勺的所有钢管沿A,--A,铺设的数量；

"(A,)：树中4的度数；

d-(A《：树中A,的入度数；

1+(&)：树中&的出度数；

〃：单位钢管1公里的公路运输费用。

2、基本假设：

(1)假设运到A.的钢管，只能在4T和AJM之间包含4的某个