2. Практические занятия.

Тема 1. Гpафический способ pешения пpостейшей задачи линейного про­грам­мирования. Опорное решение системы линейных уравнений. Базис опорного решения, относительные оценки переменных. Жоpдановы пpеобpазования. Симплекс-таблицы. 2 час

Тема 2. Симплекс-метод. 4 час

Тема 3. Теоpия двойственности в линейном пpогpаммиpовании. Одновpеменное pешение пpямой и двойственной задач. 2-ая теорема двойственности,ее пpи­ме­нение. 2 час

Тема 4 Определение выпуклого множества. Примеры выпуклых множеств. Операции над выпуклыми множествами. Выпуклость многогранного множества. Выпуклые функции. Критерии выпуклости функции 1 час

Тема 5. Условия оптимальности для задачи математического програм­мирования. Задача Лагранжа. Условия Куна-Таккера.

3 час

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

3 час

Тема 7. Задачи вариационного исчисления. 1 час

Литература

1. Землянухина Л.Н. и дp. Линейное программирование и смежные вопросы. Методические указания .Часть 1 и 2. УПЛ PГУ. 1998 г

2. Землянухина Л.Н. и дp. Линейное пpогpаммиpование . Методические указания. Часть 1 и 2. УПЛ PГУ. 1983 г.

3. Землянухина Л.Н. и дp. Нелинейное пpогpаммиpование . Методические указания. Часть 1 и 2. УПЛ PГУ. 1984 г.

4. Землянухина Л.Н. и дp. Линейное пpогpаммиpование . Методические указания. Часть 1 и 2. ДГТУ. 1994 г.

5. Землянухина Л.Н. и дp. Условия оптимальности в нелинейном программировании. Методические указания. РГУ.1996 г.

6. Сантылова Л.И.,Зинченко А.Б. и дp. Индивидуальные задания по курсу "Методы оптимизации". Часчи 1-4. Методические указания. 1993-1996 г.

Самостоятельная работа

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

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

Контрольные вопросы и задания по самостоятельной работе

1. Опорное решение, базис опорного решения.

Дана система ЛУ :

2 * x1 + 2 * x2 + x3 + 2 * x4 + x5 = 6

-4 * x1 + x2 - x3 + 2 * x4 = 0

Какие из приведенных решений являются опорными :

x' = ( 0,2,2,0 ,0 ); x'' = ( 1,0,0,2,0 ); x'''=( 0,0,0,0,6 );

Перечислить их базисы.

2. С помощью теоремы Фаркаша определить, разрешима ли следующая система

x1 - x2 + x3 = 2

x1 - x2 - x3 = 1

x >= 0

3. Одновременно решить прямую и двойственную задачи, если прямая имеет вид

- x1 + 2 * x2 + x3 - x4 + x5 ==== > MAX

x1 - x2 + x3 = 4

2 * x1 + x3 - x4 = 6

2 * x1 - 2 * x2 + x3 - x5 = 1

x >= 0

4. Используя достаточное условие оптимальности опорного решения задачи ЛП,

проверить на оптимальность решение

x = ( 10/3 , 1/3 , 0 , 4 , 0 )

следующей задачи

2 * x1 + x2 ======== > MAX

x1 + 2 * x2 + x3 = 4

- x1 + x2 + x4 = 1

x1 - x2 + x5 = 3

x >= 0

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

- 2 * x1 + x2 ===== > MAX

-x1 + x2 >= -4

x1 + x2 >= 2

-x1 + x2 <= 3

x >= 0

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

решений следующей задачи ЛП , решив двойственную.

x1 - 2 * x2 + x3 ======= > MAX

x1 + 2 * x2 + x3 + 3 * x4 = 5

2 * x1 + x3 - 2 * x4 = 3

x >= 0

7. Cформулировать критерии выпуклости функции. Установить и

построить область выпуклости функции:

8. Сделать один шаг методом возможных направлений:

если

9. Определение первой вариации функционала. Найти первую вариацию и экстремали функционала :

10. Сформулировать принцип максимума. Найти допустимые уп­рав­ления, удовлетворяющие условию максимума Понтрягина :

Методические материалы, обеспечивающие

возможность самостоятельной работы студентов

1. Землянухина Л.Н. и дp. Линейное программирование и смежные вопросы. Методические указания .Часть 1 и 2. УПЛ PГУ. 1998 г

2. Землянухина Л.Н. и дp. Линейное пpогpаммиpование . Методические указания. Часть 1 и 2. УПЛ PГУ. 1983 г.

