运筹学Chap3线性规划对偶理论及其应用.ppt

?掌握线性规划对偶理论及其基本经济学意义； 目 录 线性规划的对偶问题 对偶规划的基本性质 对偶单纯形法 影子价格和灵敏度分析 目 录 线性规划的对偶问题 对偶规划的基本性质 对偶单纯形法 影子价格和灵敏度分析 对偶问题的提出 某工厂甲生产A、B、C三种产品。这三种产品的单位利润分别是60、30、20。生产这三种单位产品所占用M、N、P三种机器的时间已知，机器M、N、P每两天可供使用的时间分别是48、20、8小时。这三种产品每两天生产多少才能使工厂获得最大效益。 现有另一工厂乙，因生产需要。拟向甲厂租用所有的机器，则乙厂希望租金越少越好，当然必须保证甲厂的利润。显然，如果甲厂的利润得不到保证，甲厂是不可能出租的。 对偶问题的一般形式 模型对比(对称形式) 最小化问题的对偶问题的一般步骤 将原问题约束条件“≤” 的不等式两边乘以-1变为“≥”的不等式 ； 对偶问题是最大化问题； 当原问题有n个决策变量，则对偶问题有n个约束条件。对偶问题的第一约束条件对应的是原问题中的x1变量，对偶问题的第二个约束条件对应的是原问题中的x2变量，依此类推。 当原问题有m个约束条件，则对偶问题有m个决策变量。对偶问题的u1变量对应的是原问题中的第一约束条件，对偶问题的u2变量对应的是原问题中的第二约束条件，依此类推。 最小化问题的对偶问题的一般步骤 ⑤将原问题约束条件的右端值成为对偶问题的目标系数； ⑥原问题的目标函数系数成为对偶问题中的约束条件的右侧值； ⑦目标函数中原问题第i个变量的系数成为对偶问题中第i个约束条件的常数项； ⑧如原问题的第i个约束条件为等式，则对偶问题中第i个决策变量取任意值； ⑨如原问题的第i个决策变量无符号限制，则对偶问题中第i个约束条件为等式约束。 线性规划问题的对偶问题（非对称）举例 原问题与对偶问题 原问题与对偶问题的关系 目 录 线性规划的对偶问题 对偶规划的基本性质 对偶单纯形法 影子价格和灵敏度分析 3、互补松弛性 练习:已知线性规划问题 目 录 线性规划的对偶问题 对偶规划的基本性质 对偶单纯形法 影子价格和灵敏度分析 定义： 对偶单纯形法的基本思想： 首先从原问题的一个对偶可行的基本解（不是原问题的可行解）出发，求改进的对偶可行的基本解，向原问题的可行域逼近，当求到对偶可行的基本解是原问题的可行解时，则得到了最优解。 对偶单纯形法的计算步骤 1．给定一个初始对偶可行的基本解，设相应的基为B。 2．若 ，则停止计算，现行对偶可行的基本解为最优解。否则令 ，则该行所对应的变量 为换出基的变量； 3．若对所有j， ，则停止计算，原问题无可行解。否则，令 则 为换入基的变量； 4．以 为主元进行主元消去，返回2。 对偶单纯形法举例 对偶单纯形法具有如下优点： 1 初始解可以是原问题的非可行解； 2 对变量个数多于约束条件的线性规划宜用对偶单纯形法计算，因此当变量数少于约束条件个数时，可先求其对偶规划，然后用对偶单纯形求解。 用单纯形法求解对偶问题（LD）（即 最大化问题）时，其最后一行的检验数行对应原问题（LP）的一个基本解。并且在最终的单纯形表中，对偶松弛变量对应的检验数的负数就是原问题（LP）的最优解。 例3.4：用对偶单纯形法求解线性规划 单纯形算法和对偶单纯形算法之差别 目 录 线性规划的对偶问题 对偶规划的基本性质 对偶单纯形法 影子价格和灵敏度分析 影子价格和对偶价格 决策变量、影子价格之间的对应关系 影子价格的经济含义 影子价格是对现有资源实现最大效益时的一种估价 企业可以根据现有资源的影子价格，对资源的使用有两种考虑： 第一，是否将设备用于外加工或出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租。 第二，是否将投资用于购买设备，以扩大生产能力，若市价低于某设备的影子价格，可考虑买进该设备，否则不宜买进。 ●在线性规划中，我们假定模型的系数都是已知常数。 ●而在实际中，各种条件都是动态变化的，因此这种假定很难成立。 ●灵敏度分析将回答：最优解对线性规划模型中各种系数变化的敏感性 灵敏度分析目标函数系数的变化 图像表示 图像表示 约束条件右边值的变化 图像描述 用图解法对例2.1进行灵敏度分析 标准化 乘以(-1) 0 0 1 3 1 0 -3 -2 -2 x4 0 0 1 -1 -1 -1 x3 0 x4 x3 x2 x1 B 0 0 1 3 初始对偶单纯形表： 出基 进基 主元 直到B≥0，停止。 解：在第2个约束方程的两边同乘以-1，然后引入