1-线性规划.ppt

《1-线性规划.ppt》由会员分享，可在线阅读，更多相关《1-线性规划.ppt（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 第三节第三节 规划理论规划理论数学模型西安电子科技大学数学与统计学院 李 伟参考书目：杨启帆，谈之奕，何勇，数学建模，浙江大学出版社，2010.赵静 但琦 数学建模与数学实验，高等教育出版社一、引言 二、线性规划模型三、整数线性规划模型第一讲 规划理论及模型 四、0-1整数规划模型 五、非线性规划模型 六、多目标规划模型 七、动态规划模型一、引言 我们从2005年“高教社杯”全国大学生数模竞谈起.其中第二个问题是一个如何来分配有限资源，从而达到人们期望目标的优化分配数学模型.它在运筹学中处于中心的地位.这类问题一般可以归结为数学规划模型.赛的B题“DVD在线租赁”问题的第二问和第三问 规划模

2、型的应用极其广泛，其作用已为越来来越急速地渗透于工农业生产、商业活动、军事行为核科学研究的各个方面，为社会节省的财富、创造的价值无法估量.特别是在数模竞赛过程中，规划模型是最常见的一类数学模型.从92-06年全国大学生数模竞越多的人所重视.随着计算机的逐渐普及，它越赛试题的解题方法统计结果来看，规划模型共出现了15次，占到了50%，也就是说每两道竞赛题中就有一道涉及到利用规划理论来分析、求解.二、线性规划模型 线性规划模型是所有规划模型中最基本、最例1.（食谱问题）设有 n 种食物，各含 m 种营养素，第 j 种食物中第 i 种营养素的含量为 aij,n 种食物价格分别为c1,c2,cn，请确

3、定食谱中n 种食物的数量x1,x2,xn，要求在食谱中 m 种营养素简单的一种.2.1 线性规划模型的标准形式 的含量分别不低于b1,b2,bm 的情况下，使得总的费用最低.首先根据食物数量及价格可写出食谱费用为 其次食谱中第 i 种营养素的含量为 因此上述问题可表述为：解 上述食谱问题就是一个典型的线性规划问题，上述食谱问题就是一个典型的线性规划问题，寻求以线性函数的最大（小）值为目标的数学模寻求以线性函数的最大（小）值为目标的数学模型型.它是指在一组线性的等式或不等式的约束条件下，它是指在一组线性的等式或不等式的约束条件下，线性规划模型的三种形式线性规划模型的三种形式 一般形式 目标函数

4、价值向量 价值系数 决策变量右端向量系数矩阵非负约束自由变量 规范形式 标准形式 三种形式的LP问题全都是等价的，即一种形式的LP可以简单的变换为另一种形式的LP，且它们有相同的解.以下我们仅将一般形式化成规范形式和标准形式.用矩阵向量符号，可更简洁的表示标准线性规划问题：用矩阵向量符号，可更简洁的表示标准线性规划问题：目标函数的转化目标函数的转化 xoz-z约束条件和变量的转化约束条件和变量的转化 为了把一般形式的LP问题变换为规范形式，我们必须消除等式约束和符号无限制变量.在一般形式的LP中，一个等式约束可用下述两个不等式约束去替代 这样就把一般形式的LP变换为规范形式.对于一个无符号限制

5、变量 ，引进两个非负变量 和 ，并设为了把一般形式的LP问题变换为标准形式，必须消除其不等式约束和符号无限制变量.对于一个不等式约束代替上述的不等式约束.对符号无限制变量的处理可按上述方法进行.可引入一个剩余变量 ，用 对于不等式约束 代替上述的不等式约束 这样就把一般形式的LP变换为标准形式.可引入一个松弛变量，用运输问题运输问题例2.设要从甲地调出物资2000吨，从乙地调出物 资1100吨，分别供给A地1700吨、B地1100吨、C假定运费与运量成正比.在这种情况下，采用不地200吨、D地100吨.已知每吨运费如下表所示.同的调拨计划，运费就可能不一样.现在问：怎样才能找出一个运费最省的调

