第2章线性规划模型图解法标准型精选文档.ppt

《第2章线性规划模型图解法标准型精选文档.ppt》由会员分享，可在线阅读，更多相关《第2章线性规划模型图解法标准型精选文档.ppt（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第2章线性规划模型图解法标准型本讲稿第一页，共三十三页1、生产组织与安排问题：、生产组织与安排问题：某工厂计划生产甲、乙两种产品。所需的设备台 时及A、B两种原材料消耗，详见下表该工厂每生产一件甲产品可获利2元，每生产一件乙产品可获利3元，问如何安排生产计划，可使利润最大？1 线性规划问题及其数学模型线性规划问题及其数学模型本讲稿第二页，共三十三页解解：设x1，x2分别为甲、乙产品的数量，则有 约束条件 x1+2x28 4x116 4x212 x10，x20，称x1，x2为决策变量 目标函数 max z=2x1+3x22、营养问题：、营养问题：某公司养动物以供出售。这些动物的生长对饲料中的三种

2、营养元素特别敏感，分别称为营养元素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-106

3、0210-1470314-1860418-2250522-22062-630本讲稿第五页，共三十三页总结：线性规划三要素：决策变量、目标函数、约束条件 线性规划的特点:目标线性、约束条件为线性不等式或等式一般情况下，其值均是正的定义：线性规划（LP）的一般模型为 目标函数：max(min)z=c1 x1+c2 x2+cn xn 约束条件：a11 x1+a12 x2+a1n xn=（、）b1 a21 x1+a22 x2+a2n xn=（、）b2 am1 x1+am2 x2+amn xn=（、）bm x10，x20，xn0本讲稿第六页，共三十三页2.1 图解法图解法 图解法不是解线性规划的主要方法

4、,只是用于说明线性规划解的性质和特点。只能解两个变量问题。（用图解法求解,线性规划不需要化成标准型）图解法的步骤：1、约束区域的确定 2、目标函数等值线 3、平移目标函数等值线求最优值 线性规划图解法线性规划图解法 线性规划解的几种可能情况 1、唯一最优解 2、无穷多最优解 3、无可行解 4、无有限最优解(无界解)本讲稿第七页，共三十三页例1：max z=2x1+3x2 x1+2x28 4x1 16 4 x2 12 x1，x2 0 有唯一解有唯一解x1x2可行域(4,2)z=14目标函数等值线画图步骤画图步骤：1、约束区域的确定 2、目标函数等值线3、平移目标函数等值线求最优值本讲稿第八页，共

5、三十三页 有无穷多解有无穷多解两个顶点处达到最优解两个顶点处达到最优解x2x1例2 max z=x1+2x2 s.t x1+2x28 4x2 16 4x1 12 x1,x2 0本讲稿第九页，共三十三页约束条件围不成区域(又称矛盾方程)无可行解例3：x1x2本讲稿第十页，共三十三页max z=4x1+3x2 -3x1+2x26 s.t -x1+3x2 18 x1,x2 0 无有限最优解(无界解)x2例4：-3x1+2x2=6本讲稿第十一页，共三十三页图解法得出线性规划问题解的几种情况 问题:围成无界区域就不能有唯一解吗?解的几种情况约束条件图形特点方程特点唯一解一般围成有限区域,最优值只在一个顶

6、点达到无穷多解在围成的区域边界上,至少有两个顶点处达到最优值目标和某一约束方程成比例无可行解(无解)围不成区域有矛盾方程无界解(无解)围成无界区域,且无有限最优值缺少一必要条件的方程本讲稿第十二页，共三十三页max z=2x1+x2 5x215 s.t 6x1+2x2 24 x1+x2 5 x1,x2 0用图解法解下面线性规划问题本讲稿第十三页，共三十三页线性规划的几何特性线性规划的几何特性线性规划的几何特性线性规划的几何特性：线性规划问题若有最优解,一定在其可行域的顶点达到 （1）有最优解(唯一最优解必在一个顶点达到;无穷多 最优解至少在两个顶点达到);（2）无解(可行域为空集或目标函数无有

7、限极值)本讲稿第十四页，共三十三页线性规划问题模型的标准型：线性规划问题模型的标准型：分量形式：分量形式：线性规划（LP）的标准型：目标函数：max z=c1 x1+c2 x2+cn xn 约束条件：a11 x1+a12 x2+a1n xn=b1 s.t a21 x1+a22 x2+a2n xn=b2 am1 x1+am2 x2+amn xn=bm x10，x20，xn0 且bi0，若 bi0的数乘（2）式在分别与（1）相加和相减，这样得到(x1-1)P1+(x2-2)P2+(xm-m)Pm=b(x1+1)P1+(x2+2)P2+(xm+m)Pm=b令X(1)=(x1-1),(x2-2),(x

8、m-m),0,0 X(2)=(x1+1),(x2+2),(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的顶点.本讲稿第三十页，共三十三页引理引理2 2 若若K K是有界凸集是有界凸集,则任何一点则任何一点XKXK可表示为可表示为K K的顶点的凸组合的顶点的凸组合.证明略。必要性（基可行解顶点，用反证法）：X不是可行域的顶点,故可在可行域内找到两个不同的点x(1),x(2)，使得X=x(1)+(1-)x(2),0m时,有X j=xj(1)=xj(2)

9、=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 3 3 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、若可行域无界，则可能无最优解，也可能有最优解，但若有，必在顶点处取得。本讲稿第三十三页，共三十三页