第7章线性规划

《第7章线性规划》由会员分享，可在线阅读，更多相关《第7章线性规划（94页珍藏版）》请在文档大全上搜索。

1、第7章 线形规划线性规划是处理线性目标函数和线性约束的一种颇有成效的方法。苏联数学家康特罗维 奇等在1939年就提出了解决下料问题和运输问题的方法，但是，直到1947年美国数学家 GBDantzig发表了求解一般线性规划问题的方法单纯形法之后，其理论和算法才趋于成熟。 目前线性规划的技术已广泛应用在军事、经济、工业、农业、教育、商业和社会科学等许多方面。能得到如此广泛应用的主要原因是：可以购买到能解大规模问题(变量可多至几万个)且高度可靠的商品程序，以及线性规划能容易地处理数据变动问题(灵敏度分析)。第7章 线形规划美国杂志Interfaces l976年11月的一份述评指出，线性规划已成为所

2、有最优化方法中最常用的技术(占74)，1979年10月出版的美国科学新闻曾报导：用于科学计算的计算机时间中，有关线性规划问题的计算约占四分之一左右。而且在运筹学其它分支中的许多问题也可以化为线性规划来求解。第7章 线形规划 虽然大多数实际工程技术问题是非线性问题，但是，了解线性规划是十分有益的。其基本原因有四点：首先，通常可用线性化的办法将一个非线性问题简化为线性问题，并用线性规划技术解之；其次，线性规划常用作开发一些较复杂的非线性规划算法的基础，第三，线性规划的学习为引入更深的数学规划概念提供了合乎逻辑的进展，第7章 线形规划71 基本概念 求设计变量X=x1, x2, xnT， 使目标函数

3、 minf= c1x1+c2x2+cnxn且满足约束条件 （Subected to）:要求 un 线性规划维数um 线性规划阶数 uPj=a1j, a2j, amjT-系数列向量 mnmmnnTmaaaaaaaaapppA21222211121121,可行解 满足式的X=x1, x2, xnT称为可行解，也可称为可行点。条件x1,x2, xn0是不能忽略的； 有时，尽管式有解，a11x1+a12x2+a1nxn =b1a21x1+a22x2+a2nxn =b2 am1x1+am2x2+amnxn =bm 但这些解如不满足x1,x2, xn0，还是没有容许解。当然式(2)本身就没有解的情况也是有

4、的，我们称这种约束条件是矛盾的,或不相容的。可行集合 所有满足约束条件的解的集合称可行集合，也就是可行区。一个可行解可以看成为可行集合(或可行区)中的一个点。矛盾的约束条件所形成的可行集合为空集. 我们称这种约束条件是矛盾的，或是不相容的。没有一个可行的集合，称为空集。 我们知道以设计变量为坐标，组成n维空间，在n维空间的一个点就代表一个设计方案。每一个不等式约束方程在n维空间就形成一个超曲(平)面。这些超曲平面合成一个所谓约束界面。通常约束界面把n维空间分为两大区域：一是可行的区域，另一是不可行的区域。在可行区域里，每一点都代表一个可以接受的设计方案，是一个可行点。 凸集与凸集顶点 设可行的

5、区域内的一个集合，若其中任意两点x(1)和x(2) 的连线都在集合中，则称这种集合是n维欧氏空间的一个凸集 。有了凸集概念后，我们再引出一个凸集顶点(或叫极点)的概念。如上所述，在凸集内若有两点，则这两点连线上的点必在凸集内。现在再倒过来提一个问题：在凸集上有一点能否找到凸集中另外两点，使已给定的那一点成为这两点连线上的点。如根本找不到或根本不存在这两点，则那一点叫“顶点”。凸集顶点的概念对于用线性规划寻找使目标函数为最小(或最大)的自变量x有什么好处呢?数学上证明结果表明，使f 的最小 (或最大) 值，一定在可行区凸集的某个顶点上。这就是说，只要从为数有限的顶点中去寻找就可以了。 72 两个

