线性规划图解法几何意义

《线性规划图解法几何意义》由会员分享，可在线阅读，更多相关《线性规划图解法几何意义（59页珍藏版）》请在金锄头文库上搜索。

1、第1章 线性规划及其扩展,第1节 线性规划问题及其数学模型 第2节 线性规划问题的几何意义 第3节 单纯形法 第4节 单纯形法的计算步骤 第5节 单纯形法的进一步讨论 第6节 应用举例,1.3线性规划问题的标准形式,(其中bi0(i=1,2,.,m),称下列形式为线性规划问题的标准形式:,目标函数求极大,约束条件为等式,决策变量及右边常数项为非负,线性规划问题的几种表示形式,用向量表示为：,则标准形式的矩阵表示：,若令,A称为系数矩阵,b称为资源向量,C称为价值向量,X称为决策变量向量,用矩阵表示为：,非标准形式化为标准形式的方法,1.当目标函数为求极小值,即 min z=c1x1+c2x2+

2、.+cnxn,因为求min z 等价于max (-z),故可令,则目标函数化为:,2.当右端项 bi0时,只需将等式或不等式两端同乘(-1),则右端项必大于0,3.当约束条件为 ai1x1+ai2x2+.+ainxnbi,引入一个变量xn+i0,可使成为等式即 ai1x1+ai2x2+.+ainxnxn+ibi,变量xn+i称为松弛变量,4. 当约束条件为ai1x1+ai2x2+.+ainxnbi时,则引入一个变量xn+i0,可使不等式成为等式,即 ai1x1+ai2x2+.+ainxnxn+ibi,变量xn+i称为剩余变量,5.当变量xi为无约束的变量时,则我们引入两个变量,令:,将其代入线

3、性规划模型中,6.当变量xi0时,则令,再代入线性规划模型中,例3 将例1的数学模型化为标准形,该线性规划问题加入三个松驰变量x3,x4,x50后：,例4 将下述线性规划问题化为标准形,解：分以下步骤进行处理,(1)令z= -z，把求min z 改为求max z; (2) 在第一个约束不等式号的左端加入松弛变量x4； (3) 在第二个约束不等式号的左端减去剩余变量x5； (4)用x6-x7替换x3，其中x6，x70,即可得到该问题的标准形.,得原问题的标准形为：,1.4 线性规划问题的解的概念,1.可行解 2.基 3.基可行解 4.可行基,一. 线性规划问题解的概念,线性规划问题,1.可行解:

4、,满足线性规划问题的约束条件的解X=(x1，x2，.，xn ) T称为线性规划问题的可行解。,2.可行域:,全部可行解构成的集合称为可行域。,3.最优解:,使目标函数达到最优的可行解称为最优解。,4.基:,设系数矩阵Amn(nm)其秩为m,B是矩阵A中的一个mm阶的满秩子矩阵,称B是线性规划问题的一个基。,一. 线性规划问题解的概念（2）,=(P1,P2,.,Pm),B中的每一列向量Pj(j=1,2,.m)称为基向量,基向量：,与基向量Pj的对应的变量xj 称为基变量,基变量：,非基变量：,线性规划中的其余变量称为非基向量,5.基解,设X是（LP）的约束方程AX=b的一个解，B是一个基，若X中

5、对应基B的非基变量取值全为零，则称X为(LP)关于基B的基解，记作X(B),不妨设基为,基解的个数不会超过 个,一. 线性规划问题解的概念（3）,可证明:一个基可以而且唯一地确定一个基解.,6.基可行解：,若基解X(B)满足非负条件X(B)0，则称基解X(B)为基可行解,7.基最优解：,若基可行解X(B)是(LP)的最优解,则称X(B)为(LP)的基最优解.,最优基：,基最优解对应的可行基B称为最优基.,可行基：,基可行解对应的基B称为可行基.,注:基解没有X0的限制,故基解不一定是可行解.,X(B)=,一. 线性规划问题解的概念（4）,8.退化解：,若基本可行解X的所有基变量的值均大于0，则

6、称X是非退化的，否则称X为退化的。,若(LP)的所有基本可行解都是非退化的, 则称线性规划问题是非退化的.,二. 例题,考虑线性规划问题：,约束方程的系数矩阵A,很显然A中的后3列是线性无关的，它们构成一个基,基B1对应的变量x3,x4,x5是基变量, x1,x2是非基变量,二. 例题（2）,若令：,得,该解是对应B1的基解，它是基可行解，B1是可行基；,如取,是（LP）的一个基，,若令：,基B2对应的变量x1,x2,x3是基变量， ,x4,x5是非基变量,得,该解是对应B2的基解，它不是基可行解，B2不是可行基；,三. 线性规划问题解的关系图,AX=b的解,基解,若非基变量为0,基可行解,基

7、最优解,B是A的m阶子矩阵,基B,若|B|0,可行基B,当B-1b0,最优基B,若基变量取非负,若对应目标函数 值最优,非可行解,三. 线性规划问题解的关系图（2）,可行解,基可行解,基解,基,可行基,最优基,第2节 线性规划问题的几何意义,2.1 基本概念 2.2 几个定理,一.凸集与顶点,凸集:,如果集合K中任意两个点X(1),X(2),其连线上的所有点也都是集合K中的点,则称集合K为凸集.,或K=X|X=X(1)+(1-)X(2), X(1)K,X(2)K,01,定理: D xRn| Ax=b,x0是凸集,顶点:凸集K中满足下列条件的点X称为顶点:如 果K中不存在任何两个不同的点X1,X

8、2,使X 成为这两个点连线上的一个点.,定理: 有限个凸集的交集还是凸集,凸组合:设,是n维欧氏空间中的k个点,则称X是 的凸组合,凸集的概念：,凸集,凸集,不是凸集,顶点,不是凸集,二.几个基本定理,定理1,若线性规划问题存在可行解,则问题的可行域是凸集.,定理2,若线性规划问题有非零可行解，则其必有基可行解。,定理4,若线性规划问题有最优解，一定存在一个基可行解是最优解。,定理3,线性规划问题的基可行解X对应线性规划问题可行域(凸集)的顶点.,引理1,线性规划的可行解X(x1,x2,xn)T为基可行解的充要条件是X的正分量所对应的系数列向量是线性无关的。,第3节 单 纯 形 法,一. 单纯

9、形法迭代的基本思想,开始于某一个可行基及其对应的基可行解，从一个基可行解迭代到另一个基可行解，并且使目标函数值不断增大，经过有限步必能求得线性规划问题的最优解或者判定线性规划问题无有界的最优解（无界解）。,二. 单纯形法引例,考虑线性规划问题：,约束方程的系数矩阵A,很显然A中的后3列是线性无关的，它们构成一个基,基B对应的变量x3,x4,x5是基变量，则,二. 单纯形法引例（2）,即：,将它们代入目标函数中得,令非基变量x1=x2=0,得目标值 z0 一个基可行解 X(0)(0,0,8,16,12),为了使目标函数能更大，让x2变成基变量，原基变量 的x3，x4，x5要有一个变为非基变量,当

10、x1=0,由最上式得,从上式可看出，当x2=3仍可保证所有变量非负， 并使目标函数增大,二. 单纯形法引例（3）,为了得到以x3,x4,x2为基变量的一个基可行解，则对左边方程中的x2与x5互换,得,再令非基变量x1=x5=0,得目标值 z9 一个基可行解 X(0)(0,3,2,16,0),为了使目标函数能更大，让x1变成基变量，原基变量 的x3，x4，x2要有一个变为非基变量,目标函数变为,二. 单纯形法引例（4）,这样如此下去，可得,X(2)(2,3,0,8,0),为了使目标函数能更大，让x1变成基变量，原基变量 的x3，x4，x2要有一个变为非基变量,此时目标函数变为,X(3)(4,2,

11、0,0,4),由于目标函数中的变量系数都小于等于0， 所以 X(3)（4,2,0,0,4)为最优解， 最优值z14,下面从几何角度分析一下最优解的寻求过程：,几何意义：顶点转移，目标增大,三. 单纯形法原理,1.确定初始基可行解：,对标准型的LP问题,在约束条件(1.1)的变量的系数矩阵中总会存在一个单位矩阵。,(2)当线性规划的约束条件都为号时，其松弛变量对应的系数列向量构成的矩阵即为单位阵；,(3)当线性规划的约束条件为或的情况，引入人工变量后也可实现。,(1)系数矩阵中可以直接观察得到一个单位子矩阵；,三. 单纯形法原理（2）,2. 从一个基可行解转换为相邻的基可行解：,定义：两个基可行

