运筹学模型

发布 2022-09-15 09:47:28 阅读 6223

运筹学发展至今已有五十多年的历史,其作用是为决策者在作决策时提供科学依据。运筹学在生产管理、工程技术、军事科学、科学试验、经济和社会科学中都有着极其广泛的应用。

运筹学的分支很多,我们只介绍数学建模中常见的:线性规划、非线性规划、库存、决策、对策和动态规划等几个方面的几个数学模型。

第一节线性规划问题的数学模型。

在生产管理、工程投术、交通运输以及工商**等各项经济活动中,都有提高经济效益,做到耗费较少的人力物力,创造出较多经济效益的问题。

提高经济效益可以通过两种途径:一种是技术方面的各种改进,改革生产工艺,使用新设备和新材料等。另一种是改进计划和生产管理安排,合理安排人力物力,合理组织生产过程,在条件不变的情况下,统筹安排,使总的经济效益最好。

后者就是运筹学研究的主要内容。

线性规划是运筹学中研究较早、发展较快、应用较广、比较成熟的一个分支。它研究的问题主要有两类:一类是当一项任务确定后,如何统筹安排,尽量做到用最少的人力物力资源去完成这一任务。

二是已有一定数量的人力物力资源,如何安排使用它们,使得完成任务最多。其实这两类问题是一个问题的两个方面,就是所谓寻求整个问题的某个整体指标最优的问题。在经济领域中,这类问题特别多。

一) 运输问题。

在某个区域内,有某种产品的产地与销地若干个,把这种产品从各个产地调运到各个销地,调运方案可以很多,应如何组织调运,才能使总的费用或运输量(即总的运行吨公里数)最少。

二) 生产的组织与计划问题。

一个工厂或车间有各种不同类型的车床各若干台,各种不同类型车床生产各种零件的效率不同,在一个生产周期,应如何安排各车床的生产时间,使得成套的产品总量最大。类似的还有劳动力的安排问题。

三) 合理下料问题。

在加工中需要将某种条材或板材下不同规格的毛坯,各种毛坯的数量也可能不同,应如何选取合适的裁法,使毛坯数量符合要求,并且使总料头最少(即所用原材料最少)。

四) 配料问题。

在食品、化工、冶炼等企业,常常用几种原料,制成达到含有一定成分的产品,而这些不同原料**不同,应如何决定配料的方案,才能使生产的产品所含成分合乎要求,而产品的成本最低。

五) 布局问题。

各种农作物在不同土壤上单位面积产量不一样,如何合理安排各种作物在各种不同土壤上的种植面积,达到因地制宜,在完成种植计划的前提下,使总产量最多。这是作物布局问题。将某几个地方出产的原料,集中到某几个地方加工成成品,然后再运到某几个成品需要地。

有些地方可能既是原料出产地,又是成品需要地,也是成品加工地。因各地间运费不同,产品加工费不同,设厂条件不同,应在什么地方设厂,规模多大,才能满足成品需要地的需要,又使费用(包括运费、加工费)最低。这是工厂布局问题。

六) 分派问题。

n件工作给n个人去做,而各人对做各种工作的效率不同,问应如何合理分派,才能使完成全部工作的总工时最少。类似的问题还有作物的种植安排、机床加工零件任务的分配问题等。

在经济领域运用数学方法作为分析经济活动、提高经济效益的一种手段是当今经济管理工作不可忽缺的重要工具。线性规划在这方面有着独特的作用。早在20世纪30年代末40年代初,康托洛维奇和希奇柯克(hitchcock)等在生产组织和运输问题等方面就开始研究应用线性规这一数学方法;后来,在40年代末又由旦次基(dantzig)等人提出了单纯形方法并从理论上给线性规划奠定了基础。

我国也在建国初期就开始应用线性规划的方法。如东北的一个物资调运小组,就创造了一个物资调运的图上作业法;并经过中国科学院数学研究所的同志给予理论上证明,在全国推广应用,成效显著,对我国交通运输工作作出了重大贡献。随着电子计算机的不断发展,计算能力的大大提高,使这一数学方法在经济活动中不仅提供了可能,而且迅速发展。

2023年国际水平只能解约束条件为10个方程的线性规划问题,到了2023年就能解1000-10000个方程的线性规划问题了。另一面,从时间上看,解一个67个方程的线性规划问题,2023年要一个小时,到2023年只要28秒钟。现在,不但解题规模大,速度快。

而且有专用的软件。以下介绍几个典型的实际问题。

一) 运输问题。

设有两个砖厂a1、a2。其产量分别为23万块和27万块。它们生产的砖**b1、b2、b3三个工地。

其需要量分别为17万块、18万块和15万块。而各自产地到各工地的运价列表如下(见表1-1):

表1-1应如何调运,才使总费用最省?

解设表示由砖厂运往工地砖的数量(单位:万块, i=1,2;j=1,2,3),例如表示由砖厂a1运往工地b1砖的数量等等。现列表如下(见表1-2)

表1-2因为由砖厂a1运往三个工地砖的总数应为a1的产量23万块,即:

