线性规划的对偶理论

《线性规划的对偶理论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章线性规划的对偶理论和灵敏度分析从经济意义上研究线性规划的对偶问题，通过对对偶问题的研究，从不同的角度对线性规划问题进行分析，从而利用有限的数据，得出更广泛的结果，间接地获得更多的有用信息，为企业经营决策提供更多的科学依据主要内容原规划与对偶规划的转换对偶定理影子价格的概念和经济学意义对偶单纯形法灵敏度分析的目的和主要内容问题的提出线性规划对偶问题线性规划有一个有趣的特性，就是对于任何一个求极大值的线性规划问题都存在一个与其对应的极小值线性规划问题，而且二者之间联系紧密，可以互相转化。对偶性（教材P53-54例题）从例子中可以看出：（1）原规划

2、问题为生产计划问题，而其对偶问题为赋予该生产计划可行性的潜在价值问题（2）原规划的目标函数是从资源拥有者的角度得出利润最大化，而其对偶规划的目标函数是从想获得该资源方的角度得出成本最小化（3）两个问题共用一套参数，但组合方式不同原问题和对偶问题的关系原问题（P）对偶问题（D）决策变量xi第i种产品数量yi第i个约束条件目标函数约束条件对偶问题在解释资源的影子价格、扩大单纯形法计算方法以及对问题进行灵敏度分析等方面有很多应用。从表中可以看出对称形式的对偶关系具有如下的对应关系：目标函数最大最小；约束条件不大于不小于约束矩阵：一个为另一

3、个的转置常数向量b和c互换目标变量皆为非负线性规划对偶问题对称形式对偶问题原问题和对偶问题的关系非对称形式的对偶问题不具备对称形式的一对线性规划称为非对称形式的对偶问题转换方式为：4、若原规划中的某个变量没有非负限制，则在对偶问题中对应的那个约束为等式。1、将模型统一为规范形式，然后先按对称形式转换2、对等式约束按（3）或（4）处理3、若原规划中某个约束为等式，则在对偶规划中与此对应的变量取值没有非负约束教材P56例题线性规划对偶问题原问题和对偶问题的关系原问题与对偶问题的转换线性规划对偶问题原问题和对偶问题的关系原问题与对偶问题的转换线性规划对偶

4、问题原问题和对偶问题的关系原问题与对偶问题的转换线性规划对偶问题对偶理论从本章的第一个例子可以看出原规划问题追求的是生产利润最大化，而其对偶规划考虑的是比生产更有利的可行性。线性规划对偶问题前者的目标函数值应当不大于后者的目标函数值，即定理3.1（弱对偶性）：若对偶规划（D）的可行解，则分别为原规划（P）和证明：从原规划的约束条件有从对偶规划的约束条件有对偶理论线性规划对偶问题定理3.1（弱对偶性）：若对偶规划（D）的可行解，则分别为原规划（P）和推论1（最优性）：分别为原规划（P）和对偶规划（D）的可行解设若分别为P和D的最优解则显而易见推论2

5、（无界性）：如原规划（P）或其对偶规划（D）具有无界解，则对偶规划（D）或原规划（P）无可行解。显而易见注意：改推论不可逆，教材P58对偶理论线性规划对偶问题推论3：若规划（P）或（D）有可行解，则（P）或（D）有最优解的充要条件是规划（D）或（P）有可行解例试用对偶理论判断下面线性规划是否有最优解解：此规划存在可行解其对偶规划为显然无可行解所以…对偶理论线性规划对偶问题例用对偶理论判断下面线性规划是否存在最优解解此规划存在可行解其对偶规划为存在可行解因此原规划存在最优解对偶理论线性规划对偶问题定理3.2（强对偶性，或称对偶定理）：若原规划（P）有

6、最优解，则对偶规划（D）也有最优解，反之亦然。且二者最优解的目标函数值相等。（证明：教材P58-59）在线性规划问题的最优解中，如果某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之，若如果约束条件取严格不等式，则其对偶变量一定为零。定理3.3（互补松弛性）：线性规划问题的原问题和对偶问题存在一对互补的基本解，其中原问题的非基变量（松弛变量）对应对偶问题的基变量，而对偶问题的非基变量（松弛变量）对应原问题的基变量。定理3.4（互补基本解）：对偶理论线性规划对偶问题线性规划问题的原问题和对偶问题存在一对互补的基本解，其中原问题的非基变量（松

7、弛变量）对应对偶问题的基变量，而对偶问题的非基变量（松弛变量）对应原问题的基变量。定理3.4（互补基本解）：在单纯形法迭代的每一步：如果原问题是可行解，而对偶问题非可行解，则如果对偶问题是可行解，而原问题非可行解，则如果原问题和对偶问题同为可行解，则为最优解影子价格线性规划对偶问题考虑如下的互为对偶的线性规划设为（D）的最优解，则称为规划（P）的第i个约束对应的影子价格（ShadowPrice）换句话说，为第第i种资源（例如设备台时）的一种估价这个价格不是市场价格，而是针对具体企业在一定时期内存在的一种特殊价格，它蕴含在追求最大利润的生产计划之中。

8、资源的市场价格随供求关系而变，而他的影子价格则有赖于资源的利用情况，随企业生产任务、产品结构等情况发生变化而改变。影子价格