第六章运输问题 在线性规划问题中，有一类特殊类型的问题一运输问题。这类问题主要研究把某种 物资从若干个产地调运到若干个销地，每个产地的供应量和每个销地的销售量及从一个 产地到一个销地的运输费用已知，要求确定一个总运费最少的方案， 6.1运输问题的线性规划模型 引例设某种物资（如粮食，棉花，煤炭等）有m个产地A1,42,,Am,产量分别为 a1,a1,am个单位：另外有n个销地B1,B2,,Bn,销量分别为b1,b1,,bn个单位。 又假设产销是平衡的，即 三- 此外，由产地A:向销地B运输每单位货物的运价为，问应该如何调运这种货物才能 使总的运费最小？ 解设为由产地A:向销地B调运这种货物的数量。连同单位运价可以列成 表6-1和表6-2 单位运价表 表6-1 销地 B Bn 产地 4 92 21 C2n Am Cml Cm2 Cmn 平衡表 表6-2 销地 B2 产量 产地 11 11 12 A2 x22 0 A 销量 02 由A,运出去的物资总量应等于A,的产量，即 xy=a,i=1,2.…m 1
✂✁✂✄ ☎✂✆✂✝✂✞ ✟✡✠✡☛✡☞✡✌✡✍✡✎✑✏, ✒✡✓✡✔✡✕✡✖✡✔✡✗✡✘✍✡✎ —- ✙✡✚✍✡✎✡✛✢✜✔ ✍✡✎✡✣✡✤✡✥✡✦✡✧✡★✡✩ ✪✬✫✬✭✬✮✬✯✬✰✬✱✬✲✬✳✙✬✴✮✬✯✬✰✬✵✬✲, ✶ ✰✬✱✬✲✘✬✷✬✸✬✹✬✺✬✶✰✬✵✬✲✘ ✵✬✻✹✬✼✭ ✓ ✰ ✱✡✲✴✡✓✰✡✵✡✲✘✡✙✡✚✡✽✡✾✑✿❁❀, ✤✡❂✡❃✡❄✓ ✰✡❅✙✡✽✡❆✡❇✡✘✡❈✡❉✛ §6.1 ❊●❋●❍●■●❏●❑●▲●▼●◆●❖◗P ❘✡❙ ❚✡★✡✩✪✡✫ (❯✡❱✡❲, ❳✡❨, ❩✡❬✡❭) ✒ m ✰✡✱✡✲ A1, A2, . . . , Am, ✱✹✡❪✡❫✡❴ a1, a1, . . . , am ✰✡❵✡❛; ❜✡❝✡✒ n ✰✡✵✡✲ B1, B2, . . . , Bn, ✵✹✡❪✡❫✡❴ b1, b1, . . . , bn ✰✡❵✡❛✛ ❞✡❡❚✱✡✵✡❢✡❣✡❤✘, ✐ Xm i=1 ai = Xn j=1 bj . ❥❝, ❦ ✱✡✲ Ai ❧✵✡✲ Bj ✙✡✚✡✶❵✡❛✡♠✡✪✘✡✙✡♥✡❴ cij ✛♦✍✸✡♣✡❯✡q✳✙ ✜✡✩♠✡✪✡r✡s t✡❅✘✡✙✡✽✡❆✡✉? ✈ ❚ xij ❴✑❦ ✱✡✲ Ai ❧✵✡✲ Bj ✳✙ ✜✡✩♠✡✪✘✡✇✡✹, ①✡②❵✡❛✙✡♥ cij ③✡④✡⑤✡⑥ ⑦ 6-1 ✺⑦ 6-2✛ ❵✡❛✙✡♥⑦ ⑦ 6–1 ✵✡✲ B1 B2 . . . Bn ✱✡✲ A1 c11 c12 . . . c1n A2 c21 c22 . . . c2n . . . . . . . . . . . . . . . Am cm1 cm2 . . . cmn ❣✡❤✡⑦ ⑦ 6–2 ✵✡✲ B1 B2 . . . Bn ✱✹ ✱✡✲ A1 x11 x12 . . . x1n a1 A2 x21 x22 . . . x2n a2 . . . . . . . . . . . . . . . . . . Am xm1 xm2 . . . xmn am ✵✹ b1 b2 . . . bn ❦ Ai ✙✡⑧✡⑨✡✘✪✡✫✡❅✹✡✸✡❭✡⑩ Ai ✘✱✹, ✐ Xn j=1 xij = ai ,i = 1, 2, . . . , m. 1
2 第六章运输问题 同理，运进B的物资总量应等于B影的销量，即 =5-12n 在表6-2中，这两组等式为第i行的未知数1，x2,,xm的和等于这一行右端的 a4:而第j列的未知数x1j,2,,工m的和等于这一列底下的b。 从表6-1和表6-2中还可以看出，总的运费等于 因此我们可以把上面的问题归纳为如下线性规划问题： min (6.1) 满足 (6.2) (6.3) x≥0，（∑a-∑） 6.4) i=1 j=1 这就是运输问题的数学模型.除了经常遇到的物资调运问题外，在其它活动中会遇到 类似的问题。由于这类问题最早是从物资运输问题产生出来的，因此把具有(6.1以、(6.2)、 (6.3)和(6.4)形式的线性规划问题都叫做运输问题。 例如，设有m台机床，要加工n种零件.第i台机床可加工出a4种零件（= 1,2,m而第方种零件必须有，个G=1,2m小，且 - =1 c为第i台机床加工种零件时每一件的加工费问这些零件应如何分配给这m台机 床，使总的加工费为最小？ 显然，当设列为第1台机床加工第方种零件的个数时，就转化为一个运输问题. 运输问题显然是一个线性规划问题，当然可以用单纯形法求解，但这个问题具有一种 固定结构，使我们可以找到另外比较简单的解法。本章介绍表上作业法. S6.2初始基本可行解的求法 既然运输问题是一种线性规划问题，所以运输问题的最优解一定可以在基本可行解 中找到。当找到初始基本可行解以后，要判别是否为最优解.不是最优解时就要进行调整
2 ❶✑❷❁❸❺❹✡❻✑❼❁❽ ②✡❾, ✙✡❿ Bj ✘✪✡✫✡❅✹✡✸✡❭✡⑩ Bj ✘ ✵✹, ✐ Xm i=1 xij = bj , j = 1, 2, . . . , n. ✟⑦ 6–2 ✏ , ✜✬➀✬➁❭✬➂✬❴✬➃ i ➄✬✘✬➅✬❀✬✇ xi1, xi2, . . . , xin ✘✬✺✬❭✬⑩✜ ✓✬➄✬➆✬➇✬✘ ai ; ➈✡➃ j ⑤✘✡➅✡❀✡✇ x1j , x2j , . . . , xmj ✘✡✺✡❭✡⑩✜ ✓⑤✡➉✡➊✘ bj ✛ ✭✡⑦ 6–1 ✺⑦ 6–2 ✏❁➋③✡④✡➌⑧, ❅ ✘✡✙✡✽✡❭✡⑩ z = Xm i=1 Xn j=1 cijxij . ➍❥✡➎✡➏③✡④ ✧✡➐✡➑✘ ✍✡✎✡➒✡➓❴✡❯➊ ✠✡☛✡☞✡✌✡✍✡✎: min z = Xm i=1 Xn j=1 cijxij (6.1) ➔✡→ Xn j=1 xij = ai ,i = 1, 2, . . . , m (6.2) Xm i=1 xij = bj , j = 1, 2, . . . , n (6.3) xij ≥ 0,( Xm i=1 ai = Xn j=1 bj ) (6.4) ✜↔➣❢✙↔✚✍↔✎✘↔✇↔↕↔➙✡✗✛➜➛↔➝✡➞↔➟✡➠✴✡✘✪↔✫✡✳✙ ✍↔✎❝, ✟↔➡↔➢↔➤↔➥➦✏➨➧↔➠✴ ✔✡➩✡✘✍✡✎✡✛ ❦❁⑩✜ ✔ ✍✡✎❆✡➫❢✡✭✡✪✡✫✙✡✚✍✡✎✱✡➭⑧✡➯✡✘, ➍❥✧✡➲✒ (6.1)➳ (6.2)➳ (6.3) ✺ (6.4) ➵✡➂✡✘✠✡☛✡☞✡✌✡✍✡✎✡➸✑➺❁➻➽➼✡➾✡➚✡➪✡✛ ➶❯, ❚ ✒ m ➹➴➘➴➷, ✤➴➬➴➮ n ✩➴➱➴✃➴✛ ➃ i ➹➴➘➴➷③ ➬➴➮⑧ ai ✩➴➱➴✃ (i = 1, 2, . . . , m); ➈✡➃ j ✩✡➱✡✃✡❐✡❒✒ bj ✰ (j = 1, 2, . . . , n), ❮ Xm i=1 ai = Xn j=1 bi cij ❴✬➃ i ➹✬➘✬➷➬✬➮ j ✩✬➱✬✃✬❰✶✬✓✃ ✘➬✬➮✽ ✛♦✍✬✜✬Ï✬➱✬✃✸✬❯✬q✬❪✬Ð✬Ñ✜ m ➹✬➘ ➷, t✡❅✘➬✡➮✽✡❴✡❆✡✉? Ò✡Ó, Ô❚ xij ❴✡➃ i ➹✡➘✡➷➬✡➮➃ j ✩✡➱✡✃✘✰✇ ❰ , ➣✡Õ✡Ö❴✡✓✰✙✡✚✍✡✎✡✛ ✙↔✚✍↔✎Ò↔Ó❢ ✓ ✰✠↔☛✡☞↔✌✡✍↔✎, ÔÓ ③↔④ ✾❵↔×➵↔Ø❂↔Ù↔✛ÛÚ✡✜✰✍✡✎↔➲✒↔✓✩ Ü❄✡Ý✡Þ, t✡➎✡➏③✡④✡ß✴✡❜✡❝✑à❁á✡â❵ ✘Ù Ø ✛♦ã✡ä✡å✡æ⑦➐✡ç✡èØ ✛ §6.2 é●ê●ë●ì●í●î●ï●❏●ð●ñ òÓ✙✬✚✍✬✎❢ ✓ ✩✬✠✬☛✬☞✬✌✬✍✬✎, ó④ ✙✬✚✍✬✎✘✬❆✬ôÙ ✓ ❄③✬④ ✟✬õ✬ã③➄ Ù ✏ß✴ ✛ Ôß✴↔ö↔÷õ↔ã③➄ Ù ④✡ø, ✤↔ù❫❢↔ú❴↔❆↔ôÙ↔✛Ûû❢ ❆↔ôÙ↔❰✡➣✡✤❿✡➄✳✡ü
562初始基本可行解的求法 3 这样继续下去，直到找到最优解时为止。下面先来研究运输问题的基本可行解具有的特 性 运输问题有n+m个约束条件，包含n×m个决策变量.在讨论线性规划问题的标 准型时，一般都假设约束方程中没有多余的方程，但在产销平衡的运输问题的约束方程组 中，其系数矩阵的前m行的和减去后n行的和恰好得到一个0向量.因此约束方程中系 数矩阵的行是线性相关的。也就是说约束方程组中存在多余的方程。可以证明，在n+m 约束方程中的任意n+m-1个都是线性无关的，从而运输问题的每一组基应由n+m-1 个基变量组成。 怎样组成一个基x,h,.(s=n+m-1)?这里先引入闭回路的概念，然 后介绍有关定理。 定义凡是能够排列成下列形式的变量集合称为一个闭回路 (6.5) 其中s=n+m-1,i,2,,i。互不相同，，2，，j。互不相同。这些出现在(6.5)中的 变量称为这个闭回路的顶点。 例如，m=3,n=4,则x21x2s,x13,x1434,x31就是一个闭回路.这里1=2，i2= 1,3=3方1=12=33=4。若把闭回路的顶点在表中画出，并且把相邻两个变量（以及 最后一个变量与第一个变量)用直线相连（称这些直线为闭回路的边）。那么上述闭回路就 具有表6-3所示的形状. 表6-3 销地 产地 A 11 12 13T14 T21 22 F24 A3 x31x32x93x34 又如12,132322，工12和工1112,3234,2421d11也是闭回路.把他们画在表上 分别如表6-4和表6-5所示。 表6-4 销地 3 3 产地 A A3 T32 T33 工34
§6.2 ý✡þ✡ÿ✁✁✂✁✄✁☎✝✆✁✞✁✟ 3 ✜✡✠✡☛✡☞➊⑨, ✌✬✴ß✴✬❆✬ôÙ✬❰❴✡✍✛ ➊ ➑✏✎➯✥✬✦✙✬✚✍✬✎✘õ✬ã③➄ Ù✬➲✒✬✘✕ ☛✡✛ ✙✡✚✍✡✎✒ n + m ✰✁✑✁✒✁✓✃ , ✔✁✕ n × m ✰✁✖✁✗✁✘✹ ✛♦✟✁✙✁✚✡✠✡☛✡☞✬✌✡✍✬✎✘✡✛ ✜ ✗❰ , ✓✁✢➸❡❚✑✁✒❈✁✣ ✏✥✤✒✁✦✁✧✡✘✡❈✁✣, Ú✡✟✱✡✵✡❣✡❤✘✡✙✡✚✍✡✎✘✑✁✒❈✁✣➁ ✏ , ➡✁★✇✁✩✁✪✡✘✁✫ m ➄✡✘✡✺✁✬✡⑨ø n ➄✡✘✡✺✁✭✁✮✁✯✡✴✡✓✰ 0 ❧✹ ✛ ➍❥✁✑✁✒❈✁✣ ✏✥★ ✇✰✩✰✪↔✘↔➄❢✠↔☛✰✱✰✲✘ ✛✴✳↔➣❢✰✵, ✑✰✒❈✰✣➁➦✏✷✶↔✟✦✰✧↔✘✡❈✰✣✛ ③✡④✰✸✝✹, ✟ n + m ✑✰✒❈✰✣✏✘✰✺✰✻ n + m − 1 ✰➸❢✠↔☛✰✼✰✲✘, ✭ ➈↔✙↔✚✍↔✎✘↔✶↔✓➁↔õ✸✑❦ n + m − 1 ✰õ✘ ✹ ➁ ⑥ ✛ ✽✠✡➁⑥✓ ✰õ :xi1j1 , xi2j2 , . . . , xisjs (s = n + m − 1)? ✜✁✾✁✎✁✿✁❀❂❁✁❃✁❄ ✘✁❅✁❆, Ó øå✡æ✒✲✡❄❾ ✛ ❇✁❈ ❉❢✡s✁❊✁❋⑤✡⑥✡➊✡⑤➵✡➂✡✘✘ ✹✁●✁❍✁■✡❴✡✓✰ ❁✁❃✁❄: xi1j1 , xi1j2 , xi2j2 , xi2j3 , . . . , xisjs , xisj1 (6.5) ➡✑✏ s = n + m − 1,i1,i2, . . . ,is ❏ û✁✱②, j1, j2, . . . , js ❏ û✁✱② ✛♦✜✡Ï⑧✁❑✟ (6.5) ✏✘ ✘ ✹✁■✡❴✜✰✁▲✝▼✥◆✘P❖✁◗✛ ➶❯, m = 3,n = 4, ❘ x21,x23,x13,x14,x34,x31 ➣❢ ✓ ✰✏▲❙▼❚◆✛ ✜✏✾ i1 = 2,i2 = 1,i3 = 3;j1 = 1,j2 = 3,j3 = 4✛ ✮✧▲✝▼✥◆✘✁❯✁❱✟⑦ ✏✥❲⑧, ❳✡❮✧✁✱✁❨✡➀✰✁✘✹ (④ ✼ ❆ø✓ ✰✰✘✹✰❩↔➃↔✓✰✰✘✹) ✾✰✌✠✰✱① (■ ✜↔Ï✌ ✠ ❴ ▲❬▼✷◆✘✰❭)✛❫❪✁❴↔➐✁❵▲✝▼✷◆➣ ➲ ✒⑦ 6–3 ó✁❛✡✘✡➵✁❜✛ ⑦ 6–3 ✵✡✲ B1 B2 B3 B4 ✱✡✲ A1 x11 x12 x13 x14 A2 x21 x22 x23 x24 A3 x31 x32 x33 x34 ❞ ❯ x12,x13,x23,x22,x12 ✺ x11,x12,x32,x34, x24,x21,x11 ✳❢✁▲✝▼✥◆✛✢✧✁❝➏❲✡✟⑦➐ ❪✡❫✡❯⑦ 6–4 ✺⑦ 6–5 ó✁❛✛ ⑦ 6–4 ✵✡✲ B1 B2 B3 B4 ✱✡✲ A1 x11 x12 x13 x14 A2 x21 x22 x23 x24 A3 x31 x32 x33 x34
第六章运输问题 表6-5 销地 B B 产地 A 11 12 13 x14 42 x21 x22 T23 工24 A 1 32 34 (应) 有了上单这平，下面介绍用的种运输问题的初始基本可行解的求法. 即此向价角该 下面何才例题介绍这个方法.运价表和平衡表问棉在一个表中，单位运价y能在使 在右上小 解数表66，求初始基本可行解 表6-6 销地 B B B B 产量 产地 12 13 x14 0 > 21 22 T23 24 A2 1 3 4 2 5 31 工32 工33 r31 A3 8 4 7 销量 3 4 6 一列连数凰可和都为21，满足平衡件，从使上小的 x11=max{3,9}=3. 电一3可以看出.和如必须为0即经知去了3个术知餐季图在0的 于空表格，把求出蛛夫知数的表填在表上，我们约定，在3的外面 葡方打上义，然后骨定知的素御表中未求出动表的使上小的的曲，取有 12=mim9-3,8}=6. 在的位置上填上6棉食圆，这时应为0.故打上×.用同线的方法可以干 出：z22=2,T32=0,23=324=0,33=1,x34=6(见表6-7)
4 ❶✑❷❁❸❺❹✡❻✑❼❁❽ ⑦ 6–5 ✵✡✲ B1 B2 B3 B4 ✱✡✲ A1 x11 x12 x13 x14 A2 x21 x22 x23 x24 A3 x31 x32 x33 x34 ❇✁❞ 1. n + m − 1 ✰✁✘✹ xi1j1 , xi2j2 , . . . , xisjs (s = n + m − 1) Þ⑥õ✡ã③➄ Ù ✘✁❡ ✤✓✃❢➢✡û✕ ▲✝▼✥◆✛ (✸✁❢) ✒ ➝✡➐✁❵✁✜✁❣, ➊ ➑✡å✡æ✡➟✾✡✘✁❤✩✙✡✚✍✡✎✘✡ö✡÷õ✡ã③➄ Ù ✘❂Ø ✛ ✐❦❥♠❧❦♥❦♦❦♣ ➊ ➑✁q✁r➶✎✡å✡æ✡✜✰❈✡Ø✛ ✙✡♥⑦ ✺❣✡❤✡⑦❍✁❳✟✓ ✰✡⑦ ✏ , ❵✡❛✙✡♥ cij s✟✁t ➊✁✉, xij s✟➆ ➐ ✉ ✛ ❙ 1. ✈✁✇⑦ 6–6, ❂ ö✡÷õ✡ã③➄ Ù✡✛ ⑦ 6–6 ✵✡✲ B1 B2 B3 B4 ✱✹ ✱✡✲ x11 x12 x13 x14 A1 2 9 10 7 9 x21 x22 x23 x24 A2 1 3 4 2 5 x31 x32 x33 x34 A3 8 4 2 5 7 ✵✹ 3 8 4 6 ✈ : ❆➊✓✡➄✁①✡✇✁②✁③✡✺✁❩✡❆✡➆✡✓⑤①✡✇✁②✁③✡✺➸ ❴ 21, ➔✡→✡❣✡❤✁✓✃✡✛ ✭t✡➐✉✘ ✘ ✹ x11 ④÷, ✎Ñ x11 ④✁⑤✡③s✁⑥✘✁⑦, ❴❥✁⑧ x11 = max{3, 9} = 3. ❦ x11 = 3 ③↔④↔➌⑧, x21 ✺ x31 ❐↔❒❴ 0, ✐➦✿➞ ❀✰⑨➝ 3 ✰ ➅↔❀↔✹↔✘✰⑦✛✴q↔➟, ✎✰❲ ✮✬✓✡⑩✡❶⑦✡❷, ✧✬❂⑧✬✘✬➅✬❀✬✇✬✘✡⑦✡❸✟⑦➐✬✛ ➎✬➏✡✑❄ , ✟ 3 ✘✬❝➑✡❲✓ ✰✡❹, ✟ 0 ✘ ✲❈✁❺➐ “×”✛ Ó ø✁❻✖❄ x12 ✘✁⑦ (✐⑦ ✏➅ ❂ ⑧ xij ⑦✡✘t✡➐✉✘✘ ✹)✛❽❼✒: x12 = min{9 − 3, 8} = 6. ✟ x12 ✘❛✡❾➐❸ ➐ 6 ❳ ❲❹ , x13,x14 ✜✬❰✸✬❴ 0, ❿✡❺➐ “×”✛ ✾✬②✠ ✘✬❈✬Ø, ③✬④ ✯ ⑧:x22 = 2,x32 = 0,x23 = 3, x24 = 0,x33 = 1, x34 = 6(➀⑦ 6–7)✛
$6.2初始基本可行解的求法 表6-7 销地 B2 产量 产地 (3) (6) Al 2 9 10 9 ② (3) A2 1 3 4 2 (1) (6) 销量 3 8 4 6 不难看出，放在表上的数(“×”代表0)是一个可行解此外画图的数共有n+m-1 各，并且可以证明，用这种方法求得的解是一个基本可行解.而且n+m一1个画图的地 方正好是基变量 例2.根据表6-8，求初始基本可行解 表6-8 销地 B B Bs B 产量 产地 工12 工13 14 A Q 1 21 2 23 T21 A2 2 6 5 3 5 T31 32 38 A3 1 8 销量 2 1 7 6 解首先，应该取x11=2,21=0,x31=0.然后，令x12=mim{3-2,1}=1.这时 显然x13.工14,2及r2都必须为0.但我们只在一个方向上打“×”（在行上，或在列上）， 而不能同时在行与列上都打“×”.例如，我们在行上“×”，然后决定2的值，它应等于 mi血0,5}=0，此时在x2处写上0，并画上圈.而在x32处打上“×”，继续做下去，可以得 到x23=5,24=0,z33=2,x34=6(见表6-9)
§6.2 ý✡þ✡ÿ✁✁✂✁✄✁☎✝✆✁✞✁✟ 5 ⑦ 6-7 ✵✡✲ B1 B2 B3 B4 ✱✹ ✱✡✲ (3) (6) × × A1 2 9 10 7 9 × (2) (3) × A2 1 3 4 2 5 × × (1) (6) A3 8 4 2 5 7 ✵✹ 3 8 4 6 û✁➁➌⑧, ➂ ✟⑦➐ ✘✡✇ (“×” ➃⑦ 0) ❢ ✓ ✰ ③➄ Ù . ❥❝, ❲❹ ✘✡✇✁➄✡✒ n + m − 1 ①✁➅❽❳✡❮③✡④✁✸✝✹, ✾✜✡✩❈✡Ø❂ ✯✡✘Ù❢ ✓ ✰õ✬ã③➄ Ù , ➈✡❮ n + m − 1 ✰❲❹ ✘✲ ❈✁➆✁✮❢õ✘ ✹ ✛ ❙ 2. ✈✁✇⑦ 6–8, ❂ ö✡÷õ✡ã③➄ Ù✡✛ ⑦ 6–8 ✵✡✲ B1 B2 B3 B4 ✱✹ ✱✡✲ x11 x12 x13 x14 A1 7 8 1 4 3 x21 x22 x23 x24 A2 2 6 5 3 5 x31 x32 x33 x34 A3 1 4 2 7 8 ✵✹ 2 1 7 6 ✈ : ➇ ✎ , ✸✬♣❼ x11 = 2,x21 = 0,x31 = 0✛ Ó ø, ⑧ x12 = min{3 − 2, 1} = 1✛♦✜✬❰, Ò✬Ó x13,x14,x22 ✼ x32 ➸✬❐✬❒❴ 0✛ Ú➎✬➏✡➈✟✓ ✰❈ ❧➐❺ “×”(✟➄ ➐ , ➉ ✟ ⑤➐ ), ➈ ûs ②❰✬✟➄✡❩⑤➐✬➸❺ “×”✛ ➶❯, ➎✬➏✟➄ ➐ “×”, Ó ø✖❄ x22 ✘✡⑦, ➢✸✬❭✬⑩ min{0, 5} = 0, ❥❰✡✟ x22 ➊✁s➐ 0, ❳ ❲✡➐❹✛ ➈ ✟ x32 ➊❺ ➐ “×”, ☛✁☞✡➻➊⑨, ③✡④ ✯ ✴ x23 = 5,x24 = 0,x33 = 2,x34 = 6(➀⑦ 6–9)✛
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 ó✁❛✛
56.3求检验数的方法 表6-14 销地 B2 产量 产地 (3) (5 (1) Al 2 9 10 9 t 42 1 3 2 5 3) (4) A 5 销 3 8 4 6 在表6-14中，初始基本可行解对应的目标函数值为 z=2×3+9×5+4×3+2×4+7×1+2×5=88. 可见用差值法求出的结果比用上述两种方法好些， 以上介绍了在表格上直接找初始基本可行解的儿种方法，并且可以证明如下定理。 定理6.21用西北角法、最小元素法和差值法得到的的值是一个基本可行解，而画图 的地方正好是基变量.证略) 在第二章中曾说过，有些线性规划问题存在最优解，而有些线性规划向题没有最优解， 即可行解可以使目标函数没有限界.在运输问题中有如下定理 定理6.2.2任何运输问题部有最优解 证明：由定理2可知，任何运输问题都有基本可行解.又因为，都是非负的，即可行 解必 永远取非负值，所以目标函数值有下界.这就证明了任何运输问题必有最优解. 56.3求检验数的方法 和用单纯形法解线性规划问题一样，在求出初始基本可行解后，就应检查这个基本可 行解是不是最优解.在求目标函数为极小化的线性规划问题中，若所有检验数都 非负，表示所检验的基本可行解是最优解.若有负检验数，就需要迭代.运输问题是线性 规划问题的特殊情况，有其独特的求检验数的方法。但在求出最优解后，上述判别基本可 行解是否为最优解的准则也是适用的。下面介绍两种求运输问题的检验数的方法。 一、闭回路法 前面的定理已介绍了闭回路的概念，以及求初始基本可行解的方法，在用闭回路求检 险数时，还需用到下述定理
§6.3 ✞✥Ñ✁Ò✁Ó✝✆✥Ô✝✟ 9 ⑦ 6–14 ✵✡✲ B1 B2 B3 B4 ✱✹ ✱✡✲ (3) (5) × (1) A1 2 9 10 7 9 × × × (5) A2 1 3 4 2 5 × (3) (4) × A3 8 4 2 5 7 ✵✹ 3 8 4 6 ✟⑦ 6–14 ✏ , ö✡÷õ✡ã③➄ Ù ➣✡✸✡✘➌➋➦✛✁➧✡✇✁⑦✡❴ z = 2 × 3 + 9 × 5 + 4 × 3 + 2 × 4 + 7 × 1 + 2 × 5 = 88. ③➀✡✾➬⑦✡Ø❂ ⑧✡✘Ý➹✑à❁✾➐✁❵✡➀✡✩❈✡Ø✁✮Ï✡✛ ④ ➐✡å✡æ✡➝✡✟⑦✁❷➐✌✁Õßö✡÷õ✡ã③➄ Ù ✘✁❤✩❈✡Ø, ❳✡❮③✡④✁✸✝✹❯➊ ❄ ❾ ✛ ❇✁❞ 6.2.1 Ö❬×✷Ø❬Ù✷Ú↔➳✴Û✰Ü✰Ý✰Þ✁Ú✁ß✰à✁á✁Ú✰â✁ã✁ä xij ä✰á✰å✰æ✰ç✰è✰é✰ê✰ë✰ì, í✰î❬ï ä✁ð✁ñ✁ò✁ó✁å✁è✁ô✁õ✛ (ö✁÷) ✟ ➃✰øä➦✏✰ù✵r , ✒ Ï↔✠↔☛↔☞↔✌↔✍↔✎✰✶↔✟❆↔ôÙ , ➈↔✒Ï↔✠↔☛↔☞↔✌↔✍↔✎✰✤✒↔❆↔ôÙ , ✐③➄ Ù ③✡④ t ➋➦✛✁➧✡✇✤ ✒✁ú✁û✛♦✟✙✡✚✍✡✎✑✏✒✡❯➊ ❄ ❾ ✛ ❇✁❞ 6.2.2 ü✁ý✁þ✁ÿ✁✄✂✆☎✆✝✁Û✆✞✁ì✛ ✟✆✠: ❦ ❄ ❾ 2 ③❀, ✺✡q✡✙✡✚✍✡✎✡➸✒õ✡ã③➄ Ù✡✛ ❞➍❴ cij ➸❢✆✡✆☛✘, ✐③➄ Ù✡❐t z = Xm i=1 Xn j=1 cijxij ☞✆✌✁❼✡✆☛⑦, ó④ ➋➦✛✁➧✡✇✁⑦✡✒➊û ✛♦✜✡➣✸✝✹➝✺✡q✡✙✡✚✍✡✎✡❐✒✡❆✡ôÙ✡✛ §6.3 ð✎✍✎✏✎✑●❏✎✒●ñ ✺✡✾❵✡×➵✡ØÙ✡✠✡☛✡☞✡✌✡✍✡✎✓ ✠ , ✟✡❂⑧✡ö✡÷õ✡ã③➄ Ù ø, ➣ ✸✆✓✆✔✜✰õ✡ã③ ➄ Ù❢û❢ ❆✡ôÙ✡✛♦✟✡❂ ➋ ✛✁➧✬✇✡❴✖✕✡✉Ö ✘✠✬☛✡☞✬✌✡✍✬✎ ✏ , ✮ ó✡✒✆✓✆✗✡✇ cj − zj ➸ ✡✖☛, ⑦ ❛✬ó✖✓✖✗✬✘õ✬ã③➄ Ù❢ ❆✬ôÙ✬✛ ✮ ✒ ☛✓✖✗✬✇, ➣✡➚✬✤➫✡➃✛ ✙✬✚✍✬✎❢✠✬☛ ☞✡✌✡✍✡✎✘✡✕✡✖✁➽✁➾, ✒➡✆✘✆✙✆✚✆✛✓✆✗✆✜✚✆✢✆✣✆✤✦✥✆✧✆✛✖★✆✩✖✪✆✫✆✬, ✭✆✮✆✯✆✰✆✱✆✲✆✳ ✴✆✫✆✵✆✶✆✷✆✩✆✪✆✫✆✚✆✸✆✹✆✺✆✵✆✻✆✼✆✚✆✤✦✽✆✾✆✿✆❀✆❁✆❂✆✛✆❃✆❄✆❅✆❆✆✚✆❇✆❈✜ ✚✆✢✆✣✆✤ ❉❋❊✎●■❍❋❏❋❑ ▲✾▼✚▼◆▼❖◗P❘✿▼❀▼❙▼❚◗❯✄❱▼✚✆❲▼❳, ❨▼❩✛▼❬▼❭✱▼✲▼✳✴▼✫▼✚▼✢✆✣▼✤❪✧▼✼✆❚◗❯✄❱▼✛✆❇ ❈✜✆❫, ❴✆❵✼✆❛✆✽✮ ◆✆❖✆✤
10 第六理运输几题 定理4.设窃量工h ,x,(s=n+m-1)说运输问题表格中的过组基y说 过个非基变量， 在恋量组 ,E11,E22,·.…,工 中，存在唯过的团回路没证略)没 下面介绍 定验数的闭回路法没毁列说过个非基变量，按定理4，在表中可以找示唯 袖黄风用路信为第过个顶点草绔花有将路的所有取虹对定的 他们的代数和即为所对应的定验数 例4.仍以例1为例没如果已利用最小元对法标出的初始可行解如表610，标诸非基 变量（空格）的定验数没 解x11对应的闭回路为1114,24，x21没11空格对应的定验数为： 11=c11-14+c24-c21=2-7+2-1=- 23空格对应的定验数为 23=c23-c24+c14-c12+c32-c33-=4-2+7-9+4-2=2 其它非基变量对应的定验数用同样的方法标出没标出的定验数记入另过张表中，见 表6-15没方格中右上函画圈的数迭为基变量，不画圈的数迭为定验数没 表6-15 销地 B B B B 产量 产地 -4 3 (4) 10 (3) -1 (2) A2 1 3 4 2 5 7 (④) 3 A3 8 4 2 5 销量 3 4 6 从表6-15可见表中存在代的定验整故这过基本可行解不说最优解没 利用闭间路法定数可做如下经解之没例如在对应的空格需把调套直类果 变过下，由产费4生产的物差调时个单位给B没为了保模平衡，就要在：需 过个 单位24需 过个单位需 过个单位，即要找婆：这非基变址条果夏 基客基点组北的路墅景调过个爨螺数要验1.数督位，得 7r4雷1 2E21需1 2原本数检 4没可见调运方案的这过 明一个 建窠格调方鬟弹季 变方不正1 ,即给定的基本可行解已说最优解没
10 ❜✁❝✄❞❢❡✆❣✁❤✄✐ ❥✆❦ 4. ❧✆♠✆♥ xi1j1 ,xi2j2 ,. . ., xisjs (s = n + m − 1) ✵✆❃✆❄✆❅✆❆✆♦✆♣✁q✄✚✆r✆s✱, y ✵ r✆t✆✉✱✆♠✆♥, ✹✆✧♠✆♥s y, xi1j1 , xi2j2 , . . . , xisjs q , ✈ ✧✆✇✆r✆✚✆❚✁❯✄❱✆✤ (①✆②)✤ ✽▼✾▼✿▼❀▼✛▼❇▼❈✜ ✚▼❚◗❯❘❱✆✣✆✤ ❧ xij ✵▼r▼t▼✉✱▼♠▼♥, ③ ◆▼❖ 4, ✧▼♦◗q✳▼❨▼④❛▼✇ r✖✚✖❚⑤❯⑥❱✖✤ ❨ xij ⑦ ✷✖⑧✖r✖t✖⑨✖⑩, ❶✖❷r✖t✖✢⑤❸⑥❹✖❚⑤❯⑥❱✖✚✖❺✖❻✖❼✜ ⑨✖⑩✖❽✖❾✖✚ cij ❿✆➀✷✆➁, ❺✆❻✆➂✜ ⑨✆⑩✆❽✆❾✆✚ cij ❿✆➀✷✆➃, ✛✆➄✆➅✆✚✆➆✜✆➇✆➈✷ xij ❺✆❽✆❾✆✚✆❇✆❈✜, ➉✆➊✆➋❾✆✚✆♣✆➌✁➍✄✤ ➎ 4. ➏✆❨✆➐ 1 ✷ ➐ ✤✦➑✆➒✁P✄➓✆✼✆✩✆➔✆→✆➣✆✣✆✛✆★✆✚✆❬✆❭✳ ✴✆✫✆➑✆♦ 6-10, ✛✆↔✆✉✱ ♠✆♥ (↕♣ ) ✚✆❇✆❈✜ ✤ ➙ :x11 ❽✆❾✆✚✆❚✁❯✄❱✆✷ x11,x14,x24,x21 ✤ x11 ↕♣✆❽✆❾✆✚✆❇✆❈✜ ✷ : λ11 = c11 − c14 + c24 − c21 = 2 − 7 + 2 − 1 = −4. x23 ↕♣✆❽✆❾✆✚✆❇✆❈✜ ✷ : λ23 = c23 − c24 + c14 − c12 + c32 − c33 = 4 − 2 + 7 − 9 + 4 − 2 = 2. ➛▼➜✉✱▼♠▼♥❽▼❾▼✚▼❇▼❈✜ ✼✆➝✆➞▼✚✆✢▼✣✆✛▼★✆✤➠➟✆✛✆★▼✚✆❇▼❈✜✆➡➊✆➢r✆➤▼♦✁q, ➥ ♦ 6–15✤✦✢✆♣✁q✄➦✭✆➧✆➨✆➩✚✜✆➫✷✱✆♠✆♥, ➭✆➨✆➩✚✜✆➫✷✆❇✆❈✜ ✤ ♦ 6–15 ➯✆➲ B1 B2 B3 B4 ➳♥ ➳ ➲ −4 (5) 3 (4) A1 2 9 10 7 9 (3) −1 2 (2) A2 1 3 4 2 5 7 (3) (4) 3 A3 8 4 2 5 7 ➯♥ 3 8 4 6 ➵♦ 6–15 ✳✆➥, ♦✁q✈ ✧✆➃✆✚✆❇✆❈✜, ➸✆➺r ✱✆✲✆✳✴✆✫➭✵✆✩✆✪✆✫✆✤ ➓✖✼✖❚⑤❯⑥❱✖✣✖✛✖❇✖❈✜✖✳✖➻➑✖✽✖➼✖➽✖✫✖➾✖✤ ➐➑✖✧ x11 ❽✖❾✖✚↕♣✖➚✖➟✖➪✖❃✖✢✖➶✖➹ ♠ r✆✽, ➘ ➳ ➲ A1 ➴✆➳✚✆➷✆➬✆➪✆r✆t✆➮✆➱✆✃ B1 ✤✦✷✆❙✆❐✆❒✆❮✆❰, Ï✆Ð✧ x14 ➚✆Ñ✆Ò✆r✆t ➮✆➱,x24 ➚✆Ó✆Ô✆r✆t✆➮✆➱,x21 ➚✆Ñ✆Ò✆r✆t✆➮✆➱, ➈✆Ð✆④r✆Õ ➘ x11 ➺ r✆✉✱✆♠✆♥✆❨✆❩✆Ö✆× ✱✆♠✆♥⑩✆s✆Ø✆✚✆❚✁❯✄❱✆✤✦Ù➥, ➪✆Ú✆r✆t✆➮✆➱✆✬ x11 ➚✆ÛÝÜßÞ✆à✜ Ó✆Ô 2,x14 ➚✆ÛÝÜßÞ✆à ✜ Ñ✆Ò 7,x24 ➚✆ÛÝÜßÞ✆à✜ Ó✆Ô 2,x21 ➚✆ÛÝÜßÞ✆à✜ Ñ✆Ò 1, Ó✆Ñ➋✆á, â ✚✆ÛÝÜßÞ✆à✜ Ñ Ò 4✤ ✳✆➥➪✆❃✆✢✆➶✆✚➺ r✆➹♠ ✵✆❻✆➓✆✚✆✤✦ã✆ä✆➑✆➒✖å✆r↕♣✆✚✖❇✆❈✜ ✷✆➁, ✹✆æ✁ç✄✧➺ r ↕♣✆➪✆Ú✆✢✆➶✆✵➭✆✳➀✚✆✤è➑✆➒✆✛✆★✆✚✆❇✆❈✜✆é✆ê✆ë✆ì✆í✆î✆ì 0, ♦✁ç✄❽✆➪✆❃✆✢✆➶✆✚✆ï ð➹ ♠✆ñ✆➭✆òÛÝÜßÞ✆à✜ Ñ✆Ò, ➈✃✆◆✆✚✱✆✲✆✳✴✆✫✁P✄✵✆✩✆✪✆✫✆✤