我爱建模[分享]

阿尔芒 · 发表于 2004-1-9 06:26:13

http://zjnumcm.126.vom  摘

                        线性规划模型

一、问题的提出

在生产管理和经营活动中经常提出一类问题，即如何合理地利用有限的人力、物力、财

力等资源，以便得到最好的经济效果。

例1    若需在长为4000mm的圆钢上，截出长为698mm和518mm两种毛坯，问怎样

截取才能使残料最少？

初步分析  可以先考虑两种“极端”的情况：

（1）全部截出长为698mm的甲件，一共可截出»5件，残料长为510mm。

（2）全部截出长为518mm的乙件，一共可截出»7件，残料长为374mm。

由此可以想到，若将 x个甲件和y 个乙件搭配起来下料，是否可能使残料减少？把截

取条件数学化地表示出来就是：

                  698 x + 518y  £ 4000

                  x ，y都是非负整数

   目标是使：z = （材料利用率）尽可能地接近或等于1。（尽可能地大）

   该问题可用数学模型表示为：

   目标函数　　： max z =

   满足约束条件：　　698 x + 518y  £ 4000 ，  (1)

                  　　　　　x ，y都是非负整数 . (2)

例2 某工厂在计划期内要安排生产I 、II两种产品，已知生产单位产品所需的设备台

数及A、B两种原料的消耗，如下表所示。



      I


      II


设备


      1


      2


   8台数

原材料A


      4


      0


   16kg

原材料B


      0


      4


   12kg

该工厂每生产一件产品I可获利 2 元，每生产一件产品II可获利 3 元，问应如何安排生产计划使工厂获利最多？

这问题可以用以下的数学模型来描述：设  x 1, x 2分别表示在计划期内产品I、II的产量。因为设备的有效台数为8 ，这是一个限制产量的条件，所以在确定I 、II的产量时，要考虑不超过设备的有效台数，即可用不等式表示为：

                                                      x 1  +  2x 2  £  8 .

同理，因原材料A 、B的限量，可以得到以下不等式：

                        4 x 1       £  16

                                                               4 x 2  £  12.

   该工厂的目标是在不超过所有资源限量的条件下，如何确定产量x 1、x 2以得到最大的利润。若用 z 表示利润，这时z = 2x 1 + 3 x 2 。综上所述，该计划问题可用数学模型表示为：

   目标函数：    max z = 2x 1 + 3 x 2

   满足约束条件：    x 1  +  2x 2  £  8

                     4 x 1       £  16

                                                         4 x 2  £  12.

                        x 1 ，x 2  ³  0

   该模型的特征是：

（1）有一组决策变量（x 1 ,x 2 ,…,x n)表示某一方案；这组决策变量的值就代表一个具体方案。一般这些变量取值是非负的。

（2）存在一定的约束条件，这些约束条件可用一组线性等式（不等式）来表示。

（3）有一个要求达到的目标，它可用决策变量的线性函数（称为目标函数）来表示。按问题的不同，要求实现目标函数最大化或最小化。

满足以上三个条件的数学模型称为线性规划模型。其一般形式为：

目标函数： max(min) z = c 1x 1 + c 2x 2 + …+ c nx n

               a11x 1 + a12x 2 +….+ a13x n  £ (= , ³) b 1

               a21x 1 + a22x 2 +…. + a23x n  £ (= , ³) b2

满足约束条件： … …

               a m1x 1 + a m2x 2 +….+ a m3x n £ (= , ³) b m

                        x 1 ,x 2 ,…, x n  ³ 0

二、          穷举法

以例1为例介绍穷举法。

先根据（1）求出x 所有可能的取值为：0、1、2、3、4、5，再由（1）把相应y 的最

大值求出，对应为7、6、5、3、2、0，依此计算住z值如下表：

  x
   0
   1
2
3
   4
   5

  y
   7
   6
5
3
   2
   0

  z
90.65%
95.15%
99.65%
91.20%
95.70%
87.25%

   由表可知，在一根圆钢上截取2个甲件和5个乙件，可以得到最高的材料利用率99.65%。

   例2作为课后练习。

三、图解法

1、用二元一次不等式表示平面区域

y                y                   y                y

  o          x    o          x       o       x o          x

ax + by > c          ax +by < c          ax +by >c             ax +by < c

a>0, b >0          a >0, b<0          a>0, b<0             a>0, b<0

2．  图解法

图解法简单直观，有助于了解线性规划问题求解的基本原理。现对例1进行图解。

条件（1）、（2）对应的恰好是图1中斜线下方和两条坐标轴在第一象限中的三角形AOB

内的整点（即横、纵坐标都是整数的点）。当整点越靠近直线AB，残料就越少（若AB恰好过其中一个整点，则该整点坐标所对应的截料方法一定是无残了的最佳截料方法）。比较C、D、E、F、G、H，知E（2，5）距直线AB最近，故知取x =2，y = 5是材料利用率最高的截料方法。

在以x1、x2为坐标轴的直角坐标系中，非负条件x1, x2 ³ 0 是指第一象限（及x轴正半轴、

y轴正半轴)。每一个约束条件都表示一个半平面。若约束条件  x 1 + 2x 2  £ 8 是代表以直线

x 1 + 2x 2 = 8为边界的左下方的半平面。    x2                         4x1 = 16

若同时满足x 1 + 2x 2 £ 8，4 x 1 £ 16，          x 1 + 2x 2 = 8       4x 2=12

4 x 2 £ 12和x 1 ，x 2 ³ 0约束的点，       Q4          Q3

必然在由这三个半平面围成的区域内。 3                Q2

由例1的所有约束条件为半平面围成    2

的区域见右图阴影部分。阴影区域中    1

的每一个点（包括边界点）都这个线                      Q1                x1

性规划问题的解。                      o

   再分析目标函数max z = 2x 1 + 3 x 2，在这坐标平面上，它表示以 z为参数、– 为斜率的一族平行直线：

            x 2 = – x1 +

位于同一直线上的点，具有相同的目标函数值，因而称它为“等值线”。当z值由小变大时，直线x 2 = – x1 + 沿其法线方向（法线方向是指与直线垂直的方向）向上方移动。当移动到Q 2点时，使z值在可行域（阴影部分）边界上实现最大化，这就得到了例 1 的最优解Q2，Q2点的坐标为（4，2）。于是算得z =14。

   这说明该厂的最优生产计划方案是：生产产品I  4件，生产产品更新换代II  2件，可得到最大利润为14元。

练习：

