《运筹学》课程教学资源（试卷习题）第3章 线性规划的对偶理论

第三章线性规划的对偶理论内容提要S3.1线性规划的对偶问题83.2 线性规划的对偶理论83.3对偶解的经济解释S3.4对偶单纯形方法83.5灵敏度分析

第三章线性规划的对偶理论 内容提要 §3.1 线性规划的对偶问题 §3.2 线性规划的对偶理论 §3.3 对偶解的经济解释 §3.4 对偶单纯形方法 §3.5 灵敏度分析

S 3.1 乡线性规划的对偶问题1．对偶问题的提出2.如何将原问题转化为对偶问题3.原问题与对偶问题的对应关系1.对偶问题的提出例3.1

§3.1 线性规划的对偶问题 1. 对偶问题的提出 2. 如何将原问题转化为对偶问题 3. 原问题与对偶问题的对应关系 1. 对偶问题的提出 例 3.1

某工厂拥有A、B、C三种类型的原料，生产甲、乙两种产品。每件产品在生产中消耗的原料数量，每件产品的价格以及三种原料可利用的数量如下表所示：原料数量产品乙甲原料(吨)300A1B2400C02250价格50（元/件）100

某工厂拥有A、B、C三种类型的原料，生 产甲、乙两种产品。每件产品在生产中消耗 的原料数量，每件产品的价格以及三种原料 可利用的数量如下表所示： 产品 原料 甲 乙 原料数量 （吨） A 1 1 300 B 2 1 400 C 0 2 250 价格（元/件） 50 100

问题：工厂应如何安排生产可获得最大的总收益？解：设变量x.为第种（甲、乙）产品的生产件数（i=1，2）。则有目标函数Maxz = 50x1+100x2S.t. Xi + X2 ≤3002xi + X2 ≤ 400X2 ≤ 2500X1,X2,X3,X4, X5 ≥

问题：工厂应如何安排生产可获得最大的总 收益？ 解：设变量xi为第i种（甲、乙）产品的生产 件数（i＝1，2）。则有 目标函数 Max z = 50x1 + 100x2 s.t. x1 + x2 ≤300 2x1 + x2 ≤ 400 x2 ≤ 250 x1 ,x2 ,x3 ,x4 ,x5 ≥ 0

现在考虑若三种原料都用于转让，试问：三种原料各如何收费才能即保证本厂的利益，有能最有竞争力？设y1，y2，y分别为每设备工时（或原料）每单位的收取费用，则有Min f = 300y,+ 400y2 + 250y3s.t.yi+2y2　≥ 50 （不少于甲产品的利润)yi+ y2+y3≥100（不少于乙产品的利润）Y1,Y2,y ≥ 0

现在考虑 若三种原料都用于转让，试问：三种原料各 如何收费才能即保证本厂的利益，有能最有 竞争力？ 设 y1 ，y2 ，y3 分别为每设备工时（或 原料）每单位的收取费用，则有 Min f = 300y1+ 400y2 + 250y3 s.t.y1+2y2 ≥ 50（不少于甲产品的利润） y1+ y2+y3 ≥100（不少于乙产品的利润） y1,y2 ,y3 ≥ 0

Max z= 50x + 100x2管理者模型一对互为对偶的模型s.t.X1 + X2 ≤300原问题2x + X2 ≤ 400X2 ≤ 250X1, X2≥ 0Min f = 300yi+ 400y2+ 250y3租赁者模型对偶问题≥50s.t.Yi+2y2Yi+ Y2+ y3≥100Y1, Y2, Y3 ≥ 0

Min f = 300y1+ 400y2+ 250y3 s.t. y1+2y2 ≥ 50 y1+ y2+ y3 ≥100 y1 , y2 , y3 ≥ 0 Max z = 50x1 + 100x2 s.t. x1 + x2 ≤300 2x1 + x2 ≤ 400 x2 ≤ 250 x1 , x2 ≥ 0 对 偶 问 题 租 赁 者 模 型 原 问 题 管 理 者 模 型 一 对 互 为 对 偶 的 模 型

（对称形式）对偶问题的定义：(LP)max Z=CiXi + C2X2 +... + CnXns.t.a11xi + a12X2 + ... + airrn≤biam1Xi+ am2X2 + ...+ amnXn ≤ b,X1,X2,... ,Xn ≥0(DP)min W=byi+ b2y2+ ... + bmyms.t.aiyi+ a21y2+ ... + am1ym ≥ Ciainyi+ a2ny2+... + amnym ≥CnYi, y2,... , Jm ≥ 0

对偶问题的定义： （对称形式） （LP ） max Z=c1 x1 + c2 x2 + . + cn xn s.t. a11x1 + a12 x2 + . + a1nxn  b1 . . . . . . am1x1 + am2x2 + .+ amn xn  bm x1 , x2 , . , xn  0 （DP） min W=b1 y1+ b2 y2+ . + bm ym s.t. a11y1+ a21 y2+ . + am1 ym  c1 . . . . . . a1ny1+ a2n y2+ . + amnym  cn y1 , y2 , . , ym  0

设：6aCyiaTYb2C2y2a22nX =b=Y=A=6xLCnaammlm2Y(LP) Max z= cT x(DP) Min f = bT ys.t. Ax ≤bS.t. ATy ≥ cx ≥0y≥0则（DP）称为（LP）的对称形式对偶问题

(LP) Max z = cT x (DP) Min f = bT y s.t. Ax ≤ b s.t. AT y ≥ c x ≥ 0 y ≥ 0 则（DP）称为（LP）的对称形式对偶问题 设：               = m m mn n n a a a a a a a a a A        1 2 21 22 2 11 12 1               = n x x x X  2 1               = n c c c C  2 1               = m y y y Y  2 1               = m b b b b  2 1

例3．2写出下面线性规划的对偶规划模型max = 3xj + 75x2 + 2x3 +x42xi +5x2 +6x3 + x4 ≤ 403xi +2x2 + X3 － x4 ≤ 50X -2x2 -3x3 +2x4 ≤ 20x, ≥ 0, j = 1,2,3,4解：按照对称形式的对偶关系，其对偶模型为

例3．2 写出下面线性规划的对偶规划模型         = − − +  + + −  + + +  = + + + 0, 1,2,3,4 2 3 2 20 3 2 50 2 5 6 40 max 3 75 2 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 x j x x x x x x x x x x x x x x x x j 解：按照对称形式的对偶关系，其对偶模型为

min f = 40yi + 50y2 +20y32yi +3y2 + y3 ≥35yi +22 2y3 ≥ 756yi + J2 -3y3 ≥2Ji J2 +2y2 ≥ 1J1,2,J3≥0

          − +  + −  + −  + +  = + + , , 0 2 1 6 3 2 5 2 2 75 2 3 3 min 40 50 20 1 2 3 1 2 2 1 2 3 1 2 3 1 2 3 1 2 3 y y y y y y y y y y y y y y y f y y y