Методические указания для выполнения курсовой работы по дисциплине «Методы оптимизации» для студентов заочной (ускоренной). Курсовая работа методы оптимизации

Методы оптимизации — курсовая работа

Министерство образования и науки РФ

Уральский государственный технический университет – УПИ

ТЕПЛОЭНЕРГЕТИЧЕСКИЙ ФАКУЛЬТЕТ

КАФЕДРА ПРИКЛАДНОЙ МАТЕМАТИКИ

КУРСОВАЯ РАБОТА

Оценка работы: .

Руководитель: Студент:

зав. каф., проф., докт. физ.-мат. наук, Самойлов Е.О.

Сесекин Александр Николаевич Группа: Т-330

__________________________ _____________________________

(подпись, дата) (подпись, дата сдачи)

Екатеринбург, 2005

СОДЕРЖАНИЕ

Требуется спроектировать трубопровод, направляющий добываемую в местечке Болотном нефть на переработку в город Нефтезаводск (Рис. 1).

Рис. 1. Схема проектируемого нефтепровода

Затраты, связанные со строительством и эксплуатацией 1 км нефтепровода, обеспечивающего транспортировку годового объема болотистой нефти, приведены в таблице 1.

Таблица 1. Проектируемые затраты.

Зона	Затраты, млн. руб.
Зона	капитальные	эксплутационные
Болото	140	15
Лес	90	10
Действующий нефтепровод (EF)	40	5

Норматив эффективности капитальных вложений принимается равным 0,15. Приведенные затраты S, связаны со строительством и эксплуатацией 1 км нефтепровода, рассчитываются по формуле

S = C + E * K,

где C – эксплутационные затраты;

K – капитальные вложения;

Требуется:

1. Построить математическую модель задачи в виде задачи оптимизации с ограничениями.

2. Построить схему метода штрафных функций.

3. Построить схему метода спуска для вспомогательной задачи метода штрафных функций.

4. Провести вычисления на компьютере.

5. Выполнить анализ результатов и сделать заключение.

Приведенные затраты S, связаны со строительством и эксплуатацией 1 км нефтепровода, рассчитываются по формуле

S = C + E * K,

учитывая E = 0,15, получим

S = C + 0,15*K,

Общие затраты Q, связаны со строительством и эксплуатацией всего нефтепровода, рассчитываются по формуле

, где

S1 = 15+0,15*140 = 36; BD = 200 км;

S2 = 10+0,15*90 = 23,5; DE = 100 км;

S3 = 5+0,15*40; x3 = 100 – x1 – x2.

Тогда получим

Цель курсовой работы: найти два параметра x1, x2 , при которых затраты Q, связаны со строительством и эксплуатацией всего нефтепровода будут минимальными, и вычислить значение функции Q(x1, x2) в этих точках.

Функция, которую необходимо минимизировать:

(1)

Необходимо решить задачу:

Q(x) à min, xΩ (2)

Множество Ω зададим системой неравенств (системой ограничений):

(3)

Формально нашу задачу запишем, как задачу безусловной оптимизации функции:

F(x) = Q(x) + δ(x| Ω), (4)

где δ(x| Ω) – индикаторная функция (штраф):

если xΩ

δ(x| Ω) = (5)

если xΩ

Функцию δ(x| Ω) можно рассматривать как бесконечный штраф за нарушение ограничений xΩ. В большинстве случаев совсем нетрудно построить вполне конкретные штрафы δk(x| Ω), такие, что при всех xRn:

δk(x| Ω) = δ(x| Ω) (6)

Тогда задачу (2) можно свести к последовательности вспомогательных задач безусловной минимизации:

Fk(x) = Q(x) + δk(x| Ω) à min, (7)

Существует два подхода к построению штрафов δk(x| Ω) – методы внутренней точки и методы внешней точки.

Рассмотрим метод внешних штрафных функций.

3. 2. Метод внешних штрафных функций.

Множество допустимых значений Ω задано системой неравенств (системой ограничений):

(8)

В качестве штрафов будем использовать функции

δk(x| Ω)=rk (9)

Здесь rk – положительное число, называемое параметром штрафа. ci – непрерывные функции из системы неравенств (8). Соотношение (6) выполняется, если rkà+0 при k à ∞.

В нашем случае получим следующий штраф

δk(x| Ω)=rk (10)

В результате получили следующую задачу безусловной минимизации функции

F(x1, x2) = Q(x1, x2) + δ(x| Ω) à min, (11)

где

δ(x| Ω)=rk.

