Проверка условий теоремы 1 

Рассмотрим структуру множества M для задач приведенных в пункте 2:

- транспортной задача с промежуточными пунктами

M={{j,k},{i,j},{i},{k},Æ},

разбиение M₁={{j,k},{k},Æ}, M₂={{i,j},{i}}, удовлетворяет условиям теоремы 1

- задача объёмно-календарного планирования

M={{i,j,k},{i,k,t},{j,k},{k,t},{t},Æ},

разбиение M₁={{i,j,k},{j,k},Æ}, M₂={{i,k,t},{k,t},{t}} удовлетворяет условиям теоремы 1

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

M={{j,k},{i,k},{i,j},Æ} и не существует разбиения множества M, удовлетворяющего условиям теоремы 1. Кроме того, для матрицы ограничений этой задачи не выполняются условия абсолютной унимодулярности, тем самым данная задача в случае произвольной матрицы  не может быть сведена к задаче L с целочисленными исходными данными.

Построение сетевой модели

Рассмотрим 3-х индексную задачу линейного программирования W(M) с ограничениями транспортного типа, образованными с использованием индексов i,j,k, iÎI, jÎJ, kÎK, при заданном множестве M={{i,k},{j,k},{k},Æ}:

и критерием

 

Существующее разбиение M₁={{i,k},{k},Æ}, M₂={{j,k}} множества М удовлетворяет условиям теоремы 1, т.е. исходная задача сводится к задаче поиска циркуляции минимальных стоимостей.

Пусть I={1,2}, J={1,2}, K={1,2,3} и задача W(M) имеет следующий вид:

        

Алгоритм построение сети, соответствующей задаче W(M), основан на конструктивном доказательстве теоремы 1.

    Транспортная сеть, соответствующая задаче W(M) приведена на рисунке 1. С дугами сети связаны сегменты, соответствующие пропускным способностям, и стоимости. Дуги, у которых сегменты не приведены, имеют нулевую нижнюю и неограниченную верхнюю пропускные способности и нулевую стоимость. Символ  означает, что в соответствующем данному узлу ограничении происходит суммирование по всем значениям данного индекса.

Рис. 1.

Заключение

При выполнении условий теоремы 1, для многоиндексной задачи линейного программирования W(M) строится соответствующая транспортная сеть с двусторонними пропускными способностями дуг. Поиск допустимой циркуляции проводится путем построения транспортной сети и решения для нее задачи поиска максимального потока. Алгоритм Голдберга и Рао для задачи о максимальном потоке, отбросив логарифмические сомножители, имеет вычислительную сложность O(m^3/2), где m – число дуг транспортной сети (см. [11]). Число вершин в построенной транспортной сети по порядку совпадает с величиной  – суммой количества переменных и ограничений в задаче W(M). При выполнении условий теоремы 1 , а число дуг транспортной сети по порядку совпадает с числом вершин. И тогда вопрос о совместности задачи W(M) требует  арифметических операций. Решение задачи L осуществляется путем нахождения потока минимальной стоимости заданной величины. Алгоритм Орлина решения задачи поиска потока минимальной стоимости, отбросив логарифмические сомножители, имеет вычислительную сложность , где n – число вершин транспортной сети (см. [12]). Отсюда задача W(M) может быть решена за  арифметических операций.

Проверка условий выполнения теоремы 1 может быть осуществлена перебором вариантов, так как при выполнении условий теоремы |M|£2s и множество М не может содержать более 2 элементов одинаковой мощности.

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

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

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

 

Список литературы

1. Гофман А.Дж., Краскал Дж.Б. Целочисленные граничные точки выпуклых многогранников// В сборнике "Линейные неравенства и смежные вопросы". М.:Изд-во ИЛ, 1959, с. 325-347.

2. Литвак Б.Г., Раппопорт А.М. Задачи линейного программирования, допускающие сетевую постановку// Экономика и мат. методы. 1970. Т. 6, Вып. 4, с.594-604.

3. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. Москва: Мир, 1985.

4. Прилуцкий М.Х. Многокритериальное распределение однородного ресурса в иерархических системах.// Автоматика и телемеханика. 1996. №2, с.24-29.

5. Прилуцкий М.Х. Распределение однородного ресурса в иерархических системах древовидной структуры// Труды международной конференции "Идентификация систем и задачи управления SICPRO'2000". Москва, 26-28 сентября 2000 г. М.: Институт проблем управления им. В.А. Трапезникова РАН, 2000, с. 2038-2049.

6. Прилуцкий М.Х., Картомин А.Г. "Потоковые алгоритмы распределения ресурсов в иерархических системах". Электронный журнал "Исследовано в России", 39, стр. 444-452, 2003 г. http://zhurnal.ape.relarn.ru/articles/2003/039.pdf

7. Прилуцкий М.Х., Афраймович Л.Г. "Условия совместности многоиндексных систем транспортного типа" Электронный журнал "Исследовано в России", 70, стр. 762-767, 2005 г. http://zhurnal.ape.relarn.ru/articles/2005/070.pdf

8. Прилуцкий М.Х., Афраймович Л.Г. Оптимальное распределение однородного ресурса в иерархических системах с доходами.// Вестник ВГАВТ. Межвузовская серия Моделирование и оптимизация сложных систем, 2004, с 56-63.

9. Раскин Л.Г., Кириченко И.О. Многоиндексные задачи линейного программирования. М.: Радио и связь, 1982.

10. Форд Л., Фалкерсон Д. Потоки в сетях. М.: МИР, 1966.

11. A.V. Goldberg , S. Rao. Beyond the flow decomposition barrier. Journal of the ACM, 45, 1998, pp. 783-797.

12. J. B. Orlin, A faster strongly polynomial minimum cost flow algorithm, Operations Research, 41, 1993, pp. 338-350.

 

 

Содержание

Введение 3

1. Постановки задач распределения ресурсов 4

1.1. Транспортная задача с промежуточными пунктами 4

1.2. Задача распределения мощностей каналов передачи данных провайдерами сети ИНТЕРНЕТ 5

1.3. Задача объемно-календарного планирования 6

2. Общая математическая модель многоиндексной иерархической системы 8

3. Исследование вопроса сводимости задачи к потоковым моделям 10

4. Примеры 13

4.1. Проверка условий теоремы 1 13

4.2. Построение сетевой модели 13

5. Заключение 15

Список литературы 17