第三章(肖健华).ppt

第三章 线性规划的对偶理论 本章主要内容 给定LP原问题P后，如何写出对偶问题D； 原问题与对偶问题的关系； 给出解LP问题的对偶单纯形算法； 灵敏度分析 §3.1 对偶问题的提出 例1：某家具厂木器车间生产木门与木窗两种产品，加工木门收入为56元/扇，加工木窗收入为30元/扇，生产一扇木门需要木工4小时，油漆工2小时；生产一扇木窗需要木工3小时，油漆工1小时，该车间每日可用木工总工时为120小时，油漆工总工时为50小时，问该车间如何安排生产才能使每日收入最大？ 例2：某工厂在某一计划期内准备生产甲、乙两种产品，生产需要消耗A、B、C三种资源，各种资源拥有量分别为8、16、12。生产甲需A、B、C分别为1，4，0，生产乙需A、B、C分别为2，0，4。现已知甲、乙的利润分别为2，3.问：如何安排生产，以使计划期内的生产获利最大？ 原问题与对偶问题的对应 原问题 对偶问题 注意： §3.2 对偶关系及对偶性质 一、原问题与其对偶问题的对应关系 对称形式的原问题：目标函数求极大值、约束条件取小于等于号、决策变量非负的线性规划问题。 对称形式的原问题与对偶问题具有对应关系： ① 原问题目标函数求极大值，对偶问题目标函数求极小值； ② 原问题约束条件的数目等于对偶问题决策变量的数目； ③ 原问题决策变量的数目等于对偶问题约束条件的数目； ④ 原问题的价值系数成为对偶问题的资源系数； 对称形式的原问题与对偶问题具有对应关系： ⑤ 原问题的资源系数成为对偶问题的价值系数； ⑥ 原问题的技术系数矩阵与对偶问题的技术系数矩阵互为转置； ⑦ 原问题的约束条件为小于等于号，对偶问题的决策变量大于等于0； ⑧ 原问题的决策变量大于等于0，对偶问题的约束条件为大于等于号。 例1：设LP的数学模型如下，求其对称形式下的对偶问题的数学模型。 例2：写出如下线性规划问题的对偶问题 本例表明：原问题约束条件不等号的方向决定对偶决策变量取值的正负。 例3 写出以下线性规划问题的对偶问题 本例表明：原问题的决策变量的取值决定其对偶约束条件不等号的方向。 对偶关系表 例4：根据对偶关系表写出下述线性规划的对偶规划 二、对偶性质 （1）对偶性：对偶问题的对偶是原问题； （2）弱对偶性：若X和Y分别是原问题（max）的任一可行解和对偶问题的任一可行解，则一定存在CX ≤ YB； （3）无界性：若原问题有无界解，则其对偶问题无可行解； （4）最优性：若X是原问题（max）的可行解， Y是对偶问题的可行解，当CX ＝ YB时，X是原问题的最优解，Y是对偶问题的最优解； （5）强对偶性：弱原问题有最优解，那么对偶问题也一定有最优解，且两者的目标函数值相等。 二、对偶性质 （6）互补松弛性：在线性规划的最优解中，若对应某一约束条件的对偶变量值为非零，则该约束条件取严格的等式；反之，若约束条件取严格的不等式，则其对应的对偶变量为零。 （7）用单纯形法求解线性规划问题时，迭代的每一步在得到原问题的一个基本可行解的同时，其检验数行σj的值是其对偶问题的一个基本解；在单纯形表中，原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量；这些互相对应的变量如果在一个问题的解中是基变量，则在另一个问题的解中是非基变量。 对性质7的说明 例：原问题 对偶问题 §3.3 对偶单纯形法 对偶单纯形法是利用的对偶原理来求解原问题的一种方法，而不是用来求解对偶问题； 之前第2章的单纯形法称为原始单纯形法。 注意： 对偶单纯形方法并不需要把原问题转化为对偶问题，只需利用原问题与对偶问题的数据相同（只是所处位置不同）这一特点，直接在反映原问题的单纯形表上进行计算； 对偶单纯形法并不要求原问题的初始解是基可行解，因此，可以从非可行的基解开始迭代，从而省去了引入人工变量的麻烦； 对偶单纯形法要求对偶问题的解始终是基可行解，即要求原问题的所有变量的检验数非负，这是对偶单纯形法应用的前提，十分苛刻，所以直接应用对偶单纯形法求解线性规划问题并不多见，主要用于灵敏度分析。 二、对偶单纯形法的计算步骤 例1：用对偶单纯形法求解LP问题 例2：用对偶单纯形法求解LP问题 二、对偶单纯形法中无可行解的识别 在对偶单纯形法中，总是存在着对偶问题的可行解，因此对于能用对偶单纯形法求解的线性规划问题来说，其解不存在无界解的可能； 对偶单纯形法无可行解的识别是通过入基变量选择失败来加以反映的，即当主行的所有元素均为非负时，线性规划问题无可行解。 例3：用对偶单纯形法求解下述线性规划问题 思考题： 问：是否存在某一单纯形表，既可用单纯形法求解，又可用对偶单纯形法法求解？ 答：不行 如果