第二章线性规划与单纯形法精选PPT.ppt
《第二章线性规划与单纯形法精选PPT.ppt》由会员分享,可在线阅读,更多相关《第二章线性规划与单纯形法精选PPT.ppt(100页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第二章线性规划与单纯形法第1页,本讲稿共100页第二章 线性规划与单纯形法第1节 线性规划问题及其数学模型第2节 图解法第3节 解第4节 单纯形法原理及其计算步骤第5节 人工变量法第6节 小结第2页,本讲稿共100页第1节 线性规划问题及其数学模型一、规划如何合理地利用有限的人力、物力、财力等资源,以便得到最好的经济效果。第3页,本讲稿共100页第1节 线性规划问题及其数学模型例1:用一块边长为a的正方形铁皮做一个容器,应该如何裁剪,使做成的容器的容积最大(如下图所示)。ax第4页,本讲稿共100页第1节 线性规划问题及其数学模型例1:解:设在铁皮四个角上剪去四个边长各为x的正方形 V=(a-
2、2x)(a-2x)xmax 满足 xa/2 x0第5页,本讲稿共100页第1节 线性规划问题及其数学模型例2:某企业计划生产、两种产品,都要分别在A,B,C,D四种不同设备上加工。按工艺资料规定,生产每件产品需占用各设备分别为2,1,4,0(小时),生产每件产品需占用各设备分别为2,2,0,4(小时)。已知各设备计划期内用于生产这两种产品的能力分别为12,8,16,12(小时),又知每生产一件产品,企业能获利2元,每生产一件产品,企业能获利3元。问:该企业应如何安排生产两种产品各多少件,使企业的利润收入最大。第6页,本讲稿共100页第1节 线性规划问题及其数学模型例2:解:设、两种产品在计划期
3、内的产量分别为x1、x2 z=2x1+3x2max 2x1+2x212 x1+2x28 满足 4x116 4x212 x1,x20表示形式第7页,本讲稿共100页第1节 线性规划问题及其数学模型二、数学规划研究在一些给定的条件下,求所考察函数在某种意义下的极值问题。第8页,本讲稿共100页第1节 线性规划问题及其数学模型特征(1)决策变量(2)约束条件(3)目标函数第9页,本讲稿共100页第1节 线性规划问题及其数学模型三、线性规划问题l特征(三要素)(1)决策变量:问题中的未知量(2)目标函数:问题要达到的目标(最大或最小),表示为决策变量的线性函数(3)约束条件:表示为含决策变量的一组互不
4、矛盾的线性等式或线性不等式的函数约束和决策变量的非负约束第10页,本讲稿共100页第1节 线性规划问题及其数学模型V=(a-2x)(a-2x)xmax xa/2 x0z=2x1+3x2max 2x1+2x212 x1+2x28 4x116 4x212 x1,x20第11页,本讲稿共100页第1节 线性规划问题及其数学模型线性规划问题数学模型的形式(1)一般形式第12页,本讲稿共100页第1节 线性规划问题及其数学模型(2)简写形式(3)向量形式 (4)矩阵形式第13页,本讲稿共100页第1节 线性规划问题及其数学模型例3:写出例2数学模型的一般形式和矩阵形式。一般形式 矩阵形式 max z=2
5、x1+3x2 2x1+2x212 x1+2x28 4x116 4x212 x1,x20解第14页,本讲稿共100页第1节 线性规划问题及其数学模型四、线性规划数学模型的标准形式(标准型)l目标函数求最大值l函数约束条件全为等式l决策变量全为非负l函数约束条件右端项全为非负第15页,本讲稿共100页第1节 线性规划问题及其数学模型五、线性规划的非标准型如何转化为标准型l目标函数求最小值:令z-zl函数约束条件为不等式:在函数约束条件左端加非负的松弛变量 :在函数约束条件左端减非负的松弛变量 松弛变量在目标函数中的系数全为0l决策变量为负值:令xj-xj,xj0l决策变量取值无约束:令xj xj-
6、xj,xj0,xj0l函数约束条件右端项(bi)为负值:函数约束条件两端同乘-1第16页,本讲稿共100页第1节 线性规划问题及其数学模型要求:将下列线性规划问题转化为标准型。例4:min z=x1+2x2+3x3 -2x1+x2+x39 -3x1+x2+2x34 3x1-2x2-3x3=-6 x10,x20,x3取值无约束第17页,本讲稿共100页第1节 线性规划问题及其数学模型例4:解:令 max z=x1-2x2-3x3+3x3+0 x4+0 x5 2x1+x2+x3-x3+x4=9 3x1+x2+2x3-2x3-x5=4 3x1+2x2+3x3-3x3=6 x1,x2,x3,x3,x4
7、,x50第18页,本讲稿共100页第1节 线性规划问题及其数学模型例5:min z=-x1+2x2-3x3 x1+x2+x37 x1-x2+x32 -3x1+x2+2x3=5 x1,x20,x3无约束第19页,本讲稿共100页第1节 线性规划问题及其数学模型例5:解:令 max z=x1-2x2-3x3+3x3 x1+x2+x3-x3+x4=7 x1-x2+x3-x3-x5=2 -3x1+x2+2x3-2x3=5 x1,x2,x3,x3,x4,x50第20页,本讲稿共100页第1节 线性规划问题及其数学模型例6:max z=2x1+3x2+5x3 x1+x2-x3-5 -6x1+7x2-9x3
8、=16 19x1-7x25x313 x1,x20,x3无约束第21页,本讲稿共100页第1节 线性规划问题及其数学模型例6:解:令 max z=2x1+3x2+5x3-5x3 -x1-x2+x3-x3+x4=5 -6x1+7x2-9x3+9x3=16 19x1-7x2+5x3-5x3+x5=13 -19x1+7x2-5x3+5x3+x6=13 x1,x2,x3,x3,x4,x5,x60第22页,本讲稿共100页作业2-1作业2-1:将下列线性规划问题化为标准型。1、min z=5x1-2x2+4x3-3x4 -x1+2x2-x3+4x4=-2 -x1+3x2+x3+x414 2x1-x2+3x
9、3-x42 x1无约束,x20,x3,x402、min z=x1+2x2+4x3 2x1+x2+3x320 3x1+x2+4x325 x1,x20,x30第23页,本讲稿共100页第2节 解线性规划问题数学模型的标准型(以一般形式表示)第24页,本讲稿共100页第2节 解一、线性规划问题解的概念l可行解:满足函数约束条件和非负约束条件的解,全部可行解的集合称为可行域l最优解:使目标函数达到最大值的可行解,对应的目标函数值称为最优值第25页,本讲稿共100页第2节 解基:设A是约束方程组的mn阶系数矩阵,B是矩阵A中mm阶非奇异子矩阵,称B是线性规划问题的一个基基向量:基B中每一个列向量Pj非基
10、向量:A中其余列向量Pj(不在B中)基变量:与基向量Pj对应的决策变量xj非基变量:与非基向量对应的决策变量基解基可行解:满足非负约束条件的基解可行基:对应于基可行解的基克莱姆法则非奇异矩阵解的关系第26页,本讲稿共100页第2节 解非奇异矩阵:行列式不等于0的矩阵。克莱姆法则:如果线性方程组 a11x1+a12x2+a1mxm=b1 a21x1+a22x2+a2mxm=b2 am1x1+am2x2+ammxm=bm 的系数行列式不等于0,则方程组有唯一解。第27页,本讲稿共100页第2节 解二、线性规划问题解的关系最优解第28页,本讲稿共100页第2节 解例7:写出例2的标准型,并指出基、基
11、变量、基解、基可行解和可行基。第29页,本讲稿共100页第2节 解例7:标准型max z=2x1+3x2 2x1+2x212 x1+2x28 4x116 4x212 x1,x20 max z=2x1+3x2 2x1+2x2+x3=12 x1+2x2+x4=8 4x1+x5=16 4x2+x6=12 x1-60图解法第30页,本讲稿共100页第2节 解例8:求下述线性规划的所有基解、基可行解及最优解。max z=3x1+x2+3x3 x1+x2+x32 x1+2x2+4x36 x1,x2,x30第31页,本讲稿共100页作业2-2作业2-2:求下列线性规划的所有基解、基可行解及最优解。1、max
12、 z=2x1+3x2+4x3+7x4 2x1+3x2-x3-4x48 -x1+2x2-6x3+7x43 x1,x2,x3,x402、max z=-5x1+2x2-3x3+6x4 x1+2x2+3x3+4x47 2x1+x2+x3+2x43 x1,x2,x3,x40第32页,本讲稿共100页第3节 图解法一、图解法l适用条件:适用于求解只有两个决策变量的线性规划问题l特点(1)不必将线性规划问题转化为标准型(2)直观性强,计算方便第33页,本讲稿共100页第3节 图解法例9:用图解法求解下述线性规划问题。max z=2x1+3x2 x1+2x28 4x116 4x212 x1,x20第34页,本
13、讲稿共100页第3节 图解法例9:标出约束条件(0,0)(0,3)(2,3)(4,2)(4,0)第35页,本讲稿共100页第3节 图解法例9:标出目标函数目标函数z唯一最优解第36页,本讲稿共100页第3节 图解法二、图解法的求解步骤l建立 二维坐标系l将约束条件表示在坐标系中,以确立可行域画出每个函数约束的约束边界,用原点判断直线的哪一边是约束条件所允许的找出所有约束条件都同时满足的区域,即可行域l将目标函数绘制在坐标系中,并标出变化的方向给定目标函数一个特定的值k,画出目标函数特定线,当k变化时,目标函数特定线将平行移动对于目标函数最大(小)化的问题,找出目标函数增加(减少)的方向,目标函
14、数最后离开可行域的点是最优解l确定最优解第37页,本讲稿共100页第3节 图解法三、图解法解的类型l唯一最优解:仅有一点使目标函数值取得最大(小)值l无穷多(多重)最优解:线段(射线)上任意一点都使目标函数值取得相同的最大(小)值l无界解:可行域无界,目标函数值可以增大到无穷大l无可行解:可行域为空集l无界解和无可行解统称为无最优解第38页,本讲稿共100页第3节 图解法要求:用图解法求解下列线性规划问题。例10:max z=2x1+4x2 x1+2x28 4x116 4x212 x1,x20第39页,本讲稿共100页第3节 图解法例10:目标函数 max z=2x1+4x2 z多重最优解第4
15、0页,本讲稿共100页第3节 图解法例11:max z=2x1+3x2 4x116 x1,x20无界解第41页,本讲稿共100页第3节 图解法例12:max z=2x1+3x2 2x1+2x212 x1+2x214 x1,x20无可行解第42页,本讲稿共100页第3节 图解法四、图解法解的特点l当可行域非空集时,可行域必是有界或无界凸多边形。(凸集:集合C中任意两个点a和b,其连线上所有点也必为集合C中的点。)l若可行域有界,则目标函数一定可以在可行域的顶点上达到最优;若可行域无界,则可能无最优解,也可能有最优解,若有也必定在某顶点上达到。第43页,本讲稿共100页第3节 图解法线性规划问题的
16、每个基可行解对应可行域的一个顶点。线性规划问题的最优解在顶点上达到,则一定存在一个基可行解是最优解。若有唯一最优解,则一定在可行域的某个顶点处得到;若有两个顶点同时达到最优解,则两个顶点之间线段上的任意一点都是最优解,既有无穷多最优解。线性规划问题有最优解,则解题思路:找出可行域的顶点,计算顶点处的目标函数值,比较各顶点的目标函数值,值最大(小)的顶点为最优解的点或最优解的点之一。第44页,本讲稿共100页第3节 图解法例13:下列哪一个图是凸集?A BC D凸多边形第45页,本讲稿共100页第3节 图解法例9图解:目标函数z第46页,本讲稿共100页第3节 图解法例10图解:目标函数 max
17、 z=2x1+4x2 z顶点最优第47页,本讲稿共100页第3节 图解法要求:用图解法求解下列线性规划问题。例14:min z=2x1-x2 -2x1+x22 x1-2x21 x1,x20无界可行域第48页,本讲稿共100页第3节 图解法例15:1、max z=x1+x2 -2x1+x24 x1-x22 x1,x20 2、max z=x1+2x2 x1+2x28 4x116 4x212 x1,x20第49页,本讲稿共100页第3节 图解法例15:2、(0,0)(0,3)(2,3)(4,2)(4,0)第50页,本讲稿共100页作业2-3作业2-3:用图解法求解下列线性规划问题。1、max z=5
18、0 x1+100 x2 x1+x2300 2x1+x2400 x2250 x1,x202、max z=4x1+8x2 2x1+2x210 -x1+x2 8 x1,x203、max z=3x1+9x2 x1+3x222 -x1+x24 x26 2x1-5x20 x1,x204、max z=2x1+2x2 x1-x2 -1 -0.5x1+x2 2 x1,x20第51页,本讲稿共100页第4节 单纯形法原理及其计算步骤例16:求解下述线性规划问题。max z=2x1+3x2 x1+2x28 4x116 4x212 x1,x20第52页,本讲稿共100页第4节 单纯形法原理及其计算步骤例16:解:方法
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第二 线性规划 单纯 精选 PPT
限制150内