圖書銷售點選址問題的多種解法

孫 峰

（樂山師范學(xué)院 數(shù)學(xué)與信息科學(xué)學(xué)院，四川 樂山 614000）

圖書銷售點選址問題的多種解法

孫 峰

（樂山師范學(xué)院 數(shù)學(xué)與信息科學(xué)學(xué)院，四川 樂山 614000）

文章對具體的數(shù)學(xué)建模問題—圖書銷售代理點的選址問題作了詳細(xì)討論。借助圖論知識，從選邊和選點的角度出發(fā)，給出了該問題的多種解法。此外，對該選址問題作了推廣，并給出了相應(yīng)的解法。

數(shù)學(xué)建模；選址問題；多種解法；圖論

數(shù)學(xué)是各門自然科學(xué)、工程科學(xué)乃至社會科學(xué)的基礎(chǔ)，在人類歷史發(fā)展和社會生活中發(fā)揮著不可替代的作用，也是學(xué)習(xí)和研究現(xiàn)代科學(xué)技術(shù)必不可少的基本工具。數(shù)學(xué)的應(yīng)用領(lǐng)域十分廣泛，數(shù)學(xué)的重要性得到大家的廣泛認(rèn)同。然而，作為一門基礎(chǔ)的自然學(xué)科和一種精確的科學(xué)語言，數(shù)學(xué)又是以極為抽象的形式出現(xiàn)的。如果人為地割斷數(shù)學(xué)與現(xiàn)實世界的密切聯(lián)系，這種抽象的形式就會掩蓋數(shù)學(xué)的豐富內(nèi)涵，并對數(shù)學(xué)的實際應(yīng)用造成巨大障礙。數(shù)學(xué)建模可以說是解決這個問題的一把鑰匙，它在實際問題與數(shù)學(xué)之間架設(shè)了一座橋梁，為實際問題的解決提供了強有力的工具[1]。數(shù)學(xué)建模是一種運用數(shù)學(xué)的語言和方法，通過抽象、簡化建立起的能近似刻畫并“解決”實際問題的一種強有力的數(shù)學(xué)手段。對于建模問題而言，不同的假設(shè)建立不同的模型，不同的分析角度往往會得到不同的解決辦法。從不同的角度分析看待問題，不僅能加深對問題的理解，而且有助于拓寬知識面、提高創(chuàng)新能力。圖書銷售代理點的選址問題是經(jīng)典數(shù)學(xué)建模教材中的一個習(xí)題[2]，本文就這一問題，從不同角度出發(fā)，分析解決該問題。

1 圖書銷售代理點選址問題

一家出版社準(zhǔn)備在某市建立兩個銷售點，向7個區(qū)的大學(xué)生售書，每個區(qū)的大學(xué)生數(shù)量（單位：千人）已經(jīng)表示在圖1上。每個銷售代理點只能向本區(qū)和一個相鄰區(qū)的大學(xué)生售書，這兩個代理點應(yīng)該建在何處，才能使所能供應(yīng)的大學(xué)生的數(shù)量最大？

圖1 各區(qū)情況

2 圖書銷售代理點選址問題的分析與假設(shè)

該問題要求我們選擇圖書銷售區(qū)域使得所能供應(yīng)的學(xué)生數(shù)達(dá)到最大。這是一個典型的數(shù)學(xué)規(guī)劃問題，建立數(shù)學(xué)規(guī)劃模型的關(guān)鍵在于理清決策、目標(biāo)和約束。該問題的決策是圖書銷售區(qū)的選擇，目標(biāo)是使得所能供應(yīng)的學(xué)生數(shù)最大，也即是圖書銷售區(qū)的學(xué)生數(shù)量總和最大，約束是所選擇的銷售代理點只能向本區(qū)和一個相鄰區(qū)的大學(xué)生售書。

對于區(qū)域的相鄰關(guān)系，我們可以借助圖論的知識，將區(qū)與區(qū)之間的相鄰關(guān)系用圖表示（見圖2，圖論有關(guān)知識可參見文獻(xiàn)[3]），其中圖2中的7個點分別代表7個區(qū)，點與點之間存在一條邊當(dāng)且僅當(dāng)這兩點所代表的區(qū)相鄰。

