算法设计与实践（基于MWORKS）课件 第八章 优化算法

第八章优化算法8.1线性规划算法8.2非线性规划算法8.3整数规划算法8.4遗传算法CONTENTS目录线性规划基本定位它是运筹学重要分支，发展成熟、应用广泛，是辅助科学管理的数学方法。线性规划核心目标在一组线性约束条件下，对线性目标函数进行最大化或最小化的优化。线性规划标准形式标准形式为最小化目标函数，约束条件为Ax=b且x≥0，涉及决策变量等四类向量矩阵。8.1.1算法原理8.1线性规划算法

经典求解方法线性规划最优解在可行域顶点取得，单纯形法是其经典算法，通过迭代移至相邻顶点寻最优解。

对偶理论介绍每个线性规划问题均对应一对偶问题，二者关联深刻，对偶问题的解可为原问题提供重要经济解释与灵敏度分析。8.1线性规划算法8.1.1算法原理

应用范围线性规划应用广泛，涵盖生产计划、资源分配、运输、投资、饮食、下料、人员调度等领域8.1.2线性规划算法：应用范围8.1线性规划算法Julia线性规划示例

通过具体例子展示Julia语言解决线性规划问题的方法，明确使用JuMP建模。求解工具搭配说明

采用JuMP作为建模语言，结合GLPK求解器来完成线性规划问题的求解操作。8.1.3线性规划算法：Julia代码实例8.1线性规划算法生产计划问题描述工厂生产A、B两种产品，明确单位产品的劳动力、原材料消耗，现有资源总量及单位产品利润，求最大利润的生产安排。Julia代码实现方案通过JuMP与GLPK库创建线性规划模型，定义决策变量、目标函数与约束条件，求解并输出最优生产方案结果。代码运行问题解决若运行时遇权限错误，可设置对应文件夹完全控制权限，或右键以管理员身份运行Mworks.Syslab。8.1.3线性规划算法：Julia代码实例8.1线性规划算法

运输问题概述给定两个工厂A、B，产量分别为100、150单位，需运往C、D、E三个仓库，需求量为70、100、80单位，各路线单位运输成本明确，求最低总成本运输方案Julia代码实现规划8.1.3线性规划算法：Julia代码实例8.1线性规划算法导入JuMP和GLPK库，定义供需、成本数据，构建模型，设置决策变量、目标函数及供需约束，求解并输出最优运输方案与总成本最优运输方案详情工厂A运70单位至C、30单位至D，工厂B运70单位至D、80单位至E，总运输成本为790.0，达成成本最优8.1.3线性规划算法：Julia代码实例8.1线性规划算法饮食优化问题设定需满足每日蛋白质50克、碳水300克、脂肪60克的最低需求，从四种食物中选择以降低总费用。食物营养价格详情鸡蛋、面包、牛奶、苹果四种食物的蛋白质、碳水、脂肪含量及每份价格各有不同，具体数值明确。Julia代码实现逻辑通过JuMP与GLPK库搭建线性规划模型，定义决策变量、目标函数及营养约束，完成求解与结果输出。求解结果及应用说明最优方案为12份鸡蛋、15份苹果，总费用33元，体现线性规划在实际问题中的建模与求解方法。8.1.3线性规划算法：Julia代码实例8.1线性规划算法非线性规划定义作为数学优化重要分支，研究非线性约束条件下，优化非线性目标函数的问题。非线性规划特性与线性规划不同，其目标函数或约束条件至少一个为非线性，求解难度更大。8.2非线性规划算法8.2.1非线性规划算法：算法原理数学模型非线性规划有标准形式，含决策变量、目标函数等要素，存在局部与全局最优解，全局最优更难求解。8.2.1非线性规划算法：算法原理8.2非线性规划算法

无约束优化算法含梯度下降法、牛顿法、拟牛顿法，分别沿负梯度迭代、用二阶导数构造公式、近似牛顿法且免算Hessian矩阵。

约束优化算法涵盖拉格朗日乘子法、序列二次规划、内点法，通过转化问题或求解子问题实现约束优化。

全局优化算法包含模拟退火、遗传、粒子群算法，分别基于蒙特卡洛迭代、生物进化、鸟群觅食行为求解最优解。8.2.1非线性规划算法：算法原理8.2非线性规划算法工程设计优化结构优化：降重同时保强度；电路设计：调参数提性能；机械设计：优零件形与尺经济与金融投资组合优化：平衡风险与收益；定价策略：最大化产品利润；资源分配：优化配置提效益。机器学习与数据科学神经网络训练：最小化损失函数支持向量机：求解最大间隔分类器8.2.2非线性规划算法：应用范围8.2非线性规划算法

