《地学数理方法线性规划课件》由会员分享，可在线阅读，更多相关《地学数理方法线性规划课件（38页珍藏版）》请在金锄头文库上搜索。
1、第10章 线性规划与单纯形法本章要点：1。线性规划问题的数学模型；2。线性规划问题的基本理论；3。线性规划问题的求解。例1.1：美佳公司计划制造I，II两种家电产品。已知各制造一件时分别占用的设备A，B的台时、调试时间、调试工序及每天可用于这两种家电的能力、各售出一件时的获得情况，如表所示。问该公司应制造两种家电各多少件，使获取的利润为最大。项目III每天可用能力设备A（h）0515设备B（h）6224调试工序（h）115利润（元）21一、问题的提出线性规划问题与及其数学模型Max解：设x1和x2分别表示美佳公司制造家电I和II的数量。则该问题可用线性规划模型表示如下：线性规划问题与及其数学模
2、型线性规划问题与及其数学模型p例1.2 某工厂计划生产A、B、C三种产品，每吨利润分别为2万元、3万元、1万元；生产单位产品所需的工时及原材料如表所示。如果供应的原材料每天不超过3吨，每天所能利用的劳动力总工时是固定的，问如何制定日生产计划，使三种产品总利润最大？1/31/3A7/34/3原 材 料1/31/3工时（占总工时比例）CB每吨产品所需资源资源产品设每天生产A产品X1吨，B产品X2吨，C产品X3吨;则用数学语言可描述为：Max线性规划问题与及其数学模型p例1.3 某工地租赁机械甲和乙来安装A、B、C三种构件。已知这两种机械每天的安装能力如表所示。而工程任务要求共安装250根A构件、3
3、00根B构件和700根C构件；又知机械甲每天租赁费为250元，机械乙每天租赁费为350元，试决定租赁机械甲和乙各多少天，才能使总租赁费最少？65A26机械乙108机械甲CB每天安装能力（根）机械构件线性规划问题与及其数学模型设租赁甲X1天，机械乙X2天，为满足A、B、C的安装要求;则用数学语言可描述为：Min线性规划问题与及其数学模型二、线性规划的数学模型共同特征：1）决策变量（向量）X2）约束条件（向量）AX=b3）线性目标函数Z=CX其中：C为价值系数（向量） A为约束条件系数矩阵线性规划问题与及其数学模型用数学语言可描述为：Max(Min)线性规划问题与及其数学模型线性规划模型的结构目标
4、函数 ：max，min约束条件：,=,变量符号：0, unr, 0用矩阵描述为：线性规划问题与及其数学模型线性规划问题的求解p图解法：适用于个决策变量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-860x1x2线性规划的求
5、解p图解法求解步骤1）建立直角坐标系；2）根据线性规划问题的约束条件和非负条件画出可行域；3）作出目标函数等值线Z=c（c为一常数），并使其平移求得最优解。线性规划的求解p线性规划的解的特殊情况n唯一解X1X2X1X222X1X222n无界解（少了约束条件）例 Max z=x1+2x2 st x1=1 x2=2n无穷解（头与身平行）例 Max z=x1+x2 st 2x1+2x2=0,x2=0线性规划的求解二、线性规划问题的标准型1。线性规划问题的标准型统一规定：1）目标函数取极大化类型（也可以是极小化类型）；2）所有约束条件用等式来表示；3）所有决策变量取非负值；4）每一约束条件的右端常数为
6、非负值。线性规划的求解2。线性规划问题的标准型为：Max线性规划的求解p标准型缩写式为:Max(i=1,2,m)线性规划的求解p向量形式为: Max Z=CX(j=1,2,n)线性规划的标准形式矩阵形式为：目标函数：max约束条件：=变量符号：0线性规划的求解线性规划的求解l线性规划问题的标准化1)目标函数的标准化：对于最小化问题MIN Z，化为最大化问题为：MAX Z=-Z=-CXp如不等号为“”，则左边减去一非负变量变为等式。p如不等号为“” ，则左边加上一非负变量变为等式。p若右端为负，则左右两同乘（-1）即可。p若某个变量 无约束，则引入两个非负变量 ， 可令2)约束条件的标准化线性规
7、划的求解例1-4MaxMax线性规划的求解例1-5 将下面的线性规划问题化成标准型MinMin线性规划的求解MinMax线性规划的求解三、 线性规划的解Max(i=1,2,m)(1)(2)(3)1。l可行解：满足上面模型中的（2）和（3）式的解X；l最优解：满足上面模型中的（1）的可行解X；l基（矩阵）：若B是A中的mm阶非奇异子式（即|B|0），则B是线性规划问题的一个基（矩阵）； 可设B=P1，P2，.，Pm则Pj为基向量，与Pj对应的变量xj为基（本）变量。线性规划的求解三、 线性规划的解Max(i=1,2,m)(1)(2)(3)1。l非基（本）变量：X中除基（本）变量外的变量；在方程A
8、X=b中，令非基变量的值为0，求得基本变量的值，这样得到的一组解X0称为方程AX=b关于基B的基本解。一般mn,故基本解的个数 ；l基本可行解：满足模型中（3）式的基本解。线性规划的求解三、 线性规划的解l解间的关系如下图所示：基本可行解基本解可行解非可行解最优解基本可行解1。基本概念l凸集：设K是n维欧氏空间的一个点集，若任意两点X(1)K，X(2)K的连线上的一切点满足下式：线性规划的求解四、线性规划问题解的几何意义则称K为凸集。l顶点：设K为凸集，XK，若不能用两点X(1)K，X(2)K组合表示为：则X为K的一个顶点（或极点）。线性规划的求解四、线性规划问题解的几何意义2。基本定理：定理1：线性规划问题的可行解集是一个凸集。即：定理2：设线性规划问题的可行解集为D，则X是D的一个顶点的充要条件是X是线性规划问题的基本可行解。定理3：若可行域非空有界，则线性规划问题的目标函数一定可以在可行域的顶点上达到最优值。线性规划的求解四、线性规划问题解的几何意义基本结论：l线性规划问题的所有可行解构成的集合是凸集；l线性规划问题的每一个基本可行解都有对应可行域的一个顶点；l若线性规划问题有最优解，必定在可行域的某个顶点上达到。
