python代码实现Bottleneck Generalized Assignment Problems

2024-03-30 15:12

本文主要是介绍python代码实现Bottleneck Generalized Assignment Problems,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Bottleneck Generalized Assignment Problems

参考文献:Mazzola J B, Neebe A W. Bottleneck generalized assignment problems[J]. Engineering Costs and Production Economics, 1988, 14(1): 61-65.

实现的总体思路:

1初始化相关的输入数据
2 根据cij与ck的关系建立新的TGBAP(K)问题
3 找到Z的下限,从这个下限开始往更大的数方向寻找
4 TGBAP(K)是否存在可行解,如果不存在的话,继续往下个数找,直到找到一个可行的TGBAP(K)
5 输出这个可行方案和对应的最小最大时间

上代码

详细的数据集见github地址https://github.com/yasuoman/BGAP

# project : BGAP
# file   : TBGAP.py
# author:yasuoman
# datetime:2024/3/27 11:31
# software: PyCharm"""
description:
说明:
"""
# 参考的文献Mazzola J B, Neebe A W. Bottleneck generalized assignment problems[J].
# Engineering Costs and Production Economics, 1988, 14(1): 61-65.
#且实现的是TBGAP# 实现的总体思路:
# 1初始化相关的输入数据
# 2 根据cij与ck的关系建立新的TGBAP(K)问题
# 3 找到Z的下限,从这个下限开始往更大的数方向寻找
# 4 TGBAP(K)是否存在可行解,如果不存在的话,继续往下个数找,直到找到一个可行的TGBAP(K)
# 5 输出这个可行方案和对应的最小最大时间
import numpy as np#这里是相关的数据集,输出相关的数据和变量
def construct_dataset():m, n = 5, 10# 运行成本矩阵cost_matrix = np.array([[36,102,35,31,18,25,30,76,108,82],[61,75,69,19,45,97,117,74,35,85],[34,79,26,114,27,44,25,76,93,89],[17,97,65,51,81,82,89,40,21,95],[70,7,74,79,74,44,52,94,107,108]])## cost_matrix = np.array(#     [[36, 102, 35, 31, 18, 25, 30, 76, 108, 65],#      [61, 75, 69, 19, 45, 97, 117, 74, 35, 85],#      [34, 79, 26, 114, 27, 44, 25, 76, 93, 76],#      [17, 97, 69, 51, 81, 82, 89, 40, 21, 95],#      [70, 7, 74, 79, 74, 44, 52, 94, 107, 108]])# 资源需求矩阵resource_matrix = np.array([[78,14,82,70,87,93,78,34,7,36],[59,28,40,89,69,21,3,32,70,33],[72,40,95,6,85,60,94,25,9,29],[96,16,34,57,39,29,20,62,95,16],[39,98,33,24,45,61,59,7,12,12]])# resource_matrix = np.array(#     [[78, 14, 82, 70, 87, 93, 78, 34, 7, 36],#      [59, 28, 40, 89, 69, 21, 3, 32, 70, 33],#      [72, 40, 95, 6, 85, 60, 94, 25, 9, 29],#      [96, 16, 34, 57, 39, 29, 20, 62, 95, 16],#      [39, 98, 33, 24, 45, 61, 59, 7, 12, 12]])# 机器资源容量向量capacity_vector = np.array([93,71,82,74,62])return m,n,cost_matrix,resource_matrix,capacity_vector
#这里是对http://www.al.cm.is.nagoya-u.ac.jp/~yagiura/gap/ 的a20100数据集进行简单的测试
#目前没有优化这组数据集的读取,只是写了个示例。有需要可以自行写这里的代码
# def construct_dataset():
#     with open('Data/gap_a/a20100', 'r') as file:
#         #先随便写着
#         import re
#         # 读取文件内容
#         content = file.read()
#         # words = content.split(' ')
#         words= re.split(r'[ ,\n]+', content)
#
#         m,n = int(words[1]),int(words[2])
#         c_list = words[3:2003]
#         r_list = words[2003:4003]
#         cap_list = words[4003:4023]
#         c_int_list = [int(item) for item in c_list]
#         r_int_list = [int(item) for item in r_list]
#         cap_int_list = [int(item) for item in cap_list]
#         cost_matrix = np.array(c_int_list).reshape(m, n)
#         resource_matrix = np.array(r_int_list).reshape(m, n)
#         capacity_vector =np.array(cap_int_list)
#         return m, n, cost_matrix, resource_matrix, capacity_vector#输入resource_matrix、cost_matrix、capacity_vector和初始的k,输出新的resource_matrix矩阵
def reconstruct_resource_matrix(resource_matrix, cost_matrix, capacity_vector,k):import copycopy_resource_matrix =copy.deepcopy(resource_matrix)# 使用fancy indexing来更新矩阵mask = k < cost_matrix# resource_matrix[mask] = 9999copy_resource_matrix[mask] = max(capacity_vector)return copy_resource_matrix#输入新的resource_matrix矩阵和capacity_vector,输出一组可行解或输出FALSE,借用Pulp包求解
def find_soulution(resource_matrix,capacity_vector,m,n):import pulp# 创建问题实例prob = pulp.LpProblem("Machine_Assignment", pulp.LpMinimize)# 二元决策变量x = pulp.LpVariable.dicts("x", ((i, j) for i in range(m) for j in range(n)),cat=pulp.LpBinary)# 目标函数:这里我们只需要找到可行解,因此可以设置一个任意的目标函数prob += 0# 约束条件# 1每个工件只能在一个机器上运行for j in range(n):prob += sum(x[(i, j)] for i in range(m)) == 1# 2每个机器的资源需求之和不能大于资源容量for i in range(m):prob += sum(resource_matrix[i][j] * x[(i, j)] for j in range(n)) <= capacity_vector[i]# 求解问题# status = prob.solve()status = prob.solve(pulp.PULP_CBC_CMD(msg=False))# 输出结果if pulp.LpStatus[status] == 'Optimal':solution = [0] * nfor i in range(m):for j in range(n):if pulp.value(x[(i, j)]) == 1:solution[j] = i + 1  # 机器编号从1开始return solutionelse:# 无法找到可行解return Falsedef main():#得到数据m, n, cost_matrix, resource_matrix, capacity_vector = construct_dataset()# 构建待遍历的数组# 得到目标函数的下界 max min(cij), 找到每一列的最小值min_values = np.min(cost_matrix, axis=0)# 从最小值中找到最大值max_of_mins = np.max(min_values)#对矩阵进行排序并去重,得到一维数组ckck= np.unique(np.sort(cost_matrix, axis=None))# 截取从下界开始到数组ck末尾的数据,保存到新的数组new_ck中new_ck = ck[ck >= max_of_mins]# object_value = new_ck[0]#遍历去找for i,k in np.ndenumerate(new_ck):new_resource_matrix =reconstruct_resource_matrix(resource_matrix, cost_matrix, capacity_vector, k)solution = find_soulution(new_resource_matrix,capacity_vector,m,n)if solution != False:print("第"+str(i)+"次,分配方案为:",solution,"最优运行时间为:",k)breakelse:print("第"+str(i)+"次,最优运行时间的分配方案"+str(k)+"不存在")if __name__ == "__main__":main()

这篇关于python代码实现Bottleneck Generalized Assignment Problems的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/861820

相关文章

java之Objects.nonNull用法代码解读

《java之Objects.nonNull用法代码解读》:本文主要介绍java之Objects.nonNull用法代码,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录Java之Objects.nonwww.chinasem.cnNull用法代码Objects.nonN

Python如何使用__slots__实现节省内存和性能优化

《Python如何使用__slots__实现节省内存和性能优化》你有想过,一个小小的__slots__能让你的Python类内存消耗直接减半吗,没错,今天咱们要聊的就是这个让人眼前一亮的技巧,感兴趣的... 目录背景:内存吃得满满的类__slots__:你的内存管理小助手举个大概的例子:看看效果如何?1.

Python+PyQt5实现多屏幕协同播放功能

《Python+PyQt5实现多屏幕协同播放功能》在现代会议展示、数字广告、展览展示等场景中,多屏幕协同播放已成为刚需,下面我们就来看看如何利用Python和PyQt5开发一套功能强大的跨屏播控系统吧... 目录一、项目概述:突破传统播放限制二、核心技术解析2.1 多屏管理机制2.2 播放引擎设计2.3 专

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2

Python实现无痛修改第三方库源码的方法详解

《Python实现无痛修改第三方库源码的方法详解》很多时候,我们下载的第三方库是不会有需求不满足的情况,但也有极少的情况,第三方库没有兼顾到需求,本文将介绍几个修改源码的操作,大家可以根据需求进行选择... 目录需求不符合模拟示例 1. 修改源文件2. 继承修改3. 猴子补丁4. 追踪局部变量需求不符合很

idea中创建新类时自动添加注释的实现

《idea中创建新类时自动添加注释的实现》在每次使用idea创建一个新类时,过了一段时间发现看不懂这个类是用来干嘛的,为了解决这个问题,我们可以设置在创建一个新类时自动添加注释,帮助我们理解这个类的用... 目录前言:详细操作:步骤一:点击上方的 文件(File),点击&nbmyHIgsp;设置(Setti

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

MySQL大表数据的分区与分库分表的实现

《MySQL大表数据的分区与分库分表的实现》数据库的分区和分库分表是两种常用的技术方案,本文主要介绍了MySQL大表数据的分区与分库分表的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有... 目录1. mysql大表数据的分区1.1 什么是分区?1.2 分区的类型1.3 分区的优点1.4 分

一文详解如何从零构建Spring Boot Starter并实现整合

《一文详解如何从零构建SpringBootStarter并实现整合》SpringBoot是一个开源的Java基础框架,用于创建独立、生产级的基于Spring框架的应用程序,:本文主要介绍如何从... 目录一、Spring Boot Starter的核心价值二、Starter项目创建全流程2.1 项目初始化(

Mysql删除几亿条数据表中的部分数据的方法实现

《Mysql删除几亿条数据表中的部分数据的方法实现》在MySQL中删除一个大表中的数据时,需要特别注意操作的性能和对系统的影响,本文主要介绍了Mysql删除几亿条数据表中的部分数据的方法实现,具有一定... 目录1、需求2、方案1. 使用 DELETE 语句分批删除2. 使用 INPLACE ALTER T