URSS.ru Магазин научной книги
Обложка Фролькис В.А. Методы и теория оптимизации: Планирование и управление. Принятие оптимальных решений. (Линейное и нелинейное программирование) Обложка Фролькис В.А. Методы и теория оптимизации: Планирование и управление. Принятие оптимальных решений. (Линейное и нелинейное программирование)
Id: 300242

Методы и теория оптимизации:
Планирование и управление. Принятие оптимальных решений. (Линейное и нелинейное программирование)

URSS. 2023. 488 с. ISBN 978-5-9710-8509-6.
Типографская бумага
  • Мягкая обложка

Аннотация

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

Издание ориентировано... (Подробнее)


Оглавление
top
Предисловие8
Введение13
Глава 1. Основные понятия теории оптимизации21
1. Экстремум функции21
2. Постановка задачи оптимизации23
3. Условия существования безусловного экстремума26
Вопросы к главе 137
Глава 2. Классическая задача условной оптимизации39
1. Формулировка задачи39
2. Метод множителей Лагранжа45
3. Интерпретация множителей Лагранжа57
4. Метод Якоби59
5. Анализ чувствительности методом Якоби67
6. Обобщенный метод множителей Лагранжа69
Вопросы к главе 270
Раздел I Методы нелинейной оптимизации72
Глава 3. Выпуклые модели оптимизации72
1. Выпуклое множество72
2. Выпуклая и вогнутая функции76
3. Выпуклая задача оптимизации84
4. Алгоритм решения простых задач97
5. Леммы, необходимые для доказательства существования решения выпуклой задачи оптимизации104
6. Необходимые и достаточные условия Куна—Таккера113
7. Основы теории двойственности117
8. Экономический смысл вектора Куна—Таккера126
9. Выпуклая задача квадратичной оптимизации128
10. Задача планирования производства130
11. Модель рынка с ограничениями на цены131
Вопросы к главе 3133
Глава 4. Численные методы оптимизации135
1. Контроль точности135
2. Идея градиентных методов137
3. Метод градиента (метод наискорейшего спуска)138
4. Метод релаксации (метод покоординатного спуска)148
5. Методы Ньютона и Ньютона—Рафсона155
6. Метод сопряженных градиентов160
7. Метод штрафных функций176
8. Решение оптимизационных задач в рамках MS Excel186
Вопросы к главе 4190
Раздел II Модели и методы линейной оптимизации191
Глава 5. Примеры построения линейных оптимизационных моделей191
1. Оптимальная смесь (задача о пищевом рационе)191
2. Оптимизация плана производства194
3. Распределение ресурсов194
4. Загрузка оборудования196
5. Ассортимент продукции199
6. Транспортная задача200
7. Сборка из комплектующих (минимизация дисбаланса производства) – задача минимакса202
8. Целевое программирование (оплата сверхурочной работы)205
9. Оптимальный раскрой209
10. Управление оборотным капиталом213
11. Задача о максимальном потоке214
Вопросы к главе 5216
Глава 6. Математическая постановка задачи линейного программирования217
1. Общая, каноническая и стандартная задачи линейного программирования217
2. Приведение задачи к каноническому и стандартному виду219
3. Базисные и свободные переменные224
4. Допустимое, базисное и оптимальное решения225
5. Метод перебора230
6. Графический метод решения некоторых линейных задач231
Вопросы к главе 6237
Глава 7. Симплекс-метод: алгебраический алгоритм238
1. Симплекс-метод238
2. Реализация алгоритма симплекс-метода241
3.Пример использования симплекс-метода242
4. Монотонность симплекс-метода и проблема зацикливания248
Вопросы к главе 7250
Глава 8. Определение начального базисного решения251
1. Трудности в определении начального базисного решения251
2. Метод штрафов (M-метод)254
3. Двухэтапный метод255
Вопросы к главе 8257
Глава 9. Симплекс-метод: табличный алгоритм258
1. Табличный алгоритм перестановки переменных258
2. Табличный вариант симплекс-метода266
Вопросы к главе 9285
Глава 10. Двойственная задача линейного программирования286
1. Правила построения двойственной задачи286
2. Примеры построения двойственной задачи293
3. Оценка оптимального значения целевой функции296
4. Связь между оптимальными решениями прямой и двойственной задач297
5. Построение решения прямой задачи (двойственной) по решению двойственной (прямой) задачи304
6. Двойственный симплекс-метод311
7. Введение дополнительного ограничения318
8. Экономическая интерпретация переменных двойственной задачи321
Вопросы к главе 10322
Глава 11. Анализ чувствительности задачи линейной оптимизации324
1. Цель анализа чувствительности324
2. Статус ресурса325
3. Изменение запаса ресурса326
4. Ценность ресурса329
5. Изменение коэффициентов целевой функции330
Вопросы к главе 11332
Глава 12. Транспортная задача333
1. Постановка задачи333
2. Сбалансированная транспортная задача335
3. Метод северо-западного угла336
4. Метод минимального элемента338
5. Метод Фогеля340
6. Цикл в транспортной таблице342
7. Распределительный метод улучшения плана перевозок344
8. Вырожденный план транспортной задачи347
9. Метод потенциалов349
10. Несбалансированная транспортная задача361
11. Введение дополнительных ограничений363
12. Транспортная задача по критерию времени364
Вопросы к главе 12369
Глава 13. Оптимизационные задачи, сводящиеся к транспортной модели371
1. Многопродуктовая транспортная модель371
2. Транспортная модель с промежуточными пунктами374
3. Модель производства с запасами379
4. Задача о кратчайшем пути382
5. Задача о назначениях385
6. Венгерский метод в задаче о назначениях и в задаче о кратчайшем пути386
Вопросы к главе 13393
Глава 14. Дискретные задачи оптимизации394
1. Задачи, приводящие к дискретной оптимизации394
2. Метод ветвей и границ398
3. Метод Гомори (метод отсечения)405
Вопросы к главе 14412
Глава 15. Многокритериальная задача линейной оптимизации413
1. Общие соображения413
2. Метод компромиссной переменной415
3. Метод последовательных уступок416
4. Метод равных отклонений419
5. Метод весовых оценок критериев (метод экспертных оценок)421
6. Примеры решения многокритериальной линейной задачи422
Вопросы к главе 15430
Глава 16. Сетевое планирование432
1. Постановка задачи432
2. Структурная таблица434
3. Вспомогательные понятия из теории графов436
4. Графический метод упорядочивания комплекса работ437
5. Сетевой граф комплекса работ440
6. Построение сетевого графа441
7. Временной сетевой граф «работа — вершина». Метод критического пути (CPM)443
8. Параметры временного сетевого графа448
9. Временной сетевой граф «вершина — событие»454
10. Математическая модель сетевого планирования456
11. Оптимизация плана комплекса работ459
Ответы на вопросы к главам481
Список литературы482