参数估计最大似然估计和贝叶斯推断

运筹学与管理科学非线性运输问题、非线性设施选址问题、生产计划与调度问题

物理与化学工程化学反应过程优化、热力学系统设计、流体力学中的最优控制问题8.2.2非线性规划算法：应用范围8.2非线性规划算法Julia建模工具说明采用JuMP作为非线性规划问题的建模语言，搭配Ipopt作为对应的求解器来完成计算。非线性规划实例演示通过具体案例展示如何运用Julia语言，借助指定工具解决非线性规划相关问题。8.2.3非线性规划算法：Julia代码实例8.2非线性规划算法例1：无约束优化问题最小化

Rastrigin函数特性该函数表达式为(,)=20+2−10cos(2π)+2−10cos(2π)，在原点(0,0)处有全局最小值0，且存在许多局部最小值。

Julia代码实现过程导入JuMP和Ipopt包，创建模型定义决策变量，以最小化Rastrigin函数为目标构建模型并求解。

代码运行结果说明运行后显示最优解状态为LOCALLY_SOLVED，最优目标值约7.96，最优解x、y均约为1.99。8.2.3非线性规划算法：Julia代码实例8.2非线性规划算法例2：约束优化问题

01约束优化问题描述给出带非线性约束的优化问题，目标函数为(x₁-3)²+(x₂-2)²，可行域是圆形区域与半平面交集。

02Julia代码实现过程引入JuMP与Ipopt包，创建模型定义决策变量、目标函数及非线性约束，执行求解并输出结果。

03代码求解结果展示运行代码后得到局部最优解，最优目标值约1.875，x₁约1.861，x₂约1.240。8.2.3非线性规划算法：Julia代码实例8.2非线性规划算法例3：投资组合优化问题

投资组合优化设定给定三种资产的预期收益率与协方差矩阵，要求在风险方差不超0.005的前提下，最大化投资预期收益。

Julia代码实现逻辑引入JuMP与Ipopt库，定义资产预期收益、协方差矩阵及风险上限，创建模型设置投资比例变量与约束。

代码求解结果说明运行后得到局部最优解，最优预期收益率约0.0923，同时给出了最优投资组合与实际风险水平。

非线性规划应用提示该实例展示了非线性规划的建模与求解，实际应用需调整模型，注意局部最优问题，全局优化需专用算法。8.2.3非线性规划算法：Julia代码实例8.2非线性规划算法

整数规划概述整数规划是运筹学重要分支，研究决策变量部分或全为整数时的目标函数优化问题，求解复杂，属NP完全问题。8.3整数规划算法8.3.1整数规划算法：算法原理标准形式定义整数规划标准形式含目标与约束，明确决策变量、系数向量等要素，指定整数变量索引集合。纯整数规划为所有决策变量均取整数值的整数规划类型。规划主要类型包含纯整数、混合整数、0-1整数规划三类，0-1型常用于表示逻辑决策，混合型部分变量连续。数学模型与类型8.3.1整数规划算法：算法原理8.3整数规划算法主要求解算法

分支定界法原理将原问题分解为子问题递归求解，通过松弛问题获取下界，借助剪枝策略缩小搜索空间。

割平面法核心逻辑通过添加线性不等式割平面，每次迭代求解松弛问题，逐步逼近整数规划的最优解。

启发式算法类型涵盖遗传算法、模拟退火、禁忌搜索等，依靠启发式规则寻找整数规划的近似解。

专用算法应用场景包括背包问题的动态规划算法、旅行商问题的最近邻算法，针对特定整数规划问题设计。8.3.1整数规划算法：算法原理8.3整数规划算法生产运营类应用

生产运营管理应用可用于生产批量计划、设施选址、资源分配，确定最优生产批次、选址方案及有限资源分配方式。

组合优化问题应用覆盖旅行商、背包、图着色问题，能寻找最短路径、最优物品组合及合规的图顶点着色方案。

调度问题场景应用适用于项目调度、人员排班、车辆路径规划，确定任务执行顺序、最优排班及配送路线。8.3.2整数规划算法：应用范围8.3整数规划算法金融投资类应用涵盖资本预算（选最优投资项目组合）、投资组合优化（风险约束下提回报）、资产分配（定资产最优占比）逻辑设计类应用涵盖集成电路布局优化、机器学习特征选择、布尔逻辑电路优化三类逻辑设计与约束满足应用8.3.2整数规划算法：应用范围8.3整数规划算法

Julia建模求解说明以Julia语言为工具，采用JuMP作为建模语言，结合Cbc求解器来解决整数规划问题。

整数规划实例展示通过几个具体的例子，详细展示使用Julia语言解决整数规划问题的具体操作。8.3.3整数规划算法：Julia代码实例8.3整数规划算法例1：背包问题

