Chapter 3.1-3.2 线性规划的对偶和灵敏度分析.ppt

《Chapter 3.1-3.2 线性规划的对偶和灵敏度分析.ppt》由会员分享，可在线阅读，更多相关《Chapter 3.1-3.2 线性规划的对偶和灵敏度分析.ppt（58页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-1-运筹学 Chapter 3 线性规划的对偶线性规划的对偶和灵敏度分析和灵敏度分析对偶问题的提出对偶问题的提出对偶问题的基本性质对偶问题的基本性质影子价格影子价格对偶单纯形法对偶单纯形法灵敏度分析灵敏度分析(选讲选讲)本章主要内容：本章主要内容：本章主要内容：本章主要内容：-2-运筹学 3.1 对偶问题的提出-3-运筹学 对偶对偶理论是线性规划中最重要的理论之一，是深入理论是线性规划中最重要的理论之一，是深入了解线性规划问题结构的重要理论基础。同时，由于了解线性规划问题结构的重要理论基础。同时，由于问题提出本身所具有的经济意义，使得它成为对线性问题提出本身所具有的经济意义，使得它成为对线性

2、规划问题系统进行经济分析和敏感性分析的重要工具。规划问题系统进行经济分析和敏感性分析的重要工具。那么，那么，对偶问题是怎样提出的，为什么会产生这样一对偶问题是怎样提出的，为什么会产生这样一种问题呢？种问题呢？对偶问题的提出对偶问题的提出-4-运筹学 两个黄鹂鸣翠柳，一行白鹭上青天。两个黄鹂鸣翠柳，一行白鹭上青天。窗含西岭千秋雪，门泊东吴万里船。窗含西岭千秋雪，门泊东吴万里船。杜甫杜甫绝句绝句-5-运筹学 俩家具制造商间的对话：俩家具制造商间的对话：唉唉!我想租您的木工和我想租您的木工和油漆工一用。咋样？价油漆工一用。咋样？价格嘛格嘛好说，肯定不好说，肯定不会让您兄弟吃亏。会让您兄弟吃亏。王老板

3、做家王老板做家具赚了大钱，具赚了大钱，可惜我老李可惜我老李有高科技产有高科技产品，却苦于品，却苦于没有足够的没有足够的木工和油漆木工和油漆工咋办？只工咋办？只有租咯。有租咯。Hi：王老板，听：王老板，听说近来家具生意说近来家具生意好呀，也帮帮兄好呀，也帮帮兄弟我哦弟我哦!家具生意还真赚钱，家具生意还真赚钱，但是现在的手机生但是现在的手机生意这么好，不如干意这么好，不如干脆把我的木工和油脆把我的木工和油漆工租给他，又能漆工租给他，又能收租金又可做生意。收租金又可做生意。价格嘛价格嘛好商量，好商量，好商量。只好商量。只是是.王王 老老 板板李李 老老 板板引例引例1对偶问题的提出对偶问题的提出-6

4、-运筹学 王老板王老板家具厂木器车间生产木门与木家具厂木器车间生产木门与木窗两种产品。窗两种产品。加工木门收入为加工木门收入为5656元元/扇，扇，加工木窗收入为加工木窗收入为3030元元/扇扇。生产一扇木。生产一扇木门需要门需要木工木工4 4小时小时，油漆工油漆工2 2小时小时；生；生产一扇木窗需要产一扇木窗需要木工木工3 3小时小时，油漆工油漆工1 1小时小时；该车间每日可用；该车间每日可用木工总工时为木工总工时为120120小时，油漆工总工时为小时，油漆工总工时为5050小时小时。该车间应如何安排生产才能使该车间应如何安排生产才能使每日收每日收入最大入最大？王王 老老 板板-7-运筹学

5、解：设该车间每日安排生产木门解：设该车间每日安排生产木门x x1 1扇，木窗扇，木窗x x2 2扇，则数学模型为扇，则数学模型为-8-运筹学 设用设用y1,y2分别表示付给木工和油漆工的价格。王老板分别表示付给木工和油漆工的价格。王老板在做定价决策时在做定价决策时,作如下比较：若用作如下比较：若用4个小时木工和个小时木工和2个个小时油漆工可以生产一扇木门小时油漆工可以生产一扇木门,可获利可获利56元元,那么付给加那么付给加工木门的木工和油漆工的价格应不低于加工一扇木门工木门的木工和油漆工的价格应不低于加工一扇木门的利润的利润,这就有这就有同理付给加工木窗的木工和油漆工的价格应不低于加同理付给加

