问题描述

模型
分析

带有分段约束和max最值，导致使用一般的线性规划pulp问题进行求解会比较麻烦
如果将分段约束转化为0/1整数规划，其余变量 $u_i$ 未必还是整数，就涉及混整问题相对麻烦，所以考虑使用遗传算法进行求解

Python代码

import numpy as np
import matplotlib.pyplot as plt
from pylab import *mpl.rcParams['font.sans-serif'] = ['SimHei']
mpl.rcParams['axes.unicode_minus'] = False####################初始化参数#####################
NP = 50  # 种群数量
L = 2  # 对应x,y
Pc = 0.4  # 交叉率
Pm = 0.1  # 变异率
G = 100  # 最大遗传代数########################这里定义一些参数，分别是计算适应度函数和计算约束惩罚项函数############def calc_f(X, ri, qi,k):"""计算群体粒子的目标函数值， size * N(,size表示种群数，N表示决策变量个数) """if k==1:return sum((ri - qi) * X)elif k==2:lamda =0.5return lamda * sum(ri * X) - (1 - lamda) * sum(qi * qi * X * X)def calc_e(X, qi, pi, ki, Mi):"""计算群体粒子的目惩罚项，X 的维度是 size * N(,size表示种群数，N表示N表示决策变量个数为11) """sumcost = []C_X = []for i in range(X.shape[0]):C_X = []ee = 0"""计算第一个约束的惩罚项"""e1 = max(qi * X[i]) - 250ee += max(0, e1)"""计算第二个约束的惩罚项"""for j in range(X.shape[1]):if X[i, j] > Mi[j]:CX = ki[j] + pi[j] * X[i, j]C_X.append(CX)else:CX = ki[j] + pi[j] * Mi[j]C_X.append(CX)e2 = sum(X[i] + C_X) - 50000ee += max(0, e2)sumcost.append(ee)return sumcost##############遗传操作方法#########def select(X, fitness):"""根据轮盘赌法选择优秀个体"""fitness = 1 / fitness  # fitness越小表示越优秀，被选中的概率越大，做 1/fitness 处理fitness = fitness / fitness.sum()  # 归一化idx = np.array(list(range(X.shape[0])))X2_idx = np.random.choice(idx, size=X.shape[0], p=fitness)  # 根据概率选择X2 = X[X2_idx, :]return X2def crossover(X, c):"""按顺序选择2个个体以概率c进行交叉操作"""for i in range(0, X.shape[0], 2):parent1 = X[i].copy()  # 父亲parent2 = X[i + 1].copy()  # 母亲# 产生0-1区间的均匀分布随机数，判断是否需要进行交叉替换if np.random.rand() <= c:child1 = (1 - c) * parent1 + c * parent2  # 交叉子代child2 = c * parent1 + (1 - c) * parent2  # 交叉子代X[i, :] = child1X[i + 1, :] = child2return Xdef mutation(X, m):"""变异操作"""for i in range(X.shape[0]):  # 遍历每一个个体# 产生0-1区间的均匀分布随机数，判断是否需要进行变异parent = X[i].copy()  # 父辈if np.random.rand() <= m:child = np.random.uniform(0, 25, (1, 11))  # 用随机赋值的方式进行变异子代X[i] = childreturn X# 子代和父辈之间的选择操作
def update_best(parent, parent_fitness, parent_e, child, child_fitness, child_e):"""判:param parent: 父辈个体:param parent_fitness:父辈适应度值:param parent_e    ：父辈惩罚项:param child:  子代个体:param child_fitness 子代适应度值:param child_e  ：子代惩罚项:return: 父辈 和子代中较优者、适应度、惩罚项"""# 规则1，如果 parent 和 child 都没有违反约束，则取适应度小的if parent_e <= 0.0000001 and child_e <= 0.0000001:if parent_fitness <= child_fitness:return parent, parent_fitness, parent_eelse:return child, child_fitness, child_e# 规则2，如果child违反约束而parent没有违反约束，则取parentif parent_e < 0.0000001 and child_e >= 0.0000001:return parent, parent_fitness, parent_e# 规则3，如果parent违反约束而child没有违反约束，则取childif parent_e >= 0.0000001 and child_e < 0.0000001:return child, child_fitness, child_e# 规则4，如果两个都违反约束，则取适应度值小的if parent_fitness <= child_fitness:return parent, parent_fitness, parent_eelse:return child, child_fitness, child_edef ga_answer1(ri, qi, pi, ki, Mi,k):"""遗传算法主函数"""best_fitness = []  # 记录每次迭代的效果best_U = []  # 存放最优Uf = np.random.uniform(0, 25, (NP, 11))  # 初始化种群for i in range(G):  # 遍历每一次迭代fitness = np.zeros((NP, 1))  # 存放适应度值ee = np.zeros((NP, 1))  # 存放惩罚项值parentfit = calc_f(f, ri, qi,k)  # 计算父辈目标函数值parentee = calc_e(f, qi, pi, ki, Mi)  # 计算父辈惩罚项parentfitness = parentfit + parentee  # 计算父辈适应度值   适应度值=目标函数值+惩罚项X2 = select(f, parentfitness)  # 选择X3 = crossover(X2, Pc)  # 交叉X4 = mutation(X3, Pm)  # 变异childfit = calc_f(X4, ri, qi,k)  # 子代目标函数值childee = calc_e(X4, qi, pi, ki, Mi)  # 子代惩罚项childfitness = childfit + childee  # 子代适应度值# 更新群体for j in range(NP):  # 遍历每一个个体X4[j], fitness[j], ee[j] = update_best(f[j], parentfitness[j], parentee[j], X4[j], childfitness[j],childee[j])best_fitness.append(fitness.min())U = X4[fitness.argmin()]best_U.append(U)f = X4# 多次迭代后的最终效果portfolio_optimal_value = -min(best_fitness)portfolio_optimal_solution = best_U[best_fitness.index(min(best_fitness))]print("最优值是：", -min(best_fitness))  # best_fitness记录最优值print("最优解是：", best_U[best_fitness.index(min(best_fitness))])  # best_U记录最优解集return portfolio_optimal_solution# 第一问答案
ri = np.array([3.5, 5.4, 4.5, 6.7, 7.7, 8.8, 8, 6.5, 7.3, 9.1, 2.3]);
qi = np.array([11, 12, 25, 25, 19, 33, 32, 31, 33, 34, 0]);
pi = np.array([0.12, 0.15, 0.15, 0.2, 0.11, 0.13, 0.18, 0.2, 0.25, 0.2, 0]);
ki = np.array([0.1, 0.2, 0.1, 0.2, 0.1, 0.2, 0.1, 0.2, 0.3, 0.2, 0]);
Mi = np.array([50, 50, 100, 50, 100, 50, 100, 50, 100, 100, 0]);
k=1
ga_answer1(ri, qi, pi, ki, Mi,k)

结果

优缺点

优点：可以解决带分段约束的线性规划问题，当然也可以将非线性的分段约束规划转化为0/1规划，然后再利用 $u_i$ 和 $w_1$ 、 $w_2$ 和 $w_3$ 关系，将其余 $u_i$ 都用 $w_1$ 、 $w_2$ 和 $w_3$ 表示，没有试过，不过可以尝试一下
缺点：遗传算法不是唯一解，变异率、变异率等参数可以调整一下，交叉和变异处可以更改交叉和变异规则，会得到不一样的效果