Методы Свенна и золотого сечения в определении решения на экстремум унимодальной функции

 

Цель: закрепить теоретические знания и получить практические навыки в разработке программы решения задач методами одномерной оптимизации.

Используемые приемы и технологии: технология визуального проектирования и событийного программирования, среда программирования Visual Studio 2010 Professional, язык программирования Visual C++ 2010 Professional.

Ключевые термины: нелинейное моделирование, математическая модель, оптимальный план, допустимый план, алгоритм Свена, метод золотого сечения.

Постановка задачи: Разработайте визуальное приложение на языке Visual C++ решения задачи методами одномерной оптимизации.

 

Варианты заданий

 

Методом Свенна найти отрезок, содержащий точку экстремума унимодальной функции , уточнить точку экстремума методом золотого сечения, .

Вариант 1.

Вариант 2.

Вариант 3.

Вариант 4.

Вариант 5.

Вариант 6.

Вариант 7.

Вариант 8.

Вариант 9.

Вариант 10.

 

Методические указания

 

1 Разработайте алгоритм программы.

2 Разработайте визуальное приложение, формализующее алгоритм методов одномерной оптимизации:

· создайте проект с помощью мастера Windows Forms Application;

· настройте свойства формы Form1;

· добавьте компоненты на форму;

· создайте и определите функции обработчика событий.

3 Оформите отчет по лабораторной работе, включающий разделы:

· Постановка задачи.

· Теоретическое обоснование.

· Скриншоты программы.

· Код программы (функции обработчиков событий).

· Выводы.

 

2. 3.3 Контрольные вопросы

 

1 Что называется нелинейным программированием?

2 Какая постановка задачи нелинейного программирования?

3 Что называется унимодальной функцией?

4 Что понимается под нелинейной моделью?

5 Какие методы одномерной оптимизации?

6 Сколько и какие этапы включает алгоритм Свенна?

7 Что понимается под золотым сечением?

8 Какое свойство золотого сечения?

9 Какие исходные данные содержит алгоритм метода золотого сечения?

10 Сколько и какие этапы метода золотого сечения?

 

3 Сетевое планирование и управление в моделировании информационных систем

 

3.1 Сетевое планирования в условиях определённости

 

Длина критического пути и топология определяются методом критического пути (Critical Path Method). Для определения длины критического пути рассчитывается ранний (ожидаемый) срок наступления завершающего события. Ранний срок совершения события  определяется по формуле

 

,где                                                                  (3.1)

 - ранний срок совершения  события;

 - продолжительность выполнения  работы.

Поздний (предельный) срок наступления  события определяется по формуле

, где                                                               (3.2)

 – поздний срок совершения  события;

 – продолжительность выполнения  работы.

Ранний срок начала работы – наиболее ранний (минимальный) из возможных моментов начала данной работы при заданной продолжительности работ. Совпадает с ранним сроком наступления начального события

 

, где                                                         (3.3)

 – ранний срок наступления начального события.

Ранний срок окончания работы – наиболее ранний (минимальный) из возможных моментов окончания данной работы при заданной продолжительности работ. Рассчитывается по формуле

 

, где                                       (3.4)

 – ранний срок совершения  события;

 – продолжительность выполнения  работы.

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

 

, где                                                  (3.5)

 – поздний срок свершения  события;

 – продолжительность выполнения  работы.

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

 

, где                                                              (3.6)

 – поздний срок свершения  события;

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

 

, где                                                          (3.7)

 – поздний срок свершения  события;

 – ранний срок совершения  события;

 – продолжительность выполнения  работы.

Критические работы не имеют резервов времени.

Степень сложности выполнения в заданный срок работы некритического пути определяется коэффициентом напряженности. Коэффициент напряженности рассчитывается по формуле

 

, где                                                   (3.8)

 – полный резерв времени работы ;

 – длина критического пути;

– продолжительность части максимального полного пути, содержащего работу , которая совпадает с критическим путем.

Алгоритм метода критического пути.

1 Ранний и поздний сроки наступления начального события  совпадают.

2 Ранний и поздний сроки наступления конечного события  совпадают.

3 Разность между ранним сроком конечного события  и ранним сроком начального события  совпадает с разностью между поздним сроком конечного события  и поздним сроком начального события  и равна продолжительности работы .

 

3.2 Сетевое планирования в условиях неопределённости

 

В условиях неопределенности время  является случайной величиной, подчиняющееся закону распределения случайной величины ( -распределение, нормальное распределение). Числовые характеристики случайной величины  математическое ожидание, дисперсия и среднеквадратическое отклонение.

Математическое ожидание рассчитывается по формуле

, где                                                  (3.9)

 – оптимистическое время (выполнение работы в благоприятных условиях);

 – пессимистическое время (выполнение работы в неблагоприятных условиях);

 – наиболее вероятное время (выполнение работы в нормальных условиях).

Дисперсия рассчитывается по формуле

, где                                                         (3.10)

 – пессимистическое время;

 – оптимистическое время.

Среднеквадратическое отклонение рассчитывается по формуле

, где                                                               (3.11)

 - дисперсия случайной величины .

Анализ сетевых графиков методом PERT (Program Evaluation and Review Technique) включает расчет временных параметров и оценку вероятности того, что общий срок выполнения проекта  не превысит директивного срока . Если вероятность  мала, например меньше 0,3, то выполнение комплекса работ в заданный срок  находится под угрозой срыва. Необходимо принять дополнительные меры: перераспределение ресурсов по сети, пересмотр состава работ и событий.

Если  значительна, например больше 0,85, то выполнение проекта в заданный срок можно прогнозировать с высокой степенью надежности.