第四章对偶问题及对偶单纯形法 无论从理论方面，还是实际应用方面，对偶理论是线性规划的重要的基础理论之 其主要内容是：每一个线性规划问题（称为原问题），都有一个与之对应的线性规划问题( 称为对偶问题)，原问题和对偶问题之间存在着密切的关系，在求出一个问题的解的同时 也自动的给出了另一个问题的解。 第一节对偶问题的提出 为了说明原问题和对偶问题间的关系，首先介绍下面例题中的线性规划问题的对偶 问题 例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 -0A0 因为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✒✯
第四章对偶问题及对倡单纯形法 攫追1和推论2的逆也成立 品文 三、可行解是最优解性质 定理3设了是原同高(17)的可行解是对偶题1.8)的可行解密C了=， 则了和夏分别是原何题和对偶问题得最优解。 证明：只需证明对原问题的得任一可行解X都有CX≤X:对对偶问题的任一可行 解Q都有Q≥O6.由弱对偶性对原问题的任一可行解X有CX≤Q-C，所以 CX≤C灭，可见是原问题的最优解.同样的方法可证可为对偶问题的最优解。 四、对偶定理 定理4. 原向题有最优解，量对偶问题一定有最优解，为原向题和对偶问题的最 优目标函数值相 证明和原阿题1，)的标这型的系数矩机为=以山，其单位矩和I为切关之量 的系数矩。设了为原问题(1.7)的最优解，B为其对应的基矩 今w=060N 为标这型中目标函数中决 之量的系数 则由最优型 这则可知最优解了对应的型数 C-CBB-1(AI)≤0，即 C-CBB-1(A,I)=C-(CBB-1A,CB B-1)=(C-CBB-1A,-CBB-1)<0 从而 C-CBB-1A≤0，-CBB-1≤0. 令石=CBB-1,由上性可知0≥0，为C-OA≤0即OA≥C.可见反为对偶问题(1.8) 的可行解为对应的目标函数值为”-CB-b.而原何题的最优解了对应的目标 函数值为之=C了 CB-1b,从而O6=C，由定理3可知为对偶问题的最优解，为 与原问题的最优目标函数值相同。 如偶原问题的目标函数为“血”型，同样可证明原问题和对偶问题的最优解的目标 函数为CBB-1b. 定理5. 了为原问题(17)的一满足最优型、 的基本解，则反=CgB-1为对偶问 题的一可行解为这两个解的目标函数的值相同.中B为基本解了对应的基矩 由上一定理的证明足见结论成立。 从上面定理的证明可以解出，对偶问题(1.8)的最优解刀=CB-,这现为为原间 意(1：)最优解表中切关之量的机会费用，原者说是原向意最优解表中切关之量型满数 cs-zs的负数.即 如偶原问题是求目标药数值最小，对偶问题是求目标函数值最大由于原问题系 其的系数构成一负单位矩，因比对偶同题的最优解是原间题最优解影中系求之量譎新 会费用2的负数原者说是最优解表中系求之量的型滑数9-8，即
6 Ö✳×✵ØÚÙ✒Û✳Ü✵Ý✒Þ✒Ù✒Û✒ß✒à✒á✳â ➆✑ 1 ❁✁➆✑ 2 ★✁➇❏ ①✩ . ❿✁➀ 3. ❆✒✼✒✸✒✹✒ÿP , ➷✒✢✒✣✒✸✒✹✒➬✒ÿP , →✼✒✸✒✹✒★ Ò◆Ó✒Ô✒Õ✒è✒✏➁ ✯ ❿✁➀ 4. ❆✒✢✒✣✒✸✒✹✒ÿP , ➷✒✼✒✸✒✹✒➬✒ÿP , →✢✒✣✒✸✒✹✒★ Ò◆Ó✒Ô✒Õ✒è✒✏➁ ✯ ➈ s✓➉✁➊✈✁➋✁➌✁➍✁✈✕✁⑥✁➎ ⑦❡ 3. ➒ X ✘✒✼✒✸✒✹ (1.7) ★✒ÿP ●, Q ✘✒✢✒✣✒✸✒✹ (1.8) ★✒ÿP ●, ❆ CX = Qb, → X ❁ Q ❻✒➭✒✘✒✼✒✸✒✹✒❁✒✢✒✣✒✸✒✹ý ➀✒ç✒●✯ ⑧✁⑨: ➏✁➐➂✳❵✢✒✼✒✸✒✹✒★ý ➃✮ ÿ P ● X ✽✒✾ CX ≤ X; ✢✒✢✒✣✒✸✒✹✒★✁➃✮ ÿ P ● Q ✽❀✾ Qb ≥ Qb✯ r➑❽❀✢❀✣❀✥, ✢❀✼❀✸❀✹❀★✬➃✮ ÿ P ● X ✾ CX ≤ Qb = CX, ♦✬ CX ≤ CX, ÿ✁➒ X ✘✒✼✒✸✒✹✒★✒➀✒ç✒●✯ ❍✄ ★✕✁♠ÿ➂ Q ✻✒✢✒✣✒✸✒✹✒★✒➀✒ç✒●✯ ➓ s⑧ò✒ô⑦❡ ⑦❡ 4. ❆❀✼❀✸❀✹❀✾❀➀❀ç❀●, ➔✬→❀✢❀✣❀✸❀✹✮ ➯❀✾❀➀❀ç❀●, ✻❀✼❀✸❀✹❀❁❀✢❀✣❀✸❀✹❀★❀➀ ç Ò◆Ó✒Ô✒Õ✒è➵✒➻✯ ⑧✁⑨: ✼✒✸✒✹ (1.7) ★Ó✁➣↕✒★✒❉Õ✁❀✁❁✻ A 0 = (A, I), ✰ ❤✵⑦✒⑨❀✁❁ I ✻✁❇✁❈✁✭✒➔ ★❀❉Õ✬❀✬❁❀✯ ➒ X ✻❀✼❀✸❀✹ (1.7) ★❀➀❀ç❀●,B ✻✰ ✢❀✛❀★❀✫❀✬❁❀✯✓↔ C 0 = (C, 0, . . . , 0) ✻Ó✁➣↕✳❤ Ò◆Ó✒Ô✒Õ❤✵❐✁✫✁✭✒➔✒★✒❉Õ✒✯ → r✵➀✒ç✁↕✁➙➣→ÿ ➤➀✒ç✒● X ✢✒✛✒★✁↕✁➙Õ C 0 − CBB−1 (A, I) ≤ 0, ä C 0 − CBB −1 (A, I) = C 0 − (CBB −1A, CBB −1 ) = (C − CBB −1A, −CBB −1 ) ≤ 0, ✓ ➷ C − CBB −1A ≤ 0, −CBB −1 ≤ 0. ↔ Q = CBB−1 , r✵å✁✥✒ÿ➤ Q ≥ 0, ✻ C − QA ≤ 0 ä QA ≥ C ✯ ÿ✁➒ Q ✻✒✢✒✣✒✸✒✹ (1.8) ★❀ÿP ●✬✻❀✢❀✛❀★ Ò Ó❀Ô❀Õ❀è✻ w = Qb = CBB−1 b✯ ➷❀✼❀✸❀✹❀★❀➀❀ç❀● X ✢❀✛❀★ Ò Ó Ô✒Õ✒è✻ z = CX = CBB−1 b, ✓ ➷ Qb = CX ✯ r✵➯✔ 3 ÿ ➤ Q ✻✒✢✒✣✒✸✒✹✒★✒➀✒ç✒●, ✻ ✿✼✒✸✒✹✒★✒➀✒ç Ò◆Ó✒Ô✒Õ✒è➵✒❍✯ ❼✬✣❀✼❀✸❀✹❀★ Ò Ó❀Ô❀Õ✻ “min” ↕, ❍✄ÿ➂❛❵✼❀✸❀✹❀❁❀✢❀✣❀✸❀✹❀★❀➀❀ç❀●❀★ Ò Ó Ô✒Õ✻ CBB−1 b✯ ⑦❡ 5. ❆ X ✻✒✼✒✸✒✹ (1.7) ★✮➙✒➛➀✒ç✁↕✁➙✒★✒✫✒⑩✒●, → Q = CBB−1 ✻✒✢✒✣✒✸ ✹✒★✮ ÿ P ●, ✻➣✒æ✷ ●✒★ Ò◆Ó✒Ô✒Õ★è ➵✒❍✯ ✰ ❤ B ✻✒✫✒⑩✒● X ✢✒✛✒★✒✫❀✁❁✒✯ r✵å✮ ➯ ✔ ★➂✳❵✚➛➒✁❾✑ ①✩✯ ✓ å✖ ➯ ✔ ★➂❛❵ÿ✬ ●❋ , ✢❀✣❀✸❀✹ (1.8) ★❀➀❀ç❀● Q = CBB−1 , ➣✬➜✻❀✻❀✼❀✸ ✹ (1.7) ➀✒ç✒●✒②✳❤✚❇✁❈✁✭✒➔✒★✁➝✒➚q ✜ zs, ✼✁➞❴ ✘✒✼✒✸✒✹✒➀✒ç✒●✒②✳❤✚❇✁❈✁✭✒➔✁↕✁➙Õ cS − zS ★✁❶Õ , ä qi = zn+i . ❼✁✣✒✼✒✸✒✹✒✘❊▲Ò◆Ó✒Ô✒Õ✒è➀✒➁, ✢✒✣✒✸✒✹✒✘❊▲Ò◆Ó✒Ô✒Õ✒è➀✒ã, r✵➺✒✼✒✸✒✹✁❉✁❊✁✭ ➔❀★❀❉Õ✬➟①✮ ❶❀⑦❀⑨❀✬❁, ➦❀➧❀✢❀✣❀✸❀✹❀★❀➀❀ç❀●❀✘❀✼❀✸❀✹❀➀❀ç❀●❀②❛❤➑❉✬❊✬✭❀➔❀★✬➝ ➚ q ✜ zS ★✁❶Õ , ✼✁➞❴ ✘✒➀✒ç✒●✒②✳❤✚❉✁❊✁✭✒➔✒★✁↕✁➙Õ cS − zS, ä qi = −zn+i
例1原问题的最优单纯形表 表4-2 632 0 0 0 CB TB 6 1 T6 0 1 0 -C 0 0 1 4 0 例1对偶问题的最优解表 表4-3 90610 0 20 21 20 6 20 16 9- -10 0 -16 原向题的最优解为二02二4=16.与此对应对偶间题的松关之量的+1一 0.m42=4.m3=16.其中m=3. 对偶问题的最优解为g1=1,2=4,3=0.与此对应，原问题的系余之量的m+1= -1,zm+ n+3=0,其中n=3 由上可见，当一个线性靓划问题是求目标函数值最小，约束方程全是“≥”时，求解时 要用大M法原两阶们法，较麻烦。如偶立此问题的对偶问题再球解，就容足得系。当 然此种情况下的较有效的算法是下节将要介绍的对偶单纯形法】 第四节对偶单纯形法 对原问题： max =CX 满足 AX≤b X>0 和对偶问题 min=Q6 满足 ∫QA≥C 1Q≥0 由第三节定理5，原问题的每一满足最优检的基本解下都对应着对偶问题的一基本可 了解万=CBB-1,为这两个解对应的目标西数值相同.当下为原问题的基本可了解时 根据定理4，原问题和对偶问题同时相到最优。基于这种思于，我们可用另一种算法，使在 单纯形法的每次选就的菩本解都满足最优 但不一定满足非负约束，迭就时使不满足 非负约束的，量个数逐减少，一且全部 之量都满足非负约束就得到最优解这种算 法称为对偶单不形法
7 ❣ 1 ✼✒✸✒✹✒★✒➀✒ç✒⑦✁➠✁✤✒② ② 4–2 cj → 6 3 2 0 0 0 cB xB b x1 x2 x3 x4 x5 x6 2 x3 16 0 0 1 −2 4 0 0 x6 10 −1 0 0 −1 0 1 3 x2 4 1 1 0 1 −4 0 zj 3 3 2 −1 −4 0 zj − cj 3 0 0 1 4 0 ❣ 1 ✢✒✣✒✸✒✹✒★✒➀✒ç✒●✒② ② 4–3 cj → 20 6 10 0 0 0 cB qB c q1 q2 q3 q4 q5 q6 0 q4 3 0 0 1 1 −1 0 6 q2 4 0 1 0 0 4 −4 20 q1 1 1 0 1 0 −1 2 zj 20 6 20 0 4 16 cj − zj 0 0 −10 0 −4 −16 ✼✒✸✒✹✒★✒➀✒ç✒●✒✻ x1 = 0,x2 = 4,x3 = 16✯ ✿➧✒✢✒✛, ✢✒✣✒✸✒✹✒★✁❇✁❈✁✭✒➔✒★ zm+1 = 0, zm+2 = 4, zm+3 = 16, ✰ ❤ m = 3✯ ✢❀✣❀✸❀✹❀★❀➀❀ç❀●❀✻ q1 = 1,q2 = 4,q3 = 0✯⑧✿➧❀✢❀✛, ✼❀✸❀✹❀★✬❉✬❊✬✭❀➔❀★ zn+1 = −1, zn+2 = −4, zn+3 = 0, ✰ ❤ n = 3✯ r✵å✒ÿ✁➒, ➸✮✒✷✤✒✥✒✦✒✧✒✸✒✹✒✘❊▲Ò◆Ó✒Ô✒Õ✒è➀✒➁, ❮✒❰✕✒Ñ✁✴✘ “≥” ■, ❊●✒■ ✪✒✜✒ã M ♠ ✼æ✁➡✁➢♠ , ✘✚✙✁➤✁➥✯ ❼✁✣★✁✩➧✒✸✒✹✒★✒✢✒✣✒✸✒✹✁♥❊●, ➾✒✴➛✒ý❉ ✯ ➸ ✃ ➧✒✉✁t✁✉✒❢✒★✙ ✾✁➦✒★✁➧♠ ✘✒❢✁➨❋ ✪✒❞✒❡✒★✒✢✒✣✒⑦✁➠✁✤♠✒✯ ❘➫➩❯ ❱❚❲✡➭✡➯✡➲✏➳ ✢✒✼✒✸✒✹: max z = CX ➙✒➛ ( AX ≤ b X ≥ 0 ❁✒✢✒✣✒✸✒✹: min z = Qb ➙✒➛ ( QA ≥ C Q ≥ 0 r✵➓✒t✁➨✒➯✔ 5, ✼✒✸✒✹✒★✒✶✮➙✒➛➀✒ç✁↕✁➙✒★✒✫❀⑩❀● X ✽✒✢✒✛❅✢✒✣✒✸✒✹✒★✮ ✫✒⑩✒ÿ P ● Q = CBB−1 , ✻➣❀æ✷ ●❀✢❀✛❀★ Ò Ó❀Ô❀Õ❀è➵❀❍ ✯ ➸ X ✻❀✼❀✸❀✹❀★❀✫❀⑩❀ÿP ●❀■, é✒ê✒➯✔ 4, ✼✒✸✒✹✒❁✒✢✒✣✒✸✒✹✒❍✒■✁➵❺➀✒ç✯ ✫✒➺➣ ✉✁➸✁➺, ➻ ➢ÿ✒✜◗✒✮✉✁➧♠ , ❿ ❄ ⑦✁➠✁✤♠ ★✒✶✁➼✁➽✁➾✒★✒✫✒⑩✒●✒✽➙✒➛➀✒ç✁↕✁➙, ❅✒➬✮ ➯➙✒➛⑩✁❶✒❮✒❰, ➽✁➾✒■✒❿✒➬➙✒➛ ⑩✁❶✒❮✒❰✒★✁✭✒➔✷✒Õ✁➚✁➪✁➶✁➹✒✯⑧✮✁➘✁✴✬➴✫✬✭✒➔✒✽➙✒➛⑩✁❶❀❮✒❰, ➾ ý✁❺➀✒ç✒●, ➣ ✉✁➧ ♠✺✒✻ ò✒ô✁➷✁➬✁➮✁➱✯
第四章对偶问题及对偶单纯形法 对偶单纯形法的计算向囊。 聚 件到子个满足最优检的初始基本解 束二条 检进当个解是否可了若可了， 量，记这 向 束四条 橙查心若心，至大于原等于石则阿题无解，停止腰'香则，便 下式相到最小的分对应的之量作为换标之量： min(9二，0.表示 基、量取值减少，而0.i=1.2....6 解函数，6为基之其令===0则足得出4=-20， -6.xe=-10 ”为了使初始基本解的基，量的系数矩和为单位矩和，用-1乘3个约束方程.因为是 求目标函数值最小用与一弓≤0检满最优。初始单纯形表如表4。 授4-4 6 32000 0 01 0 00000 -6 0 0 表中所有检满数-9≤0，目相最优但不可了函数4为换出之量，”=1 m(后子=2，°=3
8 Ö✳×✵ØÚÙ✒Û✳Ü✵Ý✒Þ✒Ù✒Û✒ß✒à✒á✳â ✢✒✣✒⑦✁➠✁✤♠ ★✁✃✁➧➪✁❐: ❒ SN ✻✁⑩✒✫✁✭✒➔✒★✒❢Ó ★✁❮✒❸✯ ❰✑✁Ï Ð❺✒✮✒✷➙✒➛➀✒ç✁↕✁➙✒★✁Ñ✁❖✒✫✒⑩✒●; ❰❫Ï ↕✁➙✒➸✷ ●✒✘➼ÿ P✒✯ ❆✒ÿP , Òý ➀✒ç✒●, ➼→❂✁Ó✒❢✮✁➪; ❰➈Ï Ô✁Õ b 0 i ➀✒➁✮✁P★✁✭✒➔♦ ✻✁Ö❋ ✭✒➔, ❒➣✮✁P✻ i ∗ , ❂✁Ó✒❢✮✁➪; ❰➓ Ï ↕✬× a 0 i ∗j ❱ ❆ a 0 i ∗j ✴ ã❀➺✬✼❀➻❀➺ 0, → ✸❀✹✏ ●❱✓Ø✬Ù✃✬➧✯ ➼→ ❱ Ô✬Õ❿ ❢✁✥✁➵❺➀✒➁✒★ j ∗ ✢✒✛✒★✁✭✒➔♦ ✻✁Ö✁Ó✁✭✒➔: min{ cj − zj a 0 i ∗j a 0 i ∗j 0, ②✁✲ ✫✁✭✒➔❹✒è✁➶✁➹❱ ➷ a 0 ij < 0 ②✁✲✒✫✁✭✒➔❹✒èà✞ ✯ ➦✒⑦✁➠✁✤✒②✳❤ i ∗ P ★ b 0 i ∗ ✻✁❶Õ ❱ ❹ ❺à✞ ❺ 0❱✓åÞ❿ ý❥P ★✒✫✁✭✒➔✒①✒✻✁Ö❋ ✭✒➔❱ ➦✒➧✒❹✒❺ a 0 i ∗j < 0✯ ❆✒➓ i ∗ P ★ a 0 i ∗j ✽✒✘✁æÕ ❱ → ã✁❢✁➃✮ ⑩✒✫✁✭✒➔✒✽✒➬Þ❿ ý i ∗ P ★✒✫✁✭✒➔✁✭✒✻ 0 ➷✁ç✁è❱ ➧✒✫✁✭✒➔✁é✁ê ➬Þ➙✒➛⑩✁❶✒❮✒❰❱ ♦✁✒➧✒✸✒✹✏ ● ✯ ➻ ➢✁ë ❣ 1 ★✒✼✒✸✒✹✒✻❣✒❴✳❵✢✒✣✒⑦✁➠✁✤♠ ★✁✃✁➧✯ü❣ 1 ❤✵✼✒✸✒✹✒★Ó✁➣↕✒❼✒❢: min z = 6x1 + 3x2 + 2x3; ➙✒➛ x1 + x2 + 2x3 − x4 = 20 1 2 x1 + 1 2 x2 + 1 4 x3 − x5 = 6 2x1 + x2 + x3 − x6 = 10 xj ≥ 0, j = 1, 2, . . . , 6 ✈ : Ô✰Õ x4, x5, x6 ✻✫✰✭➔, ↔ x1 = x2 = x3 = 0, →➛ý❋ x4 = −20, x5 = −6, x6 = −10✯ ✻ P❿✁Ñ✁❖✒✫✒⑩✒●✒★✒✫✁✭✒➔✒★✒❉Õ✁❀✁❁✻✒⑦✒⑨❀✁❁, ✜ −1 ◗ 3 ✷ ❮✒❰✕✒Ñ✒✯ ➦✒✻✒✘ ❊▲Ò◆Ó✒Ô✒Õ✒è➀✒➁, ✜ zj − cj ≤ 0 ↕✁➙✒➀✒ç✯ Ñ✁❖✒⑦✁➠✁✤✒②✒❼✒② 4-4✯ ② 4–4 cj → 6 3 2 0 0 0 cB xB b x1 x2 x3 x4 x5 x6 0 x4 −20 −1 −1 −1 1 0 0 0 x5 −6 −1 2 −1 2 −1 4 0 1 0 0 x6 −10 −2 −1 −1 0 0 1 zj 0 0 0 0 0 0 zj − cj −6 −3 −2 0 0 0 ②✳❤✵♦✒✾✁↕✁➙Õ zj − cj ≤ 0, Ò✚➵✒➀✒ç, ❅✒➬✒ÿP✒✯ Ô✁Õ x4 ✻✁Ö❋ ✭✒➔,i ∗ = 1✯ min{ −6 −1 , −3 −1 , −2 −1 } = 2, j ∗ = 3
9 以a13为偶问下了转问题此，得表4-5. 表4-5 CB R 10 0 2 -2 0 zj-cj -4 表4-5中%=-1≤0，令”=2. }=4°-2 以a为偏问下了转问题此，得表46. 表4-6 63200 0 T4 2 x316 0 0 1 -2 4 0 3 1 0 0x6 10 -1 0 0 -1 0 1 3 3 2 -1 -40 0 0 -1 -4 表46滴足星优型满为可了·目得最优有 五边 变量似经济意对 一影偶价格 在第一章第三节中，等们用图法求将行第一章例1的最优 。(见图1-1)。在实际决 基中，决基者需考感的 个问纯加某种资源是香有利。从圈11可见若纯加日 不爱餐包红商如有的可数目属数 设有如下线性的或问题： min=CX 满足∫AX≤& 1x20 和对果问题 max w =Ob 满足∫QA≥C 1Q20 若B为或间题的最优。X'对应的基矩和，X为基变量组成的向，CB为基变量在 目标函数中对应的系数向歪Q=CB~1为对果问题的最优看·由个规的定理可知，最
9 a 0 13 ✻✁Û✁Ü✁❢P ❂✁Ü✁Ý✁➧, ý② 4–5✯ ② 4–5 cj → 6 3 2 0 0 0 cB xB b x1 x2 x3 x4 x5 x6 2 x3 20 1 1 1 −1 0 0 0 x5 −1 − 1 4 − 1 4 0 − 1 4 1 0 0 x6 10 −1 0 0 −1 0 1 zj 2 2 2 −2 0 zj − cj −4 −1 0 −2 0 0 ② 4–5 ❤ b 0 2 = −1 ≤ 0, ↔ i ∗ = 2✯ min{ −4 −1/4 , −1 −1/4 , −2 −1/4 } = 4, j ∗ = 2 a 0 22 ✻✁Û✁Ü✁❢P ❂✁Ü✁Ý✁➧, ý② 4–6✯ ② 4–6 cj → 6 3 2 0 0 0 cB xB b x1 x2 x3 x4 x5 x6 2 x3 16 0 0 1 −2 4 0 3 x2 4 1 1 0 1 −4 0 0 x6 10 −1 0 0 −1 0 1 zj 3 3 2 −1 −4 0 zj − cj −3 0 0 −1 −4 0 ② 4-6 ➙✒➛➀✒ç✁↕✁➙✁✻✒ÿP , Òý ➀✒ç✒●✯ ❘✡ì❚❯ ❱❚❲✡í✡î❚❩✏ï✍ð✏ñ✏ò —- ó✡ô✡õ✡ö ❄ ➓✮✁÷➓✒t✁➨✳❤, ➻ ➢ ✜✁ø✒●♠✒❊✒❋✒P➓✮✁÷✒❣ 1 ★✒➀✒ç✒● (➒✁ø 1-1)✯⑧❄✙✒✚✒❐ ✫✳❤, ❐✁✫✁➞✁➐✒✪✁ù✁ú✒★✮✒✷✸✒✹✒✘à✞✒❦✒✉✁s✁û✒✘➼✾✁ü✯ ✓ ø 1-1 ÿ✁➒, ❆à✞ B ý ❂ ★✒ÿ✒✜✁þ✒■✁✼✁ÿ✒♥❧✁, → Ò◆Ó✒Ô✒Õ✒èà✞, ➷à✞ A ý ❂ ★✒ÿ✒✜✁þ✒■Õ , Ò◆Ó✒Ô✒Õ✒è ➬à✞ ✯ ❢ ✖ ✢ ✮✁✢★✒✸✒✹✁ù✁ú➣ ✉✁✭✁ä✯ ➒ ✾✒❼✒❢✁✤✁✥✒★✒✼✒✸✒✹: min z = CX ➙✒➛ ( AX ≤ b X ≥ 0 ❁✒✢✒✣✒✸✒✹: max w = Qb ➙✒➛ ( QA ≥ C Q ≥ 0 ❆ B ✻✒✼✒✸✒✹✒★✒➀✒ç✒● X0 ✢✒✛✒★✒✫❀✁❁,X0 B ✻✒✫✁✭✒➔✒✇✒①✒★✳➪✵➔, CB ✻✒✫✁✭✒➔❄ Ò◆Ó✒Ô✒Õ❤✵✢✒✛✒★✒❉Õ ➪✵➔✯ Q0 = CBB−1 ✻✒✢✒✣✒✸✒✹✒★✒➀✒ç✒●✯ r ✷✒✖★✒➯✔ÿ ➤ , ➀
10 第四章对偶问题及对倡单纯形法 优目标函数值为： z=CBXB=CBB-b=Q'b 也即 =+qab2+...+ 由此得 光=品= 可见约束条件方程右端的=1,2，，m)增加一单位时，目标函数z的变化量为 (2=1,2,...,m. 定义1.约束条件方程右端的（位=1,2，m)增加一单位时，最优目标函数z的变 化量称为资源=1,2，，m)的影子价格 影子价格是针对某一种资源而言的（与决策变量无关），而问题中其它数据不变.由上 面的讨论可知，在求出线性规划问题的最优解后，资源i的影子价格就是第：种资源的机 会费用n+i或一n+ 第六节对偶单纯形法的一个应用（增加约束条件 在求出线性规划问题的最优解以后，又增加一个约束条件，此时可以用对偶单纯形法 求解不必对原问题从头做起，其步骤如下： 第一步检验原来的最优解是否满足新增加的约束条件。若满足，则原最优解就是新 问题的最优解若不满足，就进行下一步； 第二步将新增加的约束条件加入松驰变量或多余变量后加到原来的最优单纯形表 中去，令原来的基变量和新增加的松地变量或多余变量组成新的基 ,进行初等变换，将基 变量对应的系数矩阵变为单位矩阵。显然此时得到的是一个满足最优检验的不可行的基 本解： 第三步利用对偶单纯形法求最优解。 例3.第一章例2在求出最优解x1=20,x2=20,x3=0(表2-3)后，增加一个市场约 束条件1≤15.显然原最优解不满足该约束条件进行第二步。对≤15，加入松弛变 量6得 x1+6=15,6≥0 (4.9) 得表4-7. 表4-7 404524 0 0 0 5 .2/3 0 15 1 0 0 进行初等变换，使a1为0，得表4-8
10 Ö✳×✵ØÚÙ✒Û✳Ü✵Ý✒Þ✒Ù✒Û✒ß✒à✒á✳â ç Ò◆Ó✒Ô✒Õ✒è✻: z = CBXB = CBB −1 b = Q 0 b ❏ ä z = q 0 1 b1 + q 0 2 b2 + . . . + q 0 mbm r✵➧ý ϑz ϑbi = q 0 i ✼ϑz ϑb = q 0 ÿ✬➒❀❮❀❰❀Ï❀Ð✕❀Ñ✽✬✾❀★ bi (i = 1, 2, . . . , m) à✞✮ ⑦❀⑨❀■, Ò Ó❀Ô❀Õ z ★✬✭✬ä❀➔❀✻ q 0 i (i = 1, 2, . . . , m)✯ ⑦✁✂ 1. ❮✒❰✒Ï✒Ð✕✒Ñ✽✁✾✒★ bi(i = 1, 2, . . . , m) à✞✮ ⑦✒⑨✒■, ➀✒ç Ò◆Ó✒Ô✒Õ z ★✁✭ ä✒➔✒✺✒✻✁s✁û i(i = 1, 2, . . . , m) ★☎✄✁✆✁✝✁✞✯ ✟✡✠➩➽➫➽✘✡☛➽✢➽❦✮ ✉✁s❳û✒➷✡☞✒★ (✿❐❳✫❳✭➽➔✏❈), ➷➽✸➽✹➶❤✰✪Õ ê➽➬❳✭✯ r➹å ✖ ★❬✒✑ÿ ➤ , ❄✒❊✒❋ ✤✒✥✒✦✒✧✒✸✒✹✒★✒➀✒ç✒●✁❙, s✁û i ★✟✁✠➩✒➫✒➾✒✘✒➓ i ✉✁s✁û✒★✁➝ ➚ q ✜ zn+i ✼ −zn+i ✯ ❘✍✌✍✎ ✏✍✑✍✒✍✓✍✔✖✕✘✗✖✙✖✚✘✛✖✜ (✢✍✣✍✤✍✥✍✦✖✧) ★✁✩✁✪✁✫✁✬✁✭✁✮✁✯✁✰✁✱✁✲✁✳✁✴✁✵✁✶, ✷✁✸✁✹✁✺✁✻✁✼✁✽✁✾✁✿, ❀✁❁✁❂✵✁❃✁❄✁❅✁❆✁❇✁❈✁❉ ✩✁✴, ❊✁❋❄✁●✁✯✁✰✁❍✁■✁❏✁❑✁▲◆▼✁❖✁P✁◗✁❘: ❙✁❚✁❯ ❱✁❲●✁❳✁✱✁✲✁✳✁✴✁❨✁❩✁❬✁❭✁❪✸✁✹✱✼✁✽✁✾✁✿▲❴❫✁❬✁❭, ❵●✁✲✁✳✁✴✁❛✁❨✁❪ ✯✁✰✁✱✁✲✁✳✁✴; ❫ ❊❬✁❭, ❛✁❜✁❝✁❘✺ ❖ ; ❙❡❞❡❯ ❢❪ ✸❡✹✱✼❡✽❡✾❡✿❡✹❡❣❡❤❡✐❡❥❡❦❡❧❡♠❡♥❡❥❡❦✶ ✹❡♦●❡❳❡✱❡✲❡✳❡❆❡❇❡❈❡♣ qsr, t ●✁❳✁✱✁✉❥✁❦✁✈❪ ✸✁✹✱❤✁✐✁❥✁❦✁❧❡♠✁♥❡❥✁❦✁✇❡①❪❡✱✁✉✁▲②❜✁❝✁③❡④❥❡⑤, ❢✉ ❥✁❦❄✁⑥✁✱✁⑦✁⑧✁⑨✁⑩❥✁❶❆❡❷✁⑨❡⑩❡▲◆❸✁❹❀❡❁✁❺❡♦✱✁❨✺✁✻❬❡❭✁✲❡✳❱✁❲✱❊❡❂❝✁✱❡✉ ❻✴ ; ❙✁❼✁❯ ❽❃✁❄✁❅✁❆✁❇✁❈✁❉✁✩✁✲✁✳✁✴✁▲ ❾ 3. ❿✁✺✁➀✁➁ 2 ★✁✩✁✪✁✲✁✳✁✴ x1 = 20, x2 = 20, x3 = 0(♣ 2-3) ✶ , ✸✁✹✁✺✁✻✁➂✁➃✁✼ ✽✁✾✁✿ x1 ≤ 15▲◆❸✁❹✁●✁✲✁✳✁✴❊❬✁❭✁➄✼✁✽✁✾✁✿, ❜✁❝❿✁➅❖✁▲◆❄ x1 ≤ 15, ✹✁❣✁❤✁✐✁❥ ❦ x6 ❺ x1 + x6 = 15, x6 ≥ 0 (4.9) ❺♣ 4–7▲ ♣ 4–7 cj → 40 45 24 0 0 0 cB xB b x1 x2 x3 x4 x5 x6 45 x2 20 0 1 −1/3 1 −2/3 0 40 x1 20 1 0 1 −1 1 0 0 x6 15 1 0 0 0 0 1 ❜✁❝✁③✁④❥✁⑤, ➆ a31 ❶ 0, ❺♣ 4-8