6、工木窗的木工和油漆工的价格应不低于加工一扇木窗的利润工一扇木窗的利润,这就有这就有把每日可用木工和油漆工的总工时出让把每日可用木工和油漆工的总工时出让,其总收入为其总收入为只能在满足只能在满足所有产品的利润的条件所有产品的利润的条件下下,其总收入尽可能少其总收入尽可能少,才能成交才能成交.-9-运筹学 王老板的王老板的家具生产模型家具生产模型：x1、x2是木门、木窗生产量。是木门、木窗生产量。Z是家具销售总收入。是家具销售总收入。max Z=56x1+30 x2s.t.4x1+3x2 120（木工）（木工）2x1+x2 50（油漆工）（油漆工）x1，x2 0原始线性规划问题，记为原始线性规划问

7、题，记为（P）王老板的王老板的资源出租模型资源出租模型：y1、y2木、油漆工出租价格。木、油漆工出租价格。W是资源出租租金总收入。是资源出租租金总收入。min W=120y1+50y2s.t.4y1+2y2 56 3y1+y2 30 y1，y2 0对偶线性规划问题，记为对偶线性规划问题，记为（D）1.所得不得低于生产的获利（不吃亏原则）所得不得低于生产的获利（不吃亏原则）2.要使对方能够接受（竞争性原则）要使对方能够接受（竞争性原则）两个原则两个原则对偶问题的提出对偶问题的提出-10-运筹学 王老板按（王老板按（D）的解）的解 y1、y2出租其出租其拥拥有的木、漆工有的木、漆工资资源，源，既保

8、既保证证了自己不吃了自己不吃亏亏（出租（出租资资源的租金收入并不低于自己生源的租金收入并不低于自己生产时产时的的销销售收入），又使得出租价格售收入），又使得出租价格对对李老板有极大的吸引李老板有极大的吸引力（李老板所付出的力（李老板所付出的总总租金租金W最少）。最少）。按时下最流行的一个词，叫什么来着按时下最流行的一个词，叫什么来着按时下最流行的一个词，叫什么来着按时下最流行的一个词，叫什么来着对偶问题的提出对偶问题的提出-11-运筹学 Max Z=1500 x1+2500 x2 3x1+2x2 65 2x1+x2 40 3x2 75 x1，x2 0s.t目标函数目标函数约束条件约束条件设三种

9、资源的使用单价分别为设三种资源的使用单价分别为 y1,y2,y3y1 y2 y3生产单位产品甲的资源消耗所得不少于单位产品甲的获利生产单位产品甲的资源消耗所得不少于单位产品甲的获利生产单位产品乙的资源消耗所得不少于单位产品乙的获利生产单位产品乙的资源消耗所得不少于单位产品乙的获利3y1+2 y2 1500 2y1+y2+3y3 2500甲甲乙乙设备能力设备能力A3265B2140C0375获利获利15002500通过使用所有设备对外利用所获得的收益通过使用所有设备对外利用所获得的收益W=65y1+40 y2+75y3对偶问题的提出对偶问题的提出-12-运筹学 根据原则根据原则2，对方能够接受的

10、价格显然是越低越，对方能够接受的价格显然是越低越好，因此此问题可归结为以下数学模型：好，因此此问题可归结为以下数学模型：Min W=65y1+40 y2+75y3 3y1+2y2 15002y1+y2+3y3 2500y1,y2,y3 0s.t目标函目标函数数约束条约束条件件原线性规划问题称为原线性规划问题称为原问题原问题，此问题为此问题为对偶问题对偶问题，y1,y2,y3为为对偶变量对偶变量，也称为，也称为影子价格影子价格对偶问题的提出对偶问题的提出-13-运筹学 2.4 线性规划的对偶理论-14-运筹学 Max Z=1500 x1+2500 x2 3x1+2x2 65 2x1+x2 40

