对偶单纯形与线性规划模型.doc

最优化模型与实验
第二章 对偶规划和灵敏度分析与实验
第 40 页
第 59 页
第二章 对偶规划和灵敏度分析与实验
§ 对偶理论
线性规划的对偶理论不仅在理论上而且在实践上都是十分重要的。
)
3．无界性 问题〔P〕和〔D〕同时有最优解的充分必要条件是它们同时有可行解。而且假设其中有一个问题无界，则另一个问题无解。
4．强对偶性 设x*和w*分别为〔P〕和〔D〕的可行解，则它们分别为 〔P〕和〔D〕的最优解当且仅当
cTx*=(w*)Tb ()
5．互补松弛性 设x*和w*分别为原问题〔P〕和对偶问题〔D〕的可行解，则它们分别为〔P〕和〔D〕的最优解当且仅当，
，；，。 () 使用矩阵形式，可得x*和w*的互补松弛性条件:
w*(Ax*–b)=0 ， (c–w*A)x*=0 (’)
归纳：一对对偶规划的最优解满足互补松弛性，如果将等式约束看成是起作用〔临界〕约束，把自由变量看成非起作用约束。那么有下面结论，设一对偶规划都有可行解，假设原规划某一约束是某个最优解的非起作用〔临界〕约束，则它的对偶约束一定是对偶规划所有最优解的起作用约束。
最优化模型与实验
第二章 对偶规划和灵敏度分析与实验
第 60 页
第 45 页
6．唯一性 问题〔P〕有非退化的最优基本可行解，那么其对偶规划(D)有唯一的最优解。
7．对偶变量的经济解释 假定所讨论的是下面的线性规划问题
〔P〕
其中b表示某工厂所拥有的m种资源的总量，aij表示生产每件第j种产品需消耗第i种资源的量，该问题的实际背景是在资源有限的条件下安排生产，以使效益最大。
影子价格 设有一个工业系统，它拥有种不同生产工厂，生产种社会所需的产品。已知一年内社会对第种产品的最低需求量为，一年内一家第类生产工厂的运行成本为，生产第种产品的数量为，那么，在保证满足社会对种产品的需求量的前提下，每种类型工厂各应投入多少家运行，才能保证成本最小？
设为投入运行的第类工厂数量，则
设最优解为，对应的最优基，对偶最优解为，则最优值：
最优化模型与实验
第二章 对偶规划和灵敏度分析与实验
第 46 页
第 47 页
假设现在社会对第种产品的最低需求量出现变化，改变量为，且此时最优基解不变，即仍是最优基，不变，则z的增量为，那么当改变量趋于时，有
即是增加一个单位时，必须增加的成本，亦即一个单位的的最低价格为，称为“影子价格”。假设使用矩阵与向量形式来说明。设B是问题〔P〕的最优基，由最优值知 〔记〕, 则
()
故可以看作当第i种资源从原来的量bi增加一个单位时，目标函数最优值的增加值。
经济学家通常把w*称为影子价格，也就是针对收益最大的产品生产安排，对资源所作的一种价格估计。即当某种资源的市场价格低于影子价格时，工厂买进该种资源安排生产将使收益增加；反之，工厂把该种资源卖出去将显得更为合适。
　某企业利用三种原料生产两种产品。三种原料的月供应量，生产一吨产品
最优化模型与实验
第二章 对偶规划和灵敏度分析与实验
第 60 页
第 47 页
所消耗各种原料的数量及单位产品价格如下表所示。设生产的产品均可在市场销售，企业应如何安排月生产计划，使总收益最大。
　　　　　　　　　　　产品
　　　　　单位产品消耗
原料
　　
原料月供应量
〔吨〕
单位产品价格〔万元／吨〕
设计划生产产品的数量为〔吨／月〕，，则所讨论的问题的数学模型为。
如果另一个公司想从该企业购买这三种原料，那么这三种原料的价格应是多少，双方才能都是合理的呢？
建立对偶模型：设原料的价格为〔万元／吨〕，显然，应有。由原问题的条件，生产一吨产品需消耗１吨原料，２吨原料，３吨原料，可获得收益为万元。因此假设将生产一吨产品的这些原料卖出所得的收益为
〔万元〕
它必须不少于生产一吨产品所得的收益，对于该企业才是合算的。所以应有
对于产品，可类似得到
最优化模型与实验
第二章 对偶规划和灵敏度分析与实验
第 48 页
第 59 页
同时，假设买方〔公司〕欲购买该工厂的全部原料，则应付出万元〔这也是该工厂卖出全部原料的总收益〕。从买方角度应使总支出尽可能的少。因此，可得到线性规划问题
不难看出问题〔P〕与问题〔D〕互为对偶问题。问题〔P〕的第个约束对应于对偶变量，问题〔D〕