概述#

模型#

Python中的线性规划求解#

本部分内容引自《数学建模算法与应用》

求解如下的线性规划问题：

min \quad z = 2x_1+3x_2+x_3

\begin{aligned} s.t. \quad x_1+x_2+x_3&=7 \\\ x_1+4x_2+2x_3&\geq8 \\\ 3x_1+2x_2&\geq6 \\\ x_1,x_2,x_3&\geq0 \end{aligned}

用Python进行线性规划求解时，

1
import numpy as np
2
from scipy import optimize
3

4
z = np.array([2, 3, 1])
5
a = np.array([[1, 4, 2], [3, 2, 0]]
6
b = np.array([8, 6])
7
a_eq = np.array([[1, 1, 1]])
8
b_eq = np.array([7])
9
x1_bound = x2_bound = x3_bound = (0, None)
10
bounds = (x1_bound, x2_bound, x3_bound)
11

12
res = optimize.linprog(z, A_ub=-a, b_ub=-b, A_eq=a_eq, b_eq=b_eq, bounds=bounds)
13
print(res)

Python中的非线性规划求解#

详见scipy的官方文档。

考虑如下的非线性规划问题：

计算 $(2+x_1)/(1+x_2)-3x_1+4x_3$ 的最小值，这里对任意 $x_i$ 均有 $0.1<x_i<0.9$ 成立。

Python代码如下：

1
import numpy as np
2
from scipy import optimize
3

4
# 定义目标函数
5
def func1(nums):
6
    a, b, c, d = nums
7
    def _func0(x):
8
        y = (a+x[0])/(b+x[1]) - c*x[0] + d*x[2]
9
  return y
10
    return _func0
11

12
# 有两种方法表示约束
13
def cons1(nums):
14
    # 'eq'表示等式，'ineq'表示大于等于
15
    x1_min, x1_max, x1_min, x2_max, x3_min, x3_max = nums
16
    _cons = ({'type':'ineq', 'fun':lambda x: x[0]-x1_min},
17
             {'type':'ineq', 'fun':lambda x: x1_max-x[0]}，
18
       {'type':'ineq', 'fun':lambda x: x[1]-x2_min},
19
       {'type':'ineq', 'fun':lambda x: x2_max-x[1]},
20
       {'type':'ineq', 'fun':lambda x: x[2]-x3_min},
21
       {'type':'ineq', 'fun':lambda x: x3_max-x[2]})
22
    return _cons
23

24
# 法2
25
bouds = []
26
for k in range(3):
27
    # 'None'为不限制
28
    bounds.append((0.1, 0.9))
29

30
args = [2, 1, 3, 4]
31
x0 = np.array([0.5, 0.5, 0.5])
32
res = optimize.minimize(func1(args), x0=x0, constraints=cons1([.1, .9]*3), bounds=bounds)
33
print(res)
34

35
# res.x = [0.9, 0.9, 0.1
36
# res.success = True]