资源描述：
《《线性规划基础》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第六章线性规划基础---------环境系统污染控制规划的数学基础6.1线性规划概述线性规划是数学规划与运筹学的一个分支，是运筹学中最重要的一种数学方法。主要研究解决有限资源的最佳分配问题，即如何对有限的资源作出最佳方式的调配和最有利的使用，以便最充分地发挥资源的效能去获取最佳经济效益。这种数学规划的方法，如果用数学语言表达，就是在一定的约束条件下，寻找目标函数的极值问题。所谓线性规划，是指约束条件为线性等式或不等式，且目标函数也是线性函数。生产调度问题1.线性规划问题的提出一、线性规划及其数学模型某企业生产甲、乙两种产品，分别用A、B、C3种不同的原料，
2、每生产1个单位的甲，需用1个单位的A、1个单位的B、0个单位的C，利润为3千元；每生产1个单位的乙，需用1个单位的A、2个单位的B、1个单位的C，利润为4千元；现有6个单位的A、8个单位的B、3个单位的C，问企业如何安排生产，可使利润最大。产品甲乙x1x2原料ABC利润11031214原料限制6832.建模的步骤(1)明确问题的经济背景(2)设定决策变量(3)明确目标----给出目标函数(4)明确问题的所有限制-------给出约束条件Z=3x1+4x2x1+x2≤6x1+2x2≤8x2≤3x1≥0,x2≥0每天总利润：Z=3x1+4x2变量x1和x2必须
3、满足三个条件：x1+x2≤6x1+2x2≤8x2≤3非负性约束：x1≥0,x2≥0目标函数决策变量函数约束约束条件MaxZ=3x1+4x2x1+x2≤6x1+2x2≤8x2≤3x1≥0,x2≥0数学模型s.t.线性规划的数学表达即求一组变量x1,x2,…,xn,在满足约束条件：a11x1+a12x2+…+a1nxn≤b1a21x1+a22x2+…+a2nxn≤b2……am1x1+am2x2+…+amnxn≤bmx1,x2,…,xn≥0的情况下，使目标函数：f=c1x1+c2x2+…+cnxn达到最大值或最小值。Max/MinF=C•XA•X≤B或A•X≥B
4、X≥0或X≤0或X自由其中：C=(c1,c2,…,cn)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模型就是由最优化的目标函数和约束条件这两部分构成的。二、线性规划的图解法线性规划的图解法，就是借助几何图形来求解线性规划问题的一种方法。图解法
5、的基本步骤：1.可行域的确定LP模型所有约束条件共同构成的图形，称为可行域图形。2.目标函数的等值线和最优点的确定F(0,6)x1+x2=6X1X2OB(4,2)C(2,3)E(8,0)G(0,6)Z=20Z=3x1+4x2A(6,0)x1+2x2=8x2=3D(0,3)可以看到：当沿法线方向平行移动直线Z=3x1+4x2至B点时，Z值在可行域R上就达到了最大值，从而确定B点即为该LP问题的最优点。最优点的坐标值为最优解。记为X*=(x1*,x2*)T,X*对应的目标函数值称为最优值，记为Z*。该实例的最优解：X*=(4,2)T,Z*=20说明最优生产方案
6、是：生产甲产品4件，乙产品2件，可获得最大利润20千元。LP问题几种可能的结果：唯一解；多重解；无界解；无可行解。唯一解：只有一个最优点多重解：有些LP问题最优解可能不唯一，如:前例中目标函数改为：maxZ=x1+2x2则目标函数等值线与约束条件x1+2x2≤8的边界线平行。当将等值线沿法线方向平移到B点时，就与R的边界线BC段重合。这表明BC上的每一点都使目标函数值取得同样的最大值。这时出现多重解的情形。无界解：MaxZ=3x1+2x2-2x1+x2≤2x1-3x2≤3x1≥0,x2≥0s.t.x1x2无可行解：有些LP问题可能不存在可行点，也就
7、是说由约束条件得到的可行域R为空集，即R=Ø。这时问题无可行解，也就无最优解了，简称无解。LP问题的可行域一般是凸多边形，而且若最优解存在，则一定在可行域的某个顶点上得到；若在两个顶点同时得到最优解，则这两个顶点连线上的每一点都是最优解，且最优值相等；若可行域无界，则可能发生最优解无界的情况，此时无最优解。若可行域为空集，则问题无可行解。三、线性规划的标准形式LP问题的各种不同形式可以相互转化，只需给出其中一种形式的解法，就可以普遍适用于一切形式的LP问题，而单纯形法所基于的LP问题的形式，称为标准形式。1.线性规划问题的标准形式A=（aij）m×n为约束
8、方程组的系数阵。R(A)=m