同样由砖厂a2运往三个工地砖的总数应为a2的产量27万块,即:

另一方面,两个砖厂运往b1工地的砖的数量应等于b1的需要量17万块,即:

同理可得:因此,调运方案就是满足下面约束条件的一组变量的值;

约束条件 显然,可行的方案有很多个。现在的问题是要在这很多个方案中,找一个运费最小的方案,即:

求一组变量的值,使它满足。

约束条件 并使目标函数。

的值最小(即总运费最少)

一般地,设某种物资有m个产地:a1, a2,…,am, 联合**n个销地:b1, b2,…bn。

各产地产量 (单位:吨),各销地销量 (单位:吨),各产地至销地单位运价 (单位:

元/吨)如表1-3所示:

表1-3表中:表示产地的产量 (i=1,2,…,m);

表示销地的销量 (j=1,2,…n);

表示间的单位运价 (元/吨) (i=1,2,…m;j=1,2,…,n)。

向应如何调运,才使总运费最少?

解假定产销平衡 (即)。设表示由产地运往销地的物资数(i=1,2,…,m;j=1,2,…,n)。那么,上述运输问题的数学模型为:

求一组变量 (i=1,2,…,m;j=1,2,…,n)的值使它满足。

约束条件 并使目标函数的值最小。

如果运输问题中,没有产销平衡这一限制,当产大于销时(即),这一问题的数学模型应为:

求一组变量 (i=1,2,…,m;j=1,2,…,n)的值,使它满足:

约束条件 并且使目标函数的值最小。

二) 布局问题。

作物布局问题,某生产队要在n块地上,种值 m种作物。各块土地亩数、各种作物计划播种面积及各种作物在各块地上的单产(每亩的产量)如表1-4所示,问应如何合理安排种植计划,才使总产量最多。

这里假定 (即计划播种总面积等于土地面积)。

表1-4 表中:表示作物的播种面积 (i=1,2,…,m);

表示土地的亩数 (j=1,2,…,n);

表示在土地上种植作物的单产数 (i=1,2,…,m;j=1,2,…,n)。

解设为土地种植作物的亩数i=1,2,…,m;j=1,2,…,n),那么作物布局问题的数学模型为:

求一组变量(i=1,2,,m;j=1,2,…,n)的值,使它满足。

约束条件。并使目标函数的值最大。(总产量最多)

这一数学模型和前面运输问题的数学模型相同。具有这杆数学模型的问题还有机床加工零件的问题等。我们称这类问题为康-希问题,或统称为运输问题。

(三) 分派问题。

设有n件工作分派给n个人去做,每人只做一件工作且每件工作只分派一人去做。设完成的工时为 (i,j=1,2,…,n)。问应如何分派才使完成全部工作的总工时最少。

解设为分派给的情况:分派给时,=1;不分派给时=0(i,j=1,2,…,n)。那末这一问题的数学模型为:

求一组变量 (i,j=1,2,…,n)的值,使它满足。

约束条件 并且使目标函数的值最小。

(完成全部工作的总工时最少)

分派问题是运输问题的特例。因为变量只取0和1,所以又称它为0-1规划问题。

(四) 生产组织与计划问题。

设用种原料,可以生产种产品。现有原料数、每单位产品所需原料数,及每单位产品可得利润数如表1-5所示。问应如何组织生产才能使利润最大?

表1-5解设为生产产品 (j=1,2,…,n) 的计划数。这一问题的数学模型为:

求一组变量 (j=1,2,…,n)的值,使它满足。

约束条件 并且使目标函数的值最大(总利润最多)。

五) 合理下料问题。

设用某原材料(条材或板材)下零件的毛坯。根据过去经验在一件原材料上有种不同的下料方式,每种下料方式可得各种毛坯个数及每种零件需要量如表1-6所示。问应怎样安排下料方式,使得既能满足需要,用的原材料又最少。

运筹学模型

第5章运筹学模型。5.2 图论模型。图论是运筹学的一个重要分支,它是建立和处理离散类数学模型的一个重要工具。用图论的方法往往能帮助人们解决一些用其它方法难于解决的问题。图论的发展可以追溯到1736年欧拉所发表的一篇关于解决著名的 哥尼斯堡七桥问题 的 由于这种数学模型和方法直观形象,富有启发性和趣味...

运筹学模型

源于第二次世界大战期间的运筹学研究,有效地解决了如何将有限的资源分配于各项军事活动,以取得最优的战争效果等重大军事决策问题,为盟军取得二战的胜利作出了不可磨灭的贡献。战后,该项技术不但在军事科学上不断发展,在工农业生产 科学实验 工程技术 经济管理和社会科学中都有着广泛的应用和发展。特别是计算机技术...

数学建模运筹学模型一

运筹学模型 一 本章重点 线性规划基础模型 目标规划模型 运输模型及其应用 图论模型 最小树问题 最短路问题。复习要求 1.进一步理解基本建模过程,掌握类比法 图示法以及问题分析 合理假设的内涵。2.进一步理解数学模型的作用与特点。本章复习重点是线性规划基础模型 运输问题模型和目标规划模型。具体说来...