本帖最后由 宇宙微尘 于 2025-1-21 16:10 编辑
实验介绍
混合整数线性规划（Mixed Integer Linear Programming，MILP）是一类优化问题，其中目标函数和约束条件均为线性，并且包含整数变量。MILP 在实际应用中具有广泛的应用，可以解决很多实际问题，如生产调度、网络设计、资源分配等。
知识点
(1)混合整数线性规划
(2)资源分配问题
混合整数线性规划的应用
混合整数线性规划（MILP）在实际应用中具有广泛的用途。下面列举了一些常见的应用领域：
(1)生产计划和调度：在制造业中，MILP 可以帮助制定最佳的生产计划和调度方案，以优化资源利用，最大化产出或最小化成本。例如，在生产线上安排作业顺序、分配工人和机器的调度等问题。
(2)物流和运输优化：MILP 可以用于优化货物的运输路线、仓库位置选择、车辆调度等物流和供应链管理问题。通过最佳路线和调度，可以最大限度地降低物流成本并提高效率。
(3)设施位置规划：在城市规划、网络设计和设施选址等领域中，MILP 可以帮助确定最佳的设施位置和配置方案。例如，确定新的工厂、仓库或服务设施的最佳位置，以便最大程度地满足需求并减少成本。
(4)资源分配和调度：MILP 可以用于优化资源的分配和调度，例如人员、设备、资金等。在医疗机构、航空公司、能源系统等领域，MILP 可以支持决策者制定最佳的资源分配方案，以提高效率和满足需求。
(5)项目管理：在项目管理中，MILP 可以帮助制定最佳的项目进度计划、资源分配和工作分配。通过优化项目执行顺序、资源利用和时间表，可以最大限度地减少项目延误和成本超支。
混合整数线性规划
混合整数线性规划（Mixed Integer Linear Programming，简称 MILP）是一种优化问题的数学建模方法。在 MILP 中，目标函数和约束条件都是线性的，并且问题中既包含连续变量（取任意实数值），又包含整数变量（取整数值）。整数变量的存在使得问题更加复杂，因为整数变量引入了离散决策的要素。
MILP 可以用于解决许多实际问题，例如生产规划、资源分配、调度问题等。通过在目标函数中考虑最小化或最大化某个指标，同时在约束条件中限制变量的取值范围，MILP 可以帮助找到最优的决策方案。
x = intlinprog(f,intcon,A,b) 最小化 f'*x，使得 intcon 中的 x 分量是整数，且 A*x ≤ b。
x = intlinprog(f,intcon,A,b,Aeq,beq) 求解上述问题，同时还满足等式约束 Aeq*x = beq。如果不存在不等式，请设置 A = [] 和 b = []。
x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub) 定义设计变量 x 的一组下界和上界，使解始终在 lb ≤ x ≤ ub 范围内。如果不存在等式，请设置 Aeq = [] 和 beq = []。
x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,x0) 使用初始可行点 x0 进行优化。如果不存在边界，请设置 lb = [] 和 ub = []。
x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,x0,options) 使用 options 中指定的优化选项执行最小化。使用 optimoptions 可设置这些选项。如果不存在初始点，请设置 x0 = []。
输入参数介绍
f — 系数向量。
系数向量，指定为实数向量或实数数组。
intcon — 整数约束组成的向量。
整数约束组成的向量，指定为正整数向量。intcon 中的值指示决策变量 x 中应取整数值的分量。
A — 线性不等式约束。
线性不等式约束，指定为实矩阵。A 是 M×N 矩阵，其中 M 是不等式的数目，而 N 是变量的数目（f 的长度）。
b — 线性不等式约束。
Aeq — 线性等式约束。
beq — 线性等式约束。
lb — 下界，ub — 上界。
示例演示一
假设我们有以下优化问题：
我们的目标是找到满足约束条件下的最大值。
f = [-5;-4];
intcon = 1:2;
A = [2,1;
1,2];
b = [8;6;];
lb=[0;0];
x = intlinprog(f,intcon,A,b,[],[],lb)
结果展示：
LP: Optimal objective value is -22.000000.
Cut Generation: Applied 1 Gomory cut.
Lower bound is -20.000000.
Relative gap is 0.00%.
Optimal solution found.
x =
4
0
示例演示二
求解具有线性不等式的 MILP。
编写目标函数向量和由整数变量组成的向量。
f = [8;1];
intcon = 2;
A = [-1,-2;
-4,-1;
2,1];
b = [14;-33;20];
x = intlinprog(f,intcon,A,b)
结果展示：
LP: Optimal objective value is 59.000000.
Optimal solution found.
x =
6.5000
7.0000
示例演示三
求解具有所有类型的约束的 MILP。
f = [-3;-2;-1];
intcon = 3;
A = [1,1,1];
b = 7;
Aeq = [4,2,1];
beq = 12;
lb = zeros(3,1);
ub = [Inf;Inf;1];
x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)
结果展示：
LP: Optimal objective value is -12.000000.
Optimal solution found.
x =
0
5.5000
1.0000
实验总结
本实验让我们了解了整数规划的流程：
(1)确定问题背景和目标，明确需要优化的目标函数，例如最小化成本、最大化利润等。
(2)定义问题中的决策变量和约束条件，包括连续变量和整数变量，以及线性等式和线性不等式约束。
(3)将问题转化为数学模型，构建目标函数和约束条件的数学表示。
利用计算工具或优化软件包提供的函数进行求解。MATLAB 的优化工具箱提供了用于求解 MILP 问题的 intlinprog 函数。需要重点考虑问题的建模准确性、求解方法的效率和可行性，以及对最优解的解释和验证。通过不断优化建模和求解过程，可以更好地解决复杂数学规划问题，并取得更好的优化结果。
本文转载自微信公众号：数学建模CUMCM | 
完善个人信息