Математическое программирование (300,00 руб.)

Стр.2

Стр.132

Стр.133

УДК 519.85(075.8) Г962 Рецензенты: канд. экон. наук, науч. сотр. ИВМ и МГ СО РАН О. А. Ляхов канд. техн. наук, доцент Г. Ы. Токтошов Работа подготовлена кафедрой экономической информатики для студентов, обучающихся по направлению 38.03.05 «Бизнес-информатика» Г962 Гусев С. А. Математическое программирование: учебное пособие / С. А. Гусев. – Новосибирск: Изд-во НГТУ, 2023. – 134 c. ISBN 978-5-7782-4996-7 Учебное пособие составлено на основе курса лекций, который читается автором для студентов IV курса факультета бизнеса Новосибирского государственного технического университета. В нем излагаются такие разделы математического программирования, как линейное программирование, целочисленное линейное программирование и динамическое программирование. Пособие может быть полезно студентам других специальностей, изучающим методы оптимизации, а также специалистам, которые занимаются решением прикладных оптимизационных задач на основе математического моделирования. УДК 519.85(075.8) ISBN 978-5-7782-4996-7 © Гусев С. А., 2023 © Новосибирский государственный технический университет, 2023 2

Стр.2

ОГЛАВЛЕНИЕ Введение ................................................................................................................... 3 1. Линейное программирование .......................................................................... 8 1.1. Задачи линейного программирования.......................................................... 8 1.2. Выпуклые множества в n-мерном пространстве ....................................... 10 1.3. Свойства решений задач ЛП ....................................................................... 12 1.4. Геометрическая интерпретация задачи ЛП. Графический метод решения ...................................................................... 16 1.5. Симплекс-метод ........................................................................................... 18 1.5.1. Переход к другому опорному плану .................................................... 18 1.5.2. Определение оптимального плана ........................................................ 21 1.5.3. Алгоритм симплекс-метода .................................................................. 23 1.6. Двойственность в линейном программировании ...................................... 29 1.6.1. Двойственные задачи линейного программирования ......................... 29 1.6.2. Теоремы двойственности ...................................................................... 32 1.6.3. Нахождение решения двойственной задачи по решению исходной ................................................................................................. 36 1.6.4. Экономическая интерпретация двойственных оценок ....................... 37 1.7. Анализ устойчивости решений задач ЛП .................................................. 41 1.7.1. Устойчивость решения к входным параметрам .................................. 41 1.7.2. Анализ устойчивости задачи ЛП на основе геометрической интерпретации ........................................................................................ 42 1.7.3. Анализ устойчивости задачи ЛП на основе анализа последней симплексной таблицы ............................................................................ 47 1.8. Двойственный симплекс-метод .................................................................. 51 Вопросы для самоконтроля ................................................................................ 56 132

Стр.132

2. Транспортная задача ....................................................................................... 57 2.1. Постановка транспортной задачи ............................................................... 57 2.2. Свойства транспортной задачи ................................................................... 59 2.3. Методы построения начального опорного плана ..................................... 62 2.4. Определение оптимального плана ТЗ методом потенциалов .................. 67 Вопросы для самоконтроля ................................................................................ 72 3. Целочисленное программирование .............................................................. 74 3.1. Постановка задачи целочисленного линейного программирования ....... 74 3.2. Метод Гомори .............................................................................................. 77 3.3. Метод ветвей и границ ................................................................................ 87 3.4. Решение задачи о коммивояжере методом ветвей и границ .................... 98 Вопросы для самоконтроля ................................................................................. 112 4. Динамическое программирование ............................................................. 113 4.1. Метод динамического программирования .............................................. 113 4.2. Решение задачи о ранце ............................................................................. 117 4.3. Задача управления запасами ..................................................................... 121 4.4. Задача распределения ресурсов ................................................................ 124 4.5. Задача достижения цели ............................................................................ 127 Вопросы для самоконтроля .............................................................................. 130 Библиографический список ................................................................................ 131 133

Стр.133