第三节 线性规划对偶.ppt

例2:某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示。求获最大利润的方案。 Max z = 1500x1 + 2500x2 s.t. 3x1 + 2x2 ≤ 65 2x1 + x2 ≤ 40 原问题 3x2 ≤ 75 x1 ,x2 ≥ 0 Min f = 65y1+ 40y2 + 75y3 s.t. 3y1+2y2 ≥1500 （不少于甲产品的利润） 2y1+y2+3y3 ≥2500 对偶问题 （不少于乙产品的利润） y1, y2 , y3 ≥ 0 标准化： max z = - 2x1 - 3x2 - 4x3 s.t. -x1-2x2-x3+x4= -3 -2x1+x2-3x3+x5= -4 x1,x2,x3,x4,x5 ≥ 0 * 例3：求解线性规划问题： min f = 2x1 + 3x2 + 4x3 s.t. x1 + 2x2 + x3 ≥ 3 2x1 - x2 + x3 ≥ 4 x1 , x2 , x3 ≥ 0 二、对偶单纯形法 * 二、对偶单纯形法 * 单纯形法和对偶单纯形法步骤 是 是 是 是 否 否 否 否 所有 所有 得到 最优解 计算 计算 典式对应原规划的基本解是可行的 典式对应原规划的基本解的检验数 所有 所有 计算 计算 以为中心元素进行迭代 以为中心元素进行迭代 停 没有最优解 没有最优解 单纯形法 对偶单纯形法 * 讨论：对偶单纯形法的适用范围 对偶单纯形法适合于解如下形式的线性规划问题： 二、对偶单纯形法 * 在引入松弛变量化为标准型之后，约束等式两侧同乘-1，能够立即得到检验数全部非正的原规划基本解，可以直接建立初始对偶单纯形表进行求解，非常方便。 对于有些线性规划模型，如果在开始求解时不能很快使所有检验数非正，最好还是采用单纯形法求解。因为，这样可以免去为使检验数全部非正而作的许多工作。从这个意义上看，可以说，对偶单纯形法是单纯形法的一个补充。除此之外，在对线性规划进行灵敏度分析中有时也要用到对偶单纯形方法，可以简化计算。 二、对偶单纯形法 * 以上讨论线性规划时，把cj，aij，bi等均看成常数，但实际上这些数据有的是统计数据，有的是测量值，有的是专家评估得到的数据，并非绝对精确的，而且也不是绝对不变的。因此有必要分析这些数据发生波动时，对目前的最优解与最优目标值会产生什么样的影响？ ——灵敏度分析 两类问题： 1.c，A，b中某部分数据发生给定的变化； 2.研究1.c，A，b的波动范围，确保原最优解仍为最优解。 三、灵敏度分析 * 进一步理解最优单纯性表中各元素的含义 考虑问题： Max z = c1 x1 + c2 x2 + … + cn xn s.t. a11x1 + a12x2 + … + a1nxn = b1 a21x1 + a22x2 + … + a2nxn = b2 . am1x1 + am2x2 + … + amnxn = bm x1 ，x2 ，… ，xn ≥ 0 三、灵敏度分析 * 设xj = 0 j = m+1, … , n ; xi = bi’ i = 1 , … , m 是基本可行解, 对应的目标函数典式为：z = -f + ?m+1xm+1+…+ ?nxn 以下是初始单纯形表： m