背包问题描述背包容量50公斤，有5个不同重量与价值的物品，需选择物品使总价值最大化。

Julia代码实现逻辑导入JuMP与Cbc包，定义物品重量、价值及背包容量，创建0-1整数规划模型并设置目标与约束。

代码求解结果说明求解得出总价值最大为270元，最优选择为物品1、2、4、5，不选物品3。8.3.3整数规划算法：Julia代码实例8.3整数规划算法例2：生产计划问题

生产规划问题描述某工厂生产A、B、C三种产品，需在M1、M2两台机器加工，各产品加工时间、利润及机器每周可用时间明确，A、B产量需为整数，求最大总利润。Julia代码实现规划通过导入JuMP和Cbc包，定义数据、创建模型、设置决策变量与目标函数、添加机器时间约束，求解并输出最优生产计划及利润。8.3.3整数规划算法：Julia代码实例8.3整数规划算法例3：旅行商问题(TSP)

旅行商问题描述给定5个城市的距离矩阵，要求旅行商访问每个城市一次且仅一次后返回出发城市，求解最短旅行路线。

问题求解代码实现通过Julia调用JuMP、Cbc等工具包，定义决策变量与MTZ约束构建整数规划模型，编写代码求解并提取最优旅行路线。

求解结果与应用提示代码运行得出最优路线为1→2→4→5→3→1，总距离85，同时提示大规模整数规划问题可采用启发式算法提升效率。8.3.3整数规划算法：Julia代码实例8.3整数规划算法

算法起源与定义遗传算法由约翰·霍兰德于20世纪70年代提出，是受生物进化启发的优化搜索算法。模拟自然选择和遗传机制在解空间寻最优解，尤其适用于复杂非线性优化问题。

算法核心特性模拟自然选择和遗传机制在解空间寻最优解，尤其适用于复杂非线性优化问题。

算法核心特性依托生物进化逻辑构建搜索逻辑，针对复杂非线性优化问题具备独特适配性。8.4遗传算法8.4.1算法原理种群一组候选解的集合个体一个候选解，通常表示为染色体染色体解的编码表示，由多个基因组成基因(Gene)染色体中的一个位置，代表解的一个特征适应度(Fitness)评估个体优劣的指标，值越高表示越优算法流程：初始化随机生成一组初始解（种群）8.4遗传算法8.4.1算法原理

评估计算每个个体的适应度值

选择根据适应度值选择优良个体作为父代

交叉对选中的父代进行基因重组，生成子代

变异对子代的部分基因进行随机突变

替换用子代替换部分或全部旧种群8.4遗传算法8.4.1算法原理终止判断

算法终止判定规则若达到最大迭代次数或找到满意解则停止运行，未满足终止条件则返回步骤2继续执行。

算法选择操作类型包含轮盘赌选择、锦标赛选择、精英保留三种方式，分别按适应度比例、随机选组取最优、直接保留最优个体来操作。

算法交叉操作类型有单点交叉、多点交叉、均匀交叉三种，分别是随机选一个点、选多个点、每个基因位按概率进行基因交换。

算法变异操作类型涵盖位翻转、随机重置、边界变异三种，分别对二进制基因取反、用随机值替换原有基因、将基因值设为边界值。8.4遗传算法8.4.1算法原理遗传算法在各个领域有广泛的应用，主要包括组合优化问题组合优化问题包含旅行商问题、背包问题、车辆路径问题、作业调度问题。函数优化高维非线性函数的全局优化多峰函数的最优解搜索带约束条件的优化问题机器学习与数据科学神经网络结构优化特征选择与降维超参数优化聚类分析8.4.2应用范围8.4遗传算法工程设计电路设计优化机械结构优化材料性能优化智能控制机器人路径规划自适应控制参数优化电力系统优化调度生物信息学DNA序列比对蛋白质结构预测基因表达数据分析8.4.2遗传算法：应用范围8.4遗传算法

算法实现思路以自定义实现方式展示Julia语言遗传算法，便于深入理解算法核心原理。

代码实例展示通过几个具体的例子，演示如何使用Julia语言完成遗传算法的实现。8.4.3遗传算法：Julia代码实例8.4遗传算法例1：函数优化问题

01目标函数与问题说明使用遗传算法求解Rastrigin函数最小值，该函数表达式为$f(x)=10n+\sum_{i=1}^{n}[x_i^2-10\cos(2\pix_i)]$，$x_i∈[-5.12,5.12]$，原点处有全局最小值0。

02Julia算法代码实现代码含目标函数定义、遗传算法核心逻辑，含种群初始化、锦标赛选择、算术交叉、高斯变异，还设置