[工程科技]第1章 线性规划及单纯形法.ppt

「线性规划」带来巨额财富 第1章 线性规划及单纯形法 §1 一般线性规划问题的数学模型 §2 图解法 §3 单纯形法原理 §4 单纯形法的计算步骤 §5单纯形法的进一步讨论 §6 数据包络分析 §1 一般线性规划问题的数学模型 问题的提出 线性规划问题的数学模型 线性规划问题的标准形式 线性规划问题的解 常山机器厂生产I、II两种产品，这两种产品都要分别在A、B、C三种不同设备上加工。生产三种产品，已知的条件如下表所示，问该企业应安排生产两种产品各多少件，使总的利润收入为最大。 问 题 分 析 §2 图解法 优点： 直观性强、计算方便 缺点：只适用问题中有两个变量的情况 步骤：建立坐标系，将约束条件在图上表示； 确立满足约束条件的范围； 绘制出目标函数的图形； 确定最优解 问题 辅 助 问 题 求 辅 助 问 题 的 三 种 情 况 系数矩阵 化为标准形式 取单位矩阵 作为基，则 就是一个基可行解 3-4 从初始基可行解转化为另一基可行解 设初始基可行解为 , 其中非零坐标有m个. 不失一般性, 假定前m个坐标为非零，因 固有 方程组(*)的增广矩阵可写为 得 由上式知， 因 是一个基，则 满足 或 要使X 1是一个基可行解，而θ0, 故应对 同时成立且至少有一个等号成立。 当aij≤0时，上式显然成立。 故可令 则由上式，知 则X 1中的正分量个数最多有m个，易证， 故只需按 来确定的θ值， X 1就是一个新的基可行解。 线性无关， 3-5 最优性检验和解的判别 将基可行解X 0和X 1分别代入目标函数得 通常简写为 检验数 说明： 1)当所有的 ?j≤0时, 现有基可行解即为最优解。 2)当所有的 ?j≤0, 又对某个非基变量xj有cj－zj=0， 且按 可以找到θ0， 这表明可以找到另一个基可行解使目标函数也达到最大，此时该规划有无穷多最优解。 3)如果某个 ?j0, 又Pj的所有分量aij≤0, 则对任意 θ0, 恒有 而θ取值可无限大， 故目标函数也可无限增大, 此时规划问题有无界解。 内容小结 基本概念 凸集、顶点 基本结论 1)若线性规划问题存在可行解，则可行域是凸集。 2) 可行解X为基可行解 X的正分量所对应的系数列向量是线性独立的。 3) 基可行解对应可行域的顶点。 4) 一定存在一个基可行解是最优解。 §4 单纯形法的计算步骤 单纯形法的计算步骤： step1、求出线性规划的初始基可行解，列出初始单纯形表。 先化成标准形式, 设法使系数矩阵中包含一个单位矩阵, 不妨设此单位矩阵是( P1,P2,…,Pm ), 以此作为基可得一个初始基可行解X=( b1,b2,…,bm ). 构造初始单纯形表 cj → cn … cj … cm … c1 xn … xj … xm … x1 b 基 CB cm c2 c1 xm x2 x1 bm b2 b1 cj -zj … 0 … 0 … 1 … 0 0 … 0 0 … 1 amn … amj … a2n … a2j … a1n … a1j … Step2 进行最优性检验 若表中所有的 ?j≤0, 则表中的基可行解就是问题的最优解，计算结束。否则转下一步。 Step3 基可行解转换，得到新单纯形表。 (1) 确定入基变量. 对应的变量xk作为换入基的变量. (2) 确定出基变量. xl作为换出基的变量. alk称为主元素 (3) 生成新的单纯形表 Step4 重复第二、三步一直到计算终止。 … … … … … … 0 0 1 0 xk ck … … … … … … xl cl 0 1 0 0 xm cm … … … … … … … … 0 cj -zj … … 0 xm cm … … 0 xk ck … … 1 x1 c1 xn xj … … x1 b 基 CB cn cj … … c1 cj → s.t. 例1 用单纯形法求解线性规划问题 解： 将上述问题化为标准形式 组成初始基， 得到初始基可行解 初始单纯形表 0 0 0 3 2 cj -zj 1 0 0 5 0 15 x5 0 0 1 0 0 4 16 x4 0 0 0 1 2 2 12 x3 0 x5 x4 x3 x2 x1 b 基 CB 0 0 0 3 2 cj → 为入基变量 为出基变量 [ ] 0 0 0 3 2 cj -zj 1 0 0 5 0 15 x5