Python小白的数学建模课---选址问题

1047521767

                                        Python小白的数学建模课---选址问题
, |2 h! ], o8 D- ?. |

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

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

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

1. 选址问题
选址问题是指在某个区域内选择设施的位置使所需的目标达到最优。选址问题也是一种互斥的计划问题。
& ]) n" h6 f% j. a2 _
+ K- x0 W4 f2 V- H  h! z例如投资场所的选址：企业要在 m 个候选位置选择若干个建厂，已知建厂费用、运输费及 n 个地区的产品需求量，应如何进行选址。

( f+ q1 D* c0 V7 J1 H  u选址问题是运筹学中经典的问题之一，选址问题在生产生活、物流、甚至军事中都有着非常广泛的应用，如工厂、仓库、急救中心、消防站、垃圾处理中心、物流中心、导弹仓库的选址等。更重要的，选址问题也是数模竞赛的热点问题。

  P- A$ w5 U0 R) N选址是重要的长期决策，选址的好坏直接影响到服务方式、服务质量、服务效率、服务成本等，从而影响到利润和市场竞争力，选址问题的研究有着重大的经济、社会和军事意义。
* K7 x8 Z; P' I2 o
选址问题有四个基本要素：设施、区域、距离和优化目标。
0 U* S1 g1 ~+ I" Y, x( o4 N; M. c1.1 设施
选址问题加粗样式中所说的设施，在具体题目中可以是工厂、仓库、服务站等形式。

1.2 区域
7 ]$ ?) _0 c6 Y2 m$ V/ J5 V选址问题中所说的区域，在具体题目中可以是工厂、车间的内部布局，也可以是给定的某个地区、甚至空间范围。
按照规划区域的特征，可以分为连续选址问题和离散选址问题。连续选址问题，设施可以布局在区域内的任意位置，就要求出最优选址的坐标；离散选址问题，只能从若干候选位置中进行选择，运筹学中的选址问题通常是这类离散选址问题。
7 o: G) w! _. j/ W+ h
1.3 距离
选址问题中所说的距离，是指设施到服务对象之间的距离，在具体题目中也可以是某个选址位置的服务时间、成本、覆盖范围。如果用图论方法求解，通常就是连接顶点的边的权值。
当问题所关注的是设施到服务对象之间的距离时，如果问题给出的不是顶点之间的距离，而是设施的位置坐标，要注意不是只有欧式距离，对于不同问题也可能是球面距离、曼哈顿距离、切比雪夫距离。

( s" r* b5 r% ^8 s1.4 优化目标
* r! @9 g# t1 W选址问题要求选择最好的选址位置，但选址位置只是决策变量，选择的最终目的通常是实现加权距离最短、费用最小、利润最大、时间最短，这才是优化问题的目标函数。
. V' ]( P% l" Y! F按照目标函数的特点，可以分为：中位问题，要求总成本最小；中心问题，服务于每个客户的最大成本最小；反中心问题：服务于每个客户的最小成本最大。
$ B+ _, O' w( L- k8 }

3 R+ P0 Y" m* m9 `  [4 h5 K' G
8 V! c( K* ~' G+ m- T' S5 ^2. 常见选址问题及建模
2.1 P-中位问题（P-median problem）
P-中位问题，假设有 N 个候选服务站和 M 个需求点，要从 N 个候选服务站中选择 P 个，使所有需求点到最近的服务站的加权距离 dij的总和最小。需求点 i 的权值，通常是指该需求点的需求量。
! X7 h0 s3 w0 o7 q4 k) ^
' [; J0 t, t/ \! |- U3 P1 i这是一个 MinSum 问题，定义决策变量 xj为选中的服务站，yij将各需求点匹配到最近的服务站：
: w. Y( w% n8 y6 N/ n  e4 _x j = { 1 ， 服务站  j 被 选 中    0  ，服 务 站 j 未 被 选 中
4 O8 F3 n4 Z% q/ K) |3 uyij={1，需要点i由服务站j服务    0，需要点i不由服务站j服务
可以建立数学模型如下：
& ^) A# c2 `  R7 qminDs.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}​
! t8 j5 T# q4 O1 @" a: A
( g  d$ u  A: h) c6 `) y
- u3 w% e0 _2 r& q​
6 O, X' w# P' j/ z% \& Z' ^其中：j 为服务站，i 为需求点，dij为需求点 i 到服务站 j 的距离。如果只求需求点到最近的服务站的最大距离，则wi=1;如果要求任一需求点到最近的服务站的最大运费，则wi为需求点 i 的需求量，即加权最大距离。
. B- r! d( q% j# j$ n" r7 v" N
) j1 i- I$ D  l: c5 O- t' L

; r0 Q! c+ c0 G- m# j5 [; R

$ o0 r7 s+ e( J

3 [; E; J, l* q! E

sjlxdn

111111111111