Loading [MathJax]/jax/output/CommonHTML/autoload/mtable.js
前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >【运筹学】整数规划 ( 整数规划求解方法 | 指派问题 )

【运筹学】整数规划 ( 整数规划求解方法 | 指派问题 )

作者头像
韩曙亮
发布于 2023-03-28 12:50:22
发布于 2023-03-28 12:50:22
1K0
举报

文章目录

一、整数规划求解方法


分支定界法 ( 普通整数规划 ) : 主要处理整数规划问题 , 规划中的变量要求是整数 ;

匈牙利法 ( 指派问题 ) : 变量只能取

0,1

值的整数规划 , 如果有

n

个变量 , 则一共可能有

2n

种可能的取值 , 使用穷举法可能比较简单 ; 在进一步 , 将一些条件考虑进其中 , 可以排除掉一些取值 , 使得搜索范围变小 ;

二、指派问题


指派问题 :

4

个人指派

4

个岗位 , 每个人在不同的岗位产生的利润不同 , 如何安排使得利润最高 ;

A A A

B B B

C C C

D D D

85 85 85

92 92 92

73 73 73

90 90 90

95 95 95

87 87 87

78 78 78

95 95 95

82 82 82

83 83 83

79 79 79

90 90 90

86 86 86

90 90 90

80 80 80

88 88 88

A
B
C
D

85
92
73
90

95
87
78
95

82
83
79
90

86
90
80
88

首先进行 变量选取 , 这里人与工作的关系只是 做 / 不做 工作 , 这里将 甲 是否做

A,B,C,D

工作设置为变量分别设置为

x11,x12,x13,x14

,

甲 如果做

A

工作 ,

x11=1

, 如果不做

A

工作 ,

x11=0

;

16

个变量如下 :

A A A

B B B

C C C

D D D

x 11 x_{11} x11​

x 12 x_{12} x12​

x 13 x_{13} x13​

x 14 x_{14} x14​

x 21 x_{21} x21​

x 22 x_{22} x22​

x 23 x_{23} x23​

x 24 x_{24} x24​

x 31 x_{31} x31​

x 32 x_{32} x32​

x 33 x_{33} x33​

x 34 x_{34} x34​

x 41 x_{41} x41​

x 42 x_{42} x42​

x 43 x_{43} x43​

x 44 x_{44} x44​

A
B
C
D

x11
x12
x13
x14

x21
x22
x23
x24

x31
x32
x33
x34

x41
x42
x43
x44

目标函数就是总的利润值 , 将两个表格中的元素按位相乘再相加即可 ;

约束条件 ① 每个人只能做一项工作 , 甲的对应

4

个变量相加之和等于

1

; 同理 乙丙丁 对应的

4

个变量相加之和也等于

1

;

约束条件 ② 每个工作只能指派一个人 ,

A

的对应

4

个变量相加之和等于

1

; 同理

BCD

对应的

4

个变量相加之和也等于

1

;

上述指派问题数学模型 :

指派问题与运输问题的 约束方程的 系数矩阵 都是稀疏矩阵 , 元素取值只能取值

;

