数学建模之规划问题.doc

一、线性规划1.简介1.1适用情况 用现有资源来安排生产，以取得最大经济效益的问题。如：（1）资源的合理利用（2）投资的风险与利用问题（3）合理下料问题（4）合理配料问题（5）运 输 问 题（6）作物布局问题（7）多周期生产平滑模型（8）公交车调度安排1.2建立线性规划的条件（1）要求解问题的目标函数能用数值指标来反映，且为线性函数；（2）要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述。1.3线性规划模型的构成决策变量、目标函数、约束条件。2、一般线性规划问题数学标准形式：目标函数：约束条件：matlab标准形式： 3、可以转化为线性规划的问题例：求解下列数学规划问题解：作変量変换并把新变量重新排序成一维变量，则可把模型转化为线性规划模型其中：。利用matlab计算得最优解：最优值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项工作，需花费单位时间，如何分配工作才能使花费总时间最少？模型的建立引入0-1变量指派问题的数学模型为利用匈牙利算法、拍卖算法等求解出最优解。三、非线性规划1、简介目标函数或约束条件中包含非线性函数的规划问题为非线性规划问题。1.1非线形规划模型的构成决策变量、目标函数、约束条件。1.2非线性规划的应用模型（1）存贮模型（2）飞行管理问题（3）森林救火（4）抽水费用最小问题（5）钢管下料问题（6）投资决策问题（7）供应与选址问题（8）广告的费用及其效用2、非线性规划的模型一般形式： 其中：为模型的决策变量。Matlab中非线性规划的数学模型其中：f(x)是标量函数；A,b,Aeq,beq,lb,ub是相应维数的矩阵和向量；c(x),cex(x)是非线性向量函数。3、罚函数法利用罚函数法可将非线性规划问题的求解转化为求解一系列无约束极值问题。问题取一个充分大的数M0，构造函数（或这里可直接利用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个目标要求恰好达到目标值，即正、负偏差变量都要尽可能地小，这时.+ 格满足的等式约束和不等式约束，66666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666（2）第i个目标要求不超过目标值，即允许达不到目标值，就是正偏差变量要尽可能地小，这时（3）第i个目标要求超过目标值，即超过量不限，但必须是负偏差变量要尽可能地小，这时1.4目标规划的模型应用（1）求多目标下产品利润最优的决策方案。（2）求多目标下总运费最小的运输调度方案。2、目标规划的一般数学模型设是目标规划的决策变量，共有m个约束是刚性约束，可能是等式约束，也可能是不等式约束。设有l 个柔性目标约束，其目标规划约束的偏差为。设有q个优先级别，分别为。在同一个优先级中，有不同的权重，分别记为。目标规划模型的一般数学表达式如下可用序贯算法求解目标规划。3、数据包网络分析（DEA）3.1适用范围DEA特别适用于具有多输入多输出的复杂系统，如技术进步、技术创新、资源配置、金融投资等领域，特别对非单纯利益公共部门，如学校、医院、某些文化设施的评价方面。3.2特点1）DEA以决策单位各输入/输出的权重为变量，1）数据包络分析的CR模型设有n 个DMU，每个DMU都有m种投入和s种产出，设表示第 j个DMU的第i 种投入量，表示第 j个DMU的第r种产出量，表示第i种投入的权值，表示第r种产出的权值。向量分别表示决策单元 j 的输入和输出向量，v和u分别表示输入输出权值向量，则，。定义决策单元j的效率评价指数为 评价决策单元效率的数学模型