平面分割的优化模型

严坤妹

(福建商业高等专科学校基础部，福建 福州 350012)

平面分割的优化模型

严坤妹

(福建商业高等专科学校基础部，福建 福州 350012)

如何建立实际问题的数学模型是很重要的。生活中经常要解决最优化问题。给出单目标优化和多目标优化问题的一般提法和相应的数学模型，对铺瓷砖问题和圆盘切割问题进行详细讨论，给出相应的数学模型，并用枚举法和MATLAB软件给出了具体结果。

优化模型；平面分割；正六边形；圆形；枚举法

1 优化问题的提法及数学模型

优化问题的一般提法是：在一定的要求下，在众多可供选择的方案中求出一个满足该要求的方案，使得某一个或某几个目标达到最优。通常将所提的要求称为约束条件，一般由一些给定的函数(不)等式所界定的区域来表达；目标则由某些数学式子表出，称为目标函数。只有一个目标函数的优化问题称为单目标优化问题；至少有两个目标函数的优化问题称为多目标优化问题。当考虑k(k≥2)个目标时，这类多目标优化问题可用数学模型描述为式(1)：

(1)

其中X=(x1,x2,…,xn),xi∈R是一个n维决策变量，gi(X)、hj(X)为给定的n元函数，F(X)是X的目标向量函数。gi(X)≤0称为不等式约束条件，hj(X)=0称为等式约束条件。在式(1)中，如果k=1，即目标函数F(X)=f(X)时，则这类单目标优化问题描述如下式(2)所示：

(2)

当一个数学模型满足以下条件时，相应的问题就是线性规划问题：

(1) 所有变量都是连续的；

(2) 目标函数只有一个；

(3) 约束条件和目标函数都是线性函数。

在实际生活中，很多问题都可以描述成线性规划问题，不属于线性规划问题的都称作非线性规划问题[1-2]。

2 蜂房的结构问题

为什么蜂房的表面是由一个个正六边形构成的，而不是其它的图形？这是个优化问题。设有一个边长为a米的正方形平面区域，选择什么样的图形可以铺满整个平面？如果只考虑铺设的图形是由最简单的一种图形组成，很显然图形可以是边长为正方形，也可以是等边三角形，或者为正六边形的网格，这三种图形可以做到边边相贴不留空隙[3]。给出具体的数学模型：假设用相同的图形分割平面，我们称这样的图形为基本单元。当基本单元是正n多边形时，要做到图形排列边边相贴不留空隙，则相邻的图形的顶点必须重合。对平面中的一个点A来说，A是各正多边形的一个顶点，设A的周围有m个正n多边形的顶点重合于此点。因为圆周角是360°，令f(m,n)表示A点为圆心、周围没有被正n多边形覆盖的圆心角，则可建立如下式(3)优化模型：

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

(3)

表1 可铺满平面的正多边形边数

进一步考虑，如果用笔画出面积相同的等边三角形、正方形和正六边形这三种正多边形网格，哪一种图形消耗的墨水最少？用数学的语言讲，这问题就是：这三种正多边形哪一种周长面积比最小或面积周长比最大？设L(n)表示正多边形的周长，g(n)表示正多边形的周长面积比，S表示面积，则建立如下(4)式模型：

(4)

通过计算可知：当面积S一定时，L(3)-4.6S,L(4)=4S,L(6)=3.7S,即g(3)=4.6,g(4)=4,g(6)=3.7。说明面积一定时，这三种正多边形中，正六边形的周长最小(或周长一定时，这三种正多边形中，正六边形的面积最大。)。因此，画出六边形网格比正方形和正三角形消耗的墨水少。如果推广到三维空间，可知以六边形为截面的管子比正方形和正三角形截面消耗更少的材料[4]，这也是蜂窝表面结构是正六边形的原因。

3 圆盘切割问题

某工厂要求从1米×1米的钢板切割直径为0.25米的圆盘,如何切割可使钢板的利用率最高?若圆盘直径改为0.1米又如何?

所谓“利用率最高”包含两个意思，一是切割出的圆盘数目最多；二是剩余的边角料最少。下面分两种方案考虑。

(1)第一种方案——切割的形状是圆形

如果从a米×b米的钢板直接切割出直径为r米的圆盘,则圆盘的个数与圆的排列位置有关。设每个圆的半径都相等，圆与圆之间相切。圆的排列方式如图1所示。

图1 圆的排列方式

每一列圆的个数为n1,每一行圆的个数为n2,用f1(n1,n2)表示切出的圆的总数，f2(n1,n2)表示剩余的边角料，则可建立数学模型如下式(5)所示：

maxf1(n1,n2)=n1n2

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

(5)

(2)第二种方案——切割的形状是正六边形

从蜂房结构的优化分析中，我们知道圆形是不能铺满整个平面的，而正六边形可以。因此这个问题可以转化为先考虑从a米×b米的钢板切割出正六边形，然后再考虑内切圆。

设正六边形的排列方式如图2所示。

图2 正六边形的排列方式

假设第一列可切出n1个正六边形，第二列可切出n1+1个正六边形，则各列的正六边形的个数遵循的规律就可知了。又设可切出的正六边形的列数为n2,用f1(n1,n2)表示切出的正六边形的总数，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)两种方案的结果比较

若用1米×1米的钢板切割直径为0.25米的圆盘和 0.1米的圆盘，上述两种方案切割出的圆盘总数及钢板利用率的计算结果如表2所示。

表2 两种切割方案结果比较

综上分析可知：用1米×1米的钢板切割圆盘，当圆盘直径为0.25米时，采用圆的排列方式切割圆盘，切出的圆盘总数多且钢板利用率较高；当圆盘的直径较小为0.1米时，采用正六边形排列方式的切割方法切出的圆盘总数多且钢板利用率较高。

[1]王立东.约束最小生成树算法的研究[D].西安：西安电子科技大学，2009.

[2]涂雪珠.遗传算法在多目标优化中的应用[D].福州：福州大学，2003.

[3]刘熙译.如何破解达芬奇密码[M].北京：人民邮电出版社，2012.

[4]任勇. 精彩数学就在身边[M].北京：中国人民大学出版社，2011.

(责任编辑：杨成平)

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

严坤妹(1966-)，女，福建莆田人，副教授，硕士。研究方向：应用数学教学及优化算法。

018

A

1008-4940(2015)02-0094-05