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

2023-03-28 20:50:22 浏览数 (1)

文章目录

  • 一、整数规划求解方法
  • 二、指派问题

一、整数规划求解方法

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

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

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.tbegin{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

;

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

变量 表格 工作 函数 搜索

0 人点赞