第2章线性规划对偶问题.ppt

《第2章线性规划对偶问题.ppt》由会员分享，可在线阅读，更多相关《第2章线性规划对偶问题.ppt（59页珍藏版）》请在优知文库上搜索。

1、第第2章章 对偶理论对偶理论线性规划续线性规划续知识点知识点 了解对偶问题的特点，熟悉互为对偶的问了解对偶问题的特点，熟悉互为对偶的问题之间的关系；题之间的关系；掌握对偶规划的理论和性质，如可逆性、掌握对偶规划的理论和性质，如可逆性、弱对偶性、对偶定理、互补松驰定理等；弱对偶性、对偶定理、互补松驰定理等；掌握对偶单纯形法；掌握对偶单纯形法；主要内容主要内容 一、对偶问题的基本概念一、对偶问题的基本概念 二、对称的对偶线性规划二、对称的对偶线性规划 三、对偶的基本性质三、对偶的基本性质 四、对偶单纯形法四、对偶单纯形法一、对偶问题的基本概念一、对偶问题的基本概念载重汽车载重汽车 大轿车大轿车资源

2、限制资源限制钢材钢材劳动力劳动力座椅座椅22.5025116002500400利润（千元利润（千元/辆）辆）34 传统的线性规划问题：传统的线性规划问题：在有限的资源下如何安排生产以获得最大利润在有限的资源下如何安排生产以获得最大利润 该问题的线性规划模型为：该问题的线性规划模型为：目标函数：目标函数：max Z=4x1+3x2 约束条件：约束条件：2x1 2x2 1600 5x1+2.5x2 2500 x1 400 x1 0,x2 0 现在的问题：如果工厂目前不再打算生产现在的问题：如果工厂目前不再打算生产汽车，而是将钢材和座椅以比买价更高的汽车，而是将钢材和座椅以比买价更高的价格卖出去（加

3、价），把生产能力以更高价格卖出去（加价），把生产能力以更高的工时费接受外协加工，那么材料和工时的工时费接受外协加工，那么材料和工时的定价应该是多少才是合算的？的定价应该是多少才是合算的？假设假设y1表示出售单位钢材的利润，表示出售单位钢材的利润，y2表示外协加工的工时利润，表示外协加工的工时利润，y3表示出售每套大轿车座椅的利润表示出售每套大轿车座椅的利润 那么生产一辆载重汽车的材料销售利润和那么生产一辆载重汽车的材料销售利润和工时利润之和不应低于出售一辆载重汽车工时利润之和不应低于出售一辆载重汽车所得的利润，即：所得的利润，即：2y1+2.5y2 3 同样有，同样有，2y1+5y2+y3 4

4、 为了不亏本，各种材料的利润（加价）不为了不亏本，各种材料的利润（加价）不能为负值，即：能为负值，即：y1、y2、y3 0 工厂的总利润是出售材料的利润、工时利工厂的总利润是出售材料的利润、工时利润和座椅利润之和，即：润和座椅利润之和，即：W=1600y1+2500y2+400y3 从工厂决策者的角度看从工厂决策者的角度看W越大越好。但为越大越好。但为了在市场实现交易，在满足上述条件的基了在市场实现交易，在满足上述条件的基础上，础上，W应尽可能小。从而得到如下线性应尽可能小。从而得到如下线性规划模型：规划模型：Min W=1600y1+2500y2+400y32y1+2.5y2 3 s.t.2

5、y1+5y2+y3 4y1、y2、y3 0线性规划原问题和对偶问题线性规划原问题和对偶问题原问题：原问题：Max Z=c1x1+cnxn a11x1+a1nxn b1 a21x1+a2nxn b2s.t.am1x1+amnxn bm X1,xn 0对偶问题：对偶问题：Min W=b1y1+bmym a11y1+am1ym c1 a12y1+am2ym c2s.t.a1ny1+amnym cn y1,ym 0矩阵表述矩阵表述原问题：原问题：Max Z=CTX s.t.AX b X 0对偶问题：对偶问题：Min W=bTY s.t.ATY C Y 0 两个模型之间的关系：两个模型之间的关系：原问题

