运筹学基础及应用第五.pptx

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