リンゴ振り分け問題をGLPKで解く

3つの八百屋から値段の異なるリンゴをいくつか仕入れた。
これを5つの袋に決められた個数ずつ振り分ける。
袋ごとの平均単価が同じくらいになるように振り分ける方法を見つけたい。

元ネタはここ

要するに画像の5x3の表を埋めつつ目的関数を最小化したい
ただし, 表の要素は非負整数

目的関数は
行ごとの平均単価からの差の絶対値を合計したもの
min: $f(X) = \sum^{5}_{i=1} |-1.26X_{i1}+1.74X_{i2}-326.X_{i3}|$

目的関数に絶対値が入ったままでは扱いづらいので
変数 $T_i=|-1.26X_{i1}+1.74X_{i2}-326.X_{i3}|$ と
制約 $-T_i \le -1.26X_{i1}+1.74X_{i2}-326.X_{i3} \le Ti$ を導入する

結局, 目的関数と制約式は次のようになる
min: $f(X) = \sum^{5}_{i=1} T_i$
subject to:
$\sum^{3}_{j=1} X_{k j} = R_k$
$\sum^{5}_{i=1} X_{i k} = S_k$
$X_{i j} \ge 0, \mathrm{integer}$
$-T_i \le -1.26X_{i1}+1.74X_{i2}-326.X_{i3} \le Ti$
ただし, Rは各袋に入れるリンゴの個数 $\{R_i\}=\{8,21,4,55,8\}$
Sは八百屋から仕入れたリンゴの個数 $\{S_i\}=\{3,4,1\}$ を表す

これをそのままGLPKのモデルとデータとして書く
モデル(shiwake.mod)

param YN;
param FN;
set Yaoya := 1..YN;
set Fukuro:= 1..FN;

param request{Fukuro};
param stock{Yaoya};
param price{Yaoya};
param mean_price;

var X{Fukuro,Yaoya} ,>=0 ,integer;
var T{Fukuro};

minimize DM: sum{i in Fukuro} T[i];
s.t. Tate{k in Yaoya}: sum{i in Fukuro}X[i,k] == stock[k];
s.t. Yoko{k in Fukuro}: sum{i in Yaoya}X[k,i] == request[k];
s.t. ABS_LB{k in Fukuro}: sum{i in Yaoya} (price[i]-mean_price)*X[k,i] >= -T[k];
s.t. ABS_UB{k in Fukuro}: sum{i in Yaoya} (price[i]-mean_price)*X[k,i] <= T[k];

データ(shiwake.dat)

param YN := 3;
param FN := 5;

param request := 
 1 8
 2 21
 3 4
 4 55
 5 8;

# 八百屋から仕入れた個数
param stock :=
 1 29
 2 51
 3 16;

# 八百屋ごとのリンゴの単価
param price :=
 1 43
 2 46
 3 41;

# 全体の平均単価
param mean_price := 44.26;

あとはglpsolに渡せばよい

glpsol.exe -m shiwake.mod -d shiwake.dat -o shiwake.txt

結果
八百屋A, 八百屋B, 八百屋Cの順に
袋1は3個, 4個, 1個で平均単価44.25円
袋2は9個,10個, 2個で平均単価44.24円
袋3は2個, 2個, 0個で平均単価44.5円
袋4は12個, 31個, 12個で平均単価44.25円
袋5は3個, 4個, 1個で平均単価44.25円
と振り分ければよいことが分かった

p.s. GLPKのWindowsバイナリのダウンロードはここ