1．某厂生产甲、乙两种产品，生产甲种产品每件要消耗煤9吨，电力4千瓦，使用劳动力3个，获利70元；生产乙种产品每件要消耗煤4吨，电力5千瓦，使用劳动力10个，获利120元。有一个生产日，这个厂可动用的煤是360吨，电力是200千瓦，劳动力是300个，问应该如何安排甲、乙两种产品的生产，才能使工厂在当日的获利最大，并问该厂当日的最大获利是多少？（甲20件，乙24件，获利4280元）

2．电视台为某个广告公司特约播放两套片集。其中片集甲播映时间为20分钟，广告时间为1分钟，收视观众为60万，片集乙播映时间为10分钟，广告时间为1分钟，收视观众为20万。广告公司规定每周至少有6分钟广告，而电视台每周只能为该公司提供不多于80分钟的节目时间。电视台每周应播映两套片集各多少次，才能获得最高的收视率？

3．预测2000年奥运会男子铅球的成绩。（资料来源：1996-08-02《体育报》）

届次
成绩（米）
届次
成绩（米）
届次
成绩（米）

7
14．81
15
17．41
21
21．05

8
14．955
16
18．57
22
21．35

9
15．87
17
19．68
23
21．26

10
16．005
18
20．33
24
22．47

11
16．20
19
20．54
25
21．70

14
17．12
20
21．18
26
？

4．预测2000年我国进出口总额。（资料来源：1994年《中国经济统计年鉴》及1997-1-2

  《人民日报》）

年份
进出口总额
年份
进出口总额
年份
进出口总额

1981
4
1987
6．8
1993
19．6

1982
3．9
1988
7．9
1994
24

1983
4
1989
11．2
1995
28．1

1984
5
1990
11．5
1996
29

1985
6
1991
13．5



1986
6
1992
16．6
2000
？

阿尔芒 · 发表于 2004-1-9 06:28:26

http://zjnumcm.126.com 摘

                                    不等式模型

一、预备知识

1．二次函数的最大值（最小值）

2．基本不等式

（1）如果a，b Î R，那么  a2 + b2 ³ 2ab (当且仅当a = b 时取“=”号）.

（2）如果a，b Î R+，那么 ³  (当且仅当a = b 时取“=”号).

（3）如果a，b ，c Î R+ ，那么a3 + b3 + c3 ³ 3abc (当且仅当a = b = c 时

   取“=”号).

（4）如果a，b ，c Î R+ ，那么 ³ (当且仅当a = b = c 时

   取“=”号).

二、利用二次函数求解

例1 在测量某物理量的过程中, 因仪器和观察的误差, 使n得次测量分别得到a 1, a 2, ××× ,

a n , 共n个数据. 我们规定所测量物理量的“最佳近似值” a是这样一个量：与其他近似值比较, a与各数据的差的平方和最小. 依此规定, 从a 1, a 2, ×××, a n推出的a = _____________.

分析：建立目标函数f (a) = (a – a1) 2 + (a – a 2 ) 2 + ××× + (a – a n) 2  .

例2 大楼共有n层，现每层指派一人，共人集中到第n层开会. 试问如何确定k，能使位参加会议人员上、下楼梯所走路程总和最小？（假设相邻两层楼梯长都一样）.

分析：设相邻两层楼梯长为a ，则问题转化为下列和式S的最小值的探求：

S = S（k) = a (1 +2 +3 + ××× + k) + 0 + a (1 +2 + ××× + n – k ) = a [ k 2 – (n +1) k + (n 2 + n) ].

目标函数S（k)为 k的二次函数，且a > 0 ，故当n为奇数时，取k = ，S最小；

当为k 偶数时，取k = 或，S最小.

三、利用基本不等式求解

例3       新购某电器价值23元，自使用之日至第n次大修共经过1800（) 天，到大修之日必须大修之后才能使用。每次大修的费用为2千元。使用者宣布该电器报废仍可由厂家回收而售得3千元。为了使开销与使用时间之比Q值最小，问使用者第几次大修时应宣布此电器已无大修必要而应报废售出?

例4       某厂要生产一批无盖的圆柱形桶，每个桶的容积为立方米，用来做底的金属每平方米  30元，做侧面的金属每平方米为  20元，如何设计圆桶尺寸，可以使成本最低？

四、                                                                                                                                                    其它相关题

例（包装成本模型）某种冰激淋是用球型塑料壳包装的，有60克装和150克装两种规格。假设冰激淋售价 = （冰激淋成本 + 包装成本）´（1 + 利润率），并且包装成本与球型外壳表面积成正比。已知60克装冰激淋售价为1.5元，其中冰激淋成本为1分/克，利润率为25%，问在利润率不变的情况下，150克冰激淋应售价多少？两种规格中，哪种比较合算？

（参考数据» 2.71，球的表面积为 S = 4p r 2，体积为V = p r 3.)

课后练习：

1．建筑学规定，民用住宅的窗户面积必须小于地板面积，但按采光标准，窗户面积与地板面积的比应不小于10%，并且这个比越大，住宅的采光标准条件越好，问同时增加相等的窗户面积与地板面积，住宅的采光是变好了还是变坏了？请说明理由。（变好）

2．一轮船行驶时，单位时间的燃料费与其速度的立方成正比，若轮船的速度为每小时10 km 时，燃料费为每小时35元，其余费用不随速度而变化，每小时为560元，求轮船速度为多少时，轮船行每千米的费用最少？（20km/小时，42元/千米）

3．要在宽为6米的辅导室当中装一盏电灯，电灯

装在距离正中桌面的高h是多少米时，才能使靠

墙的课桌得到的亮度最大？（已知电灯对课桌的                      a b

照度E = I cosa / b 2 ，  I为电灯的光度，                      h

b，a 如图所示）

                                                                  3

