1-线性规划.ppt

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

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

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

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

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

6、类似可将一般的线性规划问题转化为其标准,否则，称为不平衡的运输问题，包括：,，则称该问题为平衡的运输问题.,总产量总销量 或 总产量总销量.,形式，我们总可以通过引入假想的销地或产地，,将不平衡的运输问题转化为平衡的运输问题. 从,而，我们的重点就是解决平衡运输问题的求解.,显然，运输问题是一个标准的线性规划问题，因而当然可以运用单纯形方法求解. 但由于平衡的运输问题的特殊性质，它还可以用其它的一些特殊方法求解，其中最常用的就是图解法，该方法将单纯形法与平衡的运输问题的特殊性质结合起来，很方便地实行了运输问题的求解.,针对标准形式的线性规划问题，其解的理论,分析已经很完备，在此基础上也提出了很

7、好的算,单纯形方法是线性规划问题的最为基础、也,法单纯形方法及其相应的变化形式（两阶段,2.2 线性规划模型的求解,法，对偶单纯形法等）.,是最核心的算法。它是一个迭代算法，先从一个,特殊的可行解（极点）出发，通过判别条件去判,断该可行解是否为最优解（或问题无解），若不,是最优解，则根据相应规则，迭代到下一个更好的可行解（极点），直到最优解（或问题无解）.,然后在实际应用中，特别是数学建模过程中，遇到线性规划问题的求解，我们一般都是利用现有的软件进行求解，此时通常并不要求线性规划问题是标准形式. 比较常用的求解线性规划模型的软件包有LINGO和LINDO.,(一)线性规划的解 可行解与最优解

8、满足约束条件（即满足线性约束和非负约束）的一组变量为可行解。所有可行解组成的集合称为可行域。 使目标函数最大或最小化的可行解称为最优解。,基本解与基本可行解 在线性规划问题中，将约束方程组的mn阶矩阵A写成由n个列向量组成的分块矩阵,如果B是A中的一个m阶的非奇异子阵，则称B为该线性规划问题的一个基。不失一般性，不妨设 则称 为基向量，与基向量相对应的变量 为基变量，而其余的变量 为非基变量。,如果 是方程组 的解, 则 就是方程 组 的一个解，它称之为对应于基B的基本解，简称基解。 满足非负约束条件的基本解，称为基本可行解。对应于基本可行解的基，称为可行基。,线性规划问题的以上几个解的关系，

9、可用下图来描述：,线性规划问题的求解方法单纯形法,（一）单纯形表 根据以上讨论，令 则 基变量 ，非基变量 ，则有 变形得,相应地，记 目标函数记为 则对应于基B的基本解为,最优解的判定条件 当 时， 则由目标函数式可看出：对应于B的基本可行解为最优解，这时，B也被称为最优基。 由于 与 等价，故可得。 最优解的判定定理 对于基B ，若 ，且 , 则对应于基B 的基本解为最优解， B为最优基。,在上式中，称系数矩阵,为对应于基B的单纯形表，记为T(B) 。,或,对目标函数与约束不等式运用矩阵变形得,如果记,以及,则,(二) 单纯形法的计算步骤,第1步，找出初始可行基，建立初始单纯形表。 第2步

10、，判别检验所有的检验系数 （1）如果所有的检验系数 ,则由最优性判定定理知，已获最优解，即此时的基本可行解就是最优解。 （2）若检验系数中，有些为正数，但其中某一正的检验系数所对应的列向量的各分量均非正，则线性规划问题无解。 （3）若检验系数中，有些为正数，且它们所对应的列向量中有正的分量，则需要换基、进行迭代运算。,第3步，选主元。 在所有大于零的检验数中选取最大的一个b0s，对应的非基变量为xs，对应的列向量为 若 则确定brs为主元项。 第4步，在基B中调进Ps，换出Pjr，得到一个新的基 第5步，在单纯形表上进行初等行变换，使第s列向量变为单位向量，又得一张新的单纯形表。 第6步，转入

11、上述第2步。,例1：用单纯形方法求解线性规划问题,解：首先引入松弛变量 ，把原问题化为 标准形式,具体步骤如下： 第1步，确定初始单纯形表5.1.1。,第2步，判别。在初始单纯形表中b01=2, b02=3，所以B1不是最优基，进行换基迭代。 第3步，选主元。 根据选主元法则，确定主元项 。 第4步 ，换基，得一新基 。,表5.1.1,第5步，进行初等行变换， 得B2下的新单纯形表,第6步，因检验系数有正数b01=1，重复以上步骤可得对应于 B3=p2,p3的单纯形表，检验各检验数可知得最优解X1=3,X2=3, X3=0, X4=0:目标函数最大值为 Z=15。,表5.1.2,表5.1.3,

12、用MATLAB优化工具箱解线性规划,命令：1 x=linprog（c，A，b）,2 x, fval=linprog（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.000,f=-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= .,命令：1 x=linprog（c，A，b，Aeq,beq, VLB，VUB） 2 x=linprog（c，A，b，Aeq,beq, VLB，VUB, X0）,注意：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.03 0.02 0 0 0.05 0 0 0 0.02