数学建模之规划问题[精品文档]

一、线性规划

1.简介

1.1适用情况

用现有资源来安排生产，以取得最大经济效益的问题。如： （1）资源的合理利用

（2）投资的风险与利用问题 （3）合理下料问题 （4）合理配料问题 （5）运 输 问 题 （6）作物布局问题

（7）多周期生产平滑模型 （8）公交车调度安排 1.2建立线性规划的条件

（1）要求解问题的目标函数能用数值指标来反映，且为线性函数； （2）要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述。 1.3线性规划模型的构成

决策变量、目标函数、约束条件。

2、一般线性规划问题

数学标准形式：

目标函数：

max z??cj?1njxj

?n??aijxj?bi,i?1,2,...,m,s..t?j?1约束条件：

?x?0,j?1,2,...,n.?jmatlab标准形式：

minfTx,?A?x?b,?s.t?Aeq?x?beq,?lb?x?ub.?3、可以转化为线性规划的问题

例：求解下列数学规划问题

minz?|x1|?2|x2|?3|x3|?4|x4|,??x1?x2?x3?x4??2,?s..t?x1?x2?x3?3x4??1,?1?x1?x2?2x3?3x4??.2?

解：作変量変换u1?xi?|xi||x|?xi,vi?i,i?1,2,3,4,并把新变量重新排序成一维22?u?变量y?????u1,?v?,u4,v1,,v4?，则可把模型转化为线性规划模型

mincTy,T

??u?A,?A????v??b, s..t????y?0.?T?1???1???1??1?1?T??。 1???1??1???3其中：c??1,2,3,4,1,2,3,4?;b???2,?1,??;A????2????1?????????????利用matlab计算得最优解：x1??2,x2?x3?x4?0,最优值z=2。 程序如下：

略

二、整数规划

1.简介

数学规划中的变量(部分或全部)限制为整数时称为整数规划。目前流行求解整数规划的方法一般适用于整数线性规划。 1.1整数规划特点

1）原线性规划有最优解，当自变量限制为整数后，出现的情况有 ①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。 ②整数规划无可行解。

③有可行解（存在最优解），但最优解值变差。

2）整数规划最优解不能按照实数最优解简单取整获得。 1.2求解方法分类

（1）分枝定界法—可求纯或混合整数线性规划。 （2）隔平面法—可求纯或混合整数线性规划。 （3）隐枚举法—可求“0-1”整数规划。 （4）匈牙利法—解决指派问题。

（5）蒙特卡洛法—求解各种类型规划. 1.3整数规划的应用模型 （1）固定费用的问题。 （2）指派问题。 （3）合理下料问题。 （4）流动推销员问题。 （5）生产与销售计划问题。

2、一般整数规划模型

目标函数：

max z?约束条件：

?cj?1njxj

?n??aijxj?bj,i?1,2,...,m,s..t?j?1

?x?0,j?1,2,...,n.?j例：指派问题的数学模型(0-1型整数规划)

拟分配n人去做n项工作，若分配第i人去做第j项工作，需花费cij单位时间，如何分配工作才能使花费总时间最少？ 模型的建立

?1,第i人做第j项工作，引入0-1变量xij??

?0，第i人不做第j项工作.指派问题的数学模型为

nnmin z????ci?1j?1ijxij,

?n??xij?1,i?1,2,...,n,?j?1?ns..t??xij?1,j?1,2,...,n,?i?1 ?xij?0?或?1,i,j?1,2,...,n.??利用匈牙利算法、拍卖算法等求解出最优解。

三、非线性规划

1、简介

目标函数或约束条件中包含非线性函数的规划问题为非线性规划问题。 1.1非线形规划模型的构成

决策变量、目标函数、约束条件。 1.2非线性规划的应用模型

（1）存贮模型 （2）飞行管理问题 （3）森林救火

（4）抽水费用最小问题 （5）钢管下料问题 （6）投资决策问题 （7）供应与选址问题 （8）广告的费用及其效用

2、非线性规划的模型

一般形式：

目标函数：minf(x),?h(x)?0,j?1,2,,q,约束条件：s..t?j?gi(x)?0,i?1,2,,p.

其中：x??x1,,xn?为模型的决策变量。

TMatlab中非线性规划的数学模型

minf(x),

?A?x?b,?Aeq?x?beq,? ?s..t?c(x)?0,?ceq(x)?0,???lb?x?ub.其中：f(x)是标量函数；A,b,Aeq,beq,lb,ub是相应维数的矩阵和向量；c(x),cex(x)

是非线性向量函数。

3、罚函数法

利用罚函数法可将非线性规划问题的求解转化为求解一系列无约束极值问题。 问题

minf(x),?gi(x)?0,i?1,,r, ?s..t?hj(x)?0,j?1,,s,??km(x)?0,m?1,,t.取一个充分大的数M>0，构造函数

p(x,M)?f(x)?M?max(gi(x),0)?M?min(hj(x),0)?M?|km(x)|,

i?1j?1m?1rst???G(x)???H(x)???Msummin（或p(x,M)?f(x)?Msum?max????????M||km(x)||,这

?0???0????里G(x)??g1(x),,gr(x)?,H(x)??h1(x),,hs(x)?,K(x)??k1(x),,kt(x)?,可直接

利用matlab中的max、min和sum函数），则增广目标函数P(x,M)为目标函数

的无约束极值问题minP(x,M)的最优解x即为原问题的最优解。 注意：

1）如果非线性规划问题要求实时算法，则可用罚函数法，但计算精度较低。