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

管理运筹学 第3章,李存芳 博士/教授/硕士生导师 研究领域：战略管理、组织行为、运营管理 讲授课程：管理运筹学、管理系统工程、运营管理 经济学 单 位：江苏师范大学商学院 物流管理系 E-mail：licf66,2,第 3 章 线性规划的对偶问题,Sub title,内容提要,第一节 线性规划的对偶理论 第二节 对偶单纯形法,3,每一个线性规划问题都有一个与之相伴随的另一个问题。这两个问题：一是，在数学模型上有着对应关系；二是，从一个问题的最优解完全可以得出另一个问题最优解的全部信息。 3.1.1 问题的提出 例1 引入一个资源价格问题。,3-1 线性规划的对偶理论,4,类似于第2章例1的生产计划问题。某企业生产甲、乙两种产品，需消耗A、B、C三种材料。据市场分析，单位甲、乙产品的销售收益分别为4万元和5万元。单位甲、乙产品对材料的消耗量及材料的供应量如表3.1所示。 原问题：应如何制定生产计划，使总收益为最大。 表3.1,5,运用单纯形法，可求得其最优解为：,设计划安排：x1为甲产品的产量， x2为乙产品的产量。（决策变量） 则，该问题的数学模型为：,6,新问题：现在从另一角度来讨论这个问题。 假设该企业经过市场预测，准备进行转产，且把现有三种材料进行转让，也恰好有一个制造商急需这批材料。于是买卖双方开始对资源的出让价格问题进行磋商，希望寻找一个双方都认为比较满意的合理价格。 分析：设A、B、C三种材料的单价分别为y1、y2、y3. 对于卖方来说，生产单位甲产品所获收益为4万元，为保证其总收入不少于405/2万元，则将生产单位甲产品所需资源转让出去，该企业的收入不能少于4万元。故y1、y2、y3必须满足约束条件： y1+2y2+y34 同样，将生产单位乙产品所需的资源转让出去，其收入不能少于生产单位乙产品的收益5万元，所以y1、y2、y3还必须满足约束条件： y1+y2+3y35,7,对于买方来说，他希望在满足上述约束条件下使总的支出 W（y） =45y1+80y2+90y3 达到最小。 综上所述，资源价格问题的数学模型可描述为：,上述两个模型（3-1）和（3-2）是对同一问题的两种不同考虑的数学描述，其间有着一定的内在联系，将逐一剖析。,8,首先，分析这两个模型之间的对应关系： （1）一个问题的目标函数为极大化，约束条件为“”类型，另一个问题的目标为极小化，约束条件为“”类型； （2）一个问题的变量个数等于另一个问题的约束条件个数； （3）一个问题的右端常数（约束系数）是另一个问题的目标函数的系数（成本系数）； （4）两个问题的系数矩阵互为转置。 我们把这种对应关系称为对偶关系。如果把（3-1）称为原始问题，则（3-2）称为对偶问题。,9,3.1.2 对称型线性规划问题对称型对偶问题 每一个线性规划问题都必然有与之相伴随的对偶问题存在。先讨论对称型对偶问题；对于非对称型对偶问题，可以先转化为对称型，然后再进行分析，也可以直接从非对称型进行分析。 对称型线性规划问题数学模型的一般形式为,Y1 Y2 ym,10,这种模型的特点是： （1）目标函数是最大化类型(或是最小化类型)； （2）所有约束条件都是“”型（或都是“”型）； （3）所有决策变量都是非负的。 如果把（3-3）作为原始问题，根据原始与对偶问题的对应关系可得（3-3）的对偶问题为,11,用矩阵表示的原始问题（3-3）和对偶问题（3-4）为 其中Y=（y1,y2,ym）,其它同前。 3.1.3 一般问题的对偶问题非对称型对偶问题 线性规划有时以非对称型出现，那么如何从原始问题写出它的对偶问题呢？,12,解：（1）首先把上述非对称型问题化为对称型问题。 在第一个约束条件的两边同（-1） 把第三个约束方程分解成两个 x1-x2+3x30 和 x1-x2+3x30 再将后一个两边同（-1）改写成 -x1+x2-3x30,例1 写出下列线性规划的对偶问题,13,转换成对称型,（2）写出相应的对偶问题（4个约束，分别对应4个对偶变量y1、y2、y/3、y/3）,Y1 Y2 Y/3 y/3,14,再设y/3-y/3=y3，代入上述模型得：,15,解：（1）首先把上述非对称型问题化为对称型问题。 在第一个约束条件的两边同（-1） 把第三个约束方程分解成两个 x1-x2+3x30 和 x1-x2+3x30 再将后一个两边同（-1）改写成 -x1+x2-3x30,例2 将例1模型中的x2改为无非负约束变量，即模型为 写出其对偶问题,16,令x2=x/2-x/2.其中x/2,x/20 转换成对称型,（2）写出相应的对偶问题（4个约束，分别对应4个对偶变量y1、y2、y/3、y/3）,Y1 Y2 Y/3 y/3,17,令y/3-y/3=y3,并将第二和第三个条件合并为方程，得,18,综合上述两个例子，可以看出，线性规划与其对偶模型的关系有了新的拓展： （1）一个问题的目标函数为极大化，约束条件为“”或“=”类型，另一个问题的目标为极小化，约束条件为“”或“=”类型； （2）一个问题的变量个数等于另一个问题的约束条件个数； （3）一个问题的右端常数（约束系数）是另一个问题的目标函数的系数（成本系数）； （4）两个问题的系数矩阵互为转置; （5）一个问题的第i个约束为“=”，则另一个问题的第i个变量为“无非负约束变量”（自由变量）。反之，一个问题的第i个变量为“无非负约束变量”，则另一个问题的第i个约束为“=”（方程）。,19,关于线性规划的原始问题与对偶问题的对应关系可归纳成下表3.2,20,这样对于任意给定的一个线性规划问题，均可依据上述对应关系直接写出其对偶问题模型，而无须先化成对称型。 例3 写出下列线性规划的对偶问题,解：因目标函数为“max”类型，则约束条件应为“”和“=”类型，故只需改变第三个约束条件的不等号方向，即有：,21,原问题即为：,这样所有的约束条件均为“”和“=”类型，按前述对应关系原则，可写出其对偶问题为：,Y1 Y2 Y3,22,3.1.4 对偶问题的基本性质,设原始问题为： 则其对偶问题为： 1、对称性定理 对偶问题的对偶是原始问题。 根据对偶规划，很容易写出对偶问题的对偶模型。,2、对偶性定理 若原问题有最优解，那么对偶问题也有最优解，而且两者的目标函数值相等。,23,3.1.5 对偶问题的最优解 重要推论： 1.原始问题单纯形表中松驰变量的检验数恰好对应着对偶问题的一个解。 2.原始问题单纯形表中,原始问题的松弛变量的检验数对应于对偶问题的决策变量;而原始问题的决策变量的检验数对应于对偶问题的松弛变量,只是符号相反。 注意：在两个互为对偶的线性规划问题中，可任选一个进行求解，通常是选择约束条件少的，因求解的工作量主要受到约束条件个数的影响。,24,例4 求解下列线性规划问题 解：该问题仅有两个变量，但约束较多，其对偶问题为,Y1 Y2 Y3 Y4 Y5,25,把上述问题（3-8）作为原始问题求解，其最终单纯形表见下表（3.3） 由表（3.3）得其最优解为： 例4的最优解可直接从表（3.3）的松弛变量y6、y7的检验数中读出，即有：,26,3-2 对偶单纯形法,第一章中的单纯形法，是从线性规划标准型的一个基本可行解出发，逐步迭代，使目标函数值不断改进，直到取得最优解为止。在运算过程中，必须保证解的可行性，即在单纯形表中，始终有常数项b/0。当最优性条件j0得到满足时，迭代终止，这时原始问题和对偶问题同时达到最优。 单纯形法的实质保证解的可行性（常数项b/0）,通过逐步迭代，达到最优性条件（j0 ）。 考虑到原始和对偶问题的对称性，在求解方法上换一角度，即在运算过程中，始终保持其对偶问题解的可行性。也即在单纯形表中，始终保证最优性条件（j0 ），而原始问题的解未必可行（常数项 ）。,27,通过逐步迭代，当b/0 时，终止迭代，这时原始问题和对偶问题同时达到最优。这种方法称之为对偶单纯形法。 对偶单纯形法的实质保证最优性条件（j0），通过逐步迭代，达到解的可行性（常数项b/0 ）。,28,3.2.1 对偶单纯形法的运算步骤 单纯形法的运算思路:先从非基变量中确定进基变量,再从基变量中选择出基变量(大进-小出); 对偶单纯形法的运算思路:先从基变量中确定出基变量,再从非基变量中选择进基变量(小出-小进). 具体计算步骤如下: (1)根据线性规划模型,列出初始单纯形表,但需保证所有检验数j0 . (2)检验.若常数项b/0 ,则得到最优解,停止运算;否则转下步.,29,(3)基变换: 确定出基变量。在b/列中，将所有负值进行比较，其中最小的一个分量所对应的变量为出基变量（小出）； 确定进基变量。根据 ， 对应列的非基变量xk为进基变量(小进)。 迭代运算与检验。以 为主元素，按单纯形法进行迭代计算，得到新的单纯形表，再返回到（2）检验。,30,例7 用对偶单纯形法求线性规划问题 解：首先将问题化成标准型，得,31,将约束条件两端（-1），得 若令Y1=Y2=Y3=0，得到初始基本解： 显然，它是一个初始基本解，但不可行。 再将上述模型的有关数字填入单纯形表，得下表3.4。可见所