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

• Автор: Вознюк, Иван Петрович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Новосибирск
• Количество страниц: 110 с. : ил

Оглавление
Введение
1 Задачи размещения на сети с ограниченными мощностями и пропускными способностями коммуникаций
1.1 Задача размещения на сети с ограниченными пропускными способностями коммуникаций
1.1.1 Постановка задачи
1.1.2 Задача размещения на древовидной сети
1.1.3 Задача размещения на два-дереве
1.2 Задача размещения на сети с ограниченными мощностями и пропускными способностями коммуникаций
1.2.1 Постановка задачи
1.2.2 Сравнение релаксаций
1.2.3 Вычисление релаксаций
1.2.4 Реализация метода ветвей и границ
2 Приближенные алгоритмы для решения задач размещения с ограниченными объемами производства и поставок и обоснование условий их асимптотической точности
2.1 Постановки задач
2.2 Вспомогательные понятия и утверждения
2.3 Приближенный алгоритм для решения задачи размещения с ограниченными объемами производства и условия
его асимптотической точности

2.4 Приближенный алгоритм для решения задачи размеще-
ния с ограниченными объемами производства и единичными объемами поставок и условия его асиптотическон точности
2.5 Замечания
3 Приближенный алгоритм для задачи размещения на максимум с ограниченными объемами производства и поставок
3.1 Постановка задачи
3.2 Субмодулярные функции и жадный алгоритм
3.3 Эквивалентная задача
3.4 Оценки качества алгоритма
Заключение
Список публикаций автора по теме диссертации
Благодарности
Список литературы

Введение
Развитие экономических и производственных отношений в обществе потребовало решать задачи, связанные с принятием целесообразных (верных, правильных, оптимальных) решении в сложных системах взаимоотношения между различными объектами хозяйственной деятельности, будь то оптимальная доставка хлебобулочных изделий от хлебозаводов к магазинами или составление плана работ при постройке космического корабля.
Решая подобные задачи и абстрагируясь от их конкретных постановок, в математике возникла новая наука - исследование операций. В более узком смысле эту область науки называют теорией математических моделей и методов принятия решений. Оказалось, что во многих случаях переменные в таких задачах могут принимать только конечное число состояний. Например, в магазин может быть поставлено только конечное число хлебобулочных изделий в конечном ассортименте. В теории математического программирования такие задачи входят в область дискретной оптимизации. Множество допустимых решений таких задач конечно, и мы, в принципе, можем найти точное решение, перебрав все допустимые решения.

цесс, приходим к ситуации, когда в графе остаются только две вершины. Расчет минимума суммарных затрат, соответствующих этому случаю, завершает прямой ход динамического программирования.
Перейдем к более подробному изложению. Для единообразия записи каждому ребру е = {г, Д} 6 Е исходного графа С = (ЕкЕ) вначале поставим в соответствие функцию Д°(Д, Д)5 (Д, Д) £ В, полагая
= оо, если эти условия несовместны. Величина (Д, Д)
равна транспортным расходам на перемещение продукта по ребру {г, Д Ее можно трактовать как результат операции свертывания треугольника с фиктивной нулевой вершиной.
Рассмотрим общий шаг прямого хода динамического программирования. В текущем графе выберем произвольную вершину г степени 2, смежную с вершинами ] и к. Пусть ребрам {г, у}. {г, Л'} и Д. к} соответствуют рассчитанные на предыдущих шагах функции 5Д Д. и SJk, где а, /3,7 Є Аги{0} — номера вершин ранее свернутых треугольников. Через Sj!.(Fj|.1 Fj■j) обозначим минимум суммарных затрат, связанных с выделенным треугольным фрагментом, при фиксированных потоках (FjklF|;j) Є В продукта, идущего через вершины j и к по инцидентным с ними ребрам всех ранее свернутых треугольников.
если совместны условия
Д + Д = 0, |Д| < ае,