运筹学(简化版).docVIP

第二章 对偶线性规划与灵敏度分析 PAGE  PAGE 97  PAGE 67 对偶与灵敏度分析 XE 灵敏度分析  Chapter 2 Dual and Sensitivity Analysis 本章内容提要 线性规划问题用单纯形法求得最优解以后，还需要进行对偶分析和灵敏度分析，以了解线性规划模型的参数对最优解的影响。引进了对偶的概念以后，线性规划不仅仅是一种优化的计算方法，而且成为一种经济分析的工具。 通过本章学习，要求掌握以下内容： 掌握对偶的定义，能够熟练写出各种不同形式原始问题的对偶问题。 掌握对偶的性质，了解原始问题和对偶问题目标函数值之间的关系以及最优解之间的关系，能根据原始或对偶问题中一个问题的最优解求出另一个问题的最优解。 了解单纯形表和对偶的关系，能根据单纯形表求出对偶问题的解。掌握对偶单纯形法，从一个对偶可行，原始不可行的解出发求出最优解。 掌握灵敏度分析原理和方法，能够对目标函数系数和右边常数进行灵敏度分析，以及增加一个变量，增加一个约束后求新的最优解的方法。 对偶的经济解释：掌握影子价格、机会成本、差额成本等概念，理解互补松弛关系的经济解释。 §2.1 对偶问题 XE 对偶问题 的建立 对偶是指对同一个事物，从不同的角度考察，有两种不同的相对的描述。如：周长一定时面积最大的矩形是正方形。或面积一定时周长最短的矩形是正方形。 例2.1最小成本的生产作业计划与产品价格的最大化问题。 设一个企业生产n种产品，每种产品的单位利润为cj（单位：元/件，j=1,2,…,n），同时企业受到m种设备工时的限制，第i种设备的能力为bi（单位：小时）。生产一件j产品要消耗第i种设备工时数为aij（单位：小时/件，i=1,2,…,m；j=1,2,…,n）。设第j种产品的计划生产量为xj（单位：件，j=1,2,…,n），则使总利润最大的线性规划模型为： maxz=c1x1+c2x2+…+cjxj+…+cnxns.t.a11x1+a12x2+…+a1jxj+…+a1nxn≤b1a21x1+a22x2+…+a2jxj+…+a2nxn≤b2…………ai1x1+ai2x2+…+aijxj+…+ainxn≤bi…………am1x1+am2x2+…+amjxj+…+amnxn≤bmx1,x2,…,xj,…,xn≥0假设这时有一个商人愿意以价格w1，w2，…，wm向这个工厂租赁这m种设备，并保证他所报的每一种设备的租赁价格都不会高于同一设备的在生产n种产品时的使用价值。当然，这个推销商在确定租赁价格时总是希望总的租赁成本最小化。这样，推销商确定租赁价格的方法可以用以下线性规划表示： Miny=b1w1+b2w2+…+biwi+…+bmwms.t.a11w1+a21w2+…+ai1wi+…+am1wm≤c1a12w1+a22w2+…+ai2wi+…+am2wm≤c2…………a1jw1+a2jw2+…+aijwi+…+amjwm≤cj…………a1nw1+a2nw2+…+ainwi+…+amnwn≤cnw1,w2,…,wj,…,wn≥0用矩阵形式表示为 Min y=bTW s.t. ATW≤C W≥0 容易看出，这就是企业最小生产成本问题的对偶问题。这个对偶问题 XE 对偶问题 的经济意义是产品定价问题。从检验数可以看出线性规划得到最优解的条件是： 单纯形乘子Y=≥0和 ≥0 包括基变量在内的所有检验数可以表示为≥0即YA≥C 单纯形乘子Y右乘b，Yb=z 易得 定义2.1 设以下线性规划问题 max z=CTX s.t. AX≥b (P) X≥0 为原始问题 XE 原始问题 ，则称以下问题 min y=bTW s.t. ATW≤C (D) W≥0 为原始问题 XE 原始问题 的对偶问题 XE 对偶问题 。 对偶关系表(一定要理解) x?Rn×1Min y=bTww ?Rm×1A?Rm×n≥b ?Rm×1≤Max z=xTcc?Rn×12.1.3 其他形式的对偶问题 XE 对偶问题  2.1.3.1 等号约束问题 设原始问题 XE 原始问题