6、拨计划？1572521甲15375151乙DCBA表 1.1销地运费产地乙甲DCBA解一般的运输问题可以表述如下一般的运输问题可以表述如下：数学模型：数学模型：若其中各产地的总产量等于各销地的总销量，若其中各产地的总产量等于各销地的总销量，即即 类似可将一般的线性规划问题转化为其标准类似可将一般的线性规划问题转化为其标准否则，称为不平衡的运输问题，包括：否则，称为不平衡的运输问题，包括：，则称该问题为平衡的运输问题，则称该问题为平衡的运输问题.总产量总产量总销量总销量 或或 总产量总产量总销量总销量.形式，我们总可以通过引入假想的销地或产地，形式，我们总可以通过引入假想的销地或产地，将不平衡的

7、运输问题转化为平衡的运输问题将不平衡的运输问题转化为平衡的运输问题.从从而，我们的重点就是解决平衡运输问题的求解而，我们的重点就是解决平衡运输问题的求解.显然，运输问题是一个标准的线性规划问题，显然，运输问题是一个标准的线性规划问题，因而当然可以运用单纯形方法求解因而当然可以运用单纯形方法求解.但由于平衡的但由于平衡的运输问题的特殊性质，它还可以用其它的一些特殊运输问题的特殊性质，它还可以用其它的一些特殊方法求解，其中最常用的就是图解法，该方法将单方法求解，其中最常用的就是图解法，该方法将单纯形法与平衡的运输问题的特殊性质结合起来，很纯形法与平衡的运输问题的特殊性质结合起来，很方便地实行了运输

8、问题的求解方便地实行了运输问题的求解.针对标准形式的线性规划问题，其解的理论分析已经很完备，在此基础上也提出了很好的算 单纯形方法单纯形方法是线性规划问题的最为基础、也法单纯形方法及其相应的变化形式（两阶段2.2 线性规划模型的求解 法，对偶单纯形法等）.是最核心的算法。它是一个迭代算法，先从一个特殊的可行解（极点）出发，通过判别条件去判断该可行解是否为最优解（或问题无解），若不是最优解，则根据相应规则，迭代到下一个更好的可行解（极点），直到最优解（或问题无解）.然后在实际应用中，特别是数学建模过程中，遇到线性规划问题的求解，我们一般都是利用现有的软件进行求解，此时通常并不要求线性规划问题是标

9、准形式.比较常用的求解线性规划模型的软件包有LINGO和LINDO.(一一)线性规划的解线性规划的解 n可行解与最优解可行解与最优解 满足约束条件（即满足线性约束和非负约束）的一组变量为可行解。所有可行解组成的集合称为可行域。使目标函数最大或最小化的可行解称为最优解。n基本解与基本可行解基本解与基本可行解 在线性规划问题中，将约束方程组的mn阶矩阵A写成由n个列向量组成的分块矩阵 如果B是A中的一个m阶的非奇异子阵，则称B为该线性规划问题的一个基。不失一般性，不妨设则称 为基向量，与基向量相对应的变量 为基变量，而其余的变量 为非基变量。如果 是方程组 的解,则 就是方程组 的一个解，它称之为

10、对应于基B的基本解，简称基解。满足非负约束条件的基本解，称为基本可行解。对应于基本可行解的基，称为可行基。线性规划问题的以上几个解的关系，可用下图来描述：线性规划问题的求解方法线性规划问题的求解方法单纯形法单纯形法 （一）单纯形表（一）单纯形表 根据以上讨论，令 则 基变量 ，非基变量 ，则有 变形得相应地，记目标函数记为则对应于基B的基本解为n最优解的判定条件最优解的判定条件 当 时，则由目标函数式可看出：对应于B的基本可行解为最优解，这时，B也被称为最优基。由于 与 等价，故可得。n最优解的判定定理最优解的判定定理 对于基B，若 ，且 ,则对应于基B 的基本解为最优解，B为最优基。在上式中

