1、第二章 对偶问题与灵敏度分析w 重点与难点：1、对偶问题的定义，对偶定理，对偶问题最优解的经济含义，由最优单纯形表求对偶问题最优解；2、对偶单纯形法的特点，对偶单纯形法求解；3、灵敏度分析：价值系数 cj发生变化，右端常数 bi发生变化，增加一个变量，增加一个约束， A中对应非基变量的一列元素发生变化。OR1 1第二章 对偶问题与灵敏度分析w 要求：了解 LP对偶问题的实际背景了解对偶问题的建立规则与基本性质掌握对偶最优解的计算及其经济解释掌握 LP的灵敏度分析OR1 22.1 对偶问题w 2.1.1 对偶问题的提出回顾例题 1： 现在 A、 B两产品销路不畅，可以将所有资源出租或外卖，现在要
2、谈判，我们的（资源的）价格底线是多少？产 品 A 产 品 B 资 源限制劳动 力设备原材料9434510360200300单 位利 润 70 120OR1 3对偶模型w 设 每个工时收费 Y1元，每设备台时费用 Y2元，每单位原材料收费 Y3元。出租（卖出）收入不低于生产收入：9y1+4y2+3y3 704y1+5y2+10y3 120目标： =360y1+200y2+300y3出租收入越多越好？还是至少不低于某数？OR1 4原问题与对偶问题之比较原问题： 对偶问题：maxZ=70X1+120X2 min=360y1+200y2+300y3 9X1+4X2360 9y1+4y2+3y3 70
3、4X1+5X2 200 4y1+5y2+10y3 120 3X1+10X2 300 y1 0, y2 0, y3 0X10 X20OR1 52.1.2对偶规则原问题一般模型： 对偶问题一般模型：maxZ=CX min =YbAX b YA CX 0 Y 0OR1 6对偶规则 P56. 原问题（或对偶问题） 对偶问题（或原问题）目标函数 maxz 目标函数 minn个 n个变量 约束条件 0 0 无 约束 约束条件变量m个 m个 00 无 约束约束条件右端项 目标函数变量的系数目标函数变量的系数 约束条件右端项OR1 7例题 2：写出下列原问题的对偶问题OR1 8例题 3：写出以下模型的对偶问题w 例题 3 max =7y1+4y2-2y3minZ=3x1+2x2-6x3+x5 2y1+ y2- y3 32x1+x2-4x3+x4+3x5 7 y1 +3y3 2x1+ 2x3 -x4 4 -4y1+ 2y2 -6-x1+3x2 -x4+ x5 =-2 y1 -y2 -y3 0x1， x2， x3 0; 3y1 +y3=1x4 0;x5无限制 y1 0y2 0y3 无约束 OR1 9例题 4：写出以下模型的对偶问题OR1 10