6、是求最大值，而对偶问题是求最小值；原问题是求最大值，而对偶问题是求最小值；原问题的约束条件是原问题的约束条件是“”，而对偶问题的约，而对偶问题的约束条件是束条件是“”；原问题的目标函数系数是对偶问题的约束条件原问题的目标函数系数是对偶问题的约束条件右端的常数项；原问题的约束条件右端的常数右端的常数项；原问题的约束条件右端的常数项是对偶问题目标函数的系数；项是对偶问题目标函数的系数；原问题约束条件中原问题约束条件中xi的系数是对偶问题第的系数是对偶问题第i个约个约束条件的系数，原问题第束条件的系数，原问题第i个约束条件的系数是个约束条件的系数是对偶问题的约束条件中对偶问题的约束条件中yi的系数。

7、的系数。对称的对偶线性规划对称的对偶线性规划 定义：如果一个线性规划具备下面两个条定义：如果一个线性规划具备下面两个条件，则称它具有对称形式：件，则称它具有对称形式：所有的变量都是非负的；所有的变量都是非负的；所有的约束条件都是不等式，且在目标函数是所有的约束条件都是不等式，且在目标函数是求极大值的情况下，为求极大值的情况下，为“”型，求极小值时，型，求极小值时，为为“”型。型。原问题（对偶问题）原问题（对偶问题）对偶问题（原问题）对偶问题（原问题）目标函数目标函数限定向量限定向量价值向量价值向量技术系数技术系数约束条件约束条件变量数目变量数目约束条件个数约束条件个数变量正负变量正负目标函数目

8、标函数价值向量价值向量限定向量限定向量技术系数技术系数对偶变量对偶变量约束条件个数约束条件个数对偶变量数目对偶变量数目约束条件约束条件非对称形式的对偶问题非对称形式的对偶问题在原线性规划问题为在原线性规划问题为Max型，且变量非负型，且变量非负的前提下：的前提下：1.原问题约束条件是原问题约束条件是“”型型 两边都乘以两边都乘以“-1”转化为转化为“”型，得到对偶规型，得到对偶规划的变量约束为：划的变量约束为：yi 0 例：例：Max Z=x1+2x2-3x3 S.t.x1+2x2+5x3 1 2x1-3x2-4x3 2 x1,x2,x3 0 Max Z=x1+2x2-3x3 S.t.-x1-

9、2x2-5x3 -1 2x1-3x2-4x3 2 x1,x2,x3 0 Min W=-y1+2y2 S.t.-y1+2y2 1 -2y1-3y2 2 -5y1-4y2 -3 y1,y2 0 令令y1=-y1，上述模型化为：，上述模型化为：Min W=y1+2y2 S.t.y1+2y2 1 2y1-3y2 2 5y1-4y2 -3 y1 0,y2 0 例：例：Max Z=x1+2x2-3x3 S.t.x1+2x2+5x3 1 2x1-3x2-4x3 2 x1,x2 0,x3 0 令令x3=-x3，得：，得：Max Z=x1+2x2+3x3 S.t.x1+2x2-5x3 1 2x1-3x2+4x3

10、 2 x1,x2,x3 0 Min W=y1+2y2 S.t.y1+2y2 1 2y1-3y2 2 -5y1+4y2 3 y1,y2 0 第三个方程两边同乘第三个方程两边同乘-1，得，得 Min W=y1+2y2 S.t.y1+2y2 1 2y1-3y2 2 5y1-4y2 -3 y1,y2 02.原问题约束条件是原问题约束条件是“=”型型看成两个约束条件：看成两个约束条件：”+”组成，得到组成，得到对偶规划的变量约束为：对偶规划的变量约束为：yi无非负约束（即可正可负）无非负约束（即可正可负）例：例：Max Z=x1+2x2-3x3 S.t.x1+2x2+5x3 1 2x1-3x2-4x3=

11、2 x1,x2,x3 0 Max Z=x1+2x2-3x3 S.t.x1+2x2+5x3 1 2x1-3x2-4x3 2 2x1-3x2-4x3 2 x1,x2,x3 0 Min W=y1+2y2-2y3 S.t.y1+2y2-2y3 1 2y1-3y2+3y3 2 5y1-4y2+4y3 -3 y1,y2,y3 0 Max Z=x1+2x2-3x3 S.t.x1+2x2+5x3 1 2x1-3x2-4x3 2 -2x1+3x2+4x3 -2 x1,x2,x3 0 令令y4=y2-y3，得：，得：Min W=y1+2y4 S.t.y1+2y4 1 2y1-3y4 2 5y1-4y4 -3 y1

