每日一题【20200726】

线性规划

用0-1整数规划匈牙利算法求解指派问题

题目来源：csdn lilard_ou

根据题意，写出方程组以及约束条件

$min \ z=25x_1+29x_2+31x_3+42x_4$
$+39x_5+38x_6+26x_7+20x_8$
$+34x_9+27x_{10}+28x_{11}+40x_{12}$
$+24x_{13}+42x_{14}+36x_{15}+23x_{16}$
$s.t. $
$$x_1+x_2+x_3+x_4=1$$
$$x_5+x_6+x_7+x_8=1$$
$$x_9+x_{10}+x_{11}+x_{12}=1$$
$$x_{13}+x_{14}+x_{15}+x_{16}=1$$
$$x_1+x_5+x_9+x_{13}=1$$
$$x_2+x_6+x_{10}+x_{14}=1$$
$$x_3+x_7+x_{11}+x_{15}=1$$
$$x_4+x_8+x_{12}+x_{16}=1$$

matlab求解：
c=[25 29 31 42
39 38 26 20
34 27 28 40
24 42 36 23];
intcon=[1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16]
a=[];
b=[];
aeq=[1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0;
0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0;
0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1;
1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0;
0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0;
0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0;
0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1]
beq=ones(9,1);
lb=zeros(16,1);
ub=ones(16,1);
[x,val]=intlinprog(c,intcon,a,b,aeq,beq,lb,ub)

x =
     1
     0
     0
     0
     0
     0
     1
     0
     0
     1
     0
     0
     0
     0
     0
     1
val =
   101

执行结果大概是这样滴！！！

$val=25+26+27+23=101$

参考

1. NULL ↩