Москва, 2005

ЭЛЕМЕНТЫ ЛИНЕЙНОй И НЕЛИНЕЙНОй

Оптимизации

Учебное пособие

Москва, 2005

УДК

ББК

Элементы линейной и нелинейной оптимизации: Учеб.пособие / Ю.К. Казанов
МГАПИ, 2005. – 111 с. ISBN

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

Пособие предназначено для студентов, изучающих курс “Методы оптимизации” и обучающихся по специальности «Вычислительные машины, комплексы, сети и системы».

Табл. 23, Ил. 21. Библиограф.: 5 назв.

Печатается по решению Редакционно-издательского совета Московской государственной академии приборостроения и информатики.

Рекомендовано Ученым Советом МГАПИ в качестве учебного пособия по специальности 22.01

Научный редактор: Т.А.Степанова, к.т.н., профессор кафедры ИТ-4 МГАПИ

Рецензент: А.В.Рощин, д.т.н., профессор кафедры ИТ-4 МГАПИ

Содержание

ВВЕДЕНИЕ……………………………………………………………….5

I. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ………………………………7

1. Производственная задача или задача планирования ……………….7

2.Типы задач линейного программирования и их преобразование…11

3. Геометрическая трактовка основной задачи

линейного программирования …………….……………………….16

4. Методы решения задач линейного программирования…………..20

4.1. Графический метод ……………………………………………20

4.2. Табличный симплекс-метод решения задачи линейного

программирования ……………………………………………23

4.2.1. Метод единичных векторов ……………………………..23

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

базиса..................................................................................34

5. Двойственные задачи линейного программирования…………….37

5.1. Прямая и двойственная задача ………………………………...37

5.2. Геометрическая интерпретация двойственной задачи.

Леммы и теоремы двойственности ……………………………40

5.3. Нахождение решений двойственных задач……………………43

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

мирования и физическая трактовка двойственной задачи …..45

6. Транспортная задача ………………………………………………….51

6.1. Математическая постановка задачи ………………………........51

6.2. Нахождение опорного плана транспортной задачи …………..54

6.3. Оценка опорного плана транспортной задачи на оптималь-

ность и нахождение очередного плана …………………………58

7. Элементы теории игр ………………………………………………..61

7.1. Предмет теории игр ……………………………………………..61

7.2. Терминология и классификация игр …………………………..62

7.3. Матричные игры и понятие седловой точки ………………….63

7.4. Смешанные стратегии ………………………………………….65

7.5. Геометрический метод решения игр …………………………..69

7.6. Решение матричных игр методами линейного

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

II. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ..……………………………..78

1. Задачи нелинейного программирования …………………………..78

2. Геометрическая интерпретациязадач нелинейного программ-

мирования с ограничениями …………………..…………………...79

3. Некоторые проблемы решения задач нелинейного

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

4. Решение задач условной оптимизации методом Лагранжа……….88

5. Градиентные методы решения задач нелинейного

программирования …………………………………………………91

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

5.2. Метод штрафных функций ……..…………………………….94

5.3. Симплекс-метод поиска глобального экстремума..……..…101

ЛИТЕРАТУРА ……………………………………………………………….102

ПРИЛОЖЕНИЕ ………………………………………………………………103

Поиск по сайту: