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

?管理运筹学?

第3章李存芳博士/教授/硕士生导师研究领域：战略管理、组织行为、运营管理讲授课程：管理运筹学、管理系统工程、运营管理经济学单位：江苏师范大学商学院物流管理系E-mail：licf66@1631精品课件第3章线性规划的对偶问题Subtitle内容提要第一节线性规划的对偶理论第二节对偶单纯形法2精品课件

每一个线性规划问题都有一个与之相伴随的另一个问题。这两个问题：一是，在数学模型上有着对应关系；二是，从一个问题的最优解完全可以得出另一个问题最优解的全部信息。3.1.1问题的提出例1引入一个资源价格问题。§3-1线性规划的对偶理论3精品课件类似于第2章例1的生产方案问题。某企业生产甲、乙两种产品，需消耗A、B、C三种材料。据市场分析，单位甲、乙产品的销售收益分别为4万元和5万元。单位甲、乙产品对材料的消耗量及材料的供给量如表3.1所示。原问题：应如何制定生产方案，使总收益为最大。表3.1

产品材料甲乙供应量A1145B2180C1390收益4万元/单甲5万元/单乙4精品课件运用单纯形法，可求得其最优解为：

设方案安排：x1为甲产品的产量，x2为乙产品的产量。〔决策变量〕那么，该问题的数学模型为：5精品课件新问题：现在从另一角度来讨论这个问题。假设该企业经过市场预测，准备进行转产，且把现有三种材料进行转让，也恰好有一个制造商急需这批材料。于是买卖双方开始对资源的出让价格问题进行磋商，希望寻找一个双方都认为比较满意的合理价格。分析：设A、B、C三种材料的单价分别为y1、y2、y3.对于卖方来说，生产单位甲产品所获收益为4万元，为保证其总收入不少于405/2万元，那么将生产单位甲产品所需资源转让出去，该企业的收入不能少于4万元。故y1、y2、y3必须满足约束条件：y1+2y2+y3≥4同样，将生产单位乙产品所需的资源转让出去，其收入不能少于生产单位乙产品的收益5万元，所以y1、y2、y3还必须满足约束条件：y1+y2+3y3≥56精品课件对于买方来说，他希望在满足上述约束条件下使总的支出W〔y〕=45y1+80y2+90y3到达最小。综上所述，资源价格问题的数学模型可描述为：上述两个模型〔3-1〕和〔3-2〕是对同一问题的两种不同考虑的数学描述，其间有着一定的内在联系，将逐一剖析。7精品课件首先，分析这两个模型之间的对应关系：〔1〕一个问题的目标函数为极大化，约束条件为“≤〞类型，另一个问题的目标为极小化，约束条件为“≥〞类型；〔2〕一个问题的变量个数等于另一个问题的约束条件个数；〔3〕一个问题的右端常数〔约束系数〕是另一个问题的目标函数的系数〔本钱系数〕；〔4〕两个问题的系数矩阵互为转置。我们把这种对应关系称为对偶关系。如果把〔3-1〕称为原始问题，那么〔3-2〕称为对偶问题。8精品课件3.1.2对称型线性规划问题——对称型对偶问题

每一个线性规划问题都必然有与之相伴随的对偶问题存在。先讨论对称型对偶问题；对于非对称型对偶问题，可以先转化为对称型，然后再进行分析，也可以直接从非对称型进行分析。

对称型线性规划问题数学模型的一般形式为Y1Y2…ym9精品课件这种模型的特点是：〔1〕目标函数是最大化类型(或是最小化类型)；〔2〕所有约束条件都是“≤〞型〔或都是“≥〞型〕；〔3〕所有决策变量都是非负的。如果把〔3-3〕作为原始问题，根据原始与对偶问题的对应关系可得〔3-3〕的对偶问题为10精品课件用矩阵表示的原始问题〔3-3〕和对偶问题〔3-4〕为其中Y=〔y1,y2,…,ym〕,其它同前。3.1.3一般问题的对偶问题——非对称型对偶问题

线性规划有时以非对称型出现，那么如何从原始问题写出它的对偶问题呢？11精品课件解：〔1〕首先把上述非对称型问题化为对称型问题。

①在第一个约束条件的两边同×〔-1〕

②把第三个约束方程分解成两个

x1-x2+3x3≤0

和x1-x2+3x3≥0

再将后一个两边同×〔-1〕改写成

-x1+x2-3x3≤0例1写出以下线性规划的对偶问题12精品课件③转换成对称型〔2〕写出相应的对偶问题〔4个约束，分别对应4个对偶变量y1、y2、y/3、y//3〕Y1Y2Y/3y//313精品课件再设y/3-y//3=y3，代入上述模型得：14精品课件解：〔1〕首先把上述非对称型问题化为对称型问题。

①在第一个约束条件的两边同×〔-1〕

②把第三个约束方程分解成两个

x1-x2+3x3≤0

和x1-x2+3x3≥0

再将后一个两边同×〔-1〕改写成

-x1+x2-3x3≤0例2将例1模型中的x2改为无非负约束变量，即模型为写出其对偶问题15精品课件

