Python小白的数学建模课---选址问题' J! u. N. E' T; _2 x/ M( I; e4 r" l3 b
选址问题是要选择设施位置使目标达到最优,是数模竞赛中的常见题型。 小白不一定要掌握所有的选址问题,但要能判断是哪一类问题,用哪个模型。 进一步学习 PuLP工具包中处理复杂问题的字典格式快捷建模方法。 ' b4 h* t+ J4 a( ^
1. 选址问题. g& O/ ?% o% |5 g$ m
选址问题是指在某个区域内选择设施的位置使所需的目标达到最优。选址问题也是一种互斥的计划问题。
# ]: x- i% f/ s5 x* v9 K# x) g M% O3 j6 P2 x# f7 i0 c$ x: }
例如投资场所的选址:企业要在 m 个候选位置选择若干个建厂,已知建厂费用、运输费及 n 个地区的产品需求量,应如何进行选址。
9 `. f5 y9 Q2 s4 l; A! s0 k$ r% f8 O; e, [4 {, ~+ R$ M! q, c
选址问题是运筹学中经典的问题之一,选址问题在生产生活、物流、甚至军事中都有着非常广泛的应用,如工厂、仓库、急救中心、消防站、垃圾处理中心、物流中心、导弹仓库的选址等。更重要的,选址问题也是数模竞赛的热点问题。
* c. S* S* L: G
- ~( _5 R0 J/ p1 z/ z& M0 J选址是重要的长期决策,选址的好坏直接影响到服务方式、服务质量、服务效率、服务成本等,从而影响到利润和市场竞争力,选址问题的研究有着重大的经济、社会和军事意义。( m4 r3 D8 I6 Y
* f, |5 g8 O9 {( X' R2 }选址问题有四个基本要素:设施、区域、距离和优化目标。
& D/ z% J' e5 }. J6 I& p. I m1.1 设施* p; W' K5 c" w$ o! y/ k
选址问题加粗样式中所说的设施,在具体题目中可以是工厂、仓库、服务站等形式。
+ K+ s3 r9 O' Q7 P. f6 O* {
* D6 W3 }8 f% D" J1.2 区域
- S1 ]+ r9 p& ~选址问题中所说的区域,在具体题目中可以是工厂、车间的内部布局,也可以是给定的某个地区、甚至空间范围。
4 C: V; Z1 q7 m8 w按照规划区域的特征,可以分为连续选址问题和离散选址问题。连续选址问题,设施可以布局在区域内的任意位置,就要求出最优选址的坐标;离散选址问题,只能从若干候选位置中进行选择,运筹学中的选址问题通常是这类离散选址问题。
: J7 \$ ]+ Y4 z7 I* q% I/ x; x2 e: {
1.3 距离; O- `5 }- n0 T+ g2 w0 c
选址问题中所说的距离,是指设施到服务对象之间的距离,在具体题目中也可以是某个选址位置的服务时间、成本、覆盖范围。如果用图论方法求解,通常就是连接顶点的边的权值。
# a% L: I. _5 D4 N" ?; y% ]+ q: b- J# n当问题所关注的是设施到服务对象之间的距离时,如果问题给出的不是顶点之间的距离,而是设施的位置坐标,要注意不是只有欧式距离,对于不同问题也可能是球面距离、曼哈顿距离、切比雪夫距离。- L* q; K/ g1 [( r0 P1 b
+ l7 r7 F+ @$ V; s6 w2 c9 T1.4 优化目标
u6 D; @2 D/ l7 v9 _8 j2 Q' q' T: i选址问题要求选择最好的选址位置,但选址位置只是决策变量,选择的最终目的通常是实现加权距离最短、费用最小、利润最大、时间最短,这才是优化问题的目标函数。. p$ |& @; M1 V4 B6 a2 o2 A
按照目标函数的特点,可以分为:中位问题,要求总成本最小;中心问题,服务于每个客户的最大成本最小;反中心问题:服务于每个客户的最小成本最大。
8 U Q( _1 d6 P* a( _$ C2 Q
, q# A' A$ I$ W9 X& y {
8 F% k. R2 i6 }8 z% D4 C" k, p
~7 E5 g; o( a u. J2. 常见选址问题及建模. l8 H& b' ~$ B, q
2.1 P-中位问题(P-median problem)
8 u$ l8 p; G' d/ \8 t, KP-中位问题,假设有 N 个候选服务站和 M 个需求点,要从 N 个候选服务站中选择 P 个,使所有需求点到最近的服务站的加权距离 dij的总和最小。需求点 i 的权值,通常是指该需求点的需求量。
/ E0 s2 `5 ~& s: b3 l
, z M) \) n6 U4 O. N这是一个 MinSum 问题,定义决策变量 xj为选中的服务站,yij将各需求点匹配到最近的服务站:
6 h7 {0 k8 r! b1 F p, i7 Nx j = { 1 , 服务站 j 被 选 中 0 ,服 务 站 j 未 被 选 中 U" j" O- V7 k) O9 h
yij={1,需要点i由服务站j服务 0,需要点i不由服务站j服务& n0 O1 x; }5 b' ~
可以建立数学模型如下:& I9 w4 m+ I, }8 w9 X, X5 K
minDs.t.:⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧∑j∈Nwidijyij≤D,∀i∑j∈Nxj=P∑j∈Nyij=1,∀iyij−xj≤0,∀i,jxj∈{0,1},yij∈{0,1}) }, s) }& x }% k; l) F
4 G' E B5 g& _# E. x8 ]$ q& |
8 ?7 Q p: n, x# ]: x: V, b& l' q, P2 D1 Z% O+ E3 @# \! t" k
其中:j 为服务站,i 为需求点,dij为需求点 i 到服务站 j 的距离。如果只求需求点到最近的服务站的最大距离,则wi=1;如果要求任一需求点到最近的服务站的最大运费,则wi为需求点 i 的需求量,即加权最大距离。1 c. g7 v1 ^( S% R. a- v/ b) O
n: P, i1 a8 Z# p; _
- H6 `. c1 [6 K+ t0 V: u4 x) y
' g8 s& {. r, T6 T$ q2 `, s! q7 G0 E! h0 h1 n2 m
. \$ A5 }+ H1 \! I |