《地学数理方法第十章线性规划ppt课件》由会员分享，可在线阅读，更多相关《地学数理方法第十章线性规划ppt课件（38页珍藏版）》请在装配图网上搜索。
1、第10章 线性规划与单纯形法本章要点：1。线性规划问题的数学模型；2。线性规划问题的基本理论；3。线性规划问题的求解。例1.1：美佳公司计划制造I，II两种家电产品。已知各制造一件时分别占用的设备A，B的台时、调试时间、调试工序及每天可用于这两种家电的能力、各售出一件时的获得情况，如表所示。问该公司应制造两种家电各多少件，使获取的利润为最大。项目III每天可用能力设备A（h）0515设备B（h）6224调试工序（h）115利润（元）21一、问题的提出线性规划问题与及其数学模型212xxZMax0,052426155.2121212xxxxxxxts解：设x1和x2分别表示美佳公司制造家电I和I
2、I的数量。则该问题可用线性规划模型表示如下：线性规划问题与及其数学模型线性规划问题与及其数学模型例1.2 某工厂计划生产A、B、C三种产品，每吨利润分别为2万元、3万元、1万元；生产单位产品所需的工时及原材料如表所示。如果供应的原材料每天不超过3吨，每天所能利用的劳动力总工时是固定的，问如何制定日生产计划，使三种产品总利润最大？1/31/3A7/34/3原 材 料1/31/3工时占总工时比例）CB每吨产品所需资源资源产品设每天生产A产品X1吨，B产品X2吨，C产品X3吨;则用数学语言可描述为：32132xxxZMax0,0,031.321337234131331231131xxxxxxxxxt
3、s线性规划问题与及其数学模型p例1.3 某工地租赁机械甲和乙来安装A、B、C三种构件。已知这两种机械每天的安装能力如表所示。而工程任务要求共安装250根A构件、300根B构件和700根C构件；又知机械甲每天租赁费为250元，机械乙每天租赁费为350元，试决定租赁机械甲和乙各多少天，才能使总租赁费最少？65A26机械乙108机械甲CB每天安装能力根）机械构件线性规划问题与及其数学模型设租赁甲X1天，机械乙X2天，为满足A、B、C的安装要求;则用数学语言可描述为：21350250 xxWMin0,070020103006825065.21212121xxxxxxxxts线性规划问题与及其数学模型二
4、、线性规划的数学模型共同特征：1决策变量向量X2约束条件向量AX=b3线性目标函数Z=CX其中：C为价值系数向量）A为约束条件系数矩阵线性规划问题与及其数学模型用数学语言可描述为：nnxcxcxcZ2211Max(Min)0,0,0),(),(),(.2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxats线性规划问题与及其数学模型线性规划模型的结构目标函数：max，min约束条件：,=,变量符号：0,unr,0unrXbAXt sCXZ,0)(),(.max(min)用矩阵描述为：线性规划问题与及其数学模型线性规划问题的求解p图解
5、法：适用于个决策变量p鞍面法：1992年中国沈阳化工学院尚毅教授发明。p内点法：1984年美国籍印度数学家Karmarker卡玛卡发明p椭球法：1979年苏联数学家Khachiyan哈奇扬发明p单纯形法：1952年美国斯坦福大学教授Dantzig丹茨格发明，可以解决1.5万至2万个决策变量。线性规划的求解一、图解法max z=x1+3x2s.t.x1+x26-x1+2x28x1 0,x20可行域目标函数等值线最优解64-860 x1x2线性规划的求解p图解法求解步骤p1建立直角坐标系；p2根据线性规划问题的约束条件和非负条件画出可行域；p3作出目标函数等值线Z=cc为一常数），并使其平移求得最
6、优解。线性规划的求解p线性规划的解的特殊情况p唯一解X1X2X1X222X1X222n无界解少了约束条件）n例 Max z=x1+2x2n st x1=1 n x2=2n无穷解头与身平行）n例 Max z=x1+x2n st 2x1+2x2=0,x2=0线性规划的求解二、线性规划问题的标准型1。线性规划问题的标准型统一规定：1目标函数取极大化类型也可以是极小化类型）；2所有约束条件用等式来表示；3所有决策变量取非负值；4每一约束条件的右端常数为非负值。线性规划的求解2。线性规划问题的标准型为：nnxcxcxcZ2211Max0,0,0.2122112222212111212111nmnmnmm
7、nnnnxxxbxaxaxabxaxaxabxaxaxats线性规划的求解p标准型缩写式为:njjjxcZ1Max0,.,.211nnjijijxxxbxats(i=1,2,m)线性规划的求解p向量形式为:p Max Z=CX0.1jnjjjxbxpts(j=1,2,n)线性规划的标准形式矩阵形式为：目标函数：max约束条件：=变量符号：0OXbAXtsCXZ.max线性规划的求解线性规划的求解l线性规划问题的标准化l1)目标函数的标准化：对于最小化问题MIN Z，化为最大化问题为：MAX Z=-Z=-CXkx kxkxkxkx kxp如不等号为“”，则左边减去一非负变量变为等式。p如不等号为
8、“”，则左边加上一非负变量变为等式。p若右端为负，则左右两同乘（-1即可。p若某个变量 无约束，则引入两个非负变量 ，p 可令2)约束条件的标准化线性规划的求解例1-432132xxxZMax0,0,031.321337234131331231131xxxxxxxxxts32132xxxZMax)5,.,2,1(031.53372341314331231131jxxxxxxxxxtsj线性规划的求解例1-5 将下面的线性规划问题化成标准型32132xxxZMin无符号限制321321321321,0,052327.xxxxxxxxxxxxts)(32 3321xxxxZMin0,0,05)(2
9、327.3321 3321 3321 3321xxxxxxxxxxxxxxxxts 333xxx令线性规划的求解)(32 3321xxxxZMin0,0,05)(2327.3321 3321 3321 3321xxxxxxxxxxxxxxxxts 3321332xxxxZMax0,0,0,0,0522327.54 3321 33215 33214 3321xxxxxxxxxxxxxxxxxxxxts线性规划的求解三、线性规划的解njjjxcZ1Max0,.,.211nnjijijxxxbxats(i=1,2,m)(1)(2)(3)1。l可行解：满足上面模型中的2和3式的解X；l最优解：满足上面
10、模型中的1的可行解X；l基矩阵）：若B是A中的mm阶非奇异子式即|B|0），则B是线性规划问题的一个基矩阵）；l 可设B=P1，P2，.，Pml则Pj为基向量，与Pj对应的变量xj为基本变量。线性规划的求解三、线性规划的解njjjxcZ1Max0,.,.211nnjijijxxxbxats(i=1,2,m)(1)(2)(3)1。mncl非基本变量：X中除基本变量外的变量；在方程AX=b中，令非基变量的值为0，求得基本变量的值，这样得到的一组解X0称为方程AX=b关于基B的基本解。一般mn,故基本解的个数 ；l基本可行解：满足模型中3式的基本解。线性规划的求解三、线性规划的解l解间的关系如下图所
11、示：基本可行解基本解可行解非可行解最优解基本可行解1。基本概念凸集：设K是n维欧氏空间的一个点集，若任意两点X(1)K，X(2)K的连线上的一切点满足下式：)10()1()2()1(其中KXX线性规划的求解四、线性规划问题解的几何意义则称K为凸集。顶点：设K为凸集，XK，若不能用两点X(1)K，X(2)K组合表示为：)2()1()1(XXX则X为K的一个顶点或极点）。线性规划的求解四、线性规划问题解的几何意义2。基本定理：定理1：线性规划问题的可行解集是一个凸集。即：定理2：设线性规划问题的可行解集为D，则X是D的一个顶点的充要条件是X是线性规划问题的基本可行解。定理3：若可行域非空有界，则线性规划问题的目标函数一定可以在可行域的顶点上达到最优值。0,|1jnjjjxbxpXD线性规划的求解四、线性规划问题解的几何意义基本结论：线性规划问题的所有可行解构成的集合是凸集；线性规划问题的每一个基本可行解都有对应可行域的一个顶点；若线性规划问题有最优解，必定在可行域的某个顶点上达到。
地学数理方法第十章线性规划ppt课件
