[第二章线性规划的对偶理论1.pptVIP

一、对偶问题的提出 二、原问题与对偶问题的数学模型 三、原问题与对偶问题的对应关系 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 【例】某工厂利用现有的三种资源生产两种产品，有关数据如下表： 设备A 设备B 调试工序 利润（元） 0 6 1 2 5 2 1 1 15时 24时 5时 产品Ⅰ 产品Ⅱ 资源 一、对偶问题的提出 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 如何安排生产， 使获利最多？ 厂 商 设 Ⅰ产量为 Ⅱ产量为 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 设：设备A 元／时 设备B 元／时 调试工序 元／时 收 购 方 付出的代价最小， 且对方能接受。 出让代价应不低于 用同等数量的资源 自己生产的利润。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 设备A 设备B 调试工序 利润（元） 0 6 1 2 5 2 1 1 15时 24时 5时 Ⅰ Ⅱ D 厂家能接受的条件： 收购方的意愿： 单位产品Ⅰ出租 收入不低于2元 单位产品Ⅱ出租收入不低于1元 出让代价应不低于 用同等数量的资源 自己生产的利润。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 对 偶 问 题 原 问 题 一对对偶问题 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 原问题的一般模型可定义为： 对偶规划的一般数学模型 n n x c x c x c Z + + + = ... max 2 2 1 1 s.t. 1 1 2 12 1 11 ... b x a x a x a n n ￡ + + + 2 2 2 22 1 21 ... b x a x a x a n n ￡ + + + … … …. m n mn m m b x a x a x a ￡ + + + ... 2 2 1 1 0 ,..., , 2 1 3 n x x x 相应的对偶问题的一般模型可定义为： m m y b y b y b S + + + = ... min 2 2 1 1 s.t. 1 1 2 21 1 11 ... c y a y a y a m m 3 + + + 2 2 2 22 1 12 ... c y a y a y a m m 3 + + + … … … n m mn n n c y a y a y a 3 + + + ... 2 2 1 1 0 ,..., , 2 1 3 m y y y Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 原问题与对偶问题的对应关系 讨论对偶问题时必定是指一对问题，因为没有原问题也就不可能有对偶问题。原问题和对偶问题总是相依存在的。同时，原问题和对偶问题之间也并没有严格的界线，它们互为对偶，谁都可以是原问题，谁也都可以是对偶问题。 下表给出了原问题模型和模型的对应关系，这些也可以看作是一个线性规划原问题转化为对偶问题的一般规律。 原问题线性规划模型