《第1讲线性规划与单纯形法》由会员分享，可在线阅读，更多相关《第1讲线性规划与单纯形法（32页珍藏版）》请在金锄头文库上搜索。
1、第第1章章 线性规划线性规划线性规划模型及单纯形法线性规划模型及单纯形法 （2学时）学时）单纯形法续（单纯形法续（2学时）学时）对偶理论对偶理论 （2学时）学时）灵敏度分析及整数规划（灵敏度分析及整数规划（2学时）学时） 1线性规划与单纯形法线性规划模型（线性规划模型（1.1)单纯形法单纯形法(1.4)重重 点：线性规划的模型，单纯形法点：线性规划的模型，单纯形法难难 点：解的概念，单纯形法点：解的概念，单纯形法基本要求：掌握线性规划的标准化，基本要求：掌握线性规划的标准化， 理解解的概念、解的性质，掌握单纯形法理解解的概念、解的性质，掌握单纯形法2 例例1-1 某工厂在计划期内要安排生产某工
2、厂在计划期内要安排生产、两种产两种产品，已知生产单位产品所需的设备台时和原料品，已知生产单位产品所需的设备台时和原料A、B的消耗量如下表。的消耗量如下表。 该工厂每生产一件产品该工厂每生产一件产品可获可获利利2元，每生产一件产品元，每生产一件产品可获利可获利3元，问应如何安元，问应如何安排生产计划能使该厂获利最多？排生产计划能使该厂获利最多？ 1 1 问题的提出问题的提出1.1线性规划模型3建立模型明确问题，确定决策变量明确问题，确定决策变量明确问题，确定决策变量明确问题，确定决策变量 设计划期内产品、的产量分别为x1，x2 Max Z=2x1+3x2x1+2x2804x1 160 4x212
3、0（非负值约束非负值约束非负值约束非负值约束）x1, x20确定约束条件确定约束条件确定约束条件确定约束条件：设备条件设备条件设备条件设备条件：确定目标函数确定目标函数确定目标函数确定目标函数：确定决策变量的约束确定决策变量的约束确定决策变量的约束确定决策变量的约束：原材料原材料原材料原材料A A：原材料原材料原材料原材料B B：4整理得：整理得：目标函数：目标函数：目标函数：目标函数：Max Z=2x1+3x2 约束条件约束条件：s.t. s.t. ： x1 + 2+ 2x2 80 80 4 4x1 160 160 4 4x2 120 120 x1 , x2 0 056一般形式一般形式目标函
4、数目标函数： Max （Min） z = c1 x1 + c2 x2 + + cn xn （1-1） 约束条件约束条件： s.t. a11 x1 + a12 x2 + + a1n xn （ =, ）b1 a21 x1 + a22 x2 + + a2n xn （ =, ）b2 am1 x1 + am2 x2 + + amn xn （ =, ）bm （1-2） x1 ，x2 ， ，xn 0 （1-3）技术系数技术系数技术系数技术系数Subject toSubject to非负约束非负约束非负约束非负约束价值系数价值系数价值系数价值系数资源限制系数资源限制系数资源限制系数资源限制系数2 2 线性规划
5、模型线性规划模型7max z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bm x1, x2, , xn0其中其中，bi0 (i=1,2,m)标准型标准型8标准型的表达形式Maxz=CX AX=b X=0要求b的各个分量非负资源向量资源向量资源向量资源向量价值系数价值系数价值系数价值系数决决决决策策策策变变变变量量量量系数矩阵系数矩阵系数矩阵系数矩阵9化标准型的步骤：化标准型的步骤：（1）目标函数为最小：目标函数为最小： min z=c1x1+c2x2+cnxn令令z =-z ,变为变为
6、max z = -c1x1- c2x2- -cnxn（2）决策变量）决策变量x xj j无非负约束无非负约束。（i） xj 0，令xj= - xj ， xj 0（ii） xj无约束，令xj= xj - xj，xj xj 0（3） bi 0 ,不等式或等式两端同时乘不等式或等式两端同时乘 110 x1 + 2x2 + x3 =80 4x1 +x4 =160 4x2 +x5 =120max z=2x1 + 3x2 + 0x3+0 x4 +0x5 x1 ,x5 0将将将将例例1-11-1的的线性规划问题化为标准型线性规划问题化为标准型线性规划问题化为标准型线性规划问题化为标准型1112则该问题的标准
7、型为：则该问题的标准型为：131.3 1.3 1.3 1.3 线性规划问题的解的概念线性规划问题的解的概念线性规划问题的解的概念线性规划问题的解的概念1-41-51-61.3线性规划问题解的概念及性质14即，对于标准的即，对于标准的即，对于标准的即，对于标准的LPLPLPLP问题来说问题来说问题来说问题来说满足这两个条件的满足这两个条件的满足这两个条件的满足这两个条件的x x是可行解是可行解是可行解是可行解或者可行点或者可行点或者可行点或者可行点三者皆满足是三者皆满足是三者皆满足是三者皆满足是最优解最优解最优解最优解15n定义定义1-1 1-1 基：基： 设设A是约束方程组是约束方程组mn维的
8、系数矩阵，其秩为维的系数矩阵，其秩为m，B是矩阵是矩阵A中中mm阶非奇异子矩阵（阶非奇异子矩阵（B的行列的行列式式B0），），则称则称B是线性规划问题的一个基。是线性规划问题的一个基。最多有最多有 个基个基1.3.1 基本概念基本概念 16max z=2x1 + 3x2 + 0x3+0 x4 +0x5 x1 + 2x2 + x3 =80 4x1 +x4 =160 4x2 +x5 =120 x1 ,x2 0基有：基有：B1， B2 ，B3B4不是基不是基 1 0 0 0 1 0 0 0 1B1=系数矩阵系数矩阵: 1 2 1 0 0 4 0 0 1 0 0 4 0 0 1A= 1 2 1 4 0
9、 0 0 4 0B2= 1 2 0 4 0 1 0 4 0B3= 2 1 0 0 0 0 4 0 1B4=17基基基向量18若令方程组中的若令方程组中的非基变量非基变量x1 1= =x2 2=0=0，可以求出一个解：可以求出一个解：X= =（0 0，0 0，8080，160160，120120）T T称称X为为基解基解。19一个基本解的非零分量个数不超过一个基本解的非零分量个数不超过m m个。个。基础可行解基础可行解的非零分量个数的非零分量个数 0 i = 1 , , m Max z = c1 x1 + c2 x2 + + cn xn s.t. a11 x1 + a12 x2 + + a1n
10、xn b1 a21 x1 + a22 x2 + + a2n xn b2 am1 x1 + am2 x2 + + amn xn bm x1 ，x2 ， ，xn 0加入松弛变量：加入松弛变量： Max z = c1 x1 + c2 x2 + + cn xn s.t. a11 x1 + a12 x2 + + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + + a2n xn + xn+2 = b2 am1 x1 + am2 x2 + + amn xn+ xn+m = bm x1 ，x2 ， ，xn ，xn+1 ， ，xn+m 028 显然，显然，xj = 0 j = 1, ,
11、 n ; xn+i = bi i = 1 , , m 是基本可行解对应的基是单位矩阵。以下是初始单纯形表：以下是初始单纯形表： m其中：其中： j = cj - cn+i aij 为检验数为检验数 cn+i = 0 i= 1,m i = 1 an+i,i = 1 , an+i,j = 0 ( ji ) i , j = 1, , m单单 纯纯 形形 表表291 确定初始基可行解：确定初始基可行解：令xj = 0 j = 1, , n ; 则xn+i = bi i = 1 , , m 是基本可行解。2 解的最优性检验：解的最优性检验：计算非基变量检验数计算非基变量检验数 m j = cj - cn
12、+i aij ， j = 1, , n i = 1基变量检验数为基变量检验数为0，即即sn+i = 0 i= 1,m若若 ，则该基可行解为最优解，否则转下面，则该基可行解为最优解，否则转下面若若 ，则该问题为无界解（无最优解）。否则转第，则该问题为无界解（无最优解）。否则转第3步。步。3 解的改进：解的改进： 确定换入变量确定换入变量 为换入变量为换入变量 确定换出变量确定换出变量 为换出变量为换出变量 换基迭代换基迭代 以以 为主元，为主元， 将将 化为单位向量，主元为化为单位向量，主元为1，得到新的基可，得到新的基可行解。转第行解。转第2步。步。 单单 纯纯 形形 法法 步步 骤骤30ma
13、x z=2x1 + 3x2 + 0x3+0 x4 +0x5 x1 + 2x2 + x3 =80 4x1 +x4 =160 4x2 +x5 =120 x1 ,x5 0例例1-11 1-11 用单纯形法求解下面的线性规划用单纯形法求解下面的线性规划max z=2x1 + 3x2 + 0x3+0x4 +0x5 x1 + 2x2 80 4x1 160 4x2 120 x1 ,x2 0解：解： 标准化标准化31最优解最优解 x1 = 40 x2 = 20 x5 = 40（松弛标量，表示（松弛标量，表示B设备设备有有5个机时的剩余）个机时的剩余） 最优值最优值 z* = 140 例例1-11 1-11 的单纯形表的单纯形表32