( h = 米）

阿尔芒 · 发表于 2004-1-9 06:30:25

集四海力量为你解决你的难题！返回首页
--浙江师范大学数学建模协会留言
yyhyq@163.com
农场计划　　　　
我们需要你的帮助，如果你能解答下面的题目，请将答案通过邮件或是在本站留言版上发表!如果你有什么问题的话，也可以通过邮件或留言，我们会为你解答！
农场计划

英国某农场主有200亩土地的农场，用来饲养奶牛。现在要为未来五年制定生产计划。
现在他有120头母牛，其中20头为不到2岁的幼牛，100头为产奶牛。每头幼牛需用2/3英亩土
地供养，每头产奶牛需用一英亩。产奶牛平均每头每年生1.1头牛，其中一半为公牛，生出后
不久即卖掉，平均每头卖30英镑；另一半为母牛，可以在生出后不久卖掉，平均每头卖40英镑
，也可以留下饲养，养至2岁成为产奶牛。幼牛年损失5%；产奶牛年损失2%。产奶牛养到满12
岁就卖掉，平均每头卖120磅。现有的20头幼牛，0岁和1岁各10头；100头产奶牛，从2岁到11
岁，每一年龄的都有10头。应该卖掉的小母牛都已卖掉。所有20头是要饲养成产奶牛的。
一头牛所产的奶提供年收入370英镑。现在最多只能养130头牛。超过此数每多养一头，要
投资200英镑。每头产奶牛消耗0.6吨粮食和甜菜。粮食和甜菜可以由农场种植出来。每英亩产
甜菜1.5吨。只有80英亩的土地适合种粮食，且产量不同。按产量分作4组：
第一组20英亩，亩产1.1吨；
第二组30英亩，亩产0.9吨；
第三组20英亩，亩产0.8吨；
第四组10英亩，亩产0.65吨；从市场购粮食每吨90英镑，卖粮食每吨75英镑。买甜菜每吨70
英镑，卖出50英镑。
养牛和种植所需劳动量为：每头幼牛每年10小时；每头产奶牛每年42小时；种一英亩粮食每
年需4小时；种一英亩甜菜需14小时。
其他每费用：每头幼牛每年50英镑；产奶牛每头每年100英镑；中粮食每英亩15英镑；种甜菜
每亩每年10英镑。劳动费用现在每年为4000英磅，提供5500小时的劳动量。超过此数的劳动量
每小时费用为1.2英镑。
任何投资资本支出都从10年期贷款得到。贷款年利率15%，每年偿还本息总和的1/10，十年还
清。每年货币的收支之差不能为负值。此外，农场主不希望产奶牛的数目在五年末较现在减少
超过50%，也不希望增加超过75%。
应如何安排5年的生产，使收益为最大？

　
　
　
　
　
　
　
　
我们需要你的参与，你的合作，三人行必有我师！

　

阿尔芒 · 发表于 2004-1-9 06:31:20

首页|留言

与Logistic模型不同的另一种描述种群增长规律的是Gompert模型，x(t)=rxln(N/x),其中r和N的意义和Logistic的一样。设渔场的自然增长率服从这类型，又单位时间内捕捞量为h=Ex，讨论渔场鱼量的平衡点及其稳定性，求最大持续产量hm及获得最大产量的捕捞强度Em和渔场鱼量水平x0*。
解：有题得：记f(x)=x(t)= rxln(N/x);F(x)=f(x)-h(x)= rxln(N/x)-Ex;
得在捕捞情况下渔场鱼量满足方程为：F(x),
令F(x)=0，得平衡点为：x0=N/exp(E/r);
F'(x)=rln(N/x)-r-E,
F'(x0)=-r<0,
所以x0点是稳定点，由上述可知，存在捕捞强度Em，使渔场鱼量稳定在x0*，从而获得最大持续产量hm=Em*x0*。
根据上述做出图，分析得：
当直线y=E*m与曲线y=f(x)在顶点p＊相交时可获得最大持续产量；
计算顶点：f'(x)=0　即rln(N/x)-r=0,所以x0*=N/e;
单位时间最大持续产量为：hm=rN/e;
又因为hm=Em*x0* ，所以Em=r。

阿尔芒 · 发表于 2004-1-9 06:32:08

浙江师范大学数学建模网

返回首页中国赛题美国赛题

--------------------------------------------------------------------------------

                  中国大学生数学建模赛题选
1997年 1998年 1999年

1997年全国大学生数学建模竞赛题目

A题零件的参数设计

一件产品由若干零件组装而成，标志产品性能的某个参数取决于这些零件的参数。零件参数包括标定值和容差两部分。进行成批生产时，标定值表示一批零件该参数的平均值，容差则给出了参数偏离其标定值的容许范围。若将零件参数视为随机变量，则标定值代表期望值，在生产部门无特殊要求时，容差通常规定为均方差的3 倍。进行零件参数设计，就是要确定其标定值和容差。这时要考虑两方面因素：一是当各零件组装成产品时，如果产品参数偏离预先设定的目标值，就会造成质量损失，偏离越大，损失越大；二是零件容差的大小决定了其制造成本，容差设计得越小，成本越高。试通过如下的具体问题给出一般的零件参数设计方法。

　

　

B题截断切割

某些工业部门（如贵重石材加工等）采用截断切割的加工方式。这里“截断切割”是指将物体沿某个切割平面分成两部分。从一个长方体中加工出一个已知尺寸、位置预定的长方体（这两个长方体的对应表面是平行的），通常要经过6次截断切割。设水平切割单位面积的费用是垂直切割单位面积费用的r 倍，且当先后两次垂直切割的平面(不管它们之间是否穿插水平切割)不平行时，因调整刀具需额外费用e。试为这些部门设计一种安排各面加工次序（称“切割方式”）的方法，使加工费用最少。（由工艺要求，与水平工作台接触的长方体底面是事先指定的）详细要求如下： 1）需考虑的不同切割方式的总数。2）给出上述问题的数学模型和求解方法。3）试对某部门用的如下准则作出评价：每次选择一个加工费用最少的待切割面进行切割。4）对于e = 0的情形有无简明的优化准则。5）用以下实例验证你的方法：待加工长方体和成品长方体的长、宽、高分别为10、14.5、 19和3、2、4，二者左侧面、正面、底面之间的距离分别为6、7、9（单位均为厘米）。垂直切割费用为每平方厘米1元，r和e的数据有以下4组： a. r =1, e = 0; b. r =1.5, e =0; c. r =8, e =0; d. r =1.5; 2 <= e <= 15. 对最后一组数据应给出所有最优解，并进行讨论。

　

1998年全国大学生数学建模竞赛题目

A题投资的收益和风险

市场上有n种资产（如股票、债券、…）Si ( i=1,…n) 供投资者选择，某公司有数额为M的一笔相当大的资金可用作一个时期的投资。公司财务分析人员对这n种资产进行了评估，估算出在这一时期内购买Si的平均收益率为ri，并预测出购买Si的风险损失率为qi。考虑到投资越分散，总的风险越小，公司确定，当用这笔资金购买若干种资产时，总体风险可用所投资的Si中最大的一个风险来度量。

购买Si要付交易费，费率为pi，并且当购买额不超过给定值ui时，交易费按购买ui计算（不买当然无须付费）。另外，假定同期银行存款利率是r0, 且既无交易费又无风险。（r0=5%）

已知n = 4时的相关数据如下： Si
ri(%)
qi(%)
pi(%)
ui(元)

S1
28
2.5
1
103

S2
21
1.5
2
198

S3
23
5.5
4.5
52

S4
25
2.6
6.5
40

试给该公司设计一种投资组合方案，即用给定的资金M，有选择地购买若干种资产或存银行生息，使净收益尽可能大，而总体风险尽可能小。

试就一般情况对以上问题进行讨论，并利用以下数据进行计算。
　

Si
ri(%)
qi(%)
pi(%)
ui(元)

S1
9.6
42
2.1
181

S2
18.5
54
3.2
407

S3
49.4
60
6.0
428

S4
23.9
42
1.5
549

S5
8.1
1.2
7.6
270

S6
14
39
3.4
397

S7
40.7
68
5.6
178

S8
31.2
33.4
3.1
220

S9
33.6
53.3
2.7
475

S10
36.8
40
2.9
248

S11
11.8
31
5.1
195

S12
9
5.5
5.7
320

S13
35
46
2.7
267

S14
9.4
5.3
4.5
328

S15
15
23
7.6
131

　

　

　

　

　

　

B题灾情巡视路线

下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。

今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。

若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。
假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。
在上述关于T , t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。
若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。

　

　

　

'99创维杯全国大学生数学建模竞赛题目

A题自动化车床管理

一道工序用自动化车床连续加工某种零件，由于刀具损坏等原因该工序会出现故障，其中刀具损坏故障占95%, 其它故障仅占5%。工序出现故障是完全随机的, 假定在生产任一零件时出现故障的机会均相同。工作人员通过检查零件来确定工序是否出现故障。现积累有100次刀具故障记录，故障出现时该刀具完成的零件数如附表。现计划在刀具加工一定件数后定期更换新刀具。

已知生产工序的费用参数如下：

故障时产出的零件损失费用 f=200元/件；

进行检查的费用 t=10元/次；

发现故障进行调节使恢复正常的平均费用 d=3000元/次(包括刀具费)；

未发现故障时更换一把新刀具的费用 k=1000元/次。

1)假定工序故障时产出的零件均为不合格品，正常时产出的零件均为合格品, 试对该工序设计效益最好的检查间隔（生产多少零件检查一次）和刀具更换策略。

