线性规划的对偶理论演示文稿

线性规划的对偶理论演示文稿2023/5/251目前一页\总数五十五页\编于八点（优选）线性规划的对偶理论2023/5/252目前二页\总数五十五页\编于八点§1对偶问题的提出

一、线性规划单纯形法的矩阵描述设有线性规划问题的标准形式将系数矩阵表示成：初始单纯形表初始解非基变量基变量0基可行解基变量非基变量0初等行变换后初始表中是I的位置，经变换后成为2023/5/253目前三页\总数五十五页\编于八点其中记则例：书P36例10，验证上述公式。

上述公式对于灵敏度分析很有帮助。

2023/5/254目前四页\总数五十五页\编于八点例甲方生产计划问题：

ⅠⅡ能力设备A2212设备B4016设备C0515利润23Ⅰ，Ⅱ各生产多少,可获最大利润?二、对偶问题的提出设有原问题乙方租借设备：甲方以何种价格将设备A、B、C租借给乙方比较合理？请为其定价。解：假设A、B、C的单位租金分别为。思路：就甲方而言，租金收入应不低于将设备用于自己生产时的利润。2023/5/255目前五页\总数五十五页\编于八点而就乙方而言，希望甲方的租金收入在满足约束的条件下越小越好，这样双方才可能达成协议。于是得到下述的线性规划模型：所以：生产产品Ⅰ的资源用于出租时，租金收入应满足：类似的，生产产品Ⅱ的资源用于出租时，租金收入应满足：总的租金收入：2023/5/256目前六页\总数五十五页\编于八点原问题对偶问题用矩阵将上述原问题对偶问题写出2023/5/257目前七页\总数五十五页\编于八点即：原问题对偶问题2023/5/258目前八页\总数五十五页\编于八点§2原问题与对偶问题对于一般的线性规划问题，2023/5/259目前九页\总数五十五页\编于八点类似于前面的资源定价问题，每一个约束条件对应一个“对偶变量”，它就相当于给各资源的单位定价。于是我们有如下的对偶规划：2023/5/2510目前十页\总数五十五页\编于八点对偶问题与原问题的关系：原问题对偶问题目标函数：MAX约束条件：m个约束变量：n个变量目标函数：MIN约束条件：n个约束变量：m个变量这是规范形式的原问题，由此写出其对偶问题如右方所示，那么，当原问题不是规范形式时，应如何写出其对偶问题？可以先将原问题化成规范的原问题，再写出对偶问题。2023/5/2511目前十一页\总数五十五页\编于八点例写出下述规划的对偶问题于是对偶问题即为：解先将该问题化为规范形式也即为：于是对偶问题的对偶是原问题。---------对称性互为对偶2023/5/2512目前十二页\总数五十五页\编于八点如何写出非规范的原问题相应的对偶问题：目标函数MINMAX约束条件约束条件=?4.变量?

例：P55例2，写出下面规划的对偶规划2023/5/2513目前十三页\总数五十五页\编于八点解：将原问题模型变形则对偶问题是2023/5/2514目前十四页\总数五十五页\编于八点小结：对偶问题与原问题的关系：原问题对偶问题目标函数：MAX约束条件：m个约束变量：n个变量目标函数：MIN约束条件：n个约束变量：m个变量约束条件右端项价值系数价值系数约束条件右端项2023/5/2515目前十五页\总数五十五页\编于八点§3

对偶问题的基本性质就上节所讨论的一般的线性规划问题及其对偶问题，有如下的性质：1、弱对偶性 如果分别是原问题和对偶问题的可行解，则恒有考虑利用及代入。2、无界性 如果原问题（对偶问题）有无界解，则其对偶问题（原问题）无可行解。2023/5/2516目前十六页\总数五十五页\编于八点3、最优性 如果分别是原问题和对偶问题的可行解，且有则分别是原问题和对偶问题的最优解。证明 设分别是原问题和对偶问题的最优解，则由弱对偶性，又，所以2023/5/2517目前十七页\总数五十五页\编于八点4、强对偶性 如果原问题有最优解，则其对偶问题也必有最优解，且两者最优目标函数值相等，即。证明 设有线性规划问题经单纯形法计算后，令，最终表中所以,即：由此可知是对偶问题的可行解，又，就是最优解。基可行解基变量非基变量2023/5/2518目前十八页\总数五十五页\编于八点5、互补松弛性：在线性规划的最优解中，如果对应某一约束条件的对偶变量值非零，则该约束条件取严格等式；反之，如果约束条件取严格不等式，则其对偶变量一定为零。即若若证明 由弱对偶性知：又因在最优解中，于是上式应为等式，即有2023/5/2519目前十九页\总数五十五页\编于八点而，故要使得上式成立，必有即后半部分是前一命体的逆否命题，自然成立。互补松弛性还可写为对偶问题的相应的互补松弛性见书P58。例书P76，习题2-42023/5/2520目前二十页\总数五十五页\编于八点6、设原问题是：对偶问题是：则原问题的检验数行对应对偶问题的一个基解（不一定是可行解），对应关系如下表

