商杨建设招标 某商业集团计划开办8家新商店。为了尽早建成置业果团总部通知了多个建筑公 司。打让它们各自承建一个新的商店，要求每家公司分别哈出对8个新商店建洁费用 的投标值，收到标书后，轻专家组初审。确定了8家建筑公司为经约对蒙，这8家建宽 公司的共4个投标值如来1所示。集团总郎应当对8家建筑公司怎样分配建筑任务， 才能使总的建洁费用最少？ 表1 建洁费用的投标情百万元) 新商 店 B B b B Be Ba Be 建筑公司 A 4 9 8 5 4 5 5 1 A 0 7 10 0 10 14 A 12 8 4 5 13 12 8 Au 9 5 10 2 6 8 11 9 As 3 10 6 3 4 11 5 7 10 5 2 5 8 A 9 2 4 2 10 6 3 A 2 10 3 9 8 6 6 3 【分析】以建造费用最少为目标当然迭择授标值较小的对蒙分配建筑任务。容易 想到的方法是从小到大桃选投标值，在64个投标值中，A对应的投标值1服小， 故首选建筑公司A,承建商店B:接下来选挥投标值2，但因为每家建筑公司只承建一 个新商店。所以后面选择的投标值应和已选的投标值处于表中的不同行、不同列，在这 限制条件下，后面的选辉可能依次是：A、B,对应的投标值2，A、B1对应投标值 2,A、B2对应的投标值3，A、B对度的投标值4，A、B,对应的投标值5，A、B 对应的投标值7，A、B对应的投标值14，总的建洁费用为
商场建设招标
■1+2+2+3+4+5+7+14■38（百万元）， 由于聚后一个不得不选举聚大的投标值14，因此该建造总费用恐怕不是最低的。如果将 所有可能的分配方需全馨罗列出来雨进行选择，那么要面对8一40320个方黨，计算量 太大。看未要采用一个简便的、能包容所有机会的选择方法，这就是拖阵化处理。 首先将表1中的取据列成柜阵 498545511 97106791014 12874513128 9510268119 C-(cij)- 436106 36 3 1157105 2 5 8 924210163 (210398663 然后律立一整套选择较小元素的有放程序。 【求解】直接在矩车阵C中选择小元素与在表1中选择一样会发生困难，这是因为 阵C中较小的故据比校凌乱，不够醒日，而且缺乏可比性，应该通过阵变换对数据 加以简化和清理。 考志矩阵的减数变换将矩阵C的某一行所有元素减去同一个教，比如第1行减 去4，成为 (0,5.41,01,17), 如果把它作为所的投标值，那么对于任何一个分配方需来说。目标值都减少同一个数4 (因为第1行选且只选一个元素)，目标值减去一个常数，自然不响最优解的获得， 即在变巍后的矩阵中选择元素，和在原矩阵中选择元素的放果是一样的。 司杆道理，对炬阵的列作减数变换、对柜阵的行减列作加数变换《加上同一个数】 也不量响最忧解的获得。这种变换为简化矩阵页定了基础. 本例的求解分三个步限进行
第一步为简单化零：将车C中的每行减去最小的元素，再在每列中减去最小元素， 甲随行以下变换： 05410117 @5 3 101②7 31401348 13 (01338 84301984 8 4 2 1 9 74 73804697 7 ⊙4687 C→ → 《1) 10373030 10 2 7 30 2 93583036 9 34 8302 81319052 8 1219@42 08176441 @80⑩76431 耳中的行牙领是第1一第8行依次减去它门的最小元素4,6：4,2,3,2,1,2列 变换"是第3列减去1、第7列减去1，这种变换称为柜阵的减（加）数变换有别于矩 阵的初等变换。矩阵中每行（列）减去一个常藏，并不敌该行（列）故量间的相对大 小关系，从而不会置响工作安挂的优先次序，即最忧解不变，因此可以在后面一个零元 素较多的炬阵中进行安排， 第二步为试作安鞋：在阵中选择0元素.为了珍惜机会，应从0元素较少的行和 列开始安排：选择一个0（加括号），立即划去同行同列的0（任务分配是一对一的，不 能重叠)，划去的0用”⊙“表示，接看再选0，直到所有零元素都被选或被划为止， 如果选到了8个0元素《正好等于矩阵C的阶款)，那么最佳分配方案已经产生，但是 对上面的炬阵依此方法安挂，只选到5个0元素，这说明0元素不够多，还要走行变换 调整。 第三步为调整化零：在保留被选0元素的是础上，通过减数受统产生新的0元素， 但不得出现此0还小的负故，出现负故，用加故变换子以调整：若被选0元素变成正致， 则再用减款变换予以还原。具体做法如下， 】,选定没有(0的行（未选0的行》，准备对这些行减司一个正款文《食的值待定》： 2.若减k的行中有@（划去前0元素），则选定这些@所在的列，准备灭这些列
加正数k(已加过的不再加》，那除负数： 3.若加k的列中有0)（被选的0元素），则侧选定该（所在的行，准备对这些行减正 数k〔已减过的不再藻)，保持被选的元素仍为0： 4,重以上2、3，直至得不出斯的需要减或加正故k的行列为止： 5,在所有被选定的行（需要减故k的行》中，找出最小的正故，确定k等于该最 小正数，并实施上述1一4中选定的减（加）数变换，即对所有选定的行减正数太，对所 有选定的列加正数k。 对于本例的矩阵(1)，氟3、4、7行要减1，这会使第4、6列出现负数，第4 6列应如数1，这一加又将使第26行的被选0元素成为正数1，第2、6行再须减1， 归纳调整化零的操作，第2、34、67行诚1，第2、6列如1，变换过程如下， @53101②7 f@532⊙207 31301338 2②2②(0327 842@1974 垫化 731©963 737 @4 687 62603 6 7 6 1⑩273©2 10283 20 934830 26 823 8201 5 1219⊙4 2 70 1 18 0 3 1 80 764 3 1 8 (08 6 5 31 在调整化零的结果中试作安排，发现只选了7个0，还要划徐酒整，第2、34、6 7行减1，第2、4、5、6列加1，得到
06331307 f0)633 13 7 10100311 10) 1 a 0 31 1 9 2 华 63000952 52503665 作作 ⊙ 0 (0) 5(00 3 6 6 5 11294220 9 2 (0) 7228200 ②0) 60018020 @ @ 180) 2 0 (09097631 90)97 6 1 最后试作安挂选到了8个0，最佳分配方窝已经产生，对应选中的心米安挂承建任务， 具体为 AAAAAA h A 即建筑公司A,承建商店B,建试公司A承建商店B,建筑公司A,承建商店B,建筑 公司A承建商店B,建筑公司A,承建商店B,建筑公司A承建商店B:建筑公司 A加承建商店B,建筑公司A承建酒店B。总的建洁精用为 y=4+7+5+2+3+5+1十3=30《百万元)， 比不用矩骑化方法的相选方需节留8百万元， 【评注】本例中的调整化零，其目的并非在干增加0元素的个数，而是将0元素调 整到更合理的位置上去。只要选到的0元素放目不够，就不断进行清整化零。这和柜阵 初等安换的思路相一敌，银具有方向明确、燥作简便、有序渐进的特点。 本例安挂建筑公司学建商店，显然这一方法可以应用到其她领城，如人事部门安挂 雅员的工作、出版超门安排译员翻译书稿、足球数练组织出场阵客、消防门规划防火 区城等等。这些可题纯称为指间题，柜阵C称为指派同题的系数矩阵。指回题的最 优解也可以用矩车来表示且体是在试作安抖的最后矩阵中，将选中的()元素换成1， 具地元素频减0，便得到指矩阵，指深柜阵中的1表示指深工作，0表示不指深工作
指派矩阵将结果数字化，便于计算机处理。本例在最后的矩阵中选0元素，共有3种不 同的选法（前面只列出一种），它们对应的目标值相同，都是=30（百万元），而指派 矩阵不同，分别是 000000 0 000001 0 000001 0 00 0 00 000 000 0 001 0001 0 100 0 0 0 0 0100000 (10000000 本例的指派问题是目标最小化、每个对象指派一项任务、两者数量相等，这些限制 并不是必要的。指派问题可以推广，比如系数矩阵表示效益的最大化指派问题 一人可 做多事的重复指派问题、含有禁入规定的限制性指派可题等等，都能够采用修改化零、 选零规则的方法加以解决。比如某个最大化指派可题的系数矩阵是 6229 4 19 39 A- 172950412222 354038422733 19302916223 7230 230 50 4120 把矩阵A的所有元素变号（即乘以一1），然后每行都加上矩阵A的最大元素72，得到 矩阵 411043305731 60 533317132 55 B- 4322315050 323 30 45 42 43 70 49 42 42 2231 就化成了最小化指派问题