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

韩曙亮

发布于 2023-03-28 20:50:22

9620

文章被收录于专栏：韩曙亮的移动开发专栏韩曙亮的移动开发专栏

文章目录

一、整数规划求解方法

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

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

0 , 1

值的整数规划 , 如果有

n

个变量 , 则一共可能有

2^n

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

二、指派问题

指派问题 : 给

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

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

x_{11}, x_{12}, x_{13}, x_{14}

,

甲如果做

A

工作 ,

x_{11} = 1

, 如果不做

A

工作 ,

x_{11} = 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

甲

x_{11}

x_{12}

x_{13}

x_{14}

乙

x_{21}

x_{22}

x_{23}

x_{24}

丙

x_{31}

x_{32}

x_{33}

x_{34}

丁

x_{41}

x_{42}

x_{43}

x_{44}

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

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

4

个变量相加之和等于

1

; 同理乙丙丁对应的

4

个变量相加之和也等于

1

;

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

A

的对应

4

个变量相加之和等于

1

; 同理

BCD

对应的

4

个变量相加之和也等于

1

;

上述指派问题数学模型 :

\begin{array}{lcl} \rm maxZ = 85x_{11} + 92x_{12} + 73x_{13} + 90x_{14} + \\ \rm \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 95x_{21} + 87x_{22} + 78x_{23} + 95x_{24} + \\ \rm \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 82x_{31} + 83x_{32} + 79x_{33} + 90x_{34} + \\ \rm \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 86x_{41} + 90x_{42} + 80x_{43} + 88x_{44} \\\\ \rm s.t\begin{cases} \rm x_{11} + x_{12} + x_{13} + x_{14} = 1 \\ \rm x_{21} + x_{22} + x_{23} + x_{24} = 1 \\ \rm x_{31} + x_{32} + x_{33} + x_{34} = 1 \\ \rm x_{41} + x_{42} + x_{43} + x_{44} = 1 \\\\ \rm x_{11} + x_{21} + x_{31} + x_{41} = 1 \\ \rm x_{12} + x_{22} + x_{32} + x_{42} = 1 \\ \rm x_{13} + x_{23} + x_{33} + x_{43} = 1 \\ \rm x_{14} + x_{24} + x_{34} + x_{44} = 1 \\\\ \rm x_{ij} = 0 , 1 \ \ \ \ (i , j= 1,2,3,4 ) \end{cases}\end{array}

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

0, 1

;

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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021-01-12，如有侵权请联系 cloudcommunity@tencent.com 删除

变量