2)如果该工序正常时产出的零件不全是合格品，有2%为不合格品；而工序故障时产出的零件有40%为合格品，60%为不合格品。工序正常而误认有故障仃机产生的损失费用为1500元/次。对该工序设计效益最好的检查间隔和刀具更换策略。

3）在2)的情况, 可否改进检查方式获得更高的效益。

　
附:100次刀具故障记录(完成的零件数)


459 362 624 542 509 584 433 748 815 505
612 452 434 982 640 742 565 706 593 680
926 653 164 487 734 608 428 593 844
527 552 513 781 474 388 824 538 862 659
775 859 755 649 697 515 628 954 771 609
402 960 885 610 292 837 473 677 358 638
699 634 555 570 84 416 606 1062 484 120
447 654 564 339 280 246 687 539 790 581
621 724 531 512 577 496 468 499 544 645
764 558 378 765 666 763 217 715 310 851

　

　

B题钻井布局

勘探部门在某地区找矿。初步勘探时期已零散地在若干位置上钻井，取得了地质资料。进入系统勘探时期后，要在一个区域内按纵横等距的网格点来布置井位，进行“撒网式”全面钻探。由于钻一口井的费用很高，如果新设计的井位与原有井位重合（或相当接近），便可利用旧井的地质资料，不必打这口新井。因此，应该尽量利用旧井，少打新井，以节约钻探费用。比如钻一口新井的费用为500万元，利用旧井资料的
费用为10万元，则利用一口旧井就节约费用490万元。

设平面上有n个点Pi，其坐标为(ai,bi),i=1,2,…,n，表示已有的n个井位。新布置的井位是一个正方形网格N的所有结点（所谓“正方形网格”是指每个格子都是正方形的网格；结点是指纵线和横线的交叉点）。假定每个格子的边长（井位的纵横间距）都是1单位（比如100米）。整个网格是可以在平面上任意移动的。若一个已知点Pi与某个网格结点Xi的距离不超过给定误差ε（=0.05单位），则认为Pi处的旧井资料可以利用，不必在结点Xi处打新井。

为进行辅助决策，勘探部门要求我们研究如下问题：

1)假定网格的横向和纵向是固定的（比如东西向和南北向），并规定两点间的距离为其横向距离（横坐标之差绝对值）及纵向距离（纵坐标之差绝对值）的最大值。在平面上平行移动网格N，使可利用的旧井数尽可能大。试提供数值计算方法，并对下面的数值例子用计算机进行计算。

2)在欧氏距离的误差意义下，考虑网格的横向和纵向不固定（可以旋转）的情形，给出算法及计算结果。

3)如果有n口旧井，给出判定这些井均可利用的条件和算法（你可以任意选定一种距离）。

数值例子n=12个点的坐标如下表所示：


i 1 2 3 4 5 6 7 8 9 10 11 12
ai  0.50 1.41 3.00 3.37 3.40 4.72 4.72 5.43 7.57 8.38 8.98 9.50
bi  2.00 3.50 1.50 3.51 5.50 2.00 6.24 4.10 2.01 4.50 3.41 0.80

　

　

　

'99创维杯全国大学生数学建模竞赛题目（大专组）

　

C题煤矸石堆积

煤矿采煤时，会产出无用废料煤矸石。在平原地区，煤矿不得不征用土地堆放矸石。通常矸石的堆积方法是：

架设一段与地面角度约为 β=25゜的直线形上升轨道（角度过大，运矸车无法装满），用在轨道上行驶的运矸车将矸石运到轨道顶端后向两侧倾倒，待矸石堆高后，再借助矸石堆延长轨道，这样逐渐堆起如下图所示的一座矸石山来。　　

现给出下列数据：

矸石自然堆放安息角（矸石自然堆积稳定后，其坡面与地面形成的夹角）α<=55゜；

矸石容重（碎矸石单位体积的重量）约2吨/米3；

运矸车所需电费为 0.50元/度（不变）；

运矸车机械效率（只考虑堆积坡道上的运输）初始值（在地平面上）约30%，坡道每延长10米，效率在原有基础上约下降2%；

土地征用费现值为8万元/亩，预计地价年涨幅约10%；

银行存、贷款利率均为5%；

煤矿设计原煤产量为300万吨/年；

