《第2章线性规划模型、图解法、标准型ppt课件.ppt》由会员分享，可在线阅读，更多相关《第2章线性规划模型、图解法、标准型ppt课件.ppt（33页珍藏版）》请在三一办公上搜索。
1、第一章 线性规划（LinearProgramming）,教学目的：本章重点引入线性规划问题的模型、几何性质、单纯形解法和线性规划的对偶定理。应理解和掌握线性规划的几何性质和求解原理，能针对实际问题，建立相应的线性规划模型。,重 点：线性规划问题的求解方法、解的基本性质以及对偶原理。,难 点：线性规划的单纯形法求解思想、矩阵表述、对偶理论以及灵敏度分析,1、生产组织与安排问题：某工厂计划生产甲、乙两种产品。所需的设备台 时及A、B两种原材料消耗，详见下表,该工厂每生产一件甲产品可获利2元，每生产一件乙产品可获利3元，问如何安排生产计划，可使利润最大？,1 线性规划问题及其数学模型,解：设x1，x
2、2分别为甲、乙产品的数量，则有 约束条件 x1+2x28 4x116 4x212 x10，x20，称x1，x2为决策变量,目标函数 max z=2x1+3x2,2、营养问题：某公司养动物以供出售。这些动物的生长对饲料中的三种营养元素特别敏感，分别称为营养元素A、B、C。已求出这些动物每天至少需要700克营养元素A，30克营养元素B，而营养C恰好为200克。现有五种饲料可供选择，各种饲料的营养元素及价格如下表所示，为了避免多使用某种元素，规定混合饲料中各种饲料最高含量分别为50、60、50、70、40千克，求满足动物需要且费用最低的饲料配方。,表2 所用饲料、营养元素及单价,解：如教材14页,3
3、、人力资源分配问题：,总结：线性规划三要素：决策变量、目标函数、约束条件 线性规划的特点:目标线性、约束条件为线性不等式或等式,一般情况下，其值均是正的,2.1 图解法 图解法不是解线性规划的主要方法,只是用于说明线性规划解的性质和特点。只能解两个变量问题。（用图解法求解,线性规划不需要化成标准型）图解法的步骤：1、约束区域的确定 2、目标函数等值线 3、平移目标函数等值线求最优值,线性规划图解法,线性规划解的几种可能情况 1、唯一最优解 2、无穷多最优解 3、无可行解 4、无有限最优解(无界解),例1：max z=2x1+3x2 x1+2x28 4x1 16 4 x2 12 x1，x2 0,
4、有唯一解,画图步骤：1、约束区域的确定 2、目标函数等值线3、平移目标函数等值线求最优值,有无穷多解,两个顶点处达到最优解,例2 max z=x1+2x2 s.t x1+2x28 4x2 16 4x1 12 x1,x2 0,约束条件围不成区域(又称矛盾方程),无可行解,例3：,max z=4x1+3x2-3x1+2x26 s.t-x1+3x2 18 x1,x2 0,无有限最优解(无界解),例4：,图解法得出线性规划问题解的几种情况,问题:围成无界区域就不能有唯一解吗?,max z=2x1+x2 5x215 s.t 6x1+2x2 24 x1+x2 5 x1,x2 0,用图解法解下面线性规划问题
5、,线性规划的几何特性：,线性规划问题若有最优解,一定在其可行域的顶点达到（1）有最优解(唯一最优解必在一个顶点达到;无穷多 最优解至少在两个顶点达到);（2）无解(可行域为空集或目标函数无有限极值),线性规划问题模型的标准型：,任意线性规划模型转化为标准型的方法：,1、目标最小化：min Z=max(Z)=max Z2、约束条件为不等式：“”引进非负松弛变量xk0,(减去)松弛变量,对应于xk的目标系数取为零。“”引进松弛变量xl0,(加入)松弛变量,对应于xl 的目标系数取为零。3、决策变量xk是自由变量(无非负限制)，或xj有上下界限制是可以引进新的变量，转化为变量0形式。例如xk是自由变
6、量，引进新变量 xl0,xm0,令xk=xl-xm，对应的目标系数仍为ck。4、当bi小于零的时候，在等式两边同时乘以-1即可。“小加、大减、一变二”,标准型模型特征：,1、约束条件为线性等式2、所有变量全部大于零3、右端常数项大于等于零4、目标函数求最大值,设线性规划的标准形式：max z=cjxj(1)s.t aijxj=bi i=1,2,m(2)xj0 j=1,2,n(3)可行域：由约束条件(2)、(3)所围成的区域；可行解：满足(2)、(3)条件的解X=(x1，x2，xn)T为可行解；基：设A是约束条件方程组的mn维系数矩阵,其秩为m，B是A中mm阶非奇异子矩阵，则称B为线性规划问题的
7、一个基。设,2.2 线性规划问题解的概念,基向量、非基向量、基变量、非基变量：称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个。基可行解的数目一般
8、小于 基解的数目;基解中非零分量的个数小于m个时，基解称为退化解。以后在不声明的情况下，均假设不出现退化情况。,可行解,基解,基可行解,非可行解,解的关系：,凸集:（直观）图形中连接任意两点的直线全部都在图形区域内,称此图形是凸的.严格数学定义:设为一n维欧氏空间的点集,若任意两点x1,x2,有x=x1+(1-)x2，其中0，1，则称为凸集。,2.3 线性规划问题的几何意义,x1,x2,凸组合：设x(1),x(2),x(k)是n维空间中的k个点,若存在1,2,k(0i1 i=1,2,k 且i=1)使 x=1x(1)+2x(2)+kx(k)成立,则称 x为 x(1),x(2),x(k)的凸组合。
9、特别，平面上的两点x(1),x(2),连线上任一点x的坐标为 x=x(1)+(1-)x(2)01.顶点：设K为凸集,xK并且x不能用K内不同的两点x(1),x(2)(xx(1),xx(2)的凸组合表示,则称x为顶点.定理1:线性规划问题若存在可行域,则其必是凸集，亦即 D=XAX=b=X,xj0,凸集性质:,设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)(01)则 Ax=Ax(1)+(1-)x(2)(01)=Ax(1)+Ax(2)-Ax(2)=b+bb=b 又因为 x(1)0,
10、x(2)0,01 所以 x 0 即 xD 证毕,证明：线性规划 max z=CX s.t AX=b X0,引理1.线性规划问题的可行解X为基本可行解的充分必要条件是X的正分量所对应的系数列向量是线性独立的.证明:必要性：已知X为线性规划的基本可行解，要证X的正分量所对应的系数列向量线性独立。因为X为基本解，由定义，其非零分量所对应的系数列向量线性独立；又因为X还是可行解，从而其非零分量全为正。充分性：已知可行解X的正分量所对应的系数列向量线性独立，欲证X是线性规划的基本可行解。若向量P1,P2,Pk线性独立,则必有km；当k=m时，它们恰构成一个基，从而X=（x1，x2,xk，00）为相应的基
11、可行解。Km时，则一定可以从其余的系数列向量中取出m-k个与P1,P2,Pk构成最大的线性独立向量组，其对应的解恰为X，所以根据定义它是基可行解，(退化)。,定理2：X是线性规划问题的基可行解的充要条件是它对应于可行域D的顶点。（线性规划问题的基可行解X对应于可行域D的顶点。）证明：不失一般性，假设基可行解X的前m个分量为正。故 充分性（顶点基可行解，用反证法）：由引理1，若X不是基可行解，则其正分量所对应的系数列向量P1,P2,Pm线性相关,即存在一组不全为零的数i,i=1,2,m,（1）,令X(1)=(x1-1),(x2-2),(xm-m),0,0 X(2)=(x1+1),(x2+2),(
12、xm+m),0,0由X(1),X(2)可以得到 X=,即X是X(1),X(2)连线的中心.另一方面,当充分小时,可保证xii0 i=1,2,m,即X(1),X(2)是可行解,所以X不是可行域D的顶点.,使得 1P1+2P2+mPm=0（2）用一个0的数乘（2）式在分别与（1）相加和相减，这样得到(x1-1)P1+(x2-2)P2+(xm-m)Pm=b(x1+1)P1+(x2+2)P2+(xm+m)Pm=b,引理2 若K是有界凸集,则任何一点XK可表示为K的顶点的凸组合.证明略。,必要性（基可行解顶点，用反证法）：X不是可行域的顶点,故可在可行域内找到两个不同的点x(1),x(2)，使得X=x(
13、1)+(1-)x(2),0m时,有X j=xj(1)=xj(2)=0,由于x(1),x(2)是可行域的两点.应满足Pjxj(1)=b 与 Pjxj(2)=b将这两式相减,即得 Pj(xj(1)-xj(2)=0因x(1)x(2),所以上式系数(xj(1)-xj(2)不全为零,故向量P1,P2,Pm组线性相关与假设矛盾.即X不是基可行解.,定理3 若可行域有界,线性规划问题的目标函数一定可以在其可行域的顶点上达到最优.,证：设X(1),X(2),X(k)是可行域的顶点,若X(0)不是顶点且目标函数在X(0)处达到最优 z*=CX(0)(不妨设标准型是z*=maxz),则X(0)可以用顶点表示为 X(0)=iX(i)i0,i=1记X(1),X(2),X(k)中使max CX(i)的顶点为X(m)。于是，由假设CX(0)为最优解，所以CX(0)=CX(m)，即最优解可在顶点X(m)达到。,注意：1、有时目标函数可能在多个顶点处达到最大值，此时在这些顶点的凸组合处也达到最大值，称这种线性规划问题有无限多个最优解。2、若可行域无界，则可能无最优解，也可能有最优解，但若有，必在顶点处取得。,
