一、整数规划求解方法

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

匈牙利法 ( 指派问题 ) : 变量只能取 $0,1$ 值的整数规划 , 如果有 $n$ 个变量 , 则一共可能有 $2^n$ 种可能的取值 , 使用穷举法可能比较简单 ; 在进一步 , 将一些条件考虑进其中 , 可以排除掉一些取值 , 使得搜索范围变小 ;

二、指派问题

指派问题 : 给 $4$ 个人指派 $4$ 个岗位 , 每个人在不同的岗位产生的利润不同 , 如何安排使得利润最高 ;

首先进行 变量选取 , 这里人与工作的关系只是 做 / 不做 工作 , 这里将 甲 是否做 $A,B,C,D$ 工作设置为变量分别设置为 $x_{11},x_{12},x_{13},x_{14}$ ,

甲 如果做 $A$ 工作 , $x_{11}=1$ , 如果不做 $A$ 工作 , $x_{11}=0$ ;

$16$ 个变量如下 :

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

约束条件 ① 每个人只能做一项工作 , 甲的对应 $4$ 个变量相加之和等于 $1$ ; 同理 乙丙丁 对应的 $4$ 个变量相加之和也等于 $1$ ;

约束条件 ② 每个工作只能指派一个人 , $A$ 的对应 $4$ 个变量相加之和等于 $1$ ; 同理 $BCD$ 对应的 $4$ 个变量相加之和也等于 $1$ ;

上述指派问题数学模型 :

m a x Z = 85 x 11 + 92 x 12 + 73 x 13 + 90 x 14 +                 95 x 21 + 87 x 22 + 78 x 23 + 95 x 24 +                 82 x 31 + 83 x 32 + 79 x 33 + 90 x 34 +                 86 x 41 + 90 x 42 + 80 x 43 + 88 x 44 s . t { x 11 + x 12 + x 13 + x 14 = 1 x 21 + x 22 + x 23 + x 24 = 1 x 31 + x 32 + x 33 + x 34 = 1 x 41 + x 42 + x 43 + x 44 = 1 x 11 + x 21 + x 31 + x 41 = 1 x 12 + x 22 + x 32 + x 42 = 1 x 13 + x 23 + x 33 + x 43 = 1 x 14 + x 24 + x 34 + x 44 = 1 x i j = 0 , 1      ( i , j = 1 , 2 , 3 , 4 )

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

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

文章来源: hanshuliang.blog.csdn.net，作者：韩曙亮，版权归原作者所有，如需转载，请联系作者。

原文链接：hanshuliang.blog.csdn.net/article/details/112489987