12、 0,y4无符号约束无符号约束 原问题与对偶问题的对应关系原问题与对偶问题的对应关系原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）目标函数为目标函数为 Max Z目标函数为目标函数为 Min W变量变量n个个 0 0无约束无约束n个个 约束条件约束条件约束约束条件条件m个个 m个个 0 0无约束无约束变量变量价值系数价值系数cj约束条件右端项约束条件右端项bi约束条件的系数矩阵约束条件的系数矩阵A约束条件右端项约束条件右端项cj价值系数价值系数bi约束条件的系数矩阵约束条件的系数矩阵AT例：例：写出下面线性规划问写出下面线性规划问题的对偶问题：题的对偶问题：1

13、.123412341231341324max 235234.1,0,Zxxxxxxxxxxxstxxxx xx x无约束 解：根据上述对偶关解：根据上述对偶关系，可以写出原问题系，可以写出原问题的对偶问题：的对偶问题：1231231212313132min 54221.3310,0,Wyyyyyyyystyyyyyyyy无约束例：例：写出下面线性规划问写出下面线性规划问题的对偶问题：题的对偶问题：2.12121212min 354212.3218,0Zxxxxstxxx x 解：根据上述对偶关解：根据上述对偶关系，可以写出原问题系，可以写出原问题的对偶问题：的对偶问题：1231323132ma

14、x 4121833.2250,0,Wyyyyystyyyyy无约束对偶的基本性质对偶的基本性质 原问题：原问题：Max Z=CTX s.t.AX b X 0 对偶问题：Min W=bTY s.t.ATY C Y 0 对称性：对偶问题的对偶是原问题；对称性：对偶问题的对偶是原问题；弱对偶性：若弱对偶性：若X是原问题的可行解，是原问题的可行解，Y是是对偶问题的可行解，则对偶问题的可行解，则CTX bTY 弱对偶性的证明：弱对偶性的证明：AX bXTAT bTXTATY bTY所以：所以：bTY XTATY XTC=CT X 无界性：若原问题（对偶问题）为无界无界性：若原问题（对偶问题）为无界解，则

15、其对偶问题（原问题）无可行解。解，则其对偶问题（原问题）无可行解。例：例：说明：无界性质并不存在逆（例见：说明：无界性质并不存在逆（例见：P57）0,0442.4max21212121xxxxxxt sxxZ 可行解是最优解的条件：可行解是最优解的条件：设设X*是原问题的可行解，是原问题的可行解，Y*是对偶问题的可行是对偶问题的可行解，当解，当CTX*=bTY*时，时，X*，Y*是最优解。是最优解。证明：由弱对偶性，可知原问题的所有可行解证明：由弱对偶性，可知原问题的所有可行解X均满足均满足 CT X bTY*又因为又因为CTX*=bTY*，所以，所以CT X CTX*，即：，即：X*是使目标

16、函数取值最大的可行解。因而是最是使目标函数取值最大的可行解。因而是最优解。优解。同理可证同理可证Y*也是最优解。也是最优解。对偶定理：若原问题有最优解，则对偶对偶定理：若原问题有最优解，则对偶问题也有最优解，且最优目标函数值相等。问题也有最优解，且最优目标函数值相等。证明：设证明：设X*是原问题的最优解，则其对应的基矩阵是原问题的最优解，则其对应的基矩阵B必有：必有：CBTB-1A-CT 0，（非基变量的检验数大于或等于，（非基变量的检验数大于或等于0，基变量的检验数等于基变量的检验数等于0）即：即：ATY*C，其中，其中，Y*=CBTB-1T 故故Y*是对偶问题的可行解，它使：是对偶问题的可行解，它使：W=bTY*=bTCBTB-1T=CBTB-1b 由于由于X*是原问题的最优解，使目标函数值是原问题的最优解，使目标函数值Z=CTX*=CBTB-1b由此得到：由此得到：bTY*=CBTB-1b=CTX*因此，因此，Y*是对偶问题的最优解。是对偶问题的最优解。原规划的检验数对应于对偶规划的一个解；原规划的检验数对应于对偶规划的一个解；对偶规划的检验数对应于原规划的一个解。对偶规划的检验