数学建模-线性规划(LP)

目录

📘 线性规划（Linear Programming, LP）介绍

一、什么是线性规划？

1. 定义：

2. 核心思想：

二、线性规划问题的基本构成

1️⃣ ​​决策变量（Decision Variables）​​

2️⃣ ​​目标函数（Objective Function）​​

3️⃣ ​​约束条件（Constraints）​​

三、线性规划的标准形式（简化版）

四、线性规划的求解方法

1. ​​单纯形法（Simplex Method）​​ ⭐⭐⭐

2. ​​内点法（Interior Point Method）​​

3. ​​软件工具求解（推荐）​​

五、线性规划的应用场景（超实用！）

✅ 1. ​​生产计划问题​​

✅ 2. ​​运输问题​​

✅ 3. ​​饮食搭配 / 营养问题​​

✅ 4. ​​投资组合 / 资金分配​​

✅ 5. ​​人力资源安排​​

✅ 6. ​​混合问题（如生产 + 运输 + 库存）​​

六、线性规划的优点与局限性

✅ 优点：

❌ 局限性：

七、举个实际例子（便于理解）

🎯 问题：工厂生产计划

🧮 建立线性规划模型：

八、总结一句话：

✅ 类比熵权法介绍风格总结表：

2-理论知识

介绍

原理

定义

应用

3-基于matlab实现线性规划

源代码

运行结果

---

1-AI带你认识LP

📘 线性规划（Linear Programming, LP）介绍

---

一、什么是线性规划？

1. 定义：

​​线性规划（Linear Programming，简称 LP）​​ 是运筹学中最基础、最重要的一种数学优化方法，用于在​​一组线性约束条件下，寻找某个线性目标函数的最优值（通常是最大值或最小值）​​。

简单来说：​​在一定限制条件下，怎么安排资源、做出决策，使得某个目标达到最好（比如利润最大、成本最小）。​​

---

2. 核心思想：

​​在满足一系列线性等式或不等式约束的前提下，通过调整决策变量，使得一个线性目标函数达到最大值或最小值。​​

---

二、线性规划问题的基本构成

一个标准的线性规划问题通常由以下三个部分组成：

---

1️⃣ ​​决策变量（Decision Variables）​​

• •

  是我们需要确定的未知量，通常用 x1​,x2​,...,xn​表示

• •

  代表实际问题中的各种决策，比如生产数量、投资额度、运输量等

🔹 例如：生产产品A的数量为 x1​，产品B的数量为 x2​

---

2️⃣ ​​目标函数（Objective Function）​​

• •

  是我们要​​最大化或最小化​​的线性函数

• •

  通常表示为：

  Z=c1​x1​+c2​x2​+⋯+cn​xn​

其中 c1​,c2​,...,cn​是系数，表示每单位决策变量对目标的贡献

🔹 目标可以是：

• •

  ​​最大化​​：如利润、收益、效率

• •

  ​​最小化​​：如成本、时间、消耗

🔹 例如：

Max Z=3x1​+5x2​（求最大利润）

或

Min Z=2x1​+4x2​（求最小成本）

---

3️⃣ ​​约束条件（Constraints）​​

• •

  是对决策变量的一系列限制，通常是​​线性等式或不等式​​

• •

  包括：

  • •

    资源限制（如原材料、工时、资金）

  • •

    需求要求

  • •

    变量的非负限制（通常 xi​≥0）

🔹 一般形式为：

⎩⎨⎧​a11​x1​+a12​x2​+⋯+a1n​xn​≤b1​a21​x1​+a22​x2​+⋯+a2n​xn​≥b2​⋮x1​,x2​,…,xn​≥0​

🔹 例如：

• •

  生产产品A、B需要的总工时不超过 100 小时

• •

  使用的原材料不能超过库存

• •

  销售量不能为负数

---

三、线性规划的标准形式（简化版）

虽然实际问题可能形式多样，但为了求解方便，通常会将 LP 问题转化为如下​​标准形式​​：

目标：Max Z=c1​x1​+c2​x2​+⋯+cn​xn​

约束条件：⎩⎨⎧​a11​x1​+a12​x2​+⋯+a1n​xn​≤b1​a21​x1​+a22​x2​+⋯+a2n​xn​≤b2​⋮x1​,x2​,…,xn​≥0​

如果有 ≥ 约束，可以两边乘以 -1 变为 ≤；如果有等式约束，可以拆分为两个不等式；非负约束一般保留。

---

四、线性规划的求解方法

线性规划问题有多种求解算法，最著名的是：

---

1. ​​单纯形法（Simplex Method）​​ ⭐⭐⭐

• •

  由 George Dantzig 在 1947 年提出

• •

  是解决线性规划问题的​​经典算法​​

• •

  通过在可行域的顶点上逐步移动，找到使目标函数最优的解

• •

  适用于大多数 LP 问题，尤其在变量和约束不太大时效率很高

---

2. ​​内点法（Interior Point Method）​​

• •

  是一种较新的算法，尤其适合​​大规模线性规划问题​​

• •

  从可行域内部逐步逼近最优解，而不是沿着边界（顶点）走

---

3. ​​软件工具求解（推荐）​​

在实际应用、论文写作、数学建模竞赛中，我们通常​​不手算单纯形法​​，而是借助以下工具快速建模与求解：

工具	是否需要编程	特点
​​Excel 规划求解​​	否	简单易用，适合小型 LP 问题，直观展示
​​MATLAB​​	是（但简单）	内置 linprog函数，适合算法实现
​​Python（PuLP / SciPy / CVXPY）​​	是	强大灵活，适合建模与自动化求解
​​Lingo / Gurobi / CPLEX​​	是	专业优化软件，求解大规模 LP 极快，常用于学术研究与工业优化

