亚洲免费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黄色在线观看| 亚洲精品中文字幕视频色| 好大好湿好硬顶到了好爽视频| 激情影院内射美女| 国产一区二区激情对白在线| 丰满人妻中文字幕乱码| 精品久久一品二品三品| 新婚人妻不戴套国产精品| 国产真实强被迫伦姧女在线观看| 亚洲av中文无码乱人伦下载| 天天躁日日躁狠狠很躁 | 亚洲国产一区久久yourpan| 日本在线一区二区三区视频| 日本美女中文字幕第一区| 国产亚洲精品久久久久5区| 亚洲一卡2卡3卡4卡5卡精品| 十八岁以下禁止观看黄下载链接| 国产成人av综合色| 日本久久久精品免费免费理论| 亚洲天堂一区av在线| 国产精品亚洲色婷婷99久久精品| 国产成人无码a区在线观看视频| 国产爆乳无码一区二区在线| 久久精品国产亚洲av高清蜜臀 | av网站国产主播在线| 免费一区二区高清不卡av| 欧美黑寡妇特a级做爰| 久久棈精品久久久久久噜噜| 亚洲精品黄网在线观看| 日本韩国三级aⅴ在线观看| 国产少妇露脸精品自拍网站| 人妻少妇偷人精品免费看| 性高湖久久久久久久久| 少妇无码av无码去区钱| 91麻豆精品激情在线观最新| 亚洲男人av天堂久久资源| 风流老熟女一区二区三区| 亚洲男女免费视频| 国产成人精品中文字幕| 日韩精品专区在线观看|