Из Предисловия
top
По направлению 01.03.02 — прикладная математика и информатика — рассматриваемый материал направлен на развитие компетенций выпускника ПК-2 и ПК-3.

В рамках компетенции ПК-2 «Способность понимать, совершенствовать и применять современный математический аппарат» выпускник должен:

ЗНАТЬ а) основные понятия, результаты, задачи и методы эконометрики, финансовой математики, страхования и актуарной математики, математического моделирования, теории игр; б) методы многомерного статистического анализа; в) методы оптимизации, имитационного моделирования, экономической динамики;

УМЕТЬ а) применять методы эконометрики, финансовой математики, страхования и актуарной математики, теории игр, многомерного статистического анализа, имитационного моделирования; б) использовать математическое моделирование, модели экономической динамики, методы оптимизации;

ВЛАДЕТЬ а) основными методами и алгоритмами решения усложненных задач эконометрики, финансовой математики, страховой и актуарной математики, теории игр, стохастического и многомерного статистического анализа; б) методами математического моделирования, моделями экономической динамики, оптимизации, имитационного моделирования и применения их в нетипичных ситуациях.

В рамках компетенции ПК-3 «Способность критически переосмысливать накопленный опыт, изменять при необходимости вид и характер своей профессиональной деятельности» выпускник должен:

ЗНАТЬ а) основные понятия, результаты, задачи и методы теории принятия решений; б) программную инженерию; в) основные понятия теории финансов и кредита, рынка ценных бумаг, экспертных методов и систем, управления знаниями и инновациями; г) модели экономической динамики и оптимизации;

УМЕТЬ применять а) методы теории принятия решений, экономической динамики, оптимизации; б) алгоритмы программной инженерии, финансов и кредита, рынка ценных бумаг; в) экспертных методов и систем, управления знаниями и инновациями;

ВЛАДЕТЬ а) методами оптимизации, основными методами и алгоритмами решения усложненных задач теории принятия решений; б) моделями экономической динамики; в) инструментами программной инженерии, финансов и кредита, рынка ценных бумаг; г) методами экспертных оценок и систем, управления знаниями и инновациями и с их применением в нетипичных ситуациях.

По направлению 38.03.01 — экономика изучение дисциплины направлено на формирование и развитие компетенций выпускника ОПК-4 и УК-1.

В рамках компетенции ОПК-4 «Способен предлагать экономически и финансово обоснованные организационно-управленческие решения в профессиональной деятельности» планируется достижение компетенции ОПК-4.2 «Критически сопоставляет альтернативные варианты решения поставленных профессиональных задач, разрабатывает и обосновывает способы их решения с учётом критериев экономической эффективности, оценки рисков и возможных социально-экономических последствий». В рамках достижения компетенции ОПК-4.2 выпускник должен:

