Методы оптимизации и принятия решений. Построение оптимизационных моделей и методы их решения в Excel
Покупка
Основная коллекция
Тематика:
Табличные редакторы
Издательство:
Инфра-Инженерия
Год издания: 2025
Кол-во страниц: 276
Дополнительно
Вид издания:
Учебное пособие
Уровень образования:
ВО - Бакалавриат
ISBN: 978-5-9729-2205-5
Артикул: 866393.01.99
Приводятся краткие сведения из теории математического программирования и принятия решений. Изложены методы решения задач линейного, целочисленного и нелинейного программирования, задач транспортного типа. На большом количестве примеров иллюстрируются различные приемы решения задач, в том числе военного, производственного и экономического содержания, дается экономико-математический анализ результатов решения и принятие решений на их основе. Подробно рассмотрено решение этих задач средствами MS Excel. В каждом разделе приводится большое количество задач для самостоятельного решения. Для студентов и аспирантов экономических специальностей всех форм обучения, а также может быть полезно преподавателям и практическим работникам, занимающимся вопросами математического программирования и принятия управленческих решений.
Тематика:
ББК:
УДК:
ОКСО:
- ВО - Бакалавриат
- 02.03.02: Фундаментальная информатика и информационные технологии
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
В. Ф. Шишов, С. В. Колесникова МЕТОДЫ ОПТИМИЗАЦИИ И ПРИНЯТИЯ РЕШЕНИЙ Построение оптимизационных моделей и методы их решения в Excel Учебное пособие Москва Вологда «Инфра-Инженерия» 2025
УДК 338.45 ББК 65.301 Ш65 Р е ц е н з е н т ы : д. э. н., профессор Департамента статистики и анализа данных НИУ ВШЭ В. С. Мхитарян; д. т. н., доцент Военной академии МТО (Пензенский филиал) Д. В. Искоркин Шишов, В. Ф. Ш65 Методы оптимизации и принятия решений. Построение оптимизационных моделей и методы их решения в Excel : учебное пособие / В. Ф. Шишов, С. В. Колесникова. – Москва ; Вологда : Инфра-Инженерия, 2025. – 276 с. : ил., табл. ISBN 978-5-9729-2205-5 Приводятся краткие сведения из теории математического программирования и принятия решений. Изложены методы решения задач линейного, целочисленного и нелинейного программирования, задач транспортного типа. На большом количестве примеров иллюстрируются различные приемы решения задач, в том числе военного, производственного и экономического содержания, дается экономико-математический анализ результатов решения и принятие решений на их основе. Подробно рассмотрено решение этих задач средствами MS Excel. В каждом разделе приводится большое количество задач для самостоятельного решения. Для студентов и аспирантов экономических специальностей всех форм обучения, а также может быть полезно преподавателям и практическим работникам, занимающимся вопросами математического программирования и принятия управленческих решений. УДК 338.45 ББК 65.301 ISBN 978-5-9729-2205-5 © Шишов В. Ф., Колесникова С. В., 2025 © Издательство «Инфра-Инженерия», 2025 © Оформление. Издательство «Инфра-Инженерия», 2025
ОГЛАВЛЕНИЕ Введение .................................................................................................................... 5 1. Оптимизационные модели задач линейного программирования ............. 7 1.1. Управление и принятие решений .................................................................... 7 1.2. Построение математической модели ............................................................... 8 1.3. Математические модели задач линейного программирования ................... 10 1.4. Примеры задач линейного программирования ............................................. 13 1.5. Задачи для самостоятельного решения .......................................................... 37 2. Теоретические основы методов линейного программирования ............. 45 2.1. Элементы линейной алгебры ......................................................................... 45 2.2. Выполнение операций над матрицами с применением MS Excel ............. 45 2.3. Решение систем линейных уравнений ........................................................... 57 2.4. Графическое решение уравнений, неравенств и их систем ......................... 64 2.5. Задачи для самостоятельного решения .......................................................... 67 3. Графический метод решения задач линейного программирования ...... 71 3.1. Алгоритм графического метода ..................................................................... 71 3.2. Примеры решения задач графическим методом ........................................... 72 3.3. Задачи для самостоятельного решения .......................................................... 78 4. Симплексный метод решения задач линейного программирования ..... 82 4.1. Алгебраический симплексный метод ............................................................ 82 4.2. Табличный симплексный метод ..................................................................... 90 4.3. М-метод решения задач линейного программирования .............................. 95 4.4. Решение задач линейного программирования с помощью MS Excel ......... 97 4.5. Задачи оптимизации финансов ..................................................................... 107 4.6. Задачи для самостоятельного решения ........................................................ 112 5. Модели целочисленного линейного программирования ........................ 115 5.1. Решение задач целочисленного линейного программирования методом Гомори .................................................................................................... 115 5.2. Метод ветвей и границ .................................................................................. 126 5.3. Решение задач целочисленного программирования с помощью MS Excel ................................................................................................................. 129 5.4. Задачи для самостоятельного решения ........................................................ 139 6. Модели нелинейного программирования .................................................. 144 6.1. Экономическая и геометрическая интерпретация задачи нелинейного программирования ................................................................................................ 144 6.2. Модель планирования производства, учитывающая выпуск брака и эффект от масштаба производства ................................................................... 147 6.3. Модели формирования инвестиционного портфеля ................................. 150 6.4. Решение нелинейной задачи средствами MS Excel .................................... 152 6.5. Задачи для самостоятельного решения ........................................................ 165 7. Двойственные задачи линейного программирования ............................. 173 7.1. Постановка двойственной задачи ................................................................. 173 7.2. Теоремы двойственности и их практическое применение ........................ 177 7.3. Анализ устойчивости двойственных оценок ............................................... 181
7.4. Двойственный симплексный метод .............................................................. 193 7.5. Анализ решения прямой и двойственной задач линейного программирования с помощью MS Excel ........................................................... 200 7.6. Задачи для самостоятельного решения ........................................................ 209 8. Задачи транспортного типа ........................................................................... 219 8.1. Математическая модель транспортной задачи ........................................... 219 8.2. Решение транспортной задачи методом потенциалов ............................... 220 8.3. Особенности транспортных задач и задачи, сводимые к транспортным ................................................................................... 227 8.4. Решение транспортной задачи с помощью MS Excel ................................. 235 8.5. Задача о назначениях ..................................................................................... 256 8.6. Задачи для самостоятельного решения ........................................................ 266 Библиографический список .............................................................................. 274
ВВЕДЕНИЕ Принятие правильных управленческих решений в любой области деятельности человека: хозяйственной, научной, военной или экономической, основываясь только на качественном анализе, опыте или интуиции, становится все труднее. На практике нередко встречаются ситуации, когда достичь какого-либо результата можно различными способами. Тем не менее, из большого набора возможных способов необходимо выбрать наиболее оптимальный. Это стало возможным с использованием методов математического программирования и их составной части – моделей линейного программирования. Знание методов математического программирования стало необходимым широкому кругу лиц, связанных с организацией деятельности коллективов, использующих современные технические средства. Математическое программирование в экономике, технике и других отраслях знаний – научная дисциплина, занимающаяся разработкой и практическим применением методов эффективного управления различными системами. Это стало возможным с использованием методов исследования операций и их составной части – математического программирования. Операцией называется совокупность действий, направленных на достижение поставленной цели. Всякий определенный выбор параметров той или иной операции называется решением. Оптимальными считаются те решения, которые по тем или иным критериям предпочтительнее других. Целью исследования операции является количественное обоснование принимаемых управленческих решений и прогнозных планов развития. В создание современного математического аппарата и развитие многих направлений исследования операций (например, методов линейного программирования) большой вклад внесли российские ученые Л. В. Канторович, Н. П. Бусленко, Е. С. Вентцель, Н. Н. Воробьёв, Н. Н. Моисеев и многие другие. Особо следует отметить роль академика Л. В. Канторовича, который в 1939 г., занявшись планированием работы станочного оборудования фанерной фабрики, решил несколько задач: о наилучшей загрузке оборудования, раскрое материалов с наименьшими потерями, о распределении грузов по нескольким видам транспорта и др. Л. В. Канторович сформулировал новый класс условно-экстремальных задач и предложил универсальный метод их решения, положив начало новому направлению прикладной математики – линейному программированию. Значительные исследования были направлены на применение методов исследования операций в военном деле. За свои разработки в 1975 году Л. В. Канторович, получил Нобелевскую премию в области экономики – единственный из российских ученых.
Большой вклад в формирование и развитие методов исследования операций внесли заруб.ежные ученые Р. Беллман, Д. Данциг, Дж. Нейман, Р. Черчмен и др. Все разделы учебного пособия содержат теоретические основы рассматриваемых вопросов, подробное решение представленных задач с анализом и интерпретацией полученного решения. Приемы решения задач иллюстрируются конкретными примерами экономического и производственного содержания. Представленные задачи решены «вручную» и с использованием программы MS Excel, которая предлагает мощный инструмент их решения – средства поиска решений. При решении задач с использованием MS Excel требуется только грамотно сформулировать задачу, построить ее математическую модель, правильно организовать табличную модель задачи и использовать надстройку MS Excel «Поиск решения», а оптимальное решение будет найдено автоматически. При этом предполагается, что пользователь владеет основами работы в электронных таблицах MS Excel: – умеет вводить и форматировать данные в ячейках; – умеет вводить формулы в ячейки, распространять их («протягивать») на другие ячейки; – знаком с функциями (математическими, статистическими и др.) MS Excel и при необходимости может их использовать. Каждый раздел содержит различные задачи для самостоятельной работы, которые имеют реальное экономическое и производственное содержание. Пособие предназначено для студентов и аспирантов всех специальностей, а также может быть полезно преподавателям и практическим работникам, применяющим методы математического программирования.
1. ОПТИМИЗАЦИОННЫЕ МОДЕЛИ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 1.1. Управление и принятие решений Выбор того или иного варианта действия из множества возможных представляет собой управленческое решение, а сам процесс выбора – принятие решения. Таким образом, управлять – значит принимать решение, а принимать решение – значит осуществлять выбор некоторого, желательно наилучшего, варианта действий. Сущность управления и состоит в управлении любым видом деятельности, в какой бы сфере жизни человека и общества эта деятельность не совершалась – социальной, экономической, духовной, политической, религиозной, правовой, научной, образовательной, военной, спортивной и других. Развитие рыночной экономики породило огромный спрос на новые эффективные методы и подходы к управлению и принятию решений, составляющих существо деятельности менеджеров различного уровня. Управление и принятие решений – фундаментальные понятия, тесным образом связанные между собой и не отделимые друг от друга. Менеджмент как управление деятельностью, по существу, представляет собой совокупность управленческих решений, направленных на достижение поставленных целей. Таким образом, управление – это воздействие на процесс осуществляемой деятельности, которое корректирует его таким образом, чтобы по завершении деятельности поставленная цель оказалась достигнутой. Поэтому в понятии деятельности можно выделить два существенных аспекта. Во-первых, деятельность – это система целенаправленных действий и, во-вторых, – это управляемая система действий. Таким образом, деятельность можно определить следующим образом: деятельность – это система целенаправленных и управляемых действий. Управленческие решения принимаются постоянно, на всех уровнях общества и в повседневной жизни каждого человека. Человек выбирает профессию, место учебы, работу, друзей, прическу, совершает выбор продуктов в магазине, выбирает маршрут и вид транспорта и т. д. Руководители различных уровней выбирают конкретные экономические и административные стратегии, сценарии поведения, ежедневно контролируют ход выполнения работ и принимают решения по наилучшему выполнению всех операций, расставляют работников по работам. Работники банков и инвестиционных компаний принимают решения о выборе объектов инвестирования. На государственном уровне принимаются стратегические решения: проводить реформы или нет, если проводить, то как, с какими странами торговать и многое другое. Руководитель любого уровня должен ясно осознавать, что от принятых им решений зависит не только результат его собственной деятельности, его личное благосостояние, но и достижение поставленных в организации целей, от которых зависит процветание организации, в которой он работает, а значит и благополучие окружающих его людей. Чем выше уровень руководителя, тем более
значимы принятые им решения, тем большее количество людей зависит от них и тем более взвешенными и ответственными должны быть принимаемые им решения. Между собственно управлением и принятием решений имеется глубокая взаимосвязь. Осуществление любого вида деятельности, невозможно без ясно сформулированной цели, наличия которой, однако, еще недостаточно для ее достижения. Для достижения поставленной цели процесс осуществляемой деятельности необходимо корректировать, направлять к желаемому результату, другими словами, деятельностью необходимо управлять. В свою очередь, управление должно быть подчинено поставленной в деятельности цели, без которой выработка направленного управляющего воздействия невозможна. Выбор того или иного варианта управления из множества возможных представляет собой управленческое решение, а сам процесс выбора – принятие решения. Таким образом, управлять – значит принимать решение, а принимать решение – значит осуществлять выбор некоторого и желательно наилучшего (оптимального) варианта действий. Принятие решений в управлении сложными и ответственными видами деятельности и операциями, в которых задействованы значительные материальные, финансовые и человеческие ресурсы, должно проводиться не интуитивно, а только используя научно обоснованные методы. Проблемы принятия решений, рассматриваемые в учебном пособии, описываются конкретными математическими моделями, а решения выбираются на основе объективных критериев, для которых существуют количественные оценки, получаемые в ходе решения соответствующих математических моделей различными методами. Математическое моделирование позволяет находить оптимальные решения, которые будут руководством для любого лица, принимающего решение (ЛПР) в данной конкретной ситуации. 1.2. Построение математической модели Под моделью будем понимать условный образ какого-либо объекта, приближенно воссоздающий этот объект с помощью математического языка. В математических моделях (ММ) таким объектом является любой моделируемый процесс (например, использование ресурсов, распределение изделий между различными типами оборудования), а языком – классические и специальные разработанные математические методы. Если моделируется какой-либо экономический процесс, то модель носит название экономико-математической (ЭММ). Целями моделирования являются: – познание объекта или системы; – прогнозирование поведения объекта; – принятие наилучших решений для достижения объектом поставленных перед ним целей. Математически это сводится к нахождению наибольшего или наименьшего значения соответствующей (целевой) функции. При этом огромное значение
приобретают методы математического программирования (линейного, нелинейного, динамического). Математическое программирование – это раздел математики, занимающийся оптимизацией процессов с помощью поиска наибольшего или наименьшего значения функции при заданных ограничениях. В общем случае для функции n независимых переменных 1 2 ( , ,... ) n y f x x x = задачу математического программирования записывают следующим образом: 1 2 ( , ,... ) max(min), n F x x x → (1.1) при условиях 1 2 1 1 2 1 2 1 2 2 ( , ,... ) , 1,..., ; ( , ,... ) , 1,..., ; ( , ,... ) , 1,..., ; i n i i n i i n i g x x x b i m g x x x b i m m g x x x b i m m = = ° ≥ = + ® ° ≤ = + ¯ (1.2) 1 2 0, 0,..., 0. n x x x ≥ ≥ ≥ (1.3) В задаче математического программирования функцию 1 2 ( , ,... ) n F x x x называют целевой функцией, условия (1.2) – специальными ограничениями задачи математического программирования, а условия (1.3) – общими ограничениями задачи математического программирования. Задача линейного программирования (ЗЛП) – частный случай задачи математического программирования, в которой целевая функция и ограничения являются линейными. Именно этот класс оптимизационных моделей наиболее широко применяется в бизнесе, производстве, экономике. Алгоритм действий лица, принимающего решение (ЛПР) с использованием математических методов Если лицо, принимающее решение (руководитель) осознает, что процесс принятия оптимального решения, невозможен без использования соответствующих математических методов, то алгоритм действий, в этом случае, можно представить в следующем виде. 1. Анализ и формализация рассматриваемого процесса. Надо повести анализ рассматриваемого процесса (проблемы), понять и сформулировать цели, которые планируется достичь, факторы и ограничения, влияющие на решение и возможные результаты решения. То есть в формальном описании воедино собираются цели, факторы и ограничения и где присутствует основа для формализации отношений и зависимостей между ними.
2. Построение математической модели. Перевод формальной модели, представленной на предыдущем этапе, на язык математики. Это самый важный и сложный этап, поскольку от правильности построенной модели и ее вида зависит выбор методов и инструментов решения и получения надежных результатов решения. Примерный алгоритм при этом следующий: – выбрать некоторое число переменных величин, числовые значения которых однозначно определяют одно из возможных решений задачи; – выразить взаимосвязи, присущие исследуемому объекту (процессу), в виде математических соотношений (уравнений, неравенств); эти соотношения образуют систему ограничений задачи; – выразить выбранный критерий оптимальности в форме целевой функции (критерий оптимальности – это признак, по которому множество или одно решение задачи признается наилучшим); – дать математическую формулировку задачи как задачи отыскания экстремума целевой функции при условии выполнения ограничений, накладываемых на переменные. 3. Анализ построенной математической модели и ее решение. Проводится анализ построенной математической модели с точки зрения соответствия ее изучаемому процессу и находится ее решение. Если для решения математической модели используется вычислительная техника, то предварительно строится компьютерная модель задачи. Этот этап и сам процесс решения математической модели достаточно формализован, при этом используются хорошо разработанные алгоритмы, методы и соответствующие вычислительные инструменты. 4. Анализ полученного решения математической модели и формирование управленческого решения. После выполнения всех этих этапов следует процесс реализации принятого управленческого решения. 1.3. Математические модели задач линейного программирования Форма записи целевой функций и системы ограничений в различных задачах линейного программирования могут быть представлены по-разному в зависимости от содержательной постановки задачи. Различают три основные формы записи задач линейного программирования, к которым может быть сведена любая из задач. Общая форма записи задач линейного программирования Задачу линейного программирования в общем виде можно сформулировать следующим образом.