《线性规划的对偶问题.pptx》由会员分享，可在线阅读，更多相关《线性规划的对偶问题.pptx（86页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 每一个求极大值线性规划问题都有一个与之伴随的求极小值的线性规划问题，这个伴随的线性规划问题称之为它的对偶问题。3.1 3.1 线性规划的对偶问题线性规划的对偶问题第1页/共86页引例 某工厂用甲乙两种资源生产A、B、C、D四种产品，现有资源数、单位产品所需资源数以及单位产品可获利润如下表所示.问如何组织生产能使利润最大？产品(公斤/件)单位利润(元)资源甲乙现有资源(吨)对偶问题的提出第2页/共86页产品(公斤/件)单位利润(元)资源甲乙现有资源(吨)显然，该问题的线性规划模型为：第3页/共86页 现在从另一个角度考虑问题。假设该厂不生产A、B、C、D四种产品了，而是将甲、乙两种资源出租给其
2、它单位，其原则是：使别的单位愿意租，又使本单位获利不低于原利润。问如何给甲、乙两种资源定价最合理？产品(公斤/件)单位利润(元)资源甲乙现有资源(吨)第4页/共86页解设甲、乙两种资源的价格为设总收入为W，则 约束条件为 产品(公斤/件)单位利润(元)资源甲乙现有资源(吨)第5页/共86页比较一下这两个线性规划问题：原问题对偶问题第6页/共86页线性规划问题和它的对偶问题之间的关系：（2）原始问题约束不等式的个数等于对偶问题变量 的个数；（3）原始问题的收益系数，成为对偶问题中约束不 等式右端的常数项；（5）约束不等式，一个全是“”，另一个全是“”；（4）两个约束方程组的系数矩阵互为转置矩阵（
3、6）原始问题和对偶问题是相对的，可以互相转化；（1）目标函数，原始问题是求最大值，对偶问题 是求最小值；第7页/共86页对偶问题的矩阵表示：原问题对偶问题第8页/共86页对偶问题的矩阵表示：原问题对偶问题第9页/共86页对偶问题的矩阵表示：原问题对偶问题第10页/共86页例例1 1 写出线性规划问题的对偶问题对称形式：第11页/共86页练习 写出下列问题的对偶问题（77页）第12页/共86页非对称形式非对称形式例例 写出下面线性规划问题的对偶问题第13页/共86页解先化为对称形式第14页/共86页解先化为对称形式第15页/共86页解先化为对称形式第16页/共86页解先化为对称形式第17页/共8
4、6页写出其对偶问题,设对偶问题的变量为第18页/共86页这样的对偶问题与原问题无法对照,？第19页/共86页第20页/共86页原问题对偶问题第21页/共86页对偶关系对应表原始问题（对偶问题）对偶问题（原始问题）目标函数系数矩阵目标函数系数为常数列向量为约束条件决策变量m 个型(第i个)型(第i个)型(第i个)n 个无限制目标函数系数矩阵目标函数系数为常数列向量为约束条件对偶变量型(第j个)型(第j个)型(第j个)m 个无限制n 个第22页/共86页练习 写出下列问题的对偶问题（77页）无符号限制无符号限制第23页/共86页本小节所用课时数：两节第一节课讲完定理第二节课专门讲定理最后两个定理的
5、证明可以不讲不强调抽象晦涩的证明过程多关注对定理的理解和应用 对偶问题的基本理论第25页/共86页 对偶问题的基本理论对偶问题的基本理论定理若 和 分别是原始问题和对偶问题的任一可行解，则必有 证明：假设线性规划的原问题和对偶问题分别为和第26页/共86页定理若 和 分别是原始问题和对偶问题的任一可行解，则必有 推论1最小值原始问题的任意一个可行解对应的目标函数值是其对偶问题最优值的一个上界推论2最大值原始问题的任意一个可行解是其对偶问题最优值的一个下界推论3若原始问题可行，而目标函数无界，则其对偶问题无可行解第27页/共86页例(补充)已知线性规划问题：试用对偶理论证明该问题的最优值不超过2
6、5第28页/共86页解 写出其对偶问题 显然，是对偶问题的一个可行解，它对应的目标函数值为根据对偶理论，最小值问题的任一可行解都是其对偶问题最优值的一个上界，第29页/共86页定理若 和 分别是原始问题和对偶问题的可行解，且有 ，则 和 分别是原始问题和对偶问题的最优解证明：设 是原始问题的任一可行解由定理可得又已知由 的任意性可知，是原始问题的最优解同理可证 是对偶问题的最优解第30页/共86页定理(对偶定理)在互为对偶的线性规划问题中,如果其中一个有最优解,则另一个也有最优解，且它们的最优值相等证明：假设原始问题为如下的标准形式则其对偶问题为无符号限制第31页/共86页最优值为即 是对偶问
7、题的一个可行解,设 是原始问题的最优解，它对应的最优基为B，则相应的基变量为检验数为令则而由定理3.3.可知，是对偶问题的最优解无符号限制第32页/共86页推论1在互为对偶的线性规划问题中，若原始问题的最优基为B，则对偶问题的最优解为 推论2设 为原始问题的一个可行解，相应的可行基为B，而 为其对偶问题的可行解，则 和 分别为它们的最优解定理(对偶定理)在互为对偶的线性规划问题中,如果其中一个有最优解,则另一个也有最优解，且它们的最优值相等第33页/共86页例(补充)已知线性规划问题：试用对偶理论证明该问题无最优解解 写出对偶问题,若原问题有最优解,则对偶问题也有最优解,但是观察可知,对偶问题
8、无可行解,更不会有最优解，故原问题无最优解第34页/共86页定理若原始问题的最优解存在，则用单纯形法求解时，其对偶问题的最优解可同时在最优单纯形表上得到，且顺次等于松弛变量或剩余变量对应的检验数的相反数第39页/共86页例(补充)求线性规划问题的对偶问题的最优解标准形式最优单纯形表2 3 0 1 0 0 0 1x3 1 0 0 1 -1 0 1x5 2 0 0 0 -1 1 2x第40页/共86页例(补充)求线性规划问题的对偶问题的最优解标准形式对偶 问题第41页/共86页原始问题的最优单纯形表原始问题的最优解为对偶问题的最优解为最优值为最优值为2 3 0 1 0 0 0 1x3 1 0 0
9、1 -1 0 1x5 2 0 0 0 -1 1 2x第42页/共86页定理若原始问题的最优解存在，则用单纯形法求解时，其对偶问题的最优解可同时在最优单纯形表上得到，且顺次等于松弛变量或剩余变量对应的检验数的相反数注：此处原始问题和对偶问题的决策变量都必须是非负的第43页/共86页定理（互补松弛性）若 和 分别是原始问题和对偶问题的可行解，且 和 分别为它们的剩余变量和松弛变量，则 和 当且仅当 和 分别为它们的最优解 假设线性规划的原问题和对偶问题分别为和设原始问题的变量个数为n，约束个数为m，则对偶问题的变量个数为m，约束个数为n 第44页/共86页原始问题的变量 原始问题的剩余变量 对偶问
10、题的变量 对偶问题的松弛变量 在一对变量中,其中一个大于零,另一个一定等于零第45页/共86页标准形式标准形式对偶问题最优解第46页/共86页标准形式标准形式对偶问题最优解第47页/共86页标准形式标准形式对偶问题最优解第48页/共86页标准形式标准形式对偶问题至少有一个不是最优解第49页/共86页互补松弛条件 意味着:1、若某一决策变量的值大于零,则在其对偶问题中与之对应的约束条件取严格等式;2、若某一约束条件取严格不等式,则在其对偶问题中与之对应的决策变量值一定为零.第50页/共86页标准形式标准形式对偶问题第51页/共86页标准形式标准形式对偶问题第52页/共86页互补松弛条件 意味着:
11、1、若某一决策变量的值大于零,则在其对偶问题中与之对应的约束条件取严格等式;2、若某一约束条件取严格不等式,则在其对偶问题中与之对应的决策变量值一定为零.第53页/共86页例(补充)已知线性规划问题：已知其对偶问题的最优解为试用对偶理论找出原问题的最优解第56页/共86页第58页/共86页解 写出对偶问题 故原问题的两个约束均取严格等式是对偶问题的最优解而当 时，对偶问题的第二、三、四约束取严格不等式，故有于是由原问题的约束条件可得第59页/共86页练习：78页3.3 已知线性规划问题：已知其对偶问题的最优解为试用对偶理论求出原问题的最优解答案：第60页/共86页解 写出对偶问题 故原问题的两
12、个约束均取严格等式是对偶问题的最优解而当 时，对偶问题的第一、二、约束取严格不等式，故有于是由原问题的约束条件可得第61页/共86页作业：78页 第62页/共86页78页 题答案解 令 ，并将原问题化为对称形式 写出对称形式的对偶问题第63页/共86页显然，和分别是原问题和对偶问题的可行解，而且满足互补松弛性，故它们分别是原始问题和对偶问题的最优解。第64页/共86页第65页/共86页练习 某线性规划问题的最优单纯形表如下：（a）写出原线性规划问题并求其最优值；（b）写出原问题的对偶问题；（c）直接由表格写出对偶问题的最优解.其中，是松弛变量，问题的约束为“”形式第67页/共86页答案：（a）
13、原线性规划问题为：（b）略；（c）对偶问题的最优解为第68页/共86页解 设最优值为m，在单纯形表上做初等行变换第69页/共86页第70页/共86页产品(公斤/件)单位利润资源甲 乙现有资源 影子价格影子价格（甲资源）（甲资源）（乙资源）（乙资源）（利润）（利润）第71页/共86页则求原始规划的最优解就是求在有限资源配置下的最佳效益；设原始问题及其对偶问题分别为如下形式那么，此时相应的对偶规划的最优解，即变量y的取值对于原问题来说有何经济意义呢？第72页/共86页 设 是原问题的最优基，和 分别为原问题和对偶问题的最优解，和 分别是原问题和对偶问题的最优值，则有 其中，是第i种资源的现有总量，
14、可以看成是每一个单位第i 种资源对经济效益所做的贡献；或者说成是每一个单位第i 种资源在原生产安排的机会中所创造的价值；称 为第i种资源的影子价格.第73页/共86页 注意：影子价格不是资源的市场价格，而是对资源在生产中所做的贡献的估价.这说明，在给定的条件下,每增加一个单位第i 种资源的用量,目标函数值(即总收益)的增量就等于影子价格第74页/共86页例 某厂用甲、乙、丙三种原料生产、两种产品，线性规划模型如下第75页/共86页例 某厂用甲、乙、丙三种原料生产、两种产品，线性规划模型如下甲的用量：乙的用量：丙的用量：有剩余用完用完第76页/共86页影子价格在管理决策中的作用:(0)影子价格反
15、映了供求关系和资源的稀缺性：(1)影子价格告诉企业的经营管理者，增加哪 种资源对提高效益有利：若影子价格高于市场价格,就可以购进该资源；反之，暂时就不要购买了。影子价格为零，说明供大于求，影子价格越高资源越稀缺第77页/共86页(2)影子价格告诉决策者新的产品是否可以投入生产例如 之前那个工厂打算生产一种新产品,已知单位新产品耗用的三种原料分别是（2,3,2）,而单位新产品的售价是8元,问新产品是否应该生产？前面已经求出三种原料的影子价格了:可以生产第78页/共86页(3)当市场价格变动时，可从单纯形表中直接求出各资源的新的影子价格，从而看出各单位资源所创造的新的价值例如，上例中产品A、B的售
16、价由（6，5）变为（6，6）：第79页/共86页例 某厂用甲、乙、丙三种原料生产、两种产品，线性规划模型如下第80页/共86页例 某厂用甲、乙、丙三种原料生产、两种产品，线性规划模型如下第81页/共86页例 某厂用甲、乙、丙三种原料生产、两种产品，线性规划模型如下第82页/共86页这说明在新的形势下原料丙变得更为重要了.影子价格为零，说明供大于求，影子价格越高则资源越稀缺第83页/共86页作业 1、对于下述线性规划问题（资源1）（资源2）（资源3）已知最优解中的基变量为 ，且已知请确定三种资源的影子价格.第84页/共86页2、某厂生产甲乙丙三种产品，有关数据如右表所示：a、建立线性规划模型，求使该厂获利最大的生产计划；b、若原材料B的市场单价为个单位，问该厂是否应该购买？各产品消耗原料定额单位利润现有原料原 料A Bc、若有一种新产品丁，其原料消耗定额为：A3个单位，B2个单位，单件利润为个单位，问该产品是否值得安排生产；第85页/共86页感谢您的观看！第86页/共86页