《运筹学第2章 对偶规划(硕士).ppt》由会员分享，可在线阅读，更多相关《运筹学第2章 对偶规划(硕士).ppt（25页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、管理运筹学管理运筹学汪贤裕汪贤裕 2009.08 第第2章章 线性规划的对偶理论及应用线性规划的对偶理论及应用 2.1 线性规划的对偶问题线性规划的对偶问题 2.1.1 对偶规划问题的提出对偶规划问题的提出2单位产品用料桌子椅子可用资源木工4小时3小时120油漆工2小时1小时50单位产品利润 50元/个30元/个例例1.1生产计划问题求下列数据下家俱厂生产计划，使利润最大。求下列数据下家俱厂生产计划，使利润最大。解：设生产桌子解：设生产桌子x x1个，生产椅子个，生产椅子x x2个个线性规划模型为：线性规划模型为：max z=50 max z=50 x x1 30 30 x x2 s.t.4
2、s.t.4 x x1 3 3 x x2 120 120 2 2 x x1 x x2 50 50 x x1 0,0,x x2 0.0.3例例2.1（续）（续）设有另一个企业，缺少木工和油漆工，它向家俱厂提出租用木工和油漆工。问该企业提出什么样的租用价格。解：设它提出的木工和油漆工的租用工时价分别为y1和y2.Min w=120y150y2 s.t.4y12y250 3y1y230 y10,y20.4序号 食 品 名 称 热量（kcal）蛋白质 （g）钙（mg）价格（元)1猪 肉100050400142鸡 蛋8006020063大 米9002030034白 菜200105002营养需求300055
3、800例1.2营养配餐问题要求配餐中至少应有热量要求配餐中至少应有热量3000kcal,蛋白质蛋白质55g，钙，钙300mg。问应怎样配餐成本最低？问应怎样配餐成本最低？5解：设每天购入猪肉 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.后全是约束条件）6例例2
4、.2（续）现有一个企业生产人造营养品：热量、蛋白（续）现有一个企业生产人造营养品：热量、蛋白质、钙，并卖给营养配方管理者。它应对生产的人造营养质、钙，并卖给营养配方管理者。它应对生产的人造营养品定价，以获取更多的收入。品定价，以获取更多的收入。解：设它对三种人造营养品定价分别为解：设它对三种人造营养品定价分别为y y1 1、y y2 2、y y3 3。有线有线性规划模型：性规划模型：Max Max w=3000 yw=3000 y1 155 y55 y2 2800 y800 y3 3 s.t.1000 y s.t.1000 y1 150 y50 y2 2400 y400 y3 3 1414 8
5、00 y 800 y1 160 y60 y2 2200 y200 y3 3 66 900 y 900 y1 120 y20 y2 2300 y300 y3 3 3 3 200 y 200 y1 110 y10 y2 2500 y500 y3 3 2 2 y y1 1 0,y 0,y2 2 0,y 0,y3 3 0.0.72.1.2.线性规划对偶问题的定义线性规划对偶问题的定义 对称形式对称形式：互为对偶互为对偶(LP)Max z=cT x (DP)Min f=bT y s.t.Ax b s.t.AT y c x 0 y 0 “Max-”“Min-”8 对称形式对称形式的对偶规划的对偶规划(1)
6、若一个模型为目标目标求“极大”，约束约束为“小于等于”的不等式，则它的对偶模型为目标求“极小”，约束是“大于等于”的不等式。即“maxmax，”和“minmin，”相对应。(2)从约束系数矩阵约束系数矩阵看：一个模型中为，则另一个模型中为AT。一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量。(3)从数据数据b b、c c的位置的位置看：在两个规划模型中，b和c的位置对换对换。(4)两个规划模型中的变量变量皆非负。9 非对称形式非对称形式的对偶规划的对偶规划 一般称不具有对称形式的一对线性规划为非对称形式的对偶规划。对于非对称形式的规划，可以按照下面的对应关系直接给出其对偶规划
7、。（1 1）将模型统一为将模型统一为“maxmax，”或或“minmin，”的形的形式，对于其中的等式约束按下面（式，对于其中的等式约束按下面（2 2）、（）、（3 3）中的方法处）中的方法处理；理；（2 2）若原规划的某个若原规划的某个约束条件为等式约束约束条件为等式约束，则在对偶，则在对偶规划中与此约束对应的那个规划中与此约束对应的那个变量变量取值取值没有非负限制没有非负限制；（3 3）若原规划的某个变量的值若原规划的某个变量的值没有非负限制没有非负限制，则在对，则在对偶问题中与此变量对应的那个偶问题中与此变量对应的那个约束为等式约束为等式。10 下面对关系（2）作一说明。对于关系（3）可
8、以给出类似的解释。设原规划中第一个约束为等式：a11x1+a1nxn=b1等价这样，原规划模型可以写成11 此时已转化为对称形式，直接写出对偶规划此时已转化为对称形式，直接写出对偶规划 这里，把 y1 看作是 y1=y1-y1，于是 y1 没有非负限制，关系（2）的说明完毕。关系（3）则是这一过程的逆过程。12 例例2.32.3 写出下面线性规划的对偶规划模型解解:先将约束条件变形为“”形式13 再根据非对称形式的对应关系，直接写出对偶规划14 2.2 线性规划的对偶理论线性规划的对偶理论 定理2.1（对称性定理）对偶问题的对偶是原问题。定理2.2（弱对偶定理）设 x，y 分别是（LP）和（D
9、P）的可行解，则 c x y b 定理2.3（对偶定理）若 x x*和和 y y*分别是(LP)和(DP)的可行解可行解，则 x x*和和 y y*分别为(LP)和(DP)的最优解最优解的充分必要条件充分必要条件是：c xc x*=y=y*b b。152.3 对偶解的经济解释对偶解的经济解释 对偶解和影子价格对偶解和影子价格 若若x x*,y,y*分别为（分别为（LPLP）和（和（DPDP）的最优解，的最优解，那么，那么，c cT T x x*=b bT T y y*。根据根据 z z*=c cT T x x*=b bT T y y*=b=b1 1y y1 1*+b+b2 2y y2 2*+b
10、 bm my ym m*可知可知 z z*/b bi i=y yi i*y yi i*表示表示 b bi i 变化变化1 1个单位对目标个单位对目标 z z产生的影响，称产生的影响，称 y yi i*为为 b bi i的影子价格。的影子价格。影子价格是对系统内部资源的一种客观评价。影子价格是对系统内部资源的一种客观评价。它是一种虚拟的价格，而不是真实的价格。它是一种虚拟的价格，而不是真实的价格。16 影子价格的几个特点影子价格的几个特点:（1 1）影子价格是对现有资源实现最大效益）影子价格是对现有资源实现最大效益时的一种最优估价。时的一种最优估价。（2 2）影子价格的取值与系统的价值取向有）影
11、子价格的取值与系统的价值取向有关，并受系统状态变化的影响。关，并受系统状态变化的影响。系统内部资源数量和价格的任何变化都会引起系统内部资源数量和价格的任何变化都会引起影子价格的变化。影子价格的变化。17 （3 3）影子价格的大小客观地反映资源在系统内的）影子价格的大小客观地反映资源在系统内的稀缺程度。稀缺程度。如果某资源在系统内部供大于求，它的影子价如果某资源在系统内部供大于求，它的影子价格为零；如果资源是稀缺资源，其影子价格必然大格为零；如果资源是稀缺资源，其影子价格必然大于零。于零。（4 4）影子价格是一种边际价值，它与经济学中）影子价格是一种边际价值，它与经济学中边际成本的概念相同。边际
12、成本的概念相同。企业管理者可以根据资源在本企业内的影子价企业管理者可以根据资源在本企业内的影子价格的大小决定企业的经营策略。格的大小决定企业的经营策略。例如：出租设备，购买设备，购买或出卖资源例如：出租设备，购买设备，购买或出卖资源。18单位产品用料桌子椅子可用资源木工4小时3小时120油漆工2小时1小时50工艺工2小时3小时70单位产品利润 50元/个30元/个例例1.1生产计划问题（续）生产计划问题（续）增加一个约束条件：增加一个约束条件：现木工厂生产的是有一定工艺的产品，每个桌现木工厂生产的是有一定工艺的产品，每个桌子用工艺工子用工艺工2 2小时，每个椅子用工艺工小时，每个椅子用工艺工3
13、 3小时。小时。问工厂应如何安排生产。问工厂应如何安排生产。19线性规划模型为：线性规划模型为：max z=50 max z=50 x x1 30 30 x x2 s.t.4 s.t.4 x x1 3 3 x x2 120 120 2 2 x x1 x x2 50 50 2 2 x x1 3 3 x x2 70 70 x x1 0,0,x x2 0.0.解：设生产桌子解：设生产桌子x x1个，生产椅子个，生产椅子x x2个个求解得：20例例2.1（续）（续）设有另一个企业，缺少木工、油漆工和工艺工工艺工，它向家俱厂提出租用木工、油漆工和工艺工工艺工。问该企业提出什么样的租用价格。解：设它提出的
14、木工和油漆工工艺工工艺工的租用工时价分别为y1，y2和y3.Min w=120y1 50y2 70y3 s.t.4y1 2y2 2y350 3y1 y23 y330 y10,y20,y30.求解得：21例：某外贸公司准备购进A1,A2 两种产品。购进产品A1每件需要10元，占用5m3的空间，待每件A1卖出后，可获纯利润3元；购进产品A2每件需要15元，占用空间3m3的空间，待每件A2卖出后，可获纯收润4元。公司现有资金1400元，有430m3的仓库空间存放产品，根据这些条件，可以建立求最大利润的线性规划模型：求解得：对偶解为：22 现公司另有一笔资金585元，准备用于投资。这笔资金可以用于购买
15、A1,A2 两种产品，也可以用来增加仓库的容量。假设增加仓库的容量，每m3需0.8元。问该公司应如何使用这笔资金。考查该问题的影子价格：每增加0.8元，可增仓库容量1m3，可增利润1/9元；增加1元，可增仓库容量(1/0.8)m3，可增利润1/(90.8)元=0.14元；每增加1元，用于购买A1,A2 两种产品，可增利润11/45元=0.24元。23现用模型进行验证：求求解得：解得：增加收益为增加收益为：533533390=143390=143 从影子价格分析从影子价格分析，增加收益为增加收益为：58511/45=14358511/45=143242.4.敏感分析敏感分析2.4.1.目标函数系数变化目标函数系数变化2.4.2.右边系数变化右边系数变化2.4.3.增加约束条件增加约束条件25