6.1 整数规划
在线性规划模型中，决策变量只需取连续型数值即可．但还有大量的实际问题，虽然形式上与线性规划类似，却增加了某些约束条件，要求部分甚至全部决策变量必须取离散的非负整数值才有意义．对于限制全部或部分决策变量取离散非负整数值的线性规划，称之为整数线性规划，简称为整数规划．在整数规划中，如果所有决策变量都限制为整数，则称为纯整数规划；如果仅一部分变量限制为整数，则称为混合整数规划，整数规划的一种特殊情形是0-1整数规划，它的决策变量仅限于0或1，也分为纯0-1整数规划和混合0-1整数规划两种形式
由于cxvpy库安装繁琐，此部分待补。
6.2 非线性规划 6.2.1 非线性规划的Python求解
用scipy.optimize模块的minimize函数求解：
scipy.optimize.minimize(fun, x0, args=(), method=None, jac=None, hess=None, hessp=None, bounds=None, constraints=(), tol=None, callback=None, options=None)
- fun：目标函数
- x0：初步猜测，是一个有n个元素的数组
- bounds：参数的上下界范围
- constrains：约束条件，分为“等式”、“不等式”两种
（scipy.optimize.minimize部分内容参考自python数学建模之用scipy.optimize.minimize解决高次非线性规划问题）
例6.2.1 求解非线性规划问题：（无约束）
解：Python程序如下：
from scipy.optimize import minimize
from numpy import ones
def obj(x):
x1, x2, x3 = x
return (2+x1)/(1+x2)-3*x1+4*x3
LB = [0.1]*3
UB = [0.9]*3
bound = tuple(zip(LB, UB)) # 生成决策向量界限的元组
res = minimize(obj, ones(3), bounds=bound) # 第二个参数为初值
print(res.fun, 'n', res.success, 'n', res.x) # res.success表示是否成功
输出结果如下：
-0.7736842105263159 True [0.9 0.9 0.1]
注：在以下语句中，ones(3)给定了三个初值，相对应地，
res = minimize(obj, ones(3), bounds=bound)
传入obj函数的是一个有3个元素的一维ndarray，在def()中的语句
x1, x2, x3 = x
恰好将x的三个元素分别赋值给x1，x2，x3
例6.2.2 求解非线性规划问题：（有约束）
解：Python程序如下：
from scipy.optimize import minimize
import numpy as np
c1 = np.array([1, 1, 3, 4, 2])
c2 = np.array([-8, -2, -3, -1, -2])
A = np.array([[1, 1, 1, 1, 1], [1, 2, 2, 1, 6], [2, 1, 6, 0, 0], [0, 0, 1, 1, 5]])
b = np.array([400, 800, 200, 200])
obj = lambda x: np.dot(-c1, x**2)+np.dot(-c2, x)
cons = {'type': 'ineq', 'fun': lambda x: b-A@x}
bd = [(0, 99) for i in range(A.shape[1])]
res = minimize(obj, np.ones(5)*90, constraints=cons, bounds=bd)
print(res)
输出结果如下：
fun: -51629.92995523618
jac: array([ -93. , -196. , 3. , -791. ,
-78.80029297])
message: 'Optimization terminated successfully'
nfev: 20
nit: 4
njev: 3
status: 0
success: True
x: array([5.05000000e+01, 9.90000000e+01, 1.98182086e-10, 9.89999999e+01,
2.02000000e+01])
注：
- numpy.dot：向量内积（此处c1，c2，x都是一维的，因此是向量内积）或矩阵乘法
- 在对obj定义时，x是一个一维ndarray，因此x**2是对x中的每个元素进行平方
- 矩阵之间用@连接代表矩阵相乘（详见python中矩阵、数组使用@的含义）
- numpy.array.shape == (row, column)
- cons中约束条件默认为“表达式 ≧ 0”或“表达式 = 0”
- 如果不使用numpy库，可以用Python自带数组；或约束条件中既有等式也有不等式，也可以不按照本例代码写，参考python数学建模之用scipy.optimize.minimize解决高次非线性规划问题
计算和的Python代码如下：
import numpy as np
import pandas as pd
x0 = np.array([150, 85, 150, 145, 130, 0])
y0 = np.array([140, 85, 155, 50, 150, 0])
q = np.array([243, 236, 220.5, 159, 230, 52])
d = np.zeros((6, 6))
a0 = np.zeros((6, 6))
b0 = np.zeros((6, 6))
xy0 = np.c_[x0, y0]
for i in range(6):
for j in range(6):
d[i, j] = np.linalg.norm(xy0[i]-xy0[j]) # 两飞机之间距离
d[np.where(d == 0)] = np.inf
a0 = np.arcsin(8./d)*180/np.pi
xy1 = x0+1j*y0
xy2 = np.exp(1j*q*np.pi/180)
for m in range(6):
for n in range(6):
if n != m:
b0[m, n] = np.angle((xy2[n]-xy2[m])/(xy1[m]-xy1[n]))
b0 = b0*180/np.pi
f = pd.ExcelWriter('Plane.xlsx')
pd.DataFrame(a0).to_excel(f, "sheet1", index=None) # 把a0写入Excel的表单1
pd.DataFrame(b0).to_excel(f, "sheet2", index=None) # 把a0写入Excel的表单2
f.save()
输出结果如下：
表6.1 的值
表6.2 的值
注：
- np.linalg.norm：用来求两点之间距离（详细用法参考np.linalg.norm(求范数)）
- np.where：条件判断语句，满足则进行后续语句（详细用法参考np.where()的使用方法）
- np.inf：表示无穷大（详细用法参考NumPy库—NAN和INF值）
- np.angel：计算复数幅角（详细用法参考numpy.angle详解）
-
np.sum：用于矩阵求和（详细用法参考Python_np.sum()函数）
求最优解Python程序如下：
import numpy as np
import pandas as pd
from scipy.optimize import minimize
a0 = pd.read_excel("Plane.xlsx") # 读入第1表单
b0 = pd.read_excel("Plane.xlsx", 1) # 读入第2个表单
a0 = a0.values # 提取数值
b0 = b0.values
obj = lambda x: np.sum(np.abs(x))
bd = [(-30, 30) for i in range(6)] # 决策向量的界限
cons = []
for i in range(5):
for j in range(i+1, 6):
cons.append({'type': 'ineq', 'fun': lambda x: np.abs(b0[i, j]+(x[i]+x[j])/2)-a0[i, j]})
res = minimize(obj, np.ones(6), constraints=cons, bounds=bd)
print(res)
输出结果如下：
fun: 0.7909172985328354
jac: array([-1., -1., -1., -1., 1., 1.])
message: 'Optimization terminated successfully'
nfev: 54
nit: 6
njev: 6
status: 0
success: True
x: array([2.53262997e-07, 2.53262998e-07, 2.53262998e-07, 2.53262998e-07,
3.95458143e-01, 3.95458143e-01])
求得最优解为5号飞机偏转0.3955°，6号飞机偏转0.3955°，其他飞机不偏转，总偏转角度为0.7909°。
暑期编程PK赛 得CSDN机械键盘等精美礼品！
