第三章 线性规判问题的对偶与 灵敏度分析 本章内容重点 线性规划的对偶冋题概念、 理论及经济意义 线性规划的对偶单纯形法 线性规划的灵敏度分析
2 第三章 线性规划问题的对偶与 灵敏度分析 线性规划的对偶问题概念、 理论及经济意义 线性规划的对偶单纯形法 线性规划的灵敏度分析 本章内容重点
1.能性规物8偶问题 对偶原理 对偶问题定义- 线性规划 问题写出其对偶问题,要掌握在 对称形式和非对称情况下由原冋 题写出对偶问题的方法。 对偶定理- 只需了解原 题与对偶问题解的关系,证明从
3 1.线性规划对偶问题 对偶原理 对偶问题定义—— 线性规划 问题写出其对偶问题，要掌握在 对称形式和非对称情况下由原问 题写出对偶问题的方法。 对偶定理—— 只需了解原问 题与对偶问题解的关系，证明从 略
1.线性规利对偶问题 1.对偶问题: 若设备和原料都用于外协加工,工 厂收取加工费。试问:设备工时和原料 A、B各如何收费才最有竞争力? 设,y2,y分别为每设备工时 原料A、陈单位的收取费用
4 1.对偶问题： 若设备和原料都用于外协加工，工 厂收取加工费。试问：设备工时和原料 A、B 各如何收费才最有竞争力？ 设 y1 ，y2 ，y3 分别为每设备工时、 原料 A、B每单位的收取费用。 1.线性规划对偶问题
角1,线性规划对偶局题 Maxz=50x1+100x2 t.x1+x2≤300 400 ≤250 3,4,45 Minf=300y+400y2+250%3 s.t.y1+22>50(不少于甲产品的利润) +y2+3>100(不少于乙产品的利润)
5 Max z = 50x1 + 100x2 s.t. x1 + x2 ≤300 2x1 + x2 ≤ 400 x2 ≤ 250 x1 ,x2 ,x3 ,x4 ,x5 ≥ 0 Min f = 300y1+ 400y2 + 250y3 s.t. y1+2y2 ≥50（不少于甲产品的利润） y1+y2+y3 ≥100 （不少于乙产品的利润） y1, y2 , y3 ≥ 0 1.线性规划对偶问题
1.性规物划偶问题 对偶定义 对称形式 互为对偶 (LP)Max z=cTx ( DP)Min f=bTy s.t. Ax 0 y≥0 Max --
6 2、对偶定义 对称形式： 互为对偶 (LP) Max z = c T x (DP) Min f = b T y s.t. Ax ≤ b s.t. AT y ≥ c x ≥ 0 y ≥ 0 “Max -- ≤ ” “Min-- ≥” 1.线性规划对偶问题
1,线性规划划偶题 对对称形式的对偶规划之间具有 下面的对应关系。 (1)若一个模型为目标求“极大”, 约束为“小于等于”的不等式,则它的 对偶模型为目标求“极小”,约束是 “大于等于”的不等式。即“max,≤” 和“min,>”相对应
7 一对对称形式的对偶规划之间具有 下面的对应关系。 (1)若一个模型为目标求“极大” ， 约束为“小于等于”的不等式，则它的 对偶模型为目标求“极小” ，约束是 “大于等于”的不等式。即“max，≤” 和“min，≥”相对应。 1.线性规划对偶问题
1,线性规划划偶题 (2)从约束系数矩阵看:一个模型中 为A,则另一个模型中为A。一个模型 是m个约東,n变量。则它的对偶模型 为n个约東,m个变量。 (3)从数据b、C的位置看:在两个规 划模型中,和C的位置对换。 (4)两个规划模型中的变量皆非负
8 (2)从约束系数矩阵看：一个模型中 为Ａ，则另一个模型中为A T 。一个模型 是m个约束，n个变量，则它的对偶模型 为n个约束，m个变量。 (3)从数据b、C的位置看：在两个规 划模型中，b和C的位置对换。 (4)两个规划模型中的变量皆非负。 1.线性规划对偶问题
自1.线性规划对偶问题 非对称形式的对偶规坩 投称不具有对称形式的一对线性规划为 非对称形式的对偶规划。 对于非对称形式的规划。可以按照下面 的对应关系直接给出其对偶规划。 (1)将模型统一为“max,≤”或“min, ”的形式,对于其中的等式约束按下面 (2)、(3)中的方法处理 (2)若原规划的某个约束条件为等式约束, 则在对偶规划中与此约束对应的那个变量取值 没有非负限制;
9 非对称形式的对偶规划 一般称不具有对称形式的一对线性规划为 非对称形式的对偶规划。 对于非对称形式的规划，可以按照下面 的对应关系直接给出其对偶规划。 （1）将模型统一为“max，≤”或“min， ≥” 的形式，对于其中的等式约束按下面 （2）、（3）中的方法处理； （2）若原规划的某个约束条件为等式约束， 则在对偶规划中与此约束对应的那个变量取值 没有非负限制； 1.线性规划对偶问题 1 x2 x3 xj 0 1 y11 a23 1 b2 y21 a23 2 b 3 y31 a23 3 b 4 y41 a23 4 b y j 0 1 c2 c3 c 1 x2 x3 xj 0 1 y11 a23 1 b2 y21 a23 2 b 3 y31 a23 3 b 4 y41 a23 4 b y j 0 1 c2 c3 c 1 x2 x3 xj 0 1 y11 a23 1 b2 y21 a23 2 b 3 y31 a23 3 b 4 y41 a23 4 b y j 0 1 c2 c3 c
1,线性规划划偶题 (3)若原规划的某个变量的值没有非负限 制。则在对偶问题中与此变量对应的那个 约東为等式。 下面对关系(2)作一说明。对于关系(3) 可以给出类似的解释。 设原规划中第一个约束为等式: b 那么,这个等式与下面两个不等式等价
10 （3）若原规划的某个变量的值没有非负限 制，则在对偶问题中与此变量对应的那个 约束为等式。 下面对关系（2）作一说明。对于关系（3） 可以给出类似的解释。 设原规划中第一个约束为等式： a11x1 + … + a1n xn = b1 那么，这个等式与下面两个不等式等价 1.线性规划对偶问题
1,线性规划划偶题 a1x1+..+a1x b a1x1+….+a1nxn≤b 这样,原规划模型可以写成 maxZ=c1x1+…+Cnxn +a1xn≤b m12x1+…+c b mn n 0,j=1,2,…,m
11 1.线性规划对偶问题 这样，原规划模型可以写成