另类指派问题

aimisiyou

如表格，要求选取10个不同行不同列的单元格，使得（ai,bi）第一项的均值不大于28，第二项的均值最大。

aimisiyou

先不考虑约束条件，按指派问题求解，得(303  (7 1 0 1) (4 2 0 1) (2 4 0 1) (9 6 0 1) (10 9 1 0) (8 8 1 0) (6 10 1 0) (5 3 0 1) (3 5 0 1) (1 7 0 1))
即（31,13）（31,13）（38,10）（30,13）（28,13）（26,15）（35,13）（29,14）（23,13）（32,15）
即第一项总和为303，均值为30.3>28,需要调整选取。

aimisiyou

构造一个函数，使得每个单元内数对变为单值，再根据指派问题求解。令f(x,y)=x*(1+|28-x|)*(y_max+1-y)，如图。
根据指派问题（求最小和）得到
(2952 (10 4 0 1) (2 6 1 0) (9 5 1 0) (7 7 1 0) (1 1 1 0) (8 8 1 0) (6 10 0 1) (5 3 0 1) (4 2 0 1) (3 9 0 1))
_$

即原图中选择（29  3）,（30  13）,（28  13）,（29  14）,（26  15）,（32  11）,（29  10）,（29  14）,（28  5）,（26  15）
x和值286，y和值113。x均值28.6，稍微大于28，但仍不满足题意（不大于28），还得改进。