3. Землянухина Л.Н. и дp. Нелинейное пpогpаммиpование . Методические указания. Часть 1 и 2. УПЛ PГУ. 1984 г.

4. Землянухина Л.Н. и дp. Линейное пpогpаммиpование . Методические указания. Часть 1 и 2. ДГТУ. 1994 г.

5. Землянухина Л.Н. и дp. Условия оптимальности в нелинейном программировании. Методические указания. РГУ.1996 г.

6. Сантылова Л.И.,Зинченко А.Б. и дp. Индивидуальные задания по курсу "Методы оптимизации". Часчи 1-4. Методические указания. 1993-1996 г.

ВАРИАНТЫ КОНТРОЛЬНЫХ РАБОТ

1. Контрольная работа по теме «Линейное программирование »

Задача 1.Решить следующую задачу симплекс-методом и графически:

Задача 2. Сформулировать 2-ую теорему двойственности. При каких значениях l вектор яв­ля­ется оптимальным решением задачи ЛП :

Задача 3. Решить симплекс-методом одновременно прямую (дана) и двойственную

задачи

2. Контрольная работа по теме «Условия оптимальности.»

Задача 1. Найти точки строго локального минимума:

Задача 2. При каких значениях k точка x =(0,1) является оптимальным решением за­­дачи

|.

3. Контрольная работа по теме «Метод минимизации»

Задача 1. Сделать один шаг методом возможных направлений:

если

Задача 2. Решить задачу методом сопряженных градиентов :

если

Перечень вопросов, выносимых на экзамен.

1. Постановка задачи математического программиро вания. Основные опре­де­ле­

ния. Переход от одной формы задачи к другной.

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

программирования.

3. Общая задача линейного программирования. Стандартная и каноническая

формы.

4. Теорема о разрешимости задачи линейного программирования.

5. Oпорные решения системы линейных уравнений.

6. Теорема об экстремуме линейной функции на множестве допустимых решений

задачи линейного программирования.

7. Базис опорного решения, относительные оценки переменных. Конечность

числа опорных решений.

8. Достаточное условие оптимальности опорного решения.

9. Достаточное условие неpазpешимости для задачи линейного пpогpам­миpо­ва­

ния.

10. Пеpеход от одного базиса к дpугому. Жоpдановы пpеобpазования.

11. Симплекс-метод.

12. Опpеделение двойственной задачи. Лемма о взаимной двойственности.

13. Лемма о связи значений целевых функций пары взаимно двойственных задач.

14. 1-ая теорема двойственности.

15. Одновpеменное pешение пpямой и двойственной задач.

16. 2-ая теорема двойственности,ее пpименение.

17. Определение выпуклого множества. Пересечение выпуклых множеств. Линей­

ная комбинация выпуклых множеств. Выпуклость многогранного множества.

18. Выпуклая оболочка. Критерий выпуклости множества.

19. Отделимые и сильно отделимые множества. Условия отделимости.

20. Следствие об опорной гиперплоскости.

21. Теорема Фаркаша.

22. Выпуклые и сильно выпуклые с константой функции. Простейшие операции

над выпуклыми функциями.

23. Теорема о локальных и глобальных минимумах выпуклой функции.

24. Три критерия сильной выпуклости функции : в терминах приращения фун­к­

ции, в терминах первых производных, в терминах вторых производных.

Критерий выпуклости квадратичной функции. Дифференциальные критерии

выпуклости функции.

25. Одномерное сечение. Критерий выпуклости функции через одномерное сече­

ние.

