数学建模 算法与应用 （python实现）第一章 线性规划

第一章 线性规划

线性规划问题：

目标函数和约束条件均为线性函数时的问题，成为线性规划问题

线性规划的一般模型

$$\begin{gathered} maxz=\sum _{j=1}^n{c}_j{x}_j \\ s.t.\{\begin{array}{l}{\sum }_{j=1}^n{a}_{ij}{x}_j\le b\\ x\ge 0,j=1,2,...,n\end{array} \end{gathered}$$

• 可行解：满足约束的解$x=[x_1,...,x_n{]}^T$

• 可行域：所有可行解构成的集合，记作$R$

线性规划的软件求解

为规范，将线性规划的标准形式定为：
$$\begin{gathered} \min c^{T}x, \\ s.t.?\begin{array}{l}{A}_{up}?x=b_{Up}\\ A_{eq}?x=b_{eq}\\ lb\le x\le ub\end{array} \end{gathered}$$
python代码如下，其中$r$为解：

import numpy as np
from scipy.optimize import linprogc = np.array([-2, -3, +5])
A_up = np.array([[-2, 5, -1], [1, 3, 1]])
b_up = np.array([-10, 12])
A_eq = np.array([[1, 1, 1]])
b_eq = np.array([7])r = linprog(c, A_up, b_up, A_eq, b_eq, bounds=((0, None), (0, None), (0, None)))print(r)

运行结果实例：

     con: array([1.80711979e-09])fun: -14.571428565645085message: 'Optimization terminated successfully.'nit: 5slack: array([-2.24563479e-10,  3.85714286e+00])status: 0success: Truex: array([6.42857143e+00, 5.71428571e-01, 2.35900788e-10])

例:

求解下列线性规划问题：
$$\begin{gathered} \min z=2x_1+3x_2+x \\ s.t.?\begin{array}{l}{x}_1+4x_2+2x_3\ge 8\\ 3x_1+2x_2\ge 6\\ x_1,x_2,x_3\ge 0\end{array} \end{gathered}$$
将线性规划转化成以下形式：
$$\begin{gathered} \min z=2x_1+3x_2+x \\ s.t.?\begin{array}{l}\left[\begin{array}{ccc}?1& ?4& ?2\\ ?3& ?2& 0\end{array}\right]?\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}?\le \left[\begin{array}{c}?8\\ ?6\end{array}\right]\\ x_1,x_2,x_3\ge 0\end{array} \end{gathered}$$
python代码如下：

import numpy as np
from scipy.optimize import linprogc = np.array([2, 3, 1])
A_up = np.array([[-1, -4, -2], [-3, -2, 0]])
b_up = np.array([-8, -6])r = linprog(c, A_ub=A_up, b_ub=b_up, bounds=((0, None), (0, None), (0, None)))print(r)

结果：

     con: array([], dtype=float64)fun: 6.999999994872991message: 'Optimization terminated successfully.'nit: 3slack: array([ 3.85261067e-09, -1.41066305e-08])status: 0success: Truex: array([1.17949641, 1.23075538, 0.94874104])

注：scipy的优化函数有限，在精度和优化程度上可能比不上专业优化软件MATLAB，Lingo等。

可转化为线性规划的问题

数学规划问题：
$$\begin{gathered} \min |x_1|+|x_2|+...+|x_n| \\ s.t.Ax\le b \end{gathered}$$

例：

求解下列数学规划问题：
$$\begin{gathered} \min z=|x_1|+2|x_2|+3|x_3|+4|x_4| \\ s.t.?\begin{array}{l}{x}_1?x_2?x_3+x_4\le ?2,\\ x_1?x_2+x_3?3x_4\le ?1,\\ x_1?x_2?2x_3+3x_4\le ?\frac{1}{2}\end{array} \end{gathered}$$
将变量变换$u_i=\frac{x_i+|x_i|}{2},v_i=\frac{|x_i|?x_i}{2}$，则可把模型变换为：
$$\begin{gathered} \min c^{T}y, \\ s.t.?\begin{array}{l}[A,?A]\left[\begin{array}{c}u\\ v\end{array}\right]\le b\\ u,v\ge 0\end{array} \end{gathered}$$