6 第七章整数规划 五、0-1变量多项式 如果在前面的投资问题中，补充两点：1.项目必须在项目k和项目1同时投资的前 提下才可以投资2.项目k和项目1同时投资时，可增获利润.那么这时的棋型将成为： max 满足 p≤xk, 0≤与≤1且为整数，对一切 模型的目标函数和约束方程中都出现了变量多项式，从而成为一个非线性的0-1规 划问题。采用下面的方法，可以将问题转化为线性的0-1规刻问题 1.所有x:的非零幂用x,替换.这是因为 x号=x,n=1,2, 2.用0-1变量xQ替换乘积ⅡcQ,Q为连乘的马的下标集合，xQ应满足： 之+1-0 (.1) o≤M1Q (7.2) 式中1Q一集合Q中元素的个数. 式（亿.1）的成立将保证，当对一切j∈Q有工)=1时，xQ必等于1. 式(72)的成立将保证仅当对一切j∈Q,有=1时，xQ才可等于1，任一)=0 时，则xQ必等于0. 对于上面的例题可用Y代替x,但需增加约束 ≥xk+1+1-2 士≤(k+)/2 模型变为： max&= 满足 ∑4≤b, = xp≤x, x>xk+x1-1. 丈≤(rk+)/2. 0≤西≤1，对一切j
6 ☞✁✌✁✍✏✎✁✑✁✒✁✓ ➷✿ 0–1 ➬❀➮❀➱❀✃➊ ✶s❽➇ ✻ ✗❇ ❒ ✭✮❿♣, ❐❿❒Ó ✂ : 1. ❊ ➎ p ✲✳ ❽❊ ➎ k â❊ ➎ l ë➅❿❇❒✗➇ ❮ ➊✌å✢✌✣ ❇ ❒ ; 2. ❊ ➎ k â❊ ➎ l ë➅✁❇❒➅, ✢✌ß✁❰✁❍✁■ c 0 . ❚✁➢❯✌➅✗✌è✌é✁✞✌✾▲: max z = Xn j=1 cjxj + c 0xkxl ; ◆✌❖ Xn j=1 ajxj ≤ b, xp ≤ xkxl , 0 ≤ xj ≤ 1➴✌▲✌✴✦ , ❩ ✩✁❞j. è❭é❭✗ ➎➟➏❭➑✦ â❭ï❭ð➶❭ú ♣t ù❭ó❭▼ ✙❭✚➆❊✖✉, ❂❭➌❭✾▲❭✩❭➡❭✇✏❭✑❭✗ 0–1 ✒ ✓ ✭✌✮. ❜ ➋➊✁✻✗✌➶❣ , ✢✌✣✁✞✭✌✮✁Ï✌❚✌▲✏✌✑✌✗ 0–1 ✒✌✓✭✌✮: 1. ✷ ❜ xj ✗✇✁Ð✁Ñ➋ xj ➯✁Ò. ❯✌★✌❳✌▲ x n j = xj , n = 1, 2, . . . . 2. ➋ 0–1 ✙✌✚ xQ ➯✁Ò✁Ó✁Ô Q j∈Q xj ,Q ▲✌➢✁Ó✗ xj ✗➊✌➏✁Õ● ,xQ á✌◆✌❖: xQ ≥ X j∈Q xj + 1 − |Q|, (7.1) xQ ≤ ( X j∈Q xj )/|Q|. (7.2) ✉ ♣ |Q|—- Õ ● Q ♣❺Ï✁Ö✗➡✦ . ✉ (7.1) ✗✌✾✫ ✞❡✁❢, ✇❩ ✩✁❞ j ∈ Q ❜ xj = 1 ➅,xQ ✲✌❈❹ 1. ✉ (7.2) ✗✌✾✫ ✞❡✁❢, ×✁✇❩ ✩✁❞ j ∈ Q, ❜ xj = 1 ➅,xQ å✢✌❈❹ 1, Õ✌✩ xj = 0 ➅, ⑤ xQ ✲✌❈❹ 0. ❩✌❹➂✁✻✗ ✵✌✮✢✌➋ x 0 ➭✁➯ xkxl , ✧✁❏ß✌àï✌ð x 0 ≥ xk + xl + 1 − 2, x 0 ≤ (xk + xl)/2. è✌é✌✙▲: max z = Xn j=1 cjxj + c 0x 0 ; ◆✌❖ Xn j=1 ajxj ≤ b, xp ≤ x 0 , x 0 ≥ xk + xl − 1, x 0 ≤ (xk + xl)/2, 0 ≤ xj ≤ 1, ❩ ✩✁❞j
57.4分枝定界算法 0≤x≤1 为整数，对一切， x为整数 至此，问题已成为一个线性0-1规划问题， §7.4分枝定界算法 求解整数规划问题比较成功的方法是分枝定界算法.这种算法，可以解纯整数规划 问题和混合格数规问题 这个算法的步骤是先不考虑整数约束条件求出相应线性规划问题的最优解，如果这 个解满足已定的整数约束，它就是整数规划问题的最优解.如果有一个或多个整数约束未 被满足，就任选一个应是整数而不是整数解的变量工，设它的解是，不是整数定义 是小于的最大整数，将原问题分成两枝.一枝是原问题约束条件加xk≤⑦]构成，另 一枝是原问题约束条件加≥⑦】+1构成.解这两个分枝的新线性规划问题。对不满足 原问题整数约束的新问题，再按上述办法进行新的分枝，直到发生下面所说的情况才停止 分枝我们仍用本章的例1来说明。表7一1为例1的不考虑整数约束最优单纯形表 表7- 64000 CB 2 6 0 0 6 ci-zi 00-元-0 这个问题的相应线性规划问题的最优解是x1=多，2=2，工1不符合整数约束]= 2,将原问题分别加上1≤2和1≥3就构成两个子问题为描述方便，构造一个树形图 原问题为出发节点1，向下分成两枝，如图7-4. 图7-4 图7-5 现在画出原问题及新加约束条件的图解，如图7-5.图中，区域α表示第1个子间题 的可行域区域b表示第2个子问题的可行域.画阴影的区域（不包括边界线）排除在两 个子问题的可行域之外，但它不包含1为整数的解，这样就不会在解两个子何题时把最 优可行解遗漏掉
§7.4 Ø✁Ù✁Ú✁Û✁Ü☎Ý 7 0 ≤ x 0 ≤ 1, xj▲✌✴✦ , ❩ ✩✁❞j, x 0▲✌✴✦ . s✌❨, ✭✌✮❿Ø✾ ▲✌✩✌➡✏✌✑ 0–1 ✒✌✓✭✌✮. §7.4 Þ✤ß✤à✤á✤â✡➽ ✱✖ ✴✦❭✒❭✓✭❭✮➥ã➧ä✾✖å❭✗❭➶❣ ★❹æ✖ç✖è✖é✖ê✖ë. ❯❭Ô❢❭❣, ✢❭✣❭✖✖ì✴✦❭✒❭✓ ✭✌✮✌â✁í● ✴✦✌✒✌✓✭✌✮. ❯❭➡❢❭❣✗✖î✖ï★❭➹❊❭õ❭ö✴✦ ï❭ð❭ñ❭ò❭✱❭ù✖♦❭á✏❭✑❭✒❭✓✭❭✮✗❭✔❭✕❭✖, ✶❭s❭❯ ➡ ✖ ◆✌❖❿Ø✝▲✗✴✦ ï✌ð, ➞❉ ★✌✴✦✌✒✌✓✭✌✮✗✌✔✌✕✌✖. ✶✌s❜✩✌➡❫ ➆✌➡✌✴✦ ï✌ð✁ð ❛◆❖, ❉ Õ×✩➡á★✴✦➌✌❊★✌✴✦✖✌✗✙✌✚ xk, ❵ ➞ ✗✖ ★ bk, ❊★✴✦ , ▲❿ñ [bk] ★ ✥❹ bk ✗✌✔✌➔✴✦ , ✞ ➤✌✭✌✮❴✾Ó✁ò. ✩✁ò✌★✁➤✌✭✌✮✌ï✌ð✌ñ✌òà xk ≤ [bk] →✾ , ➣ ✩✁ò✌★✁➤✌✭✌✮✌ï✌ð✌ñ✌òà xk ≥ [bk] + 1 →✾ . ✖❯✌Ó✌➡❴ ò ✗Ò✏✌✑✌✒✌✓✭✌✮. ❩❊◆✌❖ ➤✌✭✌✮✌✴✦ ï✌ð✗Ò ✭✌✮, →✁ó➂✌➨✁ô❣➀✌þÒ✗❴ ò, ✗✁✜➛❡➊✁✻✌✷✽✌✗❧✁♠✌å✁õ✁❳ ❴ ò. ☛✌☞✁ö✌➋✁✬✁÷✁ø✁ù 1 ú✁û☎ü. ❬ 7–1 ý ù 1 ø✁þ✁ÿ✁✁✂✁✄✁☎✁✆✁✝✁✞✁✟✁ì✁✠✁✡✁☛ ✡ 7–1 cj → 6 4 0 0 0 cB xB b x1 x2 x3 x4 x5 4 x2 2 0 1 1 3 − 1 3 0 6 x1 5 2 1 0 −1 6 2 3 0 zj 6 4 1 3 8 3 0 cj − zj 0 0 − 1 3 − 8 3 0 ☞✁✌✁✍✁✎ø✁✏✁✑✁✒✁✓✁✔✁✕✍✁✎ø✁✝✁✞✁✖✁✗ x1 = 5 2 ,x2 = 2, x1 þ✁✘✁✙✁✂✁✄✁☎✁✆. [b1] = 2, ✚✁✛✍✁✎✁✜✁✢✁✣✁✤ x1 ≤ 2 ✥ x1 ≥ 3 ✦✁✧✁★✁✩✌✁✪✁✍✁✎. ý✁✫✁✬✁✭✁✮, ✧✁✯✁✰✌✁✱✠✁✲. ✛ ✍✁✎ý✁✳✁✴✁✵✁✶ 1, ✷✹✸✜ ★✁✩✁✺, ✻ ✲ 7–4. ✲ 7–4 ✲ 7–5 ✼✁✽✁✾✳✁✛✍✁✎✁✿✁❀✁✣☎❁✆❁❂✁❃✖ø✁✲❁✖, ✻ ✲ 7–5. ✲❅❄, ❆✁❇ a ✡✁❈✁❉ 1 ✌✁✪✁✍✁✎ ø❁❊❁❋❇, ❆❁❇ b ✡❁❈❁❉ 2 ✌❁✪❁✍❁✎ø❁❊❁❋❇. ✾❁●❁❍ø❆❁❇ (þ❁■❁❏❁❑❁▲❁✒) ▼❁◆✽✩ ✌❁✪❁✍❁✎ø❁❊❁❋❇❁❖❁P, ◗❁❘þ❁■❁❙ x1 ý✂❁✄✖ø❁✖, ☞❁❚✦ þ❁❯✽✖ ✩ ✌❁✪❁✍❁✎❁❱❁❲✝ ✞✁❊✁❋✁✖✁❳✁❨✁❩
8 第七章整数规划 现在求第1个问题的最优解，将1≤2代入表7-2中的第2个方程并加入松弛变 量得下式： 两-+= 加到表7-1中去，如表7-2. 7-2 64000 1 0 00 -21 64 Ci-Zi 在上转轴，得第一个子问题的最优解表，如表7-3. 表7-3 64000 CB 3 0 0 0 6 4 0 4 0 0 -1 0 为解第2个子问题，将1≥3即1=6+3代入表7-1的第2个方程整理后得： 6+有到4+西=-号 将上式加进表7-L,得到表7-4 表7-4 64000 CB TB 6 12 3T4T5 0 05 6 0 Ci-Z 在g上转轴，得如表7-5
8 ❬✁❭✁❪❴❫✁❵✁❛✁❜ ✼✁✽✁❝❉ 1 ✌✁✍✁✎ø✁✝✁✞✁✖, ✚ x1 ≤ 2 ❞✁❡✡ 7–2 ❄✝ø✁❉ 2 ✌✭✁❢, ❣ ✣❡✁❤✁✐✁❥ ❦ x5 ❧✸✁♠: 1 6 x3 − 2 3 x4 + x5 = − 1 2 . ✣✁♥✡ 7–1 ❄✹♦, ✻✡ 7–2. ✡ 7–2 cj → 6 4 0 0 0 cB xB b x1 x2 x3 x4 x5 4 x2 2 0 1 1 3 − 1 3 0 6 x1 5 2 1 0 −1 6 2 3 0 0 x5 − 1 2 0 0 1 6 − 2 3 1 zj 6 4 1 3 8 3 0 cj − zj 0 0 −1 3 −8 3 0 ✽ a34 ✤✁♣✁q, ❧ ❉✰ ✌✁✪✁✍✁✎ø✁✝✁✞✁✖✁✡, ✻✡ 7–3. ✡ 7–3 cj → 6 4 0 0 0 cB xB b x1 x2 x3 x4 x5 4 x2 9 4 0 1 1 4 0 − 1 2 6 x1 2 1 0 0 0 1 0 x4 3 4 0 0 − 1 4 1 − 2 3 zj 6 4 1 0 4 cj − zj 0 0 −1 0 −4 ý✖✁❉ 2 ✌✁✪✁✍✁✎, ✚ x1 ≥ 3 r x1 = x5 + 3 ❞✁❡✡ 7–1 ø✁❉ 2 ✌✭✁❢, ✂✁s✁t❧: − 1 6 x3 + 2 3 x4 + x5 = − 1 2 . ✚ ✤ ♠ ✣✁✉✡ 7–1, ❧ ♥✡ 7–4. ✡ 7–4 cj → 6 4 0 0 0 cB xB b x1 x2 x3 x4 x5 4 x2 2 0 1 1 3 − 1 3 0 6 x1 5 2 1 0 − 1 6 2 3 0 0 x5 −1 2 0 0 −1 6 2 3 1 zj 6 4 1 3 8 3 0 cj − zj 0 0 − 1 3 − 8 3 0 ✽ a33 ✤✁♣✁q, ❧✻✡ 7–5
57.4分当也界算法 右75 ci→ 64000 CR R6 T 0 033 c-为 0 00 -4 从图7-4开始的树形图增加其个节点.如图7-6
§7.4 ✈✁✇✁①✁②✁③❅④ 9 ✡ 7–5 cj → 6 4 0 0 0 cB xB b x1 x2 x3 x4 x5 4 x2 1 0 1 0 1 2 6 x1 3 1 0 0 0 -1 0 x3 3 0 0 1 -4 -6 zj 6 4 0 4 2 cj − zj 0 0 0 −4 −2 ⑤✲ 7–4 ⑥✁⑦ø✱✠✁✲✁⑧✣✩ ✌ ✵✁✶, ✻ ✲ 7–6