11、，称系数矩阵 为对应于基B的单纯形表，记为T(B)。或对目标函数与约束不等式运用矩阵变形得如果记以及则(二二)单纯形法的计算步骤单纯形法的计算步骤 第第1步步，找出初始可行基，建立初始单纯形表。第第2 2步步，判别检验所有的检验系数 （1）如果所有的检验系数 ,则由最优性判定定理知，已获最优解，即此时的基本可行解就是最优解。（2）若检验系数中，有些为正数，但其中某一正的检验系数所对应的列向量的各分量均非正，则线性规划问题无解。（3）若检验系数中，有些为正数，且它们所对应的列向量中有正的分量，则需要换基、进行迭代运算。第第3 3步步，选主元。在所有大于零的检验数中选取最大的一个b0s，对应的非基

12、变量为xs，对应的列向量为若则确定brs为主元项。第第4 4步步，在基B中调进Ps，换出Pjr，得到一个新的基 第第5 5步步，在单纯形表上进行初等行变换，使第s列向量变为单位向量，又得一张新的单纯形表。第第6 6步步，转入上述第2步。例例1：用单纯形方法求解线性规划问题 解解：首先引入松弛变量 ，把原问题化为标准形式 具体步骤如下：第1步，确定初始单纯形表5.1.1。x1x2x3x4-z02300 x3121310 x492101 第2步，判别。在初始单纯形表中b01=2,b02=3，所以B1不是最优基，进行换基迭代。第3步，选主元。根据选主元法则，确定主元项 。第4步，换基，得一新基 。表

13、5.1.1 第5步，进行初等行变换，得B2下的新单纯形表x1x2x3x4-z-1210-10 x241/311/30 x455/30-1/31 第6步，因检验系数有正数b01=1，重复以上步骤可得对应于 B3=p2,p3的单纯形表，检验各检验数可知得最优解X1=3,X2=3,X3=0,X4=0:目标函数最大值为 Z=15。x1x2x3x4-z-1500-4/5-3/5x23012/5-1/5x1 310-1/53/5表5.1.2表5.1.3用用MATLAB优化工具箱解线性规划优化工具箱解线性规划min z=cX 1、模型：命令：1 x=linprog（c，A，b）2 x,fval=linpro

14、g（c，A，b）c=-2-3;A=1 2;4 0;0 4;b=8;16;12;x f=linprog(c,A,b)x=4.000 2.000f=-14.000用用MATLAB优化工具箱解线性规划优化工具箱解线性规划命令：1 x=linprog（c，A，b，Aeq,beq）2 x,fval =linprog（c，A，b，Aeq,beq）2、模型：min z=cX 注意：若没有不等式：存在，则令A=，b=.3、模型：min z=cX VLBXVUB命令：1 x=linprog（c，A，b，Aeq,beq,VLB，VUB）2 x=linprog（c，A，b，Aeq,beq,VLB，VUB,X0）注意

15、：1 若没有等式约束:,则令Aeq=,beq=.2其中X0表示初始点 4、命令：x,fval=linprog()返回最优解x及x处的目标函数值fval.解解 编写编写M文件文件xxgh1.m如下：如下：c=-0.4-0.28-0.32-0.72-0.64-0.6;A=0.01 0.01 0.01 0.03 0.03 0.030.02 0 0 0.05 0 00 0.02 0 0 0.05 00 0 0.03 0 0 0.08;b=850;700;100;900;Aeq=;beq=;vlb=0;0;0;0;0;0;vub=;x,fval=linprog(c,A,b,Aeq,beq,vlb,vub)x=1.0e+004*3.5000 0.5000 3.0000 0.0000 0.0000 0.0000fval=-2.5000e+004