E-Book Content
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис» Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования «Оренбургский государственный университет» МЕТОДЫ ПРИНЯТИЯ ОПТИМАЛЬНЫХ РЕШЕНИЙ Часть I под редакцией А.Г. Реннера Рекомендовано ученым советом федерального государственного бюджетного образовательного учреждения высшего образования «Оренбургский государственный университет» в качестве учебного пособия для студентов, обучающихся по программам высшего образования по направлениям подготовки 01.03.04 Прикладная математика, 38.03.05 Бизнес-информатика, 38.04.01 Экономика Оренбург 2016 1 Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис» УДК 519.85(075.8) ББК 22.18я73 М54 Рецензент – доктор технических наук П.И. Огородников Авторы: Р.М. Безбородникова, С.Т. Денисова, Т.А. Зеленина, А.В. Раменская, А.Г. Реннер, О.Н. Яркова М54 Методы принятия оптимальных решений. I часть: учебное пособие / Р.М. Безбородникова, С.Т. Денисова, Т.А. Зеленина, А.В. Раменская, А.Г. Реннер, О.Н. Яркова; под. ред. А.Г. Реннера; Оренбургский гос. унт. – Оренбург: ОГУ, 2016. – 244 с. ISBN 978-5-7410-1562-9 В учебном пособии рассмотрены методы решения задач линейного и целочисленного программирования для принятия оптимальных решений в различных областях. Предназначено для студентов, обучающихся по направлениям подготовки 01.03.04 Прикладная математика, 38.03.05 Бизнесинформатика, 38.04.01 Экономика, магистерская программа «Математические и инструментальные методы анализа социальных и экономических процессов», а также для студентов других направлений подготовки, изучающих дисциплины «Методы оптимизации», «Методы оптимальных решений», «Математические методы и модели исследования операций». УДК 519.85(075.8) ББК 22.18я73 © Безбородникова Р.М., 2016 © Денисова С.Т., 2016 © Зеленина Т.А., 2016 © Раменская А.В., 2016 © Реннер А.Г., 2016 © Яркова О.Н., 2016 © ОГУ, 2016 ISBN 978-5-7410-1562-9 2 Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис» Содержание Введение ................................................................................................................................6 1 Линейное программирование (ЛП) .................................................................................7 1.1 Примеры задач ЛП .........................................................................................................7 1.1.1 Задача планирования выпуска продукции (планирование производства) ............7 1.1.2 Задача о смеси ..............................................................................................................8 1.1.3 Задача определения оптимального рациона питания (задача о диете) ................10 1.2 Постановка и формы записи задач линейного программирования ........................11 1.3 Геометрическая интерпретация двумерной задачи ЛП и ее решение ....................13 1.4 Свойства решений задачи ЛП .....................................................................................18 1.5 Симплекс метод решения задач ЛП ...........................................................................20 1.5.1 Обоснование симплекс метода ................................................................................20 1.5.2 Нахождение начального базиса ...............................................................................26 1.5.3 Решение в форме симплекс-таблиц .........................................................................28 1.6 Двойственные задачи ЛП ............................................................................................33 1.6.1 Пример прямой и двойственной задачи ЛП ...........................................................33 1.6.2 Общая постановка прямой и двойственной задачи .........................