1701017990
1701017991
1701017992
1701017993
数学文化教程 [:1701013761]
1701017994
数学文化教程 第二节 数学最优化例谈
1701017995
1701017996
中学里学习的求函数极值方法，可以用来处理一些简单的优化问题。微积分给出了探求极值的一般方法，能解决大量的复杂的优化问题。然而，还有许多重要的极值优化问题，是用微积分方法无法解决的。这时，就需要数学家发挥他们的聪明才智，使用更多的数学工具来解决。
1701017997
1701017998
1.最短线问题
1701017999
1701018000
美国北卡罗来纳州中部有三所大学——北卡罗来纳州大学、北卡罗来纳大学和公爵大学，它们分布在一个正三角形的三个顶点上（边长假设为1单位）。正三角形内还有其他一些研究单位和公司，因而被称为“研究三角”。
1701018001
1701018002
三校之间有专用的电话网连接；电话公司则按照传统的“最小生成树”计费方法，对电话网进行收费。
1701018003
1701018004
贝尔研究所的克鲁斯克尔在1959年提出的最小生成树构造（避圈法），曾经一直是电话公司网络线路收费的算法依据。最小生成树构造方法如下：在n个点中，先连接最近的两个点，然后在余下的可能连线中选择最短且不与已有的连线构成圈的连接线；按此方法继续构造，直到有n-1条连接线为止。
1701018005
1701018006
显然，“研究三角”专用电话网的收费应按照图8.2.1，即2个单位的线路长度来收取。因为该图是正三角形的最小生成树。
1701018007
1701018008
然而有一天，北卡罗来纳州三所大学向电话公司提出申请，要求把它们的专用电话网延伸到“研究三角”的中心点。于是电话公司派人去实地勘察，发现中心点那里是一处无人居住的沼泽地。更令人难堪的是，公司发现：一旦那里联网之后，则按照更新后的最小生成树计算，专用电话网的收费反而会减少！
1701018009
1701018010
这是怎么回事呢？请看图8.2.2：正三角形的三顶点A，B，C分别与中心点O连接起来后，形成这四点图的最小生成树；其总长度是
1701018011
1701018012
1701018013
1701018014
1701018015
▲ 图8.2.1
1701018016
1701018017
1701018018
1701018019
1701018020
▲ 图8.2.2
1701018021
1701018022
1701018023
1701018024
1701018025
电话公司不得不向大学讨饶：中心点的电话网不要架设了，收费则从2单位减为 单位。北卡罗来纳州的三所大学不费力气，就让电话公司乖乖地减少了收费。
1701018026
1701018027
可是，电话公司却不放心，究竟还会出现怎样的“新招”，让电话线的收费标准进一步降低？也就是说，是否再也没有其他安排能使收费标准的“折扣”不会大于 比2？这是一个猜想。在提出来20年里都未得到证明，成为数学难题。1987年，我国青年数学家堵丁柱证明了这一猜想是正确的。
1701018028
1701018029
2.人事指派问题，0—1规划一例
1701018030
1701018031
工厂为了电工、图书管理员和木工这三个工作岗位，招聘到甲、乙、丙三人，他们的各科考试成绩及总分如下：
1701018032
1701018033
物理 语文 制图 总分
1701018034
1701018035
甲8 7 5 20
1701018036
1701018037
乙8 6 7 21
1701018038
1701018039
丙10 5 7 22