数学建模之规划问题

一、线性规划

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标准形式：

3、可以转化为线性规划的问题

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

-来源网络，仅供个人学习参考

解：作変量変换u1xi|xi||x|xi,vii,i1,2,3,4,并把新变量重新排序成一维变量22uyu1,v,u4,v1,,v4，则可把模型转化为线性规划模型

TT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、一般整数规划模型

目标函数： 约束条件：

-来源网络，仅供个人学习参考

例：指派问题的数学模型(0-1型整数规划)

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

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

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

利用匈牙利算法、拍卖算法等求解出最优解。

三、非线性规划 1、简介 目标函数或约束条件中包含非线性函数的规划问题为非线性规划问题。 1.1非线形规划模型的构成 决策变量、目标函数、约束条件。 1.2非线性规划的应用模型 （1）存贮模型 （2）飞行管理问题 （3）森林救火 （4）抽水费用最小问题 （5）钢管下料问题 （6）投资决策问题 （7）供应与选址问题 （8）广告的费用及其效用 2、非线性规划的模型 一般形式： 其中：xx1,,xn为模型的决策变量。 TMatlab中非线性规划的数学模型 其中：f(x)是标量函数；A,b,Aeq,beq,lb,ub是相应维数的矩阵和向量；c(x),cex(x)是非线性向量函数。

3、罚函数法

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

取一个充分大的数M>0，构造函数 -来源网络，仅供个人学习参考

G(x)H(x)（或p(x,M)f(x)MsummaxMsumminM||km(x)||,这里

00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）如果非线性规划问题要求实时算法，则可用罚函数法，但计算精度较低。 2）如果非线性规划问题不要求实时算法，但要求精度高，可使用Lingo软件编程求解或使用Matlab的fmincon命令求解。

四、目标规划 1、简介 1.1求解目标规划的思路 （1）加权系数法 为每一目标赋一个权系数，把多目标模型转化成单一目标的模型。但困难是要确定合理的权系数，以反映不同目标之间的重要程度。 （2）优先等级法 将各目标按其重要程度不同的优先等级，转化为单目标模型。 （3）有效解法 寻求能够照顾到各个目标，并使决策者感到满意的解。由决策者来确定选取哪一个解，即得到一个满意解。但有效解的数目太多而难以将其一一求出。 1.2建立目标规划的条件 （1）正、负偏差变量。 （2）绝对（刚性）约束和目标约束。 （3）优先因子（优先等级）与权系数。 1.3目标规划的目标函数 目标规划的目标函数基本三种形式为 （1）第i个目标要求恰好达到目标值，即正、负偏差变量都要尽可能地小，这时 minwidiwidi. （2）第i个目标要求不超过目标值，即允许达不到目标值，就是正偏差变量要尽可能地小，这时

（3）第i个目标要求超过目标值，即超过量不限，但必须是负偏差变量要尽可能地小，这时

1.4目标规划的模型应用

（1）求多目标下产品利润最优的决策方案。 （2）求多目标下总运费最小的运输调度方案。

-来源网络，仅供个人学习参考

2、目标规划的一般数学模型

设xj(j1,2,,n)是目标规划的决策变量，共有m个约束是刚性约束，可能是等式约束，

也可能是不等式约束。设有l个柔性目标约束，其目标规划约束的偏差为

di,di(i1,2,,l)。设有q个优先级别，分别为p1,p2,,pq。在同一个优先级pk中，有

,l)。目标规划模型的一般数学表达式如下

,wki(i1,2,不同的权重，分别记为wki可用序贯算法求解目标规划。

3、数据包网络分析（DEA） 3.1适用范围 DEA特别适用于具有多输入多输出的复杂系统，如技术进步、技术创新、资源配置、金融投资等领域，特别对非单纯利益公共部门，如学校、医院、某些文化设施的评价方面。 3.2特点 1）DEA以决策单位各输入/输出的权重为变量， 1）数据包络分析的C2R模型 设有n个DMU，每个DMU都有m种投入和s种产出，设x（iji1,（ r1,的第i种投入量，yrj（第i种投入的权值，urr1,,m;j1,,n）表示第j个DMU

,m)表示

,s；j1,,n）表示第j个DMU的第r种产出量，vi(i1,,s）表示第r种产出的权值。 向量Xj,Yj(j1,则Xj(x1j,x2j,,n)分别表示决策单元j的输入和输出向量，v和u分别表示输入输出权值向量，,xmj)T，Yj(x1j,x2j,,xsj)T,u(u1,u2,,um)T，v(v1,v2,,vS)T。 定义决策单元j的效率评价指数为 评价决策单元j0效率的数学模型为 maxuTYj0vXj0T,（1） uTYj1,j1,2,,n,Ts..tvXju0,v0,u0,v0.通过Charnes?Cooper变换：tv,tu,t规划问题

-来源网络，仅供个人学习参考

1可以将模型（1）转化为等价的线性

(vTXj0)

对于C2R模型，有如下定义：

（1）若线性规划问题的最优目标vj01,则称决策单元j0是弱DEA有效的。

（2）若线性规划问题存在最优解*0,*0,并且其最优目标值Vj01，则称决策单元j0是EDA有效的。

-来源网络，仅供个人学习参考