煤矿设计寿命为20年；

采矿出矸率（矸石占全部采出的百分比）一般为7%～10%。

另外，为保护耕地，煤矿堆矸土地应比实际占地多征用10%。

现在煤矿设计中用于处理矸石的经费（只计征地费及堆积时运矸车用的电费）为100万元/年，这笔钱是否够用？试制订合理的年度征地计划，并对不同的出矸率预测处理矸石的最低费用。



D题钻井布局（同 B 题）

勘探部门在某地区找矿。初步勘探时期已零散地在若干位置上钻井，取得了地质资料。进入系统勘探时期后，要在一个区域内按纵横等距的网格点来布置井位，进行“撒网式”全面钻探。由于钻一口井的费用很高，如果新设计的井位与原有井位重合（或相当接近），便可利用旧井的地质资料，不必打这口新井。因此，应该尽量利用旧井，少打新井，以节约钻探费用。比如钻一口新井的费用为500万元，利用旧井资料的费用为10万元，则利用一口旧井就节约费用490万元。

设平面上有n个点Pi，其坐标为(ai,bi),i=1,2,…,n，表示已有的n个井位。新布置的井位是一个正方形网格N的所有结点（所谓“正方形网格”是指每个格子都是正方形的网格；结点是指纵线和横线的交叉点）。假定每个格子的边长（井位的纵横间距）都是1单位（比如100米）。整个网格是可以在平面上任意移动的。若一个已知点Pi与某个网格结点Xi的距离不超过给定误差ε（=0.05单位），则认为Pi处的旧井资料可以利用，不必在结点Xi处打新井。

为进行辅助决策，勘探部门要求我们研究如下问题：

1)假定网格的横向和纵向是固定的（比如东西向和南北向），并规定两点间的距离为其横向距离（横坐标之差绝对值）及纵向距离（纵坐标之差绝对值）的最大值。在平面上平行移动网格N，使可利用的旧井数尽可能大。试提供数值计算方法，并对下面的数值例子用计算机进行计算。

2)在欧氏距离的误差意义下，考虑网格的横向和纵向不固定（可以旋转）的情形，给出算法及计算结果。

3)如果有n口旧井，给出判定这些井均可利用的条件和算法（你可以任意选定一种距离）。


数值例子n=12个点的坐标如下表所示：


i 1 2 3 4 5 6 7 8 9 10 11 12
ai  0.50 1.41 3.00 3.37 3.40 4.72 4.72 5.43 7.57 88.38 8.98 9.50
bi  2.00 3.50 1.50 3.51 5.50 2.00 6.24 4.10 2.01 4.50 3.41 0.80

　

阿尔芒 · 发表于 2004-1-9 06:33:08

首页|留言

求网络的最小费用最大流
　
求网络的最小费用最大流，弧旁的数字是容量(运费)。

一．Ford和Fulkerson迭加算法.
基本思路：把各条弧上单位流量的费用看成某种长度,用求解最短路问题的方法确定一条自V1至Vn的最短路;在将这条最短路作为可扩充路,用求解最大流问题的方法将其上的流量增至最大可能值;而这条最短路上的流量增加后,其上各条弧的单位流量的费用要重新确定,如此多次迭代,最终得到最小费用最大流.
迭加算法：
1) 给定目标流量F或∞,给定最小费用的初始可行流{fij}=0
2) 若V(f)=F,停止,f为最小费用流;否则转(3).
3) 构造{fij} 相应的新的费用有向图W(fij),在W(fij)寻找Vs到Vt的最小费用有向路P(最短路),沿P增加流f的流量直到F,转(2);若不存在从Vs到Vt的最小费用的有向路P,停止.f就是最小费用最大流.
具体解题步骤：
设图中双线所示路径为最短路径，费用有向图为W（fij）．

在图(a)中给出零流 f,在图(b)中找到最小费用有向路,修改图(a)中的可行流,δ=min{4,3,5}=3,得图(c),再做出(c)的调整容量图,再构造相应的新的最小费用有向路得图(d), 修改图(c)中的可行流, δ=min{1,1,2,2}=1,得图(e),以此类推,一直得到图(h),在图(h)中以无最小费用有向路,停止,经计算:
图(h)中最小费用=1*4+3*3+2*4+4*1+1*1+4*2+1*1+3*1=38
图(g)中最大流=5
C语言程序如下(运行通过):
/*Ford和Fulkerson迭加算法*/
#include"stdio.h"
void main()
{int a,b,i,j,k,p,n,B[10][10],C[10][10],D[10][10],P[10][10][10];
printf("please input n:\n");
scanf("%d",&n);
printf("please input C[%d][%d],B[%d][%d]:\n",n,n,n,n);
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
scanf("%7d,%7d",&C[j],&B[j]); //输入各点(i,j)之间的容量C[j]和运费B[j]
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
{D[j]=B[j];
for(k=0;k<=n;k++)
P[j][k]=0;
if(D[j]<100) //注：100表示Vi到Vj之间无可行路
{P[j]=1[j][j]=1;}
}
for(k=0;k<=n;k++)
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
if(D[k]+D[k][j]<D[j])
{D[j]=D[k]+D[k][j];
for(p=0;p<=n;p++)
P[j][p]=P[k][p]||P[k][j][p];
} //调用FLOYD算法
printf("D[%d][%d]:\n",n,n);
for(i=0;i<=n;i++)
{for(j=0;j<=n;j++)
printf("%7d",D[j]);
printf("\n");
} //由表D中的数值确定V0到V5的最短路
a=C[1][3];b=B[1][3]*D[0][5];
printf("a=%d,b=%d\n",a,b);
B[1][3]=100; //将容量已满的路改为不可行路
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
{D[j]=B[j];
for(k=0;k<=n;k++)
P[j][k]=0;
if(D[j]<100)
{P[j]=1[j][j]=1;}
}
for(k=0;k<=n;k++)
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
if(D[k]+D[k][j]<D[j])
{D[j]=D[k]+D[k][j];
for(p=0;p<=n;p++)
P[j][p]=P[k][p]||P[k][j][p];
} //调用FLOYD算法
printf("D[%d][%d]:\n",n,n);
for(i=0;i<=n;i++)
{for(j=0;j<=n;j++)
printf("%7d",D[j]);
printf("\n");
} //由表D中的数值确定V0到V5的新最短路
a=a+C[1][2];b=b+D[0][5];
printf("a=%d,b=%d\n",a,b);
B[0][1]=100;B[1][2]=100;B[4][3]=100; //将容量已满的路改为不可行路
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
{D[j]=B[j];
for(k=0;k<=n;k++)
P[j][k]=0;
if(D[j]<100)
{P[j]=1[j][j]=1;}
}
for(k=0;k<=n;k++)
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
if(D[k]+D[k][j]<D[j])
{D[j]=D[k]+D[k][j];
for(p=0;p<=n;p++)
P[j][p]=P[k][p]||P[k][j][p];
} //调用FLOYD算法
printf("D[%d][%d]:\n",n,n);
for(i=0;i<=n;i++)
{for(j=0;j<=n;j++)
printf("%7d",D[j]);
printf("\n");
} //由表D中的数值确定V0到V5的新最短路
a=a+C[2][4]-C[4][3];b=b+D[0][5];
printf("a=%d,b=%d\n",a,b);
B[2][4]=100; //将容量已满的路改为不可行路
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
{D[j]=B[j];
for(k=0;k<=n;k++)
P[j][k]=0;
if(D[j]<100)
{P[j]=1;P[j][j]=1;}
}
for(k=0;k<=n;k++)
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
if(D[k]+D[k][j]<D[j])
{D[j]=D[k]+D[k][j];
for(p=0;p<=n;p++)
P[j][p]=P[k][p]||P[k][j][p];
} //调用FLOYD算法
printf("D[%d][%d]:\n",n,n);
for(i=0;i<=n;i++)
{for(j=0;j<=n;j++)
printf("%7d",D[j]);
printf("\n");
} //检验有无V0到V5的新最短路
}

