管理运筹学第3章线性规划的对偶问题

1、管理运筹学管理运筹学 第第3 3章章 管理、组织行为、运营管理管理、组织行为、运营管理 管理运筹学、管理系统工程、运营管理管理运筹学、管理系统工程、运营管理 经济学经济学 江苏师范大学商学院江苏师范大学商学院 物流管理系物流管理系 OR:SM 整理整理ppt 2 第一节第一节 线性规划的对偶理论线性规划的对偶理论 第二节第二节 对偶单纯形法对偶单纯形法 OR:SM 整理整理ppt 3 每一个线性规划问题都有一个与之相伴随的另一个问题。每一个线性规划问题都有一个与之相伴随的另一个问题。 这两个问题：一是，在数学模型上有着对应关系；二是，从这两个问题：一是，在数学模型上有着对应关系；二是，从 一个

2、问题的最优解完全可以得出另一个问题最优解的全部信一个问题的最优解完全可以得出另一个问题最优解的全部信 息。息。 3.1.1 3.1.1 问题的提出问题的提出 例例1 引入一个资源价格问题。引入一个资源价格问题。 OR:SM 整理整理ppt 4 某企业生产甲、乙两种某企业生产甲、乙两种 产品，需消耗产品，需消耗A A、B B、C C三种材料。据市场分析，单位甲、乙三种材料。据市场分析，单位甲、乙 产品的销售收益分别为产品的销售收益分别为4 4万元和万元和5 5万元。单位甲、乙产品对万元。单位甲、乙产品对 材料的消耗量及材料的供应量如表材料的消耗量及材料的供应量如表3.13.1所示。所示。 原问题

3、：原问题：应如何制定生产计划，使总收益为最大。应如何制定生产计划，使总收益为最大。 表表3.13.1 产品材料 甲乙供应量供应量 A1145 B2180 C1390 收益收益4万元万元/单甲单甲5万元万元/单乙单乙 OR:SM 整理整理ppt 5 12 12 12 12 12 max( )45 45 280 s.t.(31) 390 ,0 Z xxx xx xx xx xx 设计划安排：设计划安排：x x1 1为甲产品的产量，为甲产品的产量， x x2 2为乙产品的产量。（决策变量）为乙产品的产量。（决策变量） 则，该问题的数学模型为：则，该问题的数学模型为： 12 45/ 2,45/ 2 (

4、 )405/ 2 xx Z x OR:SM 整理整理ppt 6 新问题：新问题：现在从另一角度来讨论这个问题。现在从另一角度来讨论这个问题。 假设该企业经过市场预测，准备进行转产，且把现有三假设该企业经过市场预测，准备进行转产，且把现有三 种材料进行转让，也恰好有一个制造商急需这批材料。于是种材料进行转让，也恰好有一个制造商急需这批材料。于是 买卖双方开始对资源的出让价格问题进行磋商，希望寻找一买卖双方开始对资源的出让价格问题进行磋商，希望寻找一 个双方都认为比较满意的合理价格。个双方都认为比较满意的合理价格。 分析：分析：设设A、B、C三种材料的单价分别为三种材料的单价分别为y1、y2、y3

5、. 对于卖方来说，对于卖方来说，生产单位甲产品所获收益为生产单位甲产品所获收益为4万元，为万元，为 保证其总收入不少于保证其总收入不少于405/2万元，则将生产单位甲产品所需资万元，则将生产单位甲产品所需资 源转让出去，该企业的收入不能少于源转让出去，该企业的收入不能少于4万元。故万元。故y1、y2、y3必必 须满足约束条件：须满足约束条件： y1+2y2+y34 同样，将生产单位乙产品所需的资源转让出去，其收入同样，将生产单位乙产品所需的资源转让出去，其收入 不能少于生产单位乙产品的收益不能少于生产单位乙产品的收益5万元，所以万元，所以y1、y2、y3还必还必 须满足约束条件：须满足约束条件

