Задача единого среднего

Представьте себе сеть городов, связанных друг с другом дорога­ми. В каждом городе существует спрос на какие-то виды продук­ции, и вы хотите разместить хранилища для доставки этой продук­ции в эти города. В принципе лучшее место расположения может находиться в любой точке сети и, вполне вероятно, может оказать­ся на дороге, а не в одном из городов. Однако стандартный анализ показывает, что лучшее место расположения всегда находится в городе. Это во многом делает задачу более легкой, поскольку вам потребуется сравнить места расположения хранилища в каждом городе и выявить тот вариант, который дает лучший результат для выбранного показателя, характеризующего деятельность. В каче­стве такого показателя часто задается среднее расстояние или вре­мя поездки, а отыскание самого короткого из этих значений на­зывается задачей единого среднего (single median problem).

Самый легкий способ отыскать единое среднее — начать с матри­цы самых коротких расстояний между городами. На практике мы можем использовать специальное программное обеспечение по планирова­нию маршрутов или воспользоваться каким-то вспомогательным па­раметром, например прямой линией между городами. Чтобы отыс­кать кратчайшее среднее расстояние, нам надо объединить эти рас­стояния с перевозимыми грузами. Поэтому мы умножим расстояние на спрос в каждом городе и получим матрицу расстояний с учетом веса перевозимого груза. Затем мы складываем составляющие по каж­дому городу и отыскиваем вариант с наименьшим значением.

Задача

Ян Брюс доставляет товары в восемь городов, данные по размеще­нию которых и по спросу показаны на рис. 5.12. Он хочет отыскать место размещения логистического центра, имеющего минимальное среднее время доставки продукции в эти города. С чего он должен начать?