资源描述：
《Ch2 对偶规划与灵敏度分析ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章对偶规划与灵敏度分析第一节对偶规划一、问题的提出仍然回到第一章中提出的生产计划的安排问题.问题产量安排问题某部门使用设备甲,乙,丙,丁来生产产品每ABC设备总工时甲224800乙123650丙423850丁242700种产品对设备工时的要求如下表所示:又各产品单件利润分别是4.5,5,7（百元）.问该部门解由第一章中的讨论,知问题的线性规划为应如何安排相应的生产计划,可使得利润达到最大?再由单纯形方法:得该问题的解:相应的单纯形表及最优表分别为现在的问题是:如果该厂不再生产产品而是将分析:问题的关键是确定各设备单位工时的相应转包费用.以表示四种设备单位工时的转包费用,则将生产一件产
2、品的设备工时转包出去所获得的收益用于生产这些产品的设备工时转包出去,则应该如何收取转包费用?应不低于相应的收益.即同理有:而问题的目标函数为由此得到问题的线性规划为由二阶段法得该问题的解最优解值为和原问题的解对照相比发现:问题二的解是原问题所引入的松弛变量的检验数;而原问题的解是问题二所引入的剩余变量的检验数.并且最优解的解值是相同的.由此我们引入下面对偶概念.定义设线性规划Ⅰ和Ⅱ之间有关系规划Ⅰ规划Ⅱ则称规划Ⅱ是规划Ⅰ的对偶规划,规划Ⅰ是原规划.又称规划Ⅰ是规划Ⅱ的对偶规划,规划Ⅱ是原规划.二、对偶规划对偶关系⑴极大与极小的对偶;⑵价值系数与资源常数的对偶;⑶约束条件系数矩阵的对偶是矩
3、阵的转置;⑷反向不等式与非正的决策变量的对偶;⑸等式与无非负限制的决策变量的对偶;⑹最优解与检验数的对偶.注:⑴正常不等式第个不等式反向第个不等式反向⑵对偶关系反向不等式三、例例1写出下面规划的对偶规划解由对偶关系容易得到对偶规划为例2写出下面规划的对偶规划无非负限制.解由对偶关系容易得到对偶规划为无非负限制.例3写出下面的对偶规划无非负限制.解将变量限制化为约束条件限制,则有无非负限制.由此得到对偶规划.无非负限制.四、对偶性质1.对偶规划的对偶规划为原规划.2.设原规划和对偶规划分别为且规划分别有可行解和,则有3.若分别是原规划和对偶规划的两个可行解,且则他们必是原规划和对偶规划的最
4、优解.4.松弛互补定理设是规划Ⅰ和Ⅱ的解,是对应的松弛变量和剩余变量的取值,则是最优有解当且仅当例设线性规划的最优解是求对偶问题的最优解.解对偶规划为因原问题的解中故对偶规划中引入的剩余变量的取值中,因而有方程容易得到该方程的解是此即为规划的最优解.最优解值第二节对偶单纯形方法在单纯形方法中,除了对规划的系数矩阵要求有个单位向量外,并且要求当中存在负数时,尽管可以可以使用人工变量法进行求解,单会使问题复杂化.这里介绍一种新的解法——对偶单纯形方法.设线性规划满足:⑴系数矩阵中有个单位向量;⑵检验数⑶资源常数中存在负数.则可用对偶单纯形方法求解.⑴建立对偶单纯形表;⑵判定当前解是否为最优解
5、:判定方法:当前解是最⑶若当前解不是最优解,则进行换基:①确定出基变量:若则是第行对应的基变量;②确定进基变量:优解否则当前解是不可行解.⑴其中为非基变量的检验数.③以主元进行迭代,目标:主元化为1,该列的其⑷重新进行判定.余元化为零;例4求解线性规划解先将其化为标准形为了得到单位矩阵,在约束条件两端同乘即有由此得到对偶单纯形表:即:最优解为最优解值例5求解规划解首先将原规划化为标准形:对约束条件,两端同乘以由对偶单出形方法:即:最优解为最优解值为利用对偶规划和对偶原理,可求下面问题的解.例6求解规划解直接求问题的解是相当麻烦的.为此考虑对偶规划:标准形为再由对偶单纯形法得由对偶原理知原
6、问题的最优解为最优解值为第三节灵敏度分析由实际问题所建立起来的线性规划其中的系数分别表示价值,资源及各产品对资源的占有情况.这些系数因受到市场的影响会发生某些变化.自然会考虑当这些系数发生变化时,问题的最优解是否会发生变化,以及发生变化时如何求出相应的最优解.,所谓的灵敏度分析即是讨论当系数发生变化时最优解的1.使最优解或最优基不变的系数变化范围;2.若解改变,如何求出新的最优解.变化情况.主要问题有:1.价值系数的改变对最优解的影响⑴非基变量的价值系数的改变对最优解的影响.设是所讨论的线性规划的最优基,因可见,的改变将会影响到原最优解.我们将从两个方面设是非基变量,其价值系数为增量为此
7、时对该问题进行讨论.故当时,最优解不变.例7设线性规划求:⑴使最优解不变的的变化范围;⑵分别取时求最优解.解问题的单纯形表及最优表为⑵.取此时最优解将改变,因⑴因故当及时,最优解不变,此时有即原最优表为即原问题的最优解改变为若取此时有故原最优表为值为最优解经再一次得迭代,得从而原问题的最优解为最优解值为⑵基变量的价值系数的改变对最优解的影响设基变量的价值系数为增量为则当则最优解不变.其中是基变量在最优表中所处的行⑵满足标,而是非基变