可以使用表上作业法解上述问题 , 但是该问题比运输问题更特殊 , 有更简单的方法求解 , 匈牙利法 ;

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2021-01-12,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
Python 切片(Slice)
在实际开发中,经常遇到下面的需求:在线性表(数组)中提取若干个元素的操作,提取规则有很多,比如说提取前5个、提取后5个、提取奇数/偶数位元素等等。 在抽样检测提取样本时,经常遇到每隔100箱牛奶,取其中一瓶作为样本进行检测。 在其他语言中,实现上述操作是依靠for循环来实现。 //例 C++取数组偶数位元素 len = (sizeof(arrray)) / (sizeof(array[0])); //C++没有Python的len函数 for(int i=0, i < len; i +
Steve Wang
2018/02/05
1.1K0
【运筹学】指派问题、匈牙利法总结 ( 指派问题 | 克尼格定理 | 匈牙利法 | 行列出现 0 元素 | 试指派 | 打 √ | 直线覆盖 ) ★★★
指派问题 参考 【运筹学】整数规划 ( 整数规划求解方法 | 指派问题 ) 博客 ;
韩曙亮
2023/03/29
1.9K0
【运筹学】指派问题、匈牙利法总结 ( 指派问题 | 克尼格定理 | 匈牙利法 | 行列出现 0 元素 | 试指派 | 打 √ | 直线覆盖 ) ★★★
java线程池(二):聊聊newFixedThreadPool(1)和newSingleThreadExecutor()的区别
在第一部分中介绍完java中Executors的线程池创建的方式之后,实际上有一个非常好奇的问题。既然newFixedThreadPool(1)也能保证创建只有一个线程运行的线程池,那么为什么还需要一个newSingleThreadExecutor()方法呢?带着这个问题我们来详细分析。
冬天里的懒猫
2020/09/17
1.3K0
java线程池(二):聊聊newFixedThreadPool(1)和newSingleThreadExecutor()的区别
DS图—图的最短路径(无框架)迪杰斯特拉算法
每行格式:顶点v编号-其他顶点编号-最短路径值----[最短路径]。没有路径输出:顶点v编号-其他顶点编号--1。具体请参考示范数据
叶茂林
2023/07/30
3210
【运筹学】匈牙利法 ( 克尼格定理 | 匈牙利法引入 )
指派问题 参考 【运筹学】整数规划 ( 整数规划求解方法 | 指派问题 ) 博客 ;
韩曙亮
2023/03/28
4850
R语言入门 Chapter01 | 向量
这篇文章讲述的是R语言中关于向量相关知识。希望这篇R语言文章对您有所帮助!如果您有想学习的知识或建议,可以给作者留言
不温卜火
2020/10/28
1.2K0
链表操作算法题合集
*p,*q 指向第一个指针,p向前移动n次,q再跟着和p一直移动,等p移到末尾,q所指的就是倒是第n个元素
小爷毛毛_卓寿杰
2019/02/13
7640
分享一些有趣的代码注释
本文最后更新于 February 19, 2021,文中内容可能已过时,请谨慎使用。
雨临Lewis
2022/01/12
7680
Python基础——切片实例
切片实例 L = list(range(100)) print(L, end=' ') [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 5
py3study
2020/01/20
5300
【数据处理包Pandas】分组及相关操作
数据集team.xlsx下载地址: 链接:https://pan.quark.cn/s/9e3b2a933510 提取码:7i2y
Francek Chen
2025/01/22
3060
【数据处理包Pandas】分组及相关操作
【数据处理包Pandas】DataFrame数据选择的基本方法
数据集team.xlsx下载地址: 链接:https://pan.quark.cn/s/9e3b2a933510 提取码:7i2y
Francek Chen
2025/01/22
2330
【数据处理包Pandas】DataFrame数据选择的基本方法
Python计算序列中数字最大差值(美团2016校招笔试题)
题目要求:给定一个包含若干数字的序列A(本文以列表为例),求满足0≤a≤b<n(其中n为序列长度)的A[b] - A[a]的最大值。 编程要点:循环结构用法,切片,内置函数enumerate(),列表推导式。 参考代码: from random import randrange def maxDifference(lst): # 负无穷大 diff = -float('inf') for index, value in enumerate(lst[:-1]): for v in lst[ind
Python小屋屋主
2018/04/16
1.4K0
休闲娱乐|手把手教你在Python中使用turtle模块实现二次元少女(一)代码部分2
六月暴雪飞梨花
2024/04/07
3930
休闲娱乐|手把手教你在Python中使用turtle模块实现二次元少女(一)代码部分2
【欧拉计划第 11 题】 网格中的最大乘积 Largest product in a grid
Problem 11 Largest product in a grid In the grid below, four numbers along a diagonal line have been marked in red. The product of these numbers is 26 × 6
攻城狮杰森
2022/06/03
6580
【欧拉计划第 11 题】 网格中的最大乘积 Largest product in a grid
休闲娱乐|手把手教你在Python中使用turtle模块实现二次元少女(二)代码部分1
六月暴雪飞梨花
2024/04/07
4380
休闲娱乐|手把手教你在Python中使用turtle模块实现二次元少女(二)代码部分1
Day3下午解题报告
预计分数:20+40+30=90 实际分数:40+90+60=190 再次人品爆发&&手感爆发&&智商爆发 谁能告诉我为什么T1数据这么水。。 谁能告诉我为什么T2数据这么水。。 谁能告诉我为什么T3
attack
2018/04/11
8070
Day3下午解题报告
python打印数组的全部元素
学习Python的人都知道数组是最常用的的数据类型,为了保证程序的正确性,需要调试程序。因此,需要在程序中控制台中打印数组的全部元素,如果数组的容量较小,例如 只含有10个元素,采用print命令或print函数可以答应出数组中的每个元素;如果数组的容量过大,只能打印出数组的部分元素,打印结果只包含开始部分元素和结尾部分元素,中间元素省略。省略的部分不利于程序的调试,因此,为了方便调试程序,需要将数组中的元素全部打印出来。
py3study
2020/01/13
4.2K0
休闲娱乐|手把手教你在Python中使用turtle模块实现二次元少女(一)
小假期悄然走去,选题的任务还未完成,趁着年轻活力的余热好好找找资料来梳理下。今天想要学习的Python语言中的 turtle模块 工具。
六月暴雪飞梨花
2024/04/07
9085
休闲娱乐|手把手教你在Python中使用turtle模块实现二次元少女(一)
python-for循环与while循环
for 循环的循环次数受限于容器类型的长度,而while循环的循环次数需要自己控制。for循环也可以按照索引取值
py3study
2020/01/15
1.5K0
小白眼中的AI之~Numpy基础
引入一下 Numpy模块, Numpy的数组使用可以查看一下帮助文档, Numpy的 array数组类型必须是一致的(后面会讲)
逸鹏
2018/07/16
1K0
推荐阅读
相关推荐
Python 切片(Slice)
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档