對于這一問題，我們可以將決策視為選擇2個代理點并確定各代理點相應(yīng)的售書區(qū)，即從圖2中的7個頂點選取2個，然后再選擇與所選頂點有邊相連的另外2個頂點；也可以將決策視為選擇4個銷售區(qū)，即從圖2中的7個頂點選取4個。當(dāng)決策變量選定后，再根據(jù)決策變量給出相應(yīng)的目標(biāo)函數(shù)和約束即可得到該問題的數(shù)學(xué)規(guī)劃模型。

通過對該問題的分析，我們提出以下假設(shè)：

1）每個銷售代理點只能向本區(qū)和一個相鄰區(qū)的大學(xué)生售書；

2）售書所面向的人群僅考慮為大學(xué)生，且售書的多少與售書區(qū)的大學(xué)生數(shù)成正比；

3）不考慮各區(qū)之間的學(xué)生流動；

4）為使供應(yīng)人數(shù)最大，不存在重復(fù)供應(yīng)的情況，即每一個區(qū)至多只有一個代理點供應(yīng)。

圖2 各區(qū)相鄰情況關(guān)系

3 圖書銷售代理點選址問題的模型建立及求解

基于上一節(jié)的分析，我們可以從不同角度入手：選擇2個代理點并確定各代理點相應(yīng)的售書區(qū)，即從圖2中的7個頂點選取2個，然后再確定與所選頂點有邊相連的另外2個頂點（將該方法簡記為“7選2”），這也相當(dāng)于從圖2的11條邊中選取2條（將該方法簡記為“11選2”）；或者選擇4個銷售區(qū)（將該方法簡記為“7選4”）。下面我們針對不同的角度，給出該問題相應(yīng)的解法。

3.1 解法一：“11選 2”

當(dāng)一個銷售代理點確定在某個區(qū)時，我們還需要確定向哪一相鄰區(qū)域售書，這相當(dāng)于選中相鄰的兩個區(qū)，也即是圖2中的一條邊，因此該選址問題等價于從圖2的11條邊中選取2條邊使得供應(yīng)的人數(shù)達(dá)到最大。選取的2條邊互不共用頂點，若共用頂點的話，圖書實際供應(yīng)的區(qū)域僅有3個，這無疑不能滿足供應(yīng)人數(shù)最大。

記ri為第i區(qū)大學(xué)生人數(shù)；用0-1變量xij（i＜j且vi，vj相鄰）表示是否選中連接頂點vi與vj的邊，若選中連接頂點vi與vj的邊，即i，j兩區(qū)有一個銷售代理點供應(yīng)圖書，則 xij=1，否則xij=0。

于是我們可得到該選址問題的0-1規(guī)劃模型：

具體模型如下：

模型求解結(jié)果為x25=x47=1，即第2，5區(qū)及第4，7區(qū)之間有銷售代理點，總供應(yīng)人數(shù)是177千人。

3.2 解法二：“7選2”

從7個區(qū)中選2個建立銷售代理點，并根據(jù)選擇的代理點分別確定相鄰的售書區(qū)。當(dāng)區(qū)1選定時，為使供應(yīng)人數(shù)最多，則向區(qū)3供應(yīng)；區(qū)2選定，則向區(qū)5供應(yīng)；區(qū)3選定，則向區(qū)1供應(yīng)；區(qū)4選定，則向區(qū)7供應(yīng)；區(qū)5選定，則向區(qū)2供應(yīng)；區(qū)6選定，則向區(qū)7供應(yīng)；區(qū)7選定，則向區(qū)4供應(yīng)。記ri為第i區(qū)大學(xué)生人數(shù)，用0-1變量xi=1表示在第i區(qū)建立圖書銷售代理點，否則xi=0。

所能供應(yīng)的學(xué)生人數(shù)為：

