《线性规划及其对偶问题修改后》由会员分享，可在线阅读，更多相关《线性规划及其对偶问题修改后（175页珍藏版）》请在金锄头文库上搜索。
1、第3章 线性规划,Linear Programming,1,线性规划(Linear Programming)是最优化方法中理论完整、方法成熟、应用最广泛的一个分支。,线性规划问题最早是前苏联学者康德洛维奇(L.V. Kantorovich)于1939年提出的。,1952年, 美国国家标准局(NBS)在当时的SEAC电子计算机上首次实现单纯形算法。,1947年G.B.Dantzig提出了单纯形方法(Simplex method),2,Linear Programming 常研究两类问题,一类是当一项任务确定后，如何统筹安排，尽量做到以最少的人力、物力资源去完成。,另一类是已有一定数量的人力、物力
2、资源，如何安排使用它们，使完成的任务(或创造的财富、利润)最多。,3,3.1 线性规划的数学模型基本原理,4,线性规划数学模型的一般形式为：,3.1.1 线性规划模型的标准形及其转化,我们常考察以下两种形式的线性规划问题：,称以下的形式为标准形式(Standard Form)：,记 ；称D标准形线性规划问题(3.3)的可行域。,5,6,简化式为：,向量形式为：,(1)极小化目标函数的问题,设目标函数为,令 ，则,尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即,7,化为标准形式线性规划问题,(2) 约束条件不是等式的问题,设约束条件为,引入松弛变量,当约束条件为,则同样
3、令 ，约束条件成为,8,松弛变量的经济意义是还有没被利用的资源。,例3.1 将以下线性规划问题转化为标准形式,将目标函数转换成极大化, 并分别对约束(1), (2)引进松弛变量x4, x5, 得到以下标准形式的线性规划问题,(3) 变量无符号限制的问题,在标准形式中, 每一个变量都有非负约束。当一个变量xj没有非负约束时(称为自由变量), 可以令,其中,即用两个非负变量之差来表示一个无符号限制的变量， 的符号取决于 和 的大小。,10,例3.2 将以下线性规划问题转化为标准形式,令 ，引进松弛变量并令 得到以下等价的标准形式,图解法的基本思想是先将约束条件加以图解，求得满足约束条件的可行域，然
4、后结合目标函数从可行域中求得最优解。,对于只有两个变量的线性规划问题，可以在二维直角坐标平面上表示线性规划问题。,3.1.2 线性规划的图解法,例3.3 求解下列线性规划问题,其中满足约束(3.4)的点 位于坐标平面上直线 靠近原点的一侧。,满足约束(3.5)的点位于坐标平面上直线 的靠近原点的一侧。,变量x1, x2 的非负约束表明满足约束条件的点同时应位于第一象限内。如图中阴影部分所示。,令z=z0为某一确定的目标函数值, 取一组不同的z0值, 在图上得到一组相应的平行线, 称为目标函数等值线。在同一条等值线上的点, 相应的可行解的目标函数值相等。在图中, 给出了z=0, z=3, z=6
5、, 等一组目标函数等值线, 对于目标函数极大化问题, 这一组目标函数等值线沿目标函数增大而平行移动的方向(即目标函数梯度方向)就是目标函数的系数向量C=(c1,c2, ,cn)；对于极小化问题，目标函数则沿-C方向平行移动。,14,目标函数等值线在平行移动过程中与可行域的最后一个交点是点，这就是线性规划问题的最优解，这个最优解可以由两直线,线性规划问题的可行域是一个凸多边形。,线性规划的可行域以及最优解具有以下性质：,1若线性规划的可行域非空，则可行域必定为一凸集。,2若线性规划有最优解，则最优解至少位于一个极点上。,在一般的n维空间中, n个变量, m个约束的线性规划问题的可行域也应具备这一
6、性质。,15,的交点求得最优解的目标函数值为：,线性规划的可行域和最优解的几种可能的情况,可行域为封闭的有界区域,(1)有唯一的最优解,(2)有一个以上的最优解,16,可行域为非封闭的无界区域,(1)有唯一的最优解；,(2)有一个以上的最优解,17,目标函数无界(即虽有可行解, 但在可行域中, 目标函数可以无限增大或无限减小), 因而没有最优解。,可行域为空集, 因而没有可行解。,18,考察标准形式(Standard Form)线性规划问题：,记 ；称 为标准形线性规划问题的可行域。,19,定义3.1.1 (线性规划的基(Basis),对于线性规划的约束条件,3.1.3 线性规划的概念与基本定
7、理,设A 的秩为m, B是A矩阵中的一个非奇异的m阶子矩阵, 则称B为线性规划的一个基矩阵, 简称为基。,设B是线性规划的一个基, 则A可以表示为A=(B, N),x也可相应地分成 ;,20,其中xB为m维向量, 称为基变量, 其分量与基B的列向量对应; xN为n-m维向量, 称为非基变量, 其分量与非基矩阵N的列对应。这时约束等式Ax=b可表示为:,或,若 取确定的值，则 有唯一的值与之对应,特别，取 ，这时有 。,21,定义3.1.2 (基解(Basic Solution)、基可行解(Basic Feasible Solution)和可行基(Feasible Basis)。,各类解的关系,
8、线性规划的解,称为线性规划与基B对应的基解。若其中B-1b0, 则称以上的基解为一基可行解, 相应的基B称为可行基。,定理3.1 设x是标准型线性规划问题的可行解。x为其基可行解的充分必要条件是: x的正分量所对应的系数列向量线性无关。,23,定理3.2 (线性规划问题几何理论基本定理),设x为标准型线性规划问题的可行解, x为其的基可行解的充分必要条件是x为可行域D的极点。,推论：标准型线性规划问题的可行域最多具有有限个极点。,证明：由基解的定义可知，标准型线性规划问题的基解个数最多为：,个,而基可行解集合只是基解集合的一个子集。,即极点集合只是基解集合的一个子集，所以极点的个数 。,24,
9、定理3.3 若标准型线性规划问题存在可行解, 则它一定存在基可行解。,定理3.4 若标准型线性规划问题存在最优解, 则必存在基可行解是最优解。,线性规划问题的各种解与其极点有着密切的关系, 特别是有下面的对应关系：,基可行解 可行域(凸集)D的极点。,3.2 单纯形方法 (Simplex Method),将顶点逐点转移。,根据LP的标准形, 从可行域中一个基本可行解(一个顶点)开始, 转移到另一个基本可行解, 同时使目标函数值逐步优化(增大); 当目标函数值达到最优值时, 问题就得到了最优解。,线性规划的基本定理表明：一个线性规划问题若有最优解, 则一定有最优的基可行解, 而且基可行解的个数不
10、会超过 个。,25,问题: 如何找到第一个基本可行解？如何判断是否为最优解？如何从一个基本可行解另一个尚未检查到的基本可行解？,最简单方法: 基解中取零的变量个数不少于n-m个, 令自由变量取值为零相应得到的解 。,由r(A)=m, 解出m个基本变量, 剩下的n-m个变量为自由取值的变量, 称为自由变量。,26,单纯形法的基本思想是: 给出一种规则, 使由标准型线性规划问题一个基可行解(极点)转移到另一个基可行解, 目标函数值是增大的, 而且两个基可行解之间的转换是容易实现的。经过有限次迭代, 即可求得所需的最优基可行解。,27,单纯形方法的经济解释,例3.4：假设某工厂生产A、B、C三种产品
11、, 每吨利润分别为4万元、1万元、5万元; 生产单位产品所需的工时及原材料如表所示。若供应的原材料每年不超过3000吨, 所能利用的劳动力年总工时不超过8000小时, 问如何制定年生产计划, 使三种产品总利润最大？,28,解：用x1, x2, x3表示三种产品A, B, C的产量, 则有线性规划问题,化为标准形式为,29,目标函数中松弛变量的价值系数为0，其经济意义是没有被利用的资源。约束条件的系数矩阵为：,30,取基矩阵(基矩阵不惟一),对应于基矩阵的基变量为,目标函数用非基变量表示为:,当工厂未做生产时 , 此时, 工时和原材料都没被利用，取,31,工厂不产生利润, z=0 , 得一个基解
12、,由于目标函数中非基变量的系数都为正, 若将非基变量变为基变量, 也就是说安排产品生产, 就可以增加工厂的利润。首先应选获利最大的产品投产, 取目标函数中系数(贡献系数)最大的非基变量转化为基变量, 本例取x3, 由,且x1=x2=0, 有,32,取,这表明生产750吨产品C, 刚好将3000吨原材料用完, 此时x5=0, 但用去工时7504=3000小时, 工时x4还有5000小时仍未被利用。得新基可行解:,从经济意义看, 3000吨原材料生产了750吨产品C,化简为:,33,即x3变为基变量, x5变为非基变量, 也称为用x3置换x5故有:,令非基变量 ，得 ，并得基矩阵:,34,约束条件
13、的系数矩阵化为:,由于目标函数中非基变量x1的系数仍然为正, 若将非基变量x1变为基变量, 也就是说增加产品A的生产, 还可以增加工厂的利润。与前面类似地推算得:,35,即,由于目标函数中非基变量的系数全为负, 这些变量的增加, 将导致工厂的利润减少。得最佳生产方案为：,36,最优解为:,最优值为:,约束条件的系数矩阵可化为:,现考查标准型线性规划问题：,设系数矩阵A的秩为m。,设 是基变量， 是非基变量，则基矩阵为 。,非基向量构成的矩阵为 。,37,3.2.1 单纯形法的计算步骤,系数矩阵A分解为A=(B, N)，其中N叫作非基矩阵。把向量x和c也分别作相应的分解,其中xB, cB表示与基
14、变量对应的m维列向量, xN, cN表示与非基变量对应的n-m维列向量。,约束方程组Ax=b可表示为,即,38,解得,代入目标函数有,原线性规划问题可表示为,39,令,则有,40,原线性规划问题又可表示为,线性规划的这种形式叫作与基变量 对应的规范式(典式)。,41,若基变量为 ，设基变量的下标集为 ，与基变量对应的规范式为：,其中, T表示非基变量的下标集, 即T=1, 2, , n S。,42,由线性规划的规范式，令非基变量 ，得到一个基解 ，,其中,当 时， 是基可行解。,在与基变量 对应的规范式中，因为 是单位向量，所以当 时,43,定义3.2.1 称 为变量xj的判别数或检验数。写成向量形式为,即,44,设x(0)是线性规划(3.6)对应于基B=(p1, p2, , pm)的基可行解。与基变量x1, x2, , xm对应的规范式中,若x(0)的全体检验数非正, 即j0, j=1, 2, , n则x(0)是(3.6)的最优解。,
