运筹学与最优化方法第3章课件.ppt

第 三 章 线 性 规 划 3.1 线性规划模型 例:某工厂拥有A、B、C 三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示： 3.1 线性规划模型 对设备C，两种产品生产所占用的机时数不能超过75，于是我们可以得到不等式：3x2 ≤75 ；另外，产品数不可能为负，即 x1 ,x2 ≥0。同时，我们有一个追求目标，即获取最大利润。于是可写出目标函数z为相应的生产计划可以获得的总利润：z=1500x1+2500x2 。综合上述讨论，在加工时间以及利润与产品产量成线性关系的假设下，把目标函数和约束条件放在一起，可以建立如下的线性规划模型： 3.1 线性规划模型 目标函数 Max z =1500x1+2500x2? 约束条件 s.t. 3x1+2x2≤ 65 2x1+x2≤ 40 3x2≤ 75 x1 ,x2 ≥0? 3.1 线性规划模型 这是一个典型的利润最大化的生产计划问题。其中，“Max”是英文单词“Maximize”的缩写，含义为“最大化”；“s.t.”是“subject to”的缩写，表示“满足于……”。因此，上述模型的含义是：在给定条件限制下，求使目标函数z达到最大的x1 ,x2 的取值。 3.1 线性规划模型 3.1 线性规划模型 3.1 线性规划模型 3.1 线性规划模型 3.1 线性规划模型 3.1 线性规划模型 3.1 线性规划模型 3.1 线性规划模型 3.1 线性规划模型 3.1 线性规划模型 3.1 线性规划模型 3.1 线性规划模型 3.1 线性规划模型 3.1 线性规划模型 矩阵形式： 线性规划的标准形式： Max cTx (LP) s.t. Ax = b x≥0 其中, c , x ?Rn b ?Rm A m?n 矩阵 3.1 线性规划模型 线性规划的规范形式： Max cTx (P) s.t. Ax ≤ b x≥0 其中, c , x ?Rn b ?Rm A m?n 矩阵 3.2 线性规划的单纯形法线性规划的理论： 考虑(LP)的最优性条件 约束多面体 S = { x?Rn?Ax = b , x≥0 }的极点和极方向 定理 考虑(LP)及上述多面体S，设 A满秩，x(1),x(2) , …,x(k)为所有极点， d(1),d(2) , …,d(l)为所有极方向。那么， 1) (LP)存在有限最优解 ? cTd(j) ≤0, ?j . 2) 若(LP)存在有限最优解, 则最优解可以在某个极点达到 . 3.2 线性规划的单纯形法线性规划的理论 定理 考虑(LP) , 条件同上，设 x* 为极点, 存在分解 A = [ B , N ]，其中B为m阶非奇异矩阵，使 xT = [ xBT, xNT ], 这里 xB = B-1b≥0, xN =0， 相应 cT = [ cBT, cNT ] 。那么， 1）若 cNT- cBT B-1N≤0, 则 x* -- opt. 2）若 cj- cBT B-1pj 0, 且 B-1pj≤0, 则 (LP) 无有界解 . 3.2 线性规划的单纯形法 表格单纯形法 1、原理及算法过程 Max cTx (LP) s.t. Ax = b x≥0 其中, c , x ?Rn b ?Rm A m?n 矩阵，秩（A）= m 3.2 线性规划的单纯形法单纯形法原理及算法过程 算法过程 (考虑一般步, k = 0,1,2,… ) 设 x(k) 为极点, 对应分解 A = [ B , N ]，使 xT = [ xBT, xNT ], 这里 xB = B-1b0, xN =0， 相应 cT = [ cBT, cNT ] 。那么， 1）若 cNT- cBT B-1N≤0, 则 x(k) – opt，停； 2）否则，存在 cj- cBT B-1pj 0, a）若 B-1