线性规划与单纯形法

1、,1 线性规划与单纯形法,线性规划的发展,20世纪30年代 前苏联数学家康特洛维奇 提出解乘数法(1975年诺贝尔经济学奖) 1947 美国空军数学顾问 丹捷格 线性规划 单纯形法 冯. 诺依曼 对偶理论 库恩 塔克 盖尔 严格证明,概要,1 问题描述 2 建模 2.1变量 2.2 目标函数 2.3 约束条件 3 模型求解 3.1图解法 3.2 单纯形法 3.2.1 标准化 3.2.2 解的基本概念 3.2.3 单纯形法的一般思路+例子 3.2.4 单纯形表结构+例子 3.2.5 单纯形法的计算步骤 3.3 大M法,4 解的几种特殊形式 4.1 无可行解 4.2 无界解 4.3 多重最优解,1

2、 问题描述-线性规划经典问题,生产计划问题 某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：,2 建模,线性规划问题的表示一般形式,线性规划问题的表示-矩阵形式,max (min) zCX s.t. AX(,)b X0,线性规划问题的表示-标准形式,max zCX s.t. AXb X0 例子,3 模型求解 3.1图解法(线性规划问题的几何特征),(d)可行域无界 (e)可行域无界 (f)可行域为空集 多个最优解 目标函数无界 无可行解,(a)可行域有界 (b)可行域有界 (c)可行

3、域无界 唯一最优解 多个最优解 唯一最优解,3.2 单纯形法 3.2.1 标准化,松弛变量的引入,3.2.2 线性规划解的基本概念,基向量:基B中的一列为B的基向量. 基变量:与基B的基向量相应的变量. 基本解:对于基B,令所有非基变量为零,求得满足条件约束的解. 基本可行解:满足非负约束的基本解. 基本最优解:满足最优化目标的基本可行解. 退化的基本解:基本解中存在基变量为零.,基的定义,定义 线性规划的基(Basis) 对于线性规划的约束条件 AX=b A m n X0 设B是A矩阵中的一个非奇异的mm子矩阵，则称B为线性规划的一个基。,设B是线性规划的一个基，则A可以表示为 A= B,

4、N ,X也可相应地分成,其中 XB为m1向量，称为基变量 XN为(n-m)1向量，称为非基变量,约束方程 AX=b 的分块矩阵表示,AX=b可表示为,或,BXB+NXN=b,若XN取确定的值，则XB有唯一的值与之对应 XB=B-1b-B-1NXN 特别，取XN=0，这时有XB=B-1b,定义 线性规划的解 称为线性规划与基B对应的基本解(非基变量都取值为0)。 若其中B-1b0，则称以上的基本解为一基本可行解，相应的基B称为可行基。,基本解与基本可行解的定义,定理 线性规划问题的可行域是凸集. 线性规划问题的每个基本可行解对应着可行域的一个顶点. 若线性规划问题有最优解,必在可行域的某一个顶点

5、上达到.,3.2.3 单纯形法的一般思路,寻找初始基本可行解 给出基本可行解为最优解的判别准则 给出从目前基本可行解转移到新基本 可行解的方法,求解流程,例子,单纯形原理的矩阵描述,设标准的线性规划问题为 max z= CX s.t. AX=b X0 矩阵A可以分块记为A=B，N 相应地，向量X和C可以记为,AX=b可以写成 BXB+NXN=b 即 XB=B-1b-B-1NXN,对于一个确定的基B，目标函数z可以写成,目标函数z用非基变量表出的形式,3.2.4单纯形表的结构,单纯形方法例子,标准化,信息表(单纯形表),当前基本可行解：(0, 0, 150, 20, 300) , Z=0,当前基

6、本可行解：(75/2, 0, 75/2, 20, 0) , Z=1875,当前基本可行解：(30, 12, 0, 8, 0) , Z=1980,3.2.5 单纯形法的计算步骤（max）,（1）找出初始可行基，给出初始基本可行解，建立初始单纯形表。 （2）检验各非基变量的检验数，如果所有检验数都小于等于0，则已得到最优解；否则，转下一步。 （3）正检验数最大对应的变量作为换入变量；极小比值准则决定换出变量；迭代运算。 （4）再检验直到得到最优解。,单纯形法的计算步骤（min）,（1）找出初始可行基，给出初始基本可行解，建立初始单纯形表。 （2）检验各非基变量的检验数，如果所有检验数都大于等于0，

7、则已得到最优解；否则，转下一步。 （3）负检验数最小对应的变量作为换入变量；极小比值准则决定换出变量；迭代运算。 （4）再检验直到得到最优解。,3.3 大M法 一般问题的初始基本可行解,标准化,添加人工变量,添加人工变量,4 几种特殊情况 4.1无可行解,当前基本可行解：(0, 0, 0, 3, 4) , Z=-4M,当前基本可行解：(0, 3, 0, 0, 1) , Z=-M-3,无可行解的判别准则,最优解时，人工变量仍为基变量， 且人工变量不为,4.2 可行域无界,当前基本可行解：(0, 0, 0, 0, 4, 3) , Z=-7M,当前基本可行解：(0, 3, 0, 0, 1) , Z=-M-3,当前基本可行解：(0, 4, 0, 1, 0) , Z= -4,当前基本可行解：(8, 0, 0, 5, 0) , Z= 8,可行域无界的判别准则,存在非基变量，检验数0，技术系数均 0,4.3 无穷多最优解,当前基本可行解：(0, 0, 150,