请选择 进入手机版 | 继续访问电脑版

QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 2770|回复: 1

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

[复制链接]
字体大小: 正常 放大

1158

主题

15

听众

1万

积分

  • TA的每日心情
    开心
    2023-7-31 10:17
  • 签到天数: 198 天

    [LV.7]常住居民III

    自我介绍
    数学中国浅夏
    发表于 2021-10-28 18:29 |显示全部楼层
    |招呼Ta 关注Ta
                                            Python小白的数学建模课---选址问题9 p2 D/ l8 o+ |; n( R& x8 O9 G

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

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

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


    6 b1 h3 y5 ~, R" _& g# A" P7 {$ H, Y) H1. 选址问题
    6 Y4 n0 h: _  ]3 j! ~2 ?: w选址问题是指在某个区域内选择设施的位置使所需的目标达到最优。选址问题也是一种互斥的计划问题。
    1 Z* V+ x: J& V/ U2 c2 P; `, F0 u, _, `$ g, ?
    例如投资场所的选址:企业要在 m 个候选位置选择若干个建厂,已知建厂费用、运输费及 n 个地区的产品需求量,应如何进行选址。3 s; X" B3 ^/ L. Q

    " K' g% `$ d& d$ t: n  g选址问题是运筹学中经典的问题之一,选址问题在生产生活、物流、甚至军事中都有着非常广泛的应用,如工厂、仓库、急救中心、消防站、垃圾处理中心、物流中心、导弹仓库的选址等。更重要的,选址问题也是数模竞赛的热点问题。
    6 b9 F5 V/ |* v# w5 _9 z! k1 O' k" q8 i3 a( V. T% r
    选址是重要的长期决策,选址的好坏直接影响到服务方式、服务质量、服务效率、服务成本等,从而影响到利润和市场竞争力,选址问题的研究有着重大的经济、社会和军事意义。' Y0 e+ L( }, j1 l, f+ z  l, q) \

    $ k4 E) |* s6 ]- Y- {& \选址问题有四个基本要素:设施、区域、距离和优化目标。" v; v0 J1 M- A$ L- m8 ]
    1.1 设施
    9 {% d$ [7 a) I) p7 d  q- a选址问题加粗样式中所说的设施,在具体题目中可以是工厂、仓库、服务站等形式。( S) U% O. n# a3 C/ I
    1 W, a, x5 f& ~
    1.2 区域
    ) X5 N7 V* _! C* ~4 v选址问题中所说的区域,在具体题目中可以是工厂、车间的内部布局,也可以是给定的某个地区、甚至空间范围。9 [4 J1 E% }' i9 U- [8 ]1 H$ m
    按照规划区域的特征,可以分为连续选址问题和离散选址问题。连续选址问题,设施可以布局在区域内的任意位置,就要求出最优选址的坐标;离散选址问题,只能从若干候选位置中进行选择,运筹学中的选址问题通常是这类离散选址问题。
    8 x3 J2 ?$ ^9 ^& h3 O: Y. _; o
    + Q' z  \4 A0 g, W+ K! l1.3 距离
    , P9 z, `- p7 ?, e4 Q' ^& L% B选址问题中所说的距离,是指设施到服务对象之间的距离,在具体题目中也可以是某个选址位置的服务时间、成本、覆盖范围。如果用图论方法求解,通常就是连接顶点的边的权值。/ A. v" y! O# |; @* a& D* O5 Y/ [
    当问题所关注的是设施到服务对象之间的距离时,如果问题给出的不是顶点之间的距离,而是设施的位置坐标,要注意不是只有欧式距离,对于不同问题也可能是球面距离、曼哈顿距离、切比雪夫距离。4 ^- }, [; p/ `' y. \2 e+ f

    1 j3 B* k: K+ q+ B* T7 K) d& d1.4 优化目标
    3 h0 l! `; C: c# T- O选址问题要求选择最好的选址位置,但选址位置只是决策变量,选择的最终目的通常是实现加权距离最短、费用最小、利润最大、时间最短,这才是优化问题的目标函数。
    * J! d* D1 m0 ~* X$ O/ }5 t' ~7 l' l按照目标函数的特点,可以分为:中位问题,要求总成本最小;中心问题,服务于每个客户的最大成本最小;反中心问题:服务于每个客户的最小成本最大。* l- a" v, T/ p! y: n

    9 u$ S( U5 q6 W2 Y2 _: j8 \0 {
    - W) h: }( |2 y. a( W3 q8 K

    % T: o! h7 T7 D$ e# J/ h2. 常见选址问题及建模
    , e) Z0 D/ r' r1 Q: C7 I2.1 P-中位问题(P-median problem)4 M0 M6 ~: t- `1 j; c
    P-中位问题,假设有 N 个候选服务站和 M 个需求点,要从 N 个候选服务站中选择 P 个,使所有需求点到最近的服务站的加权距离 dij的总和最小。需求点 i 的权值,通常是指该需求点的需求量。8 t4 I( a3 `- k1 D. H# |( i

    3 F' l) L# ^; G8 J这是一个 MinSum 问题,定义决策变量 xj为选中的服务站,yij将各需求点匹配到最近的服务站:- d3 u( f* i2 [$ |/ d' b0 v
    x j = { 1 , 服务站  j 被 选 中    0  ,服 务 站 j 未 被 选 中 0 _0 C. b/ c; ]6 S/ V* l
    yij={1,需要点i由服务站j服务    0,需要点i不由服务站j服务1 [, _( n- f1 q7 N- H
    可以建立数学模型如下:" Z% `: K6 K- Z
    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}​
    / \, {/ o7 S7 @# @' L' X, g" h$ ^! m  P; k0 n

    6 d2 R' D" c. J% E

    ' q& o6 m5 r$ @其中:j 为服务站,i 为需求点,dij为需求点 i 到服务站 j 的距离。如果只求需求点到最近的服务站的最大距离,则wi=1;如果要求任一需求点到最近的服务站的最大运费,则wi为需求点 i 的需求量,即加权最大距离。
    ( Y6 U8 l0 N+ @+ ~6 C; j1 R/ r' V+ C" w9 }8 e! n

    5 l- o! J0 j, }! F8 R9 w

    ; F0 \, k: E0 c% T$ z0 C% }4 \
    7 z9 P7 f1 O& K: |' j$ x! ^. \9 n9 f8 Q


    & V7 E6 e1 W. n
    zan
    sjlxdn        

    1

    主题

    2

    听众

    155

    积分

    升级  27.5%

  • TA的每日心情
    无聊
    2022-2-19 17:40
  • 签到天数: 30 天

    [LV.5]常住居民I

    国际赛参赛者

    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2024-3-28 23:00 , Processed in 0.356435 second(s), 56 queries .

    回顶部