基于匈牙利算法的城市商業(yè)網(wǎng)點(diǎn)最優(yōu)布設(shè)問題研究

鄭少妹

摘 要：本文依據(jù)城市商業(yè)網(wǎng)點(diǎn)規(guī)劃理論，結(jié)合實(shí)例，基于匈牙利算法并利用WinQSB2.0軟件對(duì)城市商業(yè)網(wǎng)點(diǎn)最優(yōu)選擇問題進(jìn)行仿真模擬計(jì)算。本文的研究為解決城市商業(yè)網(wǎng)點(diǎn)選址問題提供了一種全新的科學(xué)計(jì)算方法，具有較為重要的理論和應(yīng)用價(jià)值。

關(guān)鍵詞：匈牙利算法；商業(yè)網(wǎng)點(diǎn)；模擬仿真；最優(yōu)選擇

一、引 言

從可持續(xù)發(fā)展的視角確定城市商業(yè)網(wǎng)點(diǎn)的規(guī)模與數(shù)量、空間分布和業(yè)態(tài)結(jié)構(gòu)，滿足消費(fèi)者需求，培育城市綜合競爭力，最終實(shí)現(xiàn)城市商貿(mào)經(jīng)濟(jì)可持續(xù)發(fā)展目標(biāo)。不同商業(yè)網(wǎng)點(diǎn)布局和組合決定了該區(qū)域商貿(mào)業(yè)的繁榮程度與可持續(xù)發(fā)展能力。基于城市商貿(mào)特色及內(nèi)涵，運(yùn)用匈牙利算法和WinQSB2.0軟件對(duì)城市商業(yè)網(wǎng)點(diǎn)最優(yōu)選擇問題進(jìn)行仿真模擬計(jì)算。本文的研究為解決城市商業(yè)網(wǎng)點(diǎn)選址問題提供了一種新的科學(xué)計(jì)算方法，具有重要的理論和應(yīng)用價(jià)值。

二、城市商業(yè)網(wǎng)點(diǎn)規(guī)劃理論概述

為充分體現(xiàn)“以人為本”理念，通過信息化，規(guī)?；l(fā)展，利用現(xiàn)代網(wǎng)絡(luò)技術(shù)對(duì)傳統(tǒng)行業(yè)加以改造，大幅度提升商業(yè)服務(wù)效率和質(zhì)量，改善商業(yè)生態(tài)環(huán)境，促進(jìn)商貿(mào)流通體系的發(fā)展。城市商業(yè)網(wǎng)點(diǎn)的空間布設(shè)，要求制定出符合城市發(fā)展的商業(yè)網(wǎng)點(diǎn)規(guī)劃，其城市商業(yè)網(wǎng)點(diǎn)規(guī)劃的主要理論基礎(chǔ)有：

（一）區(qū)位理論。 （1）市場競爭區(qū)位理論。市場競爭區(qū)位理論于1935年由瑞典經(jīng)濟(jì)學(xué)家帕蘭德提出。他從市場的角度來探討區(qū)位的形成與變化，發(fā)現(xiàn)人口的分布變化與新產(chǎn)品、新技術(shù)的引進(jìn)都可以打破原有的市場平衡，從而改變市場與產(chǎn)業(yè)的分布狀況。（2）貿(mào)易邊界理論。貿(mào)易邊界理論認(rèn)為，任何商業(yè)企業(yè)的競爭力主要取決于銷售量，取決于市場區(qū)域的大小與消費(fèi)者的數(shù)量。兩個(gè)企業(yè)的貿(mào)易邊界由雙方的價(jià)格和成本之比決定，成本或價(jià)格相同，貿(mào)易邊界在兩個(gè)企業(yè)的中央；成本或價(jià)格不同，市場邊界則偏向成本或價(jià)格高的一方。（3）中心地理論。中心地理論認(rèn)為，向周邊區(qū)域居住的消費(fèi)者所供應(yīng)物品和勞務(wù)的場所稱為中心點(diǎn)，而消費(fèi)者到中心點(diǎn)購買商品或服務(wù)的成本會(huì)隨離中心點(diǎn)的距離增大而增加。當(dāng)距離大到一定的程度，消費(fèi)者就會(huì)轉(zhuǎn)而向其他距離較近的中心點(diǎn)去購買，這個(gè)最大距離稱之為市場邊界。（4）市場區(qū)位理論。市場區(qū)位理認(rèn)為，市場完全是經(jīng)濟(jì)力量內(nèi)部作用的結(jié)果。因產(chǎn)品價(jià)格隨距離的增大而增加，而消費(fèi)者的購買規(guī)模與數(shù)量卻隨價(jià)格的增加而減少，直至到0。市場區(qū)位理論，使得土地的使用更高效與合理。

