Лекция №1 (стр. 5 )

Затем возврат к операции 1. Критерий окончания поиска состоит в проверке усл. e где - e произвольное малое число. f() - значение целевой функции в центре тяжести a = 1; ¡ = 2; b = 0,5. Метод Нелдера-Мида Определить хh и хl f(xh) = max f(x1, ..., xn+1)

f(xl) = min f(x1, ..., x n+1) 2. Координаты центра тяжести, исключая хh x n+2 = 3. Отражение - проектирование x h через тяжести x n+3 = xn+2 + a( x n+2 - хh); a = 1; коэф-т отражения 4. Вычислить f(x n+3) 5. Растяжение . Если f(x n+3) £ f(хh) , то растяжение x n+4 = x n+2 + ¡( x n+3 - хn+2); ¡ = 2 - растяжение вычислить f(x n+4) Если f(x n+4) < f(хh) , то хh := хn+4 и переход к операц. 1, в противном случае хh := хn+3 и переход к операции 1. 6. Сжатие . Если f(хn+3) > f(xi) для всех i ¹ h, то b = 0,5 коэф-т сжатия. вычислим f(хn+5). Если f(хn+5) > f(хh) , то редукция все векторы уменьшаются в 2 раза xi = xl +0,5(xi - xl) и переход к операции 1. Если нет, то xh = xn+5 и переход к операции 1. 7. Условие останова процесса : e

Алгоритм задачи сетевого планирования 1. Упорядочивание структурной таблицы : работы разделяются на ранги - по признаку числа и рангов работ на которые они опираются. 2. Аналитическое описание системы связей в структурно-временной таблице. ti min возможный срок начала работы аi. T i - min возмож. срок окончания. T i = t i + t i "i (1) Если a i опирается ® a j, a l, a k Тогда t i = max {T j, T l, T k} (2) 3. После того как найдены все t i и все T i Т = max{T1, ... T10} Т - время окончания всего комплекса работ 4. Определение критической работы и критического пути Определим работу а i : Т i = Т max Þ а i - критической работой. $t = max {T j, T l, T k} среди T j, T l, T k определим тот момент на котором достигается max (если моментов несколько взять "). Та работа аm при которой достигается max этот будет 2-ой критической работой. Алгоритм задачи сетевого планирования.

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

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

N n/n	Работа а	Опирается на работы	Время, t
1.	a1	¾	t1
2.	a2	¾	t2
3.	a3	¾	t3
4.	a4	a1, a2	t4
¾	¾	¾	¾
10.	a10	a8, a9	t10

2. Запишем в виде формул систему связей, отраженную в структурно-временной таблице. Обозначим ti - min возможный срок начала работы а (время отсчитывается от начала процесса). Т i - min возможный срок ее окончания. Тогда Т i = t i + t i где - t i время выполнения работы ai. пользуясь этими обозначениями опишем все логические связи между работами комплекса. Пусть работа ai опирается на работы aj, al, ak. Тогда работа ai не может начаться раньше, чем кончиться та из работ aj, al, ak, которая имеет наибольшее время (кончается позже всех). Тогда ti = max{Tj, Tk, Tl} применяя такие формулы ко всем работам комплекса по очереди, найдем все моменты окончания работ Ti и, в конце концов, минимальный срок окончания всего комплекса работ Т. Из таблицы 1. Þ Работа а опирается на a1, a2 ; она может начаться в момент t, когда окончится наиболее длительная работа.

t4 = max {T1, T2} (3) момент окончания работы a4 T4 = t4 + t4 (4) Аналогично для работ a5 , a6 и т. д. 3. После того как найдены моменты начала ti и окончания Тi всех работ комплекса, найдем время окончания всего комплекса работ : T = max{T 1 , T 2, ... T 10} (6) 4. Чтобы найти критические работы и критический путь нужно : найти работу а для которой время окончания Т i = Т max; эта работа а i будет критической. Величина t i = max {T j, T k, T l, ...} среди T j, T k, T l, ... нужно найти тот момент на котором max достигается (если таких моментов несколько взять любой их них). Та работа аm при котором достигается этот max, будет второй от конца работой на критическом пути. Далее процесс итераций повторяют. Т. о. критической будет работа с самым поздним сроком окончания и все работы, на времени окончания которых достигается max в выражении, определяющим срок начала очередной критической работы.

