动态规划问题的知识化数学模型生成器研究_胡祥培

Vol 118,No 12

管 理 工 程 学 报

Journal of Industrial Engineering P Engineering Management

2004年第2期

动态规划问题的知识化数学模型生成器研究

胡祥培1

王旭茵1

刘伟国1

,胡运权2

,钱国明

2

(1.大连理工大学系统工程研究所,辽宁大连116023;21哈尔滨工业大学管理学院,黑龙江哈尔滨150001)

摘要:针对计算机自动生成动态规划模型这一难题,研究了动态规划问题及其模型的知识表示以及相应的知识化信息模型和知识化数学模型,运用积木式建模方法提出了动态规划问题知识化数学模型生成器的结构及其工作原理,并在微机上实现了一个投资决策问题的建模过程。本项研究为运筹学模型的自动建模开辟了途径。

关键词:运筹学;动态规划;模型生成器;知识表示;积木式建模

中图分类号:F22413 文献标识码:A 文章编号:1004-6062(2004)02-0064-07

收稿日期:2003-02-20

基金项目:国家自然科学基金(70171040、79770022和79400006);高等学校博士点基金(20010141025);辽宁省自然科学基金(2001101074);教育部/高等学校骨干教师资助计划0;中国博士后基金(第20批)资助项目

作者简介:胡祥培(1962)),博士后,教授,博导,大连理工大学管理学院副院长兼系统工程研究所副所长。

0 引言

动态规划是运筹学的一个重要分枝,为了使计算机在运筹学问题建模与求解模型中能够实现基于知识的推理机制,近年来国内外学者已经把人工智能理论运用于解决运筹学实际应用问题,开展了运筹学的知识化与智能化研究,这是一个很有发展前途的研究方向。运筹学应用问题的知识表示与基于知识的模型生成方法研究是运筹学应用研究的前沿课题,也是决策支持系统(DSS)领域关注的问题。该项研究主要涉及三个关键问题:1实际应用问题的知识表示;o数学模型的知识表示;?基于知识的模型生成方法与建模支持。

对于第一问题,具有代表性的学术观点和方法有:T.P.Liang [1]提出的以实体(entity ))))属性(attribute))))子属性(subattribute)所构成的层次化体系表示问题的方法、汪时萍[2]等人提出的基于语义模型的问题描述语言SM -IPDL 等[11,12],作者在此基础上提出运筹学问题的一种基于知识的树状表示法[3],并由此形成实际问题的知识化信息模型。这一方法在问题可辨识性、问题描述结构的可扩性、信息搜索与处理效率、知识推理效率等方面取得了一定的进步。对于第二个问题,八十年代以来国内外学者对此进行了较为系统和深入的研究,主要成果和方法有:p helps [4]的类比表示(Analogu representation)与联想网络、Dolk [5]的模型抽象(model abstraction)表示法、王红卫[6]的基于框架和算子的模型知识表示法等等[13,14],它们在模型要素的独立性、关联性、推理能力与符号化知识的处理方面已取得了很大进展,但它们还难以恰当描述具有动态状态转移特征的运筹学规划模型。为

此,作者以颇具代表性的动态规划模型为研究对象,提出了

动态规划模型知识表示的新方法)))IGOTDS 表示法[7],形成了动态规划问题的知识化数学模型,较好地解决了状态转移方程、递推方程等动态规划模型要素的知识表示问题,并使计算机求解该类模型具备了基于知识的推理能力。对于第三个问题,目前的研究工作主要集中在利用建模知识库中拥有的领域知识(domain knowledge)演绎推理生成相应的模型,如结构化建模方法[8][15]、基于Petri 网的建模方法[9][16]等等,它们在一定范围内得到了初步应用。由于运筹学数学模型具有动态的状态转移特性,因此运筹学问题的知识化数学模型以及知识化信息模型在描述方式及模型结构等方面也就具有特殊性。如何把运筹学实际问题的知识化信息模型转化成一种知识化的数学模型,这是运筹学智能化应用研究中一个急待解决的核心问题,解决这一问题的思路是建立一个基于积木式建模方法的知识化数学模型生成器。本文以运筹学的主要分枝)))动态规划问题为研究对象,阐述其知识化数学模型生成器的原理与结构。

2 动态规划问题的公式化数学模型及其知识化数学模型

211 动态规划问题的公式化数学模型

无论是离散型动态规划模型还是连续型动态规划模型,它们都由七部分构成[10]:1阶段的划分;o各阶段的状态变量;à各阶段的决策变量;?允许决策集合;?状态转移方程;?递推关系式(递推方程);?边界条件。现以例1所示的动态规划实际应用问题为例,阐述其公式化数学模型的构成。

)

64)

(例1)投资决策问题:某公司准备投入3千万元资金对所属3个工厂进行技术改造,投资金额分为0、1、2、3千万元四种额度,经测算得知,每个工厂的投资额与技术改造之后每年新增的效益如下表所示(表1):

表1投资与年新增效益表单位:千万元

投资额工厂0123工厂10015112210

工厂20014113212

工厂30016114118

问如何在3个工厂之间进行投资分配,使得总的年新增收益值最大?这是一个三个阶段的动态规划问题,其公式化数学模型如下:

(1)阶段的划分:设k为阶段变量。将确定工厂k投资额的决策定为第k阶段,k=1,2,3。

(2)各阶段的状态:状态变量用x

k

表示,k=1,2,3。本例中状态变量的取值为各阶段初可用的投资资金额。

(3)各阶段的决策变量:第k阶段的决策变量用u k表示(k=1,2,3),其值表示对工厂k的投资额。

(4)允许决策集合D

k (x

k

):D

k

(x

k

)={0,1,2,3}n{0[u

k

[x k}

(5)状态转移方程:x k+1=x k-u k,k=1,2,3

(6)递推关系式:f

k (x

k

)=max

u k I D k(x k)

{v

k

(x

k

,u

k

)+f

k+1

(x

k+1

)}

其中v k(x k,u k)为阶段指标函数,本例中其值为k阶段工厂k的年新增效益值。

(7)边界条件:f

4(x

4

)=0

上述公式化数学模型由于结构复杂、难以在计算机中表示状态转移方程及递推关系式和实现基于知识的推理过程(如符号化极值和导数等),从而导致至今还没有通用的求解动态规划模型的计算机程序。解决这一问题的根本出路在于采用基于知识的模型表示法来描述动态规划模型。

212动态规划问题的知识化数学模型

根据动态规划问题的决策过程特点可知,动态规划问题的最优解对应于状态空间图中始点至目标结点的一条最佳路径,因此,动态规划模型可以用一种基于知识模型表示法)))IGOTDS法[7]进行描述,它用一个六元组来描述一个动态规划模型,由此而形成的基于知识的数学模型称之为动态规划问题的知识化数学模型。

动态规划模型M可以表示为一个六元组:

M=(I,G,O,T,D,S)(3)其中:I)))初始状态(ini tial state)的集合,用于描述状态转移图的初始节点;

G)))目标状态(goal state)的集合,用于描述状态转移图的目标节点;

O)))状态转换的操作(operate)集合,用于描述动态规划模型的允许决策集合;

T)))状态转换(transition)规则的集合,用于描述动态规划模型的状态转移方程;

D)))基本数据(data)的集合,用于描述阶段指标函数和边界条件等:

S)))在问题的状态空间中寻找最佳路径(动态规划模型最优解)的搜索与推理策略(search and inference policy)的集合,用于描述动态规划模型的递推方程以及基于R.Bellman 最优化原理的模型求解搜索与推理策略;

在六元组M=(I,G,O,T,D,S)中,集合I、G、O、D用一阶谓词描述,集合T和S均采用产生式规则(productionrole)来描述。

例1所示的动态规划问题的公式化数学模型可用IGOTDS表示法进行描述。用谓词own(stage,money)表示某阶段初拥有的投资资金额;用谓词invest(stage,money,number_of_ i nvest)表示某阶段stage拥有的投资资金数量为money,而对相应的工厂进行投资所采用的投资额为number_of_invest;用谓词V(stage,money,number_of_invest,value_of_stage)表示对应于某阶段某种状态采用某种投资额所获得的阶段指标函数值(一个阶段的效益值);用谓词f(stage,money,value_of_ process)表示对应于某一阶段的某种状态选取最优投资子策略之后得到的过程的指标函数值(即最优指标函数值)。则例1对应的动态规划公式化数学模型可描述成下列知识化数学模型:

(1)初始状态集合:

own(1,3)

(2)目标状态集合:

Own(4,0).

(3)操作/决策集合:

invest(1,3,0).,,invest(3,0,0).

