对偶及对偶单纯形法

关于对偶及对偶单纯形法本节主要内容线性规划的对偶模型对偶性质对偶单纯形法

学习要点：

1.掌握线性规划的对偶形式

2.掌握对偶单纯形法的解题思路及求解步骤第2页,共40页，2024年2月25日，星期天对偶现象普遍存在“对偶”，在不同的领域有着不同的诠释。在词语中，它是一种修辞方式，指两个字数相等、结构相似的语句，旨表达出相关或相反的意思。如：“下笔千言，离题万里”周长一定，面积最大的矩形是正方形；面积一定，周长最小的矩形是正方形。

数学上也有如下对偶例子：“横眉冷对千夫指，俯首甘为孺子牛”

“天高任鸟飞，海阔凭鱼跃”

第3页,共40页，2024年2月25日，星期天一、线性规划的对偶模型

设某工厂生产两种产品甲和乙，生产中需4种设备按A，B，C，D顺序加工，生产每件产品所需的机时数、每件产品的利润值及每种设备的可利用机时数列于下表：表1.产品数据表

设备产品ABCD产品利润（千元／件）

甲

21402乙

22043设备可利用机时数（时）

1281612问：充分利用设备机时，工厂应生产甲和乙型产品各多少件才能获得最大利润？1.对偶问题的现实来源第4页,共40页，2024年2月25日，星期天解：设甲、乙型产品各生产x1及x2件，最优解为最优值为如何安排生产，使获利最多？则数学模型为：第5页,共40页，2024年2月25日，星期天反过来问：若厂长决定不生产甲和乙型产品，决定出租机器用于接受外加工，只收加工费，那么４种机器的机时如何定价才是最佳决策？出让代价应不低于用同等数量的资源自己生产的利润。

付出的代价最小，且对方能接受。第6页,共40页，2024年2月25日，星期天在市场竞争的时代，厂长的最佳决策应符合两条：

（1）不吃亏原则。即机时定价所赚利润不能低于加工甲、乙型产品所获利润。

（2）竞争性原则。即在上述不吃亏原则下，机时总收费尽可能低一些，以便争取更多用户，最终将设备出租出去。第7页,共40页，2024年2月25日，星期天解：设A、B、C、D设备的机时价分别为y1、y2、y3、y4元，用单纯形法求得最优解为最优值为则新的线性规划数学模型为：第8页,共40页，2024年2月25日，星期天2.原问题与对偶问题的对应关系原问题（对偶问题）对偶问题（原问题）原始规划与对偶规划是同一组数据参数,只是位置有所不同,所描述的问题实际上是同一个问题从另一种角度去描述.第9页,共40页，2024年2月25日，星期天线性规划的对偶模型

特点：目标函数求极大值时，所有约束条件为≤号，变量非负;目标函数求极小值时，所有约束条件为≥号，变量非负.原始线性规划问题对偶线性规划问题对称形式的线性规划第10页,共40页，2024年2月25日，星期天线性规划的对偶模型例2写出线性规划问题的对偶问题解：由于若给出的线性规划不是对称形式，所以先将它化成对称形式，然后再写出相应的对偶问题。第11页,共40页，2024年2月25日，星期天解：首先将原问题变形为则对偶模型为：第12页,共40页，2024年2月25日，星期天线性规划的对偶变换规则(单向)原问题（或对偶问题）对偶问题（或原问题）约束条件右端项目标函数变量的系数目标函数变量的系数约束条件右端项目标函数max目标函数min约束条件m个m个变量≤≥0≥≤0=无约束变量n个n个约束条件≥0≥≤0≤无约束=第13页,共40页，2024年2月25日，星期天对偶问题的形成minz=2x1+4x2-x3s.t.3x1-x2+2x36-x1+2x2-3x3122x1+x2+2x38x1+3x2-x315maxw=6y1+12y2+8y3+15y4s.t.3y1-y2+2y3+y42-y1+2y2+y3+3y442y1-3y2+2y3-y4-1y10,y2,y30,y40≤≥=≥unr≤≥≥=≤≥x1≥0x2≤0x3:unr原始问题变量的个数(3)等于对偶问题约束条件的个数(3)；原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。原始问题变量的性质影响对偶问题约束条件的性质，用表示原始问题约束条件的性质影响对偶问题变量的性质，用表示第14页,共40页，2024年2月25日，星期天例4:写出下列线性规划问题的对偶问题.解：原问题的对偶问题为第15页,共40页，2024年2月25日，星期天定理6.1(对合性)

对偶线性规划的对偶问题是原始线性规划问题。对偶定义对偶定义二、对偶性质（选读）第16页,共40页，2024年2月25日，星期天定理6.2

弱对偶原理(弱对偶性)：设和分别是问题(LP)和(DP)的可行解，则必有推论1:原问题任一可行解的目标函数值是其对偶问题目标函数值的上界；反之，对偶问题任意可行解的目标函数值是其原问题目标函数值的下界。第17页,共40页，2024年2月25日，星期天推论2:

在一对对偶问题（LP）和（DP）中，若其中一个问题可行但目标函数无界，则另一个问题无可行解；这也是对偶问题的无界性。推论3：在一对对偶问题（LP）和（DP）中，若一个有可行解，而另一个无可行解，则该可行的问题目标函数值无界。第18页,共40页，2024年2月25日，星期天定理6.3

