第四章线性规划的标准型及单纯形法ppt课件.ppt

1 运筹学 硕士生导师 OperationsResearch 2 第 章线性规划的标准型及单纯形法 3 4 线性规划的标准型 SLP Maxz c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 5 标准型的特征 目标函数极大化约束条件为等式决策变量非负 6 线性规划的标准型 代数式Maxz c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 xj 0j 1 2 n 7 线性规划的标准型 和式 8 线性规划的标准型 向量式 9 线性规划的标准型 矩阵式 10 非标准型转化为标准型 目标函数极小化转为极大化 minZ max Z 一个数的极小化等价于其相反数的极大化 不等式约束的转化 aijxj bi加入松弛变量 aijxj bi减去剩余变量非正变量 即xk 0则令x k xk自由变量 即xk无约束 令xk x k x k 11 非标准型转化举例之一 maxZ 70X1 120X2maxZ 70X1 120X29X1 4X2 3609X1 4X2 X3 3604X1 5X2 2004X1 5X2 x4 2003X1 10X2 3003X1 10X2 x5 300X1 0X2 0X1 0X2 0X3 0 x4 0 x5 0 12 非标准型转化举例之二 minZ x1 2x2 3x3maxZ x 1 2x2 3 x 3 x 3 x1 x2 x3 9 x 1 x2 x 3 x 3 x4 9 x1 2x2 x3 2x 1 2x2 x 3 x 3 x5 23x1 x2 3x3 5 3x 1 x2 3 x 3 x 3 5x1 0 x2 0 x3无约束x 1 0 x2 0 x 3 0 x 3 0 x4 0 x5 0 13 非标准型转化举例之三 minZ 3x1 x2 4x3 x1 2x2 x3 5x1 x2 x3 6x1 0 x2 0 x3无约束 14 非标准型转化举例之三 minZ 3x1 x2 4x3maxZ 3x 1 x2 4 x 3 x 3 x1 2x2 x3 5x 1 2x2 x 3 x 3 5x1 x2 x3 6x 1 x2 x 3 x 3 x4 6x1 0 x2 0 x3无约束x 1 0 x2 0 x 3 0 x 3 0 x4 0 15 基可行解 秩基基可行解 16 秩 设m n矩阵A中有一个r阶子式D不等于零 而所有r 1阶子式 如果存在的话 全等于零 则称D为矩阵A的最高阶非零子式 称数r为矩阵A的秩 记作R A r 零矩阵的秩为零 m n矩阵A的秩R A min m n 假设 约束方程组的系数矩阵A的秩为m R A m m n 17 基 基的概念 如前所述LP标准型和式 maxZ cjxj aijxj bixj 0j 1 2 n矩阵式 maxZ CXAX bX 0约束方程的系数矩阵A的秩为m 且m n 设A B N B是A中mxm阶非奇异子矩阵 则称B是LP的一个基 即 B是A中m个线性无关向量组 18 基解 不失一般性 设B是A的前m列 即B p1 p2 pm 其相对应的变量XB x1 x2 xm T 称为基变量 其余变量XN Xm 1 Xn T称为非基变量 令所有非基变量等于零 则X x1 x2 xm 0 0 T称为基解 19 基可行解 基可行解 基解可正可负 负则不可行 故称满足非负性条件的基解为基可行解 相应的基为可行基 退化的基可行解 若某个基变量取值为零 则称之为退化的基可行解 基解的数目 最多Cmn n m n m 20 例题6基可行解说明 maxZ 70X1 120X2P1P2P3P4P59X1 4X2 X3 360941004X1 5X2 x4 200A 450103X1 10X2 x5 300310001Xj 0j 1 2 5这里m 3 n 5 Cmn 10 21 例题6基可行解说明 基 P3 P4 P5 令非基变量x1 x2 0 则基变量x3 360 x4 200 x5 300 可行解基 p2 p4 p5 令非基变量x1 0 x3 0基变量x2 90 x4 250 x5 600 非可行解基 p2 p3 p4 令非基变量x1 x5 0 则基变量x2 30 x3 240 x4 50 可行解 P21图 22 SLP 的基可行解对应于其可行域的顶点 极点 若 SLP 有最优解 则必有最优基可行解可行基解 迭代 更优的可行基解 最优基解 单纯形法的原理 23 单纯形法 最优性检验 LP经过若干步迭代 成为如下形式 X1 a 1m 1xm 1 a 1nxn b 1x1 b 1 a 1jxjx2 a 2m 1xm 1 a 2nxn b 2x2 b 2 a 2jxj xm a mm 1xm 1 a mnxn b mxm b m a mjxj 24 单纯形法 25 单纯形法 基变换若 j 0 则取max j K 相应之非基变量XK若非零 将使Z增加 故令XK进基 令XK 0其余非基变量保持为零 XK原是非基变量 取零值 XK 0将迫使某个原基变量为零 当XK取值超过任意b i a ik时 将破坏非负性条件 于是令 min b i a ik a ik 0 b L a Lk 这时原基变量XL 0 由基变量变成非基变量a Lk处在变量转换的交叉点上 称之为枢轴元素 26 单纯形法解题举例 单纯形表的格式 27 某厂生产两种产品 需要三种资源 已知各产品的利润 各资源的限量和各产品的资源消耗系数如下表 28 问题 如何安排生产计划 使得获利最多 步骤 1 确定决策变量 设生产A产品x1kg B产品x2kg2 确定目标函数 maxZ 70X1 120X23 确定约束条件 人力约束9X1 4X2 360设备约束4X1 5X2 200原材料约束3X1 10X2 300非负性约束X1 0X2 0 29 30 31 单纯形法的计算步骤 1 找到初始可行基 建立单纯形表2 计算检验数 若 j 0则得最优解 否则转下步3 若某 K 0而P K 0 则最优解无界 否则转下步4 根据max j K原则确定XK进基变量 根据 规则 min b i a ika ik 0 b l a lk确定XL出基变量5 以a lk为枢轴元素进行迭代6 重复第二步到第五步 32 单纯形法的进一步探讨 极小化问题直接求解 检验数的判别由 j 0变为 j 0