管理运筹学 课件 03线性规划的对偶理论

1运筹学

OPERATIONSRESEARCH

第二章线性规划的对偶理论2第二章线性规划的对偶理论

(DualLinearProgramming,DLP)对偶问题的提出原问题与对偶问题对偶问题的基本性质影子价格对偶单纯形法灵敏度分析参数线性规划3例甲方生产计划问题：

ⅠⅡ能力设备A2212设备B4016设备C0515利润23Ⅰ，Ⅱ各生产多少,可获最大利润?§2.1对偶问题的提出设有原问题乙方租借设备：甲方以何种价格将设备A、B、C租借给乙方比较合理？请为其定价。假设A、B、C的单位租金分别为。思路：就甲方而言，租金收入应不低于将设备用于自己生产时的利润。4所以：生产产品Ⅰ的资源用于出租时，租金收入应满足：类似的，生产产品Ⅱ的资源用于出租时，租金收入应满足：总的租金收入：5原问题对偶问题用矩阵将上述原问题对偶问题写出6原问题对偶问题矩阵形式的原问题与对偶问题7原问题对偶问题目标函数：MAX约束条件：m个约束变量：n个变量目标函数：MIN约束条件：n个约束变量：m个变量§2.2

原问题与对偶问题8例写出下述规划的对偶问题互为对偶如何写出非规范的原问题相应的对偶问题：目标函数MINMAX约束条件约束条件=?4.变量?

对偶问题与原问题的关系：原问题对偶问题目标函数：MAX约束条件：m个约束变量：n个变量目标函数：MIN约束条件：n个约束变量：m个变量约束条件右端项价值系数价值系数约束条件右端项例写出下述规划的对偶问题目标函数MAXMIN约束条件变量3.变量约束例写出下述规划的对偶问题目标函数MINMAX约束条件变量3.变量约束12原问题对偶问题§2.3

对偶问题的基本性质假定线性规划的原问题与对偶问题分别为：13例甲方生产计划问题：

ⅠⅡ能力设备A2212设备B4016设备C0515利润23Ⅰ，Ⅱ各生产多少,可获最大利润?乙方租借设备，租金如何确定？原问题对偶问题14§2.3

对偶问题的基本性质1、弱对偶性 如果分别是原问题和对偶问题的可行解，则恒有15§2.3

对偶问题的基本性质2、最优性 如果分别是原问题和对偶问题的可行解，且有则分别是原问题和对偶问题的最优解。164、强对偶性 如果原问题有最优解，则其对偶问题也必有最优解，且两者最优目标函数值相等，即。3、无界性:如果原问题（对偶问题）有无界解，则其对偶问题（原问题）无可行解。5、互补松弛性：在线性规划的最优解中，如果对应某一约束条件的对偶变量值非零，则该约束条件取严格等式；反之，如果约束条件取严格不等式，则其对偶变量一定为零。即若若§2.4

对偶问题的基本性质例：1、写出其对偶问题。2、已知原问题的最优解为用对偶理论直接求对偶问题的最优解。练习：1、写出其对偶问题。2、已知原问题的最优解为用对偶理论直接求对偶问题的最优解。196、单纯形法的双层含义（1）用单纯形法求解LP问题时，迭代的每一步在得到该问题的一个基可行解的同时，其检验数的相反数就构成对偶问题的一个基本解。206、单纯形法的双层含义（2）在单纯形表中，原问题的松

驰变量对应对偶问题的变量，

对偶问题的剩余变量对应原问

题的变量。216、单纯形法的双层含义（3）这些互相对应的变量，如果在一个问题的解中是基变量，则在另一个问题的解中是非基变量。6、单纯形法的双层含义（4）将这两个解代入各自的

目标函数，有Z=W236、单纯形法的双层含义（4）将这两个解代入各自的

目标函数，有Z=W24对偶变量可理解为对一个单位第种资源的估价，称为影子价格。§2.4

影子价格1、定义：假设有原问题和对偶问题如下25例甲方生产计划问题：

ⅠⅡ能力设备A2212设备B4016设备C0515利润23Ⅰ，Ⅱ各生产多少,可获最大利润?乙方租借设备，租金如何确定？原问题对偶问题原问题是利润最大化的生产计划问题产品的利润（元/件）产品产量（件）总利润（元）资源限量（吨）剩余的资源（吨）消耗的资源单位产品消耗的资源（吨/件）§2.4影子价格比较对偶问题资源限量（吨）资源价格（元/吨）总租金（元）对偶问题是资源定价问题，对偶问题的最优解w1、w2、...、wm称为m种资源的影子价格。§2.4影子价格（1）资源市场价格受供求变化影响，影子价格则依赖于资源

利用情况。§2.4影子价格2、对影子价格的理解§2.4影子价格2、对影子价格的理解（2）影子价格是一种边际价格：表示资源增加一个单位时，

最优解及目标函数值的变化。Z=17/2Z=35/4Z=9§2.4影子价格2、对影子价格的理解（3）影子价格是一种机会成本。

