孫 峰

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

圖書銷售點(diǎn)選址問題的多種解法

孫 峰

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

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

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

數(shù)學(xué)是各門自然科學(xué)、工程科學(xué)乃至社會(huì)科學(xué)的基礎(chǔ)，在人類歷史發(fā)展和社會(huì)生活中發(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)實(shí)世界的密切聯(lián)系，這種抽象的形式就會(huì)掩蓋數(shù)學(xué)的豐富內(nèi)涵，并對(duì)數(shù)學(xué)的實(shí)際應(yīng)用造成巨大障礙。數(shù)學(xué)建模可以說是解決這個(gè)問題的一把鑰匙，它在實(shí)際問題與數(shù)學(xué)之間架設(shè)了一座橋梁，為實(shí)際問題的解決提供了強(qiáng)有力的工具[1]。數(shù)學(xué)建模是一種運(yùn)用數(shù)學(xué)的語言和方法，通過抽象、簡(jiǎn)化建立起的能近似刻畫并“解決”實(shí)際問題的一種強(qiáng)有力的數(shù)學(xué)手段。對(duì)于建模問題而言，不同的假設(shè)建立不同的模型，不同的分析角度往往會(huì)得到不同的解決辦法。從不同的角度分析看待問題，不僅能加深對(duì)問題的理解，而且有助于拓寬知識(shí)面、提高創(chuàng)新能力。圖書銷售代理點(diǎn)的選址問題是經(jīng)典數(shù)學(xué)建模教材中的一個(gè)習(xí)題[2]，本文就這一問題，從不同角度出發(fā)，分析解決該問題。

1 圖書銷售代理點(diǎn)選址問題

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

圖1 各區(qū)情況

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

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

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

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

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

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

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

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

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

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

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

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

3.1 解法一：“11選 2”

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

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

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

具體模型如下：

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

3.2 解法二：“7選2”

從7個(gè)區(qū)中選2個(gè)建立銷售代理點(diǎn)，并根據(jù)選擇的代理點(diǎn)分別確定相鄰的售書區(qū)。當(dāng)區(qū)1選定時(shí)，為使供應(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ū)建立圖書銷售代理點(diǎn)，否則xi=0。

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

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

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

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

從而我們得到下述模型：

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

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

從7個(gè)區(qū)中選2個(gè)建立銷售代理點(diǎn)，并分別向相鄰的某個(gè)區(qū)供應(yīng)。這相當(dāng)于從7個(gè)區(qū)中選取4個(gè)，不過所選取的4個(gè)區(qū)能分為兩組，兩個(gè)區(qū)一組且同一組中的兩個(gè)區(qū)相鄰。對(duì)于同一組中的兩個(gè)區(qū)相鄰的約束條件，我們可以細(xì)分為相鄰兩區(qū)的固定搭配：當(dāng)區(qū)1選定時(shí)，為使供應(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ū)建立圖書銷售代理點(diǎn)，否則xi=0。

同一組中的兩個(gè)區(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ū)之間有銷售代理點(diǎn)，總供應(yīng)人數(shù)177千人。

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

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

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

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

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

4 問題推廣

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

基于上一節(jié)的討論，我們?cè)诖私o出該推廣問題的幾種解決辦法。首先將各區(qū)的相鄰關(guān)系表示為圖 G=（V，E），其中 V={v1，v2，…，vn}為頂點(diǎn)集表示 n個(gè)區(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ū)中編號(hào)最小的區(qū)。

4.1 基于選邊的解決辦法

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

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

4.2 基于選點(diǎn)的解決辦法

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

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

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

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

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

5 小結(jié)

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

參考文獻(xiàn)：

[1]姜啟源，謝金星.一項(xiàng)成功的高等教育改革實(shí)踐：數(shù)學(xué)建模教學(xué)與競(jìng)賽活動(dòng)的探索與實(shí)踐[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é)任編輯、校對(duì)：方忠］

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

2016-05-25

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

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