6 第六章运输问题 表69 销地 B2 B 产量 产地 ② A 7 8 1 4 3 (5) × 42 2 3 (2) (6) 销量 2 1 7 6 在22处写上0并画上圈的目的是使带圈的个数保持为n+m一1个.因为前面已 经说过，画圈的地方正好是基变量。而基变量必须是n+m一1个 从以上的例子可以看出，西北角法的一般步骤为： 1.先决定左上角变量的值，令这个变量取尽可能大的值，并在这个位置上所填的数字 外面画上园： 2.在填数的格子所在的行或列的应该为0的格子上打“×”.若行和列都应该取0，则 在行上打了“×”以后，就不能在列上打“×”：反之在列上打了“×”以后，就不能在行上打 “X”: 3.对没有填数及打“×”的地方重复上述步骤，若剩余空格的左上角的变量应取0，则 应写上0并画圈. 二、最小元素法 用西北角法求初始基本可行解时没有涉及©，若能将©%的值考感进去，常可使得基 本可行解对应的目标函数值 的值小些，比较靠近最优解，从而减少迭代次数 仍以例1为例.最小元素法不是从工1开始，而是从，值最小的空格开始（若有儿个 地方同时达到最小，则可任取 个.在例1中，e=1最小故我们先定的值.与西北 角一样，给x21尽可能大的值，即令x21-min{3,5}=3,在x21处填上3并画圈，然后在 x1131处打上“×”.在做完上一步后，在没有填数和打“×”的空格内再找一个c的最小 值，这里24 =2,g=2都是最小值，故可任取一个例如取c,令 mim471=4 填上4并可圈.用同样的方法可得21=2,2=3,14=4，工12=5，其余的地方都应该打 “×”.这就是初始基本可行解，画圈的地方为基变量，如表6-10
6 ❶✑❷❁❸❺❹✡❻✑❼❁❽ ⑦ 6–9 ✵✡✲ B1 B2 B3 B4 ✱✹ ✱✡✲ (2) (1) × × A1 7 8 1 4 3 × (0) (5) × A2 2 6 5 3 5 × × (2) (6) A3 1 4 2 7 8 ✵✹ 2 1 7 6 ✟ x22 ➊✁s➐ 0 ❳ ❲✡➐❹ ✘➌➋ ✘❢✡t✁➍✁❹✘✰✇✡➎✁➏✬❴ n + m − 1 ✰✛ ➍❴✁✫➑ ✿ ➞✵r , ❲❹ ✘✲❈✁➆✁✮❢õ✘ ✹ ✛ ➈õ✘ ✹ ❐✡❒❢ n + m − 1 ✰✛ ✭ ④ ➐ ✘ ➶✁➐③✡④✡➌⑧, ➑✁➒✉Ø✡✘✡✓✁✢✁➓✁➔✡❴: 1. ✎✖❄✁t✡➐✉✘ ✹✡✘✁⑦, ⑧✜✰✁✘✹ ❼ ⑤✡③s✁⑥✘✁⑦, ❳ ✟✡✜✰✡❛✁❾➐ó✁❸✡✘✡✇✁② ❝ ➑✁❲✡➐❹ ; 2. ✟❸✡✇✡✘❷✁➐ó ✟ ✘✡➄✁➉⑤✘✡✸✡♣✡❴ 0 ✘❷✁➐➐❺ “×”✛ ✮ ➄✡✺⑤➸✸✡♣❼ 0, ❘ ✟➄ ➐❺ ➝ “×” ④✡ø, ➣✡ûs✟ ⑤➐❺ “×”; →✁③✟ ⑤➐❺ ➝ “×” ④✡ø, ➣✡ûs✟➄ ➐❺ “×”; 3. ➣ ✤ ✒✁❸✡✇✡✼✁❺ “×” ✘✲❈✁↔✁↕➐✁❵➓✁➔, ✮✁➙✧✁❶❷ ✘t✡➐✉✘✘ ✹✡✸❼ 0, ❘ ✸s➐ 0 ❳ ❲❹✛ ➛❥♠➜❦➝❦➞❦➟➠♣ ✾✁➑✁➒✉Ø ❂ ö✡÷õ✡ã③➄ Ù✡❰✁✤✒✁➡✡✼ cij , ✮✡s✁➢ cij ✘✁⑦✁➤✁➥✡❿✡⑨, ➟③ t ✯õ ã ③➄ Ù ➣✡✸✡✘➌➋➦✛✁➧✡✇✁⑦ z = Xm i=1 Xn j=1 cijxij ✘✁⑦✡✉Ï , à❁á✁➨✁➩✡❆✡ôÙ , ✭ ➈✁✬✡❇✁➫✁➃✁➭✡✇✛ ➯ ④ ➶ 1 ❴ ➶✛ ❆↔✉✰➲✰➳↔Øû❢↔✭ x11 ④÷, ➈❢↔✭ cij ⑦↔❆↔✉↔✘✰❶❷ ④÷ (✮ ✒✰❤✰ ✲❈↔②❰✰➵✴↔❆↔✉, ❘③✺❼ ✓ ✰ )✛➜✟➶ 1 ✏ ,c21 = 1 ❆↔✉, ❿ ➎↔➏✎↔❄ x21 ✘✰⑦✛ ❩✰➑✰➒ ✉✓ ✠ , Ñ x21 ⑤✡③s✁⑥✘✁⑦, ✐⑧ x21 = min{3, 5} = 3, ✟ x21 ➊❸ ➐ 3 ❳ ❲❹ , Ó ø✟ x11,x31 ➊❺ ➐ “×”✛Û✟↔➻✰➸↔➐✓✰➓ø, ✟✰✤✒✰❸↔✇↔✺✰❺ “×” ✘✰❶❷❬➺❻↔ß✓ ✰ cij ✘↔❆↔✉ ⑦, ✜✁✾ c24 = 2,c33 = 2 ➸❢ ❆✡✉✁⑦, ❿③✺❼ ✓ ✰✛ ➶❯❼ c33, ⑧ x33 = min{4, 7} = 4, ❸ ➐ 4 ❳ ❲❹✛ ✾✡②✠ ✘✡❈✡Ø③✯ x24 = 2, x32 = 3,x14 = 4,x12 = 5, ➡✧✡✘✲❈ ➸✸✡♣✁❺ “×”✛♦✜✡➣❢ ö✡÷õ✡ã③➄ Ù , ❲❹ ✘✲❈✡❴õ✘ ✹, ❯⑦ 6–10✛
562初始基本可行解的求法 7 值610 说地 B2 Ba 产明 产地 (5 (4) Al 2 9 10 7 9 (3 (2 A2 1 3 2 5 3) (4) 5 说明 3 8 4 6 保 分别计算 函据值1任2： 一处子例1中里西北角法任里最角元素法求得变基本之共解变目标 1=2×3+9×6+3×2+4×3+2×1+5×6=110 22=1×3+9×5+4×3+2×4+7×4+2×2=100 由、之见由最角元素法球得 初始基本之共解没好些标 巴侧2中共任尽完之打×”变情祝，这时保带仍需米甲 一标 置 生器 例3根据。一1山里最角元素法求初始基本之共解标 值11 说地 B 产明 产地 11 2 x13 A 1 2 2 1 22 23 A2 3 1 3 2 32 33 说明1 2 4 根先法处打野令-2m处打最后令 面。世所深动麦处共只大0阳并子从发四
§6.2 ý✡þ✡ÿ✁✁✂✁✄✁☎✝✆✁✞✁✟ 7 ⑦ 6–10 ✵✡✲ B1 B2 B3 B4 ✱✹ ✱✡✲ × (5) × (4) A1 2 9 10 7 9 (3) × × (2) A2 1 3 4 2 5 × (3) (4) × A3 8 4 2 5 7 ✵✹ 3 8 4 6 ➎✡➏❪✡❫✁➻✁➼✡✓➊ ➐✡➑➶ 1 ✏✾✁➑✁➒✉Ø✡✺✡✾✡❆✡✉✁➲✁➳✡Ø❂ ✯✡✘õ✡ã③➄ Ù ✘➌➋➦✛ ➧✡✇✁⑦ z1 ✺ z2: z1 = 2 × 3 + 9 × 6 + 3 × 2 + 4 × 3 + 2 × 1 + 5 × 6 = 110 z2 = 1 × 3 + 9 × 5 + 4 × 3 + 2 × 4 + 7 × 4 + 2 × 2 = 100 ❦ ❥③➀✑❦❁❆✡✉✁➲✁➳✡Ø❂ ✯✡✘✡ö✡÷õ✡ã③➄ Ù✡✤✮ Ï✡✛ ✾↔❆↔✉✰➲✰➳↔Ø❰ , ✳↔➧↔➠✴✰✫➑➶ 2 ✏➄↔✺⑤➸③❺ “×” ✘✰➽✰➾, ✜↔❰➎↔➏➯✰➚✰➪✾ ❩✁✫➑ ✓ ✠ ✘✡❈✡Ø➊❾ ✛ ❆ø, ➎✡➏❻✁➶⑧✡✓✁❱✛ ✾✡❆✡✉✁➲✁➳✡Ø❰ , ❯✁➹➈✁➙➊✓✡➄✁➉✡✓⑤➅✁❸✡✇✡✺✡➅✁❺ “×” ✘❷✁➐❰ , ➈✜❸✡✇, û✁✜❺ “×”✛ ✜✁✠✡➻✘➌➋ ✘❢ ❴ ➝➎✸ ❲❹ ✘✰✇✡❴ n + m − 1 ✰✛ ❙ 3. ✈✁✇⑦ 6–11, ✾✡❆✡✉✁➲✁➳✡Ø❂ ö✡÷õ✡ã③➄ Ù✡✛ ⑦ 6–11 ✵✡✲ B1 B2 B3 ✱✹ ✱✡✲ x11 x12 x13 A1 1 2 2 1 x21 x22 x23 A2 3 1 3 2 x31 x32 x33 A3 2 3 1 4 ✵✹ 1 2 4 ✈ : ✎⑧ x11 = 1, ✟ x12,x13 ➊❺ “×”; ❻ ⑧ x22 = 2, ✟ x21,x23 ➊❺ “×”; ❆ø⑧ x33 = 4, ✜✡❰✡➋➅✁❸✡✇✡✘❷✁➐✁➈✁➙➊✓✡➄, ➈✡ss✡⑥ x31 = 0,x32 = 0, ❳ ❲✡➐❹ , ✭ ➈✁✯✡✴ ⑦ 6–12 ó✁❛✡✘✡ö✡÷õ✡ã③➄ Ù✡✛
8 第六章运输问题 表6-12 销地 B B2 产量 产地 A 1 2 1 (2) (0の (O) (4) 销量 1 2 4 此时若在1和如处打“×，分为面图的个数只有3个显然不是基本可行解了 三、差值法 差值法一般能够得到比用上述两种方法更好的初始基本可行解。这个方法与最小元 素法不同的地方是在需要考虑的突格中，首先做算各行各列中最小的与次小的句之 间的算术差.在具有最大差值的”个行或列中，选择具有最小的的空格来决定基变量 的值.这样，避。 将运量分配到这一行或列中具有与最小的差值较大的次小的的空格 中，而使得目标菡数较大.此外用最小元素法时需要些意的地方在这里仍然适用，以保证 基变量的个数为n+m-1.仍以例1为例. 表6-13 销地 B B 产量 产地 (3) 10 9 1 A 8 4 2 5 销量 3 8 4 6 由表-13中的c可见，在第一行中，次小与最小的c之间的差为7-2=5，第 列为2-1-1，其余如表6-13所示.在所有行和列中，第一行的差值5为最大，在第一行 的c中C11=2最小，故先决定x11的值.和上述两种方法一样，给x11尽可能大的值，即 mim3,9-3.在1处填上3，并画上圈.此时第一列已满足，故在 31处 打上“×”.在剩余的格子中，以同样的方法重复做下去，最后得出的基本可行解如表614 所示
8 ❶✑❷❁❸❺❹✡❻✑❼❁❽ ⑦ 6–12 ✵✡✲ B1 B2 B3 ✱✹ ✱✡✲ (1) × × A1 1 2 2 1 × (2) × A2 3 1 3 2 (0) (0) (4) A3 2 3 1 4 ✵✹ 1 2 4 ❥❰ , ✮✟ x31 ✺ x32 ➊❺ “×”, ❪✁❴✁❲❹ ✘✰✇ ➈✒ 3 ✰ , Ò✡Óû❢õ✡ã③➄ Ù✡➝. ➘❥♠➴❦➷❦♣ ➬⑦✡Ø✡✓✁✢s✁❊✯✡✴✑à✾➐✁❵✬➀✬✩❈✬Ø✡➮✁✮✬✘✬ö✡÷õ✡ã③➄ Ù✬✛♦✜✰❈✡Ø✡❩✬❆✡✉✡➲ ➳✡Øû ②✡✘✲❈ ❢✟✁➚✡✤➤✁➥✡✘✁❶❷ ✏ , ➇ ✎➻✁➼✁①✡➄✁①⑤ ✏❆✡✉✡✘ cij ❩✁➭✡✉✡✘ cij ③ ➱ ✘✁➼✁✃➬✡✛♦✟✡➲✒✡❆⑥➬⑦✡✘❪✰ ➄✁➉⑤ ✏ , ❐✁❒➲ ✒✡❆✡✉✡✘ cij ✘✁❶❷ ➯✖❄✡õ✘ ✹ ✘✁⑦✛♦✜✁✠, ❮✁❰➢✙✡✹✡❪✡Ð✡✴✜ ✓✡➄✁➉⑤ ✏❁➲✒✁❩✡❆✡✉✡✘➬⑦✡á⑥ ✘✁➭✡✉✡✘ cij ✘✁❶❷ ✏ , ➈ t ✯➌➋➦✛✁➧✡✇✡á⑥✛ ❥❝✡✾✡❆✡✉✁➲✁➳✬Ø❰✡➚✡✤✡Ï✻✡✘✲❈ ✟✡✜✡✾✁➯Ó✁Ð✾, ④ ➎✸ õ✘ ✹✡✘✰✇✡❴ n + m − 1✛❽➯④ ➶ 1 ❴ ➶✛ ⑦ 6–13 ✵✡✲ B1 B2 B3 B4 ✱✹ ✱✡✲ (3) A1 2 9 10 7 9 × A2 1 3 4 2 5 × A3 8 4 2 5 7 ✵✹ 3 8 4 6 ❦ ⑦ 6–13 ✏✘ cij ③➀, ✟ ➃✡✓✡➄ ✏ , ➭✡✉✁❩✡❆✡✉✡✘ cij ③ ➱ ✘➬ ❴ 7 − 2 = 5, ➃✡✓ ⑤❴ 2 − 1 = 1, ➡✧✡❯⑦ 6–13 ó✁❛✛ ✟ó✡✒✡➄✡✺⑤ ✏ , ➃✡✓✡➄✡✘➬⑦ 5 ❴✡❆⑥ , ✟ ➃✡✓✡➄ ✘ cij ✏ c11 = 2 ❆✡✉, ❿ ✎✖❄ x11 ✘✁⑦✛ ✺➐✁❵✡➀✡✩❈✡Ø✡✓✠ , Ñ x11 ⑤✡③s✁⑥✘✁⑦, ✐ ⑧ x11 = min{3, 9} = 3✛♦✟ x11 ➊❸ ➐ 3, ❳ ❲✡➐❹✛ ❥❰ ➃✡✓⑤ ✿➔✬→, ❿ ✟ x21,x31 ➊ ❺ ➐ “×”✛ ✟➙✧✡✘❷✁➐ ✏ , ④ ②✠ ✘✡❈✡Ø✁↔✁↕➻ ➊⑨, ❆ø✯✡⑧✡✘õ✡ã③➄ Ù ❯⑦ 6–14 ó✁❛✛