6、： y1+y2+3y35 OR:SM 整理整理ppt 7 对于买方来说，对于买方来说，他希望在满足上述约束条件下使总的他希望在满足上述约束条件下使总的 支出支出 W（y） =45y1+80y2+90y3 达到最小。达到最小。 综上所述，资源价格问题的数学模型可描述为：综上所述，资源价格问题的数学模型可描述为： 123 123 123 123 min( )458090 24 s.t.35(32) ,0 W yyyy yyy yyy yyy 上述两个模型（上述两个模型（3-1）和（）和（3-2）是对同一问题的两种不）是对同一问题的两种不 同考虑的数学描述，其间有着一定的内在联系，将逐一剖同考虑的数

7、学描述，其间有着一定的内在联系，将逐一剖 析。析。 OR:SM 整理整理ppt 8 首先，分析这两个模型之间的对应关系：首先，分析这两个模型之间的对应关系： （1 1）一个问题的目标函数为极大化，约束条件为）一个问题的目标函数为极大化，约束条件为“”类类 型，另一个问题的目标为极小化，约束条件为型，另一个问题的目标为极小化，约束条件为“”类型；类型； （2 2）一个问题的变量个数等于另一个问题的约束条件个）一个问题的变量个数等于另一个问题的约束条件个 数；数； （3 3）一个问题的右端常数（约束系数）是另一个问题的）一个问题的右端常数（约束系数）是另一个问题的 目标函数的系数（成本系数）；目标

8、函数的系数（成本系数）； （4 4）两个问题的系数矩阵互为转置。）两个问题的系数矩阵互为转置。 我们把这种对应关系称为我们把这种对应关系称为对偶关系对偶关系。如果把（。如果把（3-13-1）称为）称为 原始问题，则（原始问题，则（3-23-2）称为对偶问题。）称为对偶问题。 OR:SM 整理整理ppt 9 3.1.2 3.1.2 对称型线性规划问题对称型线性规划问题对称型对偶问题对称型对偶问题 每一个线性规划问题都必然有与之相伴随的对偶问每一个线性规划问题都必然有与之相伴随的对偶问 题存在。先讨论对称型对偶问题；对于非对称型对偶问题存在。先讨论对称型对偶问题；对于非对称型对偶问 题，可以先转化

9、为对称型，然后再进行分析，也可以直题，可以先转化为对称型，然后再进行分析，也可以直 接从非对称型进行分析。接从非对称型进行分析。 对称型线性规划问题对称型线性规划问题数学模型的一般形式为数学模型的一般形式为 1122 11112211 21122222 1122 12 max( ) s.t.(33) ,0 nn nn nn mmmnnm n Z xc xc xc x a xa xa xb a xa xaxb axaxaxb x xx Y1 Y2 ym OR:SM 整理整理ppt 10 这种模型的特点是：这种模型的特点是： （1 1）目标函数是最大化类型）目标函数是最大化类型( (或是最小化类型

10、或是最小化类型) )； （2 2）所有约束条件都是）所有约束条件都是“”型（或都是型（或都是“”型）；型）； （3 3）所有决策变量都是非负的。）所有决策变量都是非负的。 如果把（如果把（3-33-3）作为原始问题，根据原始与对偶问题）作为原始问题，根据原始与对偶问题 的对应关系可得（的对应关系可得（3-33-3）的对偶问题为）的对偶问题为 1122 11121211 12122222 1122 12 min( ) s.t.(34) ,0 mm mm mm nnmnmn m W yb yb yb y a ya ya yc a ya yayc a ya yayc y yy OR:SM 整理整理p

11、pt 11 用矩阵表示的原始问题（用矩阵表示的原始问题（3-33-3）和对偶问题（）和对偶问题（3-43-4）为）为 其中其中Y=Y=（y y1 1,y,y2 2, ,y,ym m）, ,其它同前其它同前。 3.1.3 3.1.3 一般问题的对偶问题一般问题的对偶问题非对称型对偶问题非对称型对偶问题 线性规划有时以非对称型出现，那么如何从原始问题写线性规划有时以非对称型出现，那么如何从原始问题写 出它的对偶问题呢？出它的对偶问题呢？ max( ) s.t. 0 Z xCX AXb X min( ) s.t. 0 WyYb YAC Y OR:SM 整理整理ppt 12 例例1 写出下列线性规划的

