ABSTRACT

Min-max problem model is a classical optimization model, as well as a way to solve multi objective programming, so it plays an important role in optimization method. By a simple example, min-max problem can be combined with multi objective programming and single objective programming, which would be useful for students to get an in-depth understanding of the content.

Keywords:Optimization Method, Min-Max Problem, Multi Objective Programming

最优化算法中极小极大问题的教学思考

金中

上海海事大学文理学院，上海

收稿日期：2019年9月26日；录用日期：2019年10月9日；发布日期：2019年10月16日

摘 要

极小极大问题模型既是一类优化模型，也是求解多目标优化的一种方法，在最优化算法中有着重要地位。在教学中，我们通过简单实例将极小极大问题、多目标优化和单目标优化三者有机结合在一起，对学生深入理解相关内容有积极作用。

关键词 :最优化算法，极小极大问题，多目标优化

Copyright © 2019 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

最优化算法是我校数学系数学与应用数学专业和信息与计算科学专业的一门专业课。这门课包括线性规划、非线性规划、多目标规划和现代智能算法等内容 [1] [2] 。在非线性规划中，极小极大问题是一类优化模型 [3] [4] ，它的目标函数一般形式为

$\underset{x}{\min }\underset{i}{\max }{f}_i\left(x\right)$ .

例如经典的Sylvester问题(第4页， [1] )，是求覆盖平面上m个点的最大圆盘。我们设这m个点为

$p_i\left(i=1,2,\cdots ,m\right)$ ，平面上任一点x到各点的距离则分别为 $\Vert x-p_i\Vert \left(i=1,2,\cdots ,m\right)$ 。若以 $f\left(x\right)$ 表示x到m个点 $p_i$ 的最大距离，即 $f\left(x\right)=\underset{1\le i\le m}{\max }\Vert x-p_i\Vert$ ，则以x为圆心，以 $f\left(x\right)$ 为半径的圆盘能覆盖这m个点。于

是问题转化求解

$\underset{x\in R^2}{\min }f\left(x\right)=\underset{x\in R^2}{\min }\underset{1\le i\le m}{\max }\Vert x-p_i\Vert$ ,

这是一个无约束的极小极大问题。

对于多目标规划 [5] ，在决策时采取稳妥的保守策略，即在最坏的情况下，寻求最好的结果。按照此

策略，可以构造评价函数 $\phi \left(z\right)=\underset{1\le i\le p}{\max }{z}_i$ ，然后求解

$\underset{x\in D}{\min }\phi \left[f\left(x\right)\right]=\underset{x\in D}{\min }\underset{1\le i\le p}{\max }{f}_i\left(x\right)$ .

极小极大问题涉及非线性规划和多目标规划两部分内容，对于学生来说，透彻理解该问题是非常有益的。问题本身相对抽象，直接套用Matlab优化工具箱中的fminimax命令却能直接得出结果，所以学这部分内容时容易囫囵吞枣，做不到融会贯通。因此在最优化算法教学中，非常有必要给出容易理解且印象深刻的极小极大问题，于是我们设计了如下的植树问题。

植树问题：某班有男同学30人，女同学20人，星期天准备去植树。根据经验，一天中，男同学平均每人挖坑20个，或栽树30棵，或给25棵树浇水，女同学平均每人挖坑10个，或栽树20棵，或给15棵树浇水。问应怎样安排，才能使植树(包括挖坑、栽树、浇水)最多？

2. 模型建立

2.1. 多目标规划模型

在该植树问题中，假设男同学中有 $x_1$ 人挖坑， $x_2$ 人栽树， $x_3$ 人浇水，女同学中有 $x_4$ 人挖坑， $x_5$ 人栽树， $x_6$ 人浇水。按照规则，挖坑、栽树和浇水三个步骤都完成才表示成功植树1棵，所以我们可以把每个步骤单独看成一个目标，即植树问题转化为一个三目标的多目标问题，目标函数是