。初始解非基变量基变量0原问题与对偶问题存在一对互补基解，原问题的松弛变量与对偶问题的变量对应；原问题的变量与对偶问题的剩余变量对应。互补的基解对应的目标函数值相等。2023/5/2521目前二十一页\总数五十五页\编于八点例书P59例32300023101/20-1/50400-214/53501001/500-10-1/52023/5/2522目前二十二页\总数五十五页\编于八点基1120-1/201/50-4/511/5-1/5040332023/5/2523目前二十三页\总数五十五页\编于八点1、对偶变量可理解为对一个单位第种资源的估价，称为影子价格，但并非市场价格。2、对偶变量的值（即影子价格）表示第种资源数量变化一个单位时，目标函数的增量。因为§4

影子价格假设有原问题和对偶问题如下：2023/5/2524目前二十四页\总数五十五页\编于八点资源增加一个单位时，最优解及目标函数值的变化目标函数等值线2023/5/2525目前二十五页\总数五十五页\编于八点3、影子价格可用于指导资源的购入与卖出。当影子价格

>

市场价格时，买入；影子价格<

市场价格时，卖出.4、由互补松弛性可知，即影子价格为零，经济解释：资源未用完，再增加对目标函数也无贡献。反之，表明该种资源用尽，再购进用于扩大生产可增加总利润。2023/5/2526目前二十六页\总数五十五页\编于八点§5

对偶单纯形法在单纯形表中，列对应原问题的基可行解，行对应对偶问题的一个基解（不一定可行），当时，在检验数行就得到对偶问题的基可行解，此时两个问题的目标函数值相等，由最优性条件知，两个问题都达到了最优解。单纯形法：找一个初始基可行解，保持b列为正，通过迭代找到下一个基可行解，使目标函数值不断增大，当检验数行全部小于等于零时，达到最优解。2023/5/2527目前二十七页\总数五十五页\编于八点对偶单纯形法：找一个对偶问题的基可行解（保持行非正），原问题的解为基解（b列可以为负），通过迭代，当b列全部为正（原问题也达到了基可行解），即找到最优解。3、检查是否达最优：b列非负时达最优，否则继续1、2。对偶单纯形法计算步骤：1、确定出基变量：选择b列中负值最小者对应变量出、基，即对应的为出基变量。2、确定进基变量：最小比值规则，即以对应的为进基变量，为主元素进行迭代。2023/5/2528目前二十八页\总数五十五页\编于八点1、

为何只考虑行中的元素对应的变量进基？为使迭代后的基变量取正值。2、为何采用最小比值规则选择进基变量？为了使得迭代后的多偶问题解仍为可行解（检验数行仍为非正）3、原问题无可行解的判别准则：当对偶问题存在可行解时，若有某个，而所有，则原问题无可行解，对偶问题目标值无界。因为第r行的约束方程即为：其中，，因此不可能存在使上式成立。也即原问题无可行解。2023/5/2529目前二十九页\总数五十五页\编于八点例、用对偶单纯形法求解下述问题解将问题改写为目标最大化，并化为标准型2023/5/2530目前三十页\总数五十五页\编于八点列单纯形表-12-16-15000-2-2-40100-3-20[-5]01-12-16-15000-2[-2]-4010-153/52/50[1]0-1/5-6-1600-3-121[1]20-1/20-151/50-4/511/5-1/50-40-3-3达到最优2023/5/2531目前三十一页\总数五十五页\编于八点注意：1、使用对偶单纯形法时，当约束条件是时，可以不必添加人工变量。

2、使用对偶单纯形法时，初始单纯形表中要保证对偶解为可行解常难以做到，所以一般不单独使用，常与灵敏度分析结合使用。

2023/5/2532目前三十二页\总数五十五页\编于八点§6

灵敏度分析灵敏度分析：线性规划问题中的某些参数发生变化，对解的影响。（C，A，b）灵敏度分析的一般步骤：1、将参数的改变经计算后反映到最终单纯形表中；2、检查原问题和对偶问题是否仍为可行解；3、按照下表对应情况，决定下一步骤。原问题对偶问题结论或计算步骤可行解可行解仍是最优解可行解非可行解用单纯形法继续迭代得到新的最优解非可行解可行解用对偶单纯形法继续迭代得到新的最优解非可行解非可行解引入人工变量，重新编单纯形表，重新计算2023/5/2533目前三十三页\总数五十五页\编于八点一、C的变化分析

