运筹学 第二章对偶理论

《运筹学 第二章对偶理论》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章对偶理论及灵敏度分析2.1.1单纯形法的矩阵描述2.1.2线性规划对偶问题2.1.3对偶问题的基本性质2.1.4影子价格2.1.5对偶单纯形法2.2.6灵敏度问题第1节单纯形法的矩阵描述设线性规划问题:目标函数maxz=CX;约束条件AX≤b;非负条件X≥0给这线性规划问题的约约束条件加入松弛变量以后，得到标准型：maxz=CX+0Xs;AX+IXs=b;X，Xs≥0这里I是m×m单位矩阵。单纯形法计算时，总选取I为初始基，对应基变量Xs。设迭代若干步后，基变量为XB，XB在初始单纯形表中的系数矩阵为B，将B在初始单纯形表中单独列出，而A中去掉B的若干列后剩余的列组成矩阵N，这样原线性

2、规划问题的初始单纯形表可列成以下形式：表1：原始单纯形表项目非基变量基变量XBXNXS0XsbBNI检验数CBCN0当迭代若干步后，基变量变为XB，则该步的单纯形表中由XB对应的系数列组成的矩阵为I，又因单纯形法的迭代是对约束增广矩阵进行的行的初等变换，所以对应XS的系数矩阵I在新表中为B-1，故当基变量为XB时，新的单纯形表具有下表的形式。表2：迭代后项目基变量非基变量XBXNXSCBXBB-1bIB-1NB-1检验数0CN-CBB-1N-CBB-1从表1和表2可以看出，进行迭代后基变量为XB时，其在初始单纯形表中的系数矩阵为B，则有：（1）对应初始单纯形表中的单位矩阵I，迭代后在新的单纯

3、形表中为B-1（2）初始单纯形表中基变量XS=b，迭代后在新表中XB=B-1b;(3)初始单纯形表中约束系数矩阵为[A,I]=[B,N,I],迭代后表中相应的系数矩阵为[I,B-1N,B-1](4)若初始矩阵中变量Xj的系数向量为Pj，迭代后为Pj’,则有Pj’=B-1Pj(5)当B为最优基时，在表2中应该有CN-CBB-1N≤0（1）-CB-1≤0（2）因XB的检验数可写为CB-CBI=0（3）故式（1）-（3）可重写为C-CBB-1A≤0-CB-1≤0CB-1称为单纯形乘子小结1）掌握矩阵的运算；2）理解基矩阵的作用；3）了解矩阵运算与单纯表的关系。返回继续2.1.2线性规划的对偶问题一

4、、对偶问题的提出二、原问题与对偶问题的数学模型三、原问题与对偶问题的对应关系实例：某家电厂家利用现有资源生产两种产品，有关数据如下表：设备A设备B调试工序利润（元）0612521115时24时5时产品Ⅰ产品Ⅱ最大负荷一、对偶问题的提出如何安排生产，使获利最多？厂家设Ⅰ产量–––––Ⅱ产量–––––设：设备A——元／时设备B––––元／时调试工序––––元／时租赁付出的代价最小，且对方能接受。出让代价应不低于用同等数量的资源自己生产的利润。设某人有订单，但没有生产能力，这时需要租赁厂方资源设备A设备B调试工序利润（元）0612521115时24时5时ⅠⅡD厂家能接受的条件：租赁方的意愿：单位产

5、品Ⅰ出租收入不低于2元单位产品Ⅱ出租收入不低于1元出让代价应不低于用同等数量的资源自己生产的利润。对偶性是线性规划问题的最重要的内容之一。每一个线性规划（LP）必然有与之相伴而生的另一个线性规划问题，即任何一个求maxZ的LP都有一个求minZ的LP。其中的一个问题叫“原问题”，记为“P”，另一个称为“对偶问题”，记为“D”。例23x1x2原问题12y122≤128y212≤816y340≤1612y404≤12对偶问题23厂家对偶问题原问题租赁厂家一对对偶问题3个约束2个变量2个约束3个变量原问题对偶问题一般规律特点：1．2．限定向量b价值向量C（资源向量）3．一个约束一个变量。4．的LP

6、约束“”的LP是“”的约束。5．变量都是非负限制。其它形式的对偶?二、原问题与对偶问题的数学模型1．对称形式的对偶当原问题对偶问题只含有不等式约束时，称为对称形式的对偶。原问题对偶问题情形一：原问题对偶问题化为标准对称型情形二：证明对偶2、非对称形式的对偶若原问题的约束条件是等式，则原问题对偶问题推导:原问题根据对称形式的对偶模型,可直接写出上述问题的对偶问题:令，得对偶问题为：证毕。ïîïíì≥=Þ无约束YCYAYbwmin三、原问题与对偶问题的对应关系原问题（或对偶问题）对偶问题（或原问题）例1:对偶问题为例2：求最小化线性规划对偶问题的另一种思路例题：对偶转化令Z1=-f可得则其对偶问

7、题再令z=-f1得练习题（1）练习2：练习3答案：返回继续3.1.2对偶问题的基本性质对称性弱对偶性最优性对偶性（强对偶性）互补松弛性从一般引例中可见：原问题与对偶问题在某种意义上来说，实质上是一样的，因为第二个问题仅仅是第一个问题的另一种表达而已。理论表述：原问题与对偶问题解的关系对偶问题的基本性质一、对称定理：定理：对偶问题的对偶是原问题。设原问题（1）对偶问题（2）minZ’=-CXs.t.-AX≥-b