下载掌阅APP，畅读海量书库
立即打开
最优化问题形式多样。例如，车间生产中总希望在尽可能少的人力、物力条件下获得生产效益最大化，或是在达到某一预定目标的前提下使投入成本最低；公交公司要尽可能扩大城市公交线网，又要使线路间的站点重复率降到最低；大型超市需要根据货物的销售情况来合理安排进货周期及数量，从而在满足销售需求的同时，尽可能减少库存积压，获取最大销售利润，等等。
最优化方法是一个重要的数学分支，为解决最优化问题提供所需的理论基础和求解方法，它是一门实用性很强的学科，不仅广泛应用于众多领域，同时还产生了巨大经济效益和社会效益。实践证明，通过优化能够合理地利用资源、提高效率、降低能耗。因此，对最优化问题的研究具有十分重要的意义。
对于实际问题的优化，需要先建立问题的最优化模型，把实际问题抽象为具体的数学模型来表达。最优化模型就是在一组给定的约束条件下，确定可控变量的取值，以使结果达到最优值。因此，可控变量、约束条件和目标函数是优化模型的重要组成要素。
由于最优化问题的类型较多，根据不同的分类依据有不同的分类方法。例如，按优化问题性质，可分为确定性优化问题和随机优化问题；按优化问题变量的性质，可分为连续优化问题和离散优化问题；按优化目标与变量的函数关系，可分为线性优化问题和非线性优化问题；按优化问题有无约束条件，可分为无约束优化问题和约束优化问题；按待优化变量的个数，可分为单变量最优化问题和多变量最优化问题；按待优化目标的个数，可分为单目标最优化问题和多目标最优化问题；按优化变量的取值随时间或其他因素有无变化，可分为静态最优化问题和动态最优化问题；等等。
单变量最优化问题又称为极大-极小化问题，在科学及工程领域非常常见。单变量最优化问题的求解一般按照提出问题、选择建模方法、推导模型的数学表达式、求解模型和回答问题五个步骤来进行。
问题1 出售时间问题。某加工厂需要加工一批产品，这批产品现有数目200个，每天生产的产品数目是5个，而每天生产产品的花费是40元，每个产品的市场价格为60元，但每天下降1元，求出售这批产品的最佳时间。
（1）提出问题：对所求问题提出相关假设，归纳整理出涉及的变量和常量，包括恰当的单位，找出不同量之间的数学关系表达式，界定某些量的取值范围。出售时间问题中涉及变量的符号及其关系如表1-1所示。
表1-1 出售时间问题中涉及变量的符号及其关系
（2）选择建模方法：如何运用数学方法来获得解。出售时间问题可视为一个单目标最大值优化问题，这类问题在一元微积分中有如下相关的定理：设函数 f （ x ）是定义在实数子集 S 上的实值函数，若 f （ x ）在 S 的某个内点处取得极值，且在该点可微，则在极值点处有 f ′（ x 0 ）=0。在实际应用中，求解一元函数的最大值或最小值时需要综合考虑函数在极值点、边界点和不可微点的取值情况。
（3）推导模型的数学表达式。根据表1-1中变量之间的关系，在出售时间问题中获得的利润为
Z = R-C = nP -40 t =（60 -t ）（200+5 t ）-40 t
在此，令 x = t 为决策变量， f （ x ）= Z 为目标函数，即可将出售时间问题转换为在定义域 S ={ x ： x ≥0}上求函数 f （ x ）的最大值问题。模型的数学表达式为
因此，获得的利润与出售时间之间的关系如图1-1所示。
图1-1 获得的利润与出售时间之间的关系
（4）求解模型。在区间 x ∈[0，∞）上， f （ x ）存在唯一的最大值，其导函数为 f ′（ x ）=-10 x +60，令 f ′（ x ）=0，求得 x =6时， f （ x ）取得理论最大值为12180。如果将式（1-1）改写为
f （ x ）=-5（ x -6） 2 +12180
令 x =6时，也可得到求解结果。
（5）回答问题。通过以上分析可见，在第6天之后出售这批产品获得的利润最大。
在多变量最优化问题中，随着变量个数的增加，往往会导致最优化的区域形状变得较为复杂，进而使求解过程的难度增加。
问题2 生产数量问题。某厂计划生产出售两种型号的钢笔，甲种型号钢笔生产成本为每支2元，厂家建议市场零售价为每支10元；乙种型号钢笔生产成本为每支3元，厂家建议市场零售价为每支9元。此外，生产和出售这两种型号的钢笔还需要投入400元的固定成本。假设生产的钢笔可以全部出售，但在激烈的市场竞争中，每年出售钢笔的数量会对产品的售价有一定影响。由数据分析可知：这两种型号的钢笔每出售1支，自身售价就会下降0.03元，而且其中一种型号钢笔的销量也会对另一种型号钢笔的售价产生影响。甲种钢笔每出售1支，乙种钢笔便会下降0.004元，而乙种钢笔每出售1支，甲种钢笔就会下降0.006元。为获得最大的市场利润，每种型号的钢笔各应生产多少支？
（1）提出问题。对所求问题提出相关假设，归纳整理涉及的变量和常量，找出不同量之间的数学关系表达式，界定某些量的取值范围。生产数量问题中涉及变量的符号及其关系如表1-2所示。
表1-2 生产数量问题中波及变量的符号及其关系
（2）选择建模方法。生产数量问题可以看作一个多变量优化问题，这类问题在多元微积分中有如下相关的定理：设函数 f （ x 1 ， x 2 ，…， x n ）是定义在 n 维空间 R n 子集 S 上的实值函数，若 f （ x 1 ， x 2 ，…， x n ）在 S 的某个内点上取得极值，且 f （ x 1 ， x 2 ，…， x n ）在该点可微，则在极值点处有
利用式（1-2）可以得到 n 个方程的联立方程组，只要解出相应的未知数，就可以求出极大值或极小值。在实际应用中，求解多元函数的最大值或最小值时同样需要综合考虑函数在极值点、边界点和不可微点的取值情况。
（3）推导模型的数学表达式。根据表1-2所示变量之间的关系，获得利润为
Z = R-C = sW + tP -（2 s +3 t +400）
=-0.03 s 2 -0.03 t 2 -0.01 st +8 s +6 t -400
在此，令 x 1 = s ， x 2 = t 为决策变量， f （ x 1 ， x 2 ）= Z 为目标函数，即可将钢笔生产数量问题转换为在定义域 S ={（ x 1 ， x 2 ）： x 1 ≥0， x 2 ≥0}上求 f （ x 1 ， x 2 ）的最大值问题。模型的数学表达式为
因此，获得的利润与生产数量之间的关系如图1-2所示。
图1-2 获得的利润与生产数量之间的关系
（4）求解模型。对 f （ x 1 ， x 2 ）求偏导数，并令其取值为0，得到下列方程组
求解可得
该点为 f （ x 1 ， x 2 ）在区域 S 上的最大值点。
根据实际情况，需要对决策变量进行取整处理，当 x 1 =120、 x 2 =80时，代入式（1-3），得到最大利润为320元。
（5）回答问题。由上述分析结果可知，该生产厂家如果生产甲种型号钢笔120支、乙种型号钢笔80支，生产成本为880元，销售收入为1200元，可以获得最大利润为320元，利润率为36.36%。
上述两种问题优化方法对问题的描述有严格要求，如要求目标函数有明确的解析式，甚至是连续可微的。但现实中许多优化问题非常复杂，至今没有有效的多项式时间解法。如果用传统的优化方法求解，需要的计算时间与问题的规模通常呈指数关系，这使得传统优化方法在处理复杂问题求解上往往显得无能为力。
某人想利用假期在4个城市自驾游，从城市A出发，途经城市B、城市C和城市D，最后再回到城市A，4个城市之间的距离如表1-3所示。为了节约时间和出行成本，需要进行路线规划，选择一条总里程最短的路线。
表1-3 4个城市之间的距离
利用穷举法可以得到不同出行方案的路线及其总里程，总里程最短的路线可选方案1或方案5（见表1-4）。由于表1-3所示任意两个城市之间的距离矩阵是沿主对角线矩阵对称的，因此一条路线正向行走和反向行走里程也是相等的。对于此类问题，城市数量较少时，可以采用上述穷举法求解，但当城市数量较大时，穷举法求解几乎不可行。
表1-4 不同出行方案的路线及其总里程
问题3 旅行商问题（Traveling Salesman Problem，TSP）。给定城市个数 n 和各城市之间的距离，旅行商要到这些城市推销货物，从某城市出发，其余各城市都要经过且仅经过一次，然后回到出发城市，求其最短行程。即寻找一条巡回路径 X =[ x 1 ， x 2 ，…， x n ]，使得下列目标函数最小：
式中， x i 为城市序号，取[1， n ]之间的自然数； d （ x i ， x j ）为城市 x i 与城市 x j 之间的距离。
这就是著名的旅行商问题，也称为货郎担问题。自1932年K.Menger提出该问题以来，已引起各领域许多研究者的兴趣。它是组合数学中一个古老且极具挑战性的问题，也是组合优化中研究最多的典型问题之一，虽然表面看起来很简单，但求解却很困难，已被证明是NP（Non-deterministic Polynomial）问题，至今尚未彻底解决。
如果采用穷举法，则需考虑所有可能的情况，找出所有的路径，再对其进行比较来找到最佳路径。事实上，在 n 个城市的TSP问题中，一条有效的路径可以看成 n 个城市的一种排列。 n 个城市有 n ！种排列，对于较为简单的对称型TSP问题（这些城市中，任意两个城市之间从A城市到B城市的距离与从B城市到A城市的距离相等），任意两个顺序完全相反的方案其行程相同，而对任意一种排列从哪个城市出发都可以，故可能的路径总数为
由式（1-5）可见： L 4 =3， L 5 =12， L 6 =60， L 30 =4.42×10 30 ， L 60 =6.93×10 79 ， L 100 =4.67×10 155 。因此，路径总数随 n 增大而急剧增长，当城市数目增加到一定程度时，计算量将增加到无法进行的地步。
TSP问题的求解研究相当活跃，这主要是因为：
（1）TSP问题是一个典型的易于描述却难以处理的NP完全问题，有效地解决TSP问题在计算理论领域有着重要的价值。
（2）TSP问题在科学研究、工程应用及经济活动的各个方面具有广泛的应用，是诸多领域内出现的多种复杂问题的集中概括和简化形式，具体包括电路板钻孔、货物配送、管道铺设、网络通信、交通调度、机器人控制、矿物结晶学、超大规模电路板布局、电网规划、组合电路测试、基因组测序等。这些问题或者直接就是TSP问题的原型，或者可转化为TSP问题。因此，快速有效地解决TSP问题有着极高的实际应用价值。
（3）TSP问题因其典型性已成为各种启发式搜索优化算法的间接比较标准。
目前针对TSP问题已有许多种解法，如穷举搜索法、贪婪法、动态规划法、分支界定法等。这些方法都存在一个共同的问题，即当城市数目较大时，会产生所谓的“组合爆炸”问题。例如，当 n =50时，用每秒计算一亿次的巨型计算机采用穷举搜索法计算所需时间约为5×10 48 年。
问题4 背包问题（Knapsack Problem，KP）。背包问题有许多种形式，其中最基本的是0-1背包问题。设有 n 件物品，每件物品都有自身的体积和价值，背包可以承载的最大容积为 C ，由于无法将所有物品装入，需要对物品进行合理选择，使装入背包中的物品的总价值最大。
设第 i 种物品的体积和价值分别为 v i 和 w i ， i =1，2，…， n ，则物品的体积向量为 V =[ v 1 ， v 2 ，…， v n ]，价值向量为 W =[ w 1 ， w 2 ，…， w n ]。物品的选择向量为 X =[ x 1 ， x 2 ，…， x n ]，如果第 i 件物品被选中，则 x i =1，如果第 i 件物品未被选中，则 x i =0。背包问题就是使下列目标函数最大：
因为每件物品具有“选中”和“未选中”两种可能，对于 n 件物品，可能的解就有2 n 种，当 n 较大时，2 n 也就非常大，利用传统方法求解是很困难的。
问题3和问题4都是典型的NP问题，此类问题还有：Dantzig和Ramsert于1959年提出的车辆调度问题（Vehicle Scheduling Problem，VSP）；Francis等人早在20世纪60年代讨论的选址问题（Location Problem，LP）；Dyckhoff等人在20世纪60年代研究的装箱问题（Packing Problem，LP）；等等。面对这些复杂的组合优化问题，传统的优化方法在庞大的搜索空间中寻找最优解往往需要遍历整个搜索空间，无法在短时间内完成搜索，因此，寻求高效的优化算法已成为相关学科的主要研究内容之一。