Python小白的数学建模课---选址问题
1 P$ u0 ^9 Q+ q u: l' z* K选址问题是要选择设施位置使目标达到最优,是数模竞赛中的常见题型。 小白不一定要掌握所有的选址问题,但要能判断是哪一类问题,用哪个模型。 进一步学习 PuLP工具包中处理复杂问题的字典格式快捷建模方法。
2 y0 ]2 M) X) g7 z) i8 s( c9 ]1. 选址问题; K7 ?7 D$ d2 M8 T9 U( w# o
选址问题是指在某个区域内选择设施的位置使所需的目标达到最优。选址问题也是一种互斥的计划问题。
& G: ^& T4 B; b9 i6 x$ n: l$ i5 T
例如投资场所的选址:企业要在 m 个候选位置选择若干个建厂,已知建厂费用、运输费及 n 个地区的产品需求量,应如何进行选址。
& y1 C& g: }' R4 S w" z9 ]- e& ?/ x) ]9 T
选址问题是运筹学中经典的问题之一,选址问题在生产生活、物流、甚至军事中都有着非常广泛的应用,如工厂、仓库、急救中心、消防站、垃圾处理中心、物流中心、导弹仓库的选址等。更重要的,选址问题也是数模竞赛的热点问题。
' \0 C9 B+ n! v1 H' Y& F4 Y \% g
3 {' i" h) W# C; Y9 ^2 [选址是重要的长期决策,选址的好坏直接影响到服务方式、服务质量、服务效率、服务成本等,从而影响到利润和市场竞争力,选址问题的研究有着重大的经济、社会和军事意义。& n9 ]8 }8 e& V7 u
: c1 p) Q3 `% I4 G" H* E. ^
选址问题有四个基本要素:设施、区域、距离和优化目标。
" Y7 ~) X6 [- }5 O1.1 设施
[* F9 ~9 @4 x8 V8 L选址问题加粗样式中所说的设施,在具体题目中可以是工厂、仓库、服务站等形式。& G( I$ C3 r) K9 Z0 M3 J; n, g
5 K. O$ k% n) P- d4 C7 B2 A2 C1.2 区域5 a' x* t& o& U6 q6 H
选址问题中所说的区域,在具体题目中可以是工厂、车间的内部布局,也可以是给定的某个地区、甚至空间范围。
9 _/ z, Z3 n% c4 _3 w+ @9 J n- v6 s按照规划区域的特征,可以分为连续选址问题和离散选址问题。连续选址问题,设施可以布局在区域内的任意位置,就要求出最优选址的坐标;离散选址问题,只能从若干候选位置中进行选择,运筹学中的选址问题通常是这类离散选址问题。
; B0 F% t& J9 |9 g5 l# E4 f& ?1 q9 u4 Q5 ~, M2 l
1.3 距离& D2 E5 X. U( I# d
选址问题中所说的距离,是指设施到服务对象之间的距离,在具体题目中也可以是某个选址位置的服务时间、成本、覆盖范围。如果用图论方法求解,通常就是连接顶点的边的权值。+ K/ n# o+ F: {" ~
当问题所关注的是设施到服务对象之间的距离时,如果问题给出的不是顶点之间的距离,而是设施的位置坐标,要注意不是只有欧式距离,对于不同问题也可能是球面距离、曼哈顿距离、切比雪夫距离。
0 a& g# z- ^* u2 o: a9 E4 e4 g- [# n, c
1.4 优化目标
6 V) [9 `" F& a0 R5 A/ h选址问题要求选择最好的选址位置,但选址位置只是决策变量,选择的最终目的通常是实现加权距离最短、费用最小、利润最大、时间最短,这才是优化问题的目标函数。1 z% m5 M" u# g/ t4 l* a
按照目标函数的特点,可以分为:中位问题,要求总成本最小;中心问题,服务于每个客户的最大成本最小;反中心问题:服务于每个客户的最小成本最大。6 W) w, w6 k3 b7 e8 [
( e( n( |5 v- U7 m$ D, z7 C
' ]4 d4 I9 b/ x' A7 x0 h7 F0 ?7 h- {- {4 w0 M
2. 常见选址问题及建模 d) l* m7 ?, x, g M! J
2.1 P-中位问题(P-median problem)/ K6 C; G) ^$ |6 {+ T2 w6 C( ^1 a
P-中位问题,假设有 N 个候选服务站和 M 个需求点,要从 N 个候选服务站中选择 P 个,使所有需求点到最近的服务站的加权距离 dij的总和最小。需求点 i 的权值,通常是指该需求点的需求量。
7 |6 \. u, l2 H1 w2 c1 g; r* @4 O9 Z& E, F/ c2 a
这是一个 MinSum 问题,定义决策变量 xj为选中的服务站,yij将各需求点匹配到最近的服务站:: E' h* U& j T) S L) Y e, L9 P
x j = { 1 , 服务站 j 被 选 中 0 ,服 务 站 j 未 被 选 中 9 r' {3 Q" u' {( d( o4 o
yij={1,需要点i由服务站j服务 0,需要点i不由服务站j服务. f; _& ]+ o+ E$ d8 C( k( m2 h U1 ^9 G
可以建立数学模型如下:
% D' m% K1 F% \& t2 d% |minDs.t.:⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧∑j∈Nwidijyij≤D,∀i∑j∈Nxj=P∑j∈Nyij=1,∀iyij−xj≤0,∀i,jxj∈{0,1},yij∈{0,1}
4 Y) h' h5 z Y3 I" f$ V9 T* U# ]" U- O- k' c: j7 y
3 ^# A8 T' h2 x7 c4 d; p' `# V7 N% |7 t8 s5 S. Y6 C
其中:j 为服务站,i 为需求点,dij为需求点 i 到服务站 j 的距离。如果只求需求点到最近的服务站的最大距离,则wi=1;如果要求任一需求点到最近的服务站的最大运费,则wi为需求点 i 的需求量,即加权最大距离。, T. ^: z( S2 I; K. m% ?
# j" a# g- E, I4 m5 U" B0 _) I
5 J; x" A5 A( E
% p% O1 |, e, o+ s* ^9 G% M0 r0 Y6 ]+ V: x" [
# _. [, h7 ^: {+ O
|