当前位置：首页 > news >正文

整数规划学习总结

news 2025/8/23 13:55:35

整数规划学习总结

一、整数规划概述

整数规划是一类约束优化问题，其中部分或全部决策变量必须取整数值。其一般形式为：

$\begin{aligned} \min/\max \quad & f(x) \\ \text{s.t.} \quad & g_i(x) \le 0, \quad i = 1,2,\dots,m\\ & x_j \in \mathbb{Z}, \quad j \in I \subseteq \{1,2,\dots,n\} \\ & x_j \in \mathbb{R}, \quad j \notin I \end{aligned}$
根据整数变量的个数和类型，整数规划可以分为：

纯整数规划（Pure Integer Programming, IP）：所有决策变量都是整数。
混合整数规划（Mixed-Integer Programming, MIP）：部分变量是整数，部分变量是连续值。
二进制/0-1 整数规划（Binary/0-1 IP）：整数变量只能取 0 或 1，常用于选择、分配、布置问题。

二、整数规划在数学建模中的应用

运输与物流
- 问题：配送车辆分配、仓库选址、最短路径、物流调度
- 特点：物品或车辆的数量是整数，不能分割
- 示例：设有 5 个配送中心和 10 个客户，求最小运输成本的配送方案
生产计划与资源分配
- 问题：工厂生产计划、设备选择、任务排程
- 特点：生产批次、机器台数、工人数量都是整数
- 示例：生产 3 种产品，资源有限，最大化利润
选址与布局优化
- 问题：仓库/工厂/服务器选址
- 特点：选址决策通常是二进制变量（选/不选）
- 示例：在多个候选地点中选 2 个仓库，使总运输成本最小
项目选择与投资决策
- 问题：投资项目组合、科研项目选择
- 特点：每个项目投资与否用 0-1 变量表示
- 示例：预算有限，选择若干项目，使总收益最大
网络设计与分配
- 问题：网络链路规划、电力线路建设
- 特点：是否建设某条线路用 0-1 变量表示

三、MATLAB 中的整数规划语法

MATLAB 提供 intlinprog 函数求解整数规划问题。其基本格式：

[x,fval,exitflag,output] = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)

参数说明：

f：目标函数系数向量（求最小化）
intcon：需要整数约束的变量索引
A, b：不等式约束 $\le b$
Aeq, beq：等式约束 $A e q * x = b e q$
lb, ub：变量下界和上界
x：最优解，fval 最优目标值

若求最大化问题，只需将目标函数取负再最小化：

[x,fval] = intlinprog(-f,intcon,A,b,Aeq,beq,lb,ub);
fval = -fval;

四、具体 MATLAB 示例

例 1：简单生产计划（整数规划）

问题描述：

工厂生产 A、B 两种产品，每种产品需使用两种原料。已知利润和资源约束，求整数生产量使利润最大化。

产品	利润(元)	原料1	原料2
A	40	2	1
B	30	1	2

原料总量：原料1 ≤ 8，原料2 ≤ 6。

MATLAB 代码：

f = [-40 -30];      % 最大化利润 => 最小化负利润
intcon = [1 2];     % 两个变量都要求整数
A = [2 1; 1 2];     % 原料约束
b = [8; 6];
lb = [0 0];         % 非负
ub = [];            % 无上界
x = intlinprog(f,intcon,A,b,[],[],lb,ub);
profit = -f*x;
disp('最优生产量:');
disp(x);
disp('最大利润:');
disp(profit);

运行结果示意：

最优生产量:22
最大利润:140

解释：生产 2 件 A 和 2 件 B，利润最大。

例 2：仓库选址（0-1 整数规划）

问题描述：

有 4 个候选仓库（W1~W4），要选 2 个，满足客户配送需求最小化运输成本。

MATLAB 代码：

f = [10 12 20 18];  % 运输成本
intcon = 1:4;       % 0-1 整数
Aeq = [1 1 1 1];    % 选两个仓库
beq = 2;
lb = zeros(4,1);
ub = ones(4,1);
x = intlinprog(f,intcon,[],[],Aeq,beq,lb,ub);
disp('选址方案:');
disp(x');