地学数理方法第十章线性规划.ppt

第10章线性规划与单纯形法,本章要点：1。线性规划问题的数学模型；2。线性规划问题的基本理论；3。线性规划问题的求解。,例1.1：美佳公司计划制造I，II两种家电产品。已知各制造一件时分别占用的设备A，B的台时、调试时间、调试工序及每天可用于这两种家电的能力、各售出一件时的获得情况，如表所示。问该公司应制造两种家电各多少件，使获取的利润为最大。,一、问题的提出,线性规划问题与及其数学模型,Max,解：设x1和x2分别表示美佳公司制造家电I和II的数量。则该问题可用线性规划模型表示如下：,线性规划问题与及其数学模型,线性规划问题与及其数学模型,例1.2某工厂计划生产A、B、C三种产品，每吨利润分别为2万元、3万元、1万元；生产单位产品所需的工时及原材料如表所示。如果供应的原材料每天不超过3吨，每天所能利用的劳动力总工时是固定的，问如何制定日生产计划，使三种产品总利润最大？,设每天生产A产品X1吨，B产品X2吨，C产品X3吨;则用数学语言可描述为：,Max,线性规划问题与及其数学模型,例1.3某工地租赁机械甲和乙来安装A、B、C三种构件。已知这两种机械每天的安装能力如表所示。而工程任务要求共安装250根A构件、300根B构件和700根C构件；又知机械甲每天租赁费为250元，机械乙每天租赁费为350元，试决定租赁机械甲和乙各多少天，才能使总租赁费最少？,线性规划问题与及其数学模型,设租赁甲X1天，机械乙X2天，为满足A、B、C的安装要求;则用数学语言可描述为：,Min,线性规划问题与及其数学模型,二、线性规划的数学模型共同特征：1）决策变量（向量）X2）约束条件（向量）AX=b3）线性目标函数Z=CX,其中：C为价值系数（向量）A为约束条件系数矩阵,线性规划问题与及其数学模型,用数学语言可描述为：,Max(Min),线性规划问题与及其数学模型,线性规划模型的结构目标函数：max，min约束条件：,=,变量符号：0,unr,0,用矩阵描述为：,线性规划问题与及其数学模型,线性规划问题的求解,图解法：适用于个决策变量,鞍面法：1992年中国沈阳化工学院尚毅教授发明。,内点法：1984年美国籍印度数学家Karmarker（卡玛卡）发明,椭球法：1979年苏联数学家Khachiyan（哈奇扬）发明,单纯形法：1952年美国斯坦福大学教授Dantzig（丹茨格）发明，可以解决1.5万至2万个决策变量。,线性规划的求解,一、图解法maxz=x1+3x2s.t.x1+x26-x1+2x28x10,x20,可行域,目标函数等值线,最优解,6,4,-8,6,0,x1,x2,线性规划的求解,图解法求解步骤1）建立直角坐标系；2）根据线性规划问题的约束条件和非负条件画出可行域；3）作出目标函数等值线Z=c（c为一常数），并使其平移求得最优解。,线性规划的求解,线性规划的解的特殊情况唯一解,无界解（少了约束条件）例Maxz=x1+2x2stx1=1x2=2,无穷解（头与身平行）例Maxz=x1+x2st2x1+2x2=0,x2=0,线性规划的求解,二、线性规划问题的标准型1。线性规划问题的标准型统一规定：1）目标函数取极大化类型（也可以是极小化类型）；2）所有约束条件用等式来表示；3）所有决策变量取非负值；4）每一约束条件的右端常数为非负值。,线性规划的求解,2。线性规划问题的标准型为：,Max,线性规划的求解,标准型缩写式为:,Max,(i=1,2,m),线性规划的求解,向量形式为:MaxZ=CX,(j=1,2,n),线性规划的标准形式矩阵形式为：目标函数：max约束条件：=变量符号：0,线性规划的求解,线性规划的求解,线性规划问题的标准化1)目标函数的标准化：对于最小化问题MINZ，化为最大化问题为：MAXZ=-Z=-CX,如不等号为“”，则左边减去一非负变量变为等式。,如不等号为“”，则左边加上一非负变量变为等式。,若右端为负，则左右两同乘（-1）即可。,若某个变量无约束，则引入两个非负变量，可令,2)约束条件的标准化,线性规划的求解,例1-4,Max,Max,线性规划的求解,例1-5将下面的线性规划问题化成标准型,Min,Min,线性规划的求解,Min,Max,线性规划的求解三、线性规划的解,Max,(i=1,2,m),(1),(2),(3),1。,可行解：满足上面模型中的（2）和（3）式的解X；,最优解：满足上面模型中的（1）的可行解X；,基（矩阵）：若B是A中的mm阶非奇异子式（即|B|0），则B是线性规划问题的一个基（矩阵）；可设B=P1，P2，.，Pm则Pj为基向量，与Pj对应的变量xj为基（本）变量。,线性规划的求解三、线性规划的解,Max,(i=1,2,m),(1),(2),(3),1。,非基（本）变量：X中除基（本）变量外的变量；在方程AX=b中，令非基变量的值为0，求得基本变量的值，这样得到的一组解X0称为方程AX=b关于基B的基本解。一般mn,故基本解的个数；,基本可行解：满足模型中（3）式的基本解。,线性规划的求解三、线性规划的解,解间的关系如下图所示：,基本可行解,基本解,可行解,非可行解,最优解,基本可行解,1。基本概念凸集：设K是n维欧氏空间的一个点集，若任意两点X(1)K，X(2)K的连线上的一切点满足下式：,线性规划的求解四、线性规划问题解的几何意义,则称K为凸集。顶点：设K为凸集，XK，若不能用两点X(1)K，X(2)K组合表示为：,则X为K的一个顶点（或极点）。,线性规划的求解四、线性规划问题解的几何意义,2。基本定理：定理1：线性规划问题的可行解集是一个凸集。即：定理2：设线性规划问题的可行解集为D，则X是D的一个顶点的充要条件是X是线性规划问题的基本可行解。定理3：若可行域非空有界，则线性规划问题的目