第二章 线性规划的对偶理论(1).ppt

1、第二章 线性规划的对偶问题,一、对偶问题的提出 二、原问题与对偶问题的数学模型 三、原问题与对偶问题的对应关系,【例】某工厂利用现有的三种资源生产两种产品，有关数据如下表：,一、对偶问题的提出,如何安排生产， 使获利最多？,厂 商,设 产量为 产量为,设：设备A 元时 设备B 元时 调试工序 元时,收 购 方,付出的代价最小， 且对方能接受。,出让代价应不低于 用同等数量的资源 自己生产的利润。,厂家能接受的条件： 收购方的意愿：,出让代价应不低于 用同等数量的资源 自己生产的利润。,对 偶 问 题,原 问 题,一对对偶问题,原问题的一般模型可定义为：,对偶规划的一般数学模型,相应的对偶问题的

2、一般模型可定义为：,原问题与对偶问题的对应关系,讨论对偶问题时必定是指一对问题，因为没有原问题也就不可能有对偶问题。原问题和对偶问题总是相依存在的。同时，原问题和对偶问题之间也并没有严格的界线，它们互为对偶，谁都可以是原问题，谁也都可以是对偶问题。,下表给出了原问题模型和模型的对应关系，这些也可以看作是一个线性规划原问题转化为对偶问题的一般规律。,原问题线性规划模型,对偶线性规划模型,原问题为maxZ的线性规划问题对偶关系表,由原模型三个约束条件确定对偶模型有三个变量y1,y2,y3,（还可依对偶问题写出原问题）,例1,写出下列问题的对偶问题：,min w=15y1+24y2+5y3,6y2+

3、y3 2 5y1 +2y2 +y3 1,s.t.,y1 , y2 , y3 0,原问题为minS的线性规划问题对偶关系表,由原模型三个约束条件确定对偶模型有三个变量y1,y2,y3,s.t.,，,写出下列问题的对偶问题：,s.t.,1,3,2,1,+,-4,x,x,2x,x1,x2,x3 0,，,例:,对偶问题为,3 对偶问题的基本性质 原问题 对偶问题,性质1：弱对偶性。如果 是原问题的可行解， 是其对偶问题的可行解，则恒有 性质2：最优性。如果 是原问题的可行解，是其对偶问题的可行解，且有 则 分别为原问题与对偶问题的最优解。,性质3：无界性。如果原问题（对偶问题）为无界解，则其对偶问题（

4、原问题）无可行解。反之，则不成立。 性质4：强对偶性（对偶定理）。如果原问题有最优解，则其对偶问题也一定具有最优解，且有max z=min。 性质5：互补松弛性。在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非0，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为0.即,性质6：线性规划的原问题与其对偶问题之间存在一对互补的基解，其中原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量；这些互相对应的变量如果在一个问题的解中是基变量，则在另一个问题的解中是非基变量；将这对互补的基解分别代入原问题和对偶问题的目标函数有z=。,对 偶 问

5、 题,原 问 题,原问题化为极小问题，最终单纯形表：,对偶问题用两阶段法求解的最终的单纯形表,化为极小问题,原问题 最优解,对偶问题 最优解,原问题化为极小问题，最终单纯形表：,两个问题作一比较: 1.两者的最优值相同 2.变量的解在两个单纯形表中互相包含 原问题最优解（决策变量） 对偶问题最优解（决策变量）,对偶单纯形法,由对偶问题的基本性质6知，用单纯形法求解线性规划问题时，在得到原问题的一个基可行解的同时，在检验数行得到对偶问题的一个基解，并且将两个解分别代入各自的目标函数时其值相等。,单纯形法求解的基本思想：保持原问题为可行解，通过迭代，增大目标函数，当其对偶问题的解也为可行解时，就达到了目标函数的最优值。 对偶单纯形法的基本思想：保持对偶问题为可行解，通过迭代，减小目标函数