04《运筹学》(第四版)单纯形法进一步讨论.pdfVIP

第一章线性规划（Linear Programming） 主讲人：莫莉 moli@hust.edu.cn 2015 年 4 月 水电与数字化工程学院 莫 莉 第一章 线性规划 1 线性规划模型 2 线性规划解 3 单纯形法★ 4 对偶问题 5 对偶理论 6 算法复杂性 水电与数字化工程学院 莫 莉 前节回顾 确定初始基可行解的方法  直接观察  “≤”不等式形式 • 已经存在单位矩阵 •加松弛变量，构造单位 矩阵  “≥”不等式形式 等式约束形式 • 减去剩余变量，加 •加上一个非负的人工变量 上非负的人工变量 水电与数字化工程学院 莫 莉 前节回顾 单纯形法的计算步骤： 单纯形法是一种 确定初始基可行解 迭代的算法，他的 思想是在可行域的 顶点——基本可行 解中寻优。由于顶 检验其是否最优 是 点有限个，算法经 有限步可终止。 否 寻找更好的基可行解 方法前提：模型化为标准型 更规范、方便的计算形式 水电与数字化工程学院 莫 莉 c  c  c  c  c j 1 m j n 3.4 单纯形表 CB 基 b x 1  xm  x j  xn c x