第2章线性规划模型、图解法、标准型

第一章线性规划（LinearProgramming）教学目的：本章重点引入线性规划问题的模型、几何性质、单纯形解法和线性规划的对偶定理。应理解和掌握线性规划的几何性质和求解原理，能针对实际问题，建立相应的线性规划模型。重点：线性规划问题的求解方法、解的基本性质以及对偶原理。难点：线性规划的单纯形法求解思想、矩阵表述、对偶理论以及灵敏度分析1、生产组织与安排问题：某工厂计划生产甲、乙两种产品。所需的设备台时及A、B两种原材料消耗，详见下表该工厂每生产一件甲产品可获利2元，每生产一件乙产品可获利3元，问如何安排生产计划，可使利润最大？§1线性规划问题及其数学模型甲乙设备原材料A原材料B1402048台时16kg12kg利润/元23解：设x1，x2分别为甲、乙产品的数量，则有约束条件x1+2x2≤84x1≤164x2≤12x1≥0，x2≥0，称x1，x2为决策变量目标函数maxz=2x1+3x22、营养问题：某公司养动物以供出售。这些动物的生长对饲料中的三种营养元素特别敏感，分别称为营养元素A、B、C。已求出这些动物每天至少需要700克营养元素A，30克营养元素B，而营养C恰好为200克。现有五种饲料可供选择，各种饲料的营养元素及价格如下表所示，为了避免多使用某种元素，规定混合饲料中各种饲料最高含量分别为50、60、50、70、40千克，求满足动物需要且费用最低的饲料配方。表2所用饲料、营养元素及单价12345需求/克A321618700B10.50.220.530C0.510.220.8200价格/元27495解：如教材14页3、人力资源分配问题：班次时间所需人数16-1060210-1470314-1860418-2250522-22062-630总结：线性规划三要素：决策变量、目标函数、约束条件线性规划的特点:目标线性、约束条件为线性不等式或等式一般情况下，其值均是正的定义：线性规划（LP）的一般模型为目标函数：max(min)z=c1x1+c2x2+…+cnxn约束条件：a11x1+a12x2+…+a1nxn=（≤、≥）b1a21x1+a22x2+…+a2nxn=（≤、≥）b2………am1x1+am2x2+…+amnxn=（≤、≥）bmx1≥0，x2≥0，…，xn≥0§2.1图解法图解法不是解线性规划的主要方法,只是用于说明线性规划解的性质和特点。只能解两个变量问题。（用图解法求解,线性规划不需要化成标准型）图解法的步骤：1、约束区域的确定2、目标函数等值线3、平移目标函数等值线求最优值§线性规划图解法线性规划解的几种可能情况1、唯一最优解2、无穷多最优解3、无可行解4、无有限最优解(无界解)例1：maxz=2x1+3x2x1+2x2≤84x1≤164x2≤12x1，x2≥0•有唯一解x1x2可行域(4,2)z=14目标函数等值线画图步骤：1、约束区域的确定2、目标函数等值线3、平移目标函数等值线求最优值•有无穷多解两个顶点处达到最优解x2x1例2maxz=x1+2x2s.tx1+2x2≤84x2≤164x1≤12x1,x2≥0约束条件围不成区域(又称矛盾方程)•无可行解0,124322.23max21212121xxxxxxtsxxz例3：x1x2maxz=4x1+3x2-3x1+2x2≤6s.t-x1+3x2≥18x1,x2≥0•无有限最优解(无界解)x1x2例4：-3x1+2x2=6图解法得出线性规划问题解的几种情况问题:围成无界区域就不能有唯一解吗?解的几种情况约束条件图形特点方程特点唯一解一般围成有限区域,最优值只在一个顶点达到无穷多解在围成的区域边界上,至少有两个顶点处达到最优值目标和某一约束方程成比例无可行解(无解)围不成区域有矛盾方程无界解(无解)围成无界区域,且无有限最优值缺少一必要条件的方程maxz=2x1+x25x2≤15s.t6x1+2x2≤24x1+x2≤5x1,x2≥0用图解法解下面线性规划问题线性规划的几何特性：线性规划问题若有最优解,一定在其可行域的顶点达到（1）有最优解(唯一最优解必在一个顶点达到;无穷多最优解至少在两个顶点达到);（2）无解(可行域为空集或目标函数无有限极值)线性规划问题模型的标准型：分量形式：线性规划（LP）的标准型：目标函数：maxz=c1x1+c2x2+…+cnxn约束条件：a11x1+a12x2+…+a1nxn=b1s.ta21x1+a22x2+…+a2nxn=b2………am1x1+am2x2+…+amnxn=bmx1≥0，x2≥0，…，xn≥0且bi≥0，若bi0，则乘(-1)注:有些书中以min型目标函数为标准型∑(和)表示法：目标函数maxz=∑cjxj约束条件s.t∑aijxj=bi，i=1,…,mxj≥0，j=1,…,n向量表示法:目标函数maxz=CX约束条件s.t∑pjxj=bxj≥0，j=1,…,n矩阵表示法:目标函数maxz=CX约束条件s.tAX=bX≥0任意线性规划模型转化为标准型的方法：1、目标最小化：minZ=max(―Z)=maxZ2、约束条件为不等式：“≥”引进非负松弛变量xk≥0,(减去)松弛变量,对应于xk的目标系数取为零。“≤”引进松弛变量xl≥0,(加入)松弛变量,对应于xl的目标系数取为零。3、决策变量xk是自由变量(无非负限制)，或xj有上下界限制是可以引进新的变量，转化为变量≥0形式。例如xk是自由变量，引进新变量xl≥0,xm≥0,令xk=xl-xm，对应的目标系数仍为ck。4、当bi小于零的时候，在等式两边同时乘以-1即可。“小加、大减、一变二”标准型模型特征：•1、约束条件为线性等式•2、所有变量全部大于零•3、右端常数项大于等于零•4、目标函数求最大值解：引进变量x3≥0、x4≥0，将自由变量换为x2=x3-x4，引进松弛变量x5≥0,剩余变量x6≥0得:maxZ’=-x1-2x3+2x4+0x5+0x62x1+3x3-3x4+x5=6s.tx1+x3-x4-x6=4x1-x3+x4=3xj≥0,j=1,3,4,5,6例如：将下列线性规划问题化成标准型minZ=x1+2x22x1+3x2≤6s.tx1+x2≥4x1-x2=3x1≥0，x2无限制。例如：将下列线性规划问题化成标准型minZ=-3x1+4x2-2x3+5x44x1-x2+2x3-x4=-2s.tx1+x2+3x3-x4≤14-2x1+3x2-2x3+2x4≥2x1,x2,x3≥0，x4无限制解：引进变量x5≥0、x6≥0，令x4=x41-x42化为如下标准型:maxZ’=3x1-4x2+2x3-5x41+5x42-4x1+x2-2x3+x41-x42=2s.tx1+x2+3x3-x41+x42+x5=14-2x1+3x2-x3+2x41-2x42-x6=2xj≥0,j=1,2,3,41,42,5,6练习:将下列线性规划问题化成标准型1、minZ=5x1+x2+x33x1+x2-x3≤7-3x1+x2≤6s.tx1+2x2≤4x2≥-3,x1无限制2、maxZ=-x1+4x2s.tx1-2x2+4x3≥-6x2+3x3=3x1,x2≥0,x3无限制设线性规划的标准形式：maxz=Σcjxj(1)s.tΣaijxj=bii=1,2,…,m(2)xj≥0j=1,2,…,n(3)可行域：由约束条件(2)、(3)所围成的区域；可行解：满足(2)、(3)条件的解X=(x1，x2，…，xn)T为可行解；基：设A是约束条件方程组的m×n维系数矩阵,其秩为m，B是A中m×m阶非奇异子矩阵，则称B为线性规划问题的一个基。设§2.2线性规划问题解的概念B==(p1,p2,…,pm)a11a12…a1ma21a22…a2m………am1am2…amm基向量、非基向量、基变量、非基变量：称pj(j=1,2,…,m）为基向量，其余称为非基向量；与基向量pj(j=1,2,…,m）对应的xj称为基变量，其全体写成XB=（x1，x2，…，xm）T；否则称为非基变量，其全体经常写成XN。基解：对给定基B,设XB是对应于这个基的基变量XB=(x1，x2，…，xm)T；令非基变量xm+1=xm+2=…=xn=0，由（2）式得出的解X=（x1，x2，…，xm，0，…，0）T称为基解。基可行解：所有决策变量满足非负条件(xj≥0)的基解,称作基可行解。可行基：基可行解所对应的基底称为可行基。注：基解的数目最多为Cnm个。基可行解的数目一般小于基解的数目;基解中非零分量的个数小于m个时，基解称为退化解。以后在不声明的情况下，均假设不出现退化情况。可行解基解基可行解非可行解解的关系：凸集:（直观）图形中连接任意两点的直线全部都在图形区域内,称此图形是凸的.严格数学定义:设Ω为一n维欧氏空间的点集,若任意两点x1,x2∈Ω,有x=λx1+(1-λ)x2∈Ω，其中λ∈[0，1]，则称Ω为凸集。§2.3线性规划问题的几何意义•x1•x2•x1•x2凸组合：设x(1),x(2),…,x(k)是n维空间中的k个点,若存在μ1,μ2,…,μk(0≤μi≤1i=1,2,…k且Σμi=1)使x=μ1x(1)+μ2x(2)+…+μkx(k)成立,则称x为x(1),x(2),…,x(k)的凸组合。特别，平面上的两点x(1),x(2),连线上任一点x的坐标为x=αx(1)+(1-α)x(2)0≤α≤1.顶点：设K为凸集,x∈K并且x不能用K内不同的两点x(1),x(2)(x≠x(1),x≠x(2))的凸组合表示,则称x为顶点.定理1:线性规划问题若存在可行域,则其必是凸集，亦即D={X∣AX=b}={X∣,xj≥0}凸集性质:njjjbxP1设x(1)≠x(2)为D内任取两点，则Ax(1)=b,Ax(2)=b,x(1)≥0,x(2)≥0,令x为线段x(1),x(2)上任一点,既有x=μx(1)+(1-μ)x(2)(0≤μ≤1)则Ax=A[μx(1)+(1-μ)x(2)](0≤μ≤1)=μAx(1)+Ax(2)-μAx(2)=μb+b–μb=b又因为x(1)≥0,x(2)≥0,0≤μ≤1所以x≥0即x∈D证毕证明：线性规划maxz=CXs.tAX=bX≥0引理1.线性规划问题的可行解X为基本可行解的充分必要条件是X的正分量所对应的系数列向量是线性独立的.证明:必要性：已知X为线性规划的基本可行解，要证X的正分量所对应的系数列向量线性独立。因为X为基本解，由定义，其非零分量所对应的系数列向量线性独立；又因为X还是可行解，从而其非零分量全为正。充分性：已知可行解X的正分量所对应的系数列向量线性独立，欲证X是线性规划的基本可行解。若向量P1,P2,…,Pk线性独立,则必有k≤m；当k=m时，它们恰构成一个基，从而X=（x1，x2,…,xk，0…0）为相应的基可行解。K〈m时，则一定可以从其余的系数列向量中取出m-k个与P1,P2,…,Pk构成最大的线性独立向量组，其对应的解恰为X，所以根据定义它是基可行解，(退化)。定理2：X是线性规划问题的基可行解的充要条件是它对应于可行域D的顶点。（线性规划问题的基可行解X对应于可行域D的顶点。）证明：不失一般性，假设基可行解X的前m个分量为正。故充分性（顶点基可行解，用反证法）：由引理1，若X不是基可行解，则其正分量所对应的系数列向量P1,P2,…,Pm线性相关,即存在一组不全为零的数αi,i=1,2,…,mmjjjbxp1（1）令X(1)=[(x1-μα1),(x2-μα2),…,(xm-μαm),0,…,0]X(2)=[(x1+μα1),(x2+μα2),…,(xm+μαm),0,…,0]由X(1),X(2)可以得到X=,即X是X(1),X(2)连线的中心.另一方面,当μ充分小时,可保证xi±μαi≥0i=1,2,…,m,即X(1),X(2)是可行解,所以X不是可行域D的顶点.)2()1(2121XX使得α1P1+α2P2+…+αmPm=0（2）用一个μ0的数乘（2）式在分别与（1）相加和相减，这样得到(x1-μα1)P