ЗНАТЬ а) основные теоретические факты; б) численные алгоритмы математического программирования; в) практические методы решения конкретных оптимизационных задач;

УМЕТЬ а) ставить, формулировать и формализовать экономическую или управленческую задачу оптимизации; б) построить математическую модель; в) разрабатывать алгоритмы решения задач методами оптимальных решений; г) применять на практике изученные математические методы для решения практических задач; д) использовать вычислительную технику для решения практических задач;

ВЛАДЕТЬ а) методами вычислений, в том числе с использованием MS Excel и других прикладных математических пакетов; б) навыками отладки алгоритмов оптимизации; в) навыками интерпретации полученного решения в терминах исходной экономической задачи, анализа чувствительности решения к изменениям исходных параметров, обоснования эффективности принимаемого решения и интерпретации результатов его анализа.

В рамках компетенции «Системное и критическое мышление», направлен на развитие компетенций выпускника УК-1 «Способен осуществлять поиск, критический анализ и синтез информации, применять системный подход для решения поставленных задач» и достижение компетенции УК-1.3 «Выбирает оптимальный вариант решения задачи, аргументируя свой выбор». В рамках достижения компетенции УК-1.3 выпускник должен:

ЗНАТЬ а) методы построения и решения конкретных оптимизационных задач; б) различные подходы, связанные с формулировкой и решением оптимизационных задач;

УМЕТЬ а) самостоятельно разбираться в математическом аппарате, содержащемся в литературе, связанной со специальностью экономика; б) логически верно и аргументировано обосновывать принятое решение;

ВЛАДЕТЬ а) навыками самостоятельной научно-исследовательской и инженерной работы; б) — навыками обобщения, анализа, восприятия информации, постановке цели и выбору путей её достижения; в) навыками математического и алгоритмического мышления; г) навыками математического исследования прикладных задач: перевод на математический язык, выбор метода решения, оценка полученных результатов.

Курс по методам оптимизации — это составная часть более общей дисциплины «Исследование операций», которая является одной из важнейших при подготовке по прикладной математике, экономике и менеджменту. В настоящее время существует несколько прекрасных книг, посвященных этой теме, например таких авторов как Е. С. Вентцель, Х. Таха, Г. Вагнер и ряда других. К сожалению, перечисленные издания, а также многие другие, приведенные в списке литературы, зачастую являются малодоступными широким студенческим массам, хотя некоторые из них можно найти в свободном доступе в Интернете. Эта обстоятельство плюс желание сделать лекционный курс максимально понятным и дать возможность способным прогульщикам получить знания привели к идее подготовить данное издание.

Предлагаемый материал разбит на два раздела: I — «Методы нелинейной оптимизации» и II — «Модели и методы линейной оптимизации». Первый раздел написан несколько более подробно, чем это принято в подобных курсах, и скорее рассчитан на обучающихся по специальности прикладная математика, для которых этот раздел теории оптимизации является важным кирпичиком в фундаменте их профессиональной подготовки. Отчасти это связано с тем, что, во-первых, в рамках нелинейной оптимизации можно рассмотреть некоторые общие принципы, используемые во всех разделах математического программирования, во-вторых, на взгляд автора, практически нет литературы, в которой в простой форме дается обзор основной «картины» нелинейной теории оптимизации, ее основных теорем, техники их доказательств, хотя знакомство с ней расширяет кругозор будущего специалиста и развивает навыки аналитического мышления.

Раздел I содержит больше «математики», чем раздел II. Но математика раздела I достаточно проста, так как автор, ставя перед собой цель дать последовательное изложение математических аспектов рассматриваемой теории, стремился сделать их понятными и доступными для широкого круга практических работников, зачастую не имеющих достаточной математической подготовки. Поэтому все доказательства изложены по возможности простым и ясным языком и все основные рассмотренные идеи иллюстрируются примерами. Для понимания раздела I не требуется специальных навыков, выходящих за рамки стандартного курса математики для экономистов или инженеров, а доказательство нескольких действительно трудных теорем опущено. Читатель, интересующийся только линейными моделями оптимизации, может пропустить раздел I.

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

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

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

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

Виктор Фролькис

Санкт-Петербург, январь 2022 г.


Об авторе
top
photoФролькис Виктор Абрамович
Кандидат физико-математических наук, старший научный сотрудник, доцент. Закончил физический факультет Ленинградского государственного университета по специальности «Физика». Доцент Санкт-Петербургского государственного экономического университета, ведущий геофизик Главной геофизической обсерватории имени А. И. Воейкова. С 1990 г. доцент/профессор Санкт-Петербургского государственного архитектурно-строительного университета, доцент физического факультета Санкт-Петербургского государственного университета, профессор Петербургского государственного университета путей сообщения Императора Александра I, профессор/доцент Санкт-Петербургского государственного экономического университета. Автор более 100 научных работ.