- •Исследование операций и методы оптимизации
- •Введение
- •1. Общая постановка задачи линейного программирования. Графическое решение злп. Каноническая форма. Базисное решение
- •Основные определения
- •. Графический метод решения задачи линейного программирования
- •Лабораторная работа №1
- •1.3. Каноническая форма задачи линейного программирования. Приведение к канонической форме
- •1.4. Базисное решение злп
- •1.5. Перестроение базисного решения злп
- •Лабораторная работа № 2
- •2. Симплекс-метод
- •2.1. Основная теорема линейного программирования
- •2.2. Алгоритм симплекс метода
- •Лабораторная работа № 3
- •2.3. Симплекс-метод с искусственным базисом
- •Лабораторная работа №4
- •3. Двойственность в злп
- •Основные понятия и определения
- •3.2. Леммы и теоремы двойственности
- •Лабораторная работа № 5
- •4. Транспортная задача
- •4.1. Математическая модель транспортной задачи
- •4.2. Построение начального базисного решения
- •4.3. Метод потенциалов
- •4.4. Правило вычеркивания
- •4.5. Транспортные задачи, имеющие усложнения в постановке
- •Лабораторная работа № 6
- •5. Теория расписаний
- •5.1. Общие положения
- •5.2. Задача о назначениях
- •5.2.1. Постановка задачи
- •5.2.2. Способ задания задачи о назначениях и ее анализ
- •5.2.3. Венгерский метод
- •Лабораторная работа №7
- •5.4. Система конвейерного типа с двумя приборами
- •5.4.1 Постановка задачи
- •5.4.2. Диаграмма Гантта
- •5.4.3. Вычисление длины расписания
- •Достаточное условие оптимальности расписания
- •5.4.4. Алгоритм построения расписания минимальной длины
- •5.5. Конвейерная система с тремя и более приборами
- •5.5.1. Вычисление длины расписания для системы с тремя приборами
- •5.5.2. Системы, для которых возможно построение оптимального расписания
- •5.5.3. Эвристические алгоритмы
- •5.5.4. Оценки длины расписаний
- •Лабораторная работа № 8
- •Библиографический список
- •Исследование операций и методы оптимизации
- •230700 «Прикладная информатика»
- •3 94006 Воронеж, ул. 20-летия Октября, 84
Министерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
«Воронежский государственный архитектурно-строительный университет»
Н.Г. Аснина
Исследование операций и методы оптимизации
Практикум
2-е издание, переработанное и дополненное
Рекомендовано редакционо-издательским советом
Воронежского государственного архитектурно-строительного университета
в качестве учебного пособия для студентов, обучающихся по направлению 230700
«Прикладная информатика»
Воронеж 2012
УДК 519.863(073)
ББК 65.050 я7
А90
Аснина, Н.Г.
А90 Исследование операций и методы оптимизации : практикум
/ Н.Г. Аснина; Воронежский ГАСУ. - 2 изд., перераб. и доп.-
Воронеж, 2012. - 68с.
ISBN
Изложен краткий теоретический материал по следующим разделам линейного программирования: графическое решение ЗЛП, каноническая форма ЗЛП, базисное решение, симплекс-метод, двойственность в ЗЛП, транспортная задача; и теории расписаний: задача о назначениях, системы конвейерного типа с двумя и более приборами.
Приведены основные алгоритмы решения задач в указанных разделах. Разобраны типовые примеры применения алгоритмов. Представлены контрольные задания для самостоятельного выполнения по каждой теме.
Предназначено для студентов 3 курса дневного отделения, обучающихся по направлению 230700 «Прикладная информатика».
Ил. 45. Табл. 37. Библиогр.: 9 назв.
УДК 519.863(073)
ББК 65.050 я7
Рецензенты: кафедра менеджмента и мировой экономики Воронежского филиала Российского государственного торгово-экономического университета;
З.А. Шабунина, канд. физ.-мат. наук, доцент кафедры вычислительной математики и прикладных информационных технологий Воронежского государственного университета
ISBN 978-5-89040-389-6 © Аснина Н.Г., 2012
Введение
Курс «Исследование операций и методы оптимизации» является важной составляющей экономико-математического образования студентов, обучающихся по направлению «Прикладная информатика».
Данный практикум является переработанным и дополненным изданием практикума по курсу «Оптимизационные задачи в экономике» в соответствии с требованиями Федерального государственного образовательного стандарта третьего поколения к дисциплине «Исследование операций и методы оптимизации».
Круг вопросов, рассматриваемых в предлагаемом практикуме, включает в себя раскрытие понятий и методов математического моделирования социально-экономических систем и процессов. Рассматриваются задачи линейной оптимизации, а также решение дискретных задач, в том числе NP- трудных. Подробно, на примере конкретного задания по каждой теме, описана последовательность проведения расчётов, представлены алгоритмы решения.
Предлагаемый практикум состоит из пяти разделов. Первый раздел посвящен постановке задачи линейного программирования, графическому методу ее решения, а так же основным понятиям ЛП, во втором разделе разобран симплекс-метод и симплекс-метод с искусственным базисом решения ЗЛП, третий раздел посвящен двойственности в задачах ЛП, четвертый - транспортной задаче. В пятом разделе разбираются основные понятия теории расписаний, рассматриваются методы решения задачи о назначениях, а так же системы конвейерного типа с двумя, тремя и более приборами. В начале каждого тематического раздела даны необходимые теоретические сведения, закладывающие основы знаний по принципам решения задач, и типовые примеры. Затем идут задания для самостоятельной работы в виде лабораторных работ.
После изучения на практических занятиях каждого метода, студент должен выполнить индивидуальную лабораторную работу, используя соответствующий алгоритм и представить отчет.
Такая структура глав поддерживает методику преподавания, выстраивая логику изучения каждой темы курса в строго определенном порядке: проведение лекционных занятий с осуществлением контроля усваемости материала и закреплением полученных знаний путем выполнения аналитических заданий.
В результате изучения данного курса студенты должны знать основные математические методы, применяемые при решении экономических задач, уметь разрабатывать алгоритмы и пользоваться ими при реализации соответствующих методов.