第2章 线性规划

第二章 线性规划运筹学中应用最广泛的方法之一，历史悠久，理论成熟。运筹学的最基本的方法之一，网络规划，整数规划，目标规划和多目标规划都是以线性规划为基础的解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大线性规划模型特点决策变量： x1, ., xn表示要寻求的方案，每一组值就是一个方案；约束条件：线性等式或不等式目标函数： Z=(x1 xn) 线性式，求 Z极大或极小一般式min z=c1x1+ c2x2+ cnxnai1x1+ ai2x2+ ainxn =bi ,i=1,pai1x1+ ai2x2+ ainxn bi , i=p+1,mxj 0 , j=1,qxj 符号无限制 ， j=q+1,ns.t.目标函数（ LP）3隐含的假设比例性：决策变量变化引起目标的改变量与决策变量改变量成正比可加性：每个决策变量对目标和约束的影响独立于其它变量连续性：每个决策变量取连续值确定性：线性规划中的参数 aij , bi , ci为确定值 矩阵形式说明：A1 A2 Ana11 a12 a 1nA= a21 a22 a2nam1 am2 amnx1 x= x2xnb1 b= b2bmc1 c= c2cn约束矩阵决策向量右端向量价值向量LP问题的规范型： LP问题的标准型：LP问题的三种形式是等价的：min z=cTxAx bx 0 s.t.min z=cTxAx=bx 0 s.t.LP问题的规范型 LP问题的标准型LP问题的一般型LP问题的规范型LP问题的一般型LP问题的标准型LP问题的一般型例：将线性规划问题化成标准型 (P15例 2.1.3) ： 解的概念： 满足所有约束条件的一组 x1, x2， xn的值称作线性规划的 可行解 ，所有可行解构成的集合称作 可行域 。使目标函数取得最大或最小值的可行解称为线性规划问题的 最优解 ；对应的目标函数的取值称为最优值。求解线性规划问题就是求其最优解和相应的 最优值 。 图解法 ？ 对于只有两个变量的线性规划 问题 ，可以用在平面上作图的方法求解，这种方法称为图解法 。 特 点 ： 图 解法 简单 、直 观 ， 便于初学者了解线 性 规 划基本原理和几何意 义 。2.2可行区域与基本可行解 step1. 画直角坐 标 系 ；线性规划问题图解法的步骤对每个约束（包括非负约束）条件，先取等式得到一条直线（平面）并在坐标图中画出该直线，然后取一已知点来判断该点的坐标是否满足该约束条件，若满足，则可行域与已知点在所画直线的同侧，否则可行域在直线的另一侧。若所有的约束均已画出，则可在坐标系中画出可行域。 step2. 依次做每条约束线，找出可行域 ;若不存在可行域,则该问题无可行解； step3. 做目标函数线，根据目标类型平移 ,直到该线即将离开可行域 时 与 该 线接触的最后 一 点即为一最优解 ;若 该线可无限制地在可行域内移动 ,则该问题无界 。例 1. maxZ=-X1+ X2 2 X1-X2 -2X1-2X2 2X1+X2 5X1 , X2 01.图解法示例解：确定可行域0123X21 2 3X12X1-X2 =-2 ()(0,2) (-1,0)2X1-X2 =-2X1+X2 =5 ()(0,5) (5,0) X1-2X2 =2 ()(0,-1) (2,0) X1-2X2 =2X1+X2 =5Z=-X1+ X2(1,4)在该点取到最大值 32 3 10123X2A1BC42 X1-X2 =-2X1-2X2 =2X1+X2 =5(1,4)若目标函数改为min Z=4X1-2X2 2 X1-X2 -2X1-2X2 2X1+X2 5X1 , X2 0A2A3A4O最优解： A1A2线段上所有的点，最优值为 -4X(1)=(0, 2)T , X(2)=(1,4)TX= X(1)+(1-) X(2) (0 1)X1 =1- X2=2+4 (1- )=4-2 (0 1)min Z=4X1-2X2 =-4 2 3 10123X2A1BC4 2 X1-X2 =-2X1-2X2 =2X1+X2 =5(1,4)A2A3A4O 可行域 ：由约束平面围起来的凸多边形区域，可行域内的每一个点代表一 个可行解。 最优解 ：总是在可行域的边界上，一般由可行域的顶点 表示 。 有效与无效 (紧与松 )约束 ：与最优解相关的约束为有效 (紧 )约束 。图解法的观察 【 1】无界无有限最优解例 2、 maxZ=2X1+ 4X2 2X1+X2 8-2X1+X2 2X1 , X2 0Z=0 2X1+ X2=8-2X1+ X2=28246X240 X1例 3、 maxZ=3X1+2X2 -X1 -X2 1X1 , X2 0无解无可行解-1X2-1 X10-X1-X2 =1如果可行域为空集，线性规划问题无可行解；如果目标函数线可以无限制地在可行域内向改善的方向移动，线性规划问题无界；线性规划问题可能存在无穷多个最优解。图解法的观察（ 2）唯一最优解无穷多最优解无有限最优解无可行解有最优解无最优解总结两个变量的 LP问题的解：(1)、可行域为凸多边形。(2)、若有最优解，定可在可行域的顶点得到。X(1)X(2)凸多边形 凹多边形X(1)X(2)思考：两个以上变量解的情况有又如何呢？2.可行区域的几何结构min Z=CTXAX =bX0假设：秩 (Amn)=mnD=XR n| AX =b, X0 a11 a12 a 1nA= a21 a22 a2nam1 am2 amn其中： b1 b= b2bmX = (x1 xn)T C = (c1 cn)T凸集没有凹陷部分，该集合内任取两点连线上的任何点都应该在集合内。 定义 1：xS y凸集 ： S是 n维欧氏空间的一个集合 ,如果对任意x, yS, 0 1, 有 x + (1 - ) y S。证明： 设 LP问题的可行解域为集合 DD= X| AX=b X 0 任取 X(1) , X(2) D, 则X= X(1) +(1- ) X(2) 0 (0 1)又因为 A X(1) =b， A X(2) =b所以 AX=A X(1) +(1- ) X(2) = b +(1- ) b=b 则 XD， D为凸集定理 1 D=X Rn| AX =b, X0是凸集。定义 2： 给定 bR 1,及非零向量 aR n称集合H =XR n| aTX =b是 Rn中的一个超平面 .H+ =XR n| aTX bH- =XR n| aTX bH+， H-和超平面 H都是凸集 .H+和 H-是由超平面 H产生的两个闭的半空间定理 2 任意多个 凸集的交集仍是凸集。定义 3：结论：线性规划的可行域是凸集。凸集 S的顶点 X： S是 一个 凸集， XS ，对任意 X(1), X(2)S ， X(1) X(2) ,和任意的 ， 01,都有 X X(1)+(1-) X(2) .定义 4：a11 a 1m a1m+1 a 1na21 a2m a2m+1 a2n am1 amm amm+1 amnB N(m n) r(A)=m , 至少有一个 m阶子式不为 03、基本可行解及线性规划的基本原理定义 5：基 (基阵 ) 秩为 m的约束矩阵 Amn 的 一个 m阶子矩阵 B是可逆矩阵，则方阵 B称为对应 LP问题的一个基。A= (A1 Am Am+1 An )=(B N)基向量 非基向量X= (X1 Xm Xm+1 Xn )T=(XBT ， XNT)T基变量 非基变量XBT XNTAX=b的求解 A=(B N)X=(XB XN )TXB XN(B N) = bBXB +NXN=bBXB =b-NXNXB = B-1 b - B-1N XN定义 5：基本解 对应于基 B， X=为 AX=b的一个解。B-1 b0基本可行解 基 B， 基本解 X=若 B-1 b0， 称基 B为可行基。B-1 b0 基本解中最多有 m个非零分量。 基本解的数目不超过 Cnm = 个。n!m!(n-m)!（续）X1+2X2 +X3 =303X1+2X2 +X4 =602X2 +X5=24X1 X5 0 1 2 1 0 03 2 0 1 00 2 0 0 1A1 A2 A3 A