🔹 ​​在数学建模竞赛（如美赛、国赛）中，常用 Excel、Python 或 Lingo 快速求解 LP 问题。​​

---

五、线性规划的应用场景（超实用！）

线性规划是应用最广泛的优化方法之一，几乎任何涉及​​“有限资源下如何最优配置”​​的问题都可以用 LP 建模，典型应用包括：

---

✅ 1. ​​生产计划问题​​

• •

  如何安排几种产品的生产数量，在有限原材料、工时下，使得利润最大？

✅ 2. ​​运输问题​​

• •

  多个供应商与多个需求点之间，如何安排运输方案，使得运输总成本最小？

✅ 3. ​​饮食搭配 / 营养问题​​

• •

  在一定预算和营养要求下，如何购买食物使得既健康又经济？

✅ 4. ​​投资组合 / 资金分配​​

• •

  有限的资金，如何分配到不同项目或资产，使得收益最大或风险最小？

✅ 5. ​​人力资源安排​​

• •

  如何安排员工工作时间，使得任务完成且总工资支出最小？

✅ 6. ​​混合问题（如生产 + 运输 + 库存）​​

• •

  多阶段、多环节的资源优化问题

---

六、线性规划的优点与局限性

---

✅ 优点：

1. 1.

   ​​模型简单、结构清晰​​：目标与约束都是线性的，易于理解和建模

2. 2.

   ​​求解高效​​：有成熟算法和软件工具，能快速得到最优解

3. 3.

   ​​应用广泛​​：几乎所有资源分配、优化类问题都可以尝试 LP 建模

4. 4.

   ​​结果明确​​：能给出最优解及其对应决策变量的具体数值

5. 5.

   ​​可拓展性强​​：是整数规划、非线性规划、动态规划等的基础

---

❌ 局限性：

1. 1.

   ​​要求线性关系​​：目标函数和约束必须是线性的，非线性问题无法直接使用

2. 2.

   ​​变量连续性假设​​：经典 LP 假设变量是连续的，若必须是整数（如设备台数、人数），则需要用​​整数线性规划（ILP）​​

3. 3.

   ​​对复杂系统建模有限​​：当问题涉及复杂逻辑、不确定性、动态过程时，LP 可能不再适用

---

七、举个实际例子（便于理解）

🎯 问题：工厂生产计划

某工厂生产两种产品 A 和 B，生产一个 A 需要 2 小时工时和 1 单位原料，生产一个 B 需要 1 小时工时和 2 单位原料。

• •

  工时总限制：100 小时

• •

  原料总限制：80 单位

• •

  A 的利润为 3 元/个，B 的利润为 4 元/个

​​问：如何安排 A 和 B 的产量，使得总利润最大？​​

---

🧮 建立线性规划模型：

• •

  ​​决策变量​​：

  x1​= 生产 A 的数量，x2​= 生产 B 的数量

• •

  ​​目标函数（最大化利润）​​：

  Max Z=3x1​+4x2​

• •

  ​​约束条件​​：

  ⎩⎨⎧​2x1​+x2​≤100x1​+2x2​≤80x1​≥0,x2​≥0​(工时限制)(原料限制)​

👉 你可以用 ​​Excel 规划求解、Python（PuLP）、Lingo、MATLAB​​ 等工具轻松求解这个模型，得到最优生产方案与最大利润值！

---

八、总结一句话：

​​线性规划（LP）是一种在给定线性约束条件下，通过调整决策变量使得某个线性目标函数达到最优（最大或最小）的数学优化方法，广泛应用于生产、运输、投资、资源配置等实际问题中，是运筹学与数学建模中最基础、最实用的优化工具之一。​​

---

✅ 类比熵权法介绍风格总结表：

项目	熵权法	线性规划（LP）
​​类型​​	多指标评价方法	数学优化方法
​​目的​​	确定各指标的客观权重	在限制条件下优化某个目标
​​核心思想​​	基于信息熵，反映指标数据离散程度来确定权重	在满足线性约束下，优化线性目标函数
​​输入​​	多指标数据矩阵	决策变量、目标函数、约束条件
​​输出​​	各指标权重 or 方案排序	最优解（决策变量的取值）与最优目标值
​​适用问题​​	综合评价类问题	资源配置、生产计划、投资决策等优化问题
​​是否需要优化​​	否（主要是计算权重）	是（求解最优解）
​​常用工具​​	Excel、Python、MATLAB	Excel、Python、Lingo、Gurobi、MATLAB

2-理论知识

介绍

原理

定义

应用

3-基于matlab实现线性规划

以这道题为例

源代码

%% 目标函数的系数列向量
%f = input('请输入目标函数的系数列向量：');
f = [-40;-30];
%% 不等式约束
% A = input('请输入不等式的系数矩阵：');
% b = input('请输入不等式的常数向量：');
% 因为按行写比按列写方便，所以这样写
A = [1 -1 0 240;1 0 -1 120];
% 把A转置一下
A = A';
b = [6 -1 -1 1200]';
%% 等式约束
% Aeq = input('请输入等式的系数矩阵：');
% beq = input('请输入等式的常数向量：');
Aeq = [];
beq = [];
%% 上下界约束
% lb = input('请输入上界约束：');
% ub = input('请输入下界约束：');
% 这道题没有上界，下界为0
lb = [0 0]';
ub = +Inf;
%% 计算目标函数的最小值value以及此时的x
[x,value] = linprog(f,A,b,Aeq,beq,lb,ub)

运行结果