用数学建模方法解决哥尼斯堡七桥问题.pdfVIP

用数学建模方法解决哥尼斯堡七桥问题

篇一：数学建模方法的应用

数学建模方法的应用

应用数学***

（广东惠州学院数学系****，广东惠州516007）

（E-mail:*******@）

摘要:数学建模是培养学生应用数学能力,培养学生的创造性的一种重要手段,介绍

了数

学建模的基本概念,并通过实例说明数学建模的过程。关键词：LP；IP；拉格朗日多

项式插值

把数学应用到任何一个实际问题中去,都需要把这个问题的内在规律运用数字、图表、

公式、符号表示出来,经过数学的处理,得出供人们作出分析预报、决策或者控制的定量结

果,这个过程就是人们常说的建立数学模型。

一线性规划

在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济效

益的问题。此类问题构成了运筹学的一个重要分支—数学规划，而线性规划

(LinearProgramming简记LP)则是数学规划的一个重要分支。自从1947年G.B.Dantzig提出

求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在实用中日益广泛与深入。

特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适

用领域更为广泛了，已成为现代管理中经常采用的基本方法之一。

例某公司有6个建筑工地要开工，每个工地的位置（用平面坐标x，y表示，距离单位：

km)及水泥日用量d(t)由下表给出.目前有两个临时料场位于A（5，1），B（2，7），日储量各

有20t.假设从料场到工地之间均有直线道路相连，试制定每天的供应计划，即从A，B两料

场分别向各工地运送多少吨水泥，使总的吨公

?x,y?a,b水泥日用量为

模型记工地的位置为ii，；料场位置为jj，

ec

日储量为j（j=1，2，分别表示A，B），从料场j向工地i的运送量为ij，这个优化问题

的目标函数（总吨公里数）可表示为

j?1i?1

（1）个工地的日用量必须满足，所以

di(i?1,2,...,6)

minf???cij(xj?ai)2?(yj?bi)2

2

26

j?1，i=1,2,...,6（2）各料场的运送量不能超过日储量，所以

?c

ij

?dij

i?1（3）问题归结为在约束（2），（3）及决策变量非负的条件下，使（1）式最小.决策

变

c

量只有ij，所以这是线性规划模型.

?c

6

ij

?eij,j?1,2

二、整数规划

规划中的变量（部分或全部）限制为整数时，称为整数规划（IP）。若在线性规划模型

中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适

用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。

（一）整数规划的分类如不加特殊说明，一般指整数线性规划。对于整数线性规划模

型大致可分为两类：1、变量全限制为整数时，称纯（完全）整数规划。2、变量部分限

制为整数的，称混合整数规划。整数规划特点

原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况：

①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。

②整数规划无可行解。

例求解如下IP模型：

minz?5x1?8x2s.t.x1?x2?6

5x1?9x2?45

x1,x2?0且为整数.解模型去掉整数限制后记作LP，其可行域为图中由点（0，0），（6，

0），P（2.25，

z?zmax

3.75），（0，5）围成的四边形，过P点的等值线（图中虚线）为，最优解在P点取得.

图中小圆点为整数点，四边形中的小圆点才是IP的可行解.将P点舍入成整数或者找最靠近

它的整数，都得不到IP的最优解.经在可行解中试探、比较得到下表:表

可见IP最优解不一定能从LP经过简单的“移动”得到.求解整数规划没有统一的有效方

法，不同方法的效果与问题的性质有很大关系.