运筹学第二章对偶问题.pptVIP

对于对称形式的（P）问题，如果有最优解，则在其最优单纯形表中，松弛变量 的检验数 的负值即为（D）问题的一个最优解. 约束条件中资源数量bi的变化分析 设某个资源数量变化为， 并假设原问题的其它系数不变，则使最终单纯 形表中原问题的解相应地变化为： 其中 ， 即 若要求最优基B不变，则必须 ≥0，因而可求出 br 的变化范围。 （i = 1,2,…, m） 当b改变为以后，若解的可行性不变，则目标函数变为 实例* 某汽车厂生产大轿车和载重汽车，所需资源、资源可用量和产品价格如下表所示: 大轿车 载重汽车 可用量 钢材（吨） 2 2 1600 工时(小时) 5 2.5 2500 座椅 400（辆） 获利(千元/辆) 4 3 问应如何组织生产才能使工厂活力最大？ 实例*中如果b1变化了 ，则 若要保持最优基不变，则上述解仍可行 因此得 试求解： （1）最优生产计划中A、B、C产品的产量； （2）最优生产计划中原材料和设备这两种资源实际耗用多少？剩余多少？ （3）最优生产计划中，原材料和设备这两种资源哪种资源每增加一个单位对利润的贡献大？为什么？ （4）若该厂欲将设备出让或出租，应如何定价才能保证出让和出租所得的收益不低于生产产品所得的收益，而又使得受让方所支付的租金最少？ （5）此问题是否有多个最优生产计划？若有多个，请再给出一个最优生产计划。 某工厂制造二种产品A和B，需要两种资源（原材料和设备）。每生产一件各种产品所需要的原材料和设备时数及每件产品的单位利润如下表所示： 产品 A B 资源总量资源耗用  原材料 3 4 9 设备时数 5 2 8 单位利润 10 51)列出该问题的数学模型并分别用图解法和单纯形法求解，并指出单纯形法迭代中每一基本可行解与图解法可行域中哪一极点相互对应?2)若设目标函数为：z=c1x1+c2x2则c1与c2满足什么条件时能使该LP问题有多重最优解? 3)最优生产计划中，原材料和设备这两种资源哪种资源每增加一个单位对利润的贡献大？为什么？4)求参数b1,c1的影响范围。5)若要求生产的产品必须是整套的，试用分枝定界法求该整数规划的最优解。 为保持最优解不变，应当有 因此得 也就是 即 在最终单纯形式表中若b1的值变化了 那么由下表 2600 0 1 0 0 0 -0.4 -0.4 -0.4 0.4 0 -1 0.5 1 -0.5 0 0 0 1 0 3 200 600 200 0 0 0 1 0 3 4 4 或者 对偶单纯形法的计算步骤： （1）根据线性规划问题，列出初始单纯形表，检查b列的数字，若都为非负，检验数都为非正，则已得到最优解，停止计算。若检查b 列的数字时，至少还有一个负分量，检验数保持非正，则转（2）。 （2）确定离基变量 按 min {(B-1b)i (B-1b)i ? 0} = (B-1b)l 对应的基变量 xl 为离基变量。 （3）确定进基变量 在单纯形表中检查xl 所在行的各系数 alj (j = 1, 2, …, n) ，若所有 alj ? 0 ，则无可行解，停止计算；若存在 alj ? 0 ( j = 1, 2, …, n ) ，计算 按 ? 规则所对应的列的非基变量xk 为进基变量 （4）以 alk 为主元，按单纯形法在表中进行迭代运算，得到新的计算表。 重复（1）——（4），直至求出最优解或确定无可行解。 2.6 对偶单纯形法 其中 cj ?zj＝ ?j 其中 cj ?zj＝ ?j ?k － alk 例2-4 用对偶单纯形法求解 Min ? = 2x1 +3x2 +4x3