(4)状态转换规则集合1:

IF invest(1,3,0)THE N Own(2,3).,,IF invest(3,0,0) THE N Own(4,0).

(5)基本数据集合:

V(1,3,0,0).,,V(3,0,0,0).f(4,0,0).

(6)搜索与推理策略集合:

例1属于离散型动态规划问题,其模型求解的搜索与推理策略将采用一种名为IB FS的搜索算法[7]。

3动态规划问题的知识化信息模型

采用运筹学规划问题基于知识的树状表示法[3],例1所述的投资问题的信息可以归结成为一种层次化的树状结构,其问题描述树如图1所示:

)

65

)

Vol118,No12管理工程学报2004年第2期1不同的程序语言表示规则的形式可能不同,Prolog语言采用o wn(2,3):-invest(1,3,0)的形式表示规则。

图1 投资问题的问题描述树结构图

问题描述树反映的是问题有关信息的一种逻辑结构,它还需要用具体的计算机语言加以描述才便于在计算机内实现存储,形成一个可执行程序。此可执行程序由于是一种基

于知识的描述相应问题原始信息的语言模型,故可称之为问题的知识化信息模型。图1所示的问题描述树所对应的知识化信息模型的结构如图2所示

:

图2 投资问题信息模型结构图(程序结构图)

根据图2所示的程序结构,采用Turbo Prolog 语句,该投资问题知识化信息模型的程序语句如下:

clauses

P *the s tructure of Message Model for investment problem *P message of investment contain([/aspect of investment stage 0,/aspect of investment 0,/aspect of investment profits 0,/aspect of problem object 0]).

P *the paragraphs which every aspects con tains *P aspect of i nvestment s tage con tain([/paragraph of inves tmen t stage 0]).aspect of i nvestment contain([/paragraph of investment kind 0,/paragraph of inves tmen t number 0])aspect of i nvestment profi ts contain([paragraph of profits~.for every stage]).aspect of problem object con tain([/paragraph of problem object 0]).P *The facts of every paragraphs *P

P *the facts in paragraph of investment s tage *P stage(3).P *the facts in paragraph of investment kind *P investment kinds(4).

P *the facts in paragraph of investment nu mber *P total investment(3).kinds investment(1,0).kinds investment(2,1).kinds investment(3,2).kinds investment(4,3).

P *the facts in paragraph of investment profits *P profit(1,0,0).profit(3,3,1.8)。

1the facts in paragraph of problem object*/object(/max 0)

1end of M essage Model of investmen t problem *P

在上述程序中,前半部分描述的是投资问题知识化信息模型的结构,它用表谓词进行描述,此模型结构信息为知识化数学模型生成过程中的信息模型之识别奠定了基础。计算机可以依据不同应用问题在信息模型结构及每一侧面、语句段名称的不相同来识别问题的类型,并采用相应的方法生成知识化数学模型;上述程序的后半部分是实际应用问题(投资问题)的基础数据,它是在人机交互的问题输入过程中,由知识化信息模型的生成模块自动生成的。此外,程序

)

66)

胡祥培等:动态规划问题的知识化数学模型生成器研究

中谓词kind-investment(Kinds,Investment)表示某种投资方案的投资金额,谓词profi t(Stage,Investment,Profits)表示某阶段某一投资额对应的利润。

知识化信息模型(程序语句)前半部分的模型结构信息语句在识别实际应用问题之后,可以由计算机自动生成;后半部分的事实性数据语句在用户输入实际应用问题的数据之后,由相应的生成模块予以生成。这些由/问题描述支持系统0来实现。

4由知识化信息模型转化并生成知识化数学模型的原理

在识别动态规划问题的知识化信息模型并确定出该问题对应的知识化数学模型的类型之后,需要设计和建立动态规划问题知识化数学模型的生成知识库、知识化数学模型6个数据与规则模块的生成程序模块,并由此形成一个知识化数学模型的生成器,这样就可以实现由知识化信息模型至知识化数学模型的转化,并生成知识化数学模型所包含的6个模块。上述模型间的转化及知识化数学模型的生成过程是一个基于知识的推理过程,实现这一过程需要完成的核心操作如下:

411运用积木式建模方法建立一个名为/模型转化与生成0的程序模块

本文中积木式建模方法的基本思想是依据积木游戏的方法,由若干条用一阶谓词子句表示的事实或规则构造模型的基本单元)))模块,由若干个模块按照一定的组织结构及关系构成一个较大的模块,由若干个较大的模块按照一定的组织结构及关系构成更大的模块,,,按此方法继续下去,最终可构成一个结构化的程序模块(模型)。建立/模型转化与生成0程序模块的操作步骤为:

首先,根据知识化信息模型识别过程中推导出的知识化数学模型的类型,将知识化数学模型生成知识库中与该类知识化数学模型相关的模型(模块)生成规则作为/模型转化与生成0这一程序模块的一个子模块)))/模型生成规则0子模块,并予以独立存储;其次,将问题的知识化信息模型文件作另一个子模块)))/信息数据0子模块;随后,将含有目标语句的知识化数学模型中I、G、O、T、D、S模块的生成程序作为/模型转化与生成0程序模块的第三个子模块)))目标子模块;最后,运用积木式建模方法,以目标子模块为主体,运用Prolog语言的include语句,将这三个模块连接成/模型转化与生成0程序模块的Prolog程序(mtp.pro)。

/模型转化与生成0程序模块的构成如图3所示:

模型转化与生成程序模块

(mtp.pro)

目标子模块(mtpgoal.pro)

模型生成规则子模块

(mpr.

pro)

信息数据子模块

(md.

pro)

图3/模型转化与生成0程序模块的结构成分图412运行/模型转化与生成0程序模块(mpt.pro),生成构成知识化数学模型的各个数据与规则模块

/模型转化与生成0程序mtp.pro的运行过程及程序的工作原理是;首先,将目标子模块(mtpgoal.pro)中的目标语句(仅此模块中含有目标语句段)作为搜索匹配的目标,然后, Turbo Prolog语言的内部合一程序将目标语句段的第一个目标语句与模型生成规则子模块(mpr.pro)的规则及信息数据子模块(md,pro)中的/事实0子句进行匹配。匹配过程中,内部合一程序按照从左到右的搜索程序,从事实或规则子句的左部寻找与目标谓词具有相同谓词项的谓词,若某一规则左部谓词与目标谓词匹配成功,则内部合一程序将规则右部的每一条件语句作为原目标的一个子目标,依次匹配证明每一个子目标是否成功,只有当所有子目标均匹配成功时,规则左部代表的原目标才成功,否则只要有一个子目标不成功,原目标将失败。匹配失败后,转向下一个事实或规则,直到所有事实-与规则均已被测试证明失败为止。如果目标语句段的第一条目标语句成功,就转向下一条目标语句,重复上述匹配过程,直到所有目标语句均被搜索匹配为止。

上述程序执行过程中的匹配搜索过程也是动态规划问题的知识化信息模型转化并生成知识化数学模型的过程。这是因为模型生成规则子模块mpr.pro中每一条规则子句的右部条件语句是一些知识化数学模型各组成模块的生成操作语句及从信息数据子模块(相当于一个静态数据库)获取数据信息的语句,这样,随着规则语句右部的条件语句作为子目标进行匹配,也就随之完成了模型的转化与知识化数学模型各组成模块的生成操作。

下面按照例1所述的投资问题的知识化数学模型,以初始状态模块?为例,阐述其生成原理及过程:

该投资问题的知识化信息模型的clause部分,包含有下列子句;

total_investment(3)

这条语句是建立该类问题知识化数学模型I模块必需的数据语句,它们与其它语句一起存储在信息数据子模块mdl.pro中。

在这类投资问题的知识化数学模型生成知识库中,其模型生成规则模块mprl.pro包含有如下关于生成初始状态模块?的生成规则:

do initial state prod uction:-

total investment(Amount),

do creating module I file and wri ting.

do creating module

-

I

-

file and writing:

write(/请输入知识化数学模型中初始状态模块文件的名称:0),nl,

readln(Module I name),

write(/请输入该模块的Symbolic module I name0),nl,

readln(Symbliclnodulelname),

open write(Symbolicmodulelname,Module I name),

writedevice(Symbolicmodulelname),

)

67

)

Vol118,No12管理工程学报2004年第2期

wr i te(/own(1,0,Amoun t,/)0),nl,wr i tedevice(screen),close(Symbolicmodulelname).

此外,/模型转化与生成0程序模块中还有一个包含目标语句段的目标子模块。对于生成知识化数学模型的初始状态模块?的目标子模块mtpgoall.pro,其目标语句段为:

goal