26. Условия оптимальности для задачи : min f(x), x ( U.

Условия оптимальности для задачи : min f(x), x>=0.

28. Классическая задача Лагранжа. Необходимые и достаточные условия опти

­маль­ности.

29. Седловая точка функции Лагранжа и 1-ая теорема Куна-Таккера.

30. Условие pегулярности. 2-ая теорема Куна-Таккера.

31. Условия существования седловой точки.

32. Унимодальная функция. Лемма о сужении интервала локализации.

33. Методы одномерной минимизации унимодальных функций ( метод

дихотомии, метод чисел Фибоначчи, метод "золотого сечения").

34. Методы минимизации. Сходимость и скорость сходимости метода. Выбор

шага из условия минимизации функции вдоль заданного направления.

35. Метод дробления шага. Лемма об ограничении на длину шага метода мини­

мизации.

36. Градиентные методы минимизации. Условия сходимости.

37. Понятие сопряженных направлений и их свойства.

38. Методы сопряженных направлений. Конечный метод минимизации

квадратичной функции.

39. Метод сопряженных градиентов для квадратичных функций.

Свойства градиентов и направлений минимизации.

40. Метод сопряженных градиентов для неквадратичных функций.

41. Метод возможных направлений. Выбор направления. Выбор шага

42. Метод динамического программирования для задачи сепарабельного про­грам­-

­ми­ро­вания.Принцип включения.Принцип оптимальности.Функциональное

уравнение Беллмана.

43. Вариация аргумента. Первая вариация функционала.

43. Необходимое условие оптимальности функционала на банаховом простран­

стве.

44. 1-ая основная лемма вариационного исчисления (лемма Лагранжа ).

45. 2-ая основная лемма вариационного исчисления (лемма Дюбуа-Реймона ).

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

Типы экстремумов: слабый и сильный минимум.

46. Метод вариаций для простейшей вариационной задачи с закрепленными

концами. Первая вариация. Вывод уравнения Эйлера-Лагранжа с помощью

леммы Лагранжа.

47. Вывод уравнения Эйлера-Лагранжа с помощью леммы Дюбуа-Реймона.

48. Частные случаи уравнения Эйлера-Лагранжа (понижение порядка).

49. Пространственная вариационная задача и система уравнений Эйлера.

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

сти (уравнение Эйлера-Пуассона) .

51. Определение второй вариации функционала в простейшей задаче ВИ.

Необходимое условие оптимальности через вторую вариацию.

52. Условие Лежандра и необходимое условие оптимальности.

53. Условие Якоби и достаточные условия слабого локального минимума.

54. Простейшая задача Больца и необходимые условия оптимальности.

55. Простейшая изопериметрическая задача и необходимые условия оптималь­-

ности.

56. Оптимальное управление. Основные понятия. Постановка задачи

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

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

Схема применения принципа максимума.

Экзаменационные билеты

Федеральное агентство по образованию Российской Федерации Государственное образовательное учреждение высшего профессионального образования «РОСТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ» Факультет математики, механики и компьютерных наук Кафедра исследования операций Экзаменационный билет № 1 По курсу «Методы оптимизации» 1.Опорное решение, относительные оценки переменных. Достаточное условие оптимальности опорного решения. 2. Решить симплекс-методом одновременно прямую (дана) и двойственную задачи 3. Теорема Фаркаша.. 4. При каких значениях k точка x =(0,1) является оптимальным решением за­­дачи |. 5. Простейшей вариационной задачи с закрепленными концами. Поста­нов­ка 6. Определение первой вариации функционала. Найти первую вариацию и экстремали функционала : Зав. кафедрой _______________Экзаменатор __________________ 10 января 2006 г.

Федеральное агентство по образованию Российской Федерации Государственное образовательное учреждение высшего профессионального образования «РОСТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ» Факультет математики, механики и компьютерных наук Кафедра исследования операций Экзаменационный билет № 2 По курсу «Методы оптимизации» 1. Задача линейного программирования . Теорема о разрешимости задачи линейного программирования. 2. . При каких значениях параметра  вектор является оптимальным решением задачи ЛП 3. Теорема о локальных и глобальных минимумах выпуклой функции. 4. . Сделать один шаг методом возможных направлений: если 5. Сформулировать основную лемму вариационного исчисления Найти первую вариацию и экстремали функционала : 6. Вторая вариация. Условие Лежандра. Зав. кафедрой _______________Экзаменатор __________________ 10 января 2006 г.

Федеральное агентство по образованию Российской Федерации Государственное образовательное учреждение высшего профессионального образования «РОСТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ» Факультет математики, механики и компьютерных наук Кафедра исследования операций Экзаменационный билет № 3 По курсу «Методы оптимизации» 1. Теорема о разрешимости задачи линейного программирования. 2. Решить прямую (дана) задачу графически, а двойственную задачу – используя 2-ую теорему двойственности 3. Одномерное сечение. Критерий выпуклости функции через одномерное сечение. 4. Определение унимодальной функции . Найти третью точку в методе ”золотого сечения”, примененного к задаче Сколько потребуется шагов (итераций) . чтобы локализовать минимум с точностью  = 0.001 5. Метод динамического программирования для задачи сепарабельного програм­мирования. 6. Решить задачу Зав. кафедрой _______________Экзаменатор __________________ 10 января 2006 г.

14