6、重要性质凸集与顶点和线性规划的两个重要性质有密切关系； (1)线性规划的可行域是一个凸集； (2)线性规划的基本定理 线性规划若存在可行点，则必存在可行域的顶点；若存在最优点，则至少有一个顶点是最优点。 上述基本定理的重要意义是： (1) 保证了顶点的存在性; (2)把一般要从无限个可行点中寻找最优点的问题简化为仅在有限个顶点中确定一个最优点的问题。 基本可行解基本可行解 若一个m阶线性规划问题有一个可行解，而这个解中大于0的分量又不多于m个，并且对应于非0的分量的系数向量之间是线性无关的，则称这个可行解为基本可行解当然，一般来说，一个问题的基本可行解不是唯一的，事实上这个问题的基本可行解也不

7、只这一个。 基本变量基本变量 基本可行解中那些大于0的分量相对应的变量称为基本变量，而其余变量称为非基本变量。自然，基本变量的个数一定不大于m，非基本变量的个数不少于n-m个。 基本变量与非基本变量是相对于基本可行解来说的。脱离开基本可行解，这种提法是无意义的。 73 线性规划的标准形式 为了论述上的方便与求解线性规划的单纯形法的需要，我们引入下面线性规划的标准形式:求设计变量X=x1, x2, xnT， 使目标函数 minf= c1x1+c2x2+cnxn且满足约束条件 （Subected to）: 用矩阵和向量表示 目标函数 f=CTX s.t. AX=B X0 B01 1 将等式约束的右

8、端化为非负将等式约束的右端化为非负 如果 njbj, 2 , 1, 002211jnjnjjbxaxaxa2 2 将不等式化为等式将不等式化为等式 (1) 若jnjnjjbxaxaxa2211引进”剩余变量” ,将不等式改为jjnnjnjjbwxaxaxa2211jnjnjjbxaxaxa2211引进”松弛变量” ,将不等式改为在目标函数中松驰变量的价值系数取零值，即原目标函数形式不变。注意，每添加一个剩余或松驰变量，问题就增加一维 jjnjnjjbwxaxaxa22113 化最大值问题为最小值问题化最大值问题为最小值问题 若原问题为 maxf= c1x1+c2x2+cnxn 则可引入新目标函

9、数f=-f，而约束条件不变。这样原问题就变为等价的标准形式，目标函数为 min d= d1x1+d2x2+dnxn ci=-di74 单纯形法 线性规划的典范形式若在标准形式(2.5)的m个约束方程中有m个特殊变量，它们每一个在某个方程中的系数为1，而在其它的方程中系数为零，则称这样的约束方程组为典范形式。例如以首m个变量为特殊变量的典范形式是： 0,2111,11,1111, 11nmnmnmmmmrnrnmmrrnnmmxxxbxaxaxbxaxaxbxaxax典范形式的优点是可以简单地令其m个特殊变量为基本变量，而其余(n-m)个变量为非基本变量。置非基木变量的值为零后，立即可得出基本变

10、量的值，从而求得一个基本可行解。例如典范形式(1)的一个基本可行解为： 或 n ,m,mjxm,ibxjii210210bX1 单纯形法的基本思想 单纯形法是一种迭代方法，它是从所有基本可行解中的一个较小部分里，通过迭代过程选出最优解的有效方法 。(1)迭代过程的一般描述 a 将线性规划化为典范形式(后面将给出简捷的转化方法)，从而可立即得到一个初始基本可行解X(0) (初始顶点)，以它作为迭代过程的出发点，它的目标函数值为 f(X(0)b 寻找一个基本可行解X(1) ，使f(X(1) f(X(0) 。由于寻找的范围限制在使目标函数值不超过f(X(0)的那些基本可行解内，所以搜索的效率很高。寻

11、找的方法是通过消去法把产生X(0)的典范形式化为产生X(1)的典范形式。 c 继续寻找较好的基本可行解X(2)，X(3)， X(4)，使目标函数值不断改进，即f(X(1) f(X(2) f(X(3) 。当一个基本可行解再也不能被别的基本可行解改进时，它就是所谓的最优解。 可行域的每一个顶点与一个基本可行解相对应，而线性规划的最优解必存在于顶点之中，只需在基本可行解中找出最优解。基本可行解个数不超过 )!mn( !m! n(2)由一个典范形式化为另一个典范形式的迭代过程 每次迭代是为了寻找使目标函数值更小的新基本可行解。为叙述方便起见，设迭代前的典范形式是式(1)，从而可得初始基本可行解为： 基