解答运筹学第一章线性规划及其单纯形法习题ppt课件.ppt

课后练习 一 1用图解法求下列线性规划问题 并指出问题具有唯一最优解 无穷多最优解 无界界还是无可行解 无可行解 X 10 6 无界解 无穷多最优解 唯一解 2 将下述线性规划问题化成标准形式 解 3对下述线性规划问题找出所有基解 指出那些是基可行解 并确定最优值 关键 判断2个列向量线性相关性 若线性无关 则成为基 p1p2p3p4 4 已知线性规划问题 下表中所列的解均满足约束条件1 3 试指出表中哪些是可行解 哪些是基解 哪些是基可行解 1234 p1p2p3p4p5 是基 是基 是基 基解有 a b f 基可行解有 a f 可行解有 a c e f 5已知某线性规划问题的约束条件为 判断下列各点是否为该线性规划问题可行域上的顶点 不是基 故 不是基解 更不可能是基可行解 为非可行域上的点 故不是 不是基 故 不是基解 更不可能是基可行解 课后练习 二 1 分别用图解法和单纯形法求解下述线性规划问题 并指出单纯形法迭代的每一步相当于图解法可行域中的哪一个顶点 010500 同理 2 X 3 5 1 5 7 5 0 0 Z 8 5 2用单纯形法求解下列线性规划问题 同理 2 为无界解 3用单纯形法中的大M法求解下列线性规划问题 并指出属那一类解 化为标准式有 x1x2x3x4x5x6x7 2 3 100 M M 8142 1010 0 2 3 100 M M 63200 101 x1x2x3x4x5x6x7 2 3 100 M M 8142 1010 14M4M 26M 32M 1 M M00 63200 101 x1x2x3x4x5x6x7 2 3 100 M M 8142 1010 14M4M 26M 32M 1 M M00 63200 101 23 x1x2x3x4x5x6x7 2 3 100 M M 21 411 2 1 401 40 25 20 11 2 1 1 21 84 5 x1x2x3x4x5x6x7 2 3 100 M M 21 411 2 1 401 40 25 20 11 2 1 1 21 84 5 x1x2x3x4x5x6x7 2 3 100 M M 9 5013 5 3 101 103 10 1 10 4 510 2 51 5 2 5 1 52 5 4 求解线性规划问题当某一变量的取值无约束时 通常用来替换 其中 试说明 能否在基变量中同时出现 为什么 5 下表为用单纯形法计算时某一步的表格 已知该线性规划的目标函数为约束形式为x3 x4为松弛变量 表中解代入目标函数后得Z 10 a g的值表中给出的解是否为最优解 因为目标函数值为10 而Z 5x1 3x2 由单纯形表可知x1 a x2 0 故a 2 因为x1 x2为基变量 所以因当满足高斯消元的形式 properformfromGaussianelimination 故c 0 d 1 b 0 f 0 由检验数的定义可知 1 3 0 0 e 5 e 4 5 g 0 0 1 5 1 5 g 5 a 2 b 0 c 0 d 1 e 4 5 f 0 g 5 由于所有检验非正 故该解是最优解这个表格为最终单纯形表 综上所述 6 已知某线性规划问题的初始单纯形表和用单纯刑法迭代后得到的表如下所示 试求括弧中未知数a l的值 X1X2X3X4X5 X4X5 61 b c d 10 13 e 01 X1X5 f 4 g 2 11 20 h i 11 21 a 1200 0 7 j k l 首先由于x1 x5为基变量 故g 1 h 0 l 0 再有 那么 b 1 c 2 d 1 c 3 i d e 1 b 2c 4d 2i 5e 2 又有 f 3 还剩下检验数a j k 检验数的定义为 如何求得c呢 对初始单纯形表的检验数行即为目标函数中的系数C 对迭代后的单纯形表有 a c1 3 至此我们已获得所有的目标函数的系数 j 2 3 1 0 1 5 k 0 3 1 2 0 1 2 3 2 a 3 b 2 c 4 d 2 e 2 f 3 g 1 h 0i 5 j 5 k 3 2 l 0 综上所述 7 设是线性规划问题的最优解 若目标函数中用代替C后 问题的最优解变为 求证 证明 因为 1 2 将 2 1 有 某厂生产I II III三种产品 都分别经A B两道工序加工 设A工序可分别在设备A1或A2上完成 有B1 B2 B3三种设备可用于完成B工序 已知产品I可在A B任何一种设备上加工 产品II可在任何规格的A设备上加工 但完成B工序时 只能在B1设备上加工 产品III只能在A2和B2设备上加工 产品I有6种加工方案 A1 B1 A1 B2 A1 B3 A2 B1 A2 B2 A2 B3 其各