[理学]运筹学02_对偶理论与敏感性分析.ppt

 线性规划的对偶问题概念、理论及经济意义 线性规划的对偶单纯形法 线性规划的灵敏度分析 §1.线性规划对偶问题 对偶问题的提出 例1.1:某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示： max z =1500x1 + 2500x2? s.t. 3x1 + 2x2 ≤ 65 2x1 + x2 ≤ 40 3x2 ≤ 75 x1, x2 ≥ 0? 设 y1, y2, y3 分别为每工时设备A、B、C 的出租费。 max z = 1500x1 + 2500x2 s.t. 3x1 + 2x2 ≤ 65 2x1 + x2 ≤ 40 原问题 3x2 ≤ 75 x1, x2 ≥ 0 min w = 65y1 + 40y2 + 75y3 s.t. 3y1 + 2y2 ≥1500 2y1 + y2 + 3y3 ≥ 2500 对偶问题 y1, y2, y3 ≥ 0 对偶问题的定义 对称形式：互为对偶 (LP) max z = c x (DP) min w = y b s.t. Ax ≤ b s.t. y A ≥ c x ≥ 0 y ≥ 0 注意： x为列向量, y为行向量。 原问题的最优单纯形表中关于对偶问题的最优解的信息： (LP) max z = cx (DP) min w =y b 　 s.t. Ax ≤ b 　s.t. yA ≥ c x ≥ 0 　　 y ≥ 0 max z = cx 标准化 max z = cx + 0xs s.t. Ax ≤ b s.t. Ax + Ixs = b x ≥ 0 x, xs ≥ 0 举列说明： 设原规划中第一个约束为等式： a11x1 + … + a1nxn = b1 那么，这个等式与下面两个不等式等价 a11x1 + … + a1nxn ? b1 a11x1 + … + a1nxn ? b1 此时已转化为对称形式，直接写出对偶规划 §2. 对偶问题的基本性质 推论(无界性) 若(LP)具有无界解，则(DP)无可行解。 注：反之则不一定成立。 (DP)无可行解，对应(LP)或有无界解，或无可行解 定理2.2 (最优性定理) 若x*, y*分别(LP)和(DP)的可行解，且 cx* = y*b, 那么x*, y*分别为(LP)和(DP)的最优解。 max z =2x1 + 4x2+x3+x4 s.t. x1 + 3x2 + x4 ≤ 8 2x1 + x2 ≤ 6 x2 + x3 + x4 ≤ 6 x1 + x2 + x3 ≤ 9 xj ≥ 0? 1.建立初始对偶单纯形表,对应一个基本解,所有检验数均为负,转步骤2； 2.若b’≥0,则得到最优解,停止;否则,若有bk =min {bi0}则选k行的基变量为出基变量,转步骤3 3.若所有akj’≥0( j = 1,2,…,n