一般的非线性规划求解(非凸函数)

例 5.5 (续例 5.3) 求解如下二次规划模型
$$\begin{array}{rl}& \min -x_1^2-0.3x_1{x}_2-2x_2^2+98x_1+277x_2\\ & \text{s.t.}\{\begin{array}{l}{x}_1+x_2\le 100,\\ x_1-2x_2\le 0,\\ x_1,x_2\ge 0.\end{array}\end{array}$$
由于上述二次规划的目标函数不是凸函数，不能使用 cvxpy 库进行求解。

使用 Python 软件求得的最优解为
$$x_1=0,x_2=0,$$
目标函数的最优值为 0。

计算的 Python 程序如下：

from scipy.optimize import minimize
import numpy as np# 定义目标向量
c1 = np.array([[-1, -0.15], [-0.15, -2]])
c2 = np.array([98, 277])
# 创建目标函数
obj = lambda x: x @ c1 @ x + c2 @ x
d = np.array([[1, 1], [1, -2]])
e = np.array([100, 0])
# 创建约束条件
constraints = {'type': 'ineq', 'fun': lambda x: e - d @ x}
bd = [(0, np.inf) for i in range(c1.shape[1])]
res = minimize(obj, np.random.randn(c1.shape[1]), constraints=constraints, bounds=bd)
print('最优解为：',np.round(res.x,4))
print('最优值为：',np.round(res.fun,4))

例 5.6 求下列非线性规划

$\min f(\mathbf{x})=x_1^2+x_2^2+x_3^2+8,$

s. t. $\{\begin{array}{l}{x}_1^2-x_2+x_3^2\ge 0,\\ x_1+x_2^2+x_3^3\le 20,\\ -x_1-x_2^2+2=0,\\ x_2+2x_3^2=3,\\ x_1,x_2,x_3\ge 0.\end{array}$

解 求得当 $x_1=0.5522,x_2=1.2033,x_3=0.9478$ 时，最小值 $y=10.6511$。

from scipy.optimize import minimize
import numpy as np# 定义目标函数
obj = lambda x: sum(x ** 2) + 8# 不等式约束函数
def constraint1(x):x1, x2, x3 = xreturn [x1 ** 2 - x2 + x3 ** 2,20 - x1 - x2 ** 2 - x3 ** 3]# 等式约束函数
def constraint2(x):x1, x2, x3 = xreturn [-x1 - x2 ** 2 + 2,x2 + 2 * x3 ** 2 - 3]# 定义约束条件
constraints1 = {'type': 'ineq', 'fun': constraint1}
constraints2 = {'type': 'eq', 'fun': constraint2}
constraints = [constraints1, constraints2]
# 边界值
bd = [(0,np.inf) for i in range(3)]
res = minimize(obj, np.random.randn(3), constraints=constraints, bounds=bd)
print('最优解为：', np.round(res.x, 4))
print('最优值为：', np.round(res.fun, 4))

例 5.7 求解下列规划问题
$$\begin{array}{rl}& \min z=|x_1|+2|x_2|+3|x_3|+4|x_4|,\\ & \text{s.t.}\{\begin{array}{l}{x}_1-x_2-x_3+x_4=0,\\ x_1-x_2+x_3-3x_4=1,\\ x_1-x_2-2x_3+3x_4=-\frac{1}{2}.\end{array}\end{array}$$

上述非线性规划问题是一个凸规划，可以使用 cvxpy 库求解，求得的最优解为 $ x_1 = 0.25 $, $ x_2 = x_3 = 0 $, $ x_4 = -0.25 $，目标函数的最优值为 1.25。

计算的 Python 程序如下：

import cvxpy as cp
import numpy as np# 定义变量
x = cp.Variable(4)# 定义目标向量
c = np.arange(1,5)
a = np.array([[1,-1,-1,1],[1,-1,1,-3],[1,-1,-2,3]])
b = np.array([0,1,-1/2])# 定义目标函数
obj = cp.Minimize(c @ cp.abs(x))
# 定义约束条件
constraints = [a @ x == b]
prob = cp.Problem(obj, constraints)
prob.solve(solver='GLPK_MI')
print('最优解为：',x.value)
print('最优值为：',prob.value)

例 5.8 (供应与选址) 建筑工地的位置（用平面坐标 $a,b$ 表示，距离单位：km）及水泥日用量 $c$ （单位：t）由表 5.4 给出。拟建两个料场向 6 个工地运送水泥，两个料场日储量各为 20t，问料场建在何处，使总的吨公里数最小。

表 5.4 建筑工地的位置及水泥日用量表

参数	工地 1	工地 2	工地 3	工地 4	工地 5	工地 6
$a/\mathrm{km}$	1.25	8.75	0.5	3.75	3	7.25
$b/\mathrm{km}$	1.25	0.75	4.75	5	6.5	7.75
$c/\mathrm{t}$	3	5	4	7	6	11

解 记第 $i$ 个工地的位置为 $(a_i,b_i)(i=1,2,\cdots ,6)$，水泥日用量为 $c_i$；拟建料场位置为 $(x_j,y_j)(j=1,2)$，日储量为 $e_j$，从料场 $j$ 向工地 $i$ 的运送量为 $z_{ij}$。

建立如下的非线性规划模型：
$$\begin{array}{rl}& \min \sum _{i=1}^6\sum _{j=1}^2{z}_{ij}\sqrt{(x_j-a_i{)}^2+(y_j-b_i{)}^2},\\ & \text{s.t.}\{\begin{array}{ll}{\sum }_{j=1}^2{z}_{ij}=c_i,& i=1,2,\cdots ,6,\\ {\sum }_{i=1}^6{z}_{ij}\le e_j,& j=1,2,\\ z_{ij}\ge 0,& i=1,2,\cdots ,6;j=1,2.\end{array}\end{array}$$
利用 Python 软件，求得拟建料场的坐标为 $ (3.2654, 5.1919) $，$ (7.25, 7.75) $。由两个料场向6个工地运料方案如表5.5所列,总的吨公里数为71.9352。

表 5.5 两个料场向6个工地运料方案

料 场	工地 1	工地 2	工地 3	工地 4	工地 5	工地 6
料场 1	0	5	0	0	0	11
料场 2	3	0	4	7	6	0

from scipy.optimize import minimize
import numpy as np# 读数据
data = np.loadtxt('建筑工地的位置及水泥日用量表.txt')
a = data[0];b = data[1];c = data[2]
e = np.array([20,20])# 定义目标函数
def obj(xyz):x = xyz[:2];y = xyz[2:4]z = xyz[4:].reshape(6, 2)obj = 0for i in range(6):for j in range(2):obj += z[i, j] * np.sqrt((x[j] - a[i]) ** 2 + (y[j] - b[i]) ** 2)return obj# 定义约束条件
construction = [{'type': 'eq', 'fun': lambda z: z[4:].reshape(6, 2).sum(axis=1) - c},{'type': 'ineq', 'fun': lambda z: e - z[4:].reshape(6, 2).sum(axis=0)}]# 边界
bd = [(0, np.inf) for i in range(16)]
res = minimize(obj, np.random.randn(16), constraints=construction, bounds=bd)
print('最优解为：', np.round(res.x, 4))
print('最优值为：', np.round(res.fun, 4))