亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        基于動(dòng)態(tài)規(guī)劃的指派問題網(wǎng)絡(luò)方法及其應(yīng)用

        2020-12-05 09:04:24鮑培文
        懷化學(xué)院學(xué)報(bào) 2020年5期
        關(guān)鍵詞:指派分配動(dòng)態(tài)

        鮑培文

        (武警特警學(xué)院,北京昌平 102200)

        指派問題是運(yùn)籌學(xué)中的規(guī)劃問題,主要是運(yùn)用數(shù)學(xué)和現(xiàn)代計(jì)算機(jī)技術(shù)等科學(xué)技術(shù)方法,從數(shù)量方面揭示指派問題的模型、方法和應(yīng)用,為科學(xué)地進(jìn)行指派活動(dòng)、合理利用資源、提高指派效益提供理論和方法.針對(duì)指派問題具有網(wǎng)絡(luò)特征,設(shè)計(jì)基于動(dòng)態(tài)規(guī)劃的指派問題網(wǎng)絡(luò)方法,有利于綜合運(yùn)用網(wǎng)絡(luò)模型,解決指派問題.

        1 指派問題及其網(wǎng)絡(luò)方法

        指派問題既屬于資源優(yōu)化的線性規(guī)劃,又屬于多階段決策問題的動(dòng)態(tài)規(guī)劃.這也賦予指派問題的多種模型及求解方法,每一種模型和方法都有利于合理分配資源,提高有限資源的使用效益.

        1.1 標(biāo)準(zhǔn)指派問題的網(wǎng)絡(luò)化模型

        在日常管理工作中,往往會(huì)碰到這樣的人員分配問題:有 n項(xiàng)任務(wù)(或工作)A1,A2,…,An,需要給 n個(gè)人B1,B2,…,Bn去完成,每人只能執(zhí)行一項(xiàng)任務(wù).由于每個(gè)人完成每一項(xiàng)任務(wù)的時(shí)間(或效率)不盡相同,所以不同的分配方案完成任務(wù)的總時(shí)間(或總效率)也不同,要解決的問題是分配何人去完成何項(xiàng)任務(wù),才能使完成n項(xiàng)任務(wù)的時(shí)間最少(或總效率最高).

        任務(wù)分配與工作指派問題簡(jiǎn)稱為分配問題或指派問題(Assignment Problem).指派問題的條件是:每項(xiàng)工作只能分配給一個(gè)單位(人)去完成;每個(gè)單位(人)只能接受其中一項(xiàng)任務(wù).其中,工作數(shù)和單位數(shù)一致時(shí),稱為標(biāo)準(zhǔn)指派問題.非標(biāo)準(zhǔn)指派問題可以轉(zhuǎn)變?yōu)闃?biāo)準(zhǔn)指派問題[1]303-305.

        標(biāo)準(zhǔn)指派問題的數(shù)學(xué)模型:(xij為第i項(xiàng)工作派第j個(gè)單位完成,f為總費(fèi)用)

        標(biāo)準(zhǔn)指派問題有很多種解法.筆者在《指派問題的等價(jià)問題研究》[2]中,介紹了指派問題的各種解法.隨著網(wǎng)絡(luò)方法的普及,可建立基于動(dòng)態(tài)規(guī)劃的指派問題網(wǎng)絡(luò)化模型.即指派問題按任務(wù)劃分為n個(gè)階段,每一階段初始狀態(tài)xij,代表Ai到Bj保障小組的起始狀態(tài),規(guī)定x11=0,x(n+1)1=1,

        1.2 基于動(dòng)態(tài)規(guī)劃的指派問題網(wǎng)絡(luò)方法

        指派問題屬于動(dòng)態(tài)規(guī)劃問題的特例.基于動(dòng)態(tài)規(guī)劃的指派問題,通過動(dòng)態(tài)規(guī)劃的建模方法,借用標(biāo)號(hào)法求解最短路線思路,結(jié)合網(wǎng)絡(luò)方法進(jìn)行實(shí)例分析,進(jìn)一步拓展指派問題解法[3].

        網(wǎng)絡(luò)方法可以從廣義上和狹義上區(qū)分.廣義上的網(wǎng)絡(luò)方法,是把現(xiàn)代科學(xué)思想中網(wǎng)絡(luò)的觀點(diǎn)運(yùn)用到指派問題中,不局限于內(nèi)容.而狹義的網(wǎng)絡(luò)方法,是指依托計(jì)算機(jī)網(wǎng)絡(luò)和網(wǎng)絡(luò)技術(shù)進(jìn)行網(wǎng)絡(luò)化計(jì)算.指派問題網(wǎng)絡(luò)方法基于動(dòng)態(tài)規(guī)劃問題建立多階段動(dòng)態(tài)規(guī)劃模型,采用標(biāo)號(hào)法等方法,共同完成指派任務(wù)準(zhǔn)備、任務(wù)實(shí)施和任務(wù)總結(jié)的完整過程.

        1.3 標(biāo)準(zhǔn)指派問題網(wǎng)絡(luò)方法流程圖及算法

        標(biāo)準(zhǔn)指派問題網(wǎng)絡(luò)方法流程圖(圖1)從分析實(shí)際問題、列出時(shí)間矩陣開始,給出符合要求的可能分配方案,按照動(dòng)態(tài)規(guī)劃模型,使用網(wǎng)絡(luò)方法計(jì)算每一分配方案的費(fèi)用總值,尋找費(fèi)用最小值.

        圖1 指派問題網(wǎng)絡(luò)方法流程圖

        指派問題網(wǎng)絡(luò)方法lindo算法

        model:

        !n個(gè)工人,n個(gè)工作的分配問題;

        sets:

        workers/w1..wn/;

        jobs/j1..jn/;

        links(workers,jobs):cost,volume;

        endsets

        !目標(biāo)函數(shù);

        min=@sum(links:cost*volume);

        !每個(gè)工人只能有一份工作;

        @for(workers(I):

        @sum(jobs(J):volume(I,J))=1;

        );

        !每份工作只能有一個(gè)工人;

        @for(jobs(J):

        @sum(workers(I):volume(I,J))=1;

        );

        data:

        cost=a11a12……a1n

        a21a22……a2n

        ………………

        an1an2…… ann;

        enddata

        end

        2 基于動(dòng)態(tài)規(guī)劃指派問題網(wǎng)絡(luò)方法的應(yīng)用

        基于動(dòng)態(tài)規(guī)劃指派問題網(wǎng)絡(luò)方法,應(yīng)用廣泛而靈活.

        問題 某修理所組成A1,A2,A3,A4四個(gè)修理小組,對(duì)B1,B2,B3,B4四個(gè)單位實(shí)施技術(shù)保障,由于各組的技術(shù)專長(zhǎng)和設(shè)備不同,各單位的設(shè)備損壞程度不同,因此各組在各單位完成任務(wù)所需要的時(shí)間也不一樣.假定具體時(shí)間如表1所示.問哪一修理組完成哪一個(gè)單位的技術(shù)保障任務(wù),才能使總的時(shí)間最少.

        表1 修理組分配問題

        這是線性規(guī)劃的指派問題,建立指派問題模型:按任務(wù)劃分為四個(gè)階段,xij代表Ai到Bj保障小組的狀態(tài),規(guī)定xij=0,1狀態(tài)為1表示派去,為0表示不派去,f為總的時(shí)間.

        按照匈牙利法可以求出分配方案:A1到B1,A2到B3,A3到 B4,A4 到 B2.

        下面按任務(wù)劃分為四個(gè)階段,每一階段初始狀態(tài)xij,代表 Ai到 Bj保障小組的起始狀態(tài),規(guī)定 x11=0,x51=1,

        按照指派問題的模型、流程和算法,輸出符合要求的指派方案,如圖2和圖3.

        運(yùn)行 lindo,分配方案,A1到 B1,A2到 B3,A3到B4,A4到 B2.

        調(diào)用Python,結(jié)果如下:

        #-*-coding:utf-8-*-

        import numpyas np

        import copy

        c=[2,3,5,7,3,5,2,8,9,5,7,8,2,2,3,9

        ]

        c=np.array(c)

        c=c.reshape((4,4))

        all_p=[]

        class obj:

        def_init_(self):

        self.p=[]

        self.cost=0

        for i in range(4):

        for j in range(4):

        ifj==i:

        continue

        for u in range(4):

        ifu==i or u==j:

        continue

        for vin range(4):

        ifv==i or v==j or v==u:

        continue

        p=np.zeros((4,4))

        p[0,i]=p[1,j]=p[2,u]=p[3,v]=1

        ans=obj()

        ans.p=copy.deepcopy(p)

        ans.cost=sum(sum(c*ans.p))

        all_p.append(ans)

        all_p.sort(key=lambda ans:ans.cost,reverse=False)

        print(all_p[0].p)

        print(all_p[0].cost)

        圖2

        圖3

        Python 3.7.3(v3.7.3:ef4ec6ed12,Mar 25 2019,22:22:05)

        [MSCv.1916 64 bit(AMD64)]on win32

        Type“help”,“copyright”,“credits”or“l(fā)icense()”for more

        information.

        >>>

        RESTART:C:/Users/Administrator/AppData/Local/Programs/

        Python/Python37/33333333333.py

        [[1.0.0.0.]

        [0.0.1.0.]

        [0.0.0.1.]

        [0.1.0.0.]]

        14.0

        >>>

        3 基于動(dòng)態(tài)規(guī)劃指派問題網(wǎng)絡(luò)方法應(yīng)把握的問題

        基于動(dòng)態(tài)規(guī)劃指派問題網(wǎng)絡(luò)方法應(yīng)注重理論聯(lián)系實(shí)際,進(jìn)行網(wǎng)絡(luò)化分析,把握三對(duì)關(guān)系,提高決策優(yōu)化能力.

        3.1 整體與部分相統(tǒng)一.整體的各個(gè)部分是有機(jī)地、有組織地相互聯(lián)系、相互作用著的,這種組織性使得各個(gè)部分所不具有的新特征和屬性涌現(xiàn)出來;同時(shí),部分在成為整體的成員后,作為部分所獨(dú)有的特征和屬性也會(huì)受到整體的限制和束縛.這就要求指派問題運(yùn)用網(wǎng)絡(luò)方法時(shí),既為整體形成網(wǎng)絡(luò)留出鏈路接口,提供參考,又使部分和整體內(nèi)容相統(tǒng)一.

        3.2 建模與網(wǎng)絡(luò)方法相統(tǒng)一.指派問題網(wǎng)絡(luò)方法關(guān)鍵步驟是根據(jù)問題建立模型,需要掌握一定的量化分析方法.量化分析方法并非人人都能掌握,給問題求解帶來了難度.運(yùn)用網(wǎng)絡(luò)方法,可以突破難點(diǎn),化難為易,收到意想不到的效果.如基于動(dòng)態(tài)規(guī)劃指派問題,模型的建立不是很好理解,但效仿最短路線法,用網(wǎng)絡(luò)方法可以克服建模方法的困難,通過圖上求解,還能輔助建模方法的進(jìn)一步理解和掌握.

        3.3 趣味性和互動(dòng)性相統(tǒng)一.指派問題網(wǎng)絡(luò)方法是模型的另一種形式,既拓寬了鏈路,又增強(qiáng)了互動(dòng)性.在此網(wǎng)絡(luò)方法中,看似無序,通過建模逐漸自組織為有序,形成網(wǎng)絡(luò)結(jié)構(gòu)實(shí)現(xiàn)多個(gè)屬性、功能、行為,且具有相對(duì)的穩(wěn)定性;條件變化又會(huì)影響和破壞網(wǎng)絡(luò)的有序,就會(huì)進(jìn)入下一個(gè)無序自組織、自學(xué)習(xí),進(jìn)而又成為有序.指派問題網(wǎng)絡(luò)方法呈現(xiàn)網(wǎng)絡(luò)模型的適應(yīng)性、學(xué)習(xí)和自組織等特性,可以提高學(xué)習(xí)的興趣,增強(qiáng)互動(dòng)性.

        猜你喜歡
        指派分配動(dòng)態(tài)
        國(guó)內(nèi)動(dòng)態(tài)
        國(guó)內(nèi)動(dòng)態(tài)
        國(guó)內(nèi)動(dòng)態(tài)
        應(yīng)答器THR和TFFR分配及SIL等級(jí)探討
        動(dòng)態(tài)
        遺產(chǎn)的分配
        一種分配十分不均的財(cái)富
        績(jī)效考核分配的實(shí)踐與思考
        零元素行擴(kuò)展路徑算法求解線性指派問題
        具有直覺模糊信息的任務(wù)指派問題研究
        国产av乳头久久一区| 久久精品人人做人人爽电影蜜月 | 亚洲午夜精品国产一区二区三区| 国产三级黄色大片在线免费看| 免费a级毛片18禁网站app| 国产成人精品无码播放| 日韩精人妻无码一区二区三区| 国产一区二区中文字幕在线观看| 亚洲av中文无码乱人伦在线咪咕| 亚洲人成亚洲精品| 国产成社区在线视频观看| 久久99人妖视频国产| 夜夜爽妓女8888888视频| 最新四色米奇影视777在线看| 国产精品不卡无码AV在线播放| 中文字幕综合一区二区| 亚洲婷婷五月综合狠狠爱| 99视频一区| 国产91熟女高潮一曲区| 国产毛片av最新视频| 亚洲伊人成综合网| 99精品久久久中文字幕| 人妻少妇偷人精品视频| 亚洲av综合av国产av中文| 日本a级特黄特黄刺激大片| 国产喷白浆精品一区二区| 国产成人亚洲一区二区| 护士人妻hd中文字幕| 伊香蕉大综综综合久久| 亚洲一区二区三区福利久久蜜桃| 成人试看120秒体验区| 婷婷开心深爱五月天播播| 一区二区在线视频大片| 中文字幕乱码亚洲无限码| 欧美艳星nikki激情办公室| 国产成人av在线影院无毒| 色婷婷在线一区二区三区| 麻豆婷婷狠狠色18禁久久| 久久精品波多野结衣中文字幕| 日韩性感av一区二区三区| 午夜爽爽爽男女免费观看影院 |