do initial state prod uction,

以目标子模块为主体,在其前部加上语句include /mdl.pro 0和include /mprl,pro 0,即可连接成/模型转化与生成0程序mtp1.pro 。

运行程序mtp1.pro,即可生成知识化数学模型的?文件。该程序运行中的搜索匹配操作及知识化数学模型初始状态模块I 的生成过程如图4

所示。

图4 某投资问题由信息模型生成知识化表示模型之初始状态模块I 的搜索匹配过程示意图

从上述实例不难发现,知识库中模型生成规则mpr1.pro 的右部条件语句描述并控制着三方面的操作:1从知识化信息模型文件(信息数据子模块)中获取相关的数据信息;o将有关数据信息转化为生成模块(模型)要求的数据;à建立模块文件、写入数据、关闭并存储文件。知识库中的模型(块)生成规则是控制搜索匹配过程完成预定的转化与生成操作的核心控制单元,也是使模型转化与生成过程产生/智能0的源泉。因此,动态规划问题由知识化信息模型转化并生成知识化数学模型的过程实质上是一个基于规则的推理(搜索、匹配)过程。概括起来说,由动态规划问题的知识化信息模

型转化并生成知识化数学模型的原理是:运用积木式建模方法,由相关子模块组合成一个/模型转化与生成0程序模块:根据目标语句匹配模型的生成规则,按照模型的生成规则,从知识化信息模型中获取需要的数据,并进行相应的数据转化,建立相应的模型(块)文件写入相应的数据与规则。

5 动态规划问题知识化数学模型生成器的结构

动态规划问题的知识化数学模型生成器之结构如图5所示

:

图5 动态规划问题知识化数学模型生成器的结构图

图5中,/知识化数学模型生成器的人机接口0是进行数据信息传递的接口,也是该生成器在系统维护与操作过程中

)

68)

胡祥培等:动态规划问题的知识化数学模型生成器研究

进行人机对话的窗口;/信息模型识别程序模块0的功能是根据知识库中的识别规则与知识化信息模型文件的信息内容进行匹配,推理出实际应用问题对应的知识化数学模型的类型代码;/模型的转化与生成程序模块0的功能是根据欲完成的模块生成任务,将知识化信息模型文件、知识库中的模块生成规则、生成模块?、G、O、T、D、S的一个或几个目标子模块(视模块生成任务而定,当选择多个目标子模块时。需先合并为只有一个目标语句段)用include语句连接成一个/模型转化与生成0程序模块的可执行文件;知识化数学模型的生成知识库是一个用产生式规则描述动态规划问题信息模型识别规则和知识化数学模型各组成模块之生成规则的规则库;生成模块I、G、O、T、D、S的目标子模块最主要的功能是分别给出生成知识化数学模型这六个模块的程序目标语句。

运用上述生成器,作者在微机上实现了一个投资决策问题的知识化数学模型的生成过程。运用积木式建模方法将知识化数学模型的各个模块连接成一个知识化求解模型,运行该求解模型即可求解出投资决策问题的最优解。

6结论

11基于积木式建模方法的动态规划问题知识化数学模型生成器可以根据需要比较方便地生成知识化数学模型的一个或多个模块。这一模型生成器虽然是针对动态规划问题而建立的,但是其建模方法和工作原理对于运筹学其它实际应用问题建模操作也是适用的。

21知识化数学模型生成器的建立为较完整地实现实际应用问题y知识化信息模型y知识化数学模型y知识化求解模型的转化创造了条件,可以为不熟悉运筹学知识的用户提供建模支持并求出问题的最优解。有利于拓宽运筹学的应用领域,特别是在动态系统的实时控制领域具有一定的应用前景。

参考文献

[1]T.P.Liang.Anal ogical reas oni ng and case-bas ed learning in model

management system[J].Decisi ond Support Sys tem,1993,9(10):137

~160.[2]汪时萍,张国庆,李心丹.基于语义模型的智能型问题描述

[J].决策与决策支持系统,1993,(3):214~221.

[3]胡祥培,钱国明等.运筹学规划问题一种基于知识的树状表示

法[J].哈尔滨工业大学学报,1997,29(3):8~11.

[4]R.I.phelps.Artificial intelligence)))an overvi ew of s imil arities with

O.R.[J].Journal of Operati onal Research Society,1986,37(1):13

~20.

[5]Daniel R.Dol k,Benn R.Kons ynski.Knowledge representation for

model manage ment s ystems[J].IEEE Trans.on Software

Engineering,Nov.,1984,Vol.SE-10,No.6.

[6]王红卫,费奇.决策支持系统中的模型知识化[J].系统工程理

论与实践,1993,(6).

[7]胡祥培,钱国明等.离散型动态规划模型的知识表示及其IBFS

算法研究[J].哈尔滨工业大学学报,1996,28(3):119~126. [8]于晓迪.D SS中的模型表示与模型库[J].计算机科学,1990年

第4期

[9]王红卫,何勇,费奇.基于Petri网的模型管理[J].决策与决策

支持系统,1995,(1):1~7

[10]胡运权.运筹学基础及应用[J].哈尔滨工业大学出版社,1993

年9月第2版:170~187.

[11]夏幼明,刘海庆,徐天伟.基于语义网络的知识表示的形式转

换及推理[J].武汉大学学报#信息科学版,2001(26):369~

373.

[12]Benjanmin Kuipers.The spatial semantic hierarchy[J].Artificial

Intelligence,2000,(119):191~233.

[13]Colette Faucher.Easy defini tion of new face ts i n the frame-based

language Objlog+[J].Data and Knowledge Engineering,2001,

(38):223~263.

[14]付炜.基于框架网络结构的专家知识表示方法研究[J].计算

机应用,2002,(22):3~6.

[15]Nikos Karacapilidis.Modeling discourse in collaborative work s upport

s ys te ms:a knowledge representation and configuration pers pecti ve

[J].Knowledge-based System,2002,(15):413~422.

[16]X.Li, https://www.wendangku.net/doc/0917521863.html,ra-Rosano.Adapti ve fuz zy petri nets for dynamic

knowledge representation and inference[J].Expert Systems with

Applicati ons,2000,(19):235~241.

)

69

)

Vol118,No12管理工程学报2004年第2期

胡祥培等:动态规划问题的知识化数学模型生成器研究

A Generrator of the Know ledge-based Mathematical Model for

Dynamic Programming Problems

HU Xiang-pei1,WANG Xu-yin1,LIU We-i guo1,HU Yun-quan2,QIAN Guo-ming2

(1.Institute of Systems Engineering,Dalian University of Teehnology,Dalian116023,China;

2.School of M anagement,Harbin Ins titute of Technology,Ha p erbin,150001,China)

Abstract:According to the problem ex i sting in automatic modeling of dynamic programmi ng model in compu ter,the knowledge representation for the problem together wi th its model of dynamic programming,which form the knowledge-based information model and knowledge-based mathmatical model,have been studied in this paper.Appling the methods of the building block modeling,the structure and principle of a generation to form the knowledge-based mathmatical model of dynamic programming problems are put forward.Furthermore,the modeling process of an investment decision-making problem has been realized by computer.It is benificial for this research to creat a way to modeling automatically for Operations research models.

Key words:Operations Research;Dynamic Programmin g;Model Generation;Knowledge Representation;Building Block Modeling

责任编辑:杜健

)

)

70

数学建模算法动态规划

第四章动态规划 §1 引言 1.1 动态规划的发展及研究内容 动态规划（dynamic programming）是运筹学的一个分支，是求解决策过程（decision process）最优化的数学方法。20世纪50年代初R. E. Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优性原理（principle of optimality），把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法—动态规划。1957年出版了他的名著《Dynamic Programming》，这是该领域的第一本著作。 动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。 应指出，动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种特殊算法（如线性规划是一种算法）。因而，它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。因此，在学习时，除了要对基本概念和方法正确理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。 例1 最短路线问题 下面是一个线路网，连线上的数字表示两点之间的距离（或费用）。试寻求一条由A 到G距离最短（或费用最省）的路线。 例2 生产计划问题 工厂生产某种产品，每单位（千件）的成本为1（千元），每次开工的固定成本为3（千元），工厂每季度的最大生产能力为6（千件）。经调查，市场对该产品的需求量第一、二、三、四季度分别为2，3，2，4（千件）。如果工厂在第一、二季度将全年的需求都生产出来，自然可以降低成本（少付固定成本费），但是对于第三、四季度才能上市的产品需付存储费，每季每千件的存储费为0.5（千元）。还规定年初和年末这种产品均无库存。试制定一个生产计划，即安排每个季度的产量，使一年的总费用（生产成本和存储费）最少。 1.2 决策过程的分类 根据过程的时间变量是离散的还是连续的，分为离散时间决策过程（discrete-time decision process）和连续时间决策过程（continuous-time decision process）；根据过程的演变是确定的还是随机的，分为确定性决策过程（deterministic decision process）和随