Для отыскания безусловного минимума функции двух переменных F(x1, x2) воспользуемся методом наискорейшего спуска.

3. 3. Метод наискорейшего спуска.

Известно, что градиент F(x) функции в некоторой точке x* направлен в сторону наискорейшего возрастания функции F(x) и ортогонален к поверхности F(x)=const, проходящей через точку x*.

Представим себе итерационный процесс следующего вида:

xk+1 = xk – αk F(xk), αk > 0, k = 0, 1, … (12)

То есть новая итерация получается из предыдущей движением в направлении наискорейшего убывания функции F(x) в точке xk с шагом αk. Такие процессы называются градиентными методами и отличаются друг от друга способом выбора шага αk.

В методе наискорейшего спуска шаг αk в формуле (12) выбирается из условия минимума функции F(x) в направлении движения, то есть является решением задачи одномерной минимизации:

F(xk – αk F(xk)) = F(xk – αF(xk)) (13)

Задачу (13) нужно решать на каждом шаге каким-либо из методов одномерной минимизации. Будем использовать метод квадратичной интерполяции.

3. 4. Метод квадратичной интерполяции.

Если известны значения функции в трех различных точках равные соответственно то функция может быть аппроксимирована квадратичной функцией

где А, В и С определяются из уравнений:

После преобразований этих уравнений получаем:

где . Ясно, что будет иметь минимум в точке, если А > 0. Следовательно, можно аппроксимиро-вать точку минимума функции значением

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

Идеи и результаты, изложенные выше, преобразуются в вычислительные процедуры, описанные ниже. Предположим, что заданы унимодальная функция одной переменной начальная аппроксимация положения минимума x0 и длина шага h, являющаяся величиной того же порядка, что и расстояние от точки x0 до точки истинного минимума x* (условие, которое не всегда просто выполнить). Вычислительная процедура имеет следующие шаги:

Вычислить и
Если то взять в качестве третьей точки и вычислить . В противном случае в качестве третьей точки взять и найти .

Рис. Выбор третьей точки при квадратичной интерполяции

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

freepapers.ru

Методические указания для выполнения курсовой работы по дисциплине «Методы оптимизации» для студентов заочной (ускоренной)

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

для выполнения курсовой работы

по дисциплине «Методы оптимизации»

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

специальности 230201

«Информационные системы и технологии»

В процессе изучения дисциплины "Методы оптимизации" студент готовит курсовую работу. Курсовая работа является самостоятельной (индивидуальной) исследовательской работой студента по заданной преподавателем тематике. Она заключается в построении и типизации математических оптимизационных моделей и разработке алгоритмического и программного обеспечения для решения различных классов задач оптимального выбора.

Курсовая работа выполняется по вариантам. Задание на курсовую работу выдается каждому студенту преподавателем индивидуально и заключается в программной реализации какого-либо метода оптимизации В ходе выполнения курсовой работы студент должен изучить литературу, подробно ознакомиться с представленным в задании методом, провести его сравнительный анализ с другими методами, предназначенными для решения данного класса задач, разработать программу, реализующую данный алгоритм, рассмотреть прикладные аспекты метода. Разработанная программа должна позволять решать рассматриваемые задачи в интерактивном режиме. Разработка программного обеспечения может производиться на любом языке высокого уровня

Задание на курсовую работу выдаются за 3 месяца до окончания семестра. За 2 недели до окончания семестра курсовые работы сдаются преподавателю на рецензию. Защита курсовых работ производится в конце семестра в течение зачетной недели в виде краткого доклада (3-5 минут) по данной тематике и демонстрации программного обеспечения.

Курсовая работа оформляется в бумажном виде (формат А4) в соответствии с требованиями ЕСКД. Программное обеспечение представляется на магнитном носителе (записывается на винчестер в компьютерном классе). Объем работы – 20-30 стр. без учета приложений. Работа должна включать следующие разделы:

Разделы	Рекомендуемый объем (страниц)
Титульный лист	1
Содержание	1
Введение	1-2
Теоретическая часть	8-12
Описание алгоритма	2-4
Описание программы	3-5
Контрольный пример	2-4
Заключение	1-2
Список использованных источников	1
Приложения

Название разделов и подразделов должно соответствовать тематике курсового проектирования.

Титульный лист оформляется в соответствии со стандартами и должен иметь следующий вид (на отдельном листе):

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ РФ

ВОРОНЕЖСКИЙ ИНСТИТУТ ВЫСОКИХ ТЕХНОЛОГИЙ

Кафедра физико-математической подготовки

