运筹学第2章对偶规划(硕士).ppt

1、,管理运筹学,汪贤裕 2009.08,2,第2章 线性规划的对偶理论及应用 2.1 线性规划的对偶问题 2.1.1 对偶规划问题的提出,3,例1.1生产计划问题 求下列数据下家俱厂生产计划，使利润最大。,解：设生产桌子x1个，生产椅子x2个,线性规划模型为： max z = 50 x1 30 x2 s.t. 4 x1 3 x2 120 2 x1 x2 50 x1 0, x2 0.,4,例2.1（续）设有另一个企业，缺少木工和油漆工，它向家俱厂提出租用木工和油漆工。问该企业提出什么样的租用价格。 解：设它提出的木工和油漆工的租用工时价分别为y1和y2. Min w =120y150y2 s.t.

2、 4y12y250 3y1y230 y10, y20.,5,例1.2营养配餐问题 要求配餐中至少应有热量3000kcal,蛋白质55g，钙300mg。问应怎样配餐成本最低？,6,解：设每天购入猪肉 x1千克、鸡蛋 x2千克、大米 x3千克、白菜 x4千克。（决策变量） 则配餐问题的线性规划模型如下： Min z=14x1 6x2 3x3 2x4 （目标函数) s.t. 1000 x1800 x2900 x3200 x4 3000 50 x1 60 x2 20 x3 10 x4 55 400 x1 200 x2300 x3500 x4 800 x i 0 i =1, 2, 3, 4. （s.t.

3、后全是约束条件）,7,例2.2（续）现有一个企业生产人造营养品：热量、蛋白质、钙，并卖给营养配方管理者。它应对生产的人造营养品定价，以获取更多的收入。 解：设它对三种人造营养品定价分别为y1、y2、y3。有线性规划模型： Max w =3000 y155 y2800 y3 s.t. 1000 y150 y2400 y3 14 800 y160 y2200 y3 6 900 y120 y2300 y3 3 200 y110 y2500 y3 2 y1 0, y2 0, y3 0.,8,2.1.2. 线性规划对偶问题的定义,对称形式： 互为对偶 (LP) Max z = cT x (DP) Min

4、 f = bT y s.t. Ax b s.t. AT y c x 0 y 0 “Max - ” “Min- ”,9,对称形式的对偶规划 (1)若一个模型为目标求“极大”，约束为“小于等于”的不等式，则它的对偶模型为目标求“极小”，约束是“大于等于”的不等式。即“max，”和“min，”相对应。,(2)从约束系数矩阵看：一个模型中为，则另一个模型中为AT。一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量。 (3)从数据b、c的位置看：在两个规划模型中，b和c的位置对换。 (4)两个规划模型中的变量皆非负。,10,非对称形式的对偶规划 一般称不具有对称形式的一对线性规划为非对称形

5、式的对偶规划。 对于非对称形式的规划，可以按照下面的对应关系直接给出其对偶规划。 （1）将模型统一为“max，”或“min，” 的形式，对于其中的等式约束按下面（2）、（3）中的方法处理； （2）若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制；,（3）若原规划的某个变量的值没有非负限制，则在对偶问题中与此变量对应的那个约束为等式。,11,下面对关系（2）作一说明。对于关系（3）可以给出类似的解释。 设原规划中第一个约束为等式： a11x1 + + a1nxn = b1,等价,这样，原规划模型可以写成,12,此时已转化为对称形式，直接写出对偶规划,这里，把

6、 y1 看作是 y1 = y1 - y1，于是 y1 没有非负限制，关系（2）的说明完毕。 关系（3）则是这一过程的逆过程。,13,例2.3 写出下面线性规划的对偶规划模型,解: 先将约束条件变形为“”形式,14,再根据非对称形式的对应关系，直接写出对偶规划,15,2.2 线性规划的对偶理论 定理2.1（对称性定理） 对偶问题的对偶是原问题。 定理2.2 （弱对偶定理） 设 x，y 分别是（LP）和（DP）的可行解， 则 c x y b 定理2. 3（对偶定理） 若 x* 和 y* 分别是(LP)和(DP)的可行解，则 x* 和 y* 分别为(LP)和(DP)的最优解的充分必要条件是： c x

7、*= y* b。,16,2.3 对偶解的经济解释,对偶解和影子价格 若x*,y* 分别为（LP）和（DP）的最优解， 那么， cT x* = bT y* 。 根据 z* = cT x* = bT y* = b1y1*+ b2y2*+bmym* 可知 z* / bi = yi* yi* 表示 bi 变化1个单位对目标 z产生的影响，称 yi* 为 bi的影子价格。 影子价格是对系统内部资源的一种客观评价。 它是一种虚拟的价格，而不是真实的价格。,17,影子价格的几个特点: （1）影子价格是对现有资源实现最大效益时的一种最优估价。 （2）影子价格的取值与系统的价值取向有关，并受系统状态变化的影响。

8、 系统内部资源数量和价格的任何变化都会引起影子价格的变化。,18,（3）影子价格的大小客观地反映资源在系统内的稀缺程度。 如果某资源在系统内部供大于求，它的影子价格为零；如果资源是稀缺资源，其影子价格必然大于零。 （4）影子价格是一种边际价值，它与经济学中边际成本的概念相同。 企业管理者可以根据资源在本企业内的影子价格的大小决定企业的经营策略。 例如：出租设备，购买设备，购买或出卖资源。,19,例1.1生产计划问题（续）,增加一个约束条件： 现木工厂生产的是有一定工艺的产品，每个桌 子用工艺工2小时，每个椅子用工艺工3小时。 问工厂应如何安排生产。,20,线性规划模型为： max z = 50

9、 x1 30 x2 s.t. 4 x1 3 x2 120 2 x1 x2 50 2 x1 3 x2 70 x1 0, x2 0.,解：设生产桌子x1个，生产椅子x2个,求解得：,21,例2.1（续）设有另一个企业，缺少木工、油漆工和工艺工，它向家俱厂提出租用木工、油漆工和工艺工。问该企业提出什么样的租用价格。 解：设它提出的木工和油漆工工艺工的租用工时价分别为y1，y2和y3. Min w =120y1 50y2 70y3 s.t. 4y1 2y2 2y350 3y1 y23 y330 y10, y20, y30. 求解得：,22,例：某外贸公司准备购进A1 ,A2 两种产品。购进产品A1每件

10、需要10元，占用5m3的空间，待每件A1卖出后，可获纯利润3元；购进产品A2每件需要15元，占用空间3m3的空间，待每件A2卖出后，可获纯收润4元。公司现有资金1400元，有430m3的仓库空间存放产品，根据这些条件，可以建立求最大利润的线性规划模型： 求解得： 对偶解为：,23,现公司另有一笔资金585元，准备用于投资。 这笔资金可以用于购买A1 ,A2 两种产品，也可以用来增加仓库的容量。假设增加仓库的容量，每m3需0.8元。 问该公司应如何使用这笔资金。 考查该问题的影子价格： 每增加0.8元，可增仓库容量1m3，可增利润1/9元； 增加1元，可增仓库容量(1/0.8)m3，可增利润1/(90.8)元=0.14元； 每增加1元