文档介绍：任何一个求极大化的线性规划问题都有一个求极小化的线性规划问题与之对应,反之亦然,如果我们把其中一个叫原问题,则另一个就叫做它的对偶问题,并称这一对互相联系的两个问题为一对对偶问题。本章将讨论线性规划的对偶问题及灵敏度分析,从而加深对线性规划问题的理解,扩大其应用范围。
 
§1 对偶问题的一般概念
 
 对偶问题的提出
 
在第一章中我们研究过一个生产计划问题,其数学模型为:
 
例1
                         
                                                                     ()
 
现在,从另一个角度来考虑该问题,假设这家企业想将自己生产产品改为对外加工,此时,工厂决策者必须考虑怎样为这三种资源定价的问题。设  分别代表转让两种资源和出租设备的价格和租金。定价的原则是:生产一个单位的甲产品需消耗9个单位的钢材、4个单位的铜材、3个单位的设备台时,获利70个单位;那么,将这些资源全部转让时所获得的利润  应不少于70个单位,即
                               ()
同样的分析,有
                            ()
此时,企业的总获利(即对方的总付出)为
                    ()
为使对方容易接受,该厂只能在约束条件()和()下求()式的最小值,即
                         ()
 
上述两个模型()和()是对同一问题的两种不同考虑的数学描述,其间有着一定的内在联系,我们对此进行比较分析,并从中找出规律,两个模型的对应关系有:
(1)       两个问题的系数矩阵互为转置;
(2)       一个问题的变量个数等于另一个问题的约束条件个数;
(3)       一个问题的右端系数是另一个问题的目标函数的系数;
(4)       一个问题的目标函数为极大化,约束条件为“≤”类型,另一个问题的目标函数为极小化,约束条件为“≥”
我们把这种对应关系称为对偶关系,如果把()式称为原问题,则()式称为对偶问题。
 
 对偶问题的形式
 
一、             对称形对偶问题
 
定义1 设原线性规划问题为
                             ()
则称下列线性规划问题
                                ()
为其对偶问题,其中  称其为对偶变量,并称()和()式为一对对称型对偶问题。
原始对偶问题()和对偶问题()之间的对应关系可以用表2-1表示。
 
这个表从横向看是原始问题,从纵向看使对偶问题。用矩阵符号表示原始问题()和对偶问题