11、3x2 75 x1，x2 0s.t原问题原问题（对偶问题）（对偶问题）对偶问题对偶问题（原问题）（原问题）一、一、一、一、原问题与对偶问题的对应关系原问题与对偶问题的对应关系原问题与对偶问题的对应关系原问题与对偶问题的对应关系Min W=65y1+40 y2+75y33y1+2y2 15002y1+y2+3y3 2500y1,y2,y3 0s.t（y1）（y2）（y3）（x1）3201500（x2）2102500654075min max z 3 3个约束个约束2 2个变量个变量2 2个约束个约束 3 3个变量个变量线性规划的对偶理论线性规划的对偶理论-15-运筹学 对偶问题的形式对偶问题的形

12、式定义定义 设原线性规划问题为设原线性规划问题为 则称下列线性规划问题则称下列线性规划问题l为其对偶问题，其中为其对偶问题，其中yi(i=1,2,m)称为称为对偶变量对偶变量l上述对偶问题称为上述对偶问题称为对称型对称型对称型对称型对偶问题对偶问题l原问题简记为原问题简记为(P)，对偶问题简记为，对偶问题简记为(D)称问题称问题(P)和和(D)为为一对对偶问题一对对偶问题线性规划的对偶理论线性规划的对偶理论-16-运筹学 对称型问题的对偶规则对称型问题的对偶规则1、给每个原始约束条件定义一个非负对偶变量、给每个原始约束条件定义一个非负对偶变量yi(i=1,2,m)；2、使原问题的目标函数系数、

13、使原问题的目标函数系数 cj 变为其对偶问题约束条变为其对偶问题约束条 件的右端常数；件的右端常数；3、使原问题约束条件的右端常数、使原问题约束条件的右端常数 bi 变为其对偶问题目变为其对偶问题目 标函数的系数；标函数的系数；4、将原问题约束条件的系数矩阵转置，得到其对偶问、将原问题约束条件的系数矩阵转置，得到其对偶问 题约束条件的系数矩阵；题约束条件的系数矩阵；5、改变约束问题不等号的方向，即将、改变约束问题不等号的方向，即将“”改为改为“”；6、原问题为、原问题为“max”型，对偶问题为型，对偶问题为“min”型。型。线性规划的对偶理论线性规划的对偶理论-17-运筹学 原始原始问题问题M

14、ax Z=CXs.t.AXbX 0bACMaxnm对偶问题对偶问题Min W=Ybs.t.YACY 0MinCATbnmY为行向量为行向量线性规划的对偶理论线性规划的对偶理论-18-运筹学 当原问题为求极小值时，对偶问题为求极大值。当原问题为求极小值时，对偶问题为求极大值。原始问题中目标函数的系数变成对偶问题中约束条原始问题中目标函数的系数变成对偶问题中约束条件的右端；原始问题中约束条件的右端变成对偶问件的右端；原始问题中约束条件的右端变成对偶问题中目标函数的系数。题中目标函数的系数。原始问题约束条件系数矩阵的转置对应对偶问题中原始问题约束条件系数矩阵的转置对应对偶问题中约束条件的系数矩阵。约

15、束条件的系数矩阵。原始问题的约束条件个数决定对偶问题变量的个数；原始问题的约束条件个数决定对偶问题变量的个数；原始问题变量个数，决定对偶问题的约束个数。原始问题变量个数，决定对偶问题的约束个数。原始问题的约束方程的匹配形式决定对偶问题变量原始问题的约束方程的匹配形式决定对偶问题变量的符号；原始问题决策变量的符号决定所对应对偶的符号；原始问题决策变量的符号决定所对应对偶问题的约束方程的匹配形式。问题的约束方程的匹配形式。线性规划的对偶理论线性规划的对偶理论-19-运筹学 求线性规划问题的求线性规划问题的对偶规划对偶规划解：由原问题的结构可知为对称型对偶问题解：由原问题的结构可知为对称型对偶问题例

