孫 峰

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

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

孫 峰

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

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

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

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

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

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

圖1 各區(qū)情況

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

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

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

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

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

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

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

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

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

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

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

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

3.1 解法一：“11選 2”

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

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

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

具體模型如下：

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

3.2 解法二：“7選2”

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

所能供應的學生人數(shù)為：

區(qū)1選定則向區(qū)3供應，反過來，區(qū)3選定則向區(qū)1供應，即是說選區(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ū)之間有銷售代理點，總供應人數(shù)177千人。

3.3 解法三：“7選4”細分法

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

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

選區(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ū)之間有銷售代理點，總供應人數(shù)177千人。

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

從7個區(qū)中選取4個，使得所選取的4個區(qū)能分為兩組，兩個區(qū)一組且同一組中的兩個區(qū)相鄰，這相當于從鄰接矩陣的主對角線的上方選取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ū)之間有銷售代理點，總供應人數(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當且僅當（vi，vj）∈E，Mij=0當且僅當（vi，vj）E。記={1，2，…，n}，ri為區(qū)i大學生數(shù)，（表示與區(qū) i相鄰的所有區(qū)，表示與區(qū)i相鄰的區(qū)中學生數(shù)達到最大的區(qū)，表示的最小元，即與區(qū)i相鄰的區(qū)中學生數(shù)達到最大的區(qū)中編號最小的區(qū)。

4.1 基于選邊的解決辦法

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

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

4.2 基于選點的解決辦法

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

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

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

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

綜上，相應的模型如下：

5 小結(jié)

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

參考文獻：

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

[2]姜啟源，謝金星，葉俊.數(shù)學模型[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

［責任編輯、校對：方忠］

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

2016-05-25

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

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