Присвойте продавцов рейсам, таким образом, что общая стоимость транспортировки минимизирована.

Компания имеет четырех продавцов, которые должны переместиться в ключевые города по всей стране. Компания должна забронировать их рейсы и хочет потратить как можно меньше денег. Эти продавцы базируются в различных частях страны, таким образом, стоимость для них, чтобы полететь в каждый город отличается.

Эта таблица показывает стоимость для каждого продавца, чтобы полететь в каждый ключевой город.

Каждый город представляет возможность продаж. Если город пропущен, то компания терпит неудачу на среднем усилении дохода 2 000$.

Создайте матрицу стоимости, чтобы представлять стоимость каждого продавца, летящего в каждый город.

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

Используйте matchpairs, чтобы присвоить продавцов городам с минимальной стоимостью. Задайте стоимость неприсвоения как 1 000, поскольку стоимость неприсвоения считается дважды, если строка и столбец остаются несопоставленными.

M = matchpairs(C,1000)

M = 4×2

     3     1
     2     2
     4     3
     1     4

matchpairs вычисляет наименее дорогой способ получить продавца в каждый город.

Совпадайте со строками к столбцам, когда у вас будет намного больше столбцов, чем строки в матрице стоимости.

Создайте 3 8 матрица стоимости. Поскольку у вас есть только три строки, matchpairs может произвести самое большее три соответствия с этими восемью столбцами.

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, чтобы совпадать со строками и столбцами матрицы стоимости. Чтобы получить максимальное количество соответствий, используйте большую стоимость неприсвоения (относительно значения записей в матрице стоимости). Задайте три выходных параметров, чтобы возвратить индексы несопоставленных строк и столбцов.

[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 не являются соответствующими никаким строкам.

Присвойте такси до маршрутов, таким образом, что прибыль максимизируется.

Служба такси имеет несколько запросов поездки со всех концов города. Компания хочет диспетчеризировать свое ограниченное количество такси способом, которое делает большую часть денег.

Эта таблица показывает предполагаемый тариф такси для каждого из пяти запросов поездки. Только три из пяти запросов поездки могут быть заполнены.

Создайте матрицу прибыли, чтобы представлять прибыль каждой поездки на такси.

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, чтобы совпадать с такси до самых прибыльных поездок. Задайте три выходных параметров, чтобы возвратить любые несопоставленные строки и столбцы и опцию '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')