Рассмотрим пример. Зададимся конкретными значениями t i.

N n/n	Работа аi	Опирается на работы	Время ti
1.	а1	¾	15
2.	а2	¾	12
3.	а3	¾	20
4.	а4	а1 , а2	10
5.	а5	а1 , а3 , а4	15
6.	а6	а2 , а3	18
7.	а7	а4	40
8.	а8	а4 , а5	8
9.	а9	а4 , а5 , а6	23
10.	а10	а8 , а9	11

Имеем Т1 = 15; Т2 = 12; Т3 = 20 t = max{T 1 , T 2} = max{15 , 12} = 15; Т4 = t + t4 ; Т4 = 15 + 10 = 25; t5 = max{T 1 , T 3, T 4} = max{15 , 20, 25} = 25 Т5 = t5 + t5 ; Т5 = 25 + 15 = 40 t6 = max{T 2 , T 3} = max{12 , 20 } = 20 Т6 = t6 + t6 ; Т6 = 20 + 18 = 38 t7 = max{ T 4 } = 25 Т7 = t7 + t7 ; Т7 = 25 + 40 = 65 t8 = max{T 4 , T 5} = max{25 , 40 } = 40 Т8 = t8 + t8 ; Т8 = 40 + 8 = 48 t9 = max{T 4 , T 5 , T6} = max{25 , 40, 38 } = 40 Т9 = t9 + t9 ; Т9 = 40 + 23 = 63 t10 = max{T 8 , T 9} = max{48 , 63 } = 63 Т10 = t10 + t10 ; Т10 = 63 + 11= 74 T = max{T 1 , ..., T 10} = 74

Найдем критические работы, начиная с последней. Т. к. max{T 1 , T 2 , ..., Т10} достигается для Т10 , то а10 - является критической работой. а10 опирается на а9 , а8. Из формулы имеем t10 = max{T 8 , T 9} max достигается в Т5 Þ а5 - критическая работа. Процесс итераций повторяем.

Критические работы а1 , а3 , а 4 , а 5 , а10 . Критический путь найден чисто формальным способом. Метод Хука-Дживса Задают - начальное значение; - нач. приращение Вычисляют значение f(x1, ..., x n) в базисной точке. Дают приращение Проверяют f(x1, ..., x n) улучшилось значение? Если нет, то полагают проверяют f(x1, ..., x n) улучшилось значение? Если нет, то полагают . Если нет, то оставляют без изменений. 5. Процесс итераций повторяют. f() - улучшилось, если нет, то f() - улучшилось? и т. д. пока все переменные не изменятся. 6. Если целевая функция улучшила значение на данном шаге, то ее старое значение заменяются на новое при последующих сравнениях и запоминается. 7. Проводится поиск по образцу в соответствии с правилом акселерации где - предыдущий базисный вектор - координаты точки в которой достигнут успех. 8. Проводится исследующий поиск типа II .

Методы минимизации без ограничений, не использующие производные (методы нулевого поиска).

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

Однако применяя методы, использующие производные на практике сталкиваются с 3-мя главными препятствиями : В задачах с достаточно большим числом переменных довольно трудно или даже невозможно получить производные в виде аналитических функций, необходимых для градиентного алгоритма. При замене производных разностными схемами, возникающие при этом ошибки, особенно в окрестности экстремума, может ограничить применение аппроксимации. При использовании методов оптимизации 1-го и 2-го порядков, требуется по сравнению с методами поиска довольно большое время на подготовку задачи к решению. 1. Метод прямого поиска Хука-Дживса