$f\left(x\right)=\left(f_1\left(x\right),f_2\left(x\right),f_3\left(x\right)\right)$ ，其中第一个目标是挖坑

$f_1\left(x\right)=20x_1+10x_4$ ,

第二个目标是栽树

$f_2\left(x\right)=30x_2+20x_5$ ,

第三个目标是浇水

$f_3\left(x\right)=25x_3+15x_6$ ,

接着我们给出必须要满足的约束条件，包括男同学的人数约束

$x_1+x_2+x_3\le 30$ ,

女同学的人数约束

$x_4+x_5+x_6\le 20$ ,

其中 $x_1,x_2,x_3,x_4,x_5,x_6$ 都为整数。

我们希望这三个目标的每一个都是越大越好，这样才可以植树最多，并考虑到挖坑和栽树都要比浇水多，可得如下模型

模型一(多目标规划模型)

$\begin{array}{l}\max 20x_1+10x_4\\ \max 30x_2+20x_5\\ \max 25x_3+15x_6\end{array}$

$\begin{array}{l}\text{s}\text{.t}\text{.}25x_3+15x_6\le 20x_1+10x_4,\\ 25x_3+15x_6\le 30x_2+20x_5,\\ x_1+x_2+x_3\le 30,\\ x_4+x_5+x_6\le 20,\\ 其中x_1,x_2,x_3,x_4,x_5,x_6都为整数\end{array}$

2.2. 极小极大问题模型

在模型一中，原问题的答案(最多植树的数目)实际上等于第三个目标浇水的最大值，因为只要浇上水说明前面挖坑和栽树两个步骤已经完成了，那么树也植好了。在模型一约束条件中，我们考虑挖坑和栽树都要比浇水多，这表明三个目标之间是有联系，这时我们想到只要找到三个目标的最大值中的最小值，那么它就是满足挖坑、栽树和浇水三个步骤都完成的数量，从而原问题转化为求解如下的极小极大问题。

模型二(极小极大问题模型)

$\begin{array}{l}\min \underset{1\le i\le 3}{\max }{f}_i\left(x\right)\\ \text{s}\text{.t}\text{.}{x}_1+x_2+x_3\le 30,\\ x_4+x_5+x_6\le 20,\\ 其中x_1,x_2,x_3,x_4,x_5,x_6都为整数\end{array}$

3. 模型的求解

极小极大问题通常可以使用Matlab优化工具箱中的fminimax命令进行求解， 但是通过查阅Matlab帮助文档，fminimax命令能够解决的极小极大问题是有限制的，见图1。

模型二的约束条件含有整数约束，不属于fminimax能够求解的极小极大问题类型，所以此时fminimax命令无法使用。考虑到植树包括挖坑、栽树和浇水三个阶段，不妨给它们定一个共同的下界s，只要让s能取得最大值就能解决原问题。由于挖的坑、栽的树和浇的水都比s多，我们得到如下单目标优化问题。

图1. 能够使用fminimax求解的极小极大问题类型

模型三(单目标最大值问题模型)

$\begin{array}{l}\max s\\ \text{s}\text{.t}\text{.}20x_1+10x_4\ge s,\\ 30x_2+20x_5\ge s,\\ 25x_3+15x_6\ge s,\end{array}$

$\begin{array}{l}{x}_1+x_2+x_3\le 30,\\ x_4+x_5+x_6\le 20,\\ 其中x_1,x_2,x_3,x_4,x_5,x_6都为整数\end{array}$

我们使用Lingo软件编程见图2。

图2. 模型三的程序

得到结果见图3。

图3. 模型三的结果

我们得到的结果是最多种植345棵树，此时男同学中17人挖坑，1人栽树，12人浇水，女同学中1人挖坑，16人栽树，3人浇水。

4. 结果的验证和分析

4.1. 结果的验证

极小极大问题和极大极小问题是可以如下相互转化的

