吴世涵的博客
0%

【数学建模笔记 01】数学建模的线性规划

发表于 分类于
本文字数： 1.5k 阅读时长 ≈ 1 分钟
线性规划是数学建模中常见的问题之一，本文主要介绍线性规划的定义、形式、例子等内容，并给出了 Python 代码实现。

01. 线性规划

定义

线性规划，就是在一组线性约束条件的限制下，求一线性目标函数最大或最小的问题。

线性规划由三部分组成：

  • 决策变量
  • 目标函数
  • 约束条件

形式

编程中，线性规划的标准形式为：

其中 为 ​ 维列向量， 为适当维数的矩阵， 为适当维数的列向量。

例子

如对于下列线性规划问题：

对于目标函数

化为矩阵形式有：

注意到原目标函数求最大值，因此转换为求最小值后取反。

对于约束条件中的不等式

化为矩阵形式有：

注意到最终要求左边小于等于右边，因此对于原为大于或大于等于的不等式要先取反。

对于约束条件中的等式

化为矩阵形式有：

对于约束条件中的取值范围

化为矩阵形式有： ### Python 代码

使用 python 的求解代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# %%

import numpy as np
from scipy.optimize import linprog

# %%

# 目标函数形如 min c^T·x
c = np.array([2, 3, -5])

# 不等式约束形如 A·x <= b
A = np.array([[-2, 5, -1],
              [1, 3, 1]])
b = np.array([-10, 12])

# 等式约束形如 Aeq·x = beq
Aeq = np.array([[1, 1, 1]])
beq = np.array([7])

# 取值范围约束形如 lb <= x <= ub
lb = np.array([0, 0, 0])
ub = np.array([None, None, None])
bound = tuple(zip(lb, ub))

res = linprog(c, A, b, Aeq, beq, bound)
print('min y =', res.fun)
print('x =', res.x)

输入如下：

1
2
min y = -14.000000657683218
x = [2.99999979e+00 1.04988686e-08 4.00000005e+00]

于是解得：

​ 时，目标函数取得最大值 14.