12、对偶问题写出下列线性规划的对偶问题 23 13 123 123 123 m ax()25 2 266 s.t. 30 ,0 Zxxx xx xxx xxx xxx OR:SM 整理整理ppt 13 转换成转换成对称型对称型 123 123 123 123 123 123 m ax()025 02 266 s.t.30 30 ,0 Zxxxx xxx xxx xxx xxx xxx Y1 Y2 Y/3 y/3 3 3 / 1233 / 1233 / 123 / 1233 / 123 min( )2600 20 02 s.t. 6335 ,0 Wyyyyy yyyy yyyy yyyy yyyy

13、OR:SM 整理整理ppt 14 再设再设y y/ /3 3-y-y/ /3 3=y =y3 3，代入上述模型得，代入上述模型得： 123 123 123 123 123 min( )260 20 02 s.t. 635 ,0;? Wyyyy yyy yyy yyy yyy OR:SM 整理整理ppt 15 例例2 2 将例将例1 1模型中的模型中的x x2 2改为无非负约束变量，即模型为改为无非负约束变量，即模型为 写出其对偶问题写出其对偶问题 23 13 123 123 132 m ax( )25 2 266 s.t. 30 ,0;? Zxxx xx xxx xxx xxx OR:SM 整

14、理整理ppt 16 令令x2=x 2-x2. .其中 其中x 2,x20 转换成转换成对称型对称型 2 2 2 / / 123 / / 123 / / 1223 / / 1223 / / 1223 / / 123 m ax()0225 002 266 s.t.30 30 ,0 Zxxxxx xxxx xxxx xxxx xxxx xxxx Y1 Y2 Y/3 y/3 OR:SM 整理整理ppt 17 3 3 / 1233 / 1233 / 123 / 1233 / 1233 / 123 min( )2600 20 02 s.t. 02 6335 ,0 W yyyyy yyyy yyyy yyy

15、y yyyy yyyy 123 123 123 123 123 min( )260 20 02 s.t. 635 ,0,? Wyyyy yyy yyy yyy yyy OR:SM 整理整理ppt 18 综合上述两个例子，可以看出，线性规划与其对偶模型综合上述两个例子，可以看出，线性规划与其对偶模型 的关系有了新的拓展：的关系有了新的拓展： （1 1）一个问题的目标函数为极大化，约束条件为）一个问题的目标函数为极大化，约束条件为“”或或 “= =”类型，另一个问题的目标为极小化，约束条件为类型，另一个问题的目标为极小化，约束条件为“”或或 “= =”类型；类型； （2 2）一个问题的变量个数等于

16、另一个问题的约束条件个）一个问题的变量个数等于另一个问题的约束条件个 数；数； （3 3）一个问题的右端常数（约束系数）是另一个问题的）一个问题的右端常数（约束系数）是另一个问题的 目标函数的系数（成本系数）；目标函数的系数（成本系数）； （4 4）两个问题的系数矩阵互为转置）两个问题的系数矩阵互为转置; ; （5 5）一个问题的第）一个问题的第i i个约束为个约束为“= =”，则另一个问题的第，则另一个问题的第i i 个变量为个变量为“无非负约束变量无非负约束变量”（自由变量）。反之，一个问（自由变量）。反之，一个问 题的第题的第i i个变量为个变量为“无非负约束变量无非负约束变量”，则另一

17、个问题的第，则另一个问题的第i i 个约束为个约束为“= =”（方程）。（方程）。 OR:SM 整理整理ppt 19 原始问题原始问题(或对偶问题或对偶问题)对偶问题对偶问题(或原问题或原问题) 目标目标 max 目标目标 min 变量变量 n个个 约束约束 n个个 变量变量 0 0 无非负约束无非负约束 约束约束 =（方程）（方程） 约束约束 m个个 变量变量 m个个 约束约束 = （方程）（方程） 变量变量 0 0 无非负约束无非负约束 系数矩阵系数矩阵 b c 转置转置 c b OR:SM 整理整理ppt 20 这样对于任意给定的一个线性规划问题，均可依据上述这样对于任意给定的一个线性规

