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

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

Оглавление
Введение
1 Задача размещения на цепи с одинаковыми ограничениями на объемы производства
1.1 Постановка задачи
1.2 Основные определения
1.3 Основные утверждения
1.4 Описание алгоритма
1.5 Трудоемкость алгоритма
2 Двухэтапная задача размещения на дереве
2.1 Постановка задачи
2.2 Основные утверждения
2.3 Описание алгоритма
3 Поиск совершенного паросочетания в случайном графе
3.1 Постановка задачи
3.2 Описание алгоритма
3.3 Трудоемкость алгоритма
3.4 Вероятностный анализ алгоритма
3.4.1 Оценка этапа
3.4.2 Оценка этапа
3.4.3 Оценка с помощью неравенства Чебышева
3.4.4 Оценка с помощью теоремы Петрова
3.5 Задача на ориентированном графе
3.6 Задача на двудольном графе
4 Задача размещения с ограничениями на объемы производства на случайных входах
4.1 Задача с одинаковыми ограничениями
4.1.1 Постановка задачи
4.1.2 Вспомогательные определения и утверждения
4.1.3 Идея и описание алгоритма
4.1.4 Анализ алгоритма
4.2 Задача с произвольными ограничениями
4.2.1 Постановка задачи
4.2.2 Описание алгоритма
4.2.3 Анализ алгоритма
Заключение
Список публикаций автора по теме диссертации
Благодарности
Литература

Введение
С развитием экономических отношений и стремительным производственным прогрессом все чаще в нашей жизни возникают различные задачи оптимизации — применительно к оптимизации деятельности предприятия, расписания движения поездов, разработки проекта, расходов на производство и т.п. Под оптимизацией, как правило, подразумевают поиск такого управления процессом, которое позволяет добиться оптимального результата — максимизировать прибыль предприятия, сократить время простоя поездов, минимизировать время разработки проекта, минимизировать расходы на производство. В этих условиях все чаще возникает необходимость построения математических моделей различных процессов, для дальнейшего анализа которых возможно применение математического аппарата.
В общем виде математическую модель реальной задачи можно представить таким образом:
где через <2 обозначается множество управлений, допустимых в условиях реальной задачи (допустимые решения задачи), а через С{х) обозначается стоимость (целевая функция), связанная с осуществлением управления х. Задача состоит в поиске оптимального управления х* Е <3, с которым связана минимальная стоимость реализации С* = С(х*).
Основной вопрос состоит в том, каким образом можно эффективно найти оптимальное управление х*1 Если множество допустимых управле-
С(х) —> пип £€<

Рис. 1.8. Область обслуживания Оого открытого насыщенного предприятия.
2. у4*-1 < Л- В таком случае г-ос насыщенное предприятие обслуживает в полном объеме все пункты спроса из интервала 07-1 Ог) (участок 1 на рисунке). Стоимость обслуживания данного интервала составляет
(С0»_1 — СД*^).
Транспортные затраты по обслуживанию крайнего левого пункта спроса (участок 2 на рисунке) равны
5*л*. 1 — Ву-1 — (£ — 1)с£^ .
Для крайнего правого пункта спроса ^ (участок 3 па рисунке) аналогично получаем
9щ - (ВЛ._1 - Вг-1)^ .
Таким образом, находим искомые затраты
= д® + (СгП-1 - С'гд*_11 +
{^Вц_г — Ву^ 1 — (£ — 1)9^1 + дгу — {Ву-1 — Дг-1)^ •
Обозначим через оптимальные затраты, связанные с открыти-
ем и обслуживанием £ насыщенных предприятий в сегменте [г', г], причем предприятие г обязательно открыто (считаем, что |{г;,..., г}| = г' — г + 1 >