第1讲线性规划与单纯形法

第 1章 线性规划 线性规划模型及单纯形法 （ 2学时） 单纯形法续（ 2学时） 对偶理论 （ 2学时） 灵敏度分析及整数规划（ 2学时）1Chapter 1线性规划与单纯形法 线性规划模型（ 1.1) 单纯形法 (1.4)重 点：线性规划的模型，单纯形法难 点：解的概念，单纯形法基本要求：掌握线性规划的标准化，理解解的概念、解的性质，掌握单纯形法2Chapter 1例 1-1 某工厂在计划期内要安排生产 、 两种产品，已知生产单位产品所需的设备台时和原料 A、 B的消耗量如下表。 该工厂每生产一件产品 可获利 2元，每生产一件产品 可获利 3元，问应如何安排生产计划能使该厂获利最多？ 1 问题的提出1.1线 性 规 划模型3Chapter 1建立模型 明确问题，确定决策变量明确问题，确定决策变量 设计划期内产品 、 的产量分别为 x1， x2Max Z=2x1+3x2x1+2x2804x1 1604x2120（ 非负值约束非负值约束 ）x1, x20确定约束条件确定约束条件 ：设备条件设备条件 ：确定目标函数确定目标函数 ：确定决策变量的约束确定决策变量的约束 ：原材料原材料 A：原材料原材料 B：4Chapter 1 整理得：目标函数：目标函数： Max Z=2x1+3x2约束条件 ： s.t. ： x1 + 2x2 804x1 1604x2 120x1 , x2 05Chapter 16Chapter 1一般形式目标函数 ： Max （ Min） z = c1 x1 + c2 x2 + + cn xn （ 1-1）约束条件 ： s.t. a11 x1 + a12 x2 + + a1n xn （ =, ） b1a21 x1 + a22 x2 + + a2n xn （ =, ） b2 am1 x1 + am2 x2 + + amn xn （ =, ） bm （ 1-2）x1 ， x2 ， ， xn 0 （ 1-3）技术系数技术系数Subject to非负约束非负约束价值系数价值系数资源限制系数资源限制系数2 线性规划模型7Chapter 1max z=c1x1+c2x2+ +cnxna11x1+a12x2+ +a1nxn=b1a21x1+a22x2+ +a2nxn=b2am1x1+am2x2+ +amnxn=bmx1, x2, , xn0其中 ， bi0 (i=1,2, ,m)标准型8Chapter 1标准型的表达形式 Maxz=CXAX=bX=0要求 b的各个分量非负 资源向量资源向量价值系数价值系数决决策策变变量量系数矩阵系数矩阵9Chapter 1化标准型的步骤：（ 1） 目标函数为最小： min z=c1x1+c2x2+ +cnxn令 z=-z ,变为 max z= -c1x1- c2x2- -cnxn（ 2）决策变量 xj无非负约束 。（ i） xj 0， 令 xj= - xj ， xj 0（ ii） xj无约束， 令 xj= xj - xj， xj xj 0（ 3） bi 0 i = 1 , , mMax z = c1 x1 + c2 x2 + + cn xn s.t. a11 x1 + a12 x2 + + a1n xn b1a21 x1 + a22 x2 + + a2n xn b2 am1 x1 + am2 x2 + + amn xn bmx1 ， x2 ， ， xn 0 加入松弛变量：Max z = c1 x1 + c2 x2 + + cn xn s.t. a11 x1 + a12 x2 + + a1n xn + xn+1 = b1a21 x1 + a22 x2 + + a2n xn + xn+2 = b2 am1 x1 + am2 x2 + + amn xn+ xn+m = bmx1 ， x2 ， ， xn ， xn+1 ， ， xn+m 0 28Chapter 1显然， xj = 0 j = 1, , 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单 纯 形 表29Chapter 11 确定初始基可行解：令 xj = 0 j = 1, , n ; 则 xn+i = bi i = 1 , , m 是基本可行解 。2 解的最优性检验：计算非基变量检验数mj = cj - cn+i aij ， j = 1, , n i = 1基变量检验数为 0， 即 n+i = 0 i= 1,m若 ，则该基可行解为最优解，否则转下面若 ，则该问题为无界解（无最优解）