C的变化只影响检验数。例、设有如下的线性规划模型试分析分别在什么范围变化时，最优解不变？2023/5/2534目前三十四页\总数五十五页\编于八点2300023101/20-1/50400-214/53301001/500-10-1/5解：问题的最终单纯形表如下：30003101/20-1/50400-214/53301001/50002023/5/2535目前三十五页\总数五十五页\编于八点1、当变化时，假设，则要使得问题的最优解保持不变，则检验数行即可，即要求2、当变化时，假设，则要使得问题的最优解保持不变，则检验数行即可，即要求2023/5/2536目前三十六页\总数五十五页\编于八点二、b的变化分析

b的变化将只影响原问题的基可行解，即最终表中的b列数值。例、设有如下的线性规划模型试分析分别在什么范围变化时，最优基不变？2023/5/2537目前三十七页\总数五十五页\编于八点解：将重新计算后填入问题的最终单纯形表：1、当变化时，假设，则问题的解变为填入下表，得230002101/20-1/5000-214/5301001/500-10-1/52023/5/2538目前三十八页\总数五十五页\编于八点要使得最优基保持不变，则b列数值即可，即要求同理可得的变化范围是：的变化范围是：2023/5/2539目前三十九页\总数五十五页\编于八点三、增加一个变量的变化分析

增加一个变量，在方程组（矩阵A）中就要增加一个系数列，在原来的最终表中也要添加一列，检验数也要计算，其余部分不受影响。如果检验数行仍，则最优解不变，否则继续迭代寻找最优。一般分析步骤：1、计算增加的新变量系数列在原最终表中的结果；2、计算新变量对应的检验数；3、根据的符号判断是否仍是最优解，若是，最优解不变；若不是，继续求解。

2023/5/2540目前四十页\总数五十五页\编于八点例、设有如下的线性规划模型现增加变量，其对应系数列为，价值系数，请问最优解是否改变？

解：最终表2300023101/20-1/50400-214/53301001/500-10-1/52023/5/2541目前四十一页\总数五十五页\编于八点新变量的检验数及系数列分别为：填入表中，易知未达最优，继续迭代求解。2023/5/2542目前四十二页\总数五十五页\编于八点2300023101/20-1/50400-214/53301001/500-10-1/523101/20-1/50100-1/21/41/532011/2-1/4000-1/2-1/4-2/5010000411已达最优。最优解为最优目标值2023/5/2543目前四十三页\总数五十五页\编于八点四、增加一个约束条件的变化分析

增加一个约束条件，相当于增加一道工序。分析方法:1）先将原最优解带入此新约束，若满足条件，说明此约束未起作用，原最优解不变；2）否则，将新约束加入到最终表中，继续分析。例、在上例中添加新约束，分析最优解的变化情况。解：因为将原最优解带入此约束，不满足约束，原解已不是最优，继续分析。2023/5/2544目前四十四页\总数五十五页\编于八点2300023101/20-1/50400-214/53301001/50143200000-10-1/500001023101/20-1/50400-214/53301001/50-100-3/201/500-10-1/5000106x2023/5/2545目前四十五页\总数五十五页\编于八点28/31000-1/10016/300018/153301001/502/30010-2/150000-2/51/3-4/30-2/3-2/3已达最优。最优解为最优目标值2023/5/2546目前四十六页\总数五十五页\编于八点§7

参数线性规划参数线性规划：研究参数连续变化时最优解的变化以及目标函数值随参数变化的情况。注：当多个参数同时变化时，可以引入一个参数来表示这种变化。如：b列多个值发生变化时，可表示成求解参数线性规划的步骤：1、令求解得最终单纯形表；2、将参数的变化反映到最终单纯形表中；3、找到使得最优解不变的参数变化范围，在临界点处令参数增加或减少，分析最优解的变化，并分析目标函数值随参数变化的情况。2023/5/2547目前四十七页\总数五十五页\编于八点例：求解下述参数线性规划问题:解：求得时最终单纯形表并将参数的变化填入表中：0003101/20-1/50400-214/5301001/50002023/5/2548目前四十八页\总数五十五页\编于八点2、是临界点，当时，所以选择作为进基变量，迭代一步得到：0000620[1]0-2/501640010301001/50001、由表可知，当

时，即最优解不变。目标函数值是：2023/5/2549目前四十九页\总数五十五页\编于八点3、由上表可知，当

时，即最优解不变。目标函数值是4、是临界点，当时，所以选择作为进基变量，迭代一步得到：0000122210001640010015