当某种资源的市场价低于影子价格时，应买进这种资源；否则，应卖出这种资源。Z=17/2Z=35/4Z=9§2.4影子价格2、对影子价格的理解(4)由互补松驰性理解影子价格：如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0。影子价格不为零时，表明资源已用完。§2.4影子价格2、对影子价格的理解(5)从影子价格的含义考察单纯形法的计算生产该种产品所消耗各项资源的影子价格总和——隐含成本第j种产品的产值§2.4影子价格2、对影子价格的理解（6）求解线性规划问题及对偶问题的目的34§2.5

对偶单纯形法单纯形法：找一个初始基可行解，保持b列为正，通过迭代找到下一个基可行解，使目标函数值不断增大，当检验数行全部小于等于零时，达到最优解。35§2.5

对偶单纯形法在单纯形表中，列对应原问题的基可行解，行对应对偶问题的一个基解；当时，在检验数行就得到对偶问题的基可行解，

此时两个问题的目标函数值相等；由最优性条件知，两个问题都达到了最优解。36一、对偶单纯形法思想§2.5

对偶单纯形法换个角度考虑LP求解过程：保持对偶问题可行的前提下，通过逐步迭代实现原问题可行。374、检查是否达最优：b列非负时达最优，否则继续2、3。1、建立初始单纯形表，使表中的检验数都小于等于0。2、确定出基变量：选择b列中负值最小者对应变量出基，即对应的为出基变量。3、确定入基变量：最小比值规则，即以对应的为进基变量，为主元素进行迭代。二、对偶单纯形法计算步骤：§2.5

对偶单纯形法38例：用对偶单纯形法求解下述问题§2.5

对偶单纯形法对偶单纯形法的使用条件：

①检验数全部≤0；②b列至少一个元素<0；39§2.5

对偶单纯形法40原问题无可行解的判别准则：当对偶问题存在可行解时，若有某个，而所有，则原问题无可行解，对偶问题目标值无界。§2.5

对偶单纯形法41§2.6

灵敏度分析、含义：对系统因周围条件变化显示出来的敏

感程度的分析。可能变化的条件：利润

设备产品ABCD利润(元)

Ⅰ21402

Ⅱ22043

有效台时1281612已知资料如表所示，问如何安排生产才能使利润最大？maxZ=2x1+3x2

x1≥0,x2≥0s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤12设：X1——产品Ⅰ产量X2——产品Ⅱ产量建模§2.6

灵敏度分析43§2.6

灵敏度分析二、分析方法及步骤：能把参数变化直接反映在

最终单纯形表，无需从头计算。已知线性规划问题：将参数的改变计算反映到最终表45§2.6

灵敏度分析二、分析方法及步骤：能把参数变化直接反映在

最终单纯形表，无需从头计算。已知线性规划问题：将参数的改变计算反映到最终表46§2.6

灵敏度分析已知线性规划问题：将参数的改变计算反映到最终表2.检查原问题是否仍为可行解3.检查对偶问题是否仍为可行解4.得到最优解或继续计算二、分析方法及步骤：能把参数变化直接反映在

最终单纯形表，无需从头计算。47§2.6

灵敏度分析原问题对偶问题结论或计算步骤可行解可行解仍是最优解可行解非可行解用单纯形法继续迭代得到新的最优解非可行解可行解用对偶单纯形法继续迭代得到新的最优解非可行解非可行解引入人工变量，重新编单纯形表，重新计算三、判断得出结论或决定继续计算的依据：（一）Cj

的变化分析——只影响检验数。四、各个参数变化后的讨论50（一）Cj

的变化分析——只影响检验数。四、各个参数变化后的讨论例：设有如下的线性规划模型51用单纯形法求得最终单纯形表如下所示：（a）当目标函数变为时，最优解会出现什么变化;52解：将目标函数的变化直接反映到最终单纯形表中：53Cj

的变化对最优解的影响：54（b）目标函数变为时在什么范围内变化，最优解不变？将目标函数系数的变化直接反映到最终单纯形表中：解：由已知求得最终单纯形表：55（b）目标函数变为时在什么范围内变化，最优解不变？解：将目标函数系数的变化直接反映到最终单纯形表中：56（二）分析bi变化影响：反映在最终单纯形表上只引起

基变量列数字变化例、设有如下的线性规划模型57用单纯形法求得最终单纯形表如表所示：（a）第2个约束条件的右端项增大到32，分析最优解变化。58变换后的结果及迭代如下：bi

的变化对最优解的影响：60（b）第2个约束条件变为时在什么范围内变化，表中基为最优基？已求得最终单纯形表如下：解：将b的变化反映到基变量b这一列数字上，得表62（三）增加一个变量的分析：即增加一种新产品，A增加一列，C增加一个相应的分量。63（三）增加一个变量的分析：

设备产品ABCD利润(元)

Ⅰ21402

Ⅱ22043

有效台时1281612已知资料如表所示，问如何安排生产才能使利润最大？maxZ=2x1+3x2