區(qū)1選定則向區(qū)3供應(yīng)，反過來，區(qū)3選定則向區(qū)1供應(yīng)，即是說選區(qū)1與選區(qū)3等價，因此區(qū)1與區(qū)3中至多選一個：x1+x3≤1。

選區(qū)2與選區(qū)5等價，因此區(qū)2與區(qū)5中至多選一個：x2+x5≤1。

選區(qū)6則選區(qū)7，選區(qū)7與選區(qū)4等價，因此區(qū)4、區(qū)6、區(qū)7中最多選一個：x4+x6+x7≤1。

從而我們得到下述模型：

模型求解結(jié)果為 x2＝x4＝1，即第2，5區(qū)及第4，7區(qū)之間有銷售代理點，總供應(yīng)人數(shù)177千人。

3.3 解法三：“7選4”細(xì)分法

從7個區(qū)中選2個建立銷售代理點，并分別向相鄰的某個區(qū)供應(yīng)。這相當(dāng)于從7個區(qū)中選取4個，不過所選取的4個區(qū)能分為兩組，兩個區(qū)一組且同一組中的兩個區(qū)相鄰。對于同一組中的兩個區(qū)相鄰的約束條件，我們可以細(xì)分為相鄰兩區(qū)的固定搭配：當(dāng)區(qū)1選定時，為使供應(yīng)人數(shù)最多，則向區(qū)3供應(yīng)；區(qū)2選定，則向區(qū)5供應(yīng)；區(qū)3選定，則向區(qū)1供應(yīng)；區(qū)4選定，則向區(qū)7供應(yīng)；區(qū)5選定，則向區(qū)2供應(yīng)；區(qū)6選定，則向區(qū)7供應(yīng)；區(qū)7選定，則向區(qū)4供應(yīng)。記ri為第i區(qū)大學(xué)生人數(shù)；用0-1變量xi=1表示在第i區(qū)建立圖書銷售代理點，否則xi=0。

同一組中的兩個區(qū)相鄰可細(xì)分為如下情形：

選區(qū) 1 必選區(qū) 3，選區(qū) 3 必選區(qū) 1：x1＝x3。

選區(qū) 2 必選區(qū) 5，選區(qū) 5 必選區(qū) 2：x2＝x5。

選區(qū) 4 必選區(qū) 7，選區(qū) 7 必選區(qū) 4：x4＝x7。

選區(qū) 6 必選區(qū) 7：x7≥x6。

綜上，我們得到如下模型：

模型求解結(jié)果為 x2=x4=x5=x7=1，即第2，5區(qū)及第4，7區(qū)之間有銷售代理點，總供應(yīng)人數(shù)177千人。

3.4 解法四：“7選4”矩陣法

從7個區(qū)中選取4個，使得所選取的4個區(qū)能分為兩組，兩個區(qū)一組且同一組中的兩個區(qū)相鄰，這相當(dāng)于從鄰接矩陣的主對角線的上方選取2個位于不同行不同列的1，這兩個1所在的行和列就是我們要選擇的4個區(qū)。

y 與 x 的關(guān)系：yij≤xi，yij≤xj。

綜上，我們得到下述模型：

模型求解結(jié)果為 y25=y47=1，x2=x4=x5=x7=1，即第2，5區(qū)及第4，7區(qū)之間有銷售代理點，總供應(yīng)人數(shù)177千人。

4 問題推廣

在上一節(jié)，我們考慮了從7個區(qū)選取2個銷售代理點的選址問題，我們將區(qū)之間的相鄰關(guān)系以圖的形式表示，或從選點或從選邊的方面考慮該問題，給出了該問題的不同解法?，F(xiàn)在我們討論更一般的情況：從n個區(qū)選取m（n＞2m）個銷售代理點的選址問題，同樣要求每個銷售代理點只能向本區(qū)和一個相鄰區(qū)售書。

