数学建模方法0001

[TOC]

前言

网课来源
【胎教级入门数学建模】持续更新！可能是B站大学最良心的数学建模课程了，包含全套数学模型、算法、编程、写作、MATLAB教学视频

整数规划

AI总结的

在数学建模中，整数规划（Integer Programming, IP） 是一种非常重要的优化方法，主要用于解决那些决策变量必须取整数值的问题。它是线性规划（Linear Programming, LP）的一个特例或扩展。

🧩 一、整数规划的基本概念

整数规划是一类优化问题，其一般形式为：

$$\begin{aligned} \text{minimize} \quad & c^T x \ \text{subject to} \quad & A x \le b \ & x_i \in \mathbb{Z} \text{ 或 } x_i \in {0,1}, \text{ 对某些或全部 } i \end{aligned}$$

其中：

• ( x )：决策变量；
• ( c )：目标函数的系数向量；
• ( A )、( b )：约束条件；
• 要求部分或全部变量 ( x_i ) 必须是整数。

---

🧮 二、整数规划的主要类型

1. 纯整数规划（Pure Integer Programming）
   所有决策变量都是整数。
   例：

   • 生产数量、车辆数、工人数等必须是整数。

2. 混合整数规划（Mixed Integer Programming, MIP）
   只有部分变量要求是整数，其他可以是实数。
   例：

   • 工厂选址（0/1决策） + 运输量（连续变量）。

3. 0-1整数规划（Binary Integer Programming）
   决策变量只取0或1，常用于选址、调度、分配、路径规划等问题。
   例：

   • ( x_i = 1 ) 表示选择方案i，( x_i = 0 ) 表示不选择。

---

⚙️ 三、常见应用场景

应用领域	示例
选址问题	选择哪些工厂或仓库建成，以最小化成本
任务分配	员工与任务的最优匹配
路径规划	旅行商问题（TSP）、物流配送
生产计划	不同产品的产量决策
投资组合	选择投资项目的最优组合

---

🔍 四、求解方法

由于整数规划属于 NP难问题，不能像线性规划那样用单纯形法直接求解。常见算法包括：

1. 分支定界法（Branch and Bound）
   将问题分解成若干子问题，通过界限剪枝减少计算。

2. 割平面法（Cutting Plane）
   在连续解上添加“割平面”逐步逼近整数最优解。

3. 启发式与元启发式算法（用于大规模问题）
   如：遗传算法、模拟退火、禁忌搜索、粒子群算法等。

---

📘 五、建模技巧提示

• 整数约束可用来表示逻辑关系，例如：

  • “要么选A，要么选B” → ( x_A + x_B = 1 )
  • “选A则必须选B” → ( x_A \le x_B )

• 可以与线性规划、非线性规划结合，用于复杂决策模型。

• 常用求解器：Lingo、CPLEX、Gurobi、Excel Solver、Python PuLP/OR-Tools 等。

简单来说

有的时候那你肯定不能把人、物啥的分开啊，也就是怎么可能有0.5个人这样的形式awa

所以我们既要保证最优解，又要保证是整数，这就用到了整数规划

但需要注意的是，整数规划并非一味地取整，而是根据实际问题来判断

如何用？

x = intlinprog(f, intcon, A, b, Aeq, beq, lb, ub)

参数	含义
f	目标函数的系数向量 ( $c$ )，即最小化 ( $f^T x$ )
intcon	指定哪些变量是整数（输入变量的索引）
A, b	不等式约束 ( $A x \le b$ )
Aeq, beq	等式约束 ( $A_{eq} x = b_{eq}$ )
lb, ub	变量的下界和上界
返回值 x	最优解向量（整数解）

🧮 二、整数规划的基本形式

$$\begin{aligned} \text{minimize} \quad & f^T x \ \text{subject to} \quad & A x \le b \ & A_{eq} x = b_{eq} \ & lb \le x \le ub \ & x_i \in \mathbb{Z}, , i \in \text{intcon} \end{aligned}$$

非线性规划

图论与最短路径算法

网络最大流问题

最小费用最大流

旅行商问题