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

        ?

        圓排列包裝問題最優(yōu)解解析

        2013-03-03 05:26:38楊金勇宋海洲
        關(guān)鍵詞:矩形框華僑大學(xué)橫坐標(biāo)

        楊金勇,宋海洲

        (華僑大學(xué) 數(shù)學(xué)科學(xué)學(xué)院,福建 泉州362021)

        近年來,組合優(yōu)化問題引起越來越多的關(guān)注,如文獻(xiàn)[1]用混合遺傳算法求解0-1背包問題,文獻(xiàn)[2]用蟻群算法解決TSP問題,文獻(xiàn)[3-6]用回溯法、蟻群算法求解圓排列問題.目前,圓排列研究得最多的問題是如何求解最小長度,然而,在生產(chǎn)生活中也會(huì)遇到下面這種情況,生產(chǎn)統(tǒng)一大小的盒子,要求這種盒子能夠裝下以任何一種排列順序排進(jìn)該盒子的n個(gè)大小不全相等的圓,且盒子長度盡可能的小.本文把這種問題稱為圓排列包裝問題,并對此進(jìn)行研究.

        1 圓排列包裝問題的數(shù)學(xué)模型

        圓排列包裝問題描述為找一個(gè)矩形框,將n個(gè)大小不全相等的圓以任何一種排列順序排進(jìn)該矩形框后,都能保證這n個(gè)圓與矩形的底邊相切,且要求這種矩形框長度最小.

        下面給出一些集合和相關(guān)長度的定義.

        定義1 給定n個(gè)圓C1,…,Cn,其圓心的橫坐標(biāo)分別為x1,x2,…,xn,半徑分別為R1,R2,…,Rn,R1≤R2≤…≤Rn,且R1<Rn.定義下面4個(gè)的集合S,T,Q,P.

        1)S={w|(w=i1,i2,…,in)為1,…,n的n級排列}.

        2 圓排列包裝問題的最優(yōu)解的性質(zhì)

        定理1 模型(2)中的所有最優(yōu)解中必存在一個(gè)最優(yōu)解l,使得該最優(yōu)解對應(yīng)的圓排列的圓心的橫坐標(biāo)構(gòu)成的向量屬于L.

        圖1 圓排列Fig.1 Circle permutation

        綜上所述,假設(shè)不成立,故定理得證.

        3 模型的轉(zhuǎn)化及求解

        由定理1可知:集合T必存在模型(2)的一個(gè)最優(yōu)解l,使得對應(yīng)圓心的橫坐標(biāo)向量(xk1,xk2,…,xkn)∈T.因此,對模型(2)可進(jìn)一步轉(zhuǎn)化為

        對于模型(3),得到了如下主要結(jié)果.

        定理2l=(n,n-1,n-2,…,3,2,1)為模型(3)的一個(gè)最優(yōu)解.

        為了證明定理2,先求解下面的模型,即

        其中:a1≤a2≤…≤an,a1<an.

        對于模型(4),有如下定理.

        定理3l=(n,n-1,n-2,…,3,2,1)為模型(4)的一個(gè)最優(yōu)解.

        為了證明定理3,先給出一些引理及定義.

        易證如下3個(gè)引理成立:

        由命題2及命題3易知定理2成立.

        4 應(yīng)用舉例

        [1] 宋海洲,魏旭真.求解0-1背包問題的混合遺傳算法[J].華僑大學(xué)學(xué)報(bào):自然科學(xué)版,2006,27(1):17-19.

        [2] 徐強(qiáng),宋海洲,田朝薇.解TSP問題的蟻群算法及其收斂性分析[J].華僑大學(xué)學(xué)報(bào):自然科學(xué)版,2011,32(5):589-591.

        [3] 王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析[M].北京:電子工業(yè)出版社,2001:179-181.

        [4] 高尚,楊靖宇,吳曉俊,等.圓排列問題的蟻群模擬退火算法[J].系統(tǒng)工程理論與實(shí)踐,2004(8):102-106.

        [5] 章義剛,賈瑞玉,張燕平,等.快速蟻群算法求解圓排列問題[J].計(jì)算機(jī)技術(shù)與發(fā)展,2007,17(8):48-50.

        [6] 章義剛,王會(huì)穎.改進(jìn)蟻群算法求解圓排列問題[J].機(jī)電工程,2008,25(5):92-95.

        猜你喜歡
        矩形框華僑大學(xué)橫坐標(biāo)
        不可輕用的位似形坐標(biāo)規(guī)律
        例談二次函數(shù)的頂點(diǎn)橫坐標(biāo)x=-b/2a的簡單應(yīng)用
        “平面直角坐標(biāo)系”解題秘籍
        多模態(tài)卷積神經(jīng)網(wǎng)絡(luò)的物體抓取檢測
        一種汽車式起重機(jī)防傾翻方法的研究
        僑校雙子星:暨南大學(xué)VS華僑大學(xué)
        PowerPoint 2013圖片裁剪技巧兩則
        用坐標(biāo)關(guān)系判斷圖象變換
        基于可變矩形框的人群密度估計(jì)算法
        華僑大學(xué)香港校友會(huì)慶建國六十周年暨《祖國與我》聯(lián)歡晚會(huì)
        久久水蜜桃亚洲av无码精品麻豆 | 成h视频在线观看免费| 久久久99精品免费视频| 久久久无码精品亚洲日韩蜜臀浪潮 | 国产成人精品优优av| 国产av综合影院| 久草国产视频| 日本高清一区二区三区视频| 精品国产亚洲av高清日韩专区| 九一免费一区二区三区偷拍视频| 欧洲多毛裸体xxxxx| 日出水了特别黄的视频| 国产资源在线视频| 成人免费毛片在线播放| 麻豆国产精品一区二区三区| 日韩夜夜高潮夜夜爽无码| 中文成人无码精品久久久不卡| 97色偷偷色噜噜狠狠爱网站97| 97人妻蜜臀中文字幕| 亚洲第一页视频在线观看| 国产精品白丝久久av网站| 成人综合婷婷国产精品久久蜜臀| 久久久99精品成人片中文字幕| 好爽要高潮了在线观看| 男女射精视频在线观看网站| 成熟丰满熟妇av无码区| 国外精品视频在线观看免费| 国产精品久久久一本精品| 国产美女冒白浆视频免费| 亚洲av日韩一区二区| 无码欧美毛片一区二区三| 国产裸体歌舞一区二区| 亚洲av色香蕉一区二区蜜桃| 不卡视频在线观看网站| 中文字幕人妻伦伦| 欧美mv日韩mv国产网站| 成年女人片免费视频播放A| 永久免费观看的黄网站在线| 亚洲色精品三区二区一区 | aa日韩免费精品视频一| 国产成人精品优优av|