最优性判定定理：如果是原问题的可行解，则是原问题的最优解，是其对偶问题的最优解。是其对偶问题的可行解，并且:定理6.4.

在一对对偶问题（LP）和（DP）中，若任意一个有最优解，则另一个也有最优解，且对应的最优值相等。第19页,共40页，2024年2月25日，星期天定理6.6强对偶性：若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。推论4：（LP）与（DP）要么两者都有最优解，要么都无最优解。定理6.7

互补松弛性：设X0和Y0分别是(LP)问题和(DP)问题的可行解，则它们分别是最优解的充要条件是：其中：Xs为松弛变量、Ys为剩余变量.互补松弛条件第20页,共40页，2024年2月25日，星期天对偶性质的应用

借助以上性质可以证明，在用单纯形法求解原问题的迭代过程中，单纯形表右列中的元素对应于原问题的基本可行解，底行中松弛变量对应的元素恰好构成对偶问题的基本解。逐次迭代下去，当底行对应于对偶问题的解也变成基本可行解（底行元素全非负）时，原问题和对偶问题同时达到最优解.即此时对偶问题的这个基本可行解就是它的最优解。

用单纯形方法求解原线性规划的过程中，每次迭代都保证得到原问题的一个基本可行解，底行某些元素对应于对偶问题的基本解.单纯形法的迭代的过程既可以看作使原问题的基本可行解逐步变为最优解（此时底行元素非负)的过程，也可看作使对偶问题的基本解逐步变成基本可行解的过程。

第21页,共40页，2024年2月25日，星期天根据性质1（对偶问题的对偶是它本身），在用单纯形法求解LP时也可这样考虑：从对偶问题的某个基本可行解开始，每次迭代总保证得到对偶问题的一个基本可行解（底行元素均非负），通过逐步迭代，当对偶问题达到最优解时，根据对偶理论，对偶问题的对偶即原问题也达到最优解。对偶单纯形法

适用情况：当原问题没有初始的基本可行解，但是对偶问题有初始的基本可行解（初始表格容易满足①③④）时，用此方法。

优点：当原问题没有初始的基本可行解，不需要借助大M法或二阶段法构造新的模型.对偶单纯形法的基本思想第22页,共40页，2024年2月25日，星期天三、对偶单纯形法注意：它并不是求解对偶问题的单纯形法，而是一个直接求解原LP问题的新算法。

对偶单纯形法是求解LP问题的另一个基本方法。它是根据对偶理论和单纯形法原理而设计出来的，因此称为对偶单纯形法。第23页,共40页，2024年2月25日，星期天对偶单纯形法找出一个DP的基本可行解LP是否可行保持DP为基本可行解情况下转移到LP的另一个基本解最优解是否循环结束第24页,共40页，2024年2月25日，星期天1.对偶单纯形法的迭代步骤1）将原问题化为标准形,写出相应的表格;2）利用容许的运算建立满足①

③④三个特点的单纯形表;3）检查右列元素，若全非负，即表格满足①②

③④四个特点，结束运算；否则，进去第4）步；4）确定离基变量.取右列中最小的负元素所在的行设是第行.第25页,共40页，2024年2月25日，星期天5)确定进基变量所在列对应的变量取为进基变量;观察该行竖线左边的元素若所有则无可行解，结束运算;否则，按如下规则从负系数中选择一个记为第26页,共40页，2024年2月25日，星期天6)进行旋转运算利用容许的运算将变为1,该列其它元素变为0,从而实现将变为基变量的目的.7）观察得到的新表(满足①

③④).若右列元素均非负,则已得最优解,结束运算;否则,返回第4)步.第27页,共40页，2024年2月25日，星期天例5.（教材P79例5.4）用对偶单纯形法求解：引入松弛变量得到标准型线性规划解：第28页,共40页，2024年2月25日，星期天构造对偶单纯形表选取离基变量选取进基变量-1-2-310

-5-2-2-101

-6345000满足①③④,但②不满足第29页,共40页，2024年2月25日，星期天0-1-5/21-1/2

-2111/20-1/2

3017/203/2-9015/2-11/2

210-21-1100111-11满足①③④,但②不满足满足①②③④第30页,共40页，2024年2月25日，星期天满足①②③④是具有标准形式的LP的最优解.

略去松弛变量得原LP问题的最优解为最优值为015/2-11/2

210-21-1100111-11第31页,共40页，2024年2月25日，星期天例6.

用对偶单纯形法求解：引入松弛变量得到标准型线性规划解：第32页,共40页，2024年2月25日，星期天构造对偶单纯形表选取离基变量选取进基变量-2-1-4010

-2-2-20-401

-31281612000满足①③④,但②不满足第33页,共40页，2024年2月25日，星期天-2-1-4010

-2-2-20-401

-31281612000-2-1-4010

-21/21/2010-1/43/46216003-9满足①③④,但②不满足第34页,共40页，2024年2月25日，星期天-2-1-4010

-21/21/2010-1/43/46216003-92140-10

2-1/20-211/2-1/4

-1/4208023-13满足①③④,但②不满足第35页,共40页，2024年2月25日，星期天11020-1/2

3/21/401-1/2-1/41/81/8000442-142140-10

2-1/20-211/2-1/4

-1/4208023-13满足①②③