第三章 非线性规划
§1 非线性规划
1.1 非线性规划的实例与定义 如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问
题。一般说来，解非线性规划要比解线性规划问题困难得多。而且，也不象线性规划有
单纯形法这一通用方法，非线性规划目前还没有适于各种问题的一般算法，各个方法都
有自己特定的适用范围。
下面通过实例归纳出非线性规划数学模型的一般形式，介绍有关非线性规划的基本
概念。
例 1 （投资决策问题）某企业有 n 个项目可供选择投资，并且至少要对其中一个
项目投资。已知该企业拥有总资金 A 元，投资于第 i(i 1,L, n) 个项目需花资金 ai 元，
并预计可收益 bi 元。试选择最佳投资方案。
解 设投资决策变量为
1, 决定投资第i个项目
x ， i 1,L, n ，
0 ， 决定不投资第i个项目 n n
则投资总额为 ai xi ，投资总收益为 bi xi 。因为该公司至少要对一个项目投资，并
i 1 i 1
且总的投资金额不能超过总资金 A ，故有限制条件
n
0 ai xi A
i 1
另外，由于 xi (i 1,L, n) 只取值 0 或 1，所以还有
xi (1 xi ) 0, i 1,L, n.
最佳投资方案应是投资额最小而总收益最大的方案，所以这个最佳投资决策问题归
结为总资金以及决策变量（取 0 或 1）的限制条件下，极大化总收益和总投资之比。因
此，其数学模型为：
n bi xi
max Q i 1 n ai xi
i 1
n
s.t. 0 ai xi A
i 1
xi (1 xi ) 0, i 1,L, n.
上面例题是在一组等式或不等式的约束下，求一个函数的最大值（或最小值）问
题，其中至少有一个非线性函数，这类问题称之为非线性规划问题。可概括为一般形式
常见数学建模模型
一、线性规划模型
线性规划是一种常用的数学建模方法，它通过建立线性函数和约束条件，寻找最优解。线性规划可以应用于各种实际问题，如生产调度、资源分配、运输问题等。通过确定决策变量、目标函数和约束条件，可以建立数学模型，并利用线性规划算法求解最优解。
二、整数规划模型
整数规划是线性规划的一种扩展形式，它要求决策变量为整数。整数规划模型常用于一些离散决策问题，如旅行商问题、装箱问题等。通过引入整数变量和相应的约束条件，可以将问题转化为整数规划模型，并利用整数规划算法求解最优解。
三、非线性规划模型
非线性规划是一类目标函数或约束条件中存在非线性项的优化问题。非线性规划模型常见于工程设计、经济优化等领域。通过建立非线性函数和约束条件，可以将问题转化为非线性规划模型，并利用非线性规划算法求解最优解。
四、动态规划模型
动态规划是一种通过将问题分解为子问题并以递归方式求解的数学建模方法。动态规划常用于求解具有最优子结构性质的问题，如背包问题、最短路径问题等。通过定义状态变量、状态转移方程和边界条件，可以建立动态规划模型，并利用动态规划算法求解最优解。
五、排队论模型
排队论是一种研究队列系统的数学理论，可以用于描述和优化各种排队系统，如交通流、生产线、客户服务等。排队论模型通常包括到达过程、服务过程、队列长度等要素，并通过概率和统计方法分析系统性能，如平均等待时间、系统利用率等。
六、图论模型
图论是一种研究图结构和图算法的数学理论，可以用于描述和优化各种实际问题，如网络优化、路径规划、社交网络等。图论模型通过定义节点、边和权重，以及相应的约束条件，可以建立图论模型，并利用图算法求解最优解。
七、随机模型
随机模型是一种考虑不确定性因素的数学建模方法，常用于风险评估、金融建模等领域。随机模型通过引入随机变量和概率分布，描述不确定性因素，并利用概率和统计方法分析系统行为和性能。
八、模糊模型
数学建模十大经典算法
数学建模是将现实问题转化为数学模型，并利用数学方法进行求解的过程。下面是数学建模中常用的十大经典算法：
1.线性规划（Linear Programming）：通过确定一组线性约束条件，求解线性目标函数的最优解。
2.整数规划（Integer Programming）：在线性规划的基础上，要求变量取整数值，求解整数目标函数的最优解。
3.非线性规划（Nonlinear Programming）：目标函数或约束条件存在非线性关系，通过迭代方法求解最优解。
4.动态规划（Dynamic Programming）：通过分阶段决策，将复杂问题分解为多个阶段，并存储中间结果，以求解最优解。
5.蒙特卡洛模拟（Monte Carlo Simulation）：通过随机抽样和统计分析的方法，模拟系统的行为，得出概率分布或数值近似解。
6.遗传算法（Genetic Algorithm）：模拟生物进化过程，通过选择、交叉和变异等操作，寻找最优解。
7.粒子群算法（Particle Swarm Optimization）：模拟鸟群或鱼群的行为，通过个体间的信息交流和集体协作，寻找最优解。
8.模拟退火算法（Simulated Annealing）：模拟金属退火的过程，通过控制温度和能量变化，寻找最优解。
9.人工神经网络（Artificial Neural Network）：模拟生物神经网络的结构和功能，通过训练网络参数，实现问题的分类和预测。
10.遗传规划（Genetic Programming）：通过定义适应性函数和基因编码，通过进化算子进行选择、交叉和变异等操作，求解最优模型或算法。
这些算法在不同的数学建模问题中具有广泛的应用，能够帮助解决复杂的实际问题。
【数学建模】数学模型总结 吴翔
1 四类基本模型
1 优化模型
1.1 数学规划模型
线性规划、整数线性规划、非线性规划、多目标规划、动态规划。
1.2 微分方程组模型
阻滞增长模型、SARS传播模型。
1.3 图论与网络优化问题
最短路径问题、网络最大流问题、最小费用最大流问题、最小生成树问题(MST)、旅行商问题(TSP)、图的着色问题。
1.4 概率模型
决策模型、随机存储模型、随机人口模型、报童问题、Markov链模型。
1.5 组合优化经典问题
多维背包问题(MKP)
背包问题：n个物品，对物品i，体积为iw，背包容量为W。如何将尽可能多的物品装入背包。
多维背包问题：n个物品，对物品i，价值为ip，体积为iw，背包容量为W。如何选取物品装入背包，是背包中物品的总价值最大。
多维背包问题在实际中的应用有：资源分配、货物装载和存储分配等问题。该问题属于NP难问题。
二维指派问题(QAP)
工作指派问题：n个工作可以由n个工人分别完成。工人i完成工作j的时间为ijd。如何安排使总工作时间最小。
二维指派问题（常以机器布局问题为例）：n台机器要布置在n个地方，机器i与k之间的物流量为ikf，位置j与l之间的距离为jld，如何布置使费用最小。
二维指派问题在实际中的应用有：校园建筑物的布局、医院科室的安排、成组技术中加工中心的组成问题等。
旅行商问题(TSP)
旅行商问题：有n个城市，城市i与j之间的距离为ijd，找一条经过n个城市的巡回（每个城市经过且只经过一次，最后回到出发点），使得总路程最小。
车辆路径问题(VRP)
车辆路径问题（也称车辆计划）：已知n个客户的位置坐标和货物需求，在【数学建模】数学模型总结 吴翔
2 可供使用车辆数量及运载能力条件的约束下，每辆车都从起点出发，完成若干客户点的运送任务后再回到起点，要求以最少的车辆数、最小的车辆总行程完成货物的派送任务。
