第2章线性规划模型、图解法、标准型ppt课件.ppt

《第2章线性规划模型、图解法、标准型ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章线性规划（LinearProgramming）教学目的：本章重点引入线性规划问题的模型、几何性质、单纯形解法和线性规划的对偶定理。应理解和掌握线性规划的几何性质和求解原理，能针对实际问题，建立相应的线性规划模型。重点：线性规划问题的求解方法、解的基本性质以及对偶原理。难点：线性规划的单纯形法求解思想、矩阵表述、对偶理论以及灵敏度分析1、生产组织与安排问题：某工厂计划生产甲、乙两种产品。所需的设备台时及A、B两种原材料消耗，详见下表该工厂每生产一件甲产品可获利2元，每生产一件乙产品可获利3元，问如何安排生产计划，可使利润最大？§1线性规划问题及其数学模型解：设x1，x2分别

2、为甲、乙产品的数量，则有约束条件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需求/克A32

3、1618700B10.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………am

4、1x1+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、约束区域的确定

5、2、目标函数等值线3、平移目标函数等值线求最优值有无穷多解两个顶点处达到最优解x2x1例2maxz=x1+2x2s.tx1+2x2≤84x2≤164x1≤12x1,x2≥0约束条件围不成区域(又称矛盾方程)无可行解例3：x1x2maxz=4x1+3x2-3x1+2x2≤6s.t-x1+3x2≥18x1,x2≥0无有限最优解(无界解)x1x2例4：-3x1+2x2=6图解法得出线性规划问题解的几种情况问题:围成无界区域就不能有唯一解吗?解的几种情况约束条件图形特点方程特点唯一解一般围成有限区域,最优值只在一个顶点达到无穷多解在围成的区域边界上,至少有两个顶点处达到最优值目标和某一

6、约束方程成比例无可行解(无解)围不成区域有矛盾方程无界解(无解)围成无界区域,且无有限最优值缺少一必要条件的方程maxz=2x1+x25x2≤15s.t6x1+2x2≤24x1+x2≤5x1,x2≥0用图解法解下面线性规划问题线性规划的几何特性：线性规划问题若有最优解,一定在其可行域的顶点达到（1）有最优解(唯一最优解必在一个顶点达到;无穷多最优解至少在两个顶点达到);（2）无解(可行域为空集或目标函数无有限极值)线性规划问题模型的标准型：分量形式：线性规划（LP）的标准型：目标函数：maxz=c1x1+c2x2+…+cnxn约束条件：a11x1+a12x2+…+a1nxn=b

7、1s.ta21x1+a22x2+…+a2nxn=b2………am1x1+am2x2+…+amnxn=bmx1≥0，x2≥0，…，xn≥0且bi≥0，若bi<0，则乘(-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任意线性规划模型转化为标