运筹学基础及应用(第五版),(第二章).ppt

2020/6/12,1,运筹学OPERATIONSRESEARCH,第二章线性规划的对偶理论,2020/6/12,2,第二章线性规划的对偶理论(DualLinearProgramming,DLP),原问题与对偶问题对偶问题的基本性质影子价格对偶单纯形法灵敏度分析参数线性规划,2020/6/12,3,1对偶问题的提出,一、线性规划单纯形法的矩阵描述设有线性规划问题的标准形式,将系数矩阵表示成：,初始单纯形表,初等行变换后,初始表中是I的位置，经变换后成为,2020/6/12,4,其中,记,则,例：书P36例10，验证上述公式。,上述公式对于灵敏度分析很有帮助。,2020/6/12,5,，各生产多少,可获最大利润?,二、对偶问题的提出设有原问题,乙方租借设备：甲方以何种价格将设备A、B、C租借给乙方比较合理？请为其定价。解：假设A、B、C的单位租金分别为。,思路：就甲方而言，租金收入应不低于将设备用于自己生产时的利润。,2020/6/12,6,而就乙方而言，希望甲方的租金收入在满足约束的条件下越小越好，这样双方才可能达成协议。于是得到下述的线性规划模型：,所以：生产产品的资源用于出租时，租金收入应满足：,类似的，生产产品的资源用于出租时，租金收入应满足：,总的租金收入：,2020/6/12,7,原问题,对偶问题,用矩阵将上述原问题对偶问题写出,2020/6/12,8,即：原问题,对偶问题,2020/6/12,9,2原问题与对偶问题,对于一般的线性规划问题，,2020/6/12,10,类似于前面的资源定价问题，每一个约束条件对应一个“对偶变量”，它就相当于给各资源的单位定价。于是我们有如下的对偶规划：,2020/6/12,11,对偶问题与原问题的关系：,原问题,对偶问题,目标函数：MAX,约束条件：m个约束,变量：n个变量,目标函数：MIN,约束条件：n个约束,变量：m个变量,这是规范形式的原问题，由此写出其对偶问题如右方所示，那么，当原问题不是规范形式时，应如何写出其对偶问题？可以先将原问题化成规范的原问题，再写出对偶问题。,2020/6/12,12,例写出下述规划的对偶问题,于是对偶问题即为：,解先将该问题化为规范形式,也即为：,于是对偶问题的对偶是原问题。-对称性,互为对偶,2020/6/12,13,如何写出非规范的原问题相应的对偶问题：目标函数MINMAX约束条件约束条件=?4.变量?,例：P55例2，写出下面规划的对偶规划,2020/6/12,14,解：将原问题模型变形,则对偶问题是,2020/6/12,15,小结：对偶问题与原问题的关系：,原问题,对偶问题,目标函数：MAX,约束条件：m个约束,变量：n个变量,目标函数：MIN,约束条件：n个约束,变量：m个变量,约束条件右端项价值系数,价值系数约束条件右端项,2020/6/12,16,3对偶问题的基本性质,就上节所讨论的一般的线性规划问题及其对偶问题，有如下的性质：1、弱对偶性如果分别是原问题和对偶问题的可行解，则恒有考虑利用及代入。,2、无界性如果原问题（对偶问题）有无界解，则其对偶问题（原问题）无可行解。,2020/6/12,17,3、最优性如果分别是原问题和对偶问题的可行解，且有则分别是原问题和对偶问题的最优解。,证明设分别是原问题和对偶问题的最优解，则由弱对偶性，又，所以,2020/6/12,18,4、强对偶性如果原问题有最优解，则其对偶问题也必有最优解，且两者最优目标函数值相等，即。,证明设有线性规划问题经单纯形法计算后，令，最终表中所以,即：由此可知是对偶问题的可行解，又，就是最优解。,2020/6/12,19,5、互补松弛性：在线性规划的最优解中，如果对应某一约束条件的对偶变量值非零，则该约束条件取严格等式；反之，如果约束条件取严格不等式，则其对偶变量一定为零。即若若,证明由弱对偶性知：又因在最优解中，于是上式应为等式，即有,2020/6/12,20,而，故要使得上式成立，必有即,后半部分是前一命体的逆否命题，自然成立。互补松弛性还可写为对偶问题的相应的互补松弛性见书P58。例书P76，习题2-4,2020/6/12,21,6、设原问题是：对偶问题是：则原问题的检验数行对应对偶问题的一个基解（不一定是可行解），对应关系如下表。,原问题与对偶问题存在一对互补基解，原问题的松弛变量与对偶问题的变量对应；原问题的变量与对偶问题的剩余变量对应。互补的基解对应的目标函数值相等。,2020/6/12,22,例书P59例3,2020/6/12,23,2020/6/12,24,1、对偶变量可理解为对一个单位第种资源的估价，称为影子价格，但并非市场价格。,2、对偶变量的值（即影子价格）表示第种资源数量变化一个单位时，目标函数的增量。因为,4影子价格,假设有原问题和对偶问题如下：,2020/6/12,25,资源增加一个单位时，最优解及目标函数值的变化,2020/6/12,26,3、影子价格可用于指导资源的购入与卖出。当影子价格市场价格时，买入；影子价格市场价格时，卖出.,4、由互补松弛性可知，即影子价格为零，经济解释：资源未用完，再增加对目标函数也无贡献。反之，表明该种资源用尽，再购进用于扩大生产可增加总利润。,2020/6/12,27,5对偶单纯形法,在单纯形表中，列对应原问题的基可行解，行对应对偶问题的一个基解（不一定可行），当时，在检验数行就得到对偶问题的基可行解，此时两个问题的目标函数值相等，由最优性条件知，两个问题都达到了最优解。,单纯形法：找一个初始基可行解，保持b列为正，通过迭代找到下一个基可行解，使目标函数值不断增大，当检验数行全部小于等于零时，达到最优解。,2020/6/12,28,对偶单纯形法：找一个对偶问题的基可行解（保持行非正），原问题的解为基解（b列可以为负），通过迭代，当b列全部为正（原问题也达到了基可行解），即找到最优解。,3、检查是否达最优：b列非负时达最优，否则继续1、2。,2020/6/12,29,1、为何只考虑行中的元素对应的变量进基？为使迭代后的基变量取正值。,2、为何采用最小比值规则选择进基变量？为了使得迭代后的多偶问题解仍为可行解（检验数行仍为非正）,3、原问题无可行解的判别准则：当对偶问题存在可行解时，若有某个，而所有，则原问题无可行解，对偶问题目标值无界。因为第r行的约束方程即为：其中，因此不可能存在使上式成立。也即原问题无可行解。,2020/6/12,30,例、用对偶单纯形法求解下述问题,解将问题改写为目标最大化，并化为标准型,2020/6/12,31,列单纯形表,达到最优,2020/6/12,32,注意：1、使用对偶单纯形法时，当约束条件是时，可以不必添加人工变量。2、使用对偶单纯形法时，初始单纯形表中要保证对偶解为可行解常难以做到，所以一般不单独使用，常与灵敏度分析结合使用。,2020/6/12,33,6灵敏度分析,灵敏度分析：线性规划问题中的某些参数发生变化，对解的影响。（C，A，b）,灵敏度分析的一般步骤：1、将参数的改变经计算后反映到最终单纯形表中；2、检查原问题和对偶问题是否仍为可行解；3、按照下表对应情况，决定下一步骤。,2020/6/12,34,一、C的变化分析C的变化只影响检验数。,例、设有如下的线性规划模型试分析分别在什么范围变化时，最优解不变？,2020/6/12,35,解：问题的最终单纯形表如下：,2020/6/12,36,1、当变化时，假设，则要使得问题的最优解保持不变，则检验数行即可，即要求,2、当变化时，假设，则要使得问题的最优解保持不变，则检验数行即可，即要求,2020/6/12,37,二、b的变化分析b的变化将只影响原问题的基可行解，即最终表中的b列数值。,例、设有如下的线性规划模型试分析分别在什么范围变化时，最优基不变？,2020/6/12,38,解：将重新计算后填入问题的最终单纯形表：,1、当变化时，假设，则问题的解变为填入下表，得,2020/6/12,39,要使得最优基保持不变，则b列数值即可，即要求,同理可得的变化范围是：的变化范围是：,2020/6/12,40,三、增加一个变量的变化分析增加一个变量，在方程组（矩阵A）中就要增加一个系数列，在原来的最终表中也要添加一列，检验数也要计算，其余部分不受影响。如果检验数行仍，则最优解不变，否则继续迭代寻找最优。一般分析步骤：1、计算增加的新变量系数列在原最终表中的结果；2、计算新变量对应的检验数；3、根据的符号判断是否仍是最优解，若是，最优解不变；若不是，继续求解。,2020/6/12,41,例、设有如下的线性规划模型现增加变量，其对应系数列为，价值系数，请问最优解是否改变？,解：最终表,2020/6/12,42,新变量的检验数及系数列分别为：,填入表中，易知未达最优，继续迭代求解。,2020/6/12,43,已达最优。最优解为最优目标值,2020/6/12,44,四、增加一个约束条件的变化分析增加一个约束条件，相当于增加一道工序。分析方法:1）先将原最优解带入此新约束，若满足条件，说明此约束未起作用，原最优解不变；2）否则，将新约束加入到最终表中，继续分析。,例、在上例中添加新约束，分析最优解的变化情况。解：因为将原最优解带入此约束，不满足约束，原解已不是最优，继续分析。,2020/6/12,45,6,x,2020/6/12,46,已达最优。最优解为最优目标值,2020/6/12,47,7参数线性规划,参数线性规划：研究参数连续变化时最优解的变化以及目标函数值随参数变化的情况。注：当多个参数同时变化时，可以引入一个参数来表示这种变化。如：b列多个值发生变化时，可表示成求解参数线性规划的步骤：1、令求解得最终单纯形表；2、将参数的变化反映到最终单纯形表中；3、找到使得最优解不变的参数变化范围，在临界点处令参数增加或减少，分析最优解的变化，并分析目标函数值随参数变化的情况。,2020/6/12,48,例：求解下述参数线性规划问题:,解：求得时最终单纯形表并将参数的变化填入表中：,2020/6/12,49,2、是临界点，当时，所以选择作为进基变量，迭代一步得到：,1、由表可知，当时，即最优解不变。目标函数值是：,2020/6/12,50,3、由上表可知，当时，即最优解不变。目标函数值是,4、是临界点，当时，所以选择作为进基变量，迭代一步得到：,2020/6/12,51,5、由上表可知，当时，最优解不再变化。目标函数值是,6、是临界点，当时，所以选择作为进基变量，迭代一步得到：,此时无论如何增加，检验数始终为负，最优解不再变化。目标函数值是,2020/6/12,52,15,24,34,2020/6/12,53,例：某文教用品厂利用原材料白坯纸生产原稿纸、日记本、练习本三种产品，该厂现有工人100人，每天白坯纸供应量限制是3万kg，如果单独生产各种产品时，每人每天生产原稿纸30捆、日记本30打、练习本30箱。已知原材料消耗为每捆原稿纸用白坯纸公斤，每打日记本用白坯纸公斤，每箱练习本用白坯纸公斤。又知每捆原稿纸可盈利2元，每打笔记本盈利3元，每箱练习本盈利1元。试决定（1）在现有生产条件下，工厂盈利最大的生产方案；（2）如果白坯纸的供应数量不变，当工人人数不足时可招收临时工，其工资支出为每人每天40元，问该厂要不要招收临时工，最多招多少？,2020/