数学建模社区-数学中国

标题: Python小白的数学建模课---选址问题 [打印本页]

作者: 1047521767    时间: 2021-10-28 18:29
标题: Python小白的数学建模课---选址问题
                                        Python小白的数学建模课---选址问题
8 M9 _8 o5 W* B) Z% J) |) u- R

选址问题是要选择设施位置使目标达到最优,是数模竞赛中的常见题型。

小白不一定要掌握所有的选址问题,但要能判断是哪一类问题,用哪个模型。

进一步学习 PuLP工具包中处理复杂问题的字典格式快捷建模方法。

4 ]# T  I  x9 ]8 _& L4 d
1. 选址问题: W8 L6 ]. C  z8 X7 [+ x( n9 ~& y3 |4 n
选址问题是指在某个区域内选择设施的位置使所需的目标达到最优。选址问题也是一种互斥的计划问题。7 v; M3 ~2 k8 M3 C6 O$ D9 d9 j
8 R  g" G9 E1 r) F
例如投资场所的选址:企业要在 m 个候选位置选择若干个建厂,已知建厂费用、运输费及 n 个地区的产品需求量,应如何进行选址。: G6 V) X$ R; X8 [) @% s* N
& E3 C. ^9 [9 l8 v5 u3 n, {
选址问题是运筹学中经典的问题之一,选址问题在生产生活、物流、甚至军事中都有着非常广泛的应用,如工厂、仓库、急救中心、消防站、垃圾处理中心、物流中心、导弹仓库的选址等。更重要的,选址问题也是数模竞赛的热点问题。7 L% v, T+ a8 j- }  i$ @

/ ^7 X2 w' N' d9 T% I' G/ ^9 H* `. D选址是重要的长期决策,选址的好坏直接影响到服务方式、服务质量、服务效率、服务成本等,从而影响到利润和市场竞争力,选址问题的研究有着重大的经济、社会和军事意义。7 q6 |4 {* b. D6 {- U

- `5 W( n3 N4 f  N, A0 L选址问题有四个基本要素:设施、区域、距离和优化目标。# c  i' `9 T2 y) e' [" v
1.1 设施+ F7 ]% K1 z& g, G) R
选址问题加粗样式中所说的设施,在具体题目中可以是工厂、仓库、服务站等形式。
' K# v+ L; ]* z5 L6 w) C. ^- F/ T! G3 }, T% j
1.2 区域+ x2 ?3 X: x5 W" s1 l, `9 \+ n
选址问题中所说的区域,在具体题目中可以是工厂、车间的内部布局,也可以是给定的某个地区、甚至空间范围。- U3 K- K) p5 z1 L' l
按照规划区域的特征,可以分为连续选址问题和离散选址问题。连续选址问题,设施可以布局在区域内的任意位置,就要求出最优选址的坐标;离散选址问题,只能从若干候选位置中进行选择,运筹学中的选址问题通常是这类离散选址问题。9 |6 Q. Q/ Z; j4 [" T6 N1 l4 n
4 i6 J1 |6 h1 W/ |* ]5 V
1.3 距离' e- \% Y* p' M- z6 f7 w
选址问题中所说的距离,是指设施到服务对象之间的距离,在具体题目中也可以是某个选址位置的服务时间、成本、覆盖范围。如果用图论方法求解,通常就是连接顶点的边的权值。
# g5 r; T% @! Q  r当问题所关注的是设施到服务对象之间的距离时,如果问题给出的不是顶点之间的距离,而是设施的位置坐标,要注意不是只有欧式距离,对于不同问题也可能是球面距离、曼哈顿距离、切比雪夫距离。# q* c7 u% d2 o- x2 w- _- g
1 n& |. ^, E' [# H' n
1.4 优化目标
" Y# Q4 }& |' G  D8 Z( n+ W, E选址问题要求选择最好的选址位置,但选址位置只是决策变量,选择的最终目的通常是实现加权距离最短、费用最小、利润最大、时间最短,这才是优化问题的目标函数。7 |" D; Q: C" g! |, b
按照目标函数的特点,可以分为:中位问题,要求总成本最小;中心问题,服务于每个客户的最大成本最小;反中心问题:服务于每个客户的最小成本最大。& K( S6 W8 {! i  `4 N
5 W' I0 Z9 ?! Z# o9 X/ z1 ^( i

! U2 M, }& L8 L5 l

  g3 ~, \! a: b+ G$ p2. 常见选址问题及建模7 g: G) J7 l: A+ V, ~
2.1 P-中位问题(P-median problem)8 L8 Y* R" h/ ?! ^1 ]1 O
P-中位问题,假设有 N 个候选服务站和 M 个需求点,要从 N 个候选服务站中选择 P 个,使所有需求点到最近的服务站的加权距离 dij的总和最小。需求点 i 的权值,通常是指该需求点的需求量。
/ j% f' R7 r1 _2 }3 N& s7 W( W- {: Y  @
这是一个 MinSum 问题,定义决策变量 xj为选中的服务站,yij将各需求点匹配到最近的服务站:' Z' [0 L* B% g! G- O
x j = { 1 , 服务站  j 被 选 中    0  ,服 务 站 j 未 被 选 中 9 _1 ?' @. a- o
yij={1,需要点i由服务站j服务    0,需要点i不由服务站j服务
7 X: ^- v1 r4 |可以建立数学模型如下:& @4 H# p2 A  t7 D, x0 f
minDs.t.:⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧​∑j∈N​wi​dij​yij​≤D,∀i∑j∈N​xj​=P∑j∈N​yij​=1,∀iyij​−xj​≤0,∀i,jxj​∈{0,1},yij​∈{0,1}​; \, m& [8 i& T: K- a

4 {! v0 T1 Z8 ~: H  @% c' r

3 X$ h$ J4 L* E4 Z

# V* V$ c% B) X" e. ^& X+ y其中:j 为服务站,i 为需求点,dij为需求点 i 到服务站 j 的距离。如果只求需求点到最近的服务站的最大距离,则wi=1;如果要求任一需求点到最近的服务站的最大运费,则wi为需求点 i 的需求量,即加权最大距离。
1 f1 d6 F1 Z7 o6 |9 e9 _/ g' @7 D6 ~


. f: P! s& G8 y  U; p- G3 s9 l6 |

2 y( z6 A  v7 W$ z* t

0 `0 g% S# J" B# X

作者: sjlxdn    时间: 2021-10-31 21:35
111111111111
2 Z0 {+ q  I, z0 j6 G  a; }. R




欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5