第四章对偶问题及对偶单纯形法 无论从理论方面，还是实际应用方面，对偶理论是线性规划的重要的基础理论之 其主要内容是：每一个线性规划问题（称为原问题），都有一个与之对应的线性规划问题( 称为对偶问题)，原问题和对偶问题之间存在着密切的关系，在求出一个问题的解的同时 也自动的给出了另一个问题的解。 第一节对偶问题的提出 为了说明原问题和对偶问题间的关系，首先介绍下面例题中的线性规划问题的对偶 问题 例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) 920j-1,2.,m 如果把或号指 果号指列五意前表中，它们变 建弛多就更加清楚，从横向看比或 号指，从纵向看比般 T2 或始约束 min w Q11 012 1 03 01 ,果约束 inax z ci 把表晝建数a ，般建乘起来相加后不大于这意行务边 意行四 数b,就 癸把数意碧亦 乘起来相加完 柔起聚相需后不小于 或号 日标函整 果鍰号指 美起来相加就比般果或号指。 省祭函数且T得-鹂 max =CX; 满是Ar≤a (4.7) X≥0. 式L:刀建般果号指比 min w=Ob: (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.原问题第i个约束条件是“=”形式，不加变动，对偶问题的决策变量：为自由变 量 巨).原问题的每个决策变量马和对应的系数列向量乃=(，2 ,am,对应 对偶问题的一个约束条件.如果工)≥0，则对应的对偶问题的行约束为不等式；如果) 为自由变量，则对应的对偶问题的约束为“=”型约束； (四、如原问题的松驰变量或多余变量的值不为0，可以把原约束条件方程作为等 式约束条件处理。例如松弛变量表示要存此费的多余物资.就是这种情况。 例2.建立如下线性规划问题的对偶问题 min2=2x1+4x2+3x3 满足 1+22-3g≥5 2x1-3x2-2xg≤3 x1+x2+x3=2. 西≥0，对一切 解将第2个和第3个约束条件处理后得 min 2 2r1+4r2+3r3 满足 x1+2x2-3x3>5. -2x1+32+23≥-3 1+2+≥2 -x1-2-x3≥-2 王≥0，对一切. 设对偶变量为1,2,3和。因为最后两个变量都是对应者原问题的第3个约束条件方 程，所以它们的下标都是3.则对偶问题为： max w -3qz+2gs -2q 满足q1-2g+9g-6≤2， 2q1+32+9%-g≤4 -3q1+242+g-g≤3 g:≥0.对一切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)=-bQ -O40 因为min(-2)=-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.若原问题可行，而对偶问题不可行，则原问题的目标函数值无界 推论4.若对偶问题可行，而原问题不可行，则对偶问题的目标函数值无界 三、可行解是最优解的性质 定理3.设了是原问题(1.7)的可行解可是对偶向题(1.8)的可行解若C了=6 则了和夏分别是原何题和对偶问题得最优解。 证明：只需证明对原问题的得任一可行解X都有CX≤X:对对偶问题的任一可行 解Q都有Qb2.由弱对偶性对原间题的任一可行解X有CX≤=C了，所以 CX≤C灭，可见是原问题的最优解.同样的方法可证可为对偶问题的最优解。 四、对偶定理 定理4.若原何题有最优解那么对偶问顺一定有最优解且原间顺和对偶问题的最 优目标函数值相等 证明：原阿题(1.7)的标准型的系数矩阵为A'=(4,),其中单位矩阵I为松弛变量 的系数矩阵。设下为原问题(1.7)的最优解B为其对应的基矩阵。令C=(C,0,0) 为标准型中目标函数中决策变量的系数则由最优检验准则可知最优解了对应的检验数 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，且C-瓦A≤0即瓦A≥C。可见瓦为对偶问题(1.8) 的可行解且对应的目标函数值为-Q-CB-b。而原问题的最优解对应的目标 函数值为之=C了 =CBB-,从而6=C,由定理3可知石为对偶问题的最优解，且 与原问题的最优目标函数值相同。 如果原问题的目标函数为“血”型，同样可证明原问题和对偶问题的最优解的目标 函数为CBB-1b. 定理5.若下为原间题(1.7)的一满足最优检验的基本解，则反=CBB-1为对偶间 题的一可行解，且这两个解的目标函数的值相同。其中B为基本解下对应的基矩阵。 由上一定理的证明易见结论成立。 从上面定理的证明可以看出，对偶问题(1.8)的最优解万=CB-1, 这怡为为原 题(1.7)最优解表中松弛变量的机会费用，或者说是原何题最优解表中松弛变量检验数 Cs-zs的负数.即 如果原问题是求目标函数值最小，对偶问题是求目标函数值最大由于原向题多余变 量的系数构成一负单位矩阵，因此对偶问题的最优解是原问题最优解表中多余变量的机 会费用s的负数，或者说是最优解表中多余变量的检验数cs-2,即
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 3 00本0 CR 1 0 1 0 3 0 0 4 符1对果问题最优解 43 20 6 0 CB 96 0 21 20 20 16 9- 0 _10 0 16 。或回题律最优解为二0=430一比不建切地之量建+1二 或问题 m=3. -1,m+2 物上可 连间时是余标高数值最小约束方除是之列余解列 ←当一面塞麻，如便的北对果阿露东解欧宽足相系当 用大M法原两阶们法 系此况三种进建建算达是进节将 介绍对果事纯线法 第四节 单心形法 对或问题 max =CX 满足 AX≤b X>0 和对果问题 min=Qb 满足 ∫QA≥C 1Q≥0 物第情节定理5，或问题每一满足最优型、 策本解了都对应着对果问题 一策本可 清腰 一况算法，使在 单纯线法建每次选就建高本帆都满堡最优型 ,不一定满足非负约束就列使不满足 非负约束 ,量前数遂诚少，一 “全部策 量都满足非负约束就得最优解这况算 法称为对而不形法
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, ✼✒✸✒✹✒❁✒✢✒✣✒✸✒✹✒❍✒■✁➵❺➀✒ç✯ ✫✒➺➣ ✉✁➸✁➺, ➻ ➢ÿ✒✜◗✒✮✉✁➧♠ , ❿ ❄ ⑦✁➠✁✤♠ ★✒✶✁➼✁➽✁➾✒★✒✫✒⑩✒●✒✽➙✒➛➀✒ç✁↕✁➙, ❅✒➬✮ ➯➙✒➛⑩✁❶✒❮✒❰, ➽✁➾✒■✒❿✒➬➙✒➛ ⑩✁❶✒❮✒❰✒★✁✭✒➔✷✒Õ✁➚✁➪✁➶✁➹✒✯⑧✮✁➘✁✴✬➴✫✬✭✒➔✒✽➙✒➛⑩✁❶❀❮✒❰, ➾ ý✁❺➀✒ç✒●, ➣ ✉✁➧ ♠✺✒✻ ò✒ô✁➷✁➬✁➮✁➱✯
第四章对偶问题及对倡单纯形法 对偶单纯形法的计算步骤： 记SN为非基变量的下标的集合 第一步找到一个满足最优检验的初始基本解 第二步检验当前解是否可行.若可行，已得最优解否则转入下一步 第三步 选择最小一行的变量作为换出变量，记这一行为”，转入下一步 第四步检查，若一，全大于或等于0，则问题无解，停止计算。否则，选择使 下式达到最小的方对应的变量作为换入变量： mi血（二之4，0,表示 基变量取值减少，而0.i=1.2....6 解选择x4,工6,6为基变量，令x1=2=3=0,则易得出x4=-20,x5= -6.xe=-10 为了使初始基本解的基变量的系数矩阵为单位矩阵，用-1乘3个约束方程.因为是 求目标函数值最小，用一S≤0检验最优.初始单纯形表如表44. 授4-4 6 32000 B TB 0 000 表中所有检验数一S≤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 以α13为偏问进行转问题此，得表4-5. 表4-5 CB R 10 0 2 -2 0 zj-cj -4 表4-5中%=-1≤0，令”=2. mm(-品分}=4了=2 以a2为偏问进行转问题此，得表46. 表4-6 63200 0 CB TB b 工1 工4 T5 T6 2 T3 16 0 0 1 4 0 3 1 0 0x6 10 -1 0 0 -1 0 1 3 2 -1 4 0 0 0 -1 -4 0 表4-6满足最优型为可行，目得最优解。 第五将对偶变量的经济意对一影偶价格 在第一章第三节中，等们用图解法求出了第一章例1的最优解（图1-1）。在实际决 基中，决基者需要考感的 个问题是纯加某种、源是否有利。从图1可 若纯加B 可的可用时原可筹限额则目标函数值纯加，而纯加4得间的可用工时搔目标函数程 不纯加。下面对一的问题考虑这种变即。 设有如下形性的原问题： 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 ✷✒✖★✒➯✔ÿ ➤ , ➀
0 第四章对偶问题及对偶单纯形法 优目标函数值为： 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+i 第六节对偶单纯形的的一个应用增果约武条件) 在产生变的优以后，又增加一且或条起可以用对者多 立解余必对看问题从头做起.其步行如下： 第一步检验看来的最优解是否满足新增加的或束条件.若满足，则看最优解就是新 问题的最优解：若余满足，就进行下一步： 第三步将新增加的或束条件加入松地变量或，余变量后加到看来的最优若松弛表 费去，看来的基变量 变量对的定证明阵簧署位明阵.显然韩 余量组成新的基.进行初等变换，将基 得到的是一且满足最优检验的余可行的基 本解 第三步用对若松多立最优解 结3 色量限起婆对队经 量6得 x1+6=15,6≥0 (4.9) 得表4-7. 表4-7 404524 0 0 0 .2/3 0 1 0 0 0 进行初等变换，推a41负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