Одна задача размещения с одинаковыми объемами производства на случайных входных данных

Рассматривается задача размещения с одинаковыми объемами производства при некоторых специальных ограничениях на объемы спроса клиентов и число открываемых предприятий. Предполагается, что элементы матрицы транспортных расходов $(g_{ij})$ — независимые случайные величины с равномерной функцией распределения на целочисленном сегменте $[1,r]$. Построен приближенный алгоритм решения задачи и проведен вероятностный анализ его работы. Представлены условия, при которых алгоритм является асимптотически точным и имеет временную сложность $O(n \ln m)$, где $n$ — число потребителей, $m$ — число возможных пунктов производства.