$\underset{x}{\min }\underset{i}{\max }{f}_i\left(x\right)=-\underset{x}{\max }\underset{i}{\min }\left(-f_i\left(x\right)\right)$ ,

我们将模型二改写成如下等价的极大极小问题

模型四(极大极小问题模型)

$\begin{array}{l}-\max \underset{1\le i\le 3}{\min }\left(-f_i\left(x\right)\right)\\ \text{s}\text{.t}\text{.}{x}_1+x_2+x_3\le 30\\ x_4+x_5+x_6\le 20\\ x_1,x_2,x_3,x_4,x_5,x_6都为整数\end{array}$

但是同样由于约束条件中有整数约束，Matlab优化工具箱中的fminimax命令无法使用，这里我们仍然可以考虑把这个极大极小问题转化为单目标优化问题。此时 $-s$ 是 $-f_1\left(x\right)$ ， $-f_2\left(x\right)$ 和 $-f_3\left(x\right)$ 的共同上界，可得如下单目标最小值优化问题。

模型五(单目标最小值问题模型)

$\begin{array}{l}-\min -s\\ \text{s}\text{.t}\text{.}-20x_1-10x_4\le -s,\\ -30x_2-20x_5\le -s,\\ -25x_3-15x_6\le -s,\end{array}$

$\begin{array}{l}{x}_1+x_2+x_3\le 30,\\ x_4+x_5+x_6\le 20,\\ 其中x_1,x_2,x_3,x_4,x_5,x_6都为整数\end{array}$

我们在实际编程中用的目标函数是 $\min -s$ ，使用Lingo软件编程见图4。

图4. 模型五的程序

得到结果见图5。

我们得到的结果是−345，它的相反数是345，从而最多种植345棵树。从计算结果看，男同学中有17人挖坑，有1人栽树，有12人浇水，女同学中有1人挖坑，有16人栽树，有3人浇水，这些和原结果都是相同的，原结果得到了验证。

图5. 模型五的结果

4.2. 结果的分析

我们可以分析出模型三和模型五结果相同的原因。一方面，从目标函数来看，有

$\max s=-\min -s$ ,

从而模型三和模型五的目标函数是等价的。另一方面，从约束条件来看，模型三和模型五只有前三个约束条件在形式上是不同的，我们把模型三中的前三个约束条件

$20x_1+10x_4\ge s$ , $30x_2+20x_5\ge s$ , $25x_3+15x_6\ge s$ ,

两边乘以负一之后，就变成了模型五中的前三个约束条件

$-20x_1-10x_4\le -s$ , $-30x_2-20x_5\le -s$ , $-25x_3-15x_6\le -s$ ,

所以模型三和模型五的约束条件是一样的。

由上分析可知，因为目标函数等价，约束条件相同，模型三和模型五的结果肯定是相同的。

5. 总结

本文通过实例给出相应的多目标规划问题模型和极小极大问题模型，该极小极大问题含有整数约束，无法简单地应用MATLAB优化工具箱命令进行求解。我们从问题的特点出发，将其转化成一个单目标最大值问题，使用Lingo软件编程求出结果。我们给出与原问题等价的极大极小问题，通过求解其转化成的单目标最小值问题，验证了原结果，并分析了原因。文中的例子简洁明了，学生容易理解。编程简单，能提高学生的学习兴趣。在解决问题的过程中，我们将极小极大问题、多目标优化和单目标优化三部分结合在一起，能给学生很好的启迪，可以解决学生学习极小极大问题无法融会贯通的问题。

基金项目

本文工作得到上海海事大学校精品课程建设项目和院重点课程建设项目(2018)资助。

文章引用

金 中. 最优化算法中极小极大问题的教学思考
Thoughts on Teaching Min-Max Problem in Optimization Method[J]. 创新教育研究, 2019, 07(05): 628-634. https://doi.org/10.12677/CES.2019.75107

参考文献