matchpairs

合計の移動コストが最小となるよう、営業部員をフライトに割り当てます。

会社には、国内の主要都市に出張する必要のある 4 人の営業部員がいます。会社はフライトを予約しなければならず、できるだけ費用を少なくしようとします。これらの営業部員は国内のさまざまな場所を拠点としており、そのため、彼/彼女らが各都市へ飛行する費用は異なります。

この表に、各営業部員が各主要都市へ飛行するコストを示します。

各都市は販売機会を表します。都市が失われると、会社は平均で 2,000 ドルの収益を失います。

各営業部員が各都市へ飛行するコストを表すコスト行列を作成します。

C = [600 670 960 560
     900 280 970 540
     310 350 950 820
     325 290 600 540];

matchpairs を使用して、営業部員を最小コストの都市に割り当てます。未割り当てのコストを 1000 と指定します。これは、未割り当てのコストは、行と列が不一致のままの場合 2 回カウントされるためです。

M = matchpairs(C,1000)

M = 4×2

     3     1
     2     2
     4     3
     1     4

matchpairs は、ある営業部員を各都市へ送る最も廉価な方法を計算します。

コスト行列で行より列が多い場合は、行を列に一致させます。

3 行 8 列の行列を作成します。3 行しかないため、matchpairs は 8 列に対して最大で 3 つの一致を出力できます。

rng default % for reproducibility
C = randi([10 100], 3, 8)

C = 3×8

    84    93    35    97    97    22    82    13
    92    67    59    24    54    48    97    87
    21    18    97    98    82    93    69    94

matchpairs を使用して、コスト行列の行と列を一致させます。最大の一致数を得るには、(コスト行列のエントリの大きさに対して) 未割り当てのコストを大きくします。3 つの出力を指定して、不一致の行と列のインデックスを返します。

[M,uR,uC] = matchpairs(C,1e4)

M = 3×2

     3     2
     2     4
     1     8

uR =

  0x1 empty double column vector

uC = 5×1

     1
     3
     5
     6
     7

C の 5 つの列はどの行とも一致しません。

利益が最大化するようタクシーをルートに割り当てます。

タクシー会社には市全体から多くの乗車リクエストが寄せられます。会社は限られた数のタクシーを、最大の金額を生み出すような方法で送り出すことを考えます。

この表は、5 つの乗車リクエストそれぞれの推定タクシー料金を示しています。5 つの乗車リクエストのうち 3 つしか満たせません。

各タクシー乗車の利益を表す利益行列を作成します。

P = [5.7 6.3 3.1 4.8 3.5
     5.8 6.4 3.3 4.7 3.2
     5.7 6.3 3.2 4.9 3.4];

matchpairs を使用してタクシーを最大の利益につながる乗車に一致させます。不一致の行と列を返す 3 つの出力を指定し、利益を最大化する 'max' オプションを指定します。空車のタクシーや満たせなかった乗車リクエストからは利益は生じないため、未割り当てのコストをゼロとして指定します。

costUnmatched = 0;
[M,uR,uC] = matchpairs(P,costUnmatched,'max')

M = 3×2

     1     1
     2     2
     3     4

uR =

  0x1 empty double column vector

uC = 2×1

     3
     5

matchpairs が、満たすべき最大の利益を生む乗車を計算します。この解ではリクエスト 3 およびリクエスト 5 が満たされないままとなります。

計算された解について合計利益を計算します。costUnmatched がゼロのため、各一致の利益の合算のみが必要です。

TotalProfits = sum(P(sub2ind(size(P), M(:,1), M(:,2))))

TotalProfits = 17

matchpairs を使用して、距離の変化の合計を最小化していくつかの点の移動を追跡します。

$\mathit{t}=0$ の時点での点のグリッドを緑でプロットします。$\mathit{t}=1$ の時点では、いくつかの点はランダムな方向に短い距離を移動します。

[x,y] = meshgrid(4:6:16);
x0 = x(:)';
y0 = y(:)';
plot(x0,y0,'g*')
hold on
rng default % for reproducibility
x1 = x0 + randn(size(x0));
y1 = y0 + randn(size(y0));
plot(x1,y1,'r*')

matchpairs を使用して、$\mathit{t}=0$ での点を $\mathit{t}=1$ での点と一致させます。これを行うには、まず、コスト行列を計算します。ここで、C(i,j) は点 i から点 j までのユークリッド距離です。

C = zeros(size(x).^2);
for k = 1:length(y1)
  C(k,:) = vecnorm([x1(k)-x0; y1(k)-y0],2,1)';
end
C

C = 9×9

    2.8211    3.2750    9.2462    6.1243    6.3461   10.7257   11.7922   11.9089   14.7169
    4.9987    2.2771    7.5752    6.2434    4.3794    8.4485   11.1792   10.2553   12.5447
   15.2037    9.3130    3.7833   17.1539   12.2408    8.7988   20.7211   16.8803   14.5783
    6.9004    8.6551   13.1987    1.1267    5.3446   11.3075    5.1888    7.3633   12.3901
    8.6703    6.3191    8.7571    5.9455    0.3249    6.0714    8.2173    5.6816    8.3089
   13.5530    8.1918    4.7464   12.7818    6.8409    1.4903   14.6652    9.9242    7.3426
   11.5682   13.1257   16.8150    5.5702    8.3359   13.4144    0.4796    6.2201   12.2127
   13.6699   12.3432   13.7784    8.6461    6.3438    8.8167    5.8858    0.3644    6.1337
   20.6072   17.2853   15.6495   16.5444   12.1590    9.6935   13.9562    8.3006    3.8761

次に、matchpairs を使用してコスト行列の行と列を一致させます。未割り当てのコストを 1 に指定します。未割り当てのコストがコスト行列のエントリと比較して低いため、matchpairs はいくつかの点を不一致のままにすると思われます。

M = matchpairs(C,1)

M = 5×2

     4     4
     5     5
     6     6
     7     7
     8     8

値 M(:,2) は元の点 $\left({\mathit{x}}_0,{\mathit{y}}_0\right)$ に対応し、値 M(:,1) は移動した点 $\left({\mathit{x}}_1,{\mathit{y}}_1\right)$ に対応します。

一致する点のペアをプロットします。元の点から 2*costUnmatched よりも長い距離を移動した点は不一致のままです。

xc = [x0(M(:,2)); x1(M(:,1))];
yc = [y0(M(:,2)); y1(M(:,1))];
plot(xc,yc,'-o')