Python实现分配问题常见求解算法——竞拍算法(Auction Algorithm)_拍卖算法python-程序员宅基地

技术标签: 指派问题  算法  python  

基于python语言,实现竞拍算法(Auction Algorithm)对分配(指派)问题(Assignment Problem)进行求解。

1. 适用场景

  • 单一分配问题
  • 完全分配问题

2. 案例

假设N个人对N个物品进行竞拍,每个人对每个物品的估值如下表。寻求使得整体利益最大化的分配策略。

商品B1 商品B2 商品B3 商品B4
竞拍者A1 4 8 17 10
竞拍者A2 14 18 17 7
竞拍者A3 9 5 14 10
竞拍者A4 17 18 14 6

3. 代码实现

(1)报价函数

#根据最新价格确定下一轮报价
def bidding(current_assignment,current_prices):
    new_bid={
    }
    for bidder in bidder_set:
        if bidder in current_assignment:
            continue
        #未竞拍到物品的继续报价
        else:
            v_ij=[]
            available_object_list=copy.deepcopy(available_objects_for_bidders[bidder])
            for object in available_object_list:
                v_ij.append(value_matrix[bidder,object]-current_prices[object])
            max_v=max(v_ij) #最大收益
            bid_target=available_object_list[v_ij.index(max_v)] #最大收益对象
            v_ij.remove(max_v)
            available_object_list.remove(bid_target)
            sub_max_v=max(v_ij) #次大收益
            bid_price=value_matrix[bidder,bid_target]-sub_max_v+epsilon #下次报价
            if bid_target in new_bid:
                new_bid[bid_target][0].append(bidder)
                new_bid[bid_target][1].append(bid_price)
            else:
                new_bid[bid_target]=[[bidder],[bid_price]]
    return new_bid

(2)分配函数

#根据最新报价重新分配竞拍结果
def assigning(bid_prices,current_assignment,current_prices):
    new_prices={
    }
    for object in object_set:
        #收到报价的物品重新竞拍
        if object in bid_prices:
            bidders,prices=bid_prices[object]
            max_price=max(prices)
            bidder=bidders[prices.index(max_price)]
            new_prices[object]=max_price
            for people,object_ in current_assignment.items():
                if object_ == object:
                    current_assignment.pop(people)
                    current_assignment[bidder]=object
                    break
            if bidder not in current_assignment:
                current_assignment[bidder]=object
        else:
            new_prices[object]=current_prices[object]
    return new_prices,current_assignment

(3)主函数

这里采用固定ε值,为提高效率也可采用变动值,具体可阅读文末参考1.

if __name__=='__main__':
    #价格矩阵
    value_matrix={
    
        ('A1', 'B1'): 4 , ('A1', 'B2'): 8 , ('A1', 'B3'): 17, ('A1', 'B4'): 10,
        ('A2', 'B1'): 14, ('A2', 'B2'): 18, ('A2', 'B3'): 17, ('A2', 'B4'): 7,
        ('A3', 'B1'): 9 , ('A3', 'B2'): 5 , ('A3', 'B3'): 14, ('A3', 'B4'): 10,
        ('A4', 'B1'): 17, ('A4', 'B2'): 18, ('A4', 'B3'): 14, ('A4', 'B4'): 6,
    }
    #竞拍者集合
    bidder_set=['A1','A2','A3','A4']
    #竞拍对象集合
    object_set = ['B1', 'B2', 'B3', 'B4']
    #每个竞拍者可竞拍对象集合
    available_objects_for_bidders={
    
        'A1': ['B1', 'B2', 'B3', 'B4'],
        'A2': ['B1', 'B2', 'B3', 'B4'],
        'A3': ['B1', 'B2', 'B3', 'B4'],
        'A4': ['B1', 'B2', 'B3', 'B4'],
    }
    #初始竞拍结果(满足ε互补松弛条件)
    current_assignment = {
    'A1': 'B3', 'A2': 'B2'}
    #初始报价
    current_prices = {
    'B1': 0, 'B2': 0, 'B3': 0, 'B4': 0}
    #ε阈值
    epsilon=1.0
    #竞拍过程
    k=1
    while True:
        new_bid=bidding(current_assignment,current_prices)
        if len(new_bid)>0:
            new_price,new_assignment=assigning(new_bid,current_assignment,current_prices)
            current_assignment=new_assignment
            current_prices=new_price
        else:
            break
        k += 1
        print("第{}次竞拍:".format(k))
        print("\t竞拍结果为:")
        print("\t",current_assignment)
        print("\t最新定价为:")
        print("\t",current_prices)