18、划问题，均可依据上述 对应关系对应关系直接写出其对偶问题模型直接写出其对偶问题模型，而无须先化成对称型。，而无须先化成对称型。 例例3 3 写出下列线性规划的对偶问题写出下列线性规划的对偶问题 123 123 123 123 123 m ax()2 2 1 s.t. 22 0;,? Zxxxx xxx xxx xxx xxx 解：解：因目标函数为因目标函数为“maxmax”类型，则约束条件应为类型，则约束条件应为“”和和 “= =”类型，故只需改变第三个约束条件的不等号方向，类型，故只需改变第三个约束条件的不等号方向， 即有：即有： 123 22xxx OR:SM 整理整理ppt 21 这样所

19、有的约束条件均为这样所有的约束条件均为“”和和“=”类型，按前述对类型，按前述对 应关系原则，可写出其对偶问题为：应关系原则，可写出其对偶问题为： 123 123 123 123 132 min( )22 21 2 s.t. 1 ,0,? W yyyy yyy yyy yyy yyy 123 123 123 123 123 m ax()2 2 1 s.t. 22 0;,? Zxxxx xxx xxx xxx xxx Y1 Y2 Y3 OR:SM 整理整理ppt 22 3.1.4 对偶问题的基本性质对偶问题的基本性质 设原始问题为：设原始问题为： 则其对偶问题为：则其对偶问题为： 1 1、对称性

20、定理、对称性定理 对偶问题的对偶是原始问题。对偶问题的对偶是原始问题。 根据对偶规划，很容易写出对偶问题的对偶模型。根据对偶规划，很容易写出对偶问题的对偶模型。 max( ),0(35)Z xCX AXb X min( ),0(36)W yYb YAC Y 2、对偶性定理、对偶性定理 若原问题有最优解，那么对偶问题也有最优解，而且两者的若原问题有最优解，那么对偶问题也有最优解，而且两者的 目标函数值相等。目标函数值相等。 OR:SM 整理整理ppt 23 3.1.5 对偶问题的最优解对偶问题的最优解 重要推论：重要推论： 1.1.原始问题单纯形表中松驰变量的检验数恰好对应着对原始问题单纯形表中

21、松驰变量的检验数恰好对应着对 偶问题的一个解。偶问题的一个解。 2.2.原始问题单纯形表中原始问题单纯形表中, ,原始问题的松弛变量的检验数对原始问题的松弛变量的检验数对 应于对偶问题的决策变量应于对偶问题的决策变量; ;而原始问题的决策变量的检验数对而原始问题的决策变量的检验数对 应于对偶问题的松弛变量应于对偶问题的松弛变量, ,只是只是符号相反符号相反。 注意：注意：在两个互为对偶的线性规划问题中，可任选一个进行在两个互为对偶的线性规划问题中，可任选一个进行 求解，通常是选择约束条件少的，因求解的工作量主要受到求解，通常是选择约束条件少的，因求解的工作量主要受到 约束条件个数的影响。约束条

22、件个数的影响。 OR:SM 整理整理ppt 24 例例4 求解下列线性规划问题求解下列线性规划问题 解：解：该问题仅有两个变量，但约束较多，其对偶问题为该问题仅有两个变量，但约束较多，其对偶问题为 12 1 2 12 12 2 12 m a x()43 6 8 7 s .t .( 37 ) 31 5 1 ,0 Zxxx x x xx xx x xx 12345 134 2345 125 min( )68715 34 s.t.3(3 8) ,0 W yyyyyy yyy yyyy y yy Y1 Y2 Y3 Y4 Y5 OR:SM 整理整理ppt 25 把上述问题（把上述问题（3-83-8）作为

23、原始问题求解，其最终单纯形表见下）作为原始问题求解，其最终单纯形表见下 表（表（3.33.3） 由表（由表（3.33.3）得其最优解为：）得其最优解为： 例例4 4的最优解可直接从表（的最优解可直接从表（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 -3 51 (0,0,0,0,0) 22