КУРСОВАЯ РАБОТА

по дисциплине “Методы оптимизации”

ТЕМА: “……………………………………….”

Выполнил:

студент гр. ………..

Иванов И.И.

Руководитель:

………………..

Воронеж 2006

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

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

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

Описание алгоритма содержит его блок-схему или описание работы по шагам.

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

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

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

Литература оформляется в соответствии со стандартами, например:

Нечепуренко М.И. Алгоритмы и программы решения задач на графах и сетях. Новосибирск.: Наука, 1990. 515 с.

В приложении должен быть представлен листинг разработанной программы.

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

Примерное содержание курсовой работы:

Введение ………………………………….…………………….3

1. Постановка транспортной задачи линейного программированияиееособенности..……………………………………………..….4

2. Методы решения транспортных задач …………………………….

2.1. Методы построения первоначального плана перевозок….

2.1.1. Метод северо-западного угла…………………………

2.1.2. Метод минимального элемента……………………..

2..2. Методы определения оптимального плана перевозок…….

2.2.1. Метод потенциалов

2.2.2. Метод дифференциальных рент

3. Блок-схема алгоритма потенциалов…………………………..

4. Описание программы решения транспортных задач методом

потенциалов………………………..…………………………….

4.1. Основные характеристики программы……………………

4.2. Логическая структура программы……………………….

4.3. Входные и выходные данные ……………………………

4.4.Описание диалога с пользователем…………………………..

5. Контрольный пример………………………………………….

Заключение ………………………………………………

Список литературы……………………………………………..

Приложение ………………………………….

Текст должен быть набран в редакторе Microsoft Word в соответствии со следующими требованиями: :

- шрифт Times New Roman;

- одинарный интервал;

- красная строка – 1,5 см;

- выравнивание по ширине;

- поля: верхнее – 2 см, нижнее – 2 см, левое – 2,5 см, правое – 1,5 см.

Все страницы нумеруются, начиная с титульного листа, но на титульном листе и второй странице цифры не проставляются. Начиная с введения (страница 3), цифры, обозначающие порядковый номер страницы, ставят в середине верхнего поля страницы. Каждый новый раздел начинается с новой страницы. Это же правило относится к другим основным структурным частям работы; введению, заключению, списку литературы, приложениям. Подразделы (1.1, 2.1. и т..д.) располагаются на той же странице.

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

ТЕМАТИКА КУРСОВЫХ РАБОТ

1. Решение задач линейной оптимизации симплекс-методом.

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

3. Программная реализация двойственного симплекс-метода.

4. Решение задач дробно-линейного программирования.

5. Решение задач транспортного типа методом потенциалов.

6. Решение транспортных задач методом дифференциальных рент.

7. Решение задач целочисленной линейной оптимизации методом отсечений.

8. Использование метода отсечений Гомори для решения частично целочисленных задач линейной оптимизации.

9. Программная реализация метода ветвей и границ для решения задач дискретной оптимизации.

10. Решение задачи коммивояжера методом ветвей и границ.

11. Решение задачи о назначениях венгерским методом.

12. Решение задачи о назначениях с использованием метода Мака.

13. Решение задачи о ранце методом ветвей и границ.

14. Программная реализация методов одномерной оптимизации.

15. Решение задач безусловной оптимизации методом Хука-Дживса.

16. Решение задач безусловной оптимизации методом переменного многогранника Нелдера-Мида.

17. Программная реализация модифицированного метода Хука-Дживса для решения задач с ограничениями.

18. Программная реализация комплексного метода Бокса для решения задач условной оптимизации.

19. Решение задач безусловной оптимизации с использованием градиентных методов.

20. Решение задач безусловной оптимизации с использованием метода сопряженных градиентов.

21. Решение задач безусловной оптимизации с использованием метода Ньютона и его модификаций.

22. Решение задач безусловной оптимизации с использованием квазиньютоновских методов.

23. Программная реализация методов покоординатной оптимизации.

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

25. Построение и оптимизация сетевых графиков.

26. Определение максимального потока в транспортной сети при одном и нескольких источниках и стоках. Алгоритм Форда-Фалкерсона.

27. Построение кратчайших путей в транспортной сети.

28. Решение задач векторной оптимизации.

29. Построение математической модели объекта проектирования с использованием методов планирования эксперимента. Планы первого порядка.

30. Построение математической модели объекта проектирования с использованием методов планирования эксперимента. Планы второго порядка.

ЛИТЕРАТУРА

1. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие. - М.: Высш. шк., 1986.

