【数学建模】线性规划问题求解

线性规划

建立线性规划模型的步骤：

1. 分析问题，找出决策变量
2. 根据问题的条件，找出决策变量必须满足的一组线性等式或不等式约束（即约束条件）
3. 根据问题的目标，构建目标函数（关于决策目标的线性函数）

线性规划模型的形式

一般形式

$$ max(或min)z=\sum_{j=1}^{n}c_j x_j\\ s.t.\begin{cases} \sum_{j=1}^{n}a_{ij} \leq(或=,\geq)b_i, i =1,2,\cdots m\\ x_j\geq0,j=1,2,\cdots n \end{cases} $$

向量形式

$$ max(或min)z=c^Tx\\ s.t.\begin{cases} \sum_{j=1}^{n}P_jx_j\leq(或=,\geq)b, x\geq0. \end{cases} $$

矩阵形式

$$ \begin{gather} max(或min)z=c^Tx \\ s.t.\begin{cases} A_x\leq(或=,\geq)b, x\geq0. \end{cases} \end{gather} $$

例题

求解下列线性规划问题：
$$
\begin{gather}
max z = 3x_1-x_2-x_3\
s.t.\begin{cases}
x_1-2x_2+x_3\leq11,\
-4x_1+x_2+2x_3\geq3,\
-2x_1+x_3 = 1,\
x_1,x_2,x_3\leq0.
\end{cases}
\end{gather}
$$

解：

1. 问题分析

目标函数为$z=3x_1-x_2-x_3$.
在scipy.optimize.linprog()函数中默认取最小值，则需要对目标函数系数取相反数。
即c = [-3,1,1].

约束条件：

• 不等式约束矩阵
• 等式约束矩阵
• 变量边界

1. 分析问题
   • 目标函数是(z = 3x_1 - x_2 - x_3)，在scipy.optimize.linprog中默认是求最小值，所以要将目标函数系数取负，即(c = [-3,1,1])。
   • 约束条件：
     • 不等式约束(x_1 - 2x_2 + x_3\leqslant11)和(-4x_1 + x_2 + 2x_3\geqslant3)，将(-4x_1 + x_2 + 2x_3\geqslant3)变形为(4x_1 - x_2 - 2x_3\leqslant - 3)，得到不等式约束矩阵(A=\begin{bmatrix}1& - 2&1\4&-1& - 2\end{bmatrix})，向量(b = [11,-3])。
     • 等式约束(-2x_1+x_3 = 1)，等式约束矩阵(Aeq=\begin{bmatrix}-2&0&1\end{bmatrix})，向量(beq = [1])。
     • 变量(x_1,x_2,x_3\geqslant0)，即变量边界(bounds = [(0, None),(0, None),(0, None)])。
2. 代码实现

import numpy as np
from scipy.optimize import linprog

# 目标函数系数（取负以将最大化问题转化为最小化问题）
c = np.array([-3, 1, 1])
# 不等式约束矩阵A和向量b
A = np.array([[1, -2, 1], [4, -1, -2]])
b = np.array([11, -3])
# 等式约束矩阵Aeq和向量beq
Aeq = np.array([[-2, 0, 1]])
beq = np.array([1])
# 变量边界
bounds = [(0, None), (0, None), (0, None)]

result = linprog(c, A_ub=A, b_ub=b, A_eq=Aeq, b_eq=beq, bounds=bounds)

if result.success:
    print("最优解：", result.x)
    print("目标函数最大值：", -result.fun)
else:
    print("求解失败")

3. 代码解释
   • 首先导入numpy和scipy.optimize中的linprog函数。
   • 定义目标函数系数向量c，不等式约束矩阵A和向量b，等式约束矩阵Aeq和向量beq，以及变量边界bounds。
   • 调用linprog函数进行求解，A_ub和b_ub用于指定不等式约束，A_eq和b_eq用于指定等式约束。
   • 根据求解结果的success属性判断是否求解成功，如果成功，输出最优解和目标函数最大值（因为之前将目标函数系数取负，所以这里要将result.fun取负得到原目标函数的最大值）。