16、例1线性规划的对偶理论线性规划的对偶理论-20-运筹学 求线性规划问题的求线性规划问题的对偶规划对偶规划解：由原问题的结构可知不是对称型对偶问题，可先化为解：由原问题的结构可知不是对称型对偶问题，可先化为对称型，再求其对偶规划。对称型，再求其对偶规划。例例2线性规划的对偶理论线性规划的对偶理论-21-运筹学 求线性规划问题的求线性规划问题的对偶规划对偶规划解：由原问题的结构可知不是对称型对偶问题，可先化为解：由原问题的结构可知不是对称型对偶问题，可先化为对称型，再求其对偶规划。对称型，再求其对偶规划。例例3线性规划的对偶理论线性规划的对偶理论-22-运筹学 上式已为对称型对偶问题，故可写出它的

17、对偶规划上式已为对称型对偶问题，故可写出它的对偶规划令令则上式化为则上式化为线性规划的对偶理论线性规划的对偶理论-23-运筹学 q对偶问题的非对称形式对偶问题的非对称形式min z=2x1+4x2-x3s.t.3x1-x2+2x3 6 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15max w=6y1+12y2+8y3+15y4s.t.3y1-y2+2y3+y4 2 -y1+2y2+y3+3y4 4 2y1-3y2+2y3-y4 -1 y1 0,y2 ,y3 0,y4 0=unr=x10 x20 x3:unr线性规划的对偶理论线性规划的对偶理论-24-运筹学 原

18、问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）约束条件右端项约束条件右端项目标函数变量的系数目标函数变量的系数目标函数变量的系数目标函数变量的系数约束条件右端项约束条件右端项目标函数目标函数 max目标函数目标函数 min约约束束条条件件m个个m个个变变量量00=无约束无约束变变量量n个个n个个约约束束条条件件00无约束无约束=线性规划的对偶理论线性规划的对偶理论-25-运筹学 例例例例2 2 2 2、写出下述线性规划问题的对偶问题、写出下述线性规划问题的对偶问题、写出下述线性规划问题的对偶问题、写出下述线性规划问题的对偶问题解：解：设对偶变量为设对偶变量为mi

19、ns.t.则对偶问题为则对偶问题为-26-运筹学【例例2.5】写出下列线性规划的对偶问题写出下列线性规划的对偶问题【解解】目目标标函函数数求求最最小小值值，应应将将表表21的的右右边边看看作作原原问问题题，左左边边是是对对偶偶问问题题，原原问问题题有有3个个约约束束4个个变变量量，则则对对偶偶问问题题有有3 个个变变量量4个个约约束束，对对照照表表21的对应关系，对偶问题为：的对应关系，对偶问题为：写出下列线性规写出下列线性规划的对偶问题划的对偶问题.-27-运筹学 性质性质1 对称性定理对称性定理：对偶问题的对偶是原问题：对偶问题的对偶是原问题 min W=Y bs.t.YA C Y 0ma

20、x Z=C Xs.t.AXb X 03.2 对偶问题的基本性质对偶问题的基本性质线性规划的对偶理论线性规划的对偶理论-28-运筹学 min z=-CXs.t.-AX-bX 0maxw=-Ybs.t.-YA-C Y 0min w=Ybs.t.YAC Y 0max z=CXs.t.AXb X 0对偶的对偶的定义定义对偶的对偶的定义定义简要证明：简要证明：线性规划的对偶理论线性规划的对偶理论-29-运筹学 性质性质2 弱对偶原理弱对偶原理(弱对偶性弱对偶性)：设设 和和 分分别是问题别是问题(P)和和(D)的可行解，则必有的可行解，则必有线性规划的对偶理论线性规划的对偶理论-30-运筹学 推论推论1

21、:原问题任一可行解的目标函数值是其对偶问原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之，对偶问题任意可行解题目标函数值的下界；反之，对偶问题任意可行解的目标函数值是其原问题目标函数值的上界。的目标函数值是其原问题目标函数值的上界。证明：证明：(1)当当X和和Y为原问题和对偶问题的一个可行解为原问题和对偶问题的一个可行解有有原问题目标函原问题目标函数值数值对偶问题目标函对偶问题目标函数值数值线性规划的对偶理论线性规划的对偶理论-31-运筹学 推论推论2:在一对对偶问题（在一对对偶问题（P）和（）和（D）中，若其中）中，若其中一个问题可行但目标函数无界，则另一个问题无可一个问题可行

