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

Рассматривается задача размещения с ограничениями на объёмы производства на случайных входных данных. Предполагается, что элементы матрицы транспортных расходов заданы независимыми случайными величинами с равномерной функцией распределения на целочисленном сегменте $[1,r]$. Для задачи с одинаковыми ограничениями на объёмы производства построен приближённый алгоритм решения и проведён вероятностный анализ его работы. Представлены условия, при которых алгоритм является асимптотически точным и имеет временную трудоёмкость $O(n\ln m)$, где $n$ – число потребителей, $m$ – число возможных пунктов производства. Для задачи с произвольными ограничениями построен алгоритм с трудоёмкостью порядка $O(n^{2(1-\theta)}m)$ и определены условия его асимптотической точности для некоторого $\theta<\frac12$. Ил. 1, библиогр. 17.