Lecture 2-4线性规划及Matlab实现

华南理工大学模具研究室[e-mail]线性规划基本理论线性规划（LinearProgramming，简称LP）运筹学的一个重要分支，是运筹学中研究较早、发展较快、理论上较成熟和应用上极为广泛的一个分支。1947年G.B.Dantying提出了一般线性规划问题求解的方法——单纯形法之后，线性规划的理论与应用都得到了极大的发展。60年来，随着计算机的发展，线性规划已广泛应用于工业、农业、商业、交通运输、经济管理和国防等各个领域，成为现代化管理的有力工具之一。e.g.1资源的合理利用问题问：如何安排生产计划，使得既能充分利用现有资源又使总利润最大？某工厂在下一个生产周期内生产甲、乙两种产品，要消耗A、B两种资源，已知每件产品对这两种资源的消耗，这两种资源的现有数量和每件产品可获得的利润如表1。maxz=15x1+25x2s.t.x1+3x2≤60x1+x2≤40x1，x2≥0解：设x1，x2为下一个生产周期产品甲和乙的产量；约束条件：Subjecttox1+3x2≤60x1+x2≤40x1，x2≥0目标函数：z=15x1+25x2决策变量线性规划问题三要素三个基本要素：1、决策变量xj≥02、约束条件——一组决策变量的线性等式或不等式3、目标函数——决策变量的线性函数max（min）z=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn≤（或=，≥）b1a21x1+a22x2+…+a2nxn≤（或=，≥）b2……am1x1+am2x2+…+amnxn≤（或=，≥）bmxj≥0（j=1,2,…,n）其中aij、bi、cj（i=1,2,…,m；j=1,2,…,n）为已知常数线性规划问题的一般形式：定义1：在LP问题中，凡满足约束条件(2)、(3)的解x=(x1,x2,…,xn)T称为LP问题的可行解，所有可行解的集合称为可行解集（或可行域）。记作D={x|Ax=b,x≥0}。定义2：设LP问题的可行域为D，若存在x*∈D，使得对任意的x∈D都有cx*≤cx，则称x*为LP问题的最优解，相应的目标函数值称为最优值。记作z*=cx*。min(1)..(2)0(3)zcxstAxbx线性规划问题的图解法maxz=15x1+25x2s.t.x1+3x2≤60x1+x2≤40x1，x2≥0(40,0)(0,0)CB(30,10)12360xx1240xxO(0,20)AL1L2目标函数变形：x2=-3/5x1+z/25x2x1最优解：x1=30x2=10最优值：zmax=700B点是使z达到最大的唯一可行点1、在平面上建立直角坐标系；2、图示约束条件，确定可行域和顶点坐标；3、图示目标函数（等值线）和移动方向；4、寻找最优解。LP问题图解法的基本步骤：minz=-3x1-5.7x2s.t.x1+1.9x2≥3.8x1-1.9x2≤3.8x1+1.9x2≤11.4x1-1.9x2≥-3.8x1，x2≥0x1x2ox1-1.9x2=3.8x1+1.9x2=3.8x1+1.9x2=11.4（7.6,2）D0=-3x1-5.7x2minZmaxZ（3.8,4）34.2=3x1+5.7x2可行域x1-1.9x2=-3.8(0,2)(3.8,0)绿色线段上的所有点都是最优解,即有无穷多最优解。Zmin=-34.2minz=-2x1-2x2s.t.2x1–x2≥2-x1+4x2≤4x1，x2≥01222xx1244xxOA(１,0)x1x2Note:可行域为无界区域，目标函数值可无限减小，即解无界。称为无最优解。可行域为无界区域一定无最优解吗？1、LP问题从解的角度可分为：⑴有可行解⑵无可行解a.有唯一最优解b.有无穷多最优解C.无最优解2、LP问题若有最优解，必在可行域的某个顶点上取到；若有两个顶点上同时取到，则这两点的连线上任一点都是最优解。两个重要结论：讨论线性规划的可行域和最优解的几种可能的情况。1、可行域为封闭的有界区域(a)有唯一的最优解；(b)有一个以上的最优解；2、可行域为非封闭的无界区域(a)有唯一的最优解；(b)有一个以上的最优解；(c)目标函数无界（即虽有可行解，但在可行域中，目标函数可以无限增大或无限减小），因而没有最优解。3、可行域为空集，因而没有可行解。图解法优点：直观、易掌握。有助于了解解的结构。图解法缺点：只能解决低维问题，对高维无能为力。图解法优缺点Mathmatica图解法：Lecture2GraphicalOptimizationminz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2……am1x1+am2x2+…+amnxn=bmxj≥0（j=1,2,…,n）bi≥0（i=1,2,…,m）特点：1、目标函数为极小化；2、除决策变量的非负约束外，所有的约束条件都是等式，且右端常数均为非负；3、所有决策变量均非负。线性规划问题的标准形式：标准形的特征：极小化、等式约束、变量非负1、目标函数为求极大值，即为：。1maxnjjjzcx'1minnjjjzcx因为求maxz等价于求min(-z)，令z’=-z，即化为：2、约束条件为不等式，1nijjiijaxxbnjijijbxa1njijijbxa1≥0松弛变量如何处理？如何转化为标准形式？ix1nijjiijaxxb≥0剩余变量ix３、右端项bi0时，只需将等式两端同乘（-1）则右端项必大于零4、决策变量无非负约束设xj没有非负约束，若xj≤0，可令xj=-xj’，则xj’≥0；5.又若xj为自由变量，即xj可为任意实数，可令xj=xj’-xj’’，且xj’,xj’’≥0设xj没有非负约束，若xj≥hj，可令yj=xj-hj，则yj≥0；试将LP问题maxz=-x1+2x2-3x3s.t.x1+x2+x3≤7x1-x2+x3≥2-3x1+x2+2x3=-5x1,x2≥0解：令x3=x4-x5其中x4、x5≥0；对第一个约束条件加上松弛变量x6；对第二个约束条件减去剩余变量x7；对第三个约束条件两边乘以“-1”；令z’=-z把求maxz改为求minz’minz’=x1-2x2+3x4-3x5s.t.x1+x2+x4-x5+x6=7x1-x2+x4-x5-x7=23x1-x2-2x4+2x5=5x1,x2,x4,x5,x6,x7≥0化为标准形式。11min..(1,2,,)0(1,2,,)njjjnijjijjzcxstaxbimxjn12,,,ncccc价值向量min(1)..(2)0(3)zcxstAxbx1min..0njjjzcxstpxbx决策向量Tnxxxx,,,21右端向量0,,,,21iTmbbbbb列向量的第为jAaaapTmjjjj,,,21系数矩阵mnmmnnaaaaaaaaaA212222111211LP的几种表示形式：讨论如下LP问题：min(1)..20(3)zcxstAxbx12,,,ncccc价值向量12,,,Tnxxxx12,,,,0Tmibbbbb右端向量111212122212nnmmmnaaaaaaAaaa其中系数矩阵(mn)决策向量线性规划的基(Basis)对于线性规划的约束条件Ax=bx≥0设B是A矩阵中的一个非奇异的m×m子矩阵，则称B为线性规划的一个基。设B是线性规划的一个基，则A可以表示为A=[B,N]x也可相应地分成BNxxxA=(B,N)xB=(x1,…,xm)T,xN=(xm+1,…,xn)T则BNxxx,代入约束方程（2），得.BNxBNbxBNBxNxb自由变量（独立变量）令0Nx1BxBb11BNxBbBNx1(4)0Bbx称（4）为相应于基B的基本解线性规划问题的基本解(BasicSolution,BS)、基本可行解(BasicFeasibleSolution,BFS)可行基(FeasibleBasis,FB):线性规划的解1BNxxxBb0称为线性规划与基B对应的基本解。若其中基变量的值XB=B-1b0，则称以上的基本解为基本可行解，相应的基B称为可行基。定理线性规划的基本可行解就是可行域的极点。这个定理是线性规划的基本定理，它的重要性在于把可行域的极点这一几何概念与基础可行解这一代数概念联系起来，因而可以通过求基础可行解的线性代数的方法来得到可行域的一切极点，从而有可能进一步获得最优极点。1212212max2..31,0zxxstxxxxx12123241234min-2..+3+1,,,0zxxstxxxxxxxxx10100111,,,4321aaaaAA矩阵包含以下六个2×2的子矩阵：11211[,]01Baa21311[,]00Baa31410[,]01Baa42311[,]10Baa52410[,]11Baa63410[,]01Baa3400Nxxx111320.011101B2xxxBb12342100xxxxxxxBN对于基B1=[a1，a2]，令非基变量等于0得到基变量的值为非负，因而B1是可行基。为对应于基B1的一个基本解。由于X的各分量均为非负，故X是一个基本可行解，因而对应于一个极点。用同样的方法，可以验证B3、B4、B6都是可行基，因而相应的基本解都是可行解，各对应于一个极点。但B5不是可行基，这是因为B5对应的基本解X=(x1，x2，x3，x4)T=(0，3，0，-2)T有小于零的分量，因而对应的点D不是极点。上述定理指出了一种求解线性规划问题的可能途径，这就是先确定线性规划问题的基，如果是可行基，则计算相应的基本可行解以及相应解的目标函数值。由于基的个数是有限的，因此必定可以从有限个基础可行解中找到使目标函数为最优（极大或极小）的解。基本可行解的个数不超过mnC设有一个50个变量、20个约束等式的LP问题，则最多可能有个基本可行解。20135050!4.71020!30!C1364.7101.510360024365´´´´（年）LP问题解的基本性质定理1设x是LP问题的可行解(1)若x=0，则它一定是基本可行解；(2)若x≠0，则x是基本可行解的充要条件是它的非零分量所对应的列向量线性无关。Ax=0定理2如果一个LP问题有可行解，则它必有基本可行解。定理3如果一个LP问题有最优解，则必存在一个基本可行解是它的最优解。定理2、定理3称为LP问题的基本定理LP问题是一个组合优化问题LP问题的基本定理单纯形法（SimplexMethod）是1947年由G.B.Dantzig提出，是解LP问题最有效的算法之一，且已成为整数规划和非线性规划某些算法的基础。基本思路：基于LP问题的标准形式，先设法找到一个基本可行解，判断它是否是最优解，如果是则停止计算；否则，则转换到另一个基本可行解，如此继续，直至找到最优解或者判断出不存在最优解。单纯形法12341310,,,1101Appppx3,x4是基变量.34,Bpp是可行基，基变量用非基变量表示：x3=60-x1-3x2x4=40-x1-x2代入目标函数：z=-15x1-25x2令非基变量x1=x2=0z=0基可行解x(0)=(0,0,60,40)T是最优解吗？mi