6

Градиентные методы поиска: Коши, Ньютона, Марквардта, модифицирован-

ный Ньютона, сопряженных градиентов (Флетчера-Ривса), квазиньютоновский

(Девидона-Флетчера-Пауэлла).

Вопросы и задания для самоконтроля

1.Какая точка называется седловой?

2.Дайте определение градиента функции и матрицы Гессе.

3.Какие направления называются сопряженными?

4.Охарактеризуйте способы построения системы сопряженных направлений.

5.Дайте определение линейной и квадратичной сходимости градиентных ме-

тодов поиска.

6.Как влияют на скорость сходимости собственные числа матрицы Гессе?

7.Перечислите алгоритмы, гарантирующие убывание целевой функции от

итерации к итерации.

(к)

8. Почему положительная определенность матрацы являетсяА нео6ходимым, условием реализации процедуры поиска экстремума квазиньюто-

новским методом?

1.4. Модели и методы линейного программирования

Модели задач линейного программирования (ЛП). Графический метод реше-

ния задачи ЛП. Стандартная и каноническая формы задач ЛП, характеристика экстремальных точек. Базисы и базисные решения. Способы преобразования общей формы задачи ЛП к стандартной и канонической. Опорные планы и ме-

тоды их определения. Симплекс-метод решения задачи ЛП. Двойственная задача ЛП, двойственный симплекс-метод. Модифицированный симплекс-метод. Зада-

чи целочисленного программирования. Метод отсечений Гомори. Метод ветвей и границ.

Вопросы и задания для самоконтроля

1.Характер целевой функции и ограничений в задаче ЛП?

2.Виды ограничений в задаче ЛП?

7

З. Что называется базисомn-мерного векторного пространства? Какими свойствами обладает базис?

4. В чем суть метода Жордана-Гаусса? Как определить совместность и несо-

вместность системы линейных уравнений?

5.Какое решение задачи называется базисным?

6.Как выглядят математические модели задач ЛП в векторной и матричной формах?

7.Дайте определение опорного плана (вырожденного, оптимального).

8.Kaкoe множество называется выпуклым? Какая точка выпуклого множест-

ва называется угловой?

9.Что называется многогранником решений?

10.Какие задачи ЛП можно решить графическим методом?

11.Как осуществляется выбор разрешающего элемента в симплекс-таблице?

12.Какая переменная называется "искусственной"? Как она вводится в целе-

вую функцию и систему ограничений?

13. В чем заключается сущность двойственности в задаче ЛП? Ее экономиче-

ская интерпретация?

14.В чем состоит сущность двойственного симплекс-метода?

15.На каких идеях базируются методы решения задач целочисленного про-

граммирования?

1.5. Методы нахождения условного экстремума

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

Уравнение Лагранжа. Решение задачи при ограничениях-равенствах. Решение задачи при ограничениях-неравенствах. Выпуклые функции и множества. Усло-

вия Куна-Таккера. Задача квадратичного программирования.

Методы поиска в задачах с ограничениями: прямого поиска, линейной ап-

проксимации, отсекающих плоскостей, возможных направлений, штрафных функций.

Специальные задачи нелинейного программирования: задачи с сепарабель-

ными целевыми функциями; дробно-линейное, геометрическое и стохастическое

8

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

Вопросы и задания для самоконтроля

1. В чем заключаются трудности решения задачи с неотрицательными пере-

менными методом множителей Лагранжа?

2.В чем состоит условие регулярности области допустимых решений?

3.Какую роль играет решение задачи о седловой точке в условной оптимиза-

ции?

4. При выполнении каких условий существуют седловые точки в задачах не-

линейного программирования?

5.Перечислите типы штрафных функций.

6.Почему необходимо исключать из задачи ограничения-равенства при -ис пользовании методов прямого поиска?

7.В чем состоит сущность метода проектируемых градиентов Розена?

8.В чем состоит сущность метода допустимых направлений Зойтендейка?

9.В чем состоит сущность метода Франка-Вульфа?

10.Что такое полином в задаче геометрического программирования?

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

мирования.

12. Назовите признаки отрицательно определенной(полуопределенной),

положительно определенной (полуопределенной), неопределенной матрицы.

1.6. Динамическое программирование

Понятие динамического программирования(ДП). Принцип оптимальности Беллмана. Геометрическая интерпретация задачи ДП. Принцип поэтапного по-

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

Вопросы и задания для самоконтроля

1.Сформулируйте задачу ДП.

2.Сформулируйте принцип оптимальности.

З. В чем суть метода функциональных уравнений?

9 4. Напишите функциональное уравнение общего вида для дискретного про-

цесса?

Литература

1. Моисеев Н.Н., Иванилов Ю.П., Столяров Е.М. Методы оптимизации. – М.,

Наука. Главная редакция физико-математической литературы, 1978.- 352с.

2. Дегтярев Ю.И. Методы оптимизации: Учебное пособие для вузов.- М.:

Сов. радио, 1980.- 272с.

3. Кузнецов Ю.И., Козубов В.И., Волощенко А.Б. Математическое програм-

мирование: Учебное пособие.- 2-е изд.- М.: Высшая школа, 1980.- 300c.

4. Карманов В.Г. Математическое программирование.- 2-е изд.- М.: Наука.

Главная редакция физико-математической литературы, 1980.

5. Дегтярев Ю.И. Исследования операций: Учебник для вузов по специально-

сти АСУ- М.: Высшая школа, 1986.- 320с.

6.Зайченко Ю.И. Исследования операций: Учебное пособие для студентов вузов.- Киев: Вища школа, 1980.

7.Реклейтис Г., Рейвиндран А., Регстел К. Оптимизация в технике: В 2 кн.:

Пер. с англ.- М.: Мир, 1986.

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

9.Вагнер Г. Основы исследования операций: В 3 кн.: Пер. с англ.- М.: Map,

1972.

10.Акулич И.Л. Математическое программирование в примерах и задачах:

Учебное пособие для вузов.- М.: Высшая школа, 1986.

11. Вуколов Э.А. и др. Сборник задач по математике для втузов. Специаль-

ные курсы.- М.: Наука. Главная редакция физико-математической литературы, 1984.- 608с.

12.Химмельблау Д. Прикладное нелинейное программирование.- М.: Мир, 1975.- 534с.

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