《对偶问的提出》由会员分享,可在线阅读,更多相关《对偶问的提出(6页珍藏版)》请在金锄头文库上搜索。
1、 运筹学 例例:某厂在计划期内要安排生产某厂在计划期内要安排生产、两种产品,已知生产单两种产品,已知生产单 位产品所需的设备台时及位产品所需的设备台时及A、B两种原材料的消耗、单位两种原材料的消耗、单位 产品的获利性如下表所示。产品的获利性如下表所示。(1)该厂该厂如何安排生产计划才能获利最大如何安排生产计划才能获利最大;(2)假设该厂决定不生产产品假设该厂决定不生产产品和和,而将其所有资源出租或,而将其所有资源出租或 外售,应如何给每种资源定价。外售,应如何给每种资源定价。设备设备AB1402048台时台时16千克千克12千克千克单位产品获利性单位产品获利性2元元3元元 3 3 对偶问题的提
2、出对偶问题的提出对偶问题的提出对偶问题的提出 运筹学 4 4 线性规划问题的对偶理论线性规划问题的对偶理论线性规划问题的对偶理论线性规划问题的对偶理论例:例: 求下列求下列LP问题的对偶问题问题的对偶问题 运筹学 二、对偶问题的基本性质二、对偶问题的基本性质二、对偶问题的基本性质二、对偶问题的基本性质 1. 1. 对称性对称性对称性对称性: 4 4 线性规划问题的对偶理论线性规划问题的对偶理论线性规划问题的对偶理论线性规划问题的对偶理论对偶问题的对偶是原问题。对偶问题的对偶是原问题。对偶问题的对偶是原问题。对偶问题的对偶是原问题。2. 2.弱对偶性弱对偶性弱对偶性弱对偶性:3. 3. 若原问题
3、若原问题若原问题若原问题( (对偶问题对偶问题对偶问题对偶问题) )为为为为无界解无界解无界解无界解,则其对偶问题,则其对偶问题,则其对偶问题,则其对偶问题( (原问题原问题原问题原问题) )无可无可无可无可 行解行解行解行解。注注5. 5. 对偶定理对偶定理对偶定理对偶定理: 若原问题有最优解,则其对偶问题也有最优解,若原问题有最优解,则其对偶问题也有最优解,若原问题有最优解,则其对偶问题也有最优解,若原问题有最优解,则其对偶问题也有最优解, 且目标函数值相等。且目标函数值相等。且目标函数值相等。且目标函数值相等。 运筹学 4 4 线性规划问题的对偶理论线性规划问题的对偶理论线性规划问题的对偶理论线性规划问题的对偶理论例例1: 已知已知LP问题问题试用对偶理论证明上述试用对偶理论证明上述LP问题无最优解。问题无最优解。 运筹学 4 4 线性规划问题的对偶理论线性规划问题的对偶理论线性规划问题的对偶理论线性规划问题的对偶理论例例2: 已知线性规划问题已知线性规划问题已知其对偶问题的最优解为已知其对偶问题的最优解为 试用对偶理论试用对偶理论找出原问题的最优解。找出原问题的最优解。 运筹学 作业:作业:P74:第:第2.3题之题之(1)、(2);P75:第:第2.7题题.课后练习题:课后练习题:第第2.2题;第题;第2.4题题.