5_2_選址模型及應(yīng)用(編輯修改稿)
2025-02-26 12:48 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 因素，按照重心公式求解初始方案 xs， ys； ? 利用 xs， ys計(jì)算 di； ? 根據(jù) di解出修正的 xs， ys坐標(biāo)； ? 根據(jù)修正的 xs， ys坐標(biāo)，重新計(jì)算 di； ? 直到迭代收斂。 離散點(diǎn)選址模型 ? 它所擁有的候選方案只有有限個(gè)元素，只需要在這幾個(gè)有限的位置進(jìn)行分析。 ? 覆蓋模型 ? 集合覆蓋模型，用最小數(shù)量的設(shè)施去覆蓋所有的需求點(diǎn)。 ? 最大覆蓋模型，在給定數(shù)量的設(shè)施下，覆蓋盡可能多的需求點(diǎn) ? P中值模型 集合覆蓋模型 最大覆蓋模型 集合覆蓋模型 ? ?()()m i n N1,..0 , 1 ,0 。 ,jjNijj B ii ij j ji A jjijxny i Nd y C x j Nstx i Ny i j N?????? ? ? ? ???? ? ? ????? ? ? ??? ? ? ? ?????最 小 化 設(shè) 施 數(shù) 目 ， 表 示 個(gè) 需 求 點(diǎn) 的 集 合保 證 需 求 點(diǎn) 的 需 求 得 到 完 全 滿 足服 務(wù) 網(wǎng) 點(diǎn) 的 服 務(wù) 能 力 限 制 ，每 個(gè) 地 方 只 能 建 一 個(gè) 設(shè) 施允 許 一 個(gè) 設(shè) 施 只 提 供 部 分 的 需 求。()()0,1,jijijC j d iA j jB i i jjxjy i j? ? ? ??????? ????設(shè) 施 的 容 量 。 第 個(gè) 節(jié) 點(diǎn) 的 需 求 量設(shè) 施 節(jié) 點(diǎn) 所 覆 蓋 的 需 求 節(jié) 點(diǎn) 的 集 合可 以 覆 蓋 需 求 節(jié) 點(diǎn) 的 設(shè) 施 節(jié) 點(diǎn) 的 集 合假 如 該 設(shè) 施 位 于 節(jié) 點(diǎn)假 如 設(shè) 施 不 位 于 節(jié) 點(diǎn)節(jié) 點(diǎn) 的 需 求 中 被 分 配 給 節(jié) 點(diǎn) 的 部 分求解： ? 混合整數(shù)線性規(guī)劃：分枝定界 ? 啟發(fā)式算法 例題：鄉(xiāng)村醫(yī)療診所選址問題 ? 衛(wèi)生部門計(jì)劃在某一個(gè)地區(qū)的 9個(gè)村增加一系列診所。以改善該地區(qū)的醫(yī)療衛(wèi)生水平。 ? 希望在每一個(gè)村周邊 30km的范圍之內(nèi)至少有一個(gè)診所，不考慮診所服務(wù)能力的限制。 ? 衛(wèi)生部門需要確定至少需要多少個(gè)診所和它們相應(yīng)的位置。 ? 除了第 6個(gè)村之外，其他任何一個(gè)村都可以作為診所的候選地點(diǎn)，原因是在第 6村缺乏建立診所的必要條件。 下圖是各個(gè)村之間的相對(duì)位置和距離的地圖。 村編號(hào) A(j) B(i) 1 1,2,3,4 (1,2,3,4) 2 1,2,3 (1,2,3) 3 1,2,3,4,5 1,2,3,4,5 4 1,3,4,5,6,7 1,3,4,5,7 5 3,4,5,6 (3,4,5) 6 4,5,6,7,8 4,5,7,8 7 4,6,7,8 (4,7,8) 8 6,7,8,9 7,8,9 9 8,9 (8,9) 找到第 j個(gè)村子可以提供服務(wù)的所有村的集合 A(j)。（設(shè)施在 j村） 找到可以給第 i個(gè)村提供服務(wù)的所有村的集合 B(i)； 找到其他村服務(wù)范圍的子集，將其省去 選擇合適的組合解 8 8 最大覆蓋模型 ? ?()()()m a x N1,..0 , 1 ,0 。 ,i ijj N i A jijj B ii ij j ji A jjjNjijd y ny i Nd y C x j Ns t x px i Ny i j N???????? ? ? ? ???? ? ? ????? ? ????? ? ? ??? ? ? ? ????????最 大 可 能 對(duì) 需 求 提 供 服 務(wù) ， 表 示 個(gè) 需 求 點(diǎn) 的 集 合服 務(wù) 不 可 能 大 于 當(dāng) 前 需 求 總 和服 務(wù) 網(wǎng) 點(diǎn) 的 服 務(wù) 能 力 限 制 ，設(shè) 施 數(shù) 目 限 制每 個(gè) 地 方 只 能 建 一 個(gè) 設(shè) 施允 許 一 個(gè) 設(shè) 施 只 提 供 部 分 的 需 求貪婪算法 ? 是一個(gè)空集合作為原始的解集合，然后在剩下的所有的其他候選點(diǎn)中，選擇一個(gè)具有最大滿足能力的候選點(diǎn)加入到原來的候選集合中，如此往復(fù)，直到到了設(shè)施數(shù)目的限制或者全部的需求都得到滿足為止。 例：醫(yī)療站的問題 候選集合 (3， 4， 8) 解的集合 S＝ Φ 然后比較 A(3)、 A(4)和 A(8)的數(shù)目， 4村可以提供服務(wù)的對(duì)象最多，將 4村加入到解集合 S中， S＝ {4}。 接著比較 8兩個(gè)村，除去 4提供服務(wù)的村 7外，剩下只有 {2， 8， 9}； 3村對(duì) 2村提供服務(wù)，而 8村可以對(duì) 9兩個(gè)村提供服務(wù)。 8村將作為第二個(gè)投建點(diǎn)加入到解集合中去， S＝ {4， 8}。 P—— 中值模型 ? P— 中值模型是指在一個(gè)給定數(shù)量和位置的需求集合和一個(gè)候選設(shè)施位置的集合下， 分別為 P個(gè)設(shè)施找到合適的位置， 并指派每個(gè)需求點(diǎn)到一個(gè)特定的設(shè)施， 使之達(dá)到在工廠和需求點(diǎn)之間的運(yùn)輸費(fèi)用最低。 下圖說明了P— 中值模型的原理 P— 中值模型的數(shù)學(xué)模型 ? ? ? ?m i n1,. . ,0 , 1 。 0 , 1i ij iji N j MijjMjjMij jj ijd c yy i Nxpsty x i N j Mxy????? ????????? ? ??????????保證每個(gè)客戶 (需求點(diǎn) )只有一個(gè)設(shè)施來提供相應(yīng)的服務(wù) 總的設(shè)施數(shù)目為 P個(gè) 沒有設(shè)施的地點(diǎn) 不會(huì)有客戶對(duì)應(yīng) P— 中值模型的數(shù)學(xué)模型 ? ?M 1 , 2 , , 。()1 j 010iijjijNdimc i jP p mxMy i N j M???????? ? ?? ? ? ? ? ?? ? ? ? ? ? ?需 求 點(diǎn) 的 集 合第 個(gè) 客 戶 的 需 求設(shè) 施 的 候 選 點(diǎn) 集 合地 點(diǎn) 到 設(shè) 施 的 單 位 運(yùn) 費(fèi)可 以 建 立 設(shè) 施 的 總 數(shù)假 如 在 點(diǎn) 建 立 設(shè) 施 ； 其 他假 如 客 戶 由 點(diǎn) 提 供 服 務(wù) 。 其 他? 求解一個(gè) P— 中值模型需要解決兩方面問題： ? 選擇合適設(shè)施位置 (數(shù)學(xué)表達(dá)中的 x變量 ) ? 指派客戶到相應(yīng)的設(shè)施中去 (表達(dá)式中的 y變量 ) P—— 中值模型 ? P— 中值模型是指在一個(gè)給定數(shù)量和位置的需求集合和一個(gè)候選設(shè)施位置的集合下， 分別為 P個(gè)設(shè)施找到合適的位置， 并指派每個(gè)需求點(diǎn)到一個(gè)特定的設(shè)施， 使之達(dá)到在工廠和需求點(diǎn)之間的運(yùn)輸費(fèi)用最低。 下圖說明了P— 中值模型的原理 P— 中值模型的數(shù)學(xué)模型 ? ? ? ?m i n1,. . ,0 , 1 。 0 , 1i ij iji N j MijjMjjMij jj ijd c yy i Nxpsty x i N j Mxy????? ??????
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1