运行结果:
please input n:
5
please input C[5][5],B[5][5]:
0,0 4,1 5,3 0,100 0,100 0,100
0,100 0,0 1,1 3,3 0,100 0,100
0,100 0,100 0,0 0,100 2,4 0,100
0,100 0,100 0,100 0,0 0,100 5,2
0,100 0,100 0,100 1,1 0,0 2,4
0,100 0,100 0,100 0,100 0,100 0,0
D[5][5]:
0 1 2 4 6 6
100 0 1 3 5 5
100 100 0 5 4 7
100 100 100 0 100 2
100 100 100 1 0 3
100 100 100 100 100 0
a=3,b=18
D[5][5]:
0 1 2 7 6 9
100 0 1 6 5 8
100 100 0 5 4 7
100 100 100 0 100 2
100 100 100 1 0 3
100 100 100 100 100 0
a=4,b=27
D[5][5]:
0 100 3 100 7 11
100 0 100 100 100 100
100 100 0 100 4 8
100 100 100 0 100 2
100 100 100 100 0 4
100 100 100 100 100 0
a=5,b=38
D[5][5]:
0 100 3 100 100 100
100 0 100 100 100 100
100 100 0 100 100 100
100 100 100 0 100 2
100 100 100 100 0 4
100 100 100 100 100 0
//注：100表示Vi到Vj之间无可行路

二．圈算法：
1) 利用Ford和Fulkson标号算法找出流量为F(<=最大流)的流f.
2) 构造f对应的调整容量的流网络N'(f).
3) 搜索N'(f)中的负费用有向图C(Floyd算法),若没有则停止,否则转(4).
4) 在C上找出最大的循环流,并加到N上去,同时修改N'(F)中C的容量,转(3).
具体解题步骤:

利用Ford和Fulkson标号算法,得网络的最大流F=5,见图(a),由图(a)构造相应的调整容量的流网络(b),图(b)中不存在负费用有向图,故停止．经计算:
图(b)中最小费用= 4*1+3*1+1*1+3*3+4*2+1*1+4*1+2*4=38
图(a)中最大流为F=5

C语言程序如下(运行通过):
/*圈算法*/
#include"stdio.h"
int min(int x,int y)
{if(x<y) return(x);
else return(y);
}
void main()
{int a=0,b=0,i,j,k,p,n,t,A[10][10],P[10][10],B[10][10],C[10][10],D[10][10];
printf("please input n:\n");
scanf("%d",&n);
printf("please input C[%d][%d],B[%d][%d]:\n",n,n,n,n);
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
scanf("%7d,%7d",&C[j],&B[j]); //输入各点(i,j)之间的容量C[j]和运费B[j]
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
{A[j]=C[j];D[j]=0;P[j]=B[j];}
for(i=n;i>1;i--)
for(j=i-1;j>0;j--)
for(k=j-1;k>=0;k--)
if(A[j]!=0&&A[k][j]!=0)
D[k][j]=min(A[j],A[k][j]);
printf("D[%d][%d]:\n",n,n);
for(i=0;i<=n;i++)
{for(j=0;j<=n;j++)
printf("%7d",D[j]);
printf("\n");
}
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
for(k=j+1;k<=n;k++)
if(D[j]!=0&&D[j][k]!=0)
if(D[j]+D[j][k]==C[j])
{A[j]=0;A[j][k]=0;A[j-i][k-j]=0;
P[j]=100;P[j][k]=100;P[j-i][k-j]=0;
a=a+C[j];
b=b+B[j]*C[j]+B[j][k]*C[j][k]+B[j-i][k-j]*C[j-i][k-j];
for(p=k+1;p<=n;p++)
if(C[j]<C[k][p])
{b=b+B[k][p]*C[j];
A[k][p]=C[k][p]-C[j];
}
for(p=k-j+1;p<=n;p++)
if(C[j-i][k-j]<C[k-j][p])
{b=b+B[k-j][p]*C[j-i][k-j]+B[4][3]*C[4][3];
A[k-j][p]=C[k-j][p]-C[j-i][k-j];
}
A[4][3]=0;
}
printf("a=%d,b=%d\n",a,b);
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
D[j]=0;
for(i=n;i>1;i--)
for(j=i-1;j>0;j--)
for(k=j-1;k>=0;k--)
if(A[j]!=0&&A[k][j]!=0)
D[k][j]=min(A[j],A[k][j]);
printf("D[%d][%d]:\n",n,n);
for(i=0;i<=n;i++)
{for(j=0;j<=n;j++)
printf("%7d",D[j]);
printf("\n");
}
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
for(k=j+1;k<=n;k++)
if(D[j]!=0&&D[j][k]!=0)
if(D[j]==D[j][k])
for(p=k+1;p<=n;p++)
{t=min(min(A[j],A[j][k]),min(A[j][k],A[k][p]));
a=a+t;
b=b+t*(B[j]+B[j][k]+B[k][p]);
}
printf("a=%d,b=%d\n",a,b);
}