2. Батищев Д.И., Львович Я.Е., Фролов В.Н. Оптимизация в САПР: Учебник. - Воронеж: Изд-во ВГУ, 1997.

3. Банди Б. Методы оптимизации. Вводный курс. - М.: Радио и связь, 1988.

4. Банди Б. Основы линейного программирования . - М.: Радио и связь, 1988.

5. Конструирование алгоритмов оптимального проектирования: Учеб. пособие / А.И.Каплинский, Я.Е.Львович, О.И.Черных. - Воронеж, 1993.

6. Белецкая С.Ю. Принятие оптимальных решений с использованием средств EXCEL: Учеб. пособие. - Воронеж, 2000.

7. Белецкая С.Ю. Решение задач математического программирования: Учеб. пособие. – Воронеж, 2001.

8. Васильев Ф.П. Численные методы решения экстремальных задач. - М.: Наука, 1988.

9. Введение в оптимизацию / Поляк Б.Т. - М.: Наука, 1983.

10. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. - М: Наука, 1982.

11. Емельянов С.В., Ларичев О.И. Многокритериальные методы принятия решений. - М.: Знание, 1985.

12. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. М.: Мир, 1985.

13. Реклейтис Г., Рейвиндран А. Оптимизация в технике: в 2 кн. - М.:Мир, 1986.

14. Леденева Т.М. Специальные главы математики. Прикладные дискретные модели: Учеб. пособие. Воронеж. гос. техн. ун-т. Воронеж, 1999. 130 с.

15. Свами А.А., Тхуласирман К. Графы, сети и алгоритмы. М.: Мир, 1984. 454 с.

16. Майника Э. Алгоритмы оптимизации на сетях и графах. - М.: Мир.

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

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

для выполнения работы

по дисциплине «Теория информационных процессов и систем»

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

по специальности 230201

«Информационные системы и технологии»

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

Индивидуальное задание выбирается по вариантам в соответствии с контрольными заданиями, представленными ниже.

Работа должна содержать: титульный лист, задание в соответствии с вариантом работы; необходимый материал в соответствии с заданием работы; список используемой литературы.

Объем контрольной работы: 10 – 12 машинописных листов формата А4 (или тетрадь - 12 листов) плюс необходимые приложения.

ЗАДАНИЕ

В соответствии с вариантом работы изучить раздел курса “Модели информационных систем” и выполнить приведенные ниже задания. Привести необходимые пояснения по поставленным в задании вопросам и приводимого решении конкретных задач.

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

7 вариант. Автомат Мили:

xi	zk
xi	z0	z1	z2	z3	z4	z5
Переходы
x1	z0	z1	z3	z0	z1	z3
x2	z1	z3	z4	z3	z1	z4
x3	z3	z1	z3	z1	z0	z3
Выходы
x1	y2	y1	y3	y2	y2	y1
x2	y3	y2	y4	y1	y3	y2
x3	y1	y4	y1	y2	.y4	y3

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

Литература.

Советов Б.Я., Яковлев С.А. Моделирование систем: Учебник для вузов по спец. «Автоматизированные системы управления». – М.: Высш. Шк., 1985. – 271 с.
Рындин А.А. Теория информационных систем: Учеб. пособие / А.А.Рындин, В.Н.Кострова. – Воронеж: Изд-во ВГТУ, 2000. – 92 с.

refdb.ru

Методические указания для выполнения курсовой работы по дисциплине «Методы оптимизации» для студентов заочной (ускоренной)

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

для выполнения курсовой работы

по дисциплине «Методы оптимизации»

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

специальности 230201

«Информационные системы и технологии»

Разделы	Рекомендуемый объем (страниц)
Титульный лист	1
Содержание	1
Введение	1-2
Теоретическая часть	8-12
Описание алгоритма	2-4
Описание программы	3-5
Контрольный пример	2-4
Заключение	1-2
Список использованных источников	1
Приложения

Название разделов и подразделов должно соответствовать тематике курсового проектирования.

Титульный лист оформляется в соответствии со стандартами и должен иметь следующий вид (на отдельном листе):

ВОРОНЕЖСКИЙ ИНСТИТУТ ВЫСОКИХ ТЕХНОЛОГИЙ

Кафедра физико-математической подготовки

КУРСОВАЯ РАБОТА

по дисциплине “Методы оптимизации”

ТЕМА: “……………………………………….”

Выполнил:

студент гр. ………..

Иванов И.И.

Руководитель:

………………..

Воронеж 2006

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

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

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

^ содержит его блок-схему или описание работы по шагам.

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