参考

  1. Bertsekas, D.P. The auction algorithm: A distributed relaxation method for the assignment problem. Ann Oper Res 14, 105–123 (1988). https://doi.org/10.1007/BF02186476
  2. https://blog.csdn.net/weixin_47546390/article/details/108470396
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/python_n/article/details/117333635

智能推荐

约束布局ConstraintLayout看这一篇就够了-程序员宅基地

文章浏览阅读4.2k次,点赞3次,收藏3次。真的很有必要学习约束布局和它的辅助布局,因为它可以做出很多好看的效果,且性能高;比如这个ConstraintHelper,效果如下图所示:喜欢的可以继续往下看,不夸张的说,约束布局和其辅助布局的相关的这里都有,而且很详细;引入androidx的constraintlayout的lib相对定位基本定位属性如下表,意思好比就是那一条边和那一条边对齐,比如设置B控件的属性 layout_constraintLeft_toLeftOf=“@id/A”就表示B控件的左边对齐A控件的左边,会收到这个约束。_constraintlayout

远程连接MySQL数据库服务器-程序员宅基地

文章浏览阅读115次。上文说到《[url=http://ricki.iteye.com/blog/772886]局域网内访问tomcat服务器[/url]》,主要是想在会议室内远程访问tomcat服务器,不过在演示的时候需要跑JBPM4.4官方实例的junit test,所以当把jbpm.hibernate.cfg.xml改为具体的IP地址后,会报该IP无法连接数据库服务器。 对此,以root..._客户端如何远程登录连接mysql数据库服务器,以实现远程操作mysql数据库? ( site:blog.csdn.net

#define PINT int*与typedef int *SINT的区别._c语言 sint-程序员宅基地

文章浏览阅读576次。#define PINT int* #define是预处理指令,简单的宏定义,在编译预处理时进行简单的替换,不作正确性检查,不管含义是否正确照样带入,只有在编译已被展开的源程序时才会发现可能的错误并报错。①#define PINT int*是,在预处理阶段就已经将PINT替换为int*了,它与int *不等价②如果有PINT a,b; //实际就是 int* a,b; _c语言 sint

JS_数据结构——字典与哈希表_js 声明一个空哈希表-程序员宅基地

文章浏览阅读272次。字典,顾名思义,就是由键:值对的形式进行存储一些值,同现实生活中,每个键对应的值是唯一的,这样才能做到精确查找某值。利用字典,我们可以快速得到键所对应的值,大大方便了我们查找某项数据。在js中,字典的实现和对象十分相似,因为对象在字典中也是采用属性值:属性名的方式进行存储,接下来看一下我所实现的字典吧~var Dictionary=function(){ var items={} //创建一个空字典 this.has=function(key) /_js 声明一个空哈希表

浙江大学计算机与软件学院2021年考研复试上机模拟练习_浙江大学计算机考研复试上机-程序员宅基地

文章浏览阅读533次。文章目录7-1 Square Friends (20 分)7-2 One Way In, Two Ways Out (25 分)7-3 Preorder Traversal (25 分)7-4 Load Balancing (30 分)7-1 Square Friends (20 分)#include <iostream>#include <deque>#include <vector>#include <climits>#include <_浙江大学计算机考研复试上机

tsp问题的拓展_TSP(旅行者问题)——动态规划详解(转)-程序员宅基地

文章浏览阅读2k次。1.问题定义TSP问题(旅行商问题)是指旅行家要旅行n个城市,要求各个城市经历且仅经历一次然后回到出发城市,并要求所走的路程最短。假设现在有四个城市,0,1,2,3,他们之间的代价如图一,可以存成二维表的形式 图一现在要从城市0出发,最后又回到0,期间1,2,3都必须并且只能经过一次,使代价最小。2.动态规划可行性设s, s1, s2, …, sp, s是从s出发的一条路径长度最短的..._游乐园tsp问题

随便推点

SpringMVC:用MultipartFile上传单个文件,多个文件_apache multipartfile-程序员宅基地

文章浏览阅读4w次,点赞11次,收藏52次。单个文件上传开发步骤:1.添加Apache文件上传jar包首先需要下载两个apache上传文件的jar包 commons-fileupload-1.3.1.jar commons-io-2.4.jar 具体使用版本,请根据项目进行选择。 2.配置MultipartResolver处理文件SpringMVC 用的是 的MultipartFile来进行文件上传 所以_apache multipartfile

基于STM32使用超声波HC-SR04模块-程序员宅基地

文章浏览阅读1.2w次,点赞22次,收藏116次。写在前面注意的几点: 1、HC-SR04模块必须使用5V供电,不能是3.3V 2、若单是测距,无需使用中断 3、Echo和Trig两个引脚可以任意接可用的GPIO,和定时器无关说一下超声波的工作原理 单片机给Trig引脚一个最少10us的高电平,然后拉低引脚,便启动了模块, 然后超声波就被发了出去,超声波遇到障碍物后返回被模块接收,Echo引脚会输出一段高电平,高电平的时间与距离成比例

Visual studio C++ MFC之点击按钮(菜单栏)生成新窗口-程序员宅基地

文章浏览阅读899次。背景当前做的APP有菜单栏,菜单栏有一项需要对下位机相关参数进行设置,则必须弹出一个窗口来实现设置操作。本篇即对点击菜单栏生成新的窗口,在新的窗口内完成相应计划后结束新窗口并返回原窗口的方法进行简述。菜单栏的实现可见另一篇博客Visual studio C++ MFC之Menu editor。正文创建一个新窗口在资源视图右击添加Dialog资源,会生成一个新的Dialog,该Dialog..._c++点按钮打开新窗口

「小白经验」浅谈“技术层面-理论层面”_论文中的技术层面是指什么-程序员宅基地

文章浏览阅读1.9k次。今天汇报的时候,被师兄dis了。一句话说的我牙口无言:你是在给我讲科普啊?这一课,让我明白了什么叫作:技术-理论汇报。技术层面看技术性网站、贴吧、论坛。理论层面看学术论文。回首一望那些年,果然是一直停留在技术层面学习,而没有进入理论研究。哪个更总要?哪个都重要。但,就研究生阶段而言,学术研究大于技术学习。因为:技术层是给别人打工的,而理论层是指挥别人工作的。你讲的理论,..._论文中的技术层面是指什么

java数组实现选择排序_java定义一个数组用选择排序排序的方法-程序员宅基地

文章浏览阅读707次。选择排序(Selection sort)是一种简单直观的排序算法。定义一个int类型无序的数组int[] nums = new int[]{3,5,2,6,7,8,1};定义一个int类型的 min ,用来存储每次比对的最小值int min = 0;嵌套循环数组因为是第一个元素比对后面的元素,所以第一个循环 i < 数组长度 -1第二个循环是取出下一个元素进行比对,所以 j = i + 1判断下一个元素是否小于上一个元素,是,则将该元素的索引赋给min进行记录 _java定义一个数组用选择排序排序的方法

flink+kafka+doris+springboot集成例子_springboot doris-程序员宅基地

文章浏览阅读2.2k次。1、springboot基于netty编写接收程序。_springboot doris

推荐文章

热门文章

相关标签