（二）商圈理論。商圈，指店鋪以其所在地點(diǎn)為中心，沿著相應(yīng)的方向和距離擴(kuò)展，即那些優(yōu)先選擇到本店來消費(fèi)的顧客分布的區(qū)域范圍。一個(gè)商業(yè)企業(yè)的服務(wù)空間范圍具有一定限度，才使得在該商業(yè)企業(yè)周邊存在一個(gè)以其為中心的區(qū)域，該中心區(qū)域在零售學(xué)中，就被稱之為商圈?？茖W(xué)預(yù)測(cè)未來商圈范圍的變化，對(duì)商業(yè)網(wǎng)點(diǎn)布設(shè)規(guī)劃工作有著重要的作用。

（三）集聚效益理論。俗語：店多成市。通過商店集聚、客流集聚以及各種經(jīng)濟(jì)活動(dòng)的集聚，從而產(chǎn)生集聚經(jīng)濟(jì)效益。在商業(yè)網(wǎng)點(diǎn)規(guī)劃方面，集聚經(jīng)濟(jì)效益其具體表現(xiàn)為：服務(wù)或商店設(shè)施的集聚；人流與客流的集聚可以產(chǎn)生市場規(guī)模效應(yīng)；集聚可以促進(jìn)商店的專業(yè)化分工而提高經(jīng)營效率；集聚可以提供更加廣泛全面的輔助設(shè)施以及公共服務(wù)設(shè)施的完善；集聚也可激發(fā)有才能的企業(yè)家集聚等，從而產(chǎn)生吸引與輻射效應(yīng)等。當(dāng)然，集聚形態(tài)與地理位置的不同組合，則會(huì)形成不同的城市商業(yè)布局形態(tài)。

（四）級(jí)差地租理論。級(jí)差地租理論的基本要點(diǎn)：按城市土地級(jí)差地租的級(jí)別，商業(yè)布局分為城市中心區(qū)、社區(qū)和街區(qū)等若干等級(jí)。任何一個(gè)商業(yè)中心的核心區(qū)，總會(huì)被那些足以顯示該商業(yè)中心最高等級(jí)的職能部門所占領(lǐng)。級(jí)差地租理論是通過商業(yè)房屋與市場土地的供需關(guān)系，即房租價(jià)格或土地價(jià)格的信號(hào)，推動(dòng)商業(yè)布局的合理調(diào)整。

（五）提升生活價(jià)值與和諧理論。隨著社會(huì)進(jìn)步與經(jīng)濟(jì)發(fā)展，現(xiàn)代商業(yè)規(guī)劃應(yīng)包括城市功能、城市文化、城市歷史和城市建筑風(fēng)格等方面的內(nèi)在和諧性。消費(fèi)者不僅滿足于物品的消費(fèi)，而更多是關(guān)注對(duì)生活價(jià)值的體驗(yàn)，因此，就要求商業(yè)規(guī)劃應(yīng)滿足多方面的和諧，如服務(wù)功能與多元化需求的和諧；消費(fèi)者偏好與商業(yè)企業(yè)經(jīng)營特色的和諧；等級(jí)體系與城市商業(yè)網(wǎng)絡(luò)的和諧；地區(qū)文化與個(gè)性化建筑的和諧等，從而給消費(fèi)者提供更加優(yōu)質(zhì)的綜合服務(wù)。

三、匈牙利算法概述

（一） “指派問題”的數(shù)學(xué)模型：指派問題（assignment prob

lem）標(biāo)準(zhǔn)形式是：有個(gè)人和項(xiàng)工作，已知第個(gè)人做第項(xiàng)工作的費(fèi)用為cij，i，j=1，2，…，n（cij可表示為成本、時(shí)間等），要求人與工作之間是一一對(duì)應(yīng)的指派關(guān)系，使完成項(xiàng)工作總費(fèi)用最少。

約束條件（1）表示每項(xiàng)工作必有且只有一個(gè)人去完成，約束條件（2）表示每個(gè)人必須完成且只須完成一項(xiàng)工作。

指派問題的可行解可用矩陣表示：

解矩陣的每行每列元素中都有且只有一個(gè)1，以滿足約束條件。指派問題有個(gè)可行解。

從上述數(shù)學(xué)模型可知，指派問題是0-1整數(shù)規(guī)劃的特殊情況，也是運(yùn)輸問題的特例，當(dāng)然更是一個(gè)整數(shù)規(guī)劃問題，因此指派問題可以用分枝定界法、表上作業(yè)法和隱枚舉法求解。然而我們根據(jù)指派問題數(shù)學(xué)模型特點(diǎn)，尋找更加簡便的計(jì)算方法，從而有效地減少計(jì)算量。1955年庫恩（W.W.Kuhn）利用匈牙利數(shù)學(xué)家康尼格（D.k？nig）的關(guān)于矩陣中獨(dú)立零元素的定理，提出了求解指派問題的匈牙利算法（Hungary algorithm）。

