第2章789对偶理论

1本节研究、解决三个问题：1、如何写出对偶问题；2、原问题与对偶问题之间的关系；3、对偶单纯形法（解线性规划问题的第4种方法）22.5.1对偶问题的提出例1——生产计划问题某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：产品A产品B资源限量劳动力设备原材料9434510360200300利润（元/kg）701203例1——模型问题：如何安排生产计划，使得获利最多？步骤：1、确定决策变量：设生产A产品x1kg，B产品x2kg2、确定目标函数：maxZ=70X1+120X23、确定约束条件：人力约束9X1+4X2≤360

设备约束4X1+5X2

≤200

原材料约束3X1+10X2

≤300

非负性约束X1≥0X2≥04例1——另一角度分析：成本角度

利润大的另一方面是什么：成本越小！因此，我们可以试着从成本角度来分析生产决策者的心态！现在资源的数量已经定了，那么我们可以从价格来着手！产品A产品B资源限制劳动力设备原材料9434510360200300单位利润701205目标分析设劳动力每个工时收费Y1元，设备台时费用Y2元，原材料附加费Y3元。现在我们的目标变成下面这个式子：

minw=360y1+200y2+300y3那么约束条件是什么呢？6约束条件分析单个因素的收入最大：即投入于产品A的资源收入要大于A的销售收入，投入于产品B的资源收入要大于B的销售收入，即

9y1+4y2+3y3≥704y1+5y2+10y3

≥120从整个问题来看，1、总的投入最低，2、投入品的价值也要得到合理体现！综合起来得到问题模型！7问题模型Minw=360y1+200y2+300y3s.t.9y1+4y2+3y3≥70

4y1+5y2+10y3

≥120y1，y2，y30这个线性规划问题称为例1的（称为原问题）对偶问题。8一般形式的线性规划问题，写出其对偶问题的规则是什么？课堂讲解第44页；要求：看到原问题，能立即写出其对偶形式；9原问题与对偶问题比较原问题：对偶问题：maxZ=70X1+120X2

minω=360y1+200y2+300y3

9X1+4X2≤3609y1+4y2+3y3

≥70(1)4X1+5X2

≤2004y1+5y2+10y3

≥120(2)3X1+10X2

≤300X1≥0X2≥0y1≥0,

y2≥0,

y3≥0102.5.2对偶问题表示根据上述例题可见，对于形如如下形式的线性规划问题：我们可以马上得出它的对偶问题：其中：AT、bT

分别是原LP中的约束条件矩阵A的转置矩阵与约束条件中右端向量的转置(即为行向量)。11线性规划问题与其对偶问题的相关性原问题的约束条件的个数m就是对偶问题的变量的个数；原问题的变量的个数n就是对偶问题的约束条件的个数；若原问题的目标函数是Max型，则对偶问题的目标函数必是Min型。它们二者的最优目标函数值相等。122.5.3一般LP的对偶问题

（书本P45定义2.5.1）原问题（P）：对偶问题（D）：mincTxmaxbTys.t.aiTx

=bii=1,…,ps.t.y0

aiTx

≥bii=p+1,…,my≥0xj≥0j=1,…,qAjTy

cxj

0j=q+1,…,nAjTy=c><><13对偶规则原问题有m个约束条件

对偶问题有m个变量原问题有n个变量

对偶问题有n个约束条件原问题的价值系数

对偶问题的右端项原问题的右端项

对偶问题的价值系数原问题的系数矩阵转置后为对偶问题系数矩阵14对偶规则对偶问题原问题目标函数maxmin目标函数约束条件

≤

≥

=≥变量≤无约束

≥变量≤

无约束≥

≤

约束条件

=152.5.4对偶问题的基本性质对偶定理2.5.1：若一个LP问题有最优解，则它的对偶问题也有最优解，且目标函数值相等。对称性：对偶问题与原问题互为对偶。无界性：原问题无界，对偶问题无可行解原问题与对偶问题：原始对偶有最优解问题无界无可行解有最优解1XX问题无界XX3无可行解X32162.5.5对偶变量的经济解释对偶变量yi在经济上表示原问题第i种资源的边际贡献，即当第i种资源增加一个单位时，相应的目标值z的增量。对偶问题的最优解yi*是原问题第i种资源的影子价格应用:1.出租资源或设备时，租金价格的设定(至少高于该资源在企业内的影子价格)2.企业内资源I的存量设定(当资源I的影子价格

市场价格时，可买进该资源；否则卖出)3.调整资源的分配量以增加利润172.5（1）对偶问题要求：了解LP对偶问题的实际意义掌握对偶问题的建立规则与基本性质了解对偶最优