《管理运筹学第3章线性规划的对偶问题》由会员分享，可在线阅读，更多相关《管理运筹学第3章线性规划的对偶问题（37页珍藏版）》请在金锄头文库上搜索。
1、管理运筹学管理运筹学第第3 3章章李存芳李存芳李存芳李存芳 博士博士博士博士/ /教授教授教授教授/ /硕士生导师硕士生导师硕士生导师硕士生导师研究领域：战略研究领域：战略研究领域：战略研究领域：战略管理、组织行为、运营管理管理、组织行为、运营管理讲授课程：讲授课程：讲授课程：讲授课程：管理运筹学、管理系统工程、运营管理管理运筹学、管理系统工程、运营管理 经济学经济学单单单单 位：位：位：位：江苏师范大学商学院江苏师范大学商学院 物流管理系物流管理系 E-mail E-mail：2021/3/242021/3/241 1授授课课：XXXXXXOR:SM第第 3 章章 线性规划的对偶问题线性规划
2、的对偶问题Sub titleSub title内容提要2021/3/242授课：XXXOR:SM 每一个线性规划问题都有一个与之相伴随的另一个问题。每一个线性规划问题都有一个与之相伴随的另一个问题。这两个问题：一是，在数学模型上有着对应关系；二是，从这两个问题：一是，在数学模型上有着对应关系；二是，从一个问题的最优解完全可以得出另一个问题最优解的全部信一个问题的最优解完全可以得出另一个问题最优解的全部信息。息。3.1.1 3.1.1 问题的提出问题的提出 例例1 引入一个资源价格问题。引入一个资源价格问题。3-1 线性规划的对偶理论线性规划的对偶理论2021/3/243授课：XXXOR:SM
3、类类类类似似似似于于于于第第第第2 2 2 2章章章章例例例例1 1 1 1的的的的生生生生产产产产计计计计划划划划问问问问题题题题。某某企企业业生生产产甲甲、乙乙两两种种产产品品，需需消消耗耗A A、B B、C C三三种种材材料料。据据市市场场分分析析，单单位位甲甲、乙乙产产品品的的销销售售收收益益分分别别为为4 4万万元元和和5 5万万元元。单单位位甲甲、乙乙产产品品对对材材料的消耗量及材料的供应量如表料的消耗量及材料的供应量如表3.13.1所示。所示。 原问题：原问题：应如何制定生产计划，使总收益为最大。应如何制定生产计划，使总收益为最大。 表表3.13.1 产品材料 甲乙供应量供应量A
4、1145B2180C1390收益收益4万元万元/单甲单甲5万元万元/单乙单乙2021/3/244授课：XXXOR:SM运用单纯形法，可求得其最优解为：运用单纯形法，可求得其最优解为：运用单纯形法，可求得其最优解为：运用单纯形法，可求得其最优解为：设计划安排：设计划安排：x x1 1为甲产品的产量，为甲产品的产量， x x2 2为乙产品的产量。（决策变量）为乙产品的产量。（决策变量）则，该问题的数学模型为：则，该问题的数学模型为：2021/3/245授课：XXXOR:SM新问题：新问题：现在从另一角度来讨论这个问题。现在从另一角度来讨论这个问题。 假设该企业经过市场预测，准备进行转产，且把现有三
5、假设该企业经过市场预测，准备进行转产，且把现有三种材料进行转让，也恰好有一个制造商急需这批材料。于是种材料进行转让，也恰好有一个制造商急需这批材料。于是买卖双方开始对资源的出让价格问题进行磋商，希望寻找一买卖双方开始对资源的出让价格问题进行磋商，希望寻找一个双方都认为比较满意的合理价格。个双方都认为比较满意的合理价格。 分析：分析：设设A、B、C三种材料的单价分别为三种材料的单价分别为y1、y2、y3. 对于卖方来说，对于卖方来说，生产单位甲产品所获收益为生产单位甲产品所获收益为4万元，为保万元，为保证其总收入不少于证其总收入不少于405/2万元，则将生产单位甲产品所需资源万元，则将生产单位甲
6、产品所需资源转让出去，该企业的收入不能少于转让出去，该企业的收入不能少于4万元。故万元。故y1、y2、y3必须必须满足约束条件：满足约束条件： y1+2y2+y34 同样，将生产单位乙产品所需的资源转让出去，其收入同样，将生产单位乙产品所需的资源转让出去，其收入不能少于生产单位乙产品的收益不能少于生产单位乙产品的收益5万元，所以万元，所以y1、y2、y3还必还必须满足约束条件：须满足约束条件： y1+y2+3y352021/3/246授课：XXXOR:SM 对于买方来说，对于买方来说，他希望在满足上述约束条件下使总的他希望在满足上述约束条件下使总的支出支出 W（y） =45y1+80y2+90
7、y3 达到最小。达到最小。 综上所述，资源价格问题的数学模型可描述为：综上所述，资源价格问题的数学模型可描述为： 上述两个模型（上述两个模型（3-1）和（）和（3-2）是对同一问题的两种不）是对同一问题的两种不同考虑的数学描述，其间有着一定的内在联系，将逐一剖同考虑的数学描述，其间有着一定的内在联系，将逐一剖析。析。2021/3/247授课：XXXOR:SM首先，分析这两个模型之间的对应关系：首先，分析这两个模型之间的对应关系： （1 1）一个问题的目标函数为极大化，约束条件为）一个问题的目标函数为极大化，约束条件为“”类类型，另一个问题的目标为极小化，约束条件为型，另一个问题的目标为极小化，
8、约束条件为“”类型；类型； （2 2）一个问题的变量个数等于另一个问题的约束条件个）一个问题的变量个数等于另一个问题的约束条件个数；数； （3 3）一个问题的右端常数（约束系数）是另一个问题的）一个问题的右端常数（约束系数）是另一个问题的目标函数的系数（成本系数）；目标函数的系数（成本系数）； （4 4）两个问题的系数矩阵互为转置。）两个问题的系数矩阵互为转置。 我们把这种对应关系称为我们把这种对应关系称为对偶关系对偶关系。如果把（。如果把（3-13-1）称为）称为原始问题，则（原始问题，则（3-23-2）称为对偶问题。）称为对偶问题。2021/3/248授课：XXXOR:SM3.1.2 3.
9、1.2 对称型线性规划问题对称型线性规划问题对称型对偶问题对称型对偶问题 每一个线性规划问题都必然有与之相伴随的对偶问每一个线性规划问题都必然有与之相伴随的对偶问题存在。先讨论对称型对偶问题；对于非对称型对偶问题存在。先讨论对称型对偶问题；对于非对称型对偶问题，可以先转化为对称型，然后再进行分析，也可以直题，可以先转化为对称型，然后再进行分析，也可以直接从非对称型进行分析。接从非对称型进行分析。 对称型线性规划问题对称型线性规划问题数学模型的一般形式为数学模型的一般形式为Y1Y2ym2021/3/249授课：XXXOR:SM这种模型的特点是：这种模型的特点是： （1 1）目标函数是最大化类型）
10、目标函数是最大化类型( (或是最小化类型或是最小化类型) )； （2 2）所有约束条件都是）所有约束条件都是“”“”型（或都是型（或都是“”型）；型）； （3 3）所有决策变量都是非负的。）所有决策变量都是非负的。 如果把（如果把（3-33-3）作为原始问题，根据原始与对偶问题）作为原始问题，根据原始与对偶问题的对应关系可得（的对应关系可得（3-33-3）的对偶问题为）的对偶问题为2021/3/2410授课：XXXOR:SM用矩阵表示的原始问题（用矩阵表示的原始问题（3-33-3）和对偶问题（）和对偶问题（3-43-4）为）为其中其中Y=Y=（y y1 1,y,y2 2,y,ym m）, ,其
11、它同前其它同前。3.1.3 3.1.3 一般问题的对偶问题一般问题的对偶问题非对称型对偶问题非对称型对偶问题 线性规划有时以非对称型出现，那么如何从原始问题写线性规划有时以非对称型出现，那么如何从原始问题写出它的对偶问题呢？出它的对偶问题呢？2021/3/2411授课：XXXOR:SM解：（解：（解：（解：（1 1）首先把上述非对称型问题化为首先把上述非对称型问题化为首先把上述非对称型问题化为首先把上述非对称型问题化为对称型对称型对称型对称型问题问题问题问题。 在第一个约束条件的两边同在第一个约束条件的两边同在第一个约束条件的两边同在第一个约束条件的两边同（-1-1-1-1） 把第三个约束方程
12、分解成两个把第三个约束方程分解成两个把第三个约束方程分解成两个把第三个约束方程分解成两个 x x x x1 1 1 1-x-x-x-x2 2 2 2+3x+3x+3x+3x3 3 3 30000和和和和 x x x x1 1 1 1-x-x-x-x2 2 2 2+3x+3x+3x+3x3 3 3 30 0 0 0 再将后一个两边同再将后一个两边同再将后一个两边同再将后一个两边同（-1-1-1-1）改写成）改写成）改写成）改写成 -x -x -x -x1 1 1 1+x+x+x+x2 2 2 2-3x-3x-3x-3x3 3 3 30 0 0 0 例例1 写出下列线性规划的对偶问题写出下列线性规
13、划的对偶问题2021/3/2412授课：XXXOR:SM 转换成转换成对称型对称型（2 2）写出相应的对偶问题（）写出相应的对偶问题（）写出相应的对偶问题（）写出相应的对偶问题（4 4个约束，分别对应个约束，分别对应个约束，分别对应个约束，分别对应4 4个对偶变量个对偶变量个对偶变量个对偶变量y y1 1、y y2 2、y y/ /3 3、y y/ /3 3）Y1Y2Y/3y/32021/3/2413授课：XXXOR:SM再设再设y y/ /3 3-y-y/3 3=y=y3 3，代入上述模型得，代入上述模型得：2021/3/2414授课：XXXOR:SM解：（解：（解：（解：（1 1）首先把上
14、述非对称型问题化为首先把上述非对称型问题化为首先把上述非对称型问题化为首先把上述非对称型问题化为对称型对称型对称型对称型问题问题问题问题。 在第一个约束条件的两边同在第一个约束条件的两边同在第一个约束条件的两边同在第一个约束条件的两边同（-1-1-1-1） 把第三个约束方程分解成两个把第三个约束方程分解成两个把第三个约束方程分解成两个把第三个约束方程分解成两个 x x x x1 1 1 1-x-x-x-x2 2 2 2+3x+3x+3x+3x3 3 3 30000和和和和 x x x x1 1 1 1-x-x-x-x2 2 2 2+3x+3x+3x+3x3 3 3 30 0 0 0 再将后一个
15、两边同再将后一个两边同再将后一个两边同再将后一个两边同（-1-1-1-1）改写成）改写成）改写成）改写成 -x -x -x -x1 1 1 1+x+x+x+x2 2 2 2-3x-3x-3x-3x3 3 3 30000例例2 2 将例将例1 1模型中的模型中的x x2 2改为无非负约束变量，即模型为改为无非负约束变量，即模型为写出其对偶问题写出其对偶问题2021/3/2415授课：XXXOR:SM 令令x2=x/ /2-x/ /2. .其中其中x/ /2,x/ /20 转换成转换成对称型对称型（2 2）写出相应的对偶问题（）写出相应的对偶问题（）写出相应的对偶问题（）写出相应的对偶问题（4 4
16、个约束，分别对应个约束，分别对应个约束，分别对应个约束，分别对应4 4个对偶变量个对偶变量个对偶变量个对偶变量y y1 1、y y2 2、y y/ /3 3、y y/ /3 3）Y1Y2Y/3y/32021/3/2416授课：XXXOR:SM令令令令y y y y/ / / /3 3 3 3-y-y-y-y/3 3 3 3=y=y=y=y3 3 3 3, , , ,并将第二和第三个条件合并为方程，得并将第二和第三个条件合并为方程，得并将第二和第三个条件合并为方程，得并将第二和第三个条件合并为方程，得2021/3/2417授课：XXXOR:SM 综合上述两个例子，可以看出，线性规划与其对偶模型综
17、合上述两个例子，可以看出，线性规划与其对偶模型的关系有了新的拓展：的关系有了新的拓展： （1 1）一个问题的目标函数为极大化，约束条件为）一个问题的目标函数为极大化，约束条件为“”或或“=”“=”类型，另一个问题的目标为极小化，约束条件为类型，另一个问题的目标为极小化，约束条件为“”或或“=”“=”类型；类型； （2 2）一个问题的变量个数等于另一个问题的约束条件个）一个问题的变量个数等于另一个问题的约束条件个数；数； （3 3）一个问题的右端常数（约束系数）是另一个问题的）一个问题的右端常数（约束系数）是另一个问题的目标函数的系数（成本系数）；目标函数的系数（成本系数）； （4 4）两个问题
18、的系数矩阵互为转置）两个问题的系数矩阵互为转置; ; （5 5）一个问题的第）一个问题的第i i个约束为个约束为“=”“=”，则另一个问题的第，则另一个问题的第i i个变量为个变量为“无非负约束变量无非负约束变量”（自由变量）。反之，一个问（自由变量）。反之，一个问题的第题的第i i个变量为个变量为“无非负约束变量无非负约束变量”，则另一个问题的第，则另一个问题的第i i个约束为个约束为“=”“=”（方程）。（方程）。2021/3/2418授课：XXXOR:SM 关于线性规划的原始问题与对偶问题的对应关系可归纳关于线性规划的原始问题与对偶问题的对应关系可归纳关于线性规划的原始问题与对偶问题的对
19、应关系可归纳关于线性规划的原始问题与对偶问题的对应关系可归纳成下表成下表成下表成下表3.23.23.23.2原始问题原始问题(或对偶问题或对偶问题)对偶问题对偶问题(或原问题或原问题) 目标目标 max 目标目标 min 变量变量 n个个 约束约束 n个个 变量变量 0 0 无非负约束无非负约束 约束约束 =（方程）（方程） 约束约束 m个个 变量变量 m个个 约束约束 = （方程）（方程） 变量变量 0 0 无非负约束无非负约束系数矩阵系数矩阵bc转置转置cb2021/3/2419授课：XXXOR:SM 这样对于任意给定的一个线性规划问题，均可依据上述这样对于任意给定的一个线性规划问题，均可
20、依据上述对应关系对应关系直接写出其对偶问题模型直接写出其对偶问题模型，而无须先化成对称型。，而无须先化成对称型。例例3 3 写出下列线性规划的对偶问题写出下列线性规划的对偶问题解：解：因目标函数为因目标函数为“max”“max”类型，则约束条件应为类型，则约束条件应为“”“”和和“=”“=”类型，故只需改变第三个约束条件的不等号方向，类型，故只需改变第三个约束条件的不等号方向，即有：即有：2021/3/2420授课：XXXOR:SM原问题即为：原问题即为：原问题即为：原问题即为： 这样所有的约束条件均为这样所有的约束条件均为“”和和“=”类型，按前述对应类型，按前述对应关系原则，可写出其对偶问
21、题为：关系原则，可写出其对偶问题为：Y1Y2Y32021/3/2421授课：XXXOR:SM3.1.4 对偶问题的基本性质对偶问题的基本性质设原始问题为：设原始问题为：则其对偶问题为：则其对偶问题为：1 1、对称性定理、对称性定理 对偶问题的对偶是原始问题。对偶问题的对偶是原始问题。 根据对偶规划，很容易写出对偶问题的对偶模型。根据对偶规划，很容易写出对偶问题的对偶模型。2、对偶性定理、对偶性定理 若若原原问问题题有有最最优优解解，那那么么对对偶偶问问题题也也有有最最优优解解，而而且且两两者者的的目目标函数值相等。标函数值相等。2021/3/2422授课：XXXOR:SM3.1.5 对偶问题的
22、最优解对偶问题的最优解重要推论：重要推论： 1. 1.原始问题单纯形表中松驰变量的检验数恰好对应着对原始问题单纯形表中松驰变量的检验数恰好对应着对偶问题的一个解。偶问题的一个解。 2. 2.原始问题单纯形表中原始问题单纯形表中, ,原始问题的松弛变量的检验数对原始问题的松弛变量的检验数对应于对偶问题的决策变量应于对偶问题的决策变量; ;而原始问题的决策变量的检验数对而原始问题的决策变量的检验数对应于对偶问题的松弛变量应于对偶问题的松弛变量, ,只是只是符号相反符号相反。注意：注意：在两个互为对偶的线性规划问题中，可任选一个进行在两个互为对偶的线性规划问题中，可任选一个进行求解，通常是选择约束条
23、件少的，因求解的工作量主要受到求解，通常是选择约束条件少的，因求解的工作量主要受到约束条件个数的影响。约束条件个数的影响。2021/3/2423授课：XXXOR:SM例例4 求解下列线性规划问题求解下列线性规划问题解：解：该问题仅有两个变量，但约束较多，其对偶问题为该问题仅有两个变量，但约束较多，其对偶问题为Y1Y2Y3Y4Y52021/3/2424授课：XXXOR:SM把上述问题（把上述问题（3-83-8）作为原始问题求解，其最终单纯形表见下）作为原始问题求解，其最终单纯形表见下表（表（3.33.3）由表（由表（3.33.3）得其最优解为：）得其最优解为：例例4 4的最优解可直接从表（的最优
24、解可直接从表（3.33.3）的松弛变量）的松弛变量y y6、y y7的检验数中的检验数中读出，即有：读出，即有： -6 -8 -7 -15 -1 0 0 Y1 y2 y3 y4 y5 Y6 y7-15y41/2 1/2 -1/2 0 1 1/2-1/2 1/2-7y35/2-1/2 3/2 1 0 -3/2 1/2 -3/2 j -2 -5 0 0 -4 -4 -32021/3/2425授课：XXXOR:SM3-2 对偶单纯形法对偶单纯形法 第第一一章章中中的的单单纯纯形形法法，是是从从线线性性规规划划标标准准型型的的一一个个基基本本可可行行解解出出发发，逐逐步步迭迭代代，使使目目标标函函数数
25、值值不不断断改改进进，直直到到取取得得最最优优解解为为止止。在在运运算算过过程程中中，必必须须保保证证解解的的可可行行性性，即即在在单单纯纯形形表表中中，始始终终有有常常数数项项b b/ /00。当当最最优优性性条条件件j j00得得到到满满足时，迭代终止，这时原始问题和对偶问题同时达到最优。足时，迭代终止，这时原始问题和对偶问题同时达到最优。 单单纯纯形形法法的的实实质质保保证证解解的的可可行行性性（常常数数项项b b/ /00）, ,通过逐步迭代，达到最优性条件（通过逐步迭代，达到最优性条件（j j0 0 ）。）。 考考虑虑到到原原始始和和对对偶偶问问题题的的对对称称性性，在在求求解解方方
26、法法上上换换一一角角度度，即即在在运运算算过过程程中中，始始终终保保持持其其对对偶偶问问题题解解的的可可行行性性。也也即即在在单单纯纯形形表表中中，始始终终保保证证最最优优性性条条件件（j j0 0 ），而而原原始始问题的解未必可行（常数项问题的解未必可行（常数项 ）。）。2021/3/2426授课：XXXOR:SM 通通过过逐逐步步迭迭代代，当当b b/ /0 0 时时，终终止止迭迭代代，这这时时原原始始问问题题和和对对偶偶问问题题同同时时达达到到最最优优。这这种种方方法法称称之之为为对对偶偶单单纯形法。纯形法。 对对偶偶单单纯纯形形法法的的实实质质保保证证最最优优性性条条件件（j j00）
27、，通过逐步迭代，达到解的可行性（常数项通过逐步迭代，达到解的可行性（常数项b b/ /0 0 ）。）。2021/3/2427授课：XXXOR:SM 3.2.1 3.2.1 对偶单纯形法的运算步骤对偶单纯形法的运算步骤 单纯形法的运算思路单纯形法的运算思路: :先从非基变量中确定进基变量先从非基变量中确定进基变量, ,再再从基变量中选择出基变量从基变量中选择出基变量( (大进大进-小出小出);); 对偶单纯形法的运算思路对偶单纯形法的运算思路: :先从基变量中确定出基变量先从基变量中确定出基变量, ,再从非基变量中选择进基变量再从非基变量中选择进基变量( (小出小出-小进小进).). 具体计算步
28、骤如下具体计算步骤如下: : (1) (1)根据线性规划模型根据线性规划模型, ,列出初始单纯形表列出初始单纯形表, ,但需保证所有但需保证所有检验数检验数j j0 .0 . (2) (2)检验检验. .若常数项若常数项b b/ /0 ,0 ,则得到最优解则得到最优解, ,停止运算停止运算; ;否则否则转下步转下步. . 2021/3/2428授课：XXXOR:SM (3) (3)基变换基变换: : 确定出基变量。在确定出基变量。在b b/ /列中，将所有负值进行比较，其列中，将所有负值进行比较，其中最小的一个分量所对应的变量为出基变量（中最小的一个分量所对应的变量为出基变量（小出小出）；）；
29、 确定进基变量。根据确定进基变量。根据 ，对应列的非基变量对应列的非基变量x xk k为进基变量为进基变量( (小进小进) )。 迭代运算与检验。以迭代运算与检验。以 为主元素，按单纯形法进为主元素，按单纯形法进行迭代计算，得到新的单纯形表，再返回到（行迭代计算，得到新的单纯形表，再返回到（2 2）检验。）检验。2021/3/2429授课：XXXOR:SM例例7 用对偶单纯形法求线性规划问题用对偶单纯形法求线性规划问题解：首先将问题化成标准型，得解：首先将问题化成标准型，得2021/3/2430授课：XXXOR:SM将约束条件两端（将约束条件两端（-1-1），得），得若令若令Y Y1 1=Y=
30、Y2 2=Y=Y3 3=0=0，得到初始基本解：，得到初始基本解：显然，它是一个初始基本解，但不可行。显然，它是一个初始基本解，但不可行。再将上述模型的有关数字填入单纯形表，得下表再将上述模型的有关数字填入单纯形表，得下表3.43.4。可。可见所有检验数均小于或等于见所有检验数均小于或等于0 0，因此，可用对偶单纯形法，因此，可用对偶单纯形法求解，整个求解过程见表求解，整个求解过程见表3.43.4和表和表3.53.5。cj -45 -80 -90 0 0CBYBb/ Y1 y2 y3 Y4 y50y4 -4 -1 -2 -1 1 00y5 -5 -1 -1 -3 0 1j -45 -80 -9
31、0 0 0后选：小进先选：小出2021/3/2431授课：XXXOR:SM 表表3.5:3.5:原问题最优解：原问题最优解：对偶问题最优解：对偶问题最优解： -45 -80 -90 0 0 Y1 y2 y3 y4 y5 0y4-7/3-2/3 -5/3 0 1 -1/3-90y35/3 1/3 1/3 1 0 -1/3j -15 -50 0 0 -30 -45y17/2 1 5/2 0 -3/2 1/2 -90y31/2 0 -1/2 1 1/2 -1/2 j 0 -25/2 0-45/2 -45/2 先选：小出后选：小进2021/3/2432授课：XXXOR:SM作业作业3.13.1写出线性规划问题的对偶问题写出线性规划问题的对偶问题3.23.2写出下列线性规划问题的对偶问题写出下列线性规划问题的对偶问题2021/3/2433授课：XXXOR:SM2021/3/2434授课：XXXOR:SM3.3已知线性规划问题已知线性规划问题试应用对偶理论证明上述线性规划问题无最优解。试应用对偶理论证明上述线性规划问题无最优解。 2021/3/2435授课：XXXOR:SM3.4利用对偶单纯法求解线性规划问题利用对偶单纯法求解线性规划问题2021/3/2436授课：XXXThank you!2021/3/2437