运行结果:
please input n:
5
please input C[5][5],B[5][5]:
0,0 4,1 5,3 0,100 0,100 0,100
0,100 0,0 1,1 3,3 0,100 0,100
0,100 0,100 0,0 0,100 2,4 0,100
0,100 0,100 0,100 0,0 0,100 5,2
0,100 0,100 0,100 1,1 0,0 2,4
0,100 0,100 0,100 0,100 0,100 0,0
D[5][5]:
0 1 2 0 0 0
0 0 1 3 0 0
0 0 0 0 2 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
a=4,b=27
D[5][5]:
0 0 1 0 0 0
0 0 0 0 0 0
0 0 0 0 1 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
a=5,b=38
//注：100表示Vi到Vj之间无可行路

阿尔芒 · 发表于 2004-1-9 06:52:27

                  最小二乘法
设（x 1, y 1 ), (x 2, y 2), …, (x n, y n)是直角平面坐标系下给出的一组数据，若x 1<x 2<…<x n,我们也可以把这组数据看作是一个离散的函数。根据观察，如果这组数据图象“很象”一条直线（不是直线），我们的问题是确定一条直线y = bx +a ,使得它能"最好"的反映出这组数据的变化。
对个别观察值来说，它可能是正的，也可能是负的。为了不使它们相加彼此抵消，故"最好"应该是

                     Mathematical  Modeling
                  最小二乘法
设（x 1, y 1 ), (x 2, y 2), …, (x n, y n)是直角平面坐标系下给出的一组数据，若x 1<x 2<…<x n,我们也可以把这组数据看作是一个离散的函数。根据观察，如果这组数据图象“很象”一条直线（不是直线），我们的问题是确定一条直线y = bx +a ,使得它能"最好"的反映出这组数据的变化。
对个别观察值来说，它可能是正的，也可能是负的。为了不使它们相加彼此抵消，故"最好"应该是

                     Mathematical  Modeling

albert-estan · 发表于 2004-1-9 07:19:26

首页|留言

求网络的最小费用最大流
　
求网络的最小费用最大流，弧旁的数字是容量(运费)。

一．Ford和Fulkerson迭加算法.
基本思路：把各条弧上单位流量的费用看成某种长度,用求解最短路问题的方法确定一条自V1至Vn的最短路;在将这条最短路作为可扩充路,用求解最大流问题的方法将其上的流量增至最大可能值;而这条最短路上的流量增加后,其上各条弧的单位流量的费用要重新确定,如此多次迭代,最终得到最小费用最大流.
迭加算法：
1) 给定目标流量F或∞,给定最小费用的初始可行流{fij}=0
2) 若V(f)=F,停止,f为最小费用流;否则转(3).
3) 构造{fij} 相应的新的费用有向图W(fij),在W(fij)寻找Vs到Vt的最小费用有向路P(最短路),沿P增加流f的流量直到F,转(2);若不存在从Vs到Vt的最小费用的有向路P,停止.f就是最小费用最大流.
具体解题步骤：
设图中双线所示路径为最短路径，费用有向图为W（fij）．

在图(a)中给出零流 f,在图(b)中找到最小费用有向路,修改图(a)中的可行流,δ=min{4,3,5}=3,得图(c),再做出(c)的调整容量图,再构造相应的新的最小费用有向路得图(d), 修改图(c)中的可行流, δ=min{1,1,2,2}=1,得图(e),以此类推,一直得到图(h),在图(h)中以无最小费用有向路,停止,经计算:
图(h)中最小费用=1*4+3*3+2*4+4*1+1*1+4*2+1*1+3*1=38
图(g)中最大流=5
C语言程序如下(运行通过):
/*Ford和Fulkerson迭加算法*/
#include"stdio.h"
void main()
{int a,b,i,j,k,p,n,B[10][10],C[10][10],D[10][10],P[10][10][10];
printf("please input n:\n");
scanf("%d",&n);
printf("please input C[%d][%d],B[%d][%d]:\n",n,n,n,n);
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
scanf("%7d,%7d",&C[j],&B[j]); //输入各点(i,j)之间的容量C[j]和运费B[j]
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
{D[j]=B[j];
for(k=0;k<=n;k++)
P[j][k]=0;
if(D[j]<100) //注：100表示Vi到Vj之间无可行路
{P[j]=1[j][j]=1;}
}
for(k=0;k<=n;k++)
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
if(D[k]+D[k][j]<D[j])
{D[j]=D[k]+D[k][j];
for(p=0;p<=n;p++)
P[j][p]=P[k][p]||P[k][j][p];
} //调用FLOYD算法
printf("D[%d][%d]:\n",n,n);
for(i=0;i<=n;i++)
{for(j=0;j<=n;j++)
printf("%7d",D[j]);
printf("\n");
} //由表D中的数值确定V0到V5的最短路
a=C[1][3];b=B[1][3]*D[0][5];
printf("a=%d,b=%d\n",a,b);
B[1][3]=100; //将容量已满的路改为不可行路
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
{D[j]=B[j];
for(k=0;k<=n;k++)
P[j][k]=0;
if(D[j]<100)
{P[j]=1[j][j]=1;}
}
for(k=0;k<=n;k++)
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
if(D[k]+D[k][j]<D[j])
{D[j]=D[k]+D[k][j];
for(p=0;p<=n;p++)
P[j][p]=P[k][p]||P[k][j][p];
} //调用FLOYD算法
printf("D[%d][%d]:\n",n,n);
for(i=0;i<=n;i++)
{for(j=0;j<=n;j++)
printf("%7d",D[j]);
printf("\n");
} //由表D中的数值确定V0到V5的新最短路
a=a+C[1][2];b=b+D[0][5];
printf("a=%d,b=%d\n",a,b);
B[0][1]=100;B[1][2]=100;B[4][3]=100; //将容量已满的路改为不可行路
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
{D[j]=B[j];
for(k=0;k<=n;k++)
P[j][k]=0;
if(D[j]<100)
{P[j]=1[j][j]=1;}
}
for(k=0;k<=n;k++)
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
if(D[k]+D[k][j]<D[j])
{D[j]=D[k]+D[k][j];
for(p=0;p<=n;p++)
P[j][p]=P[k][p]||P[k][j][p];
} //调用FLOYD算法
printf("D[%d][%d]:\n",n,n);
for(i=0;i<=n;i++)
{for(j=0;j<=n;j++)
printf("%7d",D[j]);
printf("\n");
} //由表D中的数值确定V0到V5的新最短路
a=a+C[2][4]-C[4][3];b=b+D[0][5];
printf("a=%d,b=%d\n",a,b);
B[2][4]=100; //将容量已满的路改为不可行路
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
{D[j]=B[j];
for(k=0;k<=n;k++)
P[j][k]=0;
if(D[j]<100)
{P[j]=1;P[j][j]=1;}
}
for(k=0;k<=n;k++)
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
if(D[k]+D[k][j]<D[j])
{D[j]=D[k]+D[k][j];
for(p=0;p<=n;p++)
P[j][p]=P[k][p]||P[k][j][p];
} //调用FLOYD算法
printf("D[%d][%d]:\n",n,n);
for(i=0;i<=n;i++)
{for(j=0;j<=n;j++)
printf("%7d",D[j]);
printf("\n");
} //检验有无V0到V5的新最短路
}

