运筹学02_对偶理论与敏感性分析-2012.pptVIP

6. 对偶单纯形法的最小比值规划则是为了保证 ?? A.使原问题保持可行??? B.使对偶问题保持可行 ?? C.逐步消除原问题不可行性?? D.逐步消除对偶问题不可行性 * 7. 互为对偶的两个线性规划问题的解存在关系 ? A.原问题有可行解，对偶问题也有可行解? ? ? B.一个有最优解，另一个也有最优解? ? C.一个无最优解，另一个可能有最优解 ? ? ?D.一个问题无可行解，则另一个问题具有无界解 * 8.某个常数bi波动时，最优表中引起变化的有??? A.检验数? B.CBB－1??? C. B－1b?? D.系数矩阵 * 9.当基变量xi的系数ci波动时，最优表中引起变化的有 A. ?最优基B? B.所有非基变量的检验数??? C.第i列的系数? D.基变量XB 10.当非基变量xj的系数cj波动时，最优表中引起变化的有 ??? A.单纯形乘子 B.目标值C.非基变量的检验数? D. 常数项 * * * 最优单纯形表 Δc3 ≤ 9/5 时，原最优解不变。 c3 在什么范围内变化，原最优解不变？ 2. 若 cs 是基变量的系数： 设 cs 变化为 cs + ?cs，那么 ?j’ = cj -∑i ? s cia’ij - (cs + ?cs) a’sj = ?j - ?csa’sj ， 只要对所有非基变量，有?j’ ≤ 0，即 ?j ≤ ?csa’sj， 则最优解不变；否则，将最优单纯形表中的检验数?j用?j’ 取代，继续单纯形法的表格计算。 * 例2.6：某工厂在计划期内要安排生产I，II两种产品，已知生产单位产品所需要的设备台时及A，B两种原材料的消耗如下表所示： I II 可用资源 设备 1 2 8台时 原材料A 4 0 16kg 原材料B 0 4 12kg 已知生产1件I可以获利2元，生产1件II可获利3元， 问应当如何安排计划使该工厂获利最多？ 例2.6：线性规划 max z = 2x1 + 3x2 + 0x3 + 0x4+ 0x5 s.t. x1 + 2x2 + x3 = 8 4x1 + x4 = 16 4x2 + x5 = 12 x1, x2, x3, x4, x5 ≥ 0 有最优解的单纯形表： 考虑基变量系数c2发生变化的范围，保持最优解不变？ 易得：当 -3≤Δc2≤1时，原最优解不变。 右端项资源向量b 发生变化 设分量 br 变化为 br + ?br ，最优解的基变量 xB = B-1b，那么只要保持 B-1(b + ?b) = B-1b + B-1?b ≥ 0 则最优基不变，即基变量保持，只有值的变化；否则，需要利用对偶单纯形法继续计算。 例2.7: 例2.6中最优单纯形表如下 若现在该厂从其他地方抽调4台时设备用于生产I和II，求此时的最优方案 b1 增加 4 0 0.25 0 这里 B-1 = -2 0.5 1 0.5 -0.125 0 各列分别对应 b1, b2, b3 的单一变化。 因此，设 b1 增加 4，则 x1, x5, x2 分别变为： 4+0×4=4, 4+(-2)×4=-40, 2+0.5×4=4 用对偶单纯形法进一步求解。 得： x* = ( 4, 3, 2, 0, 0 )T , z* = 17 增加一个变量 增加变量 xn+1，由相应的Pn+1和cn+1计算： B-1Pn+1和?n+1= cn+1 - ∑ci a’i n+1 填入最优单纯形表， 若 ?n+1 ≤ 0 则 最优解不变； 否则，进一步用单纯形法求解。 * 例2.8: ：假设在例1中，该厂除了生产产品I和II外，还有一种新产品III。已知生产产品III每件需要消耗原材料A和B各为6kg和3kg，使用设备2台时，每件可以获利5元，问该厂是否应当生产该产品和生产多少？ * 例2.8: 例2.6中增加 x6 ， P6=( 2, 6, 3 )T， c6=5 计算得到 用单纯形法进一步求解。 * 得：x* = (1, 1.5, 0, 0, 0, 2)T; z* = 16.5 增加一个约束 增