③令x2=x/2-x//2.其中x/2,x//2≥0④转换成对称型〔2〕写出相应的对偶问题〔4个约束，分别对应4个对偶变量y1、y2、y/3、y//3〕Y1Y2Y/3y//316精品课件令y/3-y//3=y3,并将第二和第三个条件合并为方程，得17精品课件综合上述两个例子，可以看出，线性规划与其对偶模型的关系有了新的拓展：〔1〕一个问题的目标函数为极大化，约束条件为“≤〞或“=〞类型，另一个问题的目标为极小化，约束条件为“≥〞或“=〞类型；〔2〕一个问题的变量个数等于另一个问题的约束条件个数；〔3〕一个问题的右端常数〔约束系数〕是另一个问题的目标函数的系数〔本钱系数〕；〔4〕两个问题的系数矩阵互为转置;〔5〕一个问题的第i个约束为“=〞，那么另一个问题的第i个变量为“无非负约束变量〞〔自由变量〕。反之，一个问题的第i个变量为“无非负约束变量〞，那么另一个问题的第i个约束为“=〞〔方程〕。18精品课件

关于线性规划的原始问题与对偶问题的对应关系可归纳成下表3.2原始问题(或对偶问题)对偶问题(或原问题)

目标max

目标min

变量n个

约束n个

变量≥0≤0

无非负约束

约束≥≤

=（方程）

约束m个

变量m个

约束≤≥

=（方程）

变量≥0≤0

无非负约束系数矩阵bc转置cb19精品课件这样对于任意给定的一个线性规划问题，均可依据上述对应关系直接写出其对偶问题模型，而无须先化成对称型。例3写出以下线性规划的对偶问题解：因目标函数为“max〞类型，那么约束条件应为“≤〞和“=〞类型，故只需改变第三个约束条件的不等号方向，即有：20精品课件原问题即为：这样所有的约束条件均为“≤〞和“=〞类型，按前述对应关系原那么，可写出其对偶问题为：Y1Y2Y321精品课件3.1.4对偶问题的根本性质设原始问题为：那么其对偶问题为：1、对称性定理对偶问题的对偶是原始问题。根据对偶规划，很容易写出对偶问题的对偶模型。2、对偶性定理假设原问题有最优解，那么对偶问题也有最优解，而且两者的目标函数值相等。22精品课件3.1.5对偶问题的最优解重要推论：

1.原始问题单纯形表中松驰变量的检验数恰好对应着对偶问题的一个解。

2.原始问题单纯形表中,原始问题的松弛变量的检验数对应于对偶问题的决策变量;而原始问题的决策变量的检验数对应于对偶问题的松弛变量,只是符号相反。注意：在两个互为对偶的线性规划问题中，可任选一个进行求解，通常是选择约束条件少的，因求解的工作量主要受到约束条件个数的影响。23精品课件例4求解以下线性规划问题解：该问题仅有两个变量，但约束较多，其对偶问题为Y1Y2Y3Y4Y524精品课件把上述问题〔3-8〕作为原始问题求解，其最终单纯形表见下表〔3.3〕由表〔3.3〕得其最优解为：例4的最优解可直接从表〔3.3〕的松弛变量y6、y7的检验数中读出，即有：-6-8-7-15-100Y1y2y3y4y5Y6y7-15y41/21/2-1/2011/2-1/21/2-7y35/2-1/23/210-3/21/2-3/2

λj-2-500-4-4-325精品课件§3-2对偶单纯形法第一章中的单纯形法，是从线性规划标准型的一个根本可行解出发，逐步迭代，使目标函数值不断改进，直到取得最优解为止。在运算过程中，必须保证解的可行性，即在单纯形表中，始终有常数项b/≥0。当最优性条件λj≤0得到满足时，迭代终止，这时原始问题和对偶问题同时到达最优。单纯形法的实质——保证解的可行性〔常数项b/≥0〕,通过逐步迭代，到达最优性条件〔λj≤0〕。考虑到原始和对偶问题的对称性，在求解方法上换一角度，即在运算过程中，始终保持其对偶问题解的可行性。也即在单纯形表中，始终保证最优性条件〔λj≤0〕，而原始问题的解未必可行〔常数项〕。26精品课件通过逐步迭代，当b/≥0时，终止迭代，这时原始问题和对偶问题同时到达最优。这种方法称之为对偶单纯形法。对偶单纯形法的实质——保证最优性条件〔λj≤0〕，通过逐步迭代，到达解的可行性〔常数项b/≥0〕。27精品课件3.2.1对偶单纯形法的运算步骤单纯形法的运算思路:先从非基变量中确定进基变量,再从基变量中选择出基变量(大进----小出);对偶单纯形法的运算思路:先从基变量中确定出基变量,再从非基变量中选择进基变量(小出----小进).具体计算步骤如下:(1)根据线性规划模型,列出初始单纯形表,但需保证所有检验数λj≤0.(2)检验.假设常数项b/≥0,那么得到最优解,停止运算;否那么转下步.28精品课件(3)基变换:①确定出基变量。在b/列中，将所有负值进行比较，其中最小的一个分量所对应的变量为出基变量〔小出〕；②确定进基变量。根据，对应列的非基变量xk为进基变量(小进)。③迭代运算与检验。以为主元素，按单纯形法进行迭代计算，得到新的单纯形表，再返回到〔2〕检验。29精品课件例7用对偶单纯形法求线性规划问题解：首先将问题化成标准型，得30精品课件将约束条件两端〔-1〕，得假设令Y1=Y2=Y3=0，得到初始根本解：显然，它是一个初始根本解，但不可行。再将上述模型的有关数字填入单纯形表，得下表3.4。可见所有检验数均小于或等于0，因此，可用对偶单纯形法求解，整个求解过程见表3.4和表3.5。cj-45-80-9000CBYBb/Y1y2y3Y4y50y4-4-1-2-1100y5

-5-1-1[-3]01λj-45