24、 51 ()71525 22 T Y W Y (4,3,2,5,0,0,4) ()443325 T X Z X OR:SM 整理整理ppt 26 第一章中的单纯形法，是从线性规划标准型的一个基本第一章中的单纯形法，是从线性规划标准型的一个基本 可行解出发，逐步迭代，使目标函数值不断改进，直到取得可行解出发，逐步迭代，使目标函数值不断改进，直到取得 最优解为止。在运算过程中，必须保证解的可行性，即在单最优解为止。在运算过程中，必须保证解的可行性，即在单 纯形表中，始终有常数项纯形表中，始终有常数项b b/ /00。当最优性条件。当最优性条件j j0 0得到满得到满 足时，迭代终止，这时原始问题和

25、对偶问题同时达到最优。足时，迭代终止，这时原始问题和对偶问题同时达到最优。 单纯形法的实质单纯形法的实质保证解的可行性（常数项保证解的可行性（常数项b b/ /00）, , 通过逐步迭代，达到最优性条件（通过逐步迭代，达到最优性条件（j j0 0 ）。）。 考虑到原始和对偶问题的对称性，在求解方法上换一角考虑到原始和对偶问题的对称性，在求解方法上换一角 度，即在运算过程中，始终保持其对偶问题解的可行性。也度，即在运算过程中，始终保持其对偶问题解的可行性。也 即在单纯形表中，始终保证最优性条件（即在单纯形表中，始终保证最优性条件（j j0 0 ），而原始），而原始 问题的解未必可行（常数项问题的

26、解未必可行（常数项 ）。）。 / b 0 OR:SM 整理整理ppt 27 通过逐步迭代，当通过逐步迭代，当b b/ /0 0 时，终止迭代，这时原始时，终止迭代，这时原始 问题和对偶问题同时达到最优。这种方法称之为对偶单问题和对偶问题同时达到最优。这种方法称之为对偶单 纯形法。纯形法。 对偶单纯形法的实质对偶单纯形法的实质保证最优性条件（保证最优性条件（j j0 0），）， 通过逐步迭代，达到解的可行性（常数项通过逐步迭代，达到解的可行性（常数项b b/ /0 0 ）。）。 OR:SM 整理整理ppt 28 3.2.1 3.2.1 对偶单纯形法的运算步骤对偶单纯形法的运算步骤 单纯形法的运算

27、思路单纯形法的运算思路: :先从非基变量中确定进基变量先从非基变量中确定进基变量, ,再再 从基变量中选择出基变量从基变量中选择出基变量( (大进大进-小出小出);); 对偶单纯形法的运算思路对偶单纯形法的运算思路: :先从基变量中确定出基变量先从基变量中确定出基变量, , 再从非基变量中选择进基变量再从非基变量中选择进基变量( (小出小出-小进小进).). 具体计算步骤如下具体计算步骤如下: : (1) (1)根据线性规划模型根据线性规划模型, ,列出初始单纯形表列出初始单纯形表, ,但需保证所有但需保证所有 检验数检验数j j0 .0 . (2) (2)检验检验. .若常数项若常数项b b

28、/ /0 ,0 ,则得到最优解则得到最优解, ,停止运算停止运算; ;否则否则 转下步转下步. . OR:SM 整理整理ppt 29 (3) (3)基变换基变换: : 确定出基变量。在确定出基变量。在b b/ /列中，将所有负值进行比较，其列中，将所有负值进行比较，其 中最小的一个分量所对应的变量为出基变量（中最小的一个分量所对应的变量为出基变量（小出小出）；）； 确定进基变量。根据确定进基变量。根据 ， 对应列的非基变量对应列的非基变量x xk k为进基变量为进基变量( (小进小进) )。 迭代运算与检验。以迭代运算与检验。以 为主元素，按单纯形法进为主元素，按单纯形法进 行迭代计算，得到新

29、的单纯形表，再返回到（行迭代计算，得到新的单纯形表，再返回到（2 2）检验。）检验。 / / min0 j k sj sjsk a aa / s k a OR:SM 整理整理ppt 30 例例7 用对偶单纯形法求线性规划问题用对偶单纯形法求线性规划问题 解：首先将问题化成标准型，得解：首先将问题化成标准型，得 123 123 123 123 min( )458090 24 s.t.35 ,0 W yyyy yyy yyy yyy 123 1234 1235 12345 max( )458090 24 s.t.35 ,0 W yyyy yyyy yyyy y yyyy OR:SM 整理整理ppt 31 将约束条件两端（将约束条件两端（-1-1