资源描述：
《线性规划讲稿2.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、第三节对偶规划一、对偶线性规划问题1．例子【例2-13】在例2-1中，有一用户想购买该厂原料及租用该厂的设备。问应如何确定原料及租用设备工作时间的价格，双方才便于达成协议。解以xx1、2分别表示工厂每天生产A、B产品的数量，fxx(12、)表示该厂每天的获利。在2-1例中得出的规划问题()L如下⎧maxf(x,x)=300x+400x1212⎪⎪3x1+6x2≤60⎨⎪2x1+x2≤16⎪x≥,0x≥0⎩12现在就工厂来说，出租设备和卖出原料所获利益不能低于自己生产所获利益。1设每吨原料定价为y1元，使用设备每小租金为y2元则有：3yy12+≥230
2、06yy+≥40012yy12≥≥0,0就用户来讲，自然希望购买全部原料及租用全部设备时间所需的总费用越少越好。因此有下面要求min(,gyy)=60y+16y1212从而我们又得如下线性规划问题（D）⎧ming(y1,y2)=60y1+16y2⎪⎪3y1+2y2≥300(D)⎨6y+y≥400⎪12⎪y≥,0y≥0⎩12显然，当maxf=ming时，厂方和用户都会认为方案是最好的。22．对偶规划问题的定义给定线性规划问题⎧maxCX⎪(L)⎨AX≤b⎪⎩X≥0⎧minYb⎪(D)⎨YA≥C⎪⎩Y≥0称()D为()L的对偶规划问题３．对偶规划问题之间
3、的关系（1）问题()L是求最大值，问题()D是求最小值。（2）问题()L中的约束全是“≤”，问题()D中约束全是“≥”。（3）问题()L中目标函数系数是问题()D中约束条件右端常数项，问题()L中约束条件右端常数项是问题()D中目标函数的系数。（4）问题()L中决策变量和约束条件的3个数分别与问题()D中约束条件和决策变量个数相同。（5）问题()L与问题()D中决策变量均非负。上述两个问题，只要知道其中一个就可按（1）－（5）的要求写出另一个，称它们之间的这种关系为对偶关系。进一步，任意给定一个线性规划问题，都可以写出他的对偶规划问题，其对应关系如下
4、表：表2-18对偶规划之间的对应关系原始问题（对偶问题）对偶问题（原始问题）目标函数f：maxf目标函数g：ming约束条件个数：m个对偶变量个数：m个约束条件i为：“≤”对偶变量yi≥0约束条件i为：“＝”对偶变量yi为自由变4量变量个数：n个约束条件个数：n个变量xj≥0约束条件j为：“≥”变量xj为自由变量约束条件j为“＝”例如：标准形式线性规划问题⎧maxf=CX⎪(LP)⎨AX=b⎪⎩X≥0的对偶问题为：⎧ming=Yb(D)⎨⎩YA≥C【例2-14】写出下述规划问题的对偶规划⎧min(x+2x)12⎪x+x≤6⎪12⎪⎨x1−x2≥−4⎪
5、x+2x=6⎪12⎪x≥,0x无非负限制⎩125解：目标函数是ming，故先将约束条件化为“≥”和“＝”得⎧min(x+2x)12⎪−x−x≥−6⎪12⎪⎨x1−x2≥−4⎪x+2x=6⎪12⎪x≥0⎩1根据表2-18所列对应关系，得对偶问题为⎧max(−6y1−4y2+6y3)⎪⎪−y1+y2+y3≤1⎨−y−y+2y=2⎪123⎪y≥,0y≥0⎩12二、对偶定理（略）三、对偶单纯形法设B为问题()L的一个基，我们知道，−1−1Bb≥,0CBBA−C≥0是为B(LP)最优基的6条件。实际上也是()D的最优基的条件。下面给出对偶单纯形法的迭代步骤。(
6、1)对初始对偶可行基，列出初始单纯形表，此表中必有λjjj=zc−≥0。(2)检验bii≥=01,,2,,?m是否成立？若成立，停止迭代，初始解就是最优解，否则转(3)。(3)确定指标集Ki={
7、bi<01,≤im≤}。(4)若对某个k∈K均有aj≥=01,,2,,?nkj则问题(LP)没有最优解，否则转(5)。(5)确定迭代元素，令jj=min{
8、b<0}kii式中：ji为对应bi<0的基变量下角标。于是θ=min{−λ/a,a<}0jkjkjl=min{j
9、−λ/a=θ,a<1,0≤j≤n}jkjkj7(6)以akl为迭代元素，按一般单纯形法迭代
10、运算，得到新的单纯形表，转(2)。【例题2－15】用对偶单纯形法求解⎧max(−x−2x)12⎪x+2x≥4⎪12⎪⎨x1≤8⎪x+x≥6⎪12⎪x≥,0x≥0⎩12解：将所给问题化为标准形得⎧max(−x−2x)12⎪−x−2x+x=−4⎪123⎪⎨x1+x4=8⎪−x−x+x=−6⎪125⎪x≥0，j=1，2，…，5⎩j以BPPP=(,,)345为初始基，可列出单纯形表（见表2-19）8表2-19基B对应的初始单纯形表基变量bix1x2x3x4x5x3－4(-1)－2100x4810010x5－6-1－1001检验数012000由于在bi<0之中
11、，对应的x3下角标最小，故x3为出基变量，而⎧⎪λj⎫⎪λ1λ2θ=min⎨−a1j<0⎬=1=−=−⎪⎩a