22、但目标函数无界，则另一个问题无可行解；行解；反之不成立反之不成立。这也是对偶问题的这也是对偶问题的无界性无界性无界性无界性。若（若（P）为无界解，则（）为无界解，则（D）无可行解；）无可行解；若（若（D）为无界解，则（）为无界解，则（P）无可行解。）无可行解。线性规划的对偶理论线性规划的对偶理论推论推论3：在一对对偶问题（在一对对偶问题（P）和（）和（D）中，若一个）中，若一个可行（如可行（如P），而另一个不可行（如），而另一个不可行（如D），则该可行），则该可行的问题目标函数值无界。的问题目标函数值无界。-32-运筹学 利用对偶性质判断下面问题有无最优解利用对偶性质判断下面问题有无最优解例例

23、3.6解：此问题的对偶问题为解：此问题的对偶问题为不能成立，因此对偶问不能成立，因此对偶问题不可行。故由推论题不可行。故由推论3知知原问题无界。原问题无界。为可行解为可行解线性规划的对偶理论线性规划的对偶理论-33-运筹学 课堂练习课堂练习 利用对偶性质判断下面问题有无最优解利用对偶性质判断下面问题有无最优解解：此问题的对偶问题为解：此问题的对偶问题为不能成立，因此对偶问不能成立，因此对偶问题不可行。故由推论题不可行。故由推论3知知原问题无界。原问题无界。为可行解为可行解线性规划的对偶理论线性规划的对偶理论-34-运筹学 性质性质3 最优性定理：最优性定理：如果如果 是原问题的可行是原问题的可

24、行解，解，是其对偶问题的可行解，则是其对偶问题的可行解，则:当且仅当当且仅当 是原问题的最优解，是原问题的最优解，是其对偶问题的最优解。是其对偶问题的最优解。线性规划的对偶理论线性规划的对偶理论-35-运筹学 性质性质4 强对偶性：强对偶性：若一对对偶问题中的任意一若一对对偶问题中的任意一个有最优解，则另一个也有最优解，且目标个有最优解，则另一个也有最优解，且目标函数最优值相等。函数最优值相等。性质性质5 无界解定理无界解定理：若原问题（对偶问题）的解为无界若原问题（对偶问题）的解为无界解，则其对偶问题（原问题）无可行解，则其对偶问题（原问题）无可行解。解。线性规划的对偶理论线性规划的对偶理论

