《线性规划基础》PPT课件.ppt
《《线性规划基础》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《线性规划基础》PPT课件.ppt(49页珍藏版)》请在三一办公上搜索。
1、第六章 线性规划基础,-环境系统污染控制规划的数学基础,6.1 线性规划概述,线性规划是数学规划与运筹学的一个分支,是运筹学中最重要的一种数学方法。主要研究解决有限资源的最佳分配问题,即如何对有限的资源作出最佳方式的调配和最有利的使用,以便最充分地发挥资源的效能去获取最佳经济效益。这种数学规划的方法,如果用数学语言表达,就是在一定的约束条件下,寻找目标函数的极值问题。所谓线性规划,是指约束条件为线性等式或不等式,且目标函数也是线性函数。,生产调度问题,1.线性规划问题的提出,一、线性规划及其数学模型,某企业生产甲、乙两种产品,分别用A、B、C 3种不同的原料,每生产1个单位的甲,需用1个单位的
2、A、1个单位的B、0个单位的C,利润为3千元;每生产1个单位的乙,需用1个单位的A、2个单位的B、1个单位的C,利润为4千元;现有6个单位的A、8个单位的B、3个单位的C,问企业如何安排生产,可使利润最大。,产品,甲,乙,x1,x2,原料,A,B,C,利润,1,1,0,3,1,2,1,4,原料限制,6,8,3,2.建模的步骤,(1)明确问题的经济背景,(2)设定决策变量,(3)明确目标-给出目标函数,(4)明确问题的所有限制-给出约束条件,Z=3x1+4x2,x1+x2 6,x1+2x2 8,x2 3,x10,x2 0,每天总利润:Z=3x1+4x2 变量 x1 和x2必须满足三个条件:x1+
3、x2 6 x1+2x2 8 x2 3非负性约束:x10,x2 0,目标函数,决策变量,函数约束,约束条件,Max Z=3x1+4x2 x1+x2 6 x1+2x2 8 x2 3 x10,x2 0,数学模型,s.t.,线性规划的数学表达,即求一组变量x1,x2,xn,在满足约束条件:a11x1+a12x2+a1nxnb1 a21x1+a22x2+a2nxnb2 am1x1+am2x2+amnxnbm x1,x2,xn 0 的情况下,使目标函数:f=c1x1+c2x2+cnxn 达到最大值或最小值。,Max/Min F=CX AXB 或 AXB X0 或 X0 或 X自由其中:C=(c1,c2,c
4、n)B=(b1,b2,bm)X=(x1,x2,xn)A=aij(i=1,2,m;j=1,2,n),一般来说,满足约束条件的变量X=(x1,x2,xn)T有无穷多个解,求解LP问题的目的就是从中找出一个能满足目标函数最大或最小的解,作为该LP问题的最终决策。决策变量、目标函数、约束条件是LP模型的三要素,其中后两者都是关于前者的线性表达式;而LP模型就是由最优化的目标函数和约束条件这两部分构成的。,二、线性规划的图解法,线性规划的图解法,就是借助几何图形来求解线性规划问题的一种方法。图解法的基本步骤:1.可行域的确定 LP模型所有约束条件共同构成的图形,称为可行域图形。2.目标函数的等值线和最优
5、点的确定,F(0,6),x1+x2=6,X1,X2,O,B(4,2),C(2,3),E(8,0),G(0,6),Z=20,Z=3x1+4x2,A(6,0),x1+2x2=8,x2=3,D(0,3),可以看到:当沿法线方向平行移动直线Z=3x1+4x2至B点时,Z值在可行域R上就达到了最大值,从而确定B点即为该LP问题的最优点。最优点的坐标值为最优解。记为X*=(x1*,x2*)T,X*对应的目标函数值称为最优值,记为Z*。该实例的最优解:X*=(4,2)T,Z*=20 说明最优生产方案是:生产甲产品4件,乙产品2件,可获得最大利润20千元。,LP问题几种可能的结果:唯一解;多重解;无界解;无可
6、行解。唯一解:只有一个最优点多重解:有些LP问题最优解可能不唯一,如:前例中目标函数改为:max Z=x1+2x2 则目标函数等值线与约束条件x1+2x28的边界线平行。当将等值线沿法线方向平移到B点时,就与R的边界线BC段重合。这表明BC上的每一点都使目标函数值取得同样的最大值。这时出现多重解的情形。,无界解:Max Z=3x1+2x2-2x1+x2 2 x1-3x2 3 x10,x2 0,s.t.,x1,x2,无可行解:有些LP问题可能不存在可行点,也就是说由约束条件得到的可行域R为空集,即R=。这时问题无可行解,也就无最优解了,简称无解。LP问题的可行域一般是凸多边形,而且若最优解存在,
7、则一定在可行域的某个顶点上得到;若在两个顶点同时得到最优解,则这两个顶点连线上的每一点都是最优解,且最优值相等;若可行域无界,则可能发生最优解无界的情况,此时无最优解。若可行域为空集,则问题无可行解。,三、线性规划的标准形式,LP问题的各种不同形式可以相互转化,只需给出其中一种形式的解法,就可以普遍适用于一切形式的LP问题,而单纯形法所基于的LP问题的形式,称为标准形式。,1.线性规划问题的标准形式,A=(aij)mn为约束方程组的系数阵。R(A)=mn,即A为满秩阵,称m为LP问题的阶数,n为维数,目标函数 min Z=CTX函数约束bi0 两端乘以-1约束为“”的情况,增加非负变量 松弛变
8、量约束为“”的情况,减去非负变量剩余变量决策变量对不满足非负性要求的变量,采用“变量代换法”,2.非标准形LP问题的标准化,max z=-CTX,举例:,如果xk0,可令xk=-xk,xk 0。如果xk为自由变量,可令xk=xk_xk,且xk0,xk0。如果方程中有多个xk为自由变量,按照上述方法会使变量的个数扩大一倍,从而增加问题求解时的计算量,为了尽量少地增加变量的个数,可以令xk=xk-x“,其中x“对每个xk的表达式都是同一个数。,变量代换法,四、线性规划的解及其性质,可行解:满足LP问题所有约束条件的向量X 可行域所有可行解构成的集合最优解:满足目标要求的可行解,记为X*,其所对应的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 线性规划基础 线性规划 基础 PPT 课件
链接地址:https://www.31ppt.com/p-5567000.html