Некоторая компания имеет четыре сбытовые базы и четыре заказа, которые необходимо доставить различным потребителям. Складские помещения каждой базы вполне достаточны для того, чтобы вместить один из этих заказов. (Решение → 39031)

Заказ №38667

Некоторая компания имеет четыре сбытовые базы и четыре заказа, которые необходимо доставить различным потребителям. Складские помещения каждой базы вполне достаточны для того, чтобы вместить один из этих заказов. В таблице содержится информация о расстоянии между каждой базой и каждым потребителем. была минимальной. Как следует распределить заказы по сбытовым базам, чтобы общая дальность транспортировки была минимальной. Сбытовая база I II III IV A 68 72 75 83 B 56 60 58 63 C 38 40 35 45 D 47 42 40 45 Решение Экономико-математическая модель задачи Данная задача является задачей о назначениях. Число баз равно количеству потребителей,. следовательно, задача является замкнутой. В ячейках таблицы находится расстояние cij от закрепления базы i (i=1, …, 3) за потребителем j (j=1, …, 3 Обозначим через xij факт закрепления i–й базы за потребителем j (1 — если назначен, 0 — если не назначен). Математическая модель задачи имеет вид: Найти такие значения xij, чтобы суммарные расстояния были наименьшими:     3 1 3 i j 1 Z cij xij  min и при этом: каждая база должна быть закреплена только за одним потребителем: 1, 1,2,3,4 3 1    j xij i за каждой базой должен быть закреплен только один потребитель: 1, 1,2,3,4 3 1    i xij j Для решения задач о назначениях применяется Венгерский метод,который заключается в следующем алгоритме: 1) выбираем в каждой строке минимальный элемент и вычитаем его из всех элементов этой строки; 2) если в каком-нибудь столбце не появилось нулей, то из всех элементов такого столбца вычитается минимальный элемент этого столбца; 3) рассматривается множество нулей таблицы и, если оно допустимо, то задача решена, иначе переходим к пункту 4; 4) минимальным числом прямых по строкам и столбцам вычеркиваются все нули, а из невычеркнутых элементов выбирается минимальный элемент ; 5 5) этот элемент вычитается из не вычеркнутых и прибавляется к дважды вычеркнутым элементам, после чего переходим к пункту 3.