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

一、整数规划求解方法

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

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

二、指派问题

指派问题 : 给 4 4 4 个人指派 4 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 A , B, C, D A,B,C,D 工作设置为变量分别设置为 x 11 , x 12 , x 13 , x 14 x_{11}, x_{12}, x_{13}, x_{14} x11​,x12​,x13​,x14​ ,

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

16 16 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​

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

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

约束条件 ② 每个工作只能指派一个人 , A A A 的对应 4 4 4 个变量相加之和等于 1 1 1 ; 同理 B C D BCD BCD 对应的 4 4 4 个变量相加之和也等于 1 1 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 ) \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} maxZ=85x11​+92x12​+73x13​+90x14​+               95x21​+87x22​+78x23​+95x24​+               82x31​+83x32​+79x33​+90x34​+               86x41​+90x42​+80x43​+88x44​s.t⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​x11​+x12​+x13​+x14​=1x21​+x22​+x23​+x24​=1x31​+x32​+x33​+x34​=1x41​+x42​+x43​+x44​=1x11​+x21​+x31​+x41​=1x12​+x22​+x32​+x42​=1x13​+x23​+x33​+x43​=1x14​+x24​+x34​+x44​=1xij​=0,1    (i,j=1,2,3,4)​​

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

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