第四章对偶问题及对偶单纯形法 无论从理论方面，还是实际应用方面，对偶理论是线性规划的重要的基础理论之 其主要内容是：每一个线性规划问题（称为原问题），都有一个与之对应的线性规划问题( 称为对偶问题)，原问题和对偶问题之间存在着密切的关系，在求出一个问题的解的同时 也自动的给出了另一个问题的解。 第一节对偶问题的提出 为了说明原问题和对偶问题间的关系，首先介绍下面例题中的线性规划问题的对偶 问题 例1.某养鸡场所用的饲料由A、B、C三种配料组成，表4-1给出了各种配料所含的 营养成份、单位成本及1份混合饲料必须含有的各种营养成分.问如何配制混合饲料使 饲料成本最小？ 表4-1 营养戚分 D 单位成本 配 1 1/2 B 1 C 1 1/4 1份饲料应含量 20 6 10 设 x,=混合饲料中第种配料的含量.行=A.B.C 则这个问题的线性规划模型是 min z=6xA+3IB+2Xo (4.1) 满足 xA+xB+xC≥20， rA+xB+xC≥6， 2xA+xB+xC≥10， (4.2) ≥0，对一切 现设想有一个饲料厂，制造含有这三种营养成分各1单位的营养丸.他们知道养鸡 场对混合饲料的要求，因此在制订营养丸的价格时，每丸D、E、F营养丸的价格分别定 为9、29，养鸡场采购1单位的配料4，相当于对这3种普养丸分别采购122丸等 等。因此问料厂定营养丸的价格时，必须有： q1+2+2g≤6， 01+2+03≤3， 1+2+g≤2 (4.3) g≥0，i=1.2.3 否则养鸡场就会向别处购买配料而不买营养丸.显然(13)就是饲料厂决定营养丸售 价时的线性规划模型的约束条件方程。目标函数是要求相当于1份混合饲料的营养丸的 1
✂✁☎✄ ✆✞✝✞✟✞✠✞✡✞✆✞✝☞☛☞✌☞✍☞✎ ✏✒✑✒✓✒✔✒✑✒✕✒✖, ✗✒✘✒✙✒✚✒✛✒✜✕✒✖, ✢✒✣✔✒✑✘✒✤✒✥✒✦✒✧✒★✒✩✒✪✒★✒✫✒✬✔✒✑✒✭✒✮✒✯ ✰✒✱✪✳✲✵✴✒✘: ✶ ✮✒✷✤✒✥✒✦✒✧✒✸✒✹ (✺✒✻✒✼✒✸✒✹), ✽✒✾✮✒✷✒✿✒✭✢✒✛✒★✒✤✒✥✒✦✒✧❀✸❀✹ ( ✺❀✻❀✢❀✣❀✸❀✹), ✼❀✸❀✹❀❁❀✢❀✣❀✸❀✹✭❀❂❀❃❀❄❀❅❀❆❀❇★❀❈❀❉, ❄❀❊❀❋❀✮❀✷✸❀✹❀★❀●❀★❀❍❀■ ❏▲❑◆▼★✒❖❋✒P✒◗✒✮✒✷✸✒✹✒★✒●✯ ❘❚❙❚❯ ❱❚❲❚❳❚❨❚❩❭❬❫❪ ✻ P❀❴❛❵✼❀✸❀✹❀❁❀✢❀✣❀✸❀✹❂ ★❀❈❀❉, ❜❀❝❀❞❀❡❀❢✖❀❣✹❛❤✐★❀✤❀✥❀✦❀✧❀✸❀✹❀★❀✢❀✣ ✸✒✹✯❥ 1. ❦✒❧✒♠✒♥✒♦✒✜✒★✒♣✒q✳r As B s C t✒✉✒✈✒q✒✇✒①, ② 4–1 ❖ ❋✒P✒③✉✒✈✒q✒♦✒④✒★ ⑤❧❀①❀⑥❀s⑧⑦❀⑨❀①❀⑩❀❶ 1 ⑥❀❷❀❸❀♣❀q❀❹❀❺❀④❀✾❀★③ ✉ ⑤❧❀①❀❻✯ ✸❀❼❀❽❀✈❀❾❀❷❀❸❀♣❀q❀❿ ♣✒q✒①✒⑩✒➀✒➁? ➂ 4–1 ➃➅➄➅➆➅➇ ➈➅➉ D E F ➊➅➋➆➅➌ A 1 1/2 2 6 B 1 1/2 1 3 C 1 1/4 1 2 1 ➍➅➎➉➅➏➅➐➅➑ 20 6 10 ➒ xj = ❷✒❸✒♣✒q✳❤✵➓ j ✉✒✈✒q✒★✒④✒➔, j = A, B, C, →✒➣✷ ✸✒✹✒★✒✤✒✥✒✦✒✧✒↔✒↕✒✘ min z = 6xA + 3xB + 2XC (4.1) ➙✒➛ xA + xB + xC ≥ 20, 1 2 xA + 1 2 xB + 1 4 xC ≥ 6, 2xA + xB + xC ≥ 10, xj ≥ 0, ✢ ✮✒❇j. (4.2) ➜➒❀➝✾✮❀✷♣❀q❀➞, ❾❀➟❀④❀✾➣ t❀✉⑤❧❀①❀❻③ 1 ⑦❀⑨❀★⑤❧❀➠✯◆➡❀➢❀➤❀➥❧❀♠ ♥❀✢❀❷❀❸❀♣❀q❀★❀✪❊ , ➦❀➧❄ ❾❀➨⑤❧❀➠❀★❀➩❀➫❀■, ✶❀➠ Ds E s F ⑤❧❀➠❀★❀➩❀➫❀❻❀➭❀➯ ✻ q1 s q2 s q3 ✯ ❧✒♠✒♥✒➲✒➳ 1 ⑦✒⑨✒★✒✈✒q A, ➵✒➸✒➺✒✢➣ 3 ✉ ⑤❧✒➠✒❻✒➭✒➲✒➳ 1,1/2,2 ➠✒➻ ➻ ✯ ➦✒➧✒♣✒q✒➞✒➯⑤❧✒➠✒★✒➩✒➫✒■, ❹✒❺✒✾: q1 + 1 2 q2 + 2q3 ≤ 6, q1 + 1 2 q2 + q3 ≤ 3, q1 + 1 4 q2 + q3 ≤ 2, qi ≥ 0,i = 1, 2, 3 (4.3) ➼→❧➽♠➽♥➽➾➽➚➶➪➹➭➽➘➽➳✒➴✒✈➽q✒➷➽➬✒➴⑤❧✒➠✯➱➮✒✃ (1.3) ➾➽✘➽♣➽q➽➞➽❐➽➯⑤❧➽➠➽❒ ➩✒■✒★✒✤✒✥✒✦✒✧✒↔✒↕✒★✒❮✒❰✒Ï✒Ð✕✒Ñ❀✯➽Ò◆Ó❀Ô✒Õ✘✒✪❊ ➵✒➸❀➺ 1 ⑥✒❷✒❸✒♣✒q✒★⑤❧✒➠✒★ 1
2 第四章对偶问题及对倡单纯形法 售价最大，即 maxD=20q1+692+10qg (4.4) 线性提划间题(1.1)、(1.2)和线性却划回题(1.3)、(1.4)之问右着密切的关系.实际上 这两个问题最优解的目标函数值相同（根据两个问题追求的目标，从直观上不难理解这 点)。 线性规划问题(1.3)和(1.4)就是原问题（线性规划问题(1.1）和(1.2)的对偶问题 实际上，对每一个线性规划问题都伴随着另一个线性规划问题，称为对偶问题。原来的线 性规划问题称为原始问题（或原问题）.值得说明的是，并不是对每一个线性规划问题（即 使是一个实际问题的对偶问题都可以象上面例题一样观地从经济上加以解释。 第二节建立对偶问题的规则 一、建立对偶问题的规则 比较线性规划问题(1.1)、(12)和线性规划问题(13)、(1.4)，不难发现原问题和对偶 可题之间的一些关系 一般地.如果原问题为如下形式的线性规划问题 maxz=CT1+C2x2十.，.+Cnxn 满足 a111+a122+…+a1mn≤b a21x1+022r2+..·+02mrn≤02 (1.5) aml1+am22+…+amnn≤br ≥0j=1,2,,n 则按照以下规则建立它的对偶问题： (一入、原问题和对偶问题的决策变量的意义不同，本书用：表示对偶问题的决策变 量 二)、如果原问题的目标函数是“max”应.则其约束条件方程必须是“<”形式.此 时对偶问题的目标函数是“mim”型，其约束条件方程全是“≥”形式.反之亦然.这就是 说，在建立对偶问题之前，原向题的约束方程中的不等号必须指向一律而且与追求目标函 数最大或最小相对应： (仨)、对偶问题的目标函数的系数是原问题约束条件方程的右端的值： (四)、对偶问题的系数矩阵为原向题的系数矩阵的转置矩阵 (伍五、对偶问题的约束条件方程的右端值是原问题目标函数中决策变量的系数；但 在建立对偶问题之前，若原问题的松地变量或多余变量的C;不为0，则将它看成实际变 量 根据以上规则，原问题(1.5)的对偶问题是 min w big1 +b292+...+bmqm
2 Ö✳×✵ØÚÙ✒Û✳Ü✵Ý✒Þ✒Ù✒Û✒ß✒à✒á✳â ❒✒➩✒➀✒ã, ä max w = 20q1 + 6q2 + 10q3. (4.4) ✤✒✥✒✦✒✧✒✸✒✹ (1.1)s (1.2) ❁✒✤✒✥✒✦✒✧✒✸✒✹ (1.3)s (1.4) ✭✒❂✾ ❅✒❆✒❇★✒❈✒❉, ✙✒✚✒å ➣✒æ✷ ✸✒✹✒➀✒ç✒●✒★ Ò◆Ó✒Ô✒Õ✒è➵✒❍ (é✒êæ✷ ✸✒✹✒ë❊ ★ Ò◆Ó, ✓✒ì✒íå✒➬✒î✔●➣✮ ï )✯ ✤✒✥✒✦✒✧✒✸✒✹ (1.3) ❁ (1.4) ➾✒✘✒✼✒✸✒✹ (✤✒✥✒✦✒✧✒✸✒✹ (1.1) ❁ (1.2)) ★✒✢✒✣✒✸✒✹✯ ✙✒✚✒å, ✢✒✶✮✒✷✤✒✥✒✦✒✧✒✸✒✹✒✽✒ð✒ñ❅✒◗✒✮✒✷✤✒✥✒✦✒✧✒✸✒✹, ✺✒✻óò✒ô✒õ✒ö✯ ✼✒÷✒★✒✤ ✥✒✦✒✧✒✸✒✹✒✺✒✻ùø✒ú✒õ✒ö (û✒ø✒õ✒ö)✯üè✒ý✒❴✳❵★✒✘, þ✒➬✒✘✒✢✒✶✮✒✷✤✒✥✒✦✒✧✒✸✒✹ (ä ❿✒✘✮✒✷✙✒✚✒✸✒✹) ★✒✢✒✣✒✸✒✹✒✽✒ÿ✁✁✂✒å✖✒❣✹ ✮✁✄✒ì✒í✁☎✒✓✁✆✁✝å✁✞✁✒●✁✟✯ ❘✡✠❚❯ ☛✡☞❚❱❚❲❚❳❭❨❭❩✍✌✏✎ ✑s✓✒✁✔✒ò✒ô✒õ✒ö✁✕✁✖✁✗ ✘✚✙✤✒✥✒✦✒✧✒✸✒✹ (1.1)s (1.2) ❁✒✤✒✥✒✦✒✧✒✸✒✹ (1.3) s (1.4), ➬✒î✁✛➜✼✒✸✒✹✒❁✒✢✒✣ ✸✒✹✭✒❂★✮✁✜❈✒❉✯ ✮✁✢✁☎. ❼✁✣✒✼✒✸✒✹✒✻✒❼✒❢✁✤✁✥✒★✒✤✒✥✒✦✒✧✒✸✒✹: max z = c1x1 + c2x2 + . . . + cnxn ➙✒➛ a11x1 + a12x2 + . . . + a1nxn ≤ b1 a21x1 + a22x2 + . . . + a2nxn ≤ b2 . . . am1x1 + am2x2 + . . . + amnxn ≤ bm xj ≥ 0, j = 1, 2, . . . , n (4.5) →✁✦✁✧✒❢✒✦→✁★✁✩✁✪★✒✢✒✣✒✸✒✹: (✮ )s◆✼❀✸❀✹❀❁❀✢❀✣❀✸❀✹❀★❀❐✬✫✬✭❀➔❀★✬✮✰✯❀➬❍, ⑩✬✱❀✜ qi ②✬✲❀✢❀✣❀✸❀✹❀★❀❐✬✫✬✭ ➔; (✳)s◆❼✬✣❀✼❀✸❀✹❀★ Ò Ó❀Ô❀Õ✘ “max” ↕, →✰ ❮❀❰❀Ï❀Ð✕❀Ñ❹❀❺❀✘ “≤” ✤✬✥✯ ➧ ■✒✢✒✣✒✸✒✹✒★ Ò◆Ó✒Ô✒Õ✘ “min” ↕, ✰ ❮✒❰✒Ï✒Ð✕✒Ñ✁✴✘ “≥ ” ✤✁✥✯✓✵✒✭✁✶✒✃✒✯ ➣ ➾✒✘ ❴ , ❄★✁✩✢✒✣✒✸✒✹✭✁✷, ✼✒✸✒✹✒★✒❮✒❰✕✒Ñ ❤✵★✒➬✒➻✁✸✒❹✒❺✁✹✳➪✮✁✺➷✁✻✿ë ❊▲Ò◆Ó✒Ô Õ ➀✒ã✁✼✒➀✒➁✒➵✒✢✒✛; (t)s⑧✢✒✣✒✸✒✹✒★ Ò◆Ó✒Ô✒Õ★✒❉Õ ✘✒✼✒✸✒✹✒❮✒❰✒Ï✒Ð✕✒Ñ★✁✽✁✾✒★è bi ; (✿)s⑧✢✒✣✒✸✒✹✒★✒❉Õ✁❀✁❁✻✒✼✒✸✒✹✒★✒❉Õ✁❀✁❁★✁❂✁❃❀✁❁; (❄)sü✢✒✣✒✸✒✹✒★✒❮✒❰✒Ï✒Ð✕✒Ñ★✁✽✁✾è ✘✒✼✒✸✒✹ Ò◆Ó✒Ô✒Õ❤✵❐✁✫✁✭✒➔✒★✒❉Õ cj ; ❅ ❄★✬✩✢❀✣❀✸❀✹✭✬✷, ❆❀✼❀✸❀✹❀★✬❇✬❈✬✭❀➔✬✼✬❉✬❊✬✭❀➔❀★ cj ➬❀✻ 0, →✬❋✬✪✬●①❀✙❀✚✬✭ ➔ ✯ é✒ê✁✒å✒✦→ , ✼✒✸✒✹ (1.5) ★✒✢✒✣✒✸✒✹✒✘: min w = b1q1 + b2q2 + . . . + bmqm
3 满足 a11+a212+.+am1gm≥q a1291+a2292+.…+am29m≥2 (4.6) 20,j=1,2.,m 如果把原问题和对偶问题列在一个表中，它们之间的关系就更加清楚，从横向看是原 问题，从纵向看是对偶问题， T2 原始约束 min w Q11 a12 01 01 对偶约束 max z CI Co 把表中的数a的每一行与王，对应的乘起来相加后不大于这一行旁边的数，就是 原问题的一个约束条件，最后 一行的与，对应的乘起来相加就是原问题的目标函数 类似地，把数的每一列与9：对应的乘起来相加后不小于C,就是对偶原问题的一个 约束条件；最后一列的，与：对应的乘起来相加就是对偶原问题的目标函数为了讨论方 便也可将原问题写成下列形式： max =CX; 满足/Ar≤6 1X≥0. (4.7) 式(1.7)的对偶问题是： min w=Ob: 满足/QA≥C (Q≥0 (4.8 或 min w bTQT: 满{092 其中Q-(q1,91,,9m 二、原问题不符合上述规则的处理
3 ➙✒➛ a11q1 + a21q2 + . . . + am1qm ≥ c1 a12q1 + a22q2 + . . . + am2qm ≥ c2 . . . a1nq1 + a2nq2 + . . . + amnqm ≥ cn qj ≥ 0, j = 1, 2, . . . , m (4.6) ❼✁✣✁❍✒✼✒✸✒✹✒❁✒✢✒✣✒✸✒✹✁■❄✒✮✒✷②✳❤, ✪➢✒✭✒❂★✒❈✒❉✒➾✁❏✁✞✁❑✁▲, ✓✁▼ ➪●✘✒✼ ✸✒✹, ✓✁◆ ➪●✘✒✢✒✣✒✸✒✹✯ xj x1 x2 . . . xn ✼✁❖✒❮✒❰ min w qi q1 a11 a12 . . . a1n ≤ b1 q2 a21 a22 . . . a2n ≤ b2 . . . . . . . . . . . . . . . . . . . . . qm am1 am2 . . . amn ≤ bm ✢✒✣✒❮✒❰ ≥ ≥ . . . ≥ max z c1 c2 . . . cn ❍✒②✳❤✵★Õ aij ★✒✶✮✁P✒✿ xj ✢✒✛✒★✁◗✁❘✒÷✒➵✁✞✁❙✒➬✒ã✒➺➣✮✁P✁❚✁❯★Õ bi ❱ ➾✒✘ ✼➽✸➽✹➽★✮➽✷❮➽❰➽Ï➽Ð❳❲ ➀❳❙✮❳P★ cj ✿ xj ✢➽✛➽★❳◗❳❘➽÷➽➵❳✞➽➾➽✘➽✼➽✸➽✹➽★ Ò⑧Ó➽Ô➽Õ➽✯ ❨✁❩☎ ❱ ❍Õ aij ★✒✶✮ ■✿ qi ✢✒✛✒★✁◗✁❘✒÷✒➵✁✞✁❙✒➬✒➁✒➺ cj ❱ ➾✒✘✒✢✒✣✒✼✒✸✒✹✒★✮✒✷ ❮➽❰➽Ï➽Ð❳❲ ➀❳❙✮ ■➽★ bi ✿ qi ✢➽✛➽★❳◗❳❘➽÷➽➵❳✞➽➾➽✘➽✢➽✣✒✼✒✸➽✹✒★ Ò◆Ó➽Ô✒Õ✻ P✁❬➽✑✒✕ ❭ , ❏ ÿ ❋ ✼✒✸✒✹✁❪✒①✒❢✁■✁✤✁✥: max z = CX; ➙✒➛ ( AX ≤ b, X ≥ 0. (4.7) ✥ (1.7) ★✒✢✒✣✒✸✒✹✒✘: min w = Qb; ➙✒➛ ( QA ≥ C, Q ≥ 0. (4.8) ✼ min w = b TQ T ; ➙✒➛ ( ATQT ≥ C T , Q ≥ 0. ✰ ❤Q = (q1, q1, . . . , qm). ❫ s⑧ø✒õ✒ö✁❴✁❵✁❛✁❜✁❝✁✖✁✗✁✕✁❞✁❡
￥ 第四章对偶问题及对偶单纯形法 的立对偶问题之个，必须对原间题下了处理，使之符合个中要求： (一入、若原问题是求目标函数最大而约束条件方程为“≥”形式，则将该约束条件方 程两端乘以一1，把约束条件，成“≤”形式.若原向题是求目标函数最小，而约束条件方 程为“≤”形式，则做同样的处理。 (仁)、原问题的每一个约束条件方程对应对偶问题的一个决策量，如偶第i个约 束条件为不等式，则限定：≥0：如约束条件方程是“-”这种形式，有两种处理方法 1.将等式约束条件为“≥”和“≤”两个约束条件方程，再按（一）处理 2.原间题第：个约策条件是“=”形式，不加之动对偶间题的决策之量为自由之 量 白)、原问题的每个决策量马和对应的系数列向量乃一(@2 am,对应 对偶问题的一个约束条件.如偶x)≥0，则对应的对偶问题的了约束为不等式；如偶) 为自由、量，则对应的对偶问题的约束为“=”型约束； (如原问题的松关量原系余，量的值不为0，可以把原约束条件方程作为等 式约束条件处理。例如松关，量表示要贮费的系余物、·就是这种情况。 例2.的立如下线性规问题的对偶问题 min2=2x1+4x2+3x3: 满足 1+2x2-3g≥5， 2x1-3.x2-2xg≤3 x1+x2+x3=2. 西≥0，对一切 解将第2个和第3个约束条件处理后得 min 2 2r1+4r2+3r3 满足 x1+2x2-3x3>5. -2x1+3z2+23≥-3 1+2+≥2 -x1-2-3≥-2 王≥0，对一切i. 设对偶之量为弘，取和么，因为最后两个之量都是对应者原间题的第3个约束条件方 程，所以它们的下标都是3.则对偶问题为： max w -3qz+2gs -2q 满足q1-2g+9g-6≤2， 2q1+3q2+q9%-g≤4， -3g1+2+9%-9g≤3 贴20，对一切i. 第三节对偶问题的成表性质
4 Ö✳×✵ØÚÙ✒Û✳Ü✵Ý✒Þ✒Ù✒Û✒ß✒à✒á✳â ★✁✩✢✒✣✒✸✒✹✭✁✷, ❹✒❺✒✢✒✼✒✸✒✹✁❢P ➘ ✔ , ❿ ✭✁❣❸✷✁❤✪ ❊ : (✮ )s✐❆➽✼➽✸➽✹➽✘❊ Ò⑧Ó➽Ô✒Õ➀➽ã, ➷➽❮➽❰➽Ï➽Ð✕➽Ñ✻ “ ≥ ” ✤❳✥, →❳❋❳❥❮➽❰➽Ï➽Ð✕ Ñæ ✾✁◗✁ −1, ❍✒❮✒❰✒Ï✒Ð✁✭✒① “ ≤ ” ✤✁✥✯ ❆✒✼✒✸✒✹✒✘❊▲Ò◆Ó✒Ô✒Õ➀✒➁, ➷✒❮✒❰✒Ï✒Ð✕ Ñ ✻ “ ≤ ” ✤✁✥, →✁❦❍✄ ★✒➘✔✒✯ (✳)sü✼✒✸✒✹✒★✒✶✮✒✷❮✒❰✒Ï✒Ð✕✒Ñ✢✒✛✒✢✒✣✒✸✒✹✒★✮✒✷❐✁✫✁✭✒➔ qi ✯ ❼✁✣✒➓ i ✷ ❮ ❰✒Ï✒Ð✒✻✒➬✒➻✁✥❱ →✁❧➯ qi ≥ 0; ❼✒❮✒❰✒Ï✒Ð✕✒Ñ✘ “=” ➣ ✉✁✤✁✥, ✾æ ✉✒➘✔✒✕✁♠: 1. ❋ ➻✁✥✒❮✒❰✒Ï✒Ð✁✭✒✻ “ ≥ ” ❁ “ ≤ ” æ✷ ❮✒❰✒Ï✒Ð✕✒Ñ, ♥ ✦ (✮ ) ➘ ✔ ; 2. ✼✒✸✒✹✒➓ i ✷ ❮✒❰✒Ï✒Ð✒✘ “ = ” ✤✁✥, ➬✁✞✁✭▼ , ✢✒✣✒✸✒✹✒★✒❐✁✫✁✭✒➔ qi ✻ ❑ r✚✭ ➔; (t)s⑧✼❀✸❀✹❀★❀✶✷❐✬✫✬✭❀➔ xj ❁❀✢❀✛❀★❀❉Õ ■❛➪✐➔ Pj = (a1j , a2j , . . . , amj ), ✢❀✛ ✢✒✣✒✸✒✹✒★✮✒✷❮✒❰✒Ï❀Ð✯ ❼✬✣ xj ≥ 0❱ →✢✒✛✒★✒✢✒✣✒✸✒✹✒★P ❮✒❰❀✻❀➬✒➻✬✥✬❲⑧❼✬✣ xj ✻ ❑ r✚✭✒➔❱ →✢✒✛✒★✒✢✒✣✒✸✒✹✒★✒❮✒❰✒✻ “=” ↕✒❮✒❰✁❲ (✿)s➅❼✒✼✒✸✒✹✒★✁❇✁❈✁✭✒➔✁✼✁❉✁❊✁✭✒➔✒★ cj è ➬✒✻ 0, ÿ✁✁❍✒✼✒❮✒❰✒Ï✒Ð✕✒Ñ✁♦✻✒➻ ✥✒❮✒❰✒Ï✒Ð✒➘✔✒✯⑧❣❼✁❇✁❈✁✭✒➔✒②✁✲✒✪❃✁♣✁q★✁❉✁❊✁r✁s✯ ➾✒✘➣ ✉✁t✁✉ ❥ ✯ 2. ★✁✩❼✒❢✒✤✒✥✒✦✒✧✒✸✒✹✒★✒✢✒✣✒✸✒✹: min z = 2x1 + 4x2 + 3x3; ➙✒➛ x1 + 2x2 − 3x3 ≥ 5, 2x1 − 3x2 − 2x3 ≤ 3, x1 + x2 + x3 = 2, xj ≥ 0, ✢ ✮✒❇j. ✈ ❋ ➓ 2 ✷ ❁✒➓ 3 ✷ ❮✒❰✒Ï✒Ð✒➘✔ ❙ý min z = 2x1 + 4x2 + 3x3; ➙✒➛ x1 + 2x2 − 3x3 ≥ 5, −2x1 + 3x2 + 2x3 ≥ −3, x1 + x2 + x3 ≥ 2, −x1 − x2 − x3 ≥ −2, xj ≥ 0, ✢ ✮✒❇j. ➒✢❀✣✬✭❀➔❀✻ q1,q2,q3 ❁ q 0 3 ✯ ➦❀✻❀➀✬❙æ✷ ✭❀➔❀✽❀✘❀✢❀✛❅✼❀✸❀✹❀★❀➓ 3 ✷ ❮❀❰❀Ï❀Ð✕ Ñ , ♦✁ ✪➢ ★✒❢Ó ✽✒✘ 3✯ →✢✒✣✒✸✒✹✒✻: max w = 5qx1 − 3q2 + 2q3 − 2q 0 3 ; ➙✒➛ q1 − 2q2 + q3 − q 0 3 ≤ 2, 2q1 + 3q2 + q3 − q3 ≤ 4, −3q1 + 2q2 + q3 − q3 ≤ 3, qi ≥ 0, ✢ ✮✒❇i. ❘✡✇❚❯ ❱❚❲❚❳❚❨❚❩✏①✏②✍③✏④
5 一、对称性 定理1.对偶问题的对偶是原问题 证明设原问题是 max 2=CX 满足 AXSi X≥0 则对偶问题为： min w=Qb 满足 JQAZC 1Q20 将上述对偶问题的约束条件（非负约束除外）两边取负号因为mi血心--max(-w),可 得 max (-w)=-bTQ -0A<-C 满足 Q≥0 根据建立对偶问题的规则，此问题的对偶问题为： min (-2)=-CX 满足 「-AX≥-b 1X>0 因为min(一)=-max云，因此有 max 满足A≤6 1X≥0 这就是原问题。 二、弱对偶性 定理2.设是原问题(1.7)的可行解，可是对偶问题(1.8)的可行解则有C了<Q 证明设是原问题(1.7)的可行解则AX≤，若石≥0是对偶问题(1.8)的可行 解用反左乘上式两端得瓦4仅≤O6.因为可A≥C,用下右乘此式两端得石4A了≥C了 从而 Cx≤瓦A下≤Ob. 由弱对偶性，可得到如下重要结果 推论1.若原问题可行，但其目标函数值无上界，则对偶问题不可行. 证明用反证法。反设对偶问题可行，瓦为对偶问题的可行解，则由定理2可知对 原问题的任意可行解X都有CX≤，即原问题的目标函数值有上界，矛盾，所以对偶 问题不可行。 类似的可证明如下推论。 推论2.若对偶问题可行，但其目标函数值无下界，则原问题不可行
5 ✑s⑧ò✁⑤✁⑥ ⑦❡ 1. ✢✒✣✒✸✒✹✒★✒✢✒✣✒✘✒✼✒✸✒✹✯ ⑧✁⑨: ➒✼✒✸✒✹✒✘: max z = CX ➙✒➛ ( AX ≤ b X ≥ 0 →✢✒✣✒✸✒✹✒✻: min w = Qb ➙✒➛ ( QA ≥ C Q ≥ 0 ❋ å❤ ✢❀✣❀✸❀✹❀★❀❮❀❰❀Ï❀Ð (⑩✬❶❀❮❀❰✬❷✬❸) æ❯✬❹❶✬✸, ➦❀✻ min w = −max (−w), ÿ ý✁❺ max (−w) = −b TQ ➙✒➛ ( −QA ≤ −C Q ≥ 0 é✒ê★✁✩✢✒✣✒✸✒✹✒★✒✦→ , ➧✒✸✒✹✒★✒✢✒✣✒✸✒✹✒✻: min (−z) = −CX ➙✒➛ ( −AX ≥ −b X ≥ 0 ➦✒✻ min (−z) = −max z, ➦✒➧✒✾ max z = CX ➙✒➛ ( AX ≤ b X ≥ 0 ➣ ➾✒✘✒✼✒✸✒✹✯ ❫ s✓❻✒ò✒ô✁⑥ ⑦❡ 2. ➒ X ✘➽✼➽✸➽✹ (1.7) ★➽ÿP ●, Q ✘➽✢➽✣➽✸➽✹ (1.8) ★➽ÿP ●, →✾ CX ≤ Qb. ⑧✁⑨ ➒ X ✘✒✼✒✸✒✹ (1.7) ★✒ÿP ●, → AX ≤ b✯ ❆ Q ≥ 0 ✘✒✢✒✣✒✸✒✹ (1.8) ★✒ÿP ●, ✜ Q ❼✁◗✒å✁✥æ ✾ ý QAX ≤ Qb✯ ➦✒✻ QA ≥ C, ✜ X ✽✁◗✒➧✁✥æ ✾ ý QAX ≥ CX, ✓ ➷ CX ≤ QAX ≤ Qb. r✚❽✒✢✒✣✒✥, ÿ ý✁❺❼✒❢✒✩✒✪✁❾✁✣✯ ❿✁➀ 1. ❆✒✼✒✸✒✹✒ÿP , ❅ ✰ Ò◆Ó✒Ô✒Õ✒è✒✏å✁➁, →✢✒✣✒✸✒✹✒➬✒ÿP✒✯ ⑧✬⑨ ✜✵✬➂✬♠❀✯✓✵➒✢❀✣❀✸❀✹❀ÿP ❱ Q ✻❀✢❀✣❀✸❀✹❀★❀ÿP ●❱ → r✐➯✔ 2 ÿ ➤✢ ✼✒✸✒✹✒★✁➃✁✮✒ÿP ● X ✽✒✾ CX ≤ Qb, ä✒✼✒✸✒✹✒★ Ò◆Ó✒Ô✒Õ✒è✾✒å✁➁❱✓➄✁➅✁❱ ♦✁✒✢✒✣ ✸✒✹✒➬✒ÿP✒✯ ❨✁❩★✒ÿ➂✳❵❼✒❢✁➆✑✒✯ ❿✁➀ 2. ❆✒✢✒✣✒✸✒✹✒ÿP , ❅ ✰ Ò◆Ó✒Ô✒Õ✒è✒✏❢✁➁, →✼✒✸✒✹✒➬✒ÿP✒✯