数学建模(农业规划模型)

数学建模论文

农业生产规划模型 杨欢 （2011级2班1110500122） 【摘要】 本模型就是研究了农民在农业生产中种植农作物和养殖畜牧业的生产规划问题。以现有标准为参考，采用逐步分析法提出了线性规划模型，计算出农民在农业生产中该如何合理规划农作物的种植和畜牧业养殖的分配问题。本文根据题目给出的数据和条件，假设出了必要未知量，再根据题意列出必要方程和不等式，从而建立了完整而又合理的数学模型。 最终建立的数学模型如下： 目标函数Max z=175*x1+300*x2+120*x3+400*x4+2*x5; 约束条件x1+x2+x3+1.5*x4<=100; 400*x4+3*x5<=15000; 20*x1+35*x2+10*x3+100*x4+0.6*x5<=3500; 50*x1+75*x2+40*x3+50*x4+0.3*x5<=4000; x4<=32; x5<=3000; x1,……,x5>=0 最后我们运用LINDO等数学软件进行模型求解和分析，确保了结果的准确性和可行性。 【关键词】农业规划投资最大净收益数学模型LINDO软件 1问题的重述

1.1 问题背景： 近年来，农业生产问题越来越收到人们的关注。人们对“农场”的热衷最初来自网络游戏带来的乐趣，同时带动和启发了人们积极投入到现实农场的建设和经营。当然，人们对农场的热衷还是日常生活的实际需求。中国是一个农业大国，农民的农业生产生活问题不仅在很大程度上影响着我国的经济发展，更是决定着中国13亿人口的温饱问题。所以，对农场进行合理的规划，使其达到最优的效果，也即是最大的收益，是一个不可忽视的问题。 让拥有有限济实力和有限土地的农民，在有限的投资和有限的土地限制下，可以按照不同季经节合理安排种植业和畜牧业的劳动时间，更可用赋予时间进行多项劳动，从而可以在规定的劳动力和劳动时间内收获最大净收益。这不仅可以展我国的农业，更可使农民富裕起来，从而缩小了我国的贫富差距，对我国的经济发展有着重大促进作用。 1.2 问题叙述： 在上述背景下。我们来研究下面的具体问题： 现某农场有100公顷土地和150000元资金可用于发展生产，农场劳动力情况为秋冬季节3500人日，春夏季节4000人日，如果劳动力本身用不了时可外出干活，春夏季收入为21元/人日，秋冬季收入为18元/人日。该农场种植三种作物，大豆、玉米、小麦，并饲养奶牛和鸡。种植作物事不需要专门投资，而饲养动物时每头奶牛投资400元，每只鸡投资3元，养奶牛时每头需要播出1.5公顷土地饲草，并占用人工秋冬季为100人日，春夏季为50人日，年净收入400元/每头奶牛，养鸡不占土地，需人工为每只鸡秋冬季需0.6人日，春夏季为0.3 人日，年净收入20元/每只鸡。农场现有鸡舍允许最多养3000只鸡，牛栏允许最多养32头奶牛。三种作物每年需要的人工及收入情况如下表，试决定该农场的经营方案，使年净收入为最大。（农作物的生产需要和收益如下表所示：） 大豆玉米麦子

数学建模论文(奶牛场问题)

奶牛场计划 摘要 本文是对农场生产计划进行最优化建模，首先要求制订未来五年的生产计划, 计划应贷款的金额、应卖的小母牛、以及用来种植粮食的土地，使成本降到最低。其中农场的收入包含卖牛的收入，卖牛奶的收入，和卖粮食甜菜的收入（当粮食和甜菜充足的情况下），农场的支出包括劳动力的消费，买牛的费用，承包农场的费用，以及购买粮食甜菜的费用（当粮食和甜菜不足的情况下）。通过迭代计算可以把本模型简化成一个收入和支出的关系表达式，将银行贷款利息结合到收支上，建立一个非线性规划模型，同时考虑到粮食的充和不足情况，运用0-1规划方法解决建模问题。最后我们利用LINGO 编程得到最终结果。 关键词：收入支出迭代计算 0-1规划 LINGO

一、问题重述 1.1问题背景 某公司计划承包有200亩土地的农场，建立奶牛场，雇佣工人进行奶牛养殖经营。由于承租费用较高，公司只能向银行贷款进行生产经营。现在要为未来的五年制定生产计划，并向银行还本付息，使公司盈利最大。 1.2相关信息 开始承包时农场有120头母牛，其中20头为不到2岁的幼牛，100头为产奶牛。产奶牛平均每头每年生1.1头牛，其中一半为公牛，生出后不久即卖掉，平均每头卖300元；另一半为母牛，可以在出生后不久卖掉，平均每头卖400元，也可以留下饲养，养至2岁成为产奶牛。幼牛年损失5%；产奶牛年损失2%。产奶牛养到满12岁就卖掉，平均每头卖1200元。现在有20头幼牛， 0岁和1岁各10头；100头产奶牛，从2岁至11岁，每一年龄的都有10头。应该卖掉的小母牛都已卖掉。所有20头是要饲养成产奶牛的。 一头牛所产的奶提供年收入3700元。现在农场最多只能养130头牛。超过此数每多养一头，要投资2000元。每头产奶牛每年消耗0.6吨粮食和0.7吨甜菜。每头小牛每年消耗粮食和甜菜量为奶牛的2/3。粮食和甜菜可以由农场种植出来。每亩产甜菜1.5吨。只有80亩的土地适于种粮食，产量平均0.9吨。从市场购粮食每吨900元，卖出750元。买甜菜每吨700元，卖出500元。 养牛和种植所需的劳动量为：每头小牛每年10小时；每头产奶牛每年42小时；种一亩粮食每年需20小时；种一亩甜菜每年需30小时。 其它费用：每头幼牛每年500元，产奶牛每头每年1000元；种粮食每亩每年150元，种甜菜每亩每年100元。劳动力成本为每小时费用为10元。 承包农场需要一笔费用，其中一部分是土地承租费用，每年6万元（每年底付清），另一部分用于支付开始承包时农场已有的120头牛的费用。平均产奶牛每头4000元，小牛每头400元，到承包结束时，农场的牛按此价折价抵卖。 任何投资都是从5年期的贷款得到。贷款的年利率为12%，每年偿还本息总共的1/5，

农场生产计划 数学建模

