Python小白的数学建模课---选址问题9 p2 D/ l8 o+ |; n( R& x8 O9 G
选址问题是要选择设施位置使目标达到最优,是数模竞赛中的常见题型。 小白不一定要掌握所有的选址问题,但要能判断是哪一类问题,用哪个模型。 进一步学习 PuLP工具包中处理复杂问题的字典格式快捷建模方法。
6 b1 h3 y5 ~, R" _& g# A" P7 {$ H, Y) H1. 选址问题
6 Y4 n0 h: _ ]3 j! ~2 ?: w选址问题是指在某个区域内选择设施的位置使所需的目标达到最优。选址问题也是一种互斥的计划问题。
1 Z* V+ x: J& V/ U2 c2 P; `, F0 u, _, `$ g, ?
例如投资场所的选址:企业要在 m 个候选位置选择若干个建厂,已知建厂费用、运输费及 n 个地区的产品需求量,应如何进行选址。3 s; X" B3 ^/ L. Q
" K' g% `$ d& d$ t: n g选址问题是运筹学中经典的问题之一,选址问题在生产生活、物流、甚至军事中都有着非常广泛的应用,如工厂、仓库、急救中心、消防站、垃圾处理中心、物流中心、导弹仓库的选址等。更重要的,选址问题也是数模竞赛的热点问题。
6 b9 F5 V/ |* v# w5 _9 z! k1 O' k" q8 i3 a( V. T% r
选址是重要的长期决策,选址的好坏直接影响到服务方式、服务质量、服务效率、服务成本等,从而影响到利润和市场竞争力,选址问题的研究有着重大的经济、社会和军事意义。' Y0 e+ L( }, j1 l, f+ z l, q) \
$ k4 E) |* s6 ]- Y- {& \选址问题有四个基本要素:设施、区域、距离和优化目标。" v; v0 J1 M- A$ L- m8 ]
1.1 设施
9 {% d$ [7 a) I) p7 d q- a选址问题加粗样式中所说的设施,在具体题目中可以是工厂、仓库、服务站等形式。( S) U% O. n# a3 C/ I
1 W, a, x5 f& ~
1.2 区域
) X5 N7 V* _! C* ~4 v选址问题中所说的区域,在具体题目中可以是工厂、车间的内部布局,也可以是给定的某个地区、甚至空间范围。9 [4 J1 E% }' i9 U- [8 ]1 H$ m
按照规划区域的特征,可以分为连续选址问题和离散选址问题。连续选址问题,设施可以布局在区域内的任意位置,就要求出最优选址的坐标;离散选址问题,只能从若干候选位置中进行选择,运筹学中的选址问题通常是这类离散选址问题。
8 x3 J2 ?$ ^9 ^& h3 O: Y. _; o
+ Q' z \4 A0 g, W+ K! l1.3 距离
, P9 z, `- p7 ?, e4 Q' ^& L% B选址问题中所说的距离,是指设施到服务对象之间的距离,在具体题目中也可以是某个选址位置的服务时间、成本、覆盖范围。如果用图论方法求解,通常就是连接顶点的边的权值。/ A. v" y! O# |; @* a& D* O5 Y/ [
当问题所关注的是设施到服务对象之间的距离时,如果问题给出的不是顶点之间的距离,而是设施的位置坐标,要注意不是只有欧式距离,对于不同问题也可能是球面距离、曼哈顿距离、切比雪夫距离。4 ^- }, [; p/ `' y. \2 e+ f
1 j3 B* k: K+ q+ B* T7 K) d& d1.4 优化目标
3 h0 l! `; C: c# T- O选址问题要求选择最好的选址位置,但选址位置只是决策变量,选择的最终目的通常是实现加权距离最短、费用最小、利润最大、时间最短,这才是优化问题的目标函数。
* J! d* D1 m0 ~* X$ O/ }5 t' ~7 l' l按照目标函数的特点,可以分为:中位问题,要求总成本最小;中心问题,服务于每个客户的最大成本最小;反中心问题:服务于每个客户的最小成本最大。* l- a" v, T/ p! y: n
9 u$ S( U5 q6 W2 Y2 _: j8 \0 {
- W) h: }( |2 y. a( W3 q8 K
% T: o! h7 T7 D$ e# J/ h2. 常见选址问题及建模
, e) Z0 D/ r' r1 Q: C7 I2.1 P-中位问题(P-median problem)4 M0 M6 ~: t- `1 j; c
P-中位问题,假设有 N 个候选服务站和 M 个需求点,要从 N 个候选服务站中选择 P 个,使所有需求点到最近的服务站的加权距离 dij的总和最小。需求点 i 的权值,通常是指该需求点的需求量。8 t4 I( a3 `- k1 D. H# |( i
3 F' l) L# ^; G8 J这是一个 MinSum 问题,定义决策变量 xj为选中的服务站,yij将各需求点匹配到最近的服务站:- d3 u( f* i2 [$ |/ d' b0 v
x j = { 1 , 服务站 j 被 选 中 0 ,服 务 站 j 未 被 选 中 0 _0 C. b/ c; ]6 S/ V* l
yij={1,需要点i由服务站j服务 0,需要点i不由服务站j服务1 [, _( n- f1 q7 N- H
可以建立数学模型如下:" Z% `: K6 K- Z
minDs.t.:⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧∑j∈Nwidijyij≤D,∀i∑j∈Nxj=P∑j∈Nyij=1,∀iyij−xj≤0,∀i,jxj∈{0,1},yij∈{0,1}
/ \, {/ o7 S7 @# @' L' X, g" h$ ^! m P; k0 n
6 d2 R' D" c. J% E
' q& o6 m5 r$ @其中:j 为服务站,i 为需求点,dij为需求点 i 到服务站 j 的距离。如果只求需求点到最近的服务站的最大距离,则wi=1;如果要求任一需求点到最近的服务站的最大运费,则wi为需求点 i 的需求量,即加权最大距离。
( Y6 U8 l0 N+ @+ ~6 C; j1 R/ r' V+ C" w9 }8 e! n
5 l- o! J0 j, }! F8 R9 w
; F0 \, k: E0 c% T$ z0 C% }4 \
7 z9 P7 f1 O& K: |' j$ x! ^. \9 n9 f8 Q
& V7 E6 e1 W. n |