E-Book Overview
Примеры и задачи: Учеб. пособие / Новосиб. гос. ун-т. Новосибирск, 2012. — 131 с.
Пособие предназначено для студентов и магистрантов Новосибирского государственного университета, изучающих дисциплины «Теория принятия решений» и «Исследование операций». Материал, содержащийся в пособии, является частью основных лекционных курсов и семинарских занятий по этим дисциплинам.Содержание:<strong>Введение <strong>Моделирование с помощью булевых переменных Примеры математических моделей Правила моделирования логических импликаций Моделирование свойств логических отношений Моделирование выбора минимального элемента Моделирование взаимоисключающих событий Линеаризация в математических моделях Линеаризация произведения переменных Линеаризация заменой переменных Линеаризация кусочно-линейной функции Симметрия в математических моделях <strong>Примеры математических моделей целочисленного линейного программирования Задача о потоке минимальной стоимости Задача коммивояжера Задача о покрытии Задача о двухстадийном гильотинном раскрое Задача о разрезе балок Задача о башнях <strong>Анализ качества моделей целочисленного линейного программирования Классификация моделей Разрыв целочисленности Число ограничений и переменных в модели Многогранники Правильные неравенства Целочисленные решения задачи линейного программирования Уточнение значения границ переменных Удаление избыточных ограничений <strong>Упражнения Теоретические задания Практические задания <strong>Решение оптимизационных задач в GAMS Список литературы
E-Book Content
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Факультет информационных технологий
Е. В. Алексеева
ПОСТРОЕНИЕ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ ЦЕЛОЧИСЛЕННОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. ПРИМЕРЫ И ЗАДАЧИ Учебное пособие
Новосибирск 2012
УДК 519.8(075.8) ББК В183я73-1 A 471 Алексеева Е. В. Построение математических моделей целочисленного линейного программирования. Примеры и задачи: Учеб. пособие / Новосиб. гос. ун-т. Новосибирск, 2012. 131 с. ISBN
Пособие предназначено для студентов и магистрантов Новосибирского государственного университета, изучающих дисциплины «Теория принятия решений» и «Исследование операций». Материал, содержащийся в пособии, является частью основных лекционных курсов и семинарских занятий по этим дисциплинам.
Рецензент д-р физ.-мат. наук, проф. Ю. А. Кочетов
ISBN
c ⃝
Новосибирский государственный университет, 2012 c ⃝
Алексеева Е. В., 2012
Оглавление 1. Введение
4
2. Моделирование с помощью булевых переменных 2.1. Примеры математических моделей . . . . . . . . . . 2.2. Правила моделирования логических импликаций . . 2.3. Моделирование свойств логических отношений . . . 2.4. Моделирование выбора минимального элемента . . 2.5. Моделирование взаимоисключающих событий . . . 2.6. Линеаризация в математических моделях . . . . . . 2.6.1. Линеаризация произведения переменных . . 2.6.2. Линеаризация заменой переменных . . . . . 2.6.3. Линеаризация кусочно-линейной функции . 2.7. Симметрия в математических моделях . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
12 13 15 22 24 25 30 30 32 36 37
. . . . . . . . . .
3. Примеры математических моделей целочисленного линейного программирования 3.1. Задача о потоке минимальной стоимости . . . . . . . . . . . . . . 3.2. Задача коммивояжера . . . . . . . . . . . . . . . . . . . . . . . . . 3.3. Задача о покрытии . . . . . . . . . . . . . . . . . . . . .