农场生产计划 数学模型 问题重述 某农场有3万亩农田，欲种植玉米、大豆和小麦三种农作物．各种作物每亩需施化肥分别为 吨、吨、 吨．预计秋后玉米每亩可收获500千克，售价为 元/千克， 大豆每亩可收获200千克，售价为 元/千克，小麦每亩可收获350 千克，售价为 元 /千克．农场年初规划时考虑如下几个方面： 第一目标：年终收益不低于350万元； 第二目标：总产量不低于万吨； 第三目标：玉米产量不超过万吨，大豆产量不少于万吨，小麦产量以 万吨为宜，同时根据三种农作物的售价分配权重； 第四目标：农场现能提供5000 吨化肥；若不够，可在市场高价购买，但希望高价采购量愈少愈好． 模型假设与建立 模型假设： 1、 假设农作物的收成不会受天灾的影响 2、 假设农作物不受市场影响，价格既定 用321,,x x x 分别表示用于种植玉米、大豆、小麦的农田（单位：亩） + +---++++++=6 455433_22_11*)107 35*10735*10760*10712(**min d p d d d d p d p d p z 模型建立 约束条件 （1）刚性约束 30000321<=++x x x （2）柔性约束 第一目标：年终收益不低于350万元； {} ?????=-++++ -- 3500000 245240120min 113211 d d x x x d

第二目标：总产量不低于万吨； {} ?????=-++++ -- 12500000 350200500min 223212 d d x x x d 第三目标：玉米产量不超过万吨，大豆产量不少于万吨，小麦产量以 万吨为宜， {} ?????=-++ -+ 6000000 500min 3313 d d x d {} ?????=-++--2000000 200m in 4424d d x d {} ?? ???=-+++-+-500000035min 55255d d x d d 第四目标：农场现能提供5000 吨化肥；若不够，可在市场高价购买，但希望 高价采购量愈少愈好． {} ?????=-++++ -+ 5000000 15.02.012.0min 663216 d d x x x d 模型求解：（见附件） 种植面积： 玉米：亩 土豆：亩 小麦：亩 能够得到一个满足条件的种植计划 附件： model : sets : L/1..4/:p,z,goal; V/1..3/:x; HN/1..1/:b; SN/1..6/:g,dp,dm; HC(HN,V):a; SC(SN,V):c; Obj(L,SN):wp,wm; endsets data : p=; goal=0;

自动控制系统的数学模型

第二章自动控制系统的数学模型 教学目的： （1）建立动态模拟的概念，能编写系统的微分方程。 （2）掌握传递函数的概念及求法。 （3）通过本课学习掌握电路或系统动态结构图的求法，并能应用各环节的传递函数，求系统的动态结构图。 （4）通过本课学习掌握电路或自动控制系统动态结构图的求法，并对系统结构图进行变换。 （5）掌握信号流图的概念，会用梅逊公式求系统闭环传递函数。 （6）通过本次课学习，使学生加深对以前所学的知识的理解，培养学生分析问题的能力 教学要求： （1）正确理解数学模型的特点； （2）了解动态微分方程建立的一般步骤和方法； （3）牢固掌握传递函数的定义和性质，掌握典型环节及传递函数； （4）掌握系统结构图的建立、等效变换及其系统开环、闭环传递函数的求取，并对重要的传递函数如：控制输入下的闭环传递函数、扰动输入 下的闭环传递函数、误差传递函数，能够熟练的掌握； （5）掌握运用梅逊公式求闭环传递函数的方法； （6）掌握结构图和信号流图的定义和组成方法，熟练掌握等效变换代数法则，简化图形结构，掌握从其它不同形式的数学模型求取系统传递函 数的方法。 教学重点： 有源网络和无源网络微分方程的编写；有源网络和无源网络求传递函数；传递函数的概念及求法；由各环节的传递函数，求系统的动态结构图；由各环节的传递函数对系统的动态结构图进行变换；梅逊增益公式的应用。 教学难点：举典型例题说明微分方程建立的方法；求高阶系统响应；求复杂系统的动态结构图；对复杂系统的动态结构图进行变换；求第K条前向通道特记式 的余子式 。 k 教学方法：讲授 本章学时：10学时 主要内容： 2.0 引言 2.1 动态微分方程的建立 2.2 线性系统的传递函数 2.3 典型环节及其传递函数 2.4系统的结构图 2.5 信号流图及梅逊公式

数学建模-动态规划

-56- 第四章动态规划 §1 引言 1.1 动态规划的发展及研究内容 动态规划（dynamic programming）是运筹学的一个分支，是求解决策过程（decision process）最优化的数学方法。20 世纪50 年代初R. E. Bellman 等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优性原理（principle of optimality），把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法—动态规划。1957 年出版了他的名著《Dynamic Programming》，这是该领域的第一本著作。 动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广 泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时 间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。 应指出，动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是 一种特殊算法（如线性规划是一种算法）。因而，它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。因此，在学习时，除了要对基本概念和方法正确理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。 例1 最短路线问题 图1 是一个线路网，连线上的数字表示两点之间的距离（或费用）。试寻求一条由A 到G 距离最短（或费用最省）的路线。 图1 最短路线问题 例2 生产计划问题 工厂生产某种产品，每单位（千件）的成本为1（千元），每次开工的固定成本为3 （千元），工厂每季度的最大生产能力为6（千件）。经调查，市场对该产品的需求量第一、二、三、四季度分别为2，3，2，4（千件）。如果工厂在第一、二季度将全年的需求都生产出来，自然可以降低成本（少付固定成本费），但是对于第三、四季度才能上市的产品需付存储费，每季每千件的存储费为0.5（千元）。还规定年初和年末这种产品均无库存。试制定一个生产计划，即安排每个季度的产量，使一年的总费用（生产成本和存储费）最少。 1.2 决策过程的分类 根据过程的时间变量是离散的还是连续的，分为离散时间决策过程（discrete-time -57- decision process）和连续时间决策过程（continuous-time decision process）；根据过程的演变是确定的还是随机的，分为确定性决策过程（deterministic decision process）和随 机性决策过程（stochastic decision process），其中应用最广的是确定性多阶段决策过程。§2 基本概念、基本方程和计算方法 2.1 动态规划的基本概念和基本方程 一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素。 2.1.1 阶段

数学建模之农场规划问题

农场规划问题 问题重述： 某农户拥有100亩土地和15000元可供投资，每年冬季（9月中旬至来年5月中旬），该家庭的成员可以贡献3500小时的劳动时间，而夏季为4000小时。如果这些劳动时间有富裕，该家庭中的年轻成员将去附近的农场打工，冬季每小时元，夏季每小时元。 现金收入来源于三中农作物（大豆、玉米和燕麦）以及奶牛和母鸡。农作物不需要付出投资，但每头奶牛需要400元的初始投资，可产奶3年，每只母鸡需要3元的吃食投资，只饲养1年。每头奶牛需要亩的土地，并且冬季需要付出100小时劳动时间，夏季付出50小时劳动时间，每年产生的净现金收入为1350元；每只母鸡的对应数字为：不占用土地，冬季小时，夏季小时，年净现金收入元。养鸡厂房最多容纳3000只母鸡，栅栏的大小限制了最多能饲养32头奶牛。 根据统计，三种农作物每种植一亩所需要的劳动时间和收入数据分别为：大豆：冬季20小时，夏季30小时，年净收入元；玉米：冬季35小时，夏季75小时，年净收入元；燕麦：冬季10小时，夏季40小时，年净收入元。 基本假设： 1、假设该农户每年都能及时获得现金收入，即本年度所获得的利润可及时 用于下一年的投资； 2、第五年的投资也考虑到计算中。 问题分析: 这个问题的目标是使得5年内净现金收入最大，要做的决策是生产规划，即确定每种农作物应该种植多少亩，奶牛和鸡各应蓄养多少只，决策受到6个变量的限制，即土地总面积、投资资金、劳动力时间（夏季和冬季）以及奶牛和鸡的

总饲养量。 模型建立: 决策变量： 设用i=0,1,2,3,4,5表示年数，用j=1,2,3,4,5分别表示三种农作物（大豆、玉米、燕麦）及奶牛和母鸡。x xx 可表示第i 年种植三种农作物的亩数或者蓄养奶牛和母鸡的个数，x x 表示第i 年的总现金收入。 目标函数： 设第i 年的总获利为x x 元，因农作物不用投资，则第i 年种植大豆为x x1亩，每亩收入360元，获利360×x x1元；第i 年种植玉米x x2亩，每亩收入600元，获利600×x x2；第i 年种植燕麦x x3亩，每亩收入400元，获利400×x x3元；第i 年买奶牛x x4头，每头收入1350元，获利1350×（x x4+x （x ?1）4+x （x ?2）4）元；第i 年鸡购买x x5只，每只收入元，获利×x x5元；若劳动力有剩余，则第i 年夏季劳动力收入［4000-(30x x1+75x x2+40x x3+50x x4+0.3x x5)］×7元，冬季劳动力收入［3500-(20x x1+35x x2+10x x3+100x x4+0.6x x5)］×6.8元。 即： x x =(x x ?1?400x x4-3x x5)+360x x1+600x x2+400x x3+1350（x x4+x （x ?1）4+x （x ?2）4）+x x5+［4000-(30x x1+75x x2+40x x3+50x x4+0.3x x5)］×7+［3500-(20x x1+35x x2+10x x3+100x x4+0.6x x5)］×6.8 约束条件: 土地总面积 各种农作物及奶牛占用的土地不得超过该农户所拥有的土地， 故∑∑x xx 4x =15i =1≤100 投资钱数 每一年的投资总额度不得高于上一年的净现金收入，故

10427-数学建模-动态规划的原理及应用

动态规划的原理及应用 动态规划是运筹学的一个分支，是求解多阶段决策过程的最优化数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类问题的新方法——动态规划。 动态规划主要用于以时间划分阶段的动态过程优化问题，但一些与时间无关的静态规划如线性规划或非线性规划，人为引进时间因素后，把它们看成多阶段过程，也可用动态规划求解。 1．动态规划的基本理论 一．动态规划的术语 在研究现实的系统时，我们必须将系统具体的术语抽象为数学统一的术语。在此先简要介绍动态规划中的常用术语。 级：我们把系统顺序地向前发展划分为若干个阶段，称这些阶段为“级”。在离散动态规划中，“级”顺序的用自然整数编号，即1，2，…，n. 状态（λ）：用来描述、刻画级的特征。状态可以是单变量，也可以时向量。在此，我们假设研究的状态具有“无记忆性”，即当前与未来的收益仅决定于当前的状态，并不依赖于过去的状态和决策的历史。 状态空间（Λ）：由全部系统可能存在的状态变量所组成。

决策：在每一级，当状态给定后，往往可以做出不同的决定，从而确定下一级的状态，这种决定称为决策。描述决策的变量称为决策变量。对每个状态λ∈Λ，有一非空集X(λ)称为λ的决策集。决策变量x(λ)∈X（λ）。 变换：若过程在状态λ，选择决策x(λ)，可确定一个状态集T（λ，x(λ)）,过程将从λ移动到其中某个状态.T(λ,x(λ))称为变换函数，它确定过程从一个状态到另一个状态的演变。T（λ,x(λ)）可分为两种类型，即确定型和不确定型。确定型的T（λ,x(λ)）只含有一个元。不确定型指我们不能确切知道决策的结果，但作为某已知概率分布支配的变换结果，在每级状态和决策是确定的。这时，集函数T（λ,x(λ)）将包含多个元素。当T（λ,x(λ)）=0 时，过程终止。 策略：顺序排列的决策集，记为v。所有可能的策略集构成策略空间Γ。 收益：评价给定策略的目标函数r(λ，v)，它依赖于状态和策略。总收益是集收益s(λ,v)的某个组合（通常为集收益之和）。若T（λ,x(λ)）=0，则r(λ1，v1)= s(λ1,v1)；若T（λ,x(λ)）= λ2，则r(λ1，v)= s(λ1,v1)+ r(λ1，v2)。 二．序贯决策过程 动态规划的寻优过程可以有正序、逆序两种方式。当初始状态给定时，用逆序方式比较好，当终止状态给定时，用正序方式较好。 采用分级的序贯决策方法，把一个含有n个变量的问题转化为求解n个单变量问题。为了应用最优化原理，必须满足分级条件，即目标函数可分性和状态可分性。 目标函数可分性：

数学建模中的优化问题与规划模型

与最大、最小、最长、最短等等有关的问题都是优化问题。 解决优化问题形成管理科学的数学方法：运筹学。运筹学主要分支：（非）线性规划、动态规划、图与网络分析、存贮学、排队伦、对策论、决策论。 6.1 线性规划 1939年苏联数学家康托洛维奇发表《生产组织与计划中的数学问题》 1947年美国数学家乔治.丹契克、冯.诺伊曼提出线性规划的一般模型及理论. 1. 问题 例1 作物种植安排 一个农场有50亩土地, 20个劳动力, 计划种蔬菜,棉花和水稻. 种植这三种农作物每亩地分别需要劳动力1/2 1/3 1/4, 预计每亩产值分别为110元, 75元, 60元. 如何规划经营使经济效益最大. 分析：以取得最高的产值的方式达到收益最大的目标. 1. 求什么？分别安排多少亩地种蔬菜、棉花、水稻？ x 1亩、 x 2 亩、 x 3 亩 2. 优化什么？产值最大 max f=10x 1+75x 2 +60x 3 3. 限制条件？田地总量 x 1+x 2 +x 3 ≤ 50 劳力总数 1/2x 1 +1/3x 2 +1/4x 3 ≤ 20 模型I : 设决策变量：种植蔬菜x1亩, 棉花x2亩, 水稻x3亩， 求目标函数f=110x1+75x2+60x3 在约束条件x1+x2+x3≤ 50 1/2x1+1/3x2+1/4x3 ≤20 下的最大值 规划问题：求目标函数在约束条件下的最值, 规划问题包含3个组成要素: 决策变量、目标函数、约束条件。 当目标函数和约束条件都是决策变量的线性函数时，称为线性规划问题, 否则称为非线性规划问题。 2. 线性规划问题求解方法 称满足约束条件的向量为可行解,称可行解的集合为可行域, 称使目标函数达最值的可行解为最优解. 命题 1 线性规划问题的可行解集是凸集. 因为可行解集由线性不等式组的解构成。两个变量的线性规划问题的可行解集是平面上的凸多边形。 命题2 线性规划问题的最优解一定在可行解集的某个极点上达到. 图解法：解两个变量的线性规划问题，在平面上画出可行域，计算目标函数在各极点处的值，经比较后，取最值点为最优解。 命题 3 当两个变量的线性规划问题的目标函数取不同的目标值时，构成一族平行直线,目标值的大小描述了直线离原点的远近。 于是穿过可行域的目标直线组中最远离(或接近)原点的直线所穿过的凸多边形的顶点即为取的极值的极点—最优解。 单纯形法: 通过确定约束方程组的基本解, 并计算相应目标函数值, 在可行解集的极点中搜寻最优解. 正则模型: 决策变量: x 1,x 2 ,…,x n . 目标函数: Z=c 1 x 1 +c 2 x 2 +…+c n x n . 约束条件: a 11 x1+…+a1n x n≤b1, ……a m1x1+…+a mn x n≤b m, 模型的标准化 10. 引入松弛变量将不等式约束变为等式约束. 若有 a i1x 1 +…+a in x n ≤b i , 则引入 x n+i ≥ 0, 使得 a i1 x 1 +…+a in x n + x n+i =b i 若有 a j1x 1 +…+a jn x n ≥b j , 则引入 x n+j ≥ 0, 使得 a j1 x 1 +…+a jn x n - x n+j =b j .

数学建模线性规划

线性规划 1.简介： 线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产组织与计划的改进，即合理安排人力物力资源. 线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.规划问题。一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。 (x)都是线性函数，则该模型称为在优化模型中，如果目标函数f(x)和约束条件中的g i 线性规划。 2.线性规划的3个基本要素 （1）决策变量 （2）目标函数f(x) (x)≤0称为约束条件） （3）约束条件（g i 3.建立线性规划的模型 （1）找出待定的未知变量（决策变量），并用袋鼠符号表示他们。 （2）找出问题中所有的限制或者约束，写出未知变量的线性方程或线性不等式。

（3）找到模型的目标或判据，写成决策变量的线性函数，以便求出其最大值或最小值。以下题为例，来了解一下如何将线性规划用与实际的解题与生活中。 生产计划问题 某工厂生产甲乙两种产品，每单位产品消耗和获得的利润如表 试拟订生产计划，使该厂获得利润最大 解答：根据解题的三个基本步骤 （1）找出未知变量，用符号表示： 设甲乙两种产品的生产量分别为x 1与x 2 吨，利润为z万元。 （2）确定约束条件： 在这道题目当中约束条件都分别为：钢材，电力，工作日以及生产量不能为负的限制 钢材：9x 1+5 x 2 ≤360， 电力：4x 1+5 x 2 ≤200， 工作日：3x 1+10 x 2 ≤300， x 1≥0 ，x 2 ≥0， （3）确定目标函数： Z=7x 1+12 x 2

农业生产规划模型数学建模

长江学院 课程设计报告课程设计题目：农业生产规划模型 姓名1：袁珍珍学号： 08354230 姓名2：倪美丹学号： 08354213 姓名3：阮鹏娟学号： 08354216 专业土木工程 班级083542 指导教师邱淑芳 2010年4月11号

摘要： 通过对题目的分析可以看出本题是关于线性规划的问题，解决此类问题要找出决策变量，目标函数，约束条件等，在解题中我们建立了两种模型，通过比较来使问题更加的具有科学性。 中国是一个农业大国，农民的生产生活可以直接影响到国家的经济，优化农业生产模型是一个不可忽视的问题。本题就是研究了农民在农业生产中种植农作物和养殖畜牧业的生产规划问题。以现有标准为参考，采用假设分析法提出了优化模型，计算出农民在农业生产中合理规划农作物的种植和畜牧业养殖的分配问题。让拥有有限经济实力和有限土地的农民，在有限的投资和有限的土地限制下，可以按照不同季节合理安排种植业和畜牧业的劳动时间，更可用赋予时间进行多项劳动，从而可以在规定的劳动力和劳动时间内收获最大净收益。这不仅可以发展我国的农业，更可使农民富裕起来，从而缩小了我国的贫富差距，对我国的经济发展有着重大促进作用。本文根据题目给出的数据和条件，假设出必要未知量，再列出必要方程式，运用Lingo等数学软件分析提出合理的数学模型。关键字： 线性规划、数学建模、Lingo、农业生产、合理分配、最大净收益

阐述题目 某农户拥有100亩土地和25000元可供投资，每年冬季（9月份中旬至来年5月中旬），该家庭的成员可以贡献 3500h的劳动时间，而夏季为4000h。如果这些劳动时间有赋予，该家庭中的年轻成员将去附近的农场打工，冬季每小时元，夏季每小时元。 现金收入来源于三种农作物（大豆、玉米和燕麦）以及两种家禽（奶牛和母鸡）。农作物不需要付出投资，但每头奶牛需要400元的初始投资，每只母鸡需要3元的初始投资，每头奶牛需要使用亩土地，并且冬季需要付出100h劳动时间，夏季付出50h劳动时间，该家庭每年产生的净现金收入为450元；每只母鸡的对应数字为：不占用土地，冬季，夏季，年净现金收入元。养鸡厂房最多只能容纳3000只母鸡，栅栏的大小限制了最多能饲养32偷奶牛。 根据估计，三种农作物每种植一亩所需要的劳动时间和收入如下表所示。建立数学模型，帮助确定每种农作物应该种植多少亩，以及奶牛和母鸡应该各蓄养多少，使年净现金收入最大。

数学建模-线性规划

-1- 第一章线性规划 §1 线性规划 在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济 效益的问题。此类问题构成了运筹学的一个重要分支—数学规划，而线性规划(Linear Programming 简记LP)则是数学规划的一个重要分支。自从1947 年G. B. Dantzig 提出 求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在实用中日益广泛与深入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性 规划的适用领域更为广泛了，已成为现代管理中经常采用的基本方法之一。 1.1 线性规划的实例与定义 例1 某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000 元与3000 元。 生产甲机床需用A、B机器加工，加工时间分别为每台2 小时和1 小时；生产乙机床 需用A、B、C三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时 数分别为A 机器10 小时、B 机器8 小时和C 机器7 小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？ 上述问题的数学模型：设该厂生产1 x 台甲机床和2 x 乙机床时总利润最大，则1 2 x , x 应满足 （目标函数）1 2 max z = 4x + 3x (1) s.t.（约束条件） ?? ? ?? ? ? ≥ ≤ + ≤ + ≤ , 0 7 8 2 10 1 2 2 1 2 1 2 x x x x x x x （2） 这里变量1 2 x , x 称之为决策变量，（1）式被称为问题的目标函数，（2）中的几个不等式是问题的约束条件，记为s.t.(即subject to)。由于上面的目标函数及约束条件均为线性

数学建模8-动态规划和目标规划

数学建模8-动态规划和目标规划 一、动态规划 1.动态规划是求解决策过程最优化的数学方法，主要用于求解以时间划分阶段的动态过程的 优化问题。但是一些与时间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。 2.基本概念、基本方程： （1）阶段 （2）状态 （3）决策 （4）策略 （5）状态转移方程： （6）指标函数和最优值函数： （7）最优策略和最优轨线 （8）递归方程： 3．计算方法和逆序解法（此处较为抽象，理解较为困难，建议结合例子去看）

4．动态规划与静态规划的关系：一些静态规划只需要引入阶段变量、状态、决策等就可以用动态规划方法求解（详见书中例4） 5．若干典型问题的动态规划模型： （1）最短路线问题： （2）生产计划问题:状态定义为每阶段开始时的储存量x k，决策为每个阶段的产量，记每个阶段的需求量（已知量）为d k，则状态转移方程为 （3）资源分配问题：详见例5

状态转移方程： 最优值函数： 自有终端条件： （4）具体应用实例：详见例6、例7。 二、目标规划 1．实际问题中，衡量方案优劣要考虑多个目标，有主要的，有主要的，也有次要的；有最大值的，也有最小值的；有定量的，也有定性的；有相互补充的，也有相互对立的，这时可用目标规划解决。其求解思路有加权系数法、优先等级法、有效解法等。 2．基本概念： （1）正负偏差变量： （2）绝对（刚性）约束和目标约束 ，次位赋（3）优先因子（优先等级）与权系数：凡要求第一位达到的目标赋予优先因子P 1……以此类推。 予P 2 （4）目标规划的目标函数： （5）一般数学模型：

数学建模实验报告

湖南城市学院 数学与计算科学学院《数学建模》实验报告 专业： 学号： 姓名： 指导教师： 成绩： 年月日

实验一 初等模型 实验目的：掌握数学建模的基本步骤，会用初等数学知识分析和解决实际问题。 实验内容：A 、B 两题选作一题，撰写实验报告，包括问题分析、模型假设、模型构建、模型求解和结果分析与解释五个步骤。 A 题 飞机的降落曲线 在研究飞机的自动着陆系统时，技术人员需要分析飞机的降落曲线。根据经验，一架水平飞行的飞机，其降落曲线是一条S 形曲线。如下图所示，已知飞机的飞行高度为h ，飞机的着陆点为原点O ，且在整个降落过程中，飞机的水平速度始终保持为常数u 。出于安全考虑，飞机垂直加速度的最大绝对值不得超过g ／10，此处g 是重力加速度。 （1）若飞机从0x x 处开始下降，试确定出飞机的降落曲线； （2）求开始下降点0x 所能允许的最小值。 y 0x 一、 确定飞机降落曲线的方程

如图所示，我们假设飞机降落的曲线的方程为I d cx bx ax x f +++=23)( 由题设有 h x f f ==)(,0)0(0。 由于曲线是光滑的，所以f(x)还要满足0)(,0)0(0='='x f f ，代入f(x) 可以得到 ?? ? ? ?? ?=++='=+++==='==0 23)()(0)0(0)0(020*******c bx ax x f h d cx bx ax x f c f d f 得 ,0,0,3,22 3 ===- =d c x h b x h a 飞机的降落曲线为 )32()(2 30 2 0x x x x h x f --= 二、 找出最佳着陆点 飞机的垂直速度是关于时间t 的导数，所以 dt dx x x x x h dt dy )66(20 20--= 其中 dt dx 是飞机的水平速度， ,u dt dx = 因此 )(60 2 20x x x x hu dt dy --= 垂直加速度为 )12(6)12(6020 20202 2--=--=x x x hu dt dx x x x hu dt y d 记 ,)(22dt y d x a =则126)(0 2 02-=x x x hu x a ，[]0,0x x ∈ 因此，垂直加速度的最大绝对值为 2 26)(max x hu x a = []0,0x x ∈ 设计要求 1062 2g x hu ≤ ，所以g h u x 600?≥ （允许的最小值）

数学建模(工厂资源规划问题)

工厂资源规划问题 冉光明 29 信息与计算科学 指导老师：赵姣珍

目录 摘要 (1) 关键词 (1) 问题的提出 (2) 问题重述与分析 (3) 符号说明 (4) 模型假设 (4) 模型建立与求解 (5) 模型检验 (9) 模型推广 (10) 参考文献 (11) 附录 (12)

摘要：本问题是个优化问题。问题首先选择合适的决策变量即各种产品数，然后通过决策变量来表达约束条件和目标函数，再利用或编写程序，求得最优产品品种计划；最后通过优化模型对问题作以解释，得出当技术服务消耗33小时、劳动力消耗67小时、不消耗行政管理时，得到的是最优品种规划。 问题一回答：当技术服务消耗33小时、劳动力消耗67小时、不消耗行政管理时， 产品不值得生产。用运算分析，当产品的利润增加至25 3 时，若使产品品种计划最优， 此时需要消耗技术服务29h，劳动力消耗46h，行政管理消耗25h。 问题二回答：利用得到当技术服务增加1h时，利润增加2.5元;劳动力增加1h，利润增加1元；行政管理的增减不会影响利润。 问题三回答：增加的决策变量，调整目标函数。当技术服务消耗33h，劳动力消耗17h，不消耗行政管理，新增量50h时，管理部门采取这样的决策得到最优的产品品种规划。 问题四回答：增加新的约束条件，此时当技术服务消耗32h，劳动力消耗58h，行政管理消耗10h时，得到最优产品品种规划。 本文对模型的求解给出在线性约束条件下的获利最多的产品品种规划。 关键词：线性规划；优化模型；最优品种规划

问题的提出 某工厂制造三种产品，生产这三种产品需要三种资源：技术服务、劳动力和行政管理。下表列出了三种单位产品对每种资源的需要量： 现有100h的技术服务、600h劳动力和300h的行政管理时间可使用，求最优产品品种规划。且回答下列问题： ⑴若产品值得生产的话，它的利润是多少？假使将产品的利润增加至25/3元，求获利最多的产品品种规划。 ⑵确定全部资源的影子价格。 ⑶制造部门提出建议，要生产一种新产品，该种产品需要技术服务1h、劳动力4h 和行政管理4h。销售部门预测这种产品售出时有8元的单位利润。管理部门应有怎样的决策？ ⑷假定该工厂至少生产10件产品，试确定最优产品品种规划。

第二章 动态数学模型

第二章控制系统的数学模型 控制系统的数学模型 本章主要内容： 引言 微分方程模型 传递函数模型 脉冲响应模型 方框图模型 信号流图模型 频域特性模型 数学模型的实验测定方法（辨识） 2.0 引言 主要解决的问题： 什么是数学模型 为什么要建立系统的数学模型 对系统数学模型的基本要求 2.0.1 什么是数学模型 控制系统的数学模型是描述系统内部各物理量（或变量）之间关系的数学表达式或图形表达式或数字表达式。 亦：描述能系统性能的数学表达式（或数字、图像表达式） 控制系统的数学模型按系统运动特性分为：静态模型

动态模型 静态模型：在稳态时（系统达到一平衡状态）描述系统各变量间关系的数学模型。 动态模型：在动态过程中描述系统各变量间关系的数学模型。 关系：静态模型是t时系统的动态模型。 控制系统的数学模型可以有多种形式，建立系统数学模型的方法可以不同，不同的模型形式适用于不同的分析方法。 2.0.2 为什么要建立控制系统的数学模型 控制系统的数学模型是由具体的物理问题、工程问题从定性的认识上升到定量的精确认识的关键！（这一点非常重要，数学的意义就在于此） 一方面，数学自身的理论是严密精确和较完善的，在工程问题的分析和设计中总是希望借助于这些成熟的理论。事实上凡是与数学关系密切的学科发展也是快的，因为它有严谨和完整的理论支持；另一方面，数学本身也只有给它提供实际应用的场合，它才具有生命力。“1”本身是没有意义的，只有给它赋予了单位（物理单位）才有意义。 建立系统数学模型的方法很多，主要有两类： 机理建模白箱实验建模（数据建模）黑箱或灰箱 系统辨识 2.0.3 对系统数学模型的基本要求 亦：什么样的数学表达式能用于一个工程系统的描述。 理论上，没有一个数学表达式能够准确（绝对准确）地描述一个系统，因为，理论上任何一个系统都是非线性的、时变的和分布参数的，都存在随机因素，系统越复杂，情况也越复杂。 而实际工程中，为了简化问题，常常对一些对系统运动过程影响不大的因素忽略，抓住主要问题进行建模，进行定量分析，也就是说建立系统的数学模型应该在模型的准确度和复杂度上进行折中的考虑。因此在具体的系统建模时往往考虑以下因素：

数学建模常用的十种解题方法

数学建模常用的十种解题方法 摘要 当需要从定量的角度分析和研究一个实际问题时，人们就要在深入调查研究、了解对象信息、作出简化假设、分析内在规律等工作的基础上，用数学的符号和语言，把它表述为数学式子，也就是数学模型，然后用通过计算得到的模型结果来解释实际问题，并接受实际的检验。这个建立数学模型的全过程就称为数学建模。数学建模的十种常用方法有蒙特卡罗算法；数据拟合、参数估计、插值等数据处理算法；解决线性规划、整数规划、多元规划、二次规划等规划类问题的数学规划算法；图论算法；动态规划、回溯搜索、分治算法、分支定界等计算机算法；最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法；网格算法和穷举法；一些连续离散化方法；数值分析算法；图象处理算法。 关键词：数学建模；蒙特卡罗算法；数据处理算法；数学规划算法；图论算法 一、蒙特卡罗算法 蒙特卡罗算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性，是比赛时必用的方法。在工程、通讯、金融等技术问题中, 实验数据很难获取, 或实验数据的获取需耗费很多的人力、物力, 对此, 用计算机随机模拟就是最简单、经济、实用的方法; 此外, 对一些复杂的计算问题, 如非线性议程组求解、最优化、积分微分方程及一些偏微分方程的解⑿, 蒙特卡罗方法也是非常有效的。 一般情况下, 蒙特卜罗算法在二重积分中用均匀随机数计算积分比较简单, 但精度不太理想。通过方差分析, 论证了利用有利随机数, 可以使积分计算的精度达到最优。本文给出算例, 并用MA TA LA B 实现。 1蒙特卡罗计算重积分的最简算法-------均匀随机数法 二重积分的蒙特卡罗方法(均匀随机数) 实际计算中常常要遇到如()dxdy y x f D ??,的二重积分, 也常常发现许多时候被积函数的原函数很难求出, 或者原函数根本就不是初等函数, 对于这样的重积分, 可以设计一种蒙特卡罗的方法计算。 定理 1 )1( 设式()y x f ,区域 D 上的有界函数, 用均匀随机数计算()??D dxdy y x f ,的方法: (l) 取一个包含D 的矩形区域Ω,a ≦x ≦b, c ≦y ≦d , 其面积A =(b 一a) (d 一c) ; ()j i y x ,,i=1,…,n 在Ω上的均匀分布随机数列,不妨设()j i y x ,, j=1，…k 为落在D 中的k 个随机数, 则n 充分大时, 有

数学建模 农场规划问题

model: Max=950*x11+7.5*x21+360*x31+600*x41+400*x51+6.8*(3500-100*x11-0.6*x21-20*x31-35*x4 1-10*x51)+7.0*(4000-50*x11-0.3*x21-30*x31-75*x41-40*x51)+1350*x11+950*x12+7.5*x21+36 0*x31+600*x41+400*x51+6.8*(3500-100*(x11+x12)-0.6*x21-20*x31-35*x41-10*x51)+7.0*(4000 -50*(x11+x12)-0.3*x21-30*x31-75*x41-40*x51)+1350*(x11+x12)+950*x13+7.5*x21+360*x31+6 00*x41+400*x51+6.8*(3500-100*(x11+x12+x13)-0.6*x21-20*x31-35*x41-10*x51)+7.0*(4000-50 *(x11+x12+x13)-0.3*x21-30*x31-75*x41-40*x51) +1350*(x12+x13)+950*x14+7.5*x21+360*x31+600*x41+400*x51+6.8*(3500-100*(x12+x13+x14) -0.6*x21-20*x31-35*x41-10*x51)+7.0*(4000-50*(x12+x13+x14)-0.3*x21-30*x31-75*x41-40*x51 ) +1350*(x13+x14)+950*x15+7.5*x21+360*x31+600*x41+400*x51+6.8*(3500-100*(x13+x14+x15) -0.6*x21-20*x31-35*x41-10*x51)+7.0*(4000-50*(x13+x14+x15)-0.3*x21-30*x31-75*x41-40*x51 ); x11+x12+x13<=32; x12+x13+x14<=32; x13+x14+x15<=32; x21<=3000; x22<=3000; x23<=3000; x24<=3000; x25<=3000; 1.5*x11+x31+x41+x51<=100; 1.5*x11+x32+x42+x52<=100; 1.5*x11+1.5*x12+1.5*x13+x33+x43+x53<=100; 1.5*x12+1.5*x13+1.5*x14+x34+x44+x54<=100; 1.5*x13+1.5*x14+1.5*x15+x35+x45+x55<=100; 100*x11+0.6*x21+20*x33+35*x43+10*x52<=3500; 100*x11+100*x12+0.6*x22+20*x33+35*x43+10*x52<=3500; 100*x11+100*x12+100*x13+0.6*x23+20*x33+35*x43+10*x52<=3500; 100*x12+100*x13+100*x14+0.6*x24+20*x34+35*x44+10*x54<=3500; 100*x13+100*x14+100*x15+0.6*x25+20*x35+35*x45+10*x55<=3500; 50*x11+0.3*x21+30*x33+75*x43+40*x52<=4000; 50*x11+50*x12+0.3*x22+30*x33+75*x43+40*x52<=4000; 50*x11+50*x12+50*x13+0.3*x23+30*x33+75*x43+40*x52<=4000; 50*x12+50*x13+50*x14+0.3*x24+30*x34+75*x44+40*x54<=4000; 50*x13+50*x14+50*x15+0.3*x25+30*x35+75*x45+40*x55<=4000; 400*x11+3*x21<=15000; 400*x12+3*x22<=15000+950*x11+7.5*x21+360*x31+600*x41+400*x51+6.8*(3500-100*x11-0.6 *x21-20*x31-35*x41-10*x51)+7.0*(4000-50*x11-0.3*x21-30*x31-75*x41-40*x51); 400*x13+3*x23<=950*x11+7.5*x21+360*x31+600*x41+400*x51+6.8*(3500-100*x11-0.6*x21-2 0*x31-35*x41-10*x51)+7.0*(4000-50*x11-0.3*x21-30*x31-75*x41-40*x51)+1350*x11+950*x12 +7.5*x21+360*x31+600*x41+400*x51+6.8*(3500-100*(x11+x12)-0.6*x21-20*x31-35*x41-10*x5 1)+7.0*(4000-50*(x11+x12)-0.3*x21-30*x31-75*x41-40*x51);