第六章线性规划基础

第六章 线性规划基础-环境系统污染控制规划的数学基础6.1 线性规划概述 线性规划是数学规划与运筹学的一个分支，是运筹学中最重要的一种数学方法。主要研究解决有限资源的最佳分配问题，即如何对有限的资源作出最佳方式的调配和最有利的使用，以便最充分地发挥资源的效能去获取最佳经济效益。 这种数学规划的方法，如果用数学语言表达，就是在一定的约束条件下，寻找目标函数的极值问题。所谓线性规划，是指约束条件为线性等式或不等式，且目标函数也是线性函数 。 生产调度问题1. 线性规划问题的提出一、线性规划及其数学模型某企业生产甲、乙两种产品，分别用 A、 B、C 3种不同的原料，每生产 1个单位的甲，需用 1个单位的 A、 1个单位的 B、 0个单位的 C，利润为 3千元；每生产 1个单位的乙，需用 1个单位的 A、 2个单位的 B、 1个单位的 C，利润为 4千元；现有 6个单位的 A、 8个单位的 B、 3个单位的 C，问企业如何安排生产，可使利润最大。产品 甲 乙x1 x2原料ABC利润11031214原料限制6832. 建模的步骤(1)明确问题的经济背景(2)设定决策变量(3)明确目标 -给出目标函数(4)明确问题的所有限制 -给出约束条件Z = 3x1 + 4x2x1 + x2 6x1 + 2x2 8x2 3x10, x2 0 每天总利润： Z = 3x1 + 4x2变量 x1 和 x2 必须满足三个条件： x1 + x2 6x1 + 2x2 8x2 3 非负性约束： x10, x2 0目标函数决策变量函数约束约束条件Max Z = 3x1 + 4x2x1 +x2 6x1 +2x2 8x2 3x10, x2 0数学模型s.t.线性规划的数学表达即求一组变量 x1 , x2 , x n ,在满足约束条件：a11x1 + a12x2 + +a 1nxnb1a21x1 + a22x2 + +a 2nxnb2 am1x1 + am2x2 + +a mnxnbmx1 , x2 , , x n 0 的情况下，使目标函数：f=c1x1+c2x2+ +c nxn 达到最大值或最小值。 Max / Min F=CXAXB 或 AX B X0 或 X 0 或 X自由其中： C=(c1,c2,c n) B=(b1,b2,b m) X=(x1,x2, ,x n)A=aij（ i=1,2, ,m； j=1,2, ,n ） 一般来说，满足约束条件的变量X=(x1,x2,x n)T有无穷多个解，求解 LP问题的目的就是从中找出一个能满足目标函数最大或最小的解，作为该 LP问题的最终决策。 决策变量、目标函数、约束条件是 LP模型的三要素，其中后两者都是关于前者的线性表达式；而 LP模型就是由最优化的目标函数和约束条件这两部分构成的。二、线性规划的图解法 线性规划的图解法，就是借助几何图形来求解线性规划问题的一种方法。 图解法的基本步骤：1.可行域的确定LP模型所有约束条件共同构成的图形，称为可行域图形。2.目标函数的等值线和最优点的确定F(0,6)x1+x2=6X1X2OB(4,2)C(2,3)E(8,0)G(0,6)Z=20Z=3x1+4x2 A(6,0)x1+2x2=8x2=3D(0,3) 可以看到：当沿法线方向平行移动直线Z=3x1+4x2至 B点时， Z值在可行域 R上就达到了最大值，从而确定 B点即为该 LP问题的 最优点。 最优点的坐标值为 最优解 。记为X*=(x1*,x2*)T,X*对应的目标函数值称为 最优值，记为 Z*。 该实例的最优解： X*=(4,2)T,Z*=20 说明最优生产方案是：生产甲产品 4件，乙产品2件，可获得最大利润 20千元。 LP问题几种可能的结果： 唯一解； 多重解； 无界解； 无可行解。 唯一解：只有一个最优点 多重解：有些 LP问题最优解可能不唯一，如 :前例中目标函数改为： max Z=x1+2x2 则目标函数等值线与约束条件 x1+2x28的边界线平行。当将等值线沿法线方向平移到 B点时，就与 R的边界线 BC段重合。这表明 BC上的每一点都使目标函数值取得同样的最大值。这时出现多重解的情形。 无界解： Max Z = 3x1 + 2x2-2x1 + x2 2x1 - 3x2 3x10, x2 0s.t.x1x2 无可行解：有些 LP问题可能不存在可行点，也就是说由约束条件得到的可行域 R为空集，即 R=。 这时问题 无可行解，也就无最 优 解了， 简 称无解。 LP问题 的可行域一般是凸多 边 形，而且若最 优 解存在， 则 一定在可行域的某个 顶 点上得到；若在两个 顶 点同 时 得到最 优 解，则这 两个 顶 点 连线 上的每一点都是最 优 解，且最 优值 相等；若可行域无界， 则 可能发 生最 优 解无界的情况，此 时 无最 优 解。若可行域 为 空集， 则问题 无可行解。三、线性规划的标准形式 LP问题的各种不同形式可以相互转化，只需给出其中一种形式的解法，就可以普遍适用于一切形式的 LP问题，而单纯形法所基于的 LP问题的形式，称为标准形式。1.线性规划问题的标准形式A=（ aij） mn为约束方程组的系数阵。R(A)=mn,即 A为满秩 阵 ，称 m为 LP问题的 阶 数， n为维 数 目标函数min Z=CTX 函数约束 bi0 两端乘以 -1 约束为 “” 的情况，增加非负变量 松弛变量 约束为 “” 的情况，减去非负变量 剩余变量 决策变量对不满足非负性要求的变量，采用 “ 变量代换法 ”2.非标准形 LP问题的标准化max z = - CTX举例： 如果 xk0, 可令 xk=- xk ， xk 0 。 如果 xk为自由变量，可令 xk=xk_x“k，且xk0 ， x“k0 。 如果方程中有多个 xk为自由变量，按照上述方法会使变量的个数扩大一倍，从而增加问题求解时的计算量，为了尽量少地增加变量的个数，可以令 xk=xk-x“，其中 x“对 每个 xk的表达式都是同一个数。变量代换法四、 线性规划的解及其性质 可行解：满足 LP问题所有约束条件的向量 X可行域 所有可行解构成的集合 最优解：满足目标要求的可行解，记为 X*，其所对应的目标函数值称为最优值，记为 z*。 基本解：基本解的概念只适用于标准型 LP问题。 基向量和非基向量：A=(aij)mn=(P1 P2 P n)为线 性 规 划 问题 LP的 约 束条件系数矩 阵 ，其秩 为 m。 则 A中任一 组 m个 线 性无关的列向量构成的矩 阵B=(Pji pj2 P jm)非奇异，称此 m个 线 性无关的列向量 为线 性 规 划 问题 的一个 基 。如果 约 束矩 阵 A中某一列向量 Pj包含于基 B中， 则 称 Pj为 基向量 ，否 则 称 为 非基向量 。对 于 给 定的一个基，整个矩 阵 A可以分 为 两部分，即可表示 为 A=(B N) 基变量与非基变量：与基向量 Pjt(t=1,2,m )相对应的变量 xjt称为基变量，否则称为非基变量。 LP问题的变量也自然被相应地分成了两部分 X=(xB xN)T 基本解： 在 LP问题中，满足条件 AX=b且非基变量全部为零的 X成为基本解。X=(xB xN)T=(xB 0)TAX=(B N) (xB xN)T=BxB+NxN=b 即基本解X可以用基变量部分来表示成 xB=B-1b 基本可行解： 满足非负条件的基本解，或者说 xB=B-1b0 就称其为基本可行解。基本解 可行解基本可行解约束矩阵 A中基的数目最多为 Cnm，因而基本解的个数最多也只能有Cnm个，所以基本可行解的个数也不会超过 Cnm 退化基本解：如果基本解中有一个或者多个基变量为零，则称为退化基本解 可行基：基本可行解对应的基 最优基：最优基本解对应的基 标准形 LP问题的任一基本可行解，其所含正分量的个数比不超过问题的阶数 m，而一个非退化的基本可行解必恰有 m个正分量，其余分量均为 0。标准形 LP问题解的概念与关系解 满足条件 适用对象备注可行解 X AX=b X0 各种形式的 LP问题最优解 X* AX*=b X*0 CTX*=optCTX基本解X=(xB xN)TAX=b |B|0,XN=0 标准形LP问题XB所含分量个数恰为阶数 m， XN含n-m个 0分量基本可行解X=(xB xN)TAX=b XB0 |B|0,XN=0线性规划解的性质 性质 1： LP问题的可行域 R为一凸集 性质 2： LP问题的一个基本可行解与可行域 R的一个极点互相对应 性质 3：线性规划的基本定理：对于任何一个给定的标准形 LP问题 M来说，若 M有可行解，则必有基本可行解；如 M有最优解，则必有最优基本可行解。 性质 4：若 LP问题的可行域 R ，则 R至少