物流配送 某零售集团有100家加盟连锁店。月初配送中心将5种商品配送给各加盟店，由于 商品数量有限，所以只有部分商店得到了配送商品，获得这5种商品的连锁店数目分别 为80,72,84,88,56。每个加盟店并未指望得到全部5种商品，如果能得到其中任意 3种便已满足。该零售集团总部欲作一估算，本次配送商品，至少有多少家加盟连锁店 得到了满足？以便为物资准备计划的调整提供决策依据。 【分析】乍一看，问题似乎很简单，如果一家连锁店获得某一种商品叫做一个“店 次”，那么总“店次"数为80+72+84+88+56=380.因为一家连锁店获得3种商品(3 个店次)即可满足，所以被满足的加盟连锁店数可达380+3=126.7，即100家连锁店都 能得到满足。但反过来验证一下发现题了：未获5种商品的连锁店数分别是100一80 =20,100-72=28,100-84=16,100-88=12,100-56=44,这些店次之0为20 +28+16+12+44=120,一家连锁店未获3种商品便得不到满足，因此未被满足的加 盟连锁店数可达到120+3=40，满足的连锁店数就只能是100一40=60家。两和相去甚 远的子盾结果说明，这样的计算方 法不可行 这个计算之所以不可行，是因为它太粗糙，有许多约束条件被隐蔽起来了。如果能 将商品配送的详细情祝全部罗列出来，问题就好解决，但是商品配送给不同加盟店的各 种可能情祝很复杂，一一列举难以实现。另一方面，配送中心未提供获得各商品的连锁 店的详细名单，集团总部似 觉得无此 要，只要进厅 简单的美 据处 理即可。 此外 集团总部想知道的是最少比例，并未提出置信度指标，所以本例不是锻率问题，而是要 求出一个确定的最小数值。 【求解】建立本例的数学模型，先应设置一些有不同含义的变量，从上面的粗略计 算中可以看出，得到商品的店家据多数，约束条件难以显现出来，所以考虑未被满足的 连锁店数最多有几家，比较容易得到正确结果。未满足的连锁店中包括没有得到商品、 仅得一种商品、仅得二种商品等三类，而后两类中，又可分别细分为5小类(5种商品 中任取1种的组合数)和10小类(5种商品中任取2种的组合数)
物 流 配 送
设和为末得到商品的连损店数，《=1,2,3,4,5)为仅得到第1种商品而未 得到其他商品的连锁店煎，，(1<)5)为仅得到第！种和第)种商品而未得到另外 三种形品的佳锁店致。我们希望求得这些变置之和的乘大菌，即 max z=而+∑两+∑， 在这三类商店中，未获得第1种商品的连锁酷故为以下11个变量之和： 和十十而十4十+公十24+5十4+5+45 而未获得第1种品的连锁店总数是100一80=20，这20个连锁店。有的已得到满足， 不在上述和数之列，所以应有不薄式 和十+两+4十形+3十两4十5十十两5+6≤20. 对耳他4种商品进行同样的分析，能够得到类似的不薄式.由此矶以得到带有约束条件 的极值间题 5 mao =而+∑+ 而十形+两十+号+知十十猫+4十5十5S20 而+有+而+4+马+丙5十有4十5十4+g+45≤28 而+有+++马巧+阳+4+s+4+g十4彩≤16 而十有+防+丙+两+2+和+5十知+5+5≤12· 而十有+2十内+有+两2+而3十两4+知++S44 而20,4206-1,234,5)，4,200s≤j≤5列
这是一个含有16个变量的线性规划问题，可以用L仆D0软件在计算机上运行求解， 如果根据本例的某些特殊性，将阿题干以简化，侧能够通过线性代数的简便方法求出它 的解。 首先考虑取得最优阳时，围些变量厦该等于零，最容易想到的是=0，若不然 将已获3种（成4种）商品的一家连锁店的任1种《或2种)已获商品取消〔它便走入 未满足商店的行列)，转配给这场个连锁店的某1家（某2家），它仍然处于来满足意 店之中，干是未满足商店的总数就增加了，这与最优解（已得最大值）相子看，可见 一0同杆道理，仅获一种商品的连锁店数也应为零，即，-0(1-1,2,3,4,5)，于 是线性规划简化为10个变堂销回题： 2=两2+再3+西4+互5+3+4+25+两4十95十5 四+24+5十而4十5+x45s20 两)十%十两5 +%+5+5≤28 两2 +马4十5 +不4十2 +x45s16 3.L 两2十和 +而5十 +5 +5 s12 两2+和十丙4 +m十 十利别 S44 5,200s1≤j≤) 其次考使这5个不等式约束藏几个不可能取等号。因为最后一个约束的常故项为 44,而左端的变堂之和较小（最多为4和小，所以这个的束以取等号。为了便于运草， 将这个约束的变量之和记为A,其余变量之和记为B,即今 A=2十两3+再4十+%+两4：B=两影+%+到十玉5" 则As44,将前4个约束不等式相加可得2A+3Bs76,注童到B20,故As8-15B38, 这说明氟5个约束不能取等号
最后考使最大值的取得。一个极端情况是A=38,=0,这时前4个约束都取等 号，日标值为zA十B=38,如果增加B,则A将减少，比如B增加到B=1,由38 一L.5B=36.5知A最多取A=36,目标值至务取x=A十B=37,同样，如果B增加到B =2或B=3,则A聚多取A=35或A=33,目标值至多取x=37成x=36,从这些试其 结果可知。随着B的增加，目标值不增反降，取不到聚大值，因此A=38,B=0是线 性规划的最优解，目标款（未被满足的注锁店敌）的最大值为3荡，即本例的答高是： 本次配送商品，至少有100一38=62家加盟连锁店得到了满足，同时还轮得到使3露家 加盟连领店得不到满足的具体配送方常，该方窝可以从前面4个约束取等号且B所含4 个变置为0的方程组解得，即乐求解线性方程翅 知++两4=20 而3十4 +34=28 两2 十4 + =16 2+石 +如 =12 利用阵变换技术，不难求得方程组的解。下面是对增厂拒阵施行的一系列初等变换。 为了保证主元变量取非负值，在变换时要尽量保持右侧常致列非负，若出现负款，应另 选主元再作变领将耳调整过来。 00011120 100 0 11120 01100128 011 00128 0101016 0-10-1104 0101 00 12 11 0 10012 00011 (0) 20 0 0 011120 2 0 1 -1 1 24 200 -204 0 -11-1 1 0 0 1 1-1 10 4 101 0 12 101 0012
00011120 10011010 0100 -102 0100-102 一（换行） 001-1006 001-1 006 10011010 00011120 从最后的矩车中诗得一组解为=10，=2，，=6，-0，其余变量都服0.因 为内程组的秩是4，小干变登的个数6所以方程组有无穷多解。我们还能邮找出别的 解，比如在最后的柜阵中选宽1行第4列元素为主元再作初等变换，得到 100(①10 10 /10011010 0100-102 0 100-102 001-1 006 10101 016 000111 20 -10000110, /0100-102Y 0101016 一（换行） 10011010 -10000110 读得的解就成了x=2:=16:x=10,u=10其余变量邮取0。这组解表示有2 个连锁店仅得到第1种和第3种百品，有16个连锁店仅得到第1种和第4种商品，有 10个连锁店仅得到第2种和第3种得品，有10个连锁店仅得到冕3种和第4种商品， 这些连锁店均未获得另外三种商品而成为受有得到满足的加盟店，其他2家加盟连锁 店都配给了不少于3种的商品。 进一步可以发现这2家得到满足的加盟店，全馨获得了前4种商品。车中还有 56家获得了第5种商品.这是因为线性规的前4个约束取等号，说明未获得剪1~宽 4种再品的连领店全部集中在没有得到满足的38延领店中，而=0又说明这38家 连锁店中，没有一家获得第5种商品
这种不均匀的送产生了得到满足的加盟店数的最小值.如果进行均匀性调整，厕 可增加这一目标值，比如取消对某些加盟店的第5种商品配送，转配给露家泛有得到 满足的连领店，就能快所有100家连锁店全部得到满足。 【讨论】从以上对求解结果的分析受到启发：为了产生得到满足的加盟店款的服小 值。2该尽置加大对每一个连锁店配送的商品种数，具体的操作思器是，能得到满足的 加盟店，要按获得5种、4种、3种商品的序，分批次配送：不能得到满足的加盟店， 要按数得2种、1种、0种每品的顺序，分批次配送。由此可以得到求解本例的史简便 的方法。 获得5种每品的洼锁店数目分别为80,72,84,88,56，重渐拉序为56(5)，72 (2),80《1),84(3》,88(4),设想将100家连锁店按1一100網号，第一批给前56 号连锁店每配送5种在品，剩涂380一5×56=100店次，如果余下100一56■44家连 损店都不能得到满足，那么仅需要244=88店次，出配送刚余所以亚进行宽二指配 送，第二批给第57一72号连锁店每家配送4种商品，徐100一472一50=36店次， 如果余下100一72=28连锁店都不能得到满足，那么需要2×28=56店次，出现配送 不足，所以乾得到清足的加星店数应在56至72之间，设为：并设不能得到病足的加 里店致为显然x+7-100.根据分配平衡原理，5×56+4x一50十-380.于是我 们只需求解二元一次方程组 x+y=100 x+y=100 5×56+4(x-50+2y=380 2x+y=162 便可得到答需，=62，y=8。具体的配送方案可以从建立方程组的过程中得到：56家 连债店哥家送5种商品、6家连锁店哥家配送4种商品、38家硅领店每家配送2种商 品， 如果上述二元一次方程组设有敌解。邦么就要进行第三批配送，即将方程组调整 为 x+y=100 5×56+4(x-56-月+3女+2y=380 具中k是获得3种稻品的连损店数，依次以k=1,2,…代入求它的整数解即可。 上面给出了本例的四种解法，话用于一般的情况，即当本例的原始故据发生变化时， 这些方法仍然适用