最优化理论与方法 课件 6 对偶原理

第四章对偶原理窗含西岭千秋雪，门泊东吴万里船对偶是一种普遍现象2线性规划的对偶理论1947年提出；支持对偶理论的思想是：每一个线性规划问题都存在一个与其对偶的问题。3某公司制造两种家电产品。假定：已知各制造一件时分别占用的设备A、设备B的台时、调试时间以及设备A、设备B和调试工序每天的可用能力、产品的单件利润，如表所示，要确定A、B两种家电各生产多少件，获利最大。问题提出产品产品1产品2每天可用能力设备A(h)0515设备B(h)6224调试工序115单件利润214这是一个典型的最优生产计划制定问题。制定获得最大利润生产计划的线性规划问题为：5再从另一个角度看问题。假定：有另一个公司想把该公司的资源收买下来，它至少应付多大的代价才能让原公司愿意放弃生产活动出让资源。显然，原公司出让自己资源的条件是：出让价不低于同等资源由自己组织生产时获取的盈利。设y1,y2,y3分别代表单位时间(h)设备A、B及调试工序的出让代价，则y1,y2,y3应满足6又另外一个公司希望用个最小代价把该公司的资源收买过来，有综上，有7

(LP1)与(LP2)两个线性规划问题的表现形式和系数之间存在许多对应关系，并且maxz=minw前者为原问题，后者是前者的对偶问题。81.对称形式的对偶9观察分析上述模型形式，可发现，按如下规则，可以从线性规划原问题得到其对偶问题：（1）目标函数由max变为min模型；（2）对应原问题，每个约束行有一个对偶变量yi,i

=1,2,…,m;（3）对偶问题约束为>=型，有n行；（4）原问题的价值系数c变换为对偶问题的右端项；（5）原问题的右端项b变换为对偶问题的价值系数。根据上述规则，可直接写出规范形式下LP问题的对偶问题。10例：写出下列线性规划问题的对偶问题11写对称形式对偶问题的要点：(1)max变成min(2)价值系数与右端向量互换(3)系数矩阵转置(4)≤变≥原问题中约束条件的个数=对偶问题中变量的个数原问题中变量的个数=对偶问题中约束条件的个数12写成等价形式对偶问题为：2.非对称形式的对偶13例min5x1+4x2+3x3s.t.x1+x2+x3=43x1+2x2+x3=5

x1≥

0,x2≥0,

x3≥0对偶问题为：

max4w1+5w2s.t.w1+3w2≤5

w1+2w2≤

4

w1+w2≤

314mincxs.t.A1x

≥b1，

A1

为m1×n,b1为m1×1

A2x

=b2，A2

为m2×n,b2为m2×1

A3x

≤b3，A3

为m3×n,b3为m3×1

x≥0引入松弛变量：

mincx

s.t.A1x–xs=b1，

xs为m1×1

A2x

=b2，

A3x+xt=

b3，xt为m3×1

x,xs

,xt≥03.一般情形的对偶问题15即：按照非对称对偶的定义，其对偶问题为：16即：17总结minmax变量>=0<=0无限制<=>==约束方程约束方程>=<==>=0<=0无限制变量18例：19练习：直接写出线性规划问题的对偶问题：20练习：直接写出线性规划问题的对偶问题：21对偶问题的基本性质原问题

对偶问题mincxmaxwbs.t.Ax

≥bs.t.wA≤c

x≥0w≥022定理1：弱对偶定理定理表明，对于对偶中的两个问题，每一个问题的任何一个可行解处的目标函数