基于上一節(jié)的討論，我們在此給出該推廣問題的幾種解決辦法。首先將各區(qū)的相鄰關(guān)系表示為圖 G=（V，E），其中 V={v1，v2，…，vn}為頂點集表示 n個區(qū)；E為邊的集合，表示各區(qū)的相鄰情況，若區(qū)i與區(qū)j相鄰，則邊（vi，vj）∈E，否則（vi，vj）E。令圖G=（V，E）的鄰接矩陣為M，其中Mij=1當(dāng)且僅當(dāng)（vi，vj）∈E，Mij=0當(dāng)且僅當(dāng)（vi，vj）E。記={1，2，…，n}，ri為區(qū)i大學(xué)生數(shù)，（表示與區(qū) i相鄰的所有區(qū)，表示與區(qū)i相鄰的區(qū)中學(xué)生數(shù)達(dá)到最大的區(qū)，表示的最小元，即與區(qū)i相鄰的區(qū)中學(xué)生數(shù)達(dá)到最大的區(qū)中編號最小的區(qū)。

4.1 基于選邊的解決辦法

設(shè)xij為0-1變量，表示i，j兩區(qū)間是否建立銷售代理點，若在i，j兩區(qū)間建立銷售代理點，則xij=1，否則 xij=0。

于是我們得到供應(yīng)人數(shù)最大化的選址模型：

4.2 基于選點的解決辦法

設(shè)xi為0-1變量，表示是否向i區(qū)售書，如果是，則 xi=1；否則 xi=0。從n個區(qū)選取 m個建立銷售代理點，并向相鄰的某個區(qū)供應(yīng)。這相當(dāng)于從n個區(qū)選取2m個區(qū)售書。若向i區(qū)售書，則必然在N(i)中的某區(qū)售書，更進(jìn)一步，為使供應(yīng)人數(shù)達(dá)到最大，必然向中的某區(qū)售書。當(dāng)然，由的定義可知向i中的任意一區(qū)售書都可以，在這里不妨設(shè)其為。即當(dāng)xi=1時，必然有，因而有。

于是得到供應(yīng)人數(shù)最大化的選址模型：

4.3 基于選邊與選點結(jié)合的解決辦法

邊與點的關(guān)系，即若i，j兩區(qū)存在銷售代理點，則必然選i，j兩區(qū)：。

綜上，相應(yīng)的模型如下：

5 小結(jié)

對于圖書銷售代理點的選址問題，我們將區(qū)之間的相鄰關(guān)系，以圖（7個頂點，11條邊）的形式表示，或從選點或從選邊的方面考慮該問題，給出了該具體問題的4種不同解法，并進(jìn)一步給出了這類問題的通用模型及其求解。

參考文獻(xiàn)：

[1]姜啟源，謝金星.一項成功的高等教育改革實踐：數(shù)學(xué)建模教學(xué)與競賽活動的探索與實踐[J].中國高教研究，2011（12）：79-83.

[2]姜啟源，謝金星，葉俊.數(shù)學(xué)模型[M].4版.北京：高等教育出版社，2011.

[3]DIESTEL R.Graph theory[M].4th ed.Springer，2010.

Multiple Solutions to Location Selection Issue of Book Sales

SUN Fenɡ
（School of Mathematics and Information Science，Leshan Normal University，Leshan Sichuan 614000，China）

The specific mathematical modeling issue which means the location selection issue of book sales has been discussed in details in this paper.Based on graph theories，this paper also gives multiple methods to solve the location selection issue within the viewpoints of choosing edges or vertices.In addition，the location problem has been generalized and the corresponding solution has been given as well.

Mathematical Modeling；Location Selection Problem；Multiple Solutions；Graph Theory

O29

A

1009-8666（2017）08-0038-08

［責(zé)任編輯、校對：方忠］

10.16069/j.cnki.51-1610/g4.2017.08.008

2016-05-25

四川省省級精品資源共享課建設(shè)項目“數(shù)學(xué)建模與數(shù)學(xué)實驗”（2013-123）

孫峰（1985—），男，四川西昌人。樂山師范學(xué)院副教授，博士，研究方向：不確定性的數(shù)學(xué)理論、數(shù)學(xué)建模等。