25、-36-运筹学 性质性质6 互补松弛性互补松弛性：设设X*和和Y*分别是分别是P问题问题 和和 D问问题题 的可行解，则它们分别是的可行解，则它们分别是最优解的充要条件最优解的充要条件是：是：其中：其中：Xs、Ys为松弛变量为松弛变量。在线性规划问题的最优解中，若对应某一约束条件的在线性规划问题的最优解中，若对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式对偶变量值为非零，则该约束条件取严格等式；另一另一方面，如果约束条件取严格不等式，则其对应的方面，如果约束条件取严格不等式，则其对应的对偶对偶变量一定为零。变量一定为零。线性规划的对偶理论线性规划的对偶理论-37-运筹学 证证:(:

26、(必要性）必要性）原问题原问题 对偶问题对偶问题线性规划的对偶理论线性规划的对偶理论-38-运筹学 Max Z=CXs.t.AX+XS=bX,XS 0Min W=Ybs.t.YA-YS=CW,WS 0XTYS=0YTXS=0mn=YYSAT-ICn=AXSIbnmmX原始问题和对偶问题变量、松弛变量的维数原始问题和对偶问题变量、松弛变量的维数线性规划的对偶理论线性规划的对偶理论-39-运筹学 y1 yi ym ym+1 ym+j yn+m x1 xj xn xn+1 xn+i xn+m 对偶问题的变量对偶问题的变量 对偶问题的松弛变量对偶问题的松弛变量 原始问题的变量原始问题的变量 原始问题的

27、松弛变量原始问题的松弛变量xjym+j=0yixn+i=0(i=1,2,m;j=1,2,n)在一对变量中，其中一个大于在一对变量中，其中一个大于0，另一个一定等于，另一个一定等于0线性规划的对偶理论线性规划的对偶理论-40-运筹学 性质性质5的应用：的应用：该性质给出了已知一个问题最优解求另一个问题该性质给出了已知一个问题最优解求另一个问题最优解的方法，即已知最优解的方法，即已知Y求求X或已知或已知X求求Y互补松弛条件互补松弛条件由于变量都非负，要使求和式等于零，则必定每一分由于变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：量为零，因而有下列关系：若若Y0，则，则Xs必为必

28、为0；若；若X0，则，则Ys必为必为0利用上述关系，建立对偶问题（或原问题）的约束线利用上述关系，建立对偶问题（或原问题）的约束线性方程组，方程组的解即为最优解。性方程组，方程组的解即为最优解。线性规划的对偶理论线性规划的对偶理论-41-运筹学 已知线性规划已知线性规划 的对偶问题的最优解为的对偶问题的最优解为Y=(0,-2)，求原问题的最优解。，求原问题的最优解。解解:对偶问题是对偶问题是标准化标准化例例3.7线性规划的对偶理论线性规划的对偶理论-42-运筹学 设原问题最优解为设原问题最优解为X(x1，x2，x3)T,由互补松弛性定由互补松弛性定理知，理知，X和和 Y满足：满足：将将Y带入由

29、方程可知，带入由方程可知，y3y50，y41。y2=-20 x50又又y4=10 x20将将x2，x5带入原问题约束方程中，得：带入原问题约束方程中，得：解方程组得：解方程组得：x1=-5,x3=-1,所以原问题的最优解为所以原问题的最优解为X=(-5,0,-1)，最优值，最优值z=-12线性规划的对偶理论线性规划的对偶理论-43-运筹学 试用对偶原理求解线性规划问题试用对偶原理求解线性规划问题已知其对偶规划的最优解为已知其对偶规划的最优解为练习练习线性规划的对偶理论线性规划的对偶理论-44-运筹学 解：解：该问题的对偶规划为该问题的对偶规划为线性规划的对偶理论线性规划的对偶理论-45-运筹学

30、 代入对偶规划的约束条件得代入对偶规划的约束条件得将最优解将最优解线性规划的对偶理论线性规划的对偶理论设原问题的最优解为设原问题的最优解为-46-运筹学 XBXNXs0CN-CBb-1N-CBB-1Ys1-Ys2-Y其中，其中，Ys1是是对应对应于原于原问题问题中基中基变变量量XB的剩余的剩余变变量，量，Ys2是是对应对应于原于原问题问题中非基中非基变变量量XN的剩余的剩余变变量。量。-47-运筹学 证证明：明：设设B是原始是原始问题问题的一个可行基，于是的一个可行基，于是A=(B,N)；原；原问题问题及其及其对对偶偶问题问题可改写可改写为为这里有这里有Ys(Ys1,Ys2)。当求得原当求得原

31、问题问题的一个解的一个解XBB-1b，XN和和Xs的的检验检验数分数分别为别为：CN-CBB-1N,-CBB-1。-48-运筹学 分析分析XN和和Xs的的检验检验数数CN-CBB-1N和和-CBB-1与与对对偶偶问题问题的解之的解之间间的关系。的关系。令令Y CBB-1，将其，将其带带入入对对偶偶问题问题的的资资源源约约束束，可得可得命命题题得得证证。-49-运筹学 Max Z=40 x1+50 x2 x1+2x2 303x1+2x2 60 2x2 24 x1,x2 0 0s.ty1y2y3Min W=30y1+60y2+24y3 y1+3y2+0y3 402y1+2y2+2y3 50 y1,

32、y2,y3 0 0s.tMax W=-30y1-60y2-24y3 y1+3y2+0y3 y4=402y1+2y2+2y3 y5=50 y1,y2,y3,y4,y5 0 0s.t举例说明举例说明线性规划的对偶理论线性规划的对偶理论-50-运筹学 Max W=-30y1-60y2-24y3+0(y4+y5)-M(y6+y7)y1+3y2+0y3 y4+y6=402y1+2y2+2y3 y5+y7=50 y1,y2,y3,y4,y5 0 0s.tcj-30-60-2400-M-MB-1bcByBy1y2y3y4y5y6y7-My6130-10104040/3-My72220-1015050/2j3

33、M-305M-602M-24-M-M00-90M线性规划的对偶理论线性规划的对偶理论-51-运筹学 cj-30-60-2400-M-MB-1bcByBy1y2y3y4y5y6y7-60y21/310-1/301/3040/3-My74/3022/3-1-2/3170/335/3j4M/3-1002M-242M/3+20-M-5M/3+200800-70M/3-60y21/310-1/301/3040/340-24y32/3011/3-1/2-1/31/235/335/2j600-12-12-M+12-M+12-1080-60y201-1/2-1/21/41/2-1/415/2-30y1103/

34、21/2-3/4-1/23/435/2j00-9-15-15/2-M+30-M-15/2-975-52-运筹学 cj4050000 B-1bcBxBx1x2x3x4x540 x1101/2-1/20150 x5003/2-1/21950 x201-3/41/4015/2j00-35/2-15/20975 Max Z=40 x1+50 x2 x1+2x2 303x1+2x2 60 2x2 24 x1,x2 0 0s.t x1+2x2+x3=303x1+2x2+x4=60 2x2+x5=24 x1 x5 0 0s.t线性规划的对偶理论线性规划的对偶理论-53-运筹学 线性规划的对偶理论线性规划的对

35、偶理论-54-运筹学 原问题与其对偶问题的变量与解的对应关系：原问题与其对偶问题的变量与解的对应关系：在单纯形表中，原问题的松弛变量对应在单纯形表中，原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量。原问题的变量。线性规划的对偶理论线性规划的对偶理论-55-运筹学 XBb原问题的变量原问题的变量原问题的松弛变量原问题的松弛变量x1x2x3x4x5x115101/2-1/20 x59003/2-1/21x215/2013/4-1/4000-35/2-15/20YBb对偶问题对偶问题的变量的变量对偶问题的对偶问题的剩余变量剩余变量y1y2

36、y3y4y5y215/201-1/2-1/21/4y135/2103/21/2-3/400-9-15-15/2原问原问题最题最优表优表对偶对偶问题问题最优最优表表-56-运筹学 对偶规划可以用线性规划的单纯形法求解。对偶规划可以用线性规划的单纯形法求解。由对偶原理可见，原问题与对偶问题之间有紧密联由对偶原理可见，原问题与对偶问题之间有紧密联系，因此我们能够通过求解原问题来找出对偶问题系，因此我们能够通过求解原问题来找出对偶问题的解，反之依然。的解，反之依然。互补松弛条件就可以解决由原问题的最优解直接求互补松弛条件就可以解决由原问题的最优解直接求出对偶问题的最优解。出对偶问题的最优解。对偶问题解

37、的求法对偶问题解的求法线性规划的对偶理论线性规划的对偶理论-57-运筹学 思考题思考题判断下列结论是否正确，如果不正确，应该怎样改正判断下列结论是否正确，如果不正确，应该怎样改正？1）任何）任何线线性性规规划都存在一个划都存在一个对应对应的的对对偶偶线线性性规规划划.2）原）原问题问题第第i个个约约束是束是“”约约束，束，则对则对偶偶变变量量yi0.3）互互为为对对偶偶问问题题，或或者者同同时时都都有有最最优优解解，或或者者同同时时都无最都无最优优解解.4）对对偶偶问题问题有可行解，有可行解，则则原原问题问题也有可行解也有可行解.5）原）原问题问题有多重解，有多重解，对对偶偶问题问题也有多重解

38、也有多重解.6）对对偶偶问问题题有有可可行行解解，原原问问题题无无可可行行解解，则则对对偶偶问问题题具有无界解具有无界解.7）原）原问题问题无最无最优优解，解，则对则对偶偶问题问题无可行解无可行解.-58-运筹学 8）对对偶偶问题问题不可行，原不可行，原问题问题可能无界解可能无界解.9）原）原问题问题与与对对偶偶问题问题都可行，都可行，则则都有最都有最优优解解.10）原）原问题问题具有无界解，具有无界解，则对则对偶偶问题问题不可行不可行.11）对对偶偶问题问题具有无界解，具有无界解，则则原原问题问题无最无最优优解解.12）若若X*、Y*是是原原问问题题与与对对偶偶问问题题的的最最优优解解，则则X*=Y*.