覆蓋模型ppt課件

1、覆蓋模型 1;. 覆蓋模型覆蓋模型是一類(lèi)離散點(diǎn)選址模型。所謂覆蓋模型，是對(duì)于需求知的一些需求點(diǎn)，如何確定一組效力設(shè)備來(lái)滿足這些需求點(diǎn)的需求。常用的有兩類(lèi)主要模型：集合覆蓋模型，即用最小數(shù)量的設(shè)備去覆蓋一切的需求點(diǎn)；最大覆蓋模型，即在給定數(shù)量的設(shè)備去覆蓋一切需求點(diǎn)。區(qū)別：集合覆蓋模型要滿足一切需求點(diǎn)的需求，而最大覆蓋模型那么只覆蓋有限的需求點(diǎn)，兩種模型的運(yùn)用情況取決于效力設(shè)備的資源充足與否。2集合覆蓋模型的構(gòu)建第一步，找到每一個(gè)候選地址可以提供效力的一切需求點(diǎn)的集合 A(j), 它們間隔該候選地址的間隔小于或者等于指定距離。第二步，找到可以給每一個(gè)需求點(diǎn)提供效力的一切候選地址的集合 B(i)，普

2、通說(shuō)來(lái)，它與 A(j)是一樣的，但是思索他條件的限制，也有不一樣的情況，這要視詳細(xì)的情況而定。第三步，設(shè)變量 xij 1 表示位于 i 點(diǎn)的物流中心向位于 j點(diǎn)的需求點(diǎn)供貨，否那么 xij 0。yi 1 表示在 i 點(diǎn)建立物流中心，否那么 yi=0。由于每個(gè)需求點(diǎn)都可以從一個(gè)或者多個(gè)物流中心進(jìn)貨，由此決議了物流效力分配的約束條件為,1，根據(jù) B(i)可以寫(xiě)出各個(gè)約束條件。但是為了減少物流中心建立的本錢(qián)，應(yīng)該選取可以覆蓋一切需求點(diǎn)的最小數(shù)量的候選地址的組合。第四步，檢驗(yàn)。根據(jù)集合 A(j)，驗(yàn)證求得的物流中心選址能否覆蓋了一切需求點(diǎn)。3實(shí)例在Ad-hoc傳感器網(wǎng)絡(luò)中，信號(hào)覆蓋范圍或覆蓋率是衡量網(wǎng)絡(luò)效力質(zhì)量的主要度量目的。因此，如何在保證信號(hào)覆蓋質(zhì)量的前提下，盡能夠地節(jié)省網(wǎng)絡(luò)建立本錢(qián)就顯得格外重要1。如圖1所示，四個(gè)平面上的圓形區(qū)域是同種型號(hào)的傳感器 S1S4的信號(hào)覆蓋范圍，e1e9是九個(gè)效力客戶(hù)，問(wèn)：設(shè)置傳感器的最正確方案是什么?4無(wú)妨將九個(gè)效力客戶(hù)視為“元素，而各傳感器的信號(hào)覆蓋范圍內(nèi)的元素客戶(hù)分別構(gòu)成集合：S1=e1，e2，e3，e4，e5S2=e3，e4，e5，e6，e7，e8S3=e2，e4，e5，e7，e8，e9S4=e1，e2，e3，e4，e8，e9那