离散优化算法MATLAB程序库与教学演示系统

资 源 简 介

本项目集合了大量基于MATLAB开发的离散优化基础与进阶程序，旨在全面展示离散优化技术在现代社会如物流调度、电力市场、医疗资源分配及科学研究中的关键作用。项目内容涵盖了约束编程、本地搜索和混合整数规划等核心领域，通过具体的代码实现帮助用户深入理解算法逻辑并解决复杂的实际问题，如调度、车辆路径规划（VRP）、供应链优化和资源分配等。具体功能模块详细包括：1. 基础算法实现，包括枚举法和蒙特卡罗方法的MATLAB代码，用于解决基础搜索和概率模拟问题；2. 整数规划工具，提供线性整数规划的标准解法，以及整数规划枚举法和隐枚举法（如分支定界）的代码实现与详细原理解析；3. 非线性规划及其可视化，包含非线性整数规划的求解程序以及专门开发的图形化工具（GUI），方便用户直观地进行参数调整和结果观察；4. 图论与网络优化，实现了最小生成树的Kruskal算法和最短路径的Dijkstra算法，特别值得一提的是，除了标准的MATLAB脚本外，还提供了经过C/C++编译优化的MEX程序版本，显著提升了算法在大规模数据集上的运行效率；5. 多阶段决策工具，提供动态规划算法的通用模板和应用说明。整个系统既作为学习离散优化基本概念和算法的教学材料，也是解决实际工程优化问题的实用工具箱。

详 情 说 明

离散优化方法 MATLAB 程序库与教学演示系统

项目简介

本项目是一个基于 MATLAB 开发的图形化教学演示系统，专注于展示离散优化、整数规划及非线性规划的基础算法与原理。系统通过一个集成的 GUI 界面，允许用户选择不同的算法模块，实时查看算法的运行日志、通过可视化图表观察收敛过程或几何原理，旨在帮助用户直观理解复杂的优化理论。

系统要求

• 运行环境: MATLAB R2016a 或更高版本
• 工具箱依赖: Optimization Toolbox (用于线性规划求解函数 linprog)

功能特性与使用方法

界面设计

系统启动后会展示一个全屏主窗口，主要分为三个区域：

• 左侧控制面板: 包含所有可用算法模块的功能按钮。
• 右侧绘图区域: 用于展示算法结果的可视化图表（如收敛曲线、可行域多边形、等高线图等）。
• 底部日志区域: 实时显示算法的执行状态、关键计算结果（如最优解、目标值）以及执行耗时。

交互逻辑

1. 系统初始化时会清理工作空间并建立图形界面。
2. 用户点击左侧按钮触发相应的回调函数。
3. 系统自动清理绘图区，记录开始时间。
4. 执行算法逻辑，同时将关键步骤和最终结果输出到底部列表框中。
5. 若执行过程中发生错误，系统会捕获异常并在日志中显示，防止程序崩溃。

详细功能模块与实现逻辑

本项目代码主要实现了以下核心算法模块，其内部逻辑严格对应 main.m 中的实现：

1. 蒙特卡罗法 (0/1 背包问题)

该模块使用随机模拟方法解决经典的背包问题。

• 问题设定: 预设了10件物品的重量和价值，背包总容量限制为25。
• 算法逻辑:

* 设定迭代次数为2000次。 * 在每次迭代中，利用 randi 函数生成一个长度为10的随机 0/1 向量，代表物品的选择方案。 * 计算当前方案的总重量和总价值。 * 约束检查: 判断总重量是否超出背包容量。若满足约束且当前价值优于历史最优值，则更新最优解。

• 可视化: 绘制迭代次数与当前发现的最优价值之间的关系曲线，直观展示随机搜索的收敛过程。

2. 线性整数规划 (分支定界原理演示)

该模块通过几何图形直观演示二维整数规划（ILP）的分支定界思想。

• 问题模型: 求解 Maximization 问题 ($3x_1 + 2x_2$)，受限于两个线性不等式约束及非负整数约束。
• 实现细节:

* 松弛解可视化: 计算并绘制由约束条件围成的多边形可行域（填充为浅蓝色），演示线性规划（LP）松弛后的解空间。 * LP求解: 调用 MATLAB 内置的 linprog 函数求解连续松弛问题的最优解，并在图中标注。 * 整数格点: 在坐标系中生成 $6 times 6$ 的网格，筛选出满足所有约束条件的整数点（黑色散点）。 * 枚举寻优: 遍历所有可行整数点，比较目标函数值，找到并高亮显示整数规划的全局最优解（绿色大点），以此模拟分支定界中寻找整数解的过程。 * 对比展示: 图形界面清晰展示了 LP 松弛最优解（通常为分数）与实际 IP 最优解（整数）之间的位置差异。

3. 非线性规划可视化

该模块展示了在非凸、非线性目标函数下的离散点搜索。

• 目标函数: $f(x,y) = (x-2)^2 + (y-3)^2 + 2sin(3x)cos(3y)$，这是一个具有多个局部极小值的复杂曲面。
• 实现细节:

* 等高线绘制: 在 $5 times 5$ 的连续区域内计算函数值，并使用 contourf 绘制填充等高线图，展示函数的全局地貌。 * 离散搜索: 在整数网格点上进行暴力搜索，评估每个整数坐标点的函数值。 * 结果标记: 找出离散域内的最小值点，并用红色五角星高亮标记，同时在日志中输出该点的坐标及函数值。

• 教学意义: 直观展示了连续最优解位置（函数谷底）与离散整数最优解位置的逼近关系。

4. 最小生成树 (Kruskal)

• 初始化: 代码实现了随机图的生成，创建10个节点并随机分配二维坐标。
• 预备步骤: 系统准备计算全连接距离矩阵，为后续生成最小生成树做数据准备（注：提供的代码片段在此处截断，但在逻辑上已包含图结构的初始化）。

5. 其他功能入口

系统界面中包含了以下功能的入口按钮，通过通用回调机制进行挂载：

• 最短路径 (Dijkstra)
• 动态规划 (资源分配)

代码结构分析

• 主函数 (main): 负责界面的生命周期管理，定义了全局数据结构，并利用匿名函数封装了带有日志记录功能的按钮回调。
• 日志辅助器 (runWithLog): 这是一个封装器（Wrapper），它负责：

* 重置绘图坐标轴。 * 使用 tic / toc 计时。 * 使用 try-catch 结构捕获算法内部可能出现的错误，确保 GUI 的稳定性。 * 更新界面上的日志列表框。

• 独立算法子函数: 每个算法（如 demo_monte_carlo, demo_ilp_bnb 等）都作为独立的子函数存在，接收绘图句柄 ax 和日志句柄 hLog 作为输入，实现了算法逻辑与界面展示的分离。