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

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

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

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

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

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

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

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')