运筹学胡运权第五版课件(第二章).ppt

;

;假设另有四海机器厂想租借常山机器厂的全部可用资源进行生产。问：常山机器厂应该如何给这些资源定出一个合理的租金，既使四海机器厂愿意租借，又使本厂能得到自己组织生产这些产品时所能获得的最大收益。

;对偶性是线性规划问题的最重要的内容之一。

每一个线性规划〔LP1〕必然有与之相伴而生的另一个线性规划问题〔LP2〕，即任何一个求maxz的LP1都有一个求minw的LP2。

将LP1称为“原问题”，记为P；

将LP2称为“对偶问题”，记为D。;原问题P;2、一般形式;其中;例：写出以下LP问题的对偶问题;§2.2原问题与对偶问题;例将以下问题作为原问题，写出其对偶问题。;3、互为对偶关系

假设LP2是LP1的对偶问题，那么LP1是LP2的对偶问题。;例写出以下问题的对偶问题。;第二步对偶化;比较原问题和对偶问题：;4、原问题与对偶问题的互化;例直接写出以下线性规划问题的对偶问题。;练习写出以下问题的对偶问题。;§2.3对偶问题的根本性质;1、弱对偶性（弱对偶原理）：设和分别是问题P和D的可行解，则必有;2、最优性：

假设X*和Y*分别是P和D的可行解且CX*=bTY*，那么X*，Y*分别是问题P和D的最优解。;3、无界性

假设原问题有无界解，那么对偶问题无可行解。

假设对偶问题有无界解，那么原问题无可行解。;4、强对偶性〔对偶定理〕

假设原问题有最优解，那么对偶问题一定有最优解，且

zmax=wmin.;;5、互补松弛性;将该性质应用于其对偶问题时，那么有：;例考虑下面问题;解:;6、P和D之间存在一对互补的基解

;原问题;例比照两个互为对偶问题间的互补基解。;利用一对互补的基解，判定目标函数的大小：;小结

利用对偶问题的根本性质确定最优解的方法：;例判断以下说法是否正确：

〔1〕假设线性规划的原问题有可行解，那么对偶问题一定有可行解。

〔2〕假设线性规划的对偶问题无可行解，那么原问题一定无可行解。

〔3〕在互为对偶的一对原问题和对偶问题中，不管原问题是求极大还是求极小，原问题可行解的目标函数值一定不超过对偶问???可行解的目标函数值。

〔4〕任何线性规划问题都有唯一的对偶问题;1、定义

对于一对互补的基解，总满足;2、性质;例P;〔3〕影子价格是一种时机本钱。;〔5〕检验数的经济意义;〔2〕使管理者了解花多大代价买进资源或卖出资源是适宜的;§2.6灵敏度分析;2．步骤;第二步在最终表中分别检查原问题和对偶问题是否为可行解。

假设第三列没有负数，那么原问题的基解是可行解；

假设检验数没有正数，那么对偶问题的基解是可行解。;6-1分析cj的变化范围;解：;当λ2=0时，将λ1反映到最终表得到;当λ1=0时，将λ2反映到最终表得到;6-2分析bi的变化范围;Cj;〔1〕分析λ1的影响;〔2〕分析λ2的影响;〔3〕分析λ3的影响;6-3增加一个变量的分析;Cj;Cj;最优解不变

最优解改变，最优基不变

最优基改变