对偶规划.PPTVIP

第四节 线性规划的对偶问题 （一）对偶问题的提出 （二）对偶规划的形式 1. 对称形式的对偶问题 2. 非对称形式的对偶问题 3. 一般形式对偶问题 （三）对偶规划的基本性质 （一）对偶问题的提出 例2 假设营养科不安排生产食品A、B、C、D，而出售单一营养成分的糖、蛋白质和脂肪。仍用例1中的数据，问该营养科如何确定糖、蛋白质和脂肪的单价，才能在市场竟争中立于不败之地，并可获得利润最多？ 同理有： 2y1 + 2y2 + y3 ≤ 0.7 4y1 + y2 + 2y3 ≤ 0.9 2y1 + 4y2 + 5y3 ≤ 1.2 我们应用单纯形法求解例1和例2，将会发现原规划的最后单纯形表不仅给出了原规划的最优解，而且它的对应的检验行Cj-Zj也给出了对应的对偶规划的最优解（符号相反）。 (二) 对偶规划的形式 对于一般的线性规划模型可以直接给出其对偶规划模型，并不需要像上面那样经过一番讨论。为此，我们需要分析原规划与对偶规划之间的关系。对偶规划的形式分为对称形式和非对称形式。 例1和例2中的一对规划就是对称形式的 （1）若一个模型目标函数是求“极大”，约束条件为“小于等于”的不等式，则对偶模型的目标函数是求“极小”，约束是“大于等于”的不等式 ； 即 “ Max，≤ ” ? “ Min， ≥ ” （2）若一个模型有n个变量， m个约束条件,则对偶模型有n个约束条件；m个变量； （3）一个模型目标函数中价值系数等于对偶模型中相应约束条件的右端常数；一个模型约束条件中的右端常数等于对偶模型目标函数中相应的价值系数； （4）若一个模型约束条件中的系数矩阵为 A，则对偶模型约束条件中的系数矩阵为A转置矩阵 AT； （5）两个规划模型中的变量皆非负。 例3 求下列线性规划的对偶规划（书中例15） 解：这两个模型都是对称形式的规划模型，它们的对偶规划分别为： 2. 非对称形式的对偶问题 对于非对称形式的规划，可以按照下面的对应关系直接给出其对偶规划。 （1）将模型统一为“max，≤”或“min，≥” 的形式，对于其中的等式约束按下面（2）、（3）中的方法处理； （2）若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制； （3）若原规划某个变量的值没有非负限制，则在对偶问题中与此变量对应的那个约束为等式。 例4 写出下面线性规划的对偶规划模型 再根据非对称形式的对应关系，直接写出对偶规划 例5 设有线性规划问题（书中例16） 对偶变量 x1 x2 x3 x4 试写出它的对偶问题。 解：对偶规划为： 对偶变量 y1 y2 * * *第一节??线性规划问题及其数学模型 *第二节 线性规划问题的图解法 *第三节 单纯形法 *第四节 线性规划的对偶问题 *第五节 线性规划在卫生管理中的应用 第二章??线性规划 标准的线性规划模型不含有明显的单位基 ——人工变量法 引入人工变量 xn+i ≥ 0，i = 1 ,…, m； x1, x2 ... xn , xn+1, …, xn+m ≥ 0 a11 x1+ a12 x2+ … + a1n xn+ xn+1 = b1 a21 x1+ a22 x2+ … + a2n xn + xn+2 = b2 am1 x1+ am2 x2+ … + amn xn + xn+m = bm ... ... 上次课内容复习 大 M 法： 引入充分大正数 M ，改造目标函数 Max Z = c1 x1 + c2 x2 + cn xn - M xn+1 - … - M xn+m 上次课内容复习 a11 x1 + a12 x2 + … + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + … + a2n xn + xn+2 = b2 . .