• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      狀態(tài)離散的確定性多階段群體滿(mǎn)意決策最優(yōu)的算法

      2013-12-23 05:17:30張艷娟
      關(guān)鍵詞:群體決策列表賦權(quán)

      張艷娟

      (三峽大學(xué)理學(xué)院,湖北宜昌 443002)

      群體決策問(wèn)題是一類(lèi)受到普遍重視和研究的決策科學(xué)問(wèn)題,它廣泛應(yīng)用于社會(huì)政治經(jīng)濟(jì),生活各個(gè)領(lǐng)域.群體決策由兩個(gè)以上的決策者所構(gòu)成,是決策群體對(duì)一集備選方案進(jìn)行評(píng)價(jià)排序后選擇某方案使得群體效用最大的決策活動(dòng).有關(guān)群體決策問(wèn)題的研究已經(jīng)取得了豐富的研究成果.文獻(xiàn)[1]研究了一類(lèi)動(dòng)態(tài)多指標(biāo)決策問(wèn)題,應(yīng)用數(shù)學(xué)理論知識(shí)建立多目標(biāo)多階段動(dòng)態(tài)決策模型.通過(guò)引入一種效用函數(shù),并據(jù)此將具有不同量綱、不同物理含義、不同指標(biāo)類(lèi)型的決策矩陣歸一化轉(zhuǎn)換到相應(yīng)的效用矩陣,提高了分辨精度,物理概念更加清晰.文獻(xiàn)[2]針對(duì)狀態(tài)離散的確定性多階段群體決策問(wèn)題,建立多階段群體決策模型,通過(guò)引入偏好關(guān)系,得到了各階段的子過(guò)程群體滿(mǎn)意策略以及全過(guò)程群體滿(mǎn)意策略,提出了一種多階段群體決策問(wèn)題的逆向遞推算法.文獻(xiàn)[3]討論了多階段群體滿(mǎn)意決策問(wèn)題,提出了一種多階段群體滿(mǎn)意策略問(wèn)題的最優(yōu)算法,該算法的主要思想是應(yīng)用圖論知識(shí)將此問(wèn)題轉(zhuǎn)化為在多部有向賦權(quán)圖中求一條權(quán)和最長(zhǎng)的路.這些文章為群體決策問(wèn)題的研究提供了很多有用的方法和理論.

      本文將針對(duì)狀態(tài)離散的確定性多階段群體決策問(wèn)題,利用圖論的知識(shí),將群體決策問(wèn)題的多階段與圖的邊集、點(diǎn)集對(duì)應(yīng)起來(lái),建立群體決策問(wèn)題的模型一多部賦權(quán)圖,定義權(quán)w 為決策者對(duì)決策的評(píng)價(jià)值或效用值,路P 的長(zhǎng)度為P 中各邊的權(quán)和,將多階段群體滿(mǎn)意決策問(wèn)題轉(zhuǎn)換成在多部賦權(quán)圖中找一條最長(zhǎng)路徑的問(wèn)題.依據(jù)一條最長(zhǎng)路徑上的任意兩個(gè)不相鄰的頂點(diǎn)之間是不可以被由不在這一條路徑上的兩個(gè)頂點(diǎn)組成的更長(zhǎng)的路所替代這一事實(shí),提出了一種多部賦權(quán)圖最長(zhǎng)路徑的算法.

      1 多階段群體決策模型

      定義1 設(shè)G=(V(G),E(G),w(G))一個(gè)賦權(quán)圖,其中V(G)是頂點(diǎn)集,E(G)是邊集,w(G)是權(quán)集,如果G 滿(mǎn)足以下條件:

      對(duì)于在連通圖中尋找最長(zhǎng)路徑的問(wèn)題,國(guó)內(nèi)外許多學(xué)者已經(jīng)做了比較多的研究.文獻(xiàn)[4]介紹了一種比較簡(jiǎn)單通用的尋找近似最長(zhǎng)路徑的算法.文獻(xiàn)[5]討論了現(xiàn)有求解最長(zhǎng)路徑問(wèn)題的幾種算法,包括近似算法、參數(shù)化算法和特殊圖的多項(xiàng)式時(shí)間算法,著重分析和比較了參數(shù)化算法中利用著色、分治和代數(shù)法研究κ-Path問(wèn)題的最新結(jié)果,并提出了該問(wèn)題的進(jìn)一步研究方向.文獻(xiàn)[6]通過(guò)定義一種有向圖,提出了一種有向圖從始點(diǎn)到其它任一頂點(diǎn)之間最長(zhǎng)路的算法.文獻(xiàn)[7]研究了無(wú)向連通圖指定起點(diǎn)和終點(diǎn)的條件下,通過(guò)對(duì)深度優(yōu)先生成樹(shù)的某條路徑不斷地進(jìn)行頂點(diǎn)插入的策略來(lái)獲得一條近似最長(zhǎng)路徑.本文在總結(jié)和借鑒已有算法的基礎(chǔ)上,依據(jù)一條最長(zhǎng)路徑上的任意兩個(gè)不相鄰的頂點(diǎn)之間不可以被由不在這一條路徑上的兩個(gè)頂點(diǎn)組成的更長(zhǎng)路所替代這一事實(shí),提出了一種多部賦權(quán)圖中尋求最長(zhǎng)路徑的算法.

      2 算 法

      設(shè)P=x0x1…xN是多部賦權(quán)連通圖G 中連接點(diǎn)x0和xN的路,其中x0∈V0,x1∈V1,…,xN∈VN.設(shè)G1,G2,…,(Gm)(m≥0)為由不在路P 上的頂點(diǎn)組成的圖G 的連通子圖.

      定義3 路P 中的任意兩個(gè)不相鄰頂點(diǎn)xk和xt同時(shí)分別與任意一個(gè)連通子圖Gl中的頂點(diǎn)xp和xq(xp和xq為Gl中的點(diǎn))相連接.在P 中頂點(diǎn)xk和xl之間路P1的長(zhǎng)度為L(zhǎng)(P1),在Gl中頂點(diǎn)xp和xq之間最長(zhǎng)路P2的長(zhǎng)度為L(zhǎng)(P2),如果L(P2)+w(xk,xp)+w(xt+xq)<L(P1),即在路P 中任意不相鄰兩個(gè)頂點(diǎn)之間的路不可被由不在路P 上頂點(diǎn)組成的更長(zhǎng)路所代替,則稱(chēng)滿(mǎn)足這個(gè)條件的路為不可替代路.

      定理1 如果路P 上的任意兩個(gè)不相鄰的頂點(diǎn)之間的路均為不可替代路,則路P 就是最長(zhǎng)路徑.

      顯然,如果路P 不滿(mǎn)足上面的性質(zhì),則路P 不是最長(zhǎng)路徑.對(duì)于任意一條路P=x0x1…xN,設(shè)點(diǎn)xk和xt是路P 上任意兩個(gè)不相鄰的頂點(diǎn),連接點(diǎn)xk和xl之間路P1的長(zhǎng)度為L(zhǎng)(P1).Gl為某個(gè)由不在路P 上的頂點(diǎn)所構(gòu)成的圖G 的極大連通子圖,設(shè)xp和xq為Gl中的點(diǎn),且邊(xk,xp)∈E(G),(xt,xq)∈E(G).Gl中頂點(diǎn)xp和xq之間最長(zhǎng)路P2的長(zhǎng)度為L(zhǎng)(P2),如果L(P2)+w(xk,xp)+w(xt,xq)>L(P1),則在路P上用頂點(diǎn)xp和xq之間的路徑替代頂點(diǎn)xk+1和xt-1之間的路徑.因此在多部有向賦權(quán)圖中尋找最長(zhǎng)路徑問(wèn)題的關(guān)鍵是要尋找不可替代路.

      步驟4:若可被替代的點(diǎn)的列表為空,轉(zhuǎn)步驟8,否則取出可被替代的點(diǎn)的列表中的點(diǎn),完成一次操作以后,如果可被替代的點(diǎn)的列表中的點(diǎn)沒(méi)有被替代,將其保留.否則將其刪除.

      步驟5:若可替代的點(diǎn)列表為空,轉(zhuǎn)步驟8,否則遍歷可以替代的點(diǎn)的列表,查找可替代點(diǎn)列表中的點(diǎn),若找到可替代點(diǎn)列表中的點(diǎn),執(zhí)行步驟6,否則轉(zhuǎn)步驟4.

      步驟6:用可替代的點(diǎn)的列表中的點(diǎn)替代可被替代的點(diǎn)的列表中的點(diǎn),可以得到一條新的路徑,如果新路徑的長(zhǎng)度大于原來(lái)路徑的長(zhǎng)度,則可被替代的點(diǎn)的列表中的點(diǎn)將會(huì)被可替代的點(diǎn)的列表中的點(diǎn)所替代,執(zhí)行步驟7.否則可被替代的點(diǎn)的列表中的點(diǎn)將不會(huì)被替代,轉(zhuǎn)步驟4.

      步驟7:將替代到原來(lái)選取的路徑中的點(diǎn)加入到可被替代的點(diǎn)的列表中,返回步驟4,調(diào)整可被替代的點(diǎn)的列表.

      例:在圖1中,找一條從頂點(diǎn)x0到x4的長(zhǎng)度最長(zhǎng)的路徑.

      圖1 例圖

      3 算法應(yīng)用

      在群體決策問(wèn)題中,經(jīng)常要對(duì)狀態(tài)離散的確定性多階段決策的群體滿(mǎn)意策略做出判斷,下面的這個(gè)例子就是實(shí)際生活中會(huì)經(jīng)常遇到的.設(shè)由5個(gè)決策者構(gòu)成的決策群體共同參與一個(gè)包含4個(gè)決策階段的狀態(tài)離散的確定性動(dòng)態(tài)決策過(guò)程,多個(gè)決策者的權(quán)重在各個(gè)決策狀態(tài)下是不變的,即決策者的權(quán)重向量為(0.1,0.3,0.3,0.1,0.2),各階段的狀態(tài)轉(zhuǎn)移過(guò)程以及決策者對(duì)方案的評(píng)價(jià)值如圖2所示,求全過(guò)程的群體滿(mǎn)意策略.為了便于表述,將其策略用所經(jīng)過(guò)的多個(gè)狀態(tài)點(diǎn)來(lái)表示.

      圖2 狀態(tài)離散的確定性多階段決策的群體問(wèn)題的示例圖

      步驟1:建立狀態(tài)離散的確定性多階段決策的群體滿(mǎn)意決策問(wèn)題的模型,利用在多階段群體決策模型中計(jì)算權(quán)的方法詳細(xì)計(jì)算出圖2中每條邊的權(quán).比如w(x0,x)=3×0.1+3×0.3+4×0.3+7×0.1+9×0.2=4.9,依次計(jì)算出所有的權(quán).此時(shí)圖2就可以轉(zhuǎn)化成多部賦權(quán)圖,如圖3所示.

      圖3 多部賦權(quán)圖

      4 結(jié) 語(yǔ)

      近幾年來(lái),經(jīng)過(guò)研究者們的努力,最長(zhǎng)路徑問(wèn)題的研究取得了重大的進(jìn)展,大量的文獻(xiàn)都在研究該問(wèn)題的參數(shù)化算法.本文針對(duì)生活中常見(jiàn)的狀態(tài)離散的確定性多階段群體滿(mǎn)意策略問(wèn)題,應(yīng)用圖論的知識(shí)建立了多階段群體決策問(wèn)題的模型,并在此基礎(chǔ)上給出了算法,但是,由于該算法采用的是點(diǎn)逐步被替代的方式,因此計(jì)算量較大,有待進(jìn)一步改善.

      [1] 戴文站,鄒立華,王建章.一種基于獎(jiǎng)優(yōu)罰劣原則的多階段多目標(biāo)決策模型[J].系統(tǒng)工程理論與實(shí)踐,2000,6(1):32-36.

      [2] 彭 怡,胡 楊.狀態(tài)離散的確定性多階段群決策的滿(mǎn)意策略性[J].運(yùn)籌學(xué)學(xué)報(bào)案,2006,10(1):80-86.

      [3] 鄭文婷,劉紅美,余 真.多階段群體滿(mǎn)意決策最優(yōu)算法[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2008,38(16):44-48.

      [4] Karger D,Motwani R,Ramkmmar G D.On Approximating the Longest Path in a Graph[J].Algorithmica,1997,18(1):82-98.

      [5] 王建新,楊志彪,陳建二.最長(zhǎng)路徑研究問(wèn)題進(jìn)展[J].計(jì)算機(jī)科學(xué),2009,36(12):1-4,31.

      [6] 屈芝蓮.一種有向圖最長(zhǎng)路的算法、靈敏度分析及其應(yīng)用[J].科學(xué)技術(shù)與工程,2011,11(16):3746-3449.

      [7] 孫承山,何援軍,蔡鴻明.無(wú)向連通圖求約束條件下近似最長(zhǎng)路算法[J].計(jì)算機(jī)仿真,2004,21(7):45-47,81.

      猜你喜歡
      群體決策列表賦權(quán)
      巧用列表來(lái)推理
      論鄉(xiāng)村治理的有效賦權(quán)——以A縣扶貧項(xiàng)目為例
      學(xué)習(xí)運(yùn)用列表法
      企業(yè)數(shù)據(jù)賦權(quán)保護(hù)的反思與求解
      擴(kuò)列吧
      試論新媒體賦權(quán)
      活力(2019年15期)2019-09-25 07:22:12
      基于改進(jìn)AHP熵博弈賦權(quán)的輸變電工程評(píng)價(jià)
      財(cái)務(wù)管理案例教學(xué)課堂討論的組織方案設(shè)計(jì)思路
      群體決策中隱性社團(tuán)組織的識(shí)別
      淺談挑戰(zhàn)者號(hào)航天災(zāi)難中群體決策的分析與建議
      科技視界(2014年9期)2014-06-13 09:50:24
      井研县| 平遥县| 万年县| 呼图壁县| 行唐县| 台中市| 泗阳县| 丰台区| 大连市| 凤阳县| 鹿泉市| 千阳县| 珠海市| 晋宁县| 靖宇县| 招远市| 宁城县| 安岳县| 留坝县| 浦北县| 镶黄旗| 渝中区| 铜山县| 江油市| 枣庄市| 绵竹市| 康保县| 三江| 昌图县| 德州市| 广昌县| 乌鲁木齐县| 康平县| 中宁县| 临漳县| 德保县| 孟连| 黎川县| 水城县| 青海省| 仙游县|