x1≥0,x2≥0s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤12设：X1——产品Ⅰ产量X2——产品Ⅱ产量建模64（三）增加一个变量的分析：65例:设有如下的线性规划模型以上模型中，若增加一个变量，有,分析最优解变化。（三）增加一个变量的分析：66用单纯形法求得最终单纯形表如表所示：67将变化反映到最终单纯形表中:68增加一个变量对最优解的影响：69§2.6

灵敏度分析、含义二、方法及步骤

三、判断或计算依据（一）Cj

的变化分析——只影响检验数四、各个参数变化后的讨论（二）分析bi变化影响——只引起基变量列数字变化（三）增加一个变量的分析人工变量法70（四）分析变化的影响1、变化的两种情况72例：设有如下的线性规划模型四、各个参数变化后的讨论（四）分析变化的影响上述问题中，的系数向量变为分析最优解变化。已用单纯形法求得最终单纯形表：上述问题中，的系数向量变为分析最优解变化。74迭代，此时换出变量必为将变化反映到最终单纯形表，得：引入人工变量，将原问题转化为可行解。变化对最优解的影响：上述问题中，的系数向量变为77四、各个参数变化后的讨论（四）分析变化的影响78例:设有如下的线性规划模型,求得最终单纯形表如下：上述问题中，的系数向量变为分析最优解变化。79（五）增加一个约束条件的分析四、各个参数变化后的讨论1、含义：相当于增加一道工序，可能使可行域变小2、方法：将原最优解取值代入新增的约束条件，如满足说明新增约束未起限制作用，原最优解不变，否则将新增约束直接反映到最终表再进行分析。80（五）增加一个约束条件的分析四、各个参数变化后的讨论例：设有如下的线性规划模型上述问题中，增加一个约束条件分析最优解变化。81用单纯形法求得最终单纯形表如表2.8所示：增加一个约束条件82将约束条件写成取为基变量，直接反映到最终表：83将约束条件写成取为基变量，直接反映到最终表：84上表中由基变量对应向量构成的矩阵不是单位阵，故进行线性变换，85用对偶单纯形法求解，结果见下表增加一个约束条件对最优解的影响：增加一个约束条件：87§2.6

灵敏度分析、含义二、方法及步骤

三、判断或计算依据（一）Cj

的变化分析——只影响检验数四、各个参数变化后的讨论（二）分析bi变化影响——只引起基变量列数字变化（三）增加一个变量的分析（四）分析变化的影响（五）增加一个约束条件的分析2024/6/1388§2.7

参数线性规划一、定义：2024/6/1389§2.7

参数线性规划二、求解的步骤：1、令=0求解得最终单纯形表；2、将参数的变化反映到最终单纯形表中；3、找到使得最优解不变的参数变化范围，在临界点处令参数增加或减少，分析最优解的变化，并分析目标函数值随参数变化的情况。2024/6/13901、（p60例11）本章例6中，约束条件3右端项不断增大时，最优解如何变化？三、举例2024/6/13911、（p60例11）本章例6中，约束条件3右端项不断增大时，最优解如何变化？三、举例2024/6/1392解：（1）先令，求得最终单纯形表

如表所示：2024/6/1393（2）将参数的变化反映到最终单纯形表中；（3）让λ值逐渐增大，观察原问题或对偶问题的变化，看哪一个先出现非可行解。2024/6/1394（2）将参数的变化反映到最终单纯形表中；（3）让λ值逐渐增大，观察原问题或对偶问题的变化，看哪一个先出现非可行解。λ=1时，基变量x3=0，λ>1时，x3将取负值，因此最优解的条件是，

当时，用对偶单纯表法求解：2024/6/1395迭代过程96迭代结果λ值继续增大时，原问题和对偶问题都保持可行解，计算结束。2024/6/1397迭代结果2024/6/13982、（p61例12）求解下述参数线性规划问题三、举例2024/6/1399解：先令求得最优解，并将Cj的变化值反映到最终单纯形表中，2024/6/13100解：先令求得最优解，并将Cj的变化值反映到最终单纯形表中，2024/6/13101解：先令求得最优解，并将Cj的变化值反映到最终单纯形表中，由上表可知，当时，表中解为最优解。当时，有正的检验数。2024/6/13102继续迭代得：2024/6/131032024/6/131043、（p62例13）：某文教用品厂利用原材料白坯纸生产原稿纸、日记本、练习本三种产品，该厂现有工人100人，每天白坯纸供应量限制是30000kg，如果单独生产各种产品时，每人每天生产原稿纸30捆、日记本30打、练习本30箱。已知原材料消耗为每捆原稿纸用白坯纸公斤，每打日记本用白坯纸公斤，每箱练习本用白坯纸公斤。又知每捆原稿纸可盈利2元，每打笔记本盈利3元，每箱练习本盈利1元。试决定（1）在现有生产条件下，工厂盈利最大的生产方案；2024/6/13105例：设该厂每天生产原稿纸、日记本、练习本的数量分别是，2024/6/131062310032000017/31/10-102100010-4/3-1/104000-10/3-1/10-50迭代求解：2024/6/131073、某文教用品厂利用原材料白坯纸生产原稿纸、日记本、练习本三种产品，该厂现有工人100人，每天白坯纸供应量