1-5+7单纯形法的矩阵描述及应用举例.ppt

返回 上页 下页 继续 第五、七节 单纯形法的进一步讨论和应用举例 ----单纯形法的矩阵描述 及应用举例 矩阵单纯形法计算的描述 P41 线性规划问题 解：化为标准型，引入松弛变量 初始解 非基变量 基变量 b B N I cj-zj σN 0, …,0 初始单纯形表： 基可行解 基变量 非基变量 b′ I N ′ B-1 cj-zj 0, …,0 σN ′ -y1, …, -ym 最终单纯形表： 单纯形法的矩阵描述 不妨设基矩阵为 基变量 非基变量 则 当前基解 当前目标函数值 目标函数 令 得当前的目标函数值为： 单纯形法的矩阵描述 当前检验数 单纯形法的矩阵描述 检验数 其中 当前 对应的系数列 当基变量为 时，新的单纯形表 矩阵单纯形法计算的描述 当前检验数 当前基解 例10 用向量矩阵描述下面LP问题的计算 系数矩阵 例10 用向量矩阵描述下面LP问题的计算 cj→ 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 0 x3 12 2 2 1 0 0 0 x4 16 4 0 0 1 0 0 x5 15 0 5* 0 0 1 cj - Zj 2 3 0 0 0 0 x3 6 2* 0 1 0 -2/5 0 x4 16 4 0 0 1 0 3 x2 3 0 1 0 0 1/5 cj - Zj 2 0 0 0 -3/5 2 x1 3 1 0 1/2 0 -1/5 0 x4 4 0 0 -2 1 4/5 3 x2 3 0 1 0 0 1/5 cj - Zj 0 0 -1 0 -1/5 初始单纯形表 2 0 3 0 0 0 0 12 2 0 2 1 0 0 0 16 4 1 0 0 1 0 0 15 0 0 5 0 0 1 2 0 3 0 0 0 B I 例10单纯形表 2 0 3 0 0 0 2 3 1 0 0 1/2 0 -1/5 0 4 0 1 0 -2 1 4/5 3 3 0 0 1 0 0 1/5 0 0 0 -1 0 -1/5 最优解为(3,3,0,4,0)，最大值为Z = 15 I B-1 应用举例 一个经济、管理问题要满足下列条件，才能 归结为线性规划模型： (一) 要求解的问题的目标能用某种效益指标度 量大小程度,并能用线性函数描述目标的要求 (二) 为达到这个目标存在多种方案 (三) 要达到的目标是在一定约束条件下实现的, 这些条件可用线性等式或不等式描述 例1 混合配料问题 某糖果厂用原料A、B、C加工成三种不同牌号的糖果甲、乙、 丙.已知各种牌号糖果中A、B、C含量，原料成本，各种原料的 每月限制用量，三种牌号糖果的单位加工费及售价如下表所示. 问该厂每月生产这三种牌号糖果各多少千克，使该厂获利最大. 试建立这个问题的线性规划的数学模型. 甲 乙 丙 原料成本(元/k