（二）匈牙利算法（Hungary algorithm）設(shè)計(jì)如下： （1）先對(duì)各行元素分別減去本行的最小元素，然后對(duì)各列也如此。此時(shí)，

中各行和各列都已出現(xiàn)元素，且沒有負(fù)數(shù)。（2）確定

中的獨(dú)立元素。（3）此時(shí)，需要確定能覆蓋所有元素的最少直線數(shù)目的直線集合?？砂聪旅娌襟E進(jìn)行： ① 對(duì)沒有○0的行打“√”； ② 在已打“√”的行中，對(duì)所在列打“√”； ③ 在已打“√”的列中；對(duì)○0所在行打“√”； ④ 重復(fù)②和③，直到再也不能找到可以打“√”的行或列為止； ⑤ 對(duì)沒有打“√”的行畫一橫線，對(duì)打“√”的列畫一垂線，這樣就得到了覆蓋所有零元素的最少直線數(shù)目的直線集合。（4）在未被直線覆蓋的元素中找出一個(gè)最小元素，對(duì)未被覆蓋元素所在行中各元素都減去這一最小元素，這樣勢(shì)必會(huì)出現(xiàn)元素，但同時(shí)卻又使已被直線覆蓋的元素中出現(xiàn)負(fù)數(shù)，為了消除這些負(fù)數(shù)，只要對(duì)劃了線的列的各元素都加上這一最小元素即可。 （5）返回步驟（2）確定中的獨(dú)立元素，故可確定指派問題的最優(yōu)指派方案。

四、算法應(yīng)用與模擬仿真

本文將采用WinQSB2.0專用軟件基于匈牙利算法對(duì)城市商業(yè)網(wǎng)點(diǎn)最優(yōu)選擇問題進(jìn)行仿真模擬。

通過一系列評(píng)估，家具超市不能置于第三個(gè)網(wǎng)點(diǎn)，而計(jì)算機(jī)超市不能置于第四個(gè)網(wǎng)點(diǎn)，不同類別的商品投資到各商業(yè)網(wǎng)點(diǎn)的年利潤（萬元）預(yù)測(cè)值如下表1。該商業(yè)集團(tuán)在該城市如何對(duì)商業(yè)網(wǎng)點(diǎn)做出最優(yōu)選擇才能使其年利潤最大。

求解與模擬仿真步驟如下：

（1）輸入數(shù)據(jù)。在選擇數(shù)據(jù)輸入格式時(shí)，選擇Spreadsheet

Matrix Form則以電子表格形式輸入價(jià)值系數(shù)矩陣，并點(diǎn)擊菜單欄Edit→Node Names對(duì)目標(biāo)和配置進(jìn)行重命名如下圖1所示：

2）選擇Solve the Problem（只求出最優(yōu)解）。如下圖2所示：

（3）點(diǎn)擊菜單欄Results→Graphic Solution，以網(wǎng)絡(luò)圖的形式顯示結(jié)果。如下圖3所示：

（4）最優(yōu)決策方案。從求解結(jié)果可得，最優(yōu)選擇方案為：計(jì)算機(jī)超市設(shè)在地點(diǎn)1、服裝超市設(shè)在地點(diǎn)2、食品超市設(shè)在地點(diǎn)3、電器超市設(shè)在地點(diǎn)4， 最大年利潤為1350.00萬元。

結(jié)束語：本文利用城市商業(yè)網(wǎng)點(diǎn)規(guī)劃理論，通過實(shí)例，基于匈牙利算法并結(jié)合WinQSB2.0軟件對(duì)城市商業(yè)網(wǎng)點(diǎn)最優(yōu)選擇的問題進(jìn)行仿真模擬計(jì)算。為城市商業(yè)網(wǎng)點(diǎn)的布設(shè)問題提供了一種新的科學(xué)計(jì)算方法。然而，需要闡明的是，基于城市商業(yè)網(wǎng)點(diǎn)的布設(shè)問題的復(fù)雜性、不確定性以及人們認(rèn)識(shí)能力的局限性。所以，城市商業(yè)網(wǎng)點(diǎn)布設(shè)問題的研究是一項(xiàng)復(fù)雜的系統(tǒng)工程，無論在理論上還是在方法技術(shù)等方面仍然需要展開系統(tǒng)的深入思考。

參考文獻(xiàn)：

[1]劉星原.城市商業(yè)網(wǎng)點(diǎn)規(guī)劃布局的若干問題探討[J].北京工商大學(xué)學(xué)報(bào)，2007（04）：6-10

[2]李萍.城市商業(yè)網(wǎng)點(diǎn)規(guī)劃理論框架的構(gòu)建[J].現(xiàn)代商貿(mào)工業(yè)，2007（08）：39-40