Python小白的数学建模课---选址问题
$ M3 V" D, r# ^: g+ w E选址问题是要选择设施位置使目标达到最优,是数模竞赛中的常见题型。 小白不一定要掌握所有的选址问题,但要能判断是哪一类问题,用哪个模型。 进一步学习 PuLP工具包中处理复杂问题的字典格式快捷建模方法。 9 k5 b0 Y# s" W x; O
1. 选址问题, H& [- L8 X# L% z5 d$ g8 f
选址问题是指在某个区域内选择设施的位置使所需的目标达到最优。选址问题也是一种互斥的计划问题。
, k9 F" s- b) Z- M9 o3 ~
+ V3 V. C1 @- c" h7 K例如投资场所的选址:企业要在 m 个候选位置选择若干个建厂,已知建厂费用、运输费及 n 个地区的产品需求量,应如何进行选址。
. T5 `) e6 S9 R
" h- W" |! d0 d ~& u, U# k选址问题是运筹学中经典的问题之一,选址问题在生产生活、物流、甚至军事中都有着非常广泛的应用,如工厂、仓库、急救中心、消防站、垃圾处理中心、物流中心、导弹仓库的选址等。更重要的,选址问题也是数模竞赛的热点问题。" Q% j; R2 O- U- \- v
7 n( q8 P6 F# g; f1 A
选址是重要的长期决策,选址的好坏直接影响到服务方式、服务质量、服务效率、服务成本等,从而影响到利润和市场竞争力,选址问题的研究有着重大的经济、社会和军事意义。# E+ W) }6 ]; T5 x2 y
1 f( P( J$ Q5 ]) \, c0 X6 H D选址问题有四个基本要素:设施、区域、距离和优化目标。
& g% h3 q _' G( B' I) ~+ V3 K1.1 设施, j- ?# W. B" j; E0 n6 a
选址问题加粗样式中所说的设施,在具体题目中可以是工厂、仓库、服务站等形式。3 t1 W7 I$ c- V+ f
: { \$ T; x* X& C; S
1.2 区域
2 [$ h7 }* A, o, r+ ?5 U& x$ ?选址问题中所说的区域,在具体题目中可以是工厂、车间的内部布局,也可以是给定的某个地区、甚至空间范围。
3 _! F( \8 e" w( ?按照规划区域的特征,可以分为连续选址问题和离散选址问题。连续选址问题,设施可以布局在区域内的任意位置,就要求出最优选址的坐标;离散选址问题,只能从若干候选位置中进行选择,运筹学中的选址问题通常是这类离散选址问题。& V# a( j4 g7 }* x
; S# F3 K- J; l0 W, L1.3 距离
/ `/ t: ^' y7 H" [! I选址问题中所说的距离,是指设施到服务对象之间的距离,在具体题目中也可以是某个选址位置的服务时间、成本、覆盖范围。如果用图论方法求解,通常就是连接顶点的边的权值。1 V, a; ?: M& E1 Y; D# k
当问题所关注的是设施到服务对象之间的距离时,如果问题给出的不是顶点之间的距离,而是设施的位置坐标,要注意不是只有欧式距离,对于不同问题也可能是球面距离、曼哈顿距离、切比雪夫距离。7 b* Y3 Q F0 z9 {* f# I
, r6 i% P( a4 C% j' b3 P1.4 优化目标+ e" g, T8 t6 ^- p0 |
选址问题要求选择最好的选址位置,但选址位置只是决策变量,选择的最终目的通常是实现加权距离最短、费用最小、利润最大、时间最短,这才是优化问题的目标函数。) e; G9 U$ W! D
按照目标函数的特点,可以分为:中位问题,要求总成本最小;中心问题,服务于每个客户的最大成本最小;反中心问题:服务于每个客户的最小成本最大。: y+ f& @: w) N& ~
' h; i4 S% Z- \ g, [$ N
: z, X. a$ C2 W5 {; w8 w, v5 X
6 r1 V. h: o3 P2. 常见选址问题及建模
1 z* n6 L7 ]4 B/ E$ _) @2.1 P-中位问题(P-median problem)
" S8 H7 Y( v1 t! e. [6 sP-中位问题,假设有 N 个候选服务站和 M 个需求点,要从 N 个候选服务站中选择 P 个,使所有需求点到最近的服务站的加权距离 dij的总和最小。需求点 i 的权值,通常是指该需求点的需求量。
( G/ {7 t3 Q# X. |9 X
* g4 _7 E+ @) i3 s这是一个 MinSum 问题,定义决策变量 xj为选中的服务站,yij将各需求点匹配到最近的服务站:
* m4 B2 S/ s: S5 ]x j = { 1 , 服务站 j 被 选 中 0 ,服 务 站 j 未 被 选 中 % Y1 J7 D5 b9 x. I( D
yij={1,需要点i由服务站j服务 0,需要点i不由服务站j服务
3 J8 k8 }7 A, m7 }; z5 N& a可以建立数学模型如下:6 Q6 X8 c: {& d/ l7 f
minDs.t.:⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧∑j∈Nwidijyij≤D,∀i∑j∈Nxj=P∑j∈Nyij=1,∀iyij−xj≤0,∀i,jxj∈{0,1},yij∈{0,1}
# x1 S: @& t$ s7 `
4 T/ s/ W8 ^9 R m5 |
* h- o3 b9 k# f. n$ ]! f( d" q, s
其中:j 为服务站,i 为需求点,dij为需求点 i 到服务站 j 的距离。如果只求需求点到最近的服务站的最大距离,则wi=1;如果要求任一需求点到最近的服务站的最大运费,则wi为需求点 i 的需求量,即加权最大距离。
- w5 Y- g5 w1 H) K) ^7 J* O" E/ D
0 K% m' o0 b' t' U" Z+ S5 ?- O4 D4 [) B
i2 E! b W5 t8 ^& ]$ ]3 C c& g % E3 f% |/ Z1 t- d1 O# q8 d# b
|