运行结果:
please input n:
5
please input C[5][5],B[5][5]:
0,0 4,1 5,3 0,100 0,100 0,100
0,100 0,0 1,1 3,3 0,100 0,100
0,100 0,100 0,0 0,100 2,4 0,100
0,100 0,100 0,100 0,0 0,100 5,2
0,100 0,100 0,100 1,1 0,0 2,4
0,100 0,100 0,100 0,100 0,100 0,0
D[5][5]:
0 1 2 4 6 6
100 0 1 3 5 5
100 100 0 5 4 7
100 100 100 0 100 2
100 100 100 1 0 3
100 100 100 100 100 0
a=3,b=18
D[5][5]:
0 1 2 7 6 9
100 0 1 6 5 8
100 100 0 5 4 7
100 100 100 0 100 2
100 100 100 1 0 3
100 100 100 100 100 0
a=4,b=27
D[5][5]:
0 100 3 100 7 11
100 0 100 100 100 100
100 100 0 100 4 8
100 100 100 0 100 2
100 100 100 100 0 4
100 100 100 100 100 0
a=5,b=38
D[5][5]:
0 100 3 100 100 100
100 0 100 100 100 100
100 100 0 100 100 100
100 100 100 0 100 2
100 100 100 100 0 4
100 100 100 100 100 0
//注：100表示Vi到Vj之间无可行路

二．圈算法：
1) 利用Ford和Fulkson标号算法找出流量为F(<=最大流)的流f.
2) 构造f对应的调整容量的流网络N'(f).
3) 搜索N'(f)中的负费用有向图C(Floyd算法),若没有则停止,否则转(4).
4) 在C上找出最大的循环流,并加到N上去,同时修改N'(F)中C的容量,转(3).
具体解题步骤:

利用Ford和Fulkson标号算法,得网络的最大流F=5,见图(a),由图(a)构造相应的调整容量的流网络(b),图(b)中不存在负费用有向图,故停止．经计算:
图(b)中最小费用= 4*1+3*1+1*1+3*3+4*2+1*1+4*1+2*4=38
图(a)中最大流为F=5

C语言程序如下(运行通过):
/*圈算法*/
#include"stdio.h"
int min(int x,int y)
{if(x<y) return(x);
else return(y);
}
void main()
{int a=0,b=0,i,j,k,p,n,t,A[10][10],P[10][10],B[10][10],C[10][10],D[10][10];
printf("please input n:\n");
scanf("%d",&n);
printf("please input C[%d][%d],B[%d][%d]:\n",n,n,n,n);
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
scanf("%7d,%7d",&C[j],&B[j]); //输入各点(i,j)之间的容量C[j]和运费B[j]
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
{A[j]=C[j];D[j]=0;P[j]=B[j];}
for(i=n;i>1;i--)
for(j=i-1;j>0;j--)
for(k=j-1;k>=0;k--)
if(A[j]!=0&&A[k][j]!=0)
D[k][j]=min(A[j],A[k][j]);
printf("D[%d][%d]:\n",n,n);
for(i=0;i<=n;i++)
{for(j=0;j<=n;j++)
printf("%7d",D[j]);
printf("\n");
}
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
for(k=j+1;k<=n;k++)
if(D[j]!=0&&D[j][k]!=0)
if(D[j]+D[j][k]==C[j])
{A[j]=0;A[j][k]=0;A[j-i][k-j]=0;
P[j]=100;P[j][k]=100;P[j-i][k-j]=0;
a=a+C[j];
b=b+B[j]*C[j]+B[j][k]*C[j][k]+B[j-i][k-j]*C[j-i][k-j];
for(p=k+1;p<=n;p++)
if(C[j]<C[k][p])
{b=b+B[k][p]*C[j];
A[k][p]=C[k][p]-C[j];
}
for(p=k-j+1;p<=n;p++)
if(C[j-i][k-j]<C[k-j][p])
{b=b+B[k-j][p]*C[j-i][k-j]+B[4][3]*C[4][3];
A[k-j][p]=C[k-j][p]-C[j-i][k-j];
}
A[4][3]=0;
}
printf("a=%d,b=%d\n",a,b);
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
D[j]=0;
for(i=n;i>1;i--)
for(j=i-1;j>0;j--)
for(k=j-1;k>=0;k--)
if(A[j]!=0&&A[k][j]!=0)
D[k][j]=min(A[j],A[k][j]);
printf("D[%d][%d]:\n",n,n);
for(i=0;i<=n;i++)
{for(j=0;j<=n;j++)
printf("%7d",D[j]);
printf("\n");
}
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
for(k=j+1;k<=n;k++)
if(D[j]!=0&&D[j][k]!=0)
if(D[j]==D[j][k])
for(p=k+1;p<=n;p++)
{t=min(min(A[j],A[j][k]),min(A[j][k],A[k][p]));
a=a+t;
b=b+t*(B[j]+B[j][k]+B[k][p]);
}
printf("a=%d,b=%d\n",a,b);
}

运行结果:
please input n:
5
please input C[5][5],B[5][5]:
0,0 4,1 5,3 0,100 0,100 0,100
0,100 0,0 1,1 3,3 0,100 0,100
0,100 0,100 0,0 0,100 2,4 0,100
0,100 0,100 0,100 0,0 0,100 5,2
0,100 0,100 0,100 1,1 0,0 2,4
0,100 0,100 0,100 0,100 0,100 0,0
D[5][5]:
0 1 2 0 0 0
0 0 1 3 0 0
0 0 0 0 2 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
a=4,b=27
D[5][5]:
0 0 1 0 0 0
0 0 0 0 0 0
0 0 0 0 1 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
a=5,b=38
//注：100表示Vi到Vj之间无可行路

wuxinbin · 发表于 2004-1-13 19:25:49

大家好！希望大家多多指教！！谢谢！！

		自动登录	找回密码
密码			注-册-帐-号