《运筹学_对偶规划》由会员分享，可在线阅读，更多相关《运筹学_对偶规划（97页珍藏版）》请在金锄头文库上搜索。
1、第三章 对偶规划,对偶原理对偶单纯形方法灵敏度分析,对偶原理,对偶问题概念：任何一个线性规划问题都有一个伴生的线性规划问题，称为其“对偶”问题。对偶问题是对原问题从另一角度进行的描述，其最优解与原问题的最优解有着密切的联系，在求得一个线性规划最优解的同时也就得到对偶线性规划的最优解，反之亦然。对偶理论就是研究线性规划及其对偶问题的理论，是线性规划理论的重要内容之一。,问题的引出,问题的引出,例3-1,假设有客户提出要求，购买工厂所拥有的工时和材料，为客户加工别的产品，由客户支付工时费和材料费。那么工厂给工时和材料制订的最低价格应是多少，才值得出售工时和材料 ?,问题的引出,例3-1,约束 出卖
2、资源获利应不少于生产产品的获利; 目标 价格应该尽量低，这样才能有市场竞争力; 价格应该是非负的,问题的引出,用y1和y2分别表示工时和材料的出售价格,总利润最小 min W=3y1+9y2 保证A产品利润 y1+y22 保证B产品利润 y1+4y23 保证C产品利润 y1+7y23 售价非负 y10 y20,问题的引出,问题的引出,原问题,对偶问题,模型比较分析,例子：,原问题单纯形表,对偶问题单纯形表,对偶问题的定义,对称型对偶关系,对偶问题的定义,对称形式的对偶问题,或,简记： 极大化Z， 约束为,简记： 极小化W， 约束为,注意！ X：列向量 Y：行向量,对偶问题的定义,对偶问题的特点
3、 若原问题目标是求极大化，则对偶问题的目标是极小化，反之亦然 原问题的约束系数矩阵与对偶问题的约束系数矩阵互为转置矩阵 极大化问题的每个约束对应于极小化问题的一个变量，其每个变量对应于对偶问题的一个约束。,对偶问题的写出,例32 标准型对偶问题,原问题： 有等式约束怎么办？,对偶问题的写出,例33：写出对偶问题,原问题：有约束怎么办？ 有变量无符号要求怎么办？ 有非正变量怎么办？,对偶问题的写出,例33,对偶问题的定义,非对称形式下的对偶关系：对偶问题对应表,对偶问题的定义,非对称形式下的对偶问题,对偶问题课堂练习： 1.课本P49，例3 2.,对偶问题的定义,非对称形式下的对偶关系：对偶问题
4、对应表,对偶问题的定义,非对称形式下的对偶关系：对偶问题对应表,定理1 对称性定理,原问题与对偶问题互为对偶,定理2 弱对偶定理 若互为对偶的线性规划分别有可行解 则其相应的目标函数值满足,推论1 极大化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个下界。,推论2 极小化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个上界。,推论,定理3 若原始问题(对偶问题)具有无界解，则其对偶问题（原问题）无可行解。,定理4 最优性准则定理 若X 和Y 分别是互为对偶的线性规划的可行解 ，且使CX=Yb，则X和Y分别是相应线性规划问题的最优解,证明：由弱对偶定
5、理可知，对任意可行解有，CXYb 因此对于X 和Y也将分别有CXYb CXYb又因为 CX=Yb故有 Yb Yb CXCX,定理5 对偶定理 若原始问题和对偶问题都有可行解，那么两者均有最优解，且目标函数值相同。,证明：由两者均有可行解，则根据定理2可知两者均有界，因此均有最优解。,设B是其最优基，X是其对应的基本可行解 令A=(B N)，则：对应于基B的检验数满足,定理5 对偶定理,设B是其最优基，X是其对应的基本可行解 令A=(B N)，则：对应于基B的检验数满足,对偶问题的一个可行解, 其目标值：,再运用最优性准则定理得结论！,定理6 互补松弛定理若 分别是原问题和对偶问题的可行解， 分
6、别为对应的松弛变量和剩余变量，那么 分别是原问题和对偶问题的最优解的充分必要条件是,原问题,对偶问题,7,注：V1和V2分别是对应原规划问题基变量和非基变量的剩余变量,已知原问题及其解如下所示，求对偶规划问题的最优解。,课堂练习已知如下线性规划问题,对偶单纯形法,单纯形法基本过程是什么？,对偶单纯形法,单纯性法的矩阵表示,对偶单纯形法,初始单纯形表,非基变量,基变量,变换后的单纯形表,非基变量,基变量,对偶单纯形法,单纯形算法,对偶单纯形法,对偶单纯形法,称满足,的基解为对偶可行解。对偶单纯形算法就是从对偶可行解出发，从一个对偶可行解调整到另一个对偶可行解，直至找到基可行解。,对偶单纯形法,对
7、于标准线性规划问题：,对偶单纯形法,否,算 法 过 程,初始对偶可行解,是则停止,得最优解,选择出基变量,检查 是否无可 行解,是则停止,否,无最优解,选入基变量,计算检验数,对偶单纯形法,对于标准线性规划问题：,对偶单纯形法,可行基B 保持对偶可行性 对偶可行基B, 找一个基，建立初始对偶单纯形表，检验数全部非负； 若b列元素非负，则已经是最优基。反之，则取相应行的基变量为出基变量； 为保证能对基的可行性有所改进，则将来的主元应该为负数；为保证下一个基还能是对偶可行基，应使检验数仍为非负的。 主元变换,对偶单纯形表,或br为任意bi满足bi0,对偶单纯形法,换入变量选取：,换出变量选取：,进
8、行迭代运算,对偶单纯形法举例,例34 用对偶单纯形法求解：,大家想想以前在单纯形法里面，我们如何处理这个问题？,对偶单纯形法举例,对偶单纯形法举例,练习：用对偶单纯形法求解,对偶单纯形法的特点 对偶单纯形法先确定换出变量然后确定换入变量 初始基解可以是非可行解，但是要求检验数满足最优性条件（对偶可行），在计算中无需加入人工变量； 如果变量较少而约束较多时可以将问题转化为对偶问题进行求解，通常可以用对偶单纯形法简化计算 在应用中对偶可行解通常不太容易找到，所以很少单独使用。,对偶单纯形法是求解对偶问题解的方法吗？,影子价格,对偶变量的经济解释影子价格,对偶问题的最优解yi*是原问题第i种资源的影
9、子价格，是根据资源在生产中做出的贡献而做出的估价。资源的影子价格与市场价格不同，有赖于资源的使用情况，是未知的，当企业的生产任务、产品结构等发生变化时，资源的影子价格也会变化。而市场价格是相对稳定的。对偶变量yi在经济上表示原问题第i种资源的边际贡献,即在不改变最优基的条件下，当第i种资源增加一个单位时,相应的最优值z的增量。当资源 i 的增减超出一定范围时，原最优解就将变为不可行的解，从而将引起最优基的改变，并使yi也随着改变。,影子价格,如果原问题目标函数中决策变量的系数为产品的单位利润，则资源的影子价格yi可以看成是第i种资源的所提供的单位利润，所以当资源的市场价格高于影子价格时应卖出该
10、资源，否则买进。由互补松弛性，当生产中某种资源未得到充分利用时其影子价格就为零，当影子价格不为零时资源就已耗尽，增加这种资源会带来经济效益。,影子价格举例,y1=5/3, y2=1/3即工时的影子价格为5/3，材料的影子价格为1/3。 如果目前市场上材料的价格低于1/3，则企业可以购进材料来扩大生产，反之可以卖掉部分材料。如果有客户以高于5/3的价格购买工时，则可以出售一些工时，反之则反,灵敏度分析,在生产计划问题的一般形式中，A代表企业的技术状况，b代表企业的资源状况，而C代表企业产品的市场状况，在这些因素不变的情况下企业的最优生产计划和最大利润由线性规划的最优解和最优值决定。在实际生产过程
11、中，上述三类因素均是在不断变化的，如果按照初始的状况制订了最佳的生产计划，而在计划实施前或实施中上述状况发生了改变，则决策者所关心的是目前所执行的计划还是不是最优，如果不是应该如何修订原来的最优计划。更进一步，为了防止在各类状况发生时，来不及随时对其变化作出反应，即所谓“计划不如变化快”，企业应当预先了解，当各项因素变化时，应当作出什么样的反应。,灵敏度分析,当系数A，b，C发生改变时，目前最优基是否还最优？为保持目前最优基还是最优，系数A，b，C的允许变化范围是什么？假设每次只有一种系数变化目标系数C变化基变量系数发生变化；非基变量系数发生变化； 右端常数b变化 增加一个变量 增加一个约束
12、技术系数A发生变化,灵敏度分析,灵敏度分析的基本步骤 将参数的改变在最终单纯形表中表示出来； 检查原问题是否可行; 检查对偶问题是否可行； 按照以下几种情况决定是否继续计算及计算方法,灵敏度分析,灵敏度分析,改变价值向量,一般改变情况改变非基变量的价值向量改变基变量的价值向量算例,灵敏度分析,若B是最优基，则最优单纯形表形式如下：,灵敏度分析总是在最优表上进行,灵敏度分析,非 基 变 量,所以,由此可以确定,的范围,例1：考虑线性规划问题,问题1：如果保持最优解不变，那么非基变量x1 , x3的系数c1, c3各应控制在什么范围。 问题2：当c1 =4时，线性规划的最优解是否改变？,（1）,（
13、2）,基 变 量,公式记不住没有关系，只要知道推导的过程，就能计算出结果！,问题3 求例1中使最优基不变的c2的变化范围,当基变量系数变化超出该范围时，必然会出现某个检验数为负 的情况，需要继续进行迭代直到得到最优解。,问题4在例1中如果c2增加1，求此时线性规划的最优解。,资源数量（右端常数bi）变化,最终单纯形表中解相应地变为,由于b发生变化不影响检验数，对偶问题仍然可行，但是最优解会发生变化。要保证变换后的解还是最优解，即最优基不变，就需要保证变换后得到的解仍然是原问题的可行解，为此需要满足：,问题5：求例1中使最优基保持不变的b1,b2, b3的变化范围。,大家不要死记计算公式，在理解
14、的基础上去求解问题！,推出具体的值。比如课本p62，公式（3-6）,该值是如何得到的呢？为什么？,类似的方法，我们可以求b2,b3允许的变化范围(练习）,原最优解变为非可行解，B不再是可行基，需要重新计算最优解，怎么算呢？,约束条件矩阵元素aij变化,非基变量的系数变化,问题7：在例1所示的线性规划中，x3的系数变为 （1）(1,2,3)T （2）(1,3,2)T 原最优基是否会发生变化？,(1),最优解不变,(2),最优基发生变化如何计算新的最优解呢？,基变量系数发生变化基变量系数发生变化时，最优基发生变化，影响到所有的元素，需要重新运用单纯形法进行计算。,增加新的决策变量xn+1,否则需要
15、在原单纯形表中增加一列，再进行迭代,问题8：在例1中增加变量x8，且p8=(2,5,3)T，c8 分别等于4和5时，最优解是否发生变化？,新增加的变量为非基变量。,增加一个约束条件最优解仍然可行（原最优解满足新的约束条件） 最优解不可行 新加入的约束条件化为标准型（正规型），加入最终单纯形表中，对新的表进行迭代变换，应用对偶单纯形法进行计算。,问题9：在例1中增加约束条件,大家想想我们该如何处理？,首先将新增的约束条件化为标准型后直接添加到原单纯形表,课本方法比较复杂难理解！用下面的方法。,然后将所有的新的基变量的系数矩阵转化为单位矩阵。,最后使用对偶单纯形法求解,例2 某工厂在计划期内要安排生产I，II两种产品，已知生产单位产品所需要的设备台时及A，B两种原材料的消耗如下表所示：,已知生产1件I可以获利2元，生产1件II可获利3元， 问应当如何安排计划使该工厂获利最多？,应用单纯形法计算得到的最终单纯形表如下：,假设在例1中基变量x2的系数c2变化，那么在什么范围内变化最优解不变？,解得，,要使最优解不变，,问题1：原材料A的量在什么范围内变化时最优基不变？,问题2：若现在该厂从其他地方抽调4台时设备用于生产I和II，求此时的最优方案,
