论文部分内容阅读
摘要：“组合最优化”是运筹学与管理学专业研究生的一门专业课程。组合最优化问题通俗易懂，并且在实际生活中有着广泛的应用背景。和大多数其他学科不同，研究组合最优化问题往往都是使用一些最基本的数学运算，然而问题的解决又体现了相当强的方法巧妙性。因此，不仅仅广大专业人士去研究组合最优化问题，更是吸引了很多非专业的数学爱好者去研究。本文主要介绍了笔者在“组合最优化”教学中的一些具体体会，以及一些常见的组合最优化问题和求解方法。
关键词：组合最优化；运筹学；最优算法；近似算法
作者简介：录岭法（1979-），男，河南郑州人，郑州大学数学系，讲师。（河南 郑州 450001）
基金项目：本文系国家自然科学基金项目NSFC（10901142）的研究成果。
中图分类号：G642.3 文献标识码：A 文章编号：1007-0079（2011）35-0118-02
什么是组合最优化？这一概念很多人可能都会感到比较陌生。也有一些人会立即想到很多报纸上经常报道说某某单位对很多人员的工作岗位进行了重新调整，经过重新组合调整后人们的工作效率有了较大幅度的提高。那这是不是组合最优化？这其实也是一种组合最优化。所谓组合最优化，一个比较通俗的定义是：从离散的、有限的可行解集合中，寻找一个最优的可行解，使得它满足给定的约束条件并使某个目标函数达到最大或者最小。在上述例子中，由于人员和工作岗位都是有限的，因此所有的分配方案就构成了一个有限的可行解集合。进一步，因为人员之间的工作能力是不相同的，每个工作岗位也必须分配给适合这个岗位的人，这就构成了相应的约束条件。而我们的目标是使人员的工作效率达到最高或者用最短的时间完成给定的任务。“组合最优化”是运筹学与管理学专业研究生的一门专业课程。为了让学生认真学习这门课程，我们必须尽可能使用一些简单的、有趣的例子来吸引学生的兴趣。在这方面，组合最优化问题有着得天独厚的优势，因为组合最优化问题一个最显著的特点就是它的趣味性非常强。绝大多数的组合最优化问题都是非常通俗易懂的，而且在实际中有着广泛的应用背景。不像其他的一些数学学科，需要很深的数学功底。解决这类问题又体现了相当强的方法巧妙性，因此吸引了很多专业和非专业的爱好者去研究。以下简单介绍一些常见的组合优化问题。
一、问题介绍
称次品问题：有一批物品和一架天平（有左右两个托盘以及足够多的砝码），已知物品中包含若干件次品，且次品的重量和正品不一样。怎么才能用最少的次数准确找出所有的次品。
最短路问题：某人要开车从A地到B地，中间需要途经若干个城市。假设相邻的两个城市之间都有至少一条道路，每条道路的距离是给定的，我们的问题是选择走哪条路线从A地到B地路程最短？
最大流问题：物流公司每天都要从A地到B地运送很多货物，中间需要途经若干个城市。假设相邻的两个城市之间都有至少一条道路，假设每条道路都有一个给定的运输容量。我们如何决定每条道路的实际运输数量能保证最多的货物顺利从A地到达B地。
背包问题：有一批物品，每件物品对应有一个体积和价值。假设有一个背包并且背包的容量是有限的。我们的问题是选择装哪些物品到背包里使得背包里的物品总体积不超过背包的容量并且它们的价值之和达到最大。
装箱问题：有一批物品，每件物品都有一个体积。假设有足够多容量相同的箱子，我们的问题是如何用最少的箱子装完所有的物品。
排序问题：有一批工件要在若干台机器上加工，每台机器一次只能加工一个工件，每个工件在任何时间至多只能在一台机器上加工。我们的问题是如何安排工件在机器上加工使得某一个给定的目标函数达到最小或者最大。
很容易看出，这些问题都和我们的生活息息相关，在实际生活中有着广泛的应用，也是我们当前急需解决的问题。
二、问题求解
如何求解一个给定的组合优化问题？尽管这类组合最优化非常通俗易懂，看起来并不难，但是实际解决起来并不容易。并且这类问题的解决方法有一个比较普遍的特点就是很难想到。解决这类问题需要有很强的跳跃式思维。我们举一个比较简单的例子来说明这一点。
例1：假设有一个天平和相应的砝码，有9摞盘子且每一摞中有9个盘子，其中有1摞盘子里面全是次品而其他8摞都是正品。已知每个次品比正品重，问如何使用给定的天平和砝码用最少的次数准确判断出哪1摞盘子都是次品？
看到这个例子，很多人就会想到，把任意2摞盘子分别放在天平的左右托盘上，如果不平衡，则较重的那1摞一定是次品；如果平衡，则2摞盘子都不是次品，我们可以排除这2摞，再任意选2摞来称；依次类推。很容易看出，在最坏的情形下，也就是前4次选择的8摞盘子中都没有次品，那最后1摞一定是次品。因此，这个方法最坏需要使用4次才能判断出哪1摞盘子是次品。
但是，4次是最优的么？还有更好的方法使用更少的次数么？我们的回答是有。方法如下：首先把9摞盘子任意分成三份，分别记为A、B、C，使得每份包含3摞盘子。然后，把A和B分别放在天平的左右托盘中，如果天平左右平衡，则次品一定在C中，否则的话，次品一定在比较重的托盘中。假设X（A、B、C中的某一个）是包含次品的那一份盘子，其中的3摞盘子分别记为D、E、F。再把D和E分别放在天平的左右托盘中，如果天平左右平衡，则次品一定是F，否则的话，次品一定在比较重的托盘中的那一摞。因此，上述方法使用2次就能准确判断出那1摞盘子都是次品。2次是最优的么？有没有更好的方法只使用1次就能准确判断出哪1摞盘子都是次品？我们不难发现这样的方法是不存在的。上述方法已经是最优的且最优的次数是2。
从上述例子我们可以发现，我们很难在较短的时间想到最好的方法最优的解决上述问题，然而这些最优的方法都是很容易看懂的。这有些像“脑筋急转弯”，想到就容易，想不到就很难。注意到组合优化问题都是非连续的，因此很难有一个比较有效的、普遍的方法解决所有的这一类问题，甚至是一些很相似的问题的解决方法也不通用的。这是组合优化问题的解决方法另一个比较普遍的特点。我们再看下面一个与上述例子相似的例子。
例2：假设有一个天平和相应的砝码，有9摞盘子且每一摞中有9个盘子，其中有1摞盘子里面全是次品而其他8摞都是正品。已知每个次品都比正品重且已知每个次品重量是110克，正品是100克，问如何使用给定的天平和砝码用最少的次数准确判断出那1摞盘子都是次品？
显然，例2与例1唯一的不同就是，在例2中知道每个正品和次品的重量。进一步，我们能看到，例1的方法对例2也是适用的，也就是说，使用例1的方法我们使用2次天平就能准确判断出哪1摞盘子都是次品。然而，对例2而言，2次是最少的么？例2新加的条件有没有用，还有没有更好的方法使用更少的次数？显然，0次是不可行的。那么，1次呢，可能么？很多人也许根本不相信一次就能准确称出那1摞盘子都是次品？其实我可以告诉大家答案。仅仅一次就足够了，方法如下：把9摞盘子任意摆好一个顺序，我们在第一摞盘子中取出1个盘子，在第2摞中取出2个盘子，依次类推，在第9摞中取出9个盘子。总共我们取出了1+2+…+9=45个盘子。我们把这45个盘子放在天平上称重量，显然如果都是正品，总重量为4500克，如果次品在第一摞中，则45个盘子中包含一个次品，重量比为4510克；如果次品在第2摞中，则45个盘子中包含2个次品，重量比为4520克；依次类推，如果次品在第9摞中，则45个盘子中包含9个次品，重量比为4590克。因此，根据所称的重量，我们一次就能准确判断出哪1摞盘子都是次品。
例1和例2都是本人参加小学奥数竞赛的题目。例2更是本人小学五年级时参加的小学数学五省联赛的最后一道大题。当时，笔者也做不出来，比赛后甚至找了一些大学生来做也做不出来。看了以上例子，你可能会发现，尽管例1和例2很相似，但是例2的方法对例1而言是不适用的；而尽管例1的方法对例2适用，然而显然不是最优的。这也说明不同的组合优化问题，即使相似，方法也是不通用的。
从上面例子我们可以看出，对组合最优化问题找出最优算法并不容易。甚至很多组合最优化问题都是NP-困难的（例如背包问题和装箱问题），我们几乎不可能找到好的方法最优地解决这些问题。这使得我们有时候不得不降低要求，不要追求最优解，转而寻找一个合适的“满意解”或者“近似解”。对一个最小化问题，如果一个算法对任何实例都输出一个近似解并且近似解的值小于或者等于最优解的k倍，我们称它是一个k-近似算法。以下我们简单介绍背包问题和装箱问题的两个近似算法。
背包问题的贪婪算法：
第一步：计算所有物品的单位体积价值，将所有物品按照从大到小排序。
第二步：从单位体积价值最大的物品开始，从前往后尽可能多的装物品到背包中，直到装不下为止。
第三步：计算第二步所得到物品的总价值，与所有物品的最大价值相比较。选取两者价值最大的。
装箱问题的FFD算法：
第一步：将所有物品按照体积从大到小排序。将第一件物品放入到第一个箱子中并将第一个箱子标号为1。
第二步：假设第j件物品被考虑，当前有k个箱子被开启。如果可能，把物品j放入标号最小的、能够装下物品j的箱子中。否则的话，开启一个新的箱子把物品j放入并将新开启的箱子标号为k+1。
第三步：如果所有的物品都被装入到箱子中，算法结束。
以上是背包问题和装箱问题比较经典的两个近似算法，第一个算法是背包问题的一个2-近似算法。而第二个算法是装箱问题的一个1.5-近似算法。并且这个算法是最好的，即不存在一个近似算法有更小的近似比。
三、结束语
“组合最优化”是运筹学与管理学专业研究生的一门专业课程。本文主要介绍了笔者在“组合最优化”教学中的一些具体体会，以及一些常见的组合最优化问题和求解方法。尽管几乎所有的组合最优化问题都是非常通俗易懂的，但是要解决这些问题并不容易的。解决这类问题需要较强的思维能力，尤其要打破常规，进行跳跃性思维。然而，大多数的组合最优化问题是NP-困难的，我们几乎不可能找到好的方法最优的解决这些问题。这使得我们有时候不得不降低需求，不要追求最优解，转而寻找一个合适的“满意解”。
参考文献：
[1]B.Korte,J.Vygen.Combinatorial Optimization:Theory and Algorithms,
Springer-Verlag Berlin Heideberg,2000.
[2]B.Korte,高彻.组合最优化(一)[J].运筹学杂志,1985,(1).
[3 B.Korte,高彻.组合最优化(二)[J].运筹学杂志,1985,(2).
[4]C.H Papadimitriou,K.Steiglitz.Combinatorial Optimization Algorithms and Complexity,Prentice-Hall,Inc.,Englewood Cliffs,New Jersey,1982.
[5]越民义.运筹学简介[J].运筹学学报,1982,(1).
（责任编辑：麻剑飞）
关键词：组合最优化；运筹学；最优算法；近似算法
作者简介：录岭法（1979-），男，河南郑州人，郑州大学数学系，讲师。（河南 郑州 450001）
基金项目：本文系国家自然科学基金项目NSFC（10901142）的研究成果。
中图分类号：G642.3 文献标识码：A 文章编号：1007-0079（2011）35-0118-02
什么是组合最优化？这一概念很多人可能都会感到比较陌生。也有一些人会立即想到很多报纸上经常报道说某某单位对很多人员的工作岗位进行了重新调整，经过重新组合调整后人们的工作效率有了较大幅度的提高。那这是不是组合最优化？这其实也是一种组合最优化。所谓组合最优化，一个比较通俗的定义是：从离散的、有限的可行解集合中，寻找一个最优的可行解，使得它满足给定的约束条件并使某个目标函数达到最大或者最小。在上述例子中，由于人员和工作岗位都是有限的，因此所有的分配方案就构成了一个有限的可行解集合。进一步，因为人员之间的工作能力是不相同的，每个工作岗位也必须分配给适合这个岗位的人，这就构成了相应的约束条件。而我们的目标是使人员的工作效率达到最高或者用最短的时间完成给定的任务。“组合最优化”是运筹学与管理学专业研究生的一门专业课程。为了让学生认真学习这门课程，我们必须尽可能使用一些简单的、有趣的例子来吸引学生的兴趣。在这方面，组合最优化问题有着得天独厚的优势，因为组合最优化问题一个最显著的特点就是它的趣味性非常强。绝大多数的组合最优化问题都是非常通俗易懂的，而且在实际中有着广泛的应用背景。不像其他的一些数学学科，需要很深的数学功底。解决这类问题又体现了相当强的方法巧妙性，因此吸引了很多专业和非专业的爱好者去研究。以下简单介绍一些常见的组合优化问题。
一、问题介绍
称次品问题：有一批物品和一架天平（有左右两个托盘以及足够多的砝码），已知物品中包含若干件次品，且次品的重量和正品不一样。怎么才能用最少的次数准确找出所有的次品。
最短路问题：某人要开车从A地到B地，中间需要途经若干个城市。假设相邻的两个城市之间都有至少一条道路，每条道路的距离是给定的，我们的问题是选择走哪条路线从A地到B地路程最短？
最大流问题：物流公司每天都要从A地到B地运送很多货物，中间需要途经若干个城市。假设相邻的两个城市之间都有至少一条道路，假设每条道路都有一个给定的运输容量。我们如何决定每条道路的实际运输数量能保证最多的货物顺利从A地到达B地。
背包问题：有一批物品，每件物品对应有一个体积和价值。假设有一个背包并且背包的容量是有限的。我们的问题是选择装哪些物品到背包里使得背包里的物品总体积不超过背包的容量并且它们的价值之和达到最大。
装箱问题：有一批物品，每件物品都有一个体积。假设有足够多容量相同的箱子，我们的问题是如何用最少的箱子装完所有的物品。
排序问题：有一批工件要在若干台机器上加工，每台机器一次只能加工一个工件，每个工件在任何时间至多只能在一台机器上加工。我们的问题是如何安排工件在机器上加工使得某一个给定的目标函数达到最小或者最大。
很容易看出，这些问题都和我们的生活息息相关，在实际生活中有着广泛的应用，也是我们当前急需解决的问题。
二、问题求解
如何求解一个给定的组合优化问题？尽管这类组合最优化非常通俗易懂，看起来并不难，但是实际解决起来并不容易。并且这类问题的解决方法有一个比较普遍的特点就是很难想到。解决这类问题需要有很强的跳跃式思维。我们举一个比较简单的例子来说明这一点。
例1：假设有一个天平和相应的砝码，有9摞盘子且每一摞中有9个盘子，其中有1摞盘子里面全是次品而其他8摞都是正品。已知每个次品比正品重，问如何使用给定的天平和砝码用最少的次数准确判断出哪1摞盘子都是次品？
看到这个例子，很多人就会想到，把任意2摞盘子分别放在天平的左右托盘上，如果不平衡，则较重的那1摞一定是次品；如果平衡，则2摞盘子都不是次品，我们可以排除这2摞，再任意选2摞来称；依次类推。很容易看出，在最坏的情形下，也就是前4次选择的8摞盘子中都没有次品，那最后1摞一定是次品。因此，这个方法最坏需要使用4次才能判断出哪1摞盘子是次品。
但是，4次是最优的么？还有更好的方法使用更少的次数么？我们的回答是有。方法如下：首先把9摞盘子任意分成三份，分别记为A、B、C，使得每份包含3摞盘子。然后，把A和B分别放在天平的左右托盘中，如果天平左右平衡，则次品一定在C中，否则的话，次品一定在比较重的托盘中。假设X（A、B、C中的某一个）是包含次品的那一份盘子，其中的3摞盘子分别记为D、E、F。再把D和E分别放在天平的左右托盘中，如果天平左右平衡，则次品一定是F，否则的话，次品一定在比较重的托盘中的那一摞。因此，上述方法使用2次就能准确判断出那1摞盘子都是次品。2次是最优的么？有没有更好的方法只使用1次就能准确判断出哪1摞盘子都是次品？我们不难发现这样的方法是不存在的。上述方法已经是最优的且最优的次数是2。
从上述例子我们可以发现，我们很难在较短的时间想到最好的方法最优的解决上述问题，然而这些最优的方法都是很容易看懂的。这有些像“脑筋急转弯”，想到就容易，想不到就很难。注意到组合优化问题都是非连续的，因此很难有一个比较有效的、普遍的方法解决所有的这一类问题，甚至是一些很相似的问题的解决方法也不通用的。这是组合优化问题的解决方法另一个比较普遍的特点。我们再看下面一个与上述例子相似的例子。
例2：假设有一个天平和相应的砝码，有9摞盘子且每一摞中有9个盘子，其中有1摞盘子里面全是次品而其他8摞都是正品。已知每个次品都比正品重且已知每个次品重量是110克，正品是100克，问如何使用给定的天平和砝码用最少的次数准确判断出那1摞盘子都是次品？
显然，例2与例1唯一的不同就是，在例2中知道每个正品和次品的重量。进一步，我们能看到，例1的方法对例2也是适用的，也就是说，使用例1的方法我们使用2次天平就能准确判断出哪1摞盘子都是次品。然而，对例2而言，2次是最少的么？例2新加的条件有没有用，还有没有更好的方法使用更少的次数？显然，0次是不可行的。那么，1次呢，可能么？很多人也许根本不相信一次就能准确称出那1摞盘子都是次品？其实我可以告诉大家答案。仅仅一次就足够了，方法如下：把9摞盘子任意摆好一个顺序，我们在第一摞盘子中取出1个盘子，在第2摞中取出2个盘子，依次类推，在第9摞中取出9个盘子。总共我们取出了1+2+…+9=45个盘子。我们把这45个盘子放在天平上称重量，显然如果都是正品，总重量为4500克，如果次品在第一摞中，则45个盘子中包含一个次品，重量比为4510克；如果次品在第2摞中，则45个盘子中包含2个次品，重量比为4520克；依次类推，如果次品在第9摞中，则45个盘子中包含9个次品，重量比为4590克。因此，根据所称的重量，我们一次就能准确判断出哪1摞盘子都是次品。
例1和例2都是本人参加小学奥数竞赛的题目。例2更是本人小学五年级时参加的小学数学五省联赛的最后一道大题。当时，笔者也做不出来，比赛后甚至找了一些大学生来做也做不出来。看了以上例子，你可能会发现，尽管例1和例2很相似，但是例2的方法对例1而言是不适用的；而尽管例1的方法对例2适用，然而显然不是最优的。这也说明不同的组合优化问题，即使相似，方法也是不通用的。
从上面例子我们可以看出，对组合最优化问题找出最优算法并不容易。甚至很多组合最优化问题都是NP-困难的（例如背包问题和装箱问题），我们几乎不可能找到好的方法最优地解决这些问题。这使得我们有时候不得不降低要求，不要追求最优解，转而寻找一个合适的“满意解”或者“近似解”。对一个最小化问题，如果一个算法对任何实例都输出一个近似解并且近似解的值小于或者等于最优解的k倍，我们称它是一个k-近似算法。以下我们简单介绍背包问题和装箱问题的两个近似算法。
背包问题的贪婪算法：
第一步：计算所有物品的单位体积价值，将所有物品按照从大到小排序。
第二步：从单位体积价值最大的物品开始，从前往后尽可能多的装物品到背包中，直到装不下为止。
第三步：计算第二步所得到物品的总价值，与所有物品的最大价值相比较。选取两者价值最大的。
装箱问题的FFD算法：
第一步：将所有物品按照体积从大到小排序。将第一件物品放入到第一个箱子中并将第一个箱子标号为1。
第二步：假设第j件物品被考虑，当前有k个箱子被开启。如果可能，把物品j放入标号最小的、能够装下物品j的箱子中。否则的话，开启一个新的箱子把物品j放入并将新开启的箱子标号为k+1。
第三步：如果所有的物品都被装入到箱子中，算法结束。
以上是背包问题和装箱问题比较经典的两个近似算法，第一个算法是背包问题的一个2-近似算法。而第二个算法是装箱问题的一个1.5-近似算法。并且这个算法是最好的，即不存在一个近似算法有更小的近似比。
三、结束语
“组合最优化”是运筹学与管理学专业研究生的一门专业课程。本文主要介绍了笔者在“组合最优化”教学中的一些具体体会，以及一些常见的组合最优化问题和求解方法。尽管几乎所有的组合最优化问题都是非常通俗易懂的，但是要解决这些问题并不容易的。解决这类问题需要较强的思维能力，尤其要打破常规，进行跳跃性思维。然而，大多数的组合最优化问题是NP-困难的，我们几乎不可能找到好的方法最优的解决这些问题。这使得我们有时候不得不降低需求，不要追求最优解，转而寻找一个合适的“满意解”。
参考文献：
[1]B.Korte,J.Vygen.Combinatorial Optimization:Theory and Algorithms,
Springer-Verlag Berlin Heideberg,2000.
[2]B.Korte,高彻.组合最优化(一)[J].运筹学杂志,1985,(1).
[3 B.Korte,高彻.组合最优化(二)[J].运筹学杂志,1985,(2).
[4]C.H Papadimitriou,K.Steiglitz.Combinatorial Optimization Algorithms and Complexity,Prentice-Hall,Inc.,Englewood Cliffs,New Jersey,1982.
[5]越民义.运筹学简介[J].运筹学学报,1982,(1).
（责任编辑：麻剑飞）