《线性规划及其对偶问题ppt课件》由会员分享，可在线阅读，更多相关《线性规划及其对偶问题ppt课件（153页珍藏版）》请在金锄头文库上搜索。
1、线性规划及其对偶问题,1 线性规划问题及其数学模型 2 线性规划问题的图解法 3 单纯形法 4 对偶问题 5 EXCEL求解线性规划 6 灵敏度分析,1 线性规划问题及其数学模型,(1) 线性规划问题,例、生产组织与计划问题,A, B 各生产多少, 可获最大利润?,解: 设产品A, B产量分别为变量x1， x2 可以建立如下的数学模型：,Max Z= 40 x1 +50 x2,目标函数,约束条件,例 某建筑设计院设计每万办公建筑和工业厂房需要的建筑师、结构工程师、设备工程师和电气工程师的平均人数列在表。问该院应如何安排设计任务，才能使设计费收入最大?,解设办公建筑和工业厂房各承揽、万。根据题意
2、 max Z36x120 x2 5 x1x228 s.t 3 x12x228 2 x1x212 x12x210 x1 、x2 0,例、合理下料问题,设按第i种方案下料的原材料为xi根,例、运输问题,求：运输费用最小的运输方案。,解：设xij为i 仓库运到j工厂的产品数量 其中：i 1，2，3 j 1，2，3,Min Z= 2x11 + x12+3x13+2x21 +2x22 +4x23 +3x31 +4x32 +2x33,x11 + x12+ x13 = 50 x21 + x22+ x23 = 30 x31 + x32+ x33 = 10 x11 + x21+ x31 = 40 x12 + x
3、22+ x32 = 15 x13 + x23+ x33 = 35 xij 0,s.t,(2) 线性规划问题的特点,决策变量： (x1 xn)T 代表某一方案， 决策者要考虑和控制的因素非负； 目标函数：Z=(x1 xn) 为线性函数，求Z极大或极小; 约束条件：可用线性等式或不等式表示. 具备以上三个要素的问题就称为 线性规划问题。,目标函数,约束条件,(3) 线性规划模型一般形式,隐含的假设 比例性：决策变量变化引起目标的改变量与决策变量改变量成正比 可加性：每个决策变量对目标和约束的影响独立于其它变量 连续性：每个决策变量取连续值 确定性：线性规划中的参数aij , bi , cj为确定值
4、,2 线性规划问题的图解法,定义1：满足约束(2)的X=(X1 Xn)T称为线性规划问题的可行解，全部可行解的集合称为可行域。,定义2：满足(1)的可行解称为线性规划问题的最优解。,例1 Max Z=40X1+ 50X2,解：(1)、确定可行域 X1+2X2 30 3X1+2X2 60 2X2 24 X1 0 X2 0,2X2 24,X1+2X2 30,3X1+2X2 60,X1 0,X2 0,可行域,(2)、求最优解,最优解： X* = (15,7.5) Zmax =975,Z=40X1+50X2 0=40X1+50X2 (0,0)， (10,-8) C点： X1+2X2 =30 3X1+2
5、X2 =60,0,20,30,10,10,20,30,X1,X2,最优解 Z=975,可行解 Z=0,等值线,例2、 Max Z=40X1+ 80X2,s.t,解：(1)、确定可行域与上例完全相同。 (2)、求最优解,0,20,30,10,10,20,30,最优解 Z=1200,最优解：BC线段,最优解：BC线段 B点：X(1)=(6,12) C点：X(2)=(15,7.5) X=X(1)+(1-)X(2) (0 1),Max Z=1200,X1 =6 +(1- )15 X2=12+(1- )7.5,X1 =15-9 X2 =7.5+4.5 (0 1),例3、 Max Z=2X1+ 4X2,2
6、X1+X2 8 -2X1+X2 2 X1 , X2 0,s.t,Z=0,-2X1+X2 2,2X1+X2 8,X1 0,X20,可行域,无界 无有限最优解,无有限最优解,可行域 无上界,例4、 Max Z=3X1+2X2,-X1 -X2 1 X1 , X2 0,无可行域 无可行解,0,s.t,X2 0,X1 0,-X1 -X2 1,直观结论,线性规划问题的解有四种情况 唯一最优解 无穷多最优解 无有限最优解 无可行解 若线性规划问题有解，则可行域是一个凸多边形（或凸多面体）； 若线性规划问题有最优解，则 唯一最优解对应于可行域的一个顶点； 无穷多个最优解对应于可行域的一条边；,3 单纯形法,3
7、.1 线性规划问题的标准形式 3.2 线性规划问题的基本解 3.3 单纯形法的基本思想,3.1 线性规划问题的标准形式,目标函数,约束条件,(1) 线性规划模型一般形式,价值系数,决策变量,技术系数,右端常数,(2) 线性规划模型标准形式,价值向量,决策向量,系数矩阵,右端向量,(3) 线性规划模型矩阵形式,对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:,(4) 一般型向标准型的转化,目标函数 目标函数为极小化 约束条件 分两种情况：大于、小于 决策变量 可能存在小于零的情况,3.2 线性规划问题的基本解,(1) 解的基本概念,定义 在线性规划问题中，约束方程组
8、(2)的系数矩阵A(假定 )的任意一个 阶的非奇异(可逆)的子方阵B(即 )，称为线性规划问题的一个基阵或基。,基阵,非基阵,基 向 量,非 基 向 量,基变量,非基变量,令,则,定义 在约束方程组(2) 中，对于一个选定的基B，令所有的非基变量为零得到的解，称为相应于基B的基本解。,定义 在基本解中，若该基本解满足非负约束，即 ，则称此基本解为基本可行解，简称基可行解；对应的基B称为可行基。,基本解中最多有m个非零分量。,基本解的数目不超过 个。,若B满足下列条件，称为最优基 称为最优解,例 现有线性规划问题,试求其基本解、基本可行解。,解: (1)首先将原问题转化为标准型 引入松弛变量x3
9、和x4,(2) 求基本解 由上式得,可能的基阵,由于所有|B| 0，所以有6个基阵和6个基本解。,对于基阵,令,则,对于基阵,令,则,为基本可行解，B13为可行基,为基本可行解，B12为可行基,对于基阵,令,则,对于基阵,令,则,对于基阵,令,则,对于基阵,令,则,为基本可行解，B24为可行基,为基本可行解，B34为可行基,0,A,B,C,D,E,所以，本问题存在6个基本解，其中4个为基可行解.,(2) 几点结论,若线性规划问题有可行解,则可行域是一个凸多边形或凸多面体(凸集),且仅有有限个顶点(极点); 线性规划问题的每一个基可行解都对应于可行域上的一个顶点(极点); 若线性规划问题有最优解
10、,则最优解必可在基可行解(极点)上达到; 线性规划问题的基可行解(极点)的个数是有限的,不会超过 个.,上述结论说明: 线性规划的最优解可通过有限次运算在基可行解中获得.,3.3 单纯形法,(1) 单纯形法的引入,(2)表格单纯形法,n,j,m+1,k,1,- CBTb*,amn,amj,amm+1,0,am1,bm*,xm,cm,akn,akj,akm+1,akk,ak1,bk*,xk,ck,a1n,a1j,a1m+1,a1k,a11,b1*,x1,c1,xn,xj,xm+1,xm,xk,x1,b*,XB,CB,cn,cj,cm+1,cm,ck,c1,cj ,单纯形表,amm,m,maxZc
11、1x1十c2x2十十cnxn a11x1a12x2十十a1nxnb1 a21x1a22x2十十a2nxnb2 am1x1am2x2十十amnxnbm xj0 (jl、2、，n),a1m,x3,x5,x4,0,0,0,10,18,0,0,0,170/2,100/3,150/5,maxZ10 x118x2 （1） 5x12x2 x3170 s.t 2x13x2x4100 （2） x15x2x5150 xj0 （j1，2，3，4，5）,主元,x3,x4,0,0,x2,1,0,0,18,1/5,0,0,1/5,30,10,110（0 23/ 50 7/518 1/5）32/5,7/5,0,1,110,
12、23/5,1,3/5,0,2/5,32/5,0,0,0,18/5,550/23,50/7,150,maxZ10 x118x2 （1） 5x12x2 x3170 s.t 2x13x2x4100 （2） x15x2x5150 xj0 （j1，2，3，4，5）,218 （0 00 018 1） 0,10100（30 3）,7/52（1/5 3）,x3,x1,x2,0,10,18,1,50/7,0,0,5/7,3/7,540/7,0,0,1,23/7,11/7,200/7,0,1,0,1/7,2/7,X*=(50/7, 200/7, 540/7, 0, 0)T Z*=4100/7,0,0,0,32/7
13、,6/7,例 某房地产公司欲开发一七通一平空地，总面积2500m2。公司原计划开发商业楼1000m2，住宅楼5250m2。请根据下列前提条件，确定其是否最佳开发方式。 (1)根据规划要求：沿马路建商业房，为4层楼框架结构，其余为砖混住宅，为6层楼；容积率为2.5，建筑密度50%。 (2)开发日期为2019年12月，建筑物完成时间不超过一年半。 (3)根据预测，一年半以后商业楼平均造价为1400元/m2，砖混住宅平均造价为950元/m2 ，不计土地成本。 (4)预计建筑物完成后商业楼及住宅均可全部售出，商业楼出售当时的平均售价为2400元/m2 ，住宅楼出售当时的平均售价为1700元/m2 。
14、(5)物业出售时的税费为总额的5%。 (6)公司投入资金不超过650万元。,分析： 容积率总建筑面积/总占地面积 建筑密度建筑基地总面积/总占地面积 (1)总建筑面积 25002.5=6250m2 (2)建筑基地总面积 250050%1250m2 (3)商业楼每平方米的利润: (0.240.14一0.245%)=0.088(万元/m2) (4)住宅楼每平方米的利润: (0.17一0.095一0.175%)=0.0665(万元/m2),设商业楼建筑面积为x1m2;砖混住宅建筑面积为x2m2 求x1、x2 目标函数max Z=0.088 x10.0665 x2 满足: x1x26250 x1/4+
15、x2/61250 0.14 x1十0.095 x2650 x1、x20,(1)总建筑面积 25002.5=6250m2 (2)建筑基地总面积 250050%1250m2 (3)商业楼每平方米的利润: (0.240.14一0.245%)=0.088(万元/元m2) (4)住宅楼每平方米的利润: (0.17一0.095一0.175%)=0.0665(万元/m2),为了便于计算，变换一下约束条件及目标函数。（由于在整个价值最优程序中只是相对的价值是重要的，而不是它们绝对值。绝对值的值只影响目标函数的最后值，但不影响设计变量的最优值）因此，我们可以将其变换为: x1/4+x2/61250 转变为 3 x1十2 x215000 0.14 x1十0.095 x2650 转变为 1.4737 x1十x26842 max Z=0.088 x10.0665 x2 转变为 max Z= Z /0.06651.323 x1x2,max Z=0.088 x10.0665 x2 x1x26250 x1/4+x2/61250 0.14 x1十0.095 x2650 x1、x20,数学模型 max Z= 1.323 x1+x2 x1x26250 3
