Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...
Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...
Топ:
Теоретическая значимость работы: Описание теоретической значимости (ценности) результатов исследования должно присутствовать во введении...
Техника безопасности при работе на пароконвектомате: К обслуживанию пароконвектомата допускаются лица, прошедшие технический минимум по эксплуатации оборудования...
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного хозяйства...
Интересное:
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Инженерная защита территорий, зданий и сооружений от опасных геологических процессов: Изучение оползневых явлений, оценка устойчивости склонов и проектирование противооползневых сооружений — актуальнейшие задачи, стоящие перед отечественными...
Влияние предпринимательской среды на эффективное функционирование предприятия: Предпринимательская среда – это совокупность внешних и внутренних факторов, оказывающих влияние на функционирование фирмы...
Дисциплины:
2017-12-21 | 292 |
5.00
из
|
Заказать работу |
|
|
Пусть для каждой дуги (n + 1)-вершинной сети заданы два числа: эффект Эij и время tij. Каждый путь m из начальной вершины в конечную вершину характеризует некоторый процесс (проект). Под продолжительностью пути будем понимать сумму времен его дуг. Если продолжительность процесса отличается от заданного времени T, то налагаются штрафы c (m), пропорциональные отклонению, то есть: c (m) = , где коэффициенты a и b могут быть как положительными, так и отрицательными.
Задача заключается в том, чтобы найти путь m*, максимизирующий разность между эффектом и штрафами, то есть m* = arg [ Э (m) - c (m)].
Обозначим lij (l) = Эij - l tij, где l - некоторый параметр, T (l) – продолжительность оптимального пути при параметре l, то есть пути, имеющего максимальную длину, измеряемую в lij (l).
С ростом l величина T (l) не возрастает.
Обозначим T (a), T (b) – продолжительности оптимального пути при l равном a (соответственно, b), m (a), m (b) – эти пути (для их нахождения необходимо решить две задачи на поиск пути максимальной длины). Рассмотрим шесть случаев.
Пусть a ³ b, тогда T (b) ³ T (a) и:
1) если T (b) ³ T (a) ³ T, то m (b) – оптимальное решение;
2) если T ³ T (b) ³ T (a), то m (a) – оптимальное решение;
3) если T (b) ³ T ³ T (a), то, сравнивая m (a) и m (b) по длинам l = Э - c, выбираем путь, имеющий максимальную длину.
Пусть a £ b, тогда T (b) £ T (a) и:
4) если T (a) ³ T (b) ³ T, то m (b) – оптимальное решение;
5) если T ³ T (a) ³ T (b), то m (a) – оптимальное решение;
6) если T (a) ³ T ³ T (b), то задача не имеет эффективных методов решения (возможные подходы описаны в [8]).
В этом случае задача не имеет простого решения, как в предыдущих случаях и приходится решать две задачи.
Задача 1. Минимизировать S(µ)+α(T(µ)-T0) при ограничении T(µ)≤T0
|
Задача 2. Минимизировать S(µ)+β(T(µ)-T0 при ограничении T(µ)≥T0
Лучшее из решений задач 1 и 2 будет оптимальным решением задачи.
Пример. Рассмотрим сеть приведённую на рис. 16. Затраты Sij и продолжительности τij указаны у дуг (первое число – затраты, а второе - продолжительности).
(70;4)
(80;1) (90;1) (50;3)
(50;6) (40;3) (70;2)
(10;7)
(80;2)
(40;4)
(30;6) ( (10;9)
Рис. 16. Исходная сеть к примеру
I. Пусть α=10, β=5
Определим µ(α). Соответствующая сеть с длинами дуг Lij=Sij+ατij приведена на рис. 17, путь µ(α) выделен µ(α)=(0,3,5,7)
(110)
|
Рис. 17. Преобразованная сеть
Имеем Т(α)=13 S(α)=120
L(α)=250
Определим µ(β).Соответствующем сеть приведем на рис. 18.
(90) (85) (95) (65) (55) (80) (80) (45) (90) (60) (55) (60)
Pис. 18. Определение µ(β)
Имеем µ(β)=(0,3,6,7)
T(β)=22, S(β)=50, L(β)=160
Рассмотрим три случая
1. Пусть Т0 = 24
поскольку
Т0 > T() > T (),
то µ(α)= (0,3,5,7) – оптимальное решение.
Имеем F=S(α)+ α(T-T0)=120+10(13-24)=10
2. Пусть Т0 = 10.
Поскольку Т0 < Т (α) <T(β), то
µ(β)=(0,3,6,7) - оптимальное решение.
Имеем:
F=S(β)+β(T(β)-T0)=110
3. Пусть Т0=16, поскольку
T(α)<T0<T(β)
то необходимо сравнить два решения.
3.1 µ=µ(α)=(0,3,5,7)
Имеем:
F1=L(α)-αT0=250-10*16=90
3.2 µ=µ(β)=(0,3,6,7)
Имеем:
F2=L(β)-βT0=160-5*16=80
Так как F1>F2,то µ(β) - оптимальное решение и F=min (90;80)=80
II. Пусть α=5, β=10.
Пути µ(α) и µ(β) были определены выше:
µ(α)=(0,3,6,7)
T(α)=22, S(α)=50, L(α)=160
µ(β)=(0,3,5,7)
T(β)=13, S(β)=120, L(β)=250
Рассмотрим три случая
1. Пусть Т0 = 24
Поскольку Т0 >T(α)>T(β), то µ(α)=(0,3,6,7)- оптимальное решение.
Имеем:
F=S(α)+α(T(α)-T0)=50-2*5=40
2. Пусть Т0 = 10.
Поскольку Т0 <T(β)<T(α), то μ(β)=(0,3,5,7) - оптимальное решение.
Имеем:
F=S(β)+β[T(β)-T0]=120+10*3=150
3. Пусть Т0 = 16. Поскольку T(β)<T0<T(α), то для определения оптимального решения необходимо решить две задачи.
Задача 1. Определить путь μ, минимизирующий L(α)= при ограничении T(μ)≤T0
Задача 2. Определить путь μ минимизирующий L(β),при ограничении T(μ)≥T0
Рассмотрим первую задачу. Для этого заметим, что путей для которых T(μ)≥16 всего два.
|
Это путь μ1=(0,2,6,7) и путь μ2 =(0,3,6,7,). Чтобы их исключить, достаточно удалить вершину 6. В полученной подграфе определим путь с минимальными затратами S(μ) (см. рис. 19)
[85]
(90) [135] (85) (65) [185] [80] (55)
(80) (95) (45) [105] (80) [45] (60)
Рис. 19. Путь с минимальными затратами S(μ)
Имеем μ=(0,3,5,7),
F1=L(α)-αT0=185-5*16=105
Рассмотрим вторую задачу.
Поскольку всего два пути имеют T(μ)>16, то сравнив их получаем оптимальный путь μ=(0,3,6,7), L(β)=270
F2=L(β)-βT0=270-10*16=110
Из двух решений выбираем лучшее.
Окончательно получаем оптимальный путь μ=(0,3,5,7) с величиной критерия F= 105.
В данном случае обе задачи удалось решить сравнительно легко. В общем случае для решения этих задач необходимо разрабатывать специальные методы, которые будут рассмотрены ниже.
|
|
Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!