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

第 10章 线性规划与单纯形法本章要点 ：1。线性规划问题的数学模型；2。线性规划问题的基本理论；3。线性规划问题的求解。例 1.1：美佳公司计划制造 I， II两种家电产品。已知各制造一件时分别占用的设备 A， B的台时、调试时间、调试工序及每天可用于这两种家电的能力、各售出一件时的获得情况，如表所示。问该公司应制造两种家电各多少件，使获取的利润为最大。项 目 I II 每天可用能力设备 A（ h） 0 5 15设备 B（ h） 6 2 24调试 工序（ h） 1 1 5利 润 （元） 2 1一、问题的提出线性规划问题与及其数学模型Max解：设 x1和 x2分别表示美佳公司制造家电 I和 II的数量。则该问题可用线性规划模型表示如下：线性规划问题与及其数学模型线性规划问题与及其数学模型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构件、 300根B构件和 700根 C构件；又知机械甲每天租赁费 为250元，机械乙每天租赁费为 350元，试决定租赁机械甲和乙各多少天，才能使总租赁费最少？65A26机械乙108机械甲 CB每天安装能力（根）机械构件线性规划问题与及其数学模型设租赁甲 X1天，机械乙 X2天，为满足 A、 B、 C的安装要求 ;则用数学语言可描述为：Min线性规划问题与及其数学模型二、线性规划的数学模型共同特征：1）决策变量（向量） X 2） 约束条件（向量） AX=b 3） 线性目标函数 Z=CX其中： C为价值系数（向量）A为约束条件系数矩阵线性规划问题与及其数学模型用数学语言可描述为：Max(Min)线性规划问题与及其数学模型线性规划模型的结构目标函数 ： max， min约束条件： ,=,变量符号： 0, unr, 0用 矩阵描述 为：线性规划问题与及其数学模型线性规划问题的求解p 图解法：适用于个决策变量p鞍面法： 1992年中国沈阳化工学院尚毅教授发明。p内点法： 1984年美国籍印度数学家 Karmarker（卡玛卡）发明p椭球法： 1979年苏联数学家 Khachiyan（哈奇扬）发明p单纯形法： 1952年美国斯坦福大学教授Dantzig（丹茨格）发明，可以解决 1.5万至 2万个决策变量。线性规划的求解一、 图解法max z=x1+3x2 s.t. x1+ x26-x1+2x28x1 0, x20可行域目标函数等值线最优解64-860x1x2线性规划的求解p 图解法求解步骤1）建立直角坐标系；2）根据线性规划问题的约束条件和非负条件画出可行域；3）作出目标函数等值线 Z=c（ c为一常数），并使其平移求得最优解。线性规划的求解p 线性规划的解的 特殊情况n 唯一解X1X2X1X222X1X222n无界解（少了约束条件）例 Max z=x1+2x2st x1=1 x2=2n无穷解（头与身平行）例 Max z=x1+x2st 2x1+2x2=0,x2=0线性规划的求解二、线性规划问题的标准型1。线性规划问题的标准型统一规定：1）目标函数取极大化类型（也可以是极小化类型）；2）所有约束条件用等式来表示；3）所有决策变量取非负值；4）每一约束条件的右端常数为非负值。线性规划的求解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)约束条件的标准化线性规划的求解例 1-4Max Max线性规划的求解例 1-5 将下面的线性规划问题化成标准型Min Min线性规划的求解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中除基（本）变量外的变量；在方程 AX=b中，令非基变量的值为 0，求得基本变量的值，这样得到的一组解 X0称为方程 AX=b关于基 B的 基本解 。一般 mn,故基本解的个数 ；l基本可行解：满足模型中（ 3）式的基本解。线性规划的求解三、 线性规划的解l 解间的关系如下图所示：基本可行解基本解可行解非可行解 最优解基本可行解1。基本概念l 凸集：设 K是 n维欧氏空间的一个点集，若任意两点X(1) K， X(2) K的连线上的一切点满足下式：线性规划的求解四、线性规划问题解的几何意义则称 K为凸集。l顶点：设 K为凸集， X K， 若不能用两点 X(1) K， X(2) K组合表示为：则 X为 K的一个顶点（或极点）。线性规划的求解四、线性规划问题解的几何意义2。基本定理：定理 1：线性规划问题的可行解集是一个凸集。即：定理 2：设线性规划问题的可行解集为 D，则 X是 D的一个顶点的充要条件是 X是线性规划问题的基本 可行解 。定理 3：若可行域非空有界，则