12、解称为相邻的，如果他们之间变换且仅变换一个基变量。,设初始基可行解为：,可知：,其对应的系数矩阵的增广矩阵为：,三. 单纯形法原理（3）,易得：,(1.3)+(1.4) (0), 得,令：,显然：,为使X(1)成为可行解，令：,可证明:将(1.6)式代回到X(1)中,X(1) 为基可行解，此时完成了从一个基可行解到另一个与其相邻的基可行解的转换。,三. 单纯形法原理（4）,证明：将与变量 x1,xl-1,xl+1,xm,xj对应的列向量，经重新排列后加上b列有如下形式：,因为 P1,P2, ,Pl-1， Pj,Pl+1,Pm 线性无关，故X(1)为基可行解。,三. 单纯形法原理（5）,3.最优

13、性检验与解的判别：,将2中的基可行解X(0)与X(1)分别代入目标函数，得,称为检验数,三. 单纯形法原理（6）,(1)当所有的j0时 ，现行基可行解为最优解； 当所有的j0时 ，该线性规划问题有唯一最优解； 当所有的j0，且对某个非基变量xk，有k=0,该线性规划问题有无穷多最优解。,(2)当存在某个j0且对应的列向量Pj 0时，该线性规划问题有无界解；,(4)对线性规划问题无可行解的判别将在后面讨论。,(2)当存在某个j0且对应的列向量Pj 中有正分量时，说明目标函数值还可以增大，需要进行基变换；,第 4 节 单 纯 形 法的计算步骤,一. 单纯形法的计算步骤,第一步：求初始基可行解，列出

14、初始单纯形表,首先写出关于价值系数的表：（非单纯形表）,一. 单纯形法的计算步骤（2）,将基变量下方的价值系数通过变换化为零，得初始单纯形表,一. 单纯形法的计算步骤（3）,第二步：最优性检验,(1)当所有的j0时 ，现行基可行解为最优解； 当所有的j0时 ，该线性规划问题有唯一最优解； 当所有的j0，且对某个非基变量xk，有k=0,该线性规划问题有无穷多最优解。,(2)当存在某个j0且对应的列向量Pj 0时，该线性规划问题有无界解；,(3)当存在某个j0且对应的列向量Pj 中有正分量时，说明目标函数值还可以增大，需要进行基变换。,一. 单纯形法的计算步骤(4),第三步：换基迭代,(1)确定进

15、基变量,选择检验数最大的非基变量为进基变量,k=max j| j0,j=1,2,.,n,则xk为进基变量,(2)确定出基变量,根据下列原则确定出基变量,则l所对应的基变量xl为出基变量,元素alk为轴心项(或称为主元素),(3)以alk为轴心项进行换基迭代,即利用矩阵的初等行变换,把元素alk所在的列化为单位向量.得到新的单纯形表,一. 单纯形法的计算步骤（5）,第四步：重复第二、三步，一直到计算结束为止。,二单纯形法 例1(1),例 用单纯形法解下列线性规划,解:,将原问题化为标准形为：,得单纯形初表为:,二单纯形法 例1(2),T(B1),x3,x4,x2,-z,2,1 0 1 0 -1/2,16,4 0 0 1 0,3,0,1,0,0,1/4,-9,2,0,0,0,-3/4,T(B2),T(B2),x1,x4,x2,-z,2,1 0 1 0 -1/2,8,