嚴(yán)坤妹

(福建商業(yè)高等?？茖W(xué)校基礎(chǔ)部，福建 福州 350012)

平面分割的優(yōu)化模型

嚴(yán)坤妹

(福建商業(yè)高等專科學(xué)?；A(chǔ)部，福建 福州 350012)

如何建立實際問題的數(shù)學(xué)模型是很重要的。生活中經(jīng)常要解決最優(yōu)化問題。給出單目標(biāo)優(yōu)化和多目標(biāo)優(yōu)化問題的一般提法和相應(yīng)的數(shù)學(xué)模型，對鋪瓷磚問題和圓盤切割問題進行詳細(xì)討論，給出相應(yīng)的數(shù)學(xué)模型，并用枚舉法和MATLAB軟件給出了具體結(jié)果。

優(yōu)化模型；平面分割；正六邊形；圓形；枚舉法

1 優(yōu)化問題的提法及數(shù)學(xué)模型

優(yōu)化問題的一般提法是：在一定的要求下，在眾多可供選擇的方案中求出一個滿足該要求的方案，使得某一個或某幾個目標(biāo)達到最優(yōu)。通常將所提的要求稱為約束條件，一般由一些給定的函數(shù)(不)等式所界定的區(qū)域來表達；目標(biāo)則由某些數(shù)學(xué)式子表出，稱為目標(biāo)函數(shù)。只有一個目標(biāo)函數(shù)的優(yōu)化問題稱為單目標(biāo)優(yōu)化問題；至少有兩個目標(biāo)函數(shù)的優(yōu)化問題稱為多目標(biāo)優(yōu)化問題。當(dāng)考慮k(k≥2)個目標(biāo)時，這類多目標(biāo)優(yōu)化問題可用數(shù)學(xué)模型描述為式(1)：

(1)

其中X=(x1,x2,…,xn),xi∈R是一個n維決策變量，gi(X)、hj(X)為給定的n元函數(shù)，F(xiàn)(X)是X的目標(biāo)向量函數(shù)。gi(X)≤0稱為不等式約束條件，hj(X)=0稱為等式約束條件。在式(1)中，如果k=1，即目標(biāo)函數(shù)F(X)=f(X)時，則這類單目標(biāo)優(yōu)化問題描述如下式(2)所示：

(2)

當(dāng)一個數(shù)學(xué)模型滿足以下條件時，相應(yīng)的問題就是線性規(guī)劃問題：

(1) 所有變量都是連續(xù)的；

(2) 目標(biāo)函數(shù)只有一個；

(3) 約束條件和目標(biāo)函數(shù)都是線性函數(shù)。

在實際生活中，很多問題都可以描述成線性規(guī)劃問題，不屬于線性規(guī)劃問題的都稱作非線性規(guī)劃問題[1-2]。

2 蜂房的結(jié)構(gòu)問題

為什么蜂房的表面是由一個個正六邊形構(gòu)成的，而不是其它的圖形？這是個優(yōu)化問題。設(shè)有一個邊長為a米的正方形平面區(qū)域，選擇什么樣的圖形可以鋪滿整個平面？如果只考慮鋪設(shè)的圖形是由最簡單的一種圖形組成，很顯然圖形可以是邊長為正方形，也可以是等邊三角形，或者為正六邊形的網(wǎng)格，這三種圖形可以做到邊邊相貼不留空隙[3]。給出具體的數(shù)學(xué)模型：假設(shè)用相同的圖形分割平面，我們稱這樣的圖形為基本單元。當(dāng)基本單元是正n多邊形時，要做到圖形排列邊邊相貼不留空隙，則相鄰的圖形的頂點必須重合。對平面中的一個點A來說，A是各正多邊形的一個頂點，設(shè)A的周圍有m個正n多邊形的頂點重合于此點。因為圓周角是360°，令f(m,n)表示A點為圓心、周圍沒有被正n多邊形覆蓋的圓心角，則可建立如下式(3)優(yōu)化模型：

minf(m,n)=360°-m×α

(3)

表1 可鋪滿平面的正多邊形邊數(shù)

進一步考慮，如果用筆畫出面積相同的等邊三角形、正方形和正六邊形這三種正多邊形網(wǎng)格，哪一種圖形消耗的墨水最少？用數(shù)學(xué)的語言講，這問題就是：這三種正多邊形哪一種周長面積比最小或面積周長比最大？設(shè)L(n)表示正多邊形的周長，g(n)表示正多邊形的周長面積比，S表示面積，則建立如下(4)式模型：

(4)

通過計算可知：當(dāng)面積S一定時，L(3)-4.6S,L(4)=4S,L(6)=3.7S,即g(3)=4.6,g(4)=4,g(6)=3.7。說明面積一定時，這三種正多邊形中，正六邊形的周長最小(或周長一定時，這三種正多邊形中，正六邊形的面積最大。)。因此，畫出六邊形網(wǎng)格比正方形和正三角形消耗的墨水少。如果推廣到三維空間，可知以六邊形為截面的管子比正方形和正三角形截面消耗更少的材料[4]，這也是蜂窩表面結(jié)構(gòu)是正六邊形的原因。

3 圓盤切割問題

某工廠要求從1米×1米的鋼板切割直徑為0.25米的圓盤,如何切割可使鋼板的利用率最高?若圓盤直徑改為0.1米又如何?

所謂“利用率最高”包含兩個意思，一是切割出的圓盤數(shù)目最多；二是剩余的邊角料最少。下面分兩種方案考慮。

(1)第一種方案——切割的形狀是圓形

如果從a米×b米的鋼板直接切割出直徑為r米的圓盤,則圓盤的個數(shù)與圓的排列位置有關(guān)。設(shè)每個圓的半徑都相等，圓與圓之間相切。圓的排列方式如圖1所示。

圖1 圓的排列方式

每一列圓的個數(shù)為n1,每一行圓的個數(shù)為n2,用f1(n1,n2)表示切出的圓的總數(shù)，f2(n1,n2)表示剩余的邊角料，則可建立數(shù)學(xué)模型如下式(5)所示：

maxf1(n1,n2)=n1n2

minf2(n1,n2)=ab-n1n2πr2

(5)

(2)第二種方案——切割的形狀是正六邊形

從蜂房結(jié)構(gòu)的優(yōu)化分析中，我們知道圓形是不能鋪滿整個平面的，而正六邊形可以。因此這個問題可以轉(zhuǎn)化為先考慮從a米×b米的鋼板切割出正六邊形，然后再考慮內(nèi)切圓。

設(shè)正六邊形的排列方式如圖2所示。

圖2 正六邊形的排列方式

假設(shè)第一列可切出n1個正六邊形，第二列可切出n1+1個正六邊形，則各列的正六邊形的個數(shù)遵循的規(guī)律就可知了。又設(shè)可切出的正六邊形的列數(shù)為n2,用f1(n1,n2)表示切出的正六邊形的總數(shù)，f2(n1,n2)表示剩余的邊角料，模型建立如下式(6)或(7)所示：

minf2(n1,n2)=ab-f1(n1,n2)πr2

(6)

或

maxf1(n1,n2)=

minf2(n1,n2)=ab-f1(n1,n2)πr2

(7)

模型求解：用枚舉法和MATLAB軟件求解。

(3)兩種方案的結(jié)果比較

若用1米×1米的鋼板切割直徑為0.25米的圓盤和 0.1米的圓盤，上述兩種方案切割出的圓盤總數(shù)及鋼板利用率的計算結(jié)果如表2所示。

表2 兩種切割方案結(jié)果比較

綜上分析可知：用1米×1米的鋼板切割圓盤，當(dāng)圓盤直徑為0.25米時，采用圓的排列方式切割圓盤，切出的圓盤總數(shù)多且鋼板利用率較高；當(dāng)圓盤的直徑較小為0.1米時，采用正六邊形排列方式的切割方法切出的圓盤總數(shù)多且鋼板利用率較高。

[1]王立東.約束最小生成樹算法的研究[D].西安：西安電子科技大學(xué)，2009.

[2]涂雪珠.遺傳算法在多目標(biāo)優(yōu)化中的應(yīng)用[D].福州：福州大學(xué)，2003.

[3]劉熙譯.如何破解達芬奇密碼[M].北京：人民郵電出版社，2012.

[4]任勇. 精彩數(shù)學(xué)就在身邊[M].北京：中國人民大學(xué)出版社，2011.

(責(zé)任編輯：楊成平)

Optimization Model for Plane Segmentation

YAN Kun-mei

(Foundation Department, Fujian Commercial College, Fuzhou 350012, China)

It’s very important to construct a mathematical model dealing with practical problem. In our life, we often need to solve optimization problems. This article gives general formulation and corresponding mathematical model to the single objective optimization and multi-objective optimization problem, discusses the tiling problem and disc cutting issue, constructs corresponding mathematical model, and finally uses enumeration method and MATLAB software to make a calculation.

optimization model; plane segmentation; hexagon; round; enumeration method

2015-03-11

嚴(yán)坤妹(1966-)，女，福建莆田人，副教授，碩士。研究方向：應(yīng)用數(shù)學(xué)教學(xué)及優(yōu)化算法。

018

A

1008-4940(2015)02-0094-05