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

* 某厂生产I、II、III三种产品，都分别经A、B两道工序加工。设A工序可分别在设备A1或A2上完成，有B1、B2、B3三种设备可用于完成B工序。 已知产品I可在A、B任何一种设备上加工； 产品II可在任何规格的A设备上加工，但完成B工序时， 只能在B1设备上加工； 产品III只能在A2和B2设备上加工。 设备 产品 设备有效台时 设备加工费 I II III A1 5 10 6000 0.05 A2 7 9 12 10000 0.03 B1 6 8 4000 0.06 B2 4 11 7000 0.11 B3 7 4000 0.05 原料费 0.25 0.35 0.50 售价 1.25 2.00 2.80 设备 产品 设备有效台时 设备加工费 I II III A1 5 10 6000 0.05 A2 7 9 12 10000 0.03 B1 6 8 4000 0.06 B2 4 11 7000 0.11 B3 7 4000 0.05 原料费 0.25 0.35 0.50 售价 1.25 2.00 2.80 产品I有6种加工方案（A1, B1）、(A1，B2)、(A1， B3) （A2, B1）、(A2，B2)、(A2， B3) 其各自产量分别用 设备 产品 设备有效台时 设备加工费 I II III A1 5 10 6000 0.05 A2 7 9 12 10000 0.03 B1 6 8 4000 0.06 B2 4 11 7000 0.11 B3 7 4000 0.05 原料费 0.25 0.35 0.50 售价 1.25 2.00 2.80 产品II有6种加工方案（A1, B1）、(A2，B1) 其各自产量分别用 代表 设备 产品 设备有效台时 设备加工费 I II III A1 5 10 6000 0.05 A2 7 9 12 10000 0.03 B1 6 8 4000 0.06 B2 4 11 7000 0.11 B3 7 4000 0.05 原料费 0.25 0.35 0.50 售价 1.25 2.00 2.80 产品III只有1种加工方案（A2, B2） 其各自产量用 代表 * * * * * * * * * * * * * * * * * * * * * * * * * 课后练习（一） 1 用图解法求下列线性规划问题，并指出问题具有唯一最优解、无穷多最优解、无界界还是无可行解。 无可行解 X*=(10, 6) 无界解 无穷多最优解 唯一解 2、将下述线性规划问题化成标准形式 解： 3 对下述线性规划问题找出所有基解，指出那些是基可行 解，并确定最优值。 关键：判断2个列向量线性相关性，若线性无关，则成为基 序号 向量组 是否线性无关 是否为基 1 p1 p2 √ √ 2 p1 p3 √ √ 3 p1 p4 √ √ 4 p2 p3 √ √ 5 p2 p4 √ √ 6 p3 p4 √ √ p1 p2 p3 p4 序号 基 基解 是否为基可行解 1 p1 p2 (-4, 11/2, 0 , 0) × 2 p1 p3 (2/5, 0, 11/5 , 0) √ 3 p1 p4 (-1/3, 0, 0, 11/6) × 4 p2 p3 (0, 1/2, 2, 0) √ 5 p2 p4 (0, -1/2, 0, 2) × 6 p3 p4 (0, 0, 1, 1) √ 4、已知线性规划问题 : 序号 X1 X2 X3 X4 X5 A 2 4 3 0 0 B 10 0 -5 0 4 C 3 0 2 7 4 D 1 4.5 4 0 -0.5 E 0 2 5 6 2 F 0 4 5 2 0 下表中所列的解均满足约束条件1-3，试指出表中哪些是可行解，哪些是基解，哪些是基可行解。 1 2 3 4 p1 p2 p3 p4 p5 是基 是基 是基 基解有(a), (b), (f); 基可行解有(a) (f). 可行解有(a), (c), (e), (f); 5 已知某线性规划问题的约束条件为 判断下列各点是否为该线性规划问题可行域上的顶点： 不是基，故 不是基解，更不可能是基可行解 是基，故