методы математического програмировани. методы математического програмирования. Формирование исследования операций как самостоятельной ветви прикладной математики относится к периоду 40х и 50х годов
 Скачать 0.98 Mb.
|
|
ВВЕДЕНИЕ Формирование исследования операций как самостоятельной ветви прикладной математики относится к периоду 40-х и 50-х годов. Последующие полтора десятилетия были отмечены широким применением полученных фундаментальных теоретических результатов к разнообразным практическим задачам и связанным с этим переосмыслением потенциальных возможностей теории. В результате исследование операций приобрело черты классической научной дисциплины, без которой немыслимо базовое экономическое образование. Следует отметить, что не существует жесткого, устоявшегося и общепринятого определения предмета исследования операций. Часто при ответе на данный вопрос говорится, что операционный анализ представляет собой применение научных методов к сложным проблемам, возникающим в управлении большими системами людей, машин, материалов и денег в промышленности, деловых кругах, правительстве и обороне. Характерной особенностью подхода является построение для системы научной модели, включающей факторы вероятности и риска, при помощи которой можно рассчитать и сравнить результаты различных решений, стратегий и управлений. Второе определение: Исследование операций – это научная подготовка принимаемого решения – это совокупность методов, предлагаемых для подготовки и нахождения самых эффективных или самых экономичных решений [8]. Управление любой системой реализуется как процесс, подчиняющийся определенным закономерностям. Их знание помогает определить условия, необходимые и достаточные для осуществления данного процесса. Для этого все параметры, характеризующие процесс и внешние условия, должны быть количественно определены, измерены. Следовательно, цель исследования операций — количественное обоснование принимаемых решений по организации управления. При решении конкретной задачи управления применение методов исследования операций предполагает: построение экономических и математических моделей для задач принятия решения в сложных ситуациях или в условиях неопределенности; изучение взаимосвязей, определяющих впоследствии принятие решений, и установление критериев эффективности, позволяющих оценивать преимущество того или иного варианта действия. Первые формальные разработки по исследованию операций (ИО) были инициированы в Англии во время Второй мировой войны, когда команда британских ученых сформулировала и нашла решение задачи наиболее эффективной доставки военного снаряжения на фронт. После окончания войны эти идеи были перенесены в гражданскую сферу для повышения эффективности и продуктивности экономической и производственной деятельности. Сегодня теория исследования операций является основным и неотъемлемым инструментом при принятии решений в самых разнообразных областях человеческой деятельности [5]. Краеугольным камнем исследования операций является математическое моделирование. Хотя данные, полученные в процессе исследования математических моделей, являются основой для принятия решений, окончательный выбор обычно делается с учетом многих других "нематериальных" (не имеющих числового выражения) факторов (таких как человеческое поведение), которые невозможно отобразить в математических моделях [4]. В исследовании операций нет единого общего метода решения всех математических моделей, которые встречаются на практике. Вместо этого выбор метода решения диктуют тип и сложность исследуемой математической модели. Практически все методы ИО не позволяют получить решение в замкнутой (в виде формул) форме. Напротив, они порождают вычислительные алгоритмы, которые являются итерационными по своей природе. Это означает, что задача решается последовательно (итерационно), когда на каждом шаге (итерации) получаем решения, постепенно сходящиеся к оптимальному. Итерационная природа алгоритмов обычно приводит к объемным однотипным вычислениям, В этом и заключается причина того, что эти алгоритмы разрабатываются, в основном, для реализации с помощью вычислительной техники. Некоторые математические модели могут быть такими сложными, что их невозможно решить никакими доступными методами оптимизации. В этом случае остается только эвристический подход: поиск подходящего "хорошего" решения вместо оптимального. Эвристический подход предполагает наличие эмпирических правил, в соответствии с которыми ведется поиск подходящего решения [5]. Несмотря на впечатляющие достижения математического моделирования, многие реальные ситуации невозможно адекватно представить с помощью соответствующих математических моделей. Часто в этом "виновата" определенная "жесткость" математики как языка описания и представления событий и явлений. Но даже если существует возможность формализовать рассматриваемую жизненную ситуацию посредством построения математической модели, полученная на ее основе задача оптимизации может быть слишком сложной для современных алгоритмов решения задач этого класса [6]. Альтернативой математическому моделированию сложных систем может служить имитационное моделирование. Различие между математической и имитационной моделями заключается в том, что в последней отношение между "входом" и "выходом" может быть явно не задано. Вместо явного математического описания взаимоотношения между входными и выходными переменными математической модели, при имитационном моделировании реальная система разбивается на ряд достаточно малых (в функциональном отношении) элементов или модулей. Затем поведение исходной системы имитируется как поведение совокупности этих элементов, определенным образом связанных (путем установки соответствующих взаимосвязей) в единое целое. Вычислительная реализация такой модели начинается с входного элемента, далее проходит по всем элементам, пока не будет достигнут выходной элемент. Имитационные модели значительно гибче в представлении реальных систем, чем их математические "конкуренты". Причина такой гибкости заключается в том, что при имитационном моделировании исходная система рассматривается на элементарном уровне, а математические модели стремятся описать системы на глобальном уровне. За гибкость имитационных моделей приходится платить высокими требованиями к потребляемым временным и вычислительным ресурсам. Поэтому реализация некоторых имитационных моделей даже на современных быстрых и высокопроизводительных компьютерах может быть очень медленной [4]. Несмотря на многообразие задач организационного управления, при их решении можно выделить некоторую общую последовательность этапов, через которые проходит любое операционное исследование. Как правило, это: Постановка задачи. Формируется концептуальная модель исследуемой системы (задачи), в которой в содержательной форме описывается состав системы, ее компоненты и их взаимосвязи, перечень основных показателей качества, переменных, как контролируемых так и неконтролируемых внешних факторов, а также их взаимосвязей с показателями качества системы, перечень стратегий управления (или решений), которые надо определить в результате решения поставленной задачи. Построение содержательной (вербальной) модели рассматриваемого объекта (процесса). На данном этапе происходит формализация цели управления объектом, выделение возможных управляющих воздействий, влияющих на достижение сформулированной цели, а также описание системы ограничений на управляющие воздействия. Построение математической модели, т. е. перевод сконструированной вербальной модели в ту форму, в которой для ее изучения может быть использован математический аппарат. Решение задач, сформулированных на базе построенной математической модели. После достижения удовлетворительного уровня адекватности модели применяют соответствующий метод или алгоритм для нахождения оптимального (или субоптимального) решения на математической модели. Это решение может принимать разные формы: аналитическую, численную, или алгоритмическую (в виде набора процедур, правил, и т.п.). Проверка полученных результатов на их адекватность природе изучаемой системы, включая исследование влияния так называемых внемодельных факторов, и возможная корректировка первоначальной модели. Реализация полученного решения на практике. Это один из важнейших этапов, завершающий операционное исследование. Внедрение в практику найденного на модели решения можно рассмотреть как самостоятельную задачу, применив системный подход и анализ. Полученной на модели оптимальной стратегии управления необходимо предоставить соответствующую содержательную форму в виде инструкций и правил, что и как делать, которая была бы понятной для административного персонала данной фирмы или организации и легкой для выполнения в производственных условиях [8]. Методы исследования операций Если критерий эффективности (целевая функция)представляет линейную функцию, а функции в системе ограничений также линейны, то такая задача является задачей линейного программирования. Если, исходя из содержательного смысла, ее решения должны быть целыми числами, то эта задача целочисленного линейного программирования. Если критерий эффективности и (или) система ограничений задаются нелинейными функциями, то имеем задачу нелинейного программирования. В частности, если указанные функции обладают свойствами выпуклости, то полученная задача является задачей выпуклого программирования. Если в задаче математического программирования имеется переменная времени и критерий эффективности выражается не в явном виде как функция переменных, а косвенно — через уравнения, описывающие протекание операций во времени, то такая задача является задачей динамического программирования. Если критерий эффективности и система ограничений задаются функциями представляющих собой сумму произведений степенных функций от независимых переменных, то имеем задачу геометрического программирования. Если функции в выражениях зависят от параметров, то получаем задачу параметрического программирования, если эти функции носят случайный характер, — задачу стохастического программирования. Если точный оптимум найти алгоритмическим путем невозможно из-за чрезмерно большого числа вариантов решения, то прибегают к методам эвристического программирования, позволяющим существенно сократить просматриваемое число вариантов и найти если не оптимальное, то достаточно хорошее, удовлетворительное с точки зрения практики, решение. Из перечисленных методов математического программирования наиболее распространенным и разработанным является линейное программирование, В его рамки укладывается широкий круг задач исследования операций. По своей содержательной постановке множество других, типичных задач исследования операций может быть разбито на ряд классов. Задачи сетевого планирования и управления рассматривают соотношения между сроками окончания крупного комплекса операций (работ) и моментами начала всех операций комплекса. Эти задачи состоят в нахождении минимальных продолжительностей комплекса операций, оптимального соотношения величин стоимости и сроков их выполнения. Задачи массового обслуживания посвящены изучению и анализу систем обслуживания с очередями заявок или требований и состоят в определении показателей эффективности работы систем, их оптимальных характеристик, например, в определении числа каналов обслуживания, времени обслуживания и т.п. Задачи управления запасами состоят в отыскании оптимальных значений уровня запасов (точки заказа) и размера заказа. Особенность таких задач заключается в том, что с увеличением уровня запасов, с одной стороны, увеличиваются затраты на их хранение, но с другой стороны, уменьшаются потери вследствие возможного дефицита запасаемого продукта. Задачи распределения ресурсов возникают при определенном наборе операций (работ), которые необходимо выполнять при ограниченных наличных ресурсах, и требуется найти оптимальные распределения ресурсов между операциями или состав операций. Задачи ремонта и замены оборудования актуальны в связи с износом и старением оборудования и необходимостью его замены с течением времени. Задачи сводятся к определению оптимальных сроков, числа профилактических ремонтов и проверок, а также моментов замены оборудования модернизированным. Задачи составления расписания (календарного планирования) состоят в определении оптимальной очередности выполнения операций (например, обработки деталей) на различных видах оборудования. Задачи планировки и размещения состоят в определении оптимального числа и места размещения новых объектов с учетом их взаимодействия с существующими объектами и между собой. Задачи выбора маршрута, или сетевые задачи, чаше всего встречаются при исследовании разнообразных задач на транспорте и в системе связи и состоят в определении наиболее экономичных маршрутов. На практике в большинстве случаев успех операции оценивается не по одному, а сразу по нескольким критериям, один из которых следует максимизировать, другие — минимизировать. Математический аппарат может принести пользу и в случаях многокритериальных задач исследования операции, по крайней мере, помочь отбросить заведомо неудачные варианты решений. Попытка сведения многокритериальной задачи к задаче с одним критерием эффективности (целевой функцией) в большинстве случаев не дает удовлетворительных результатов. Другой подход состоит в отбрасывании ("выбраковке") из множества допустимых решений заведомо неудачных решений, уступающих другим по всем критериям. В результате такой процедуры остаются так называемые эффективные (или "паретовские") решения, множество которых обычно существенно меньше исходного. А окончательный выбор "компромиссного" решения (не оптимального по всем критериям, которого, как правило, не существует, а приемлемого по этим критериям) остается за человеком — лицом, принимающим решение. Методы исследования операций, как и любые математические методы, всегда в той или иной мере упрощают, огрубляют задачу, отражая порой нелинейные процессы линейными моделями, стохастические системы — детерминированными, динамические процессы — статическими моделями и т.д. Жизнь богаче любой схемы. Поэтому не следует ни преувеличивать значение количественных методов исследования операций, ни преуменьшать его, ссылаясь на примеры неудачных решений. Уместно привести в связи с этим шутливо-парадоксальное определение исследования операций, сделанное одним из его создателей Т. Саати, как "искусства давать плохие ответы на те практические вопросы, на которые даются еще худшие ответы другими методами" [7]. ПОСТАНОВКА ЗАДАЧИ Нефтеперерабатывающий завод закупает сырую нефть у двух компаний: “Севернефть” (по цене 75000 ден.ед./т) и “Афройл” (67000 ден.ед./т). Нефть, поставляемая компанией “Севернефть”, содержит 10% примесей, которые необходимо удалять при очистке. Нефть, поставляемая компанией “Афройл”, содержит 15% таких примесей. Очищенная нефть смешивается для получения двух видов смазочных материалов: “Люкс” и “Стандарт”. Смазочный материал “Люкс” должен содержать не менее 10% нефти компании “Севернефть” и не более 25% нефти компании “Афройл”. Смазочный материал “Стандарт” должен содержать не менее 15% нефти компании “Севернефть”. Смазочные материалы продаются по следующим ценам: “Люкс” – 90000 ден.ед./т, “Стандарт” – 87000 ден.ед./т. Спрос на смазочный материал “Люкс” не превышает 100000 т., “Стандарт” – 120000 т. Составить план закупок и использования нефти, обеспечивающий нефтеперерабатывающему заводу максимальную прибыль. ПОСТРОЕНИЕ АНАЛИТИЧЕСКОЙ МОДЕЛИ Составим аналитическую модель задачи, для этого введем переменные:  : количество тонн нефти компании “Севернефть” купленной для изготовления смазочного материал “Люкс”  : количество тонн нефти компании “Севернефть” купленной для изготовления смазочного материал “Стандарт” : количество тонн нефти компании “Афройл” купленной для изготовления смазочного материал “Люкс”  : количество тонн нефти компании “Афройл” купленной для изготовления смазочного материал “Стандарт”Закупаемая у поставщиков нефть содержит примеси и потому перед ее использованием необходимо произвести очистку. После очистки нефти компании “Севернефть” будет получено 90% очищенной, так как примеси составляют 10%. Таким образом, для величин , будет получено  ,  очищенной от примесей нефти. Нефть компании “Афройл” содержит 15% примесей, следовательно очищенной нефти для величин , будет получено  и  .Введем ограничения. Ограничения действующие при производстве смазочного материала “Люкс”:  - данный смазочный материл должен содержать не менее 10% нефти компании “Севернефть”. - в данном смазочном материале не должно использоваться более чем 25% нефти компании “Афройл”. - спрос на данный тип смазочного материала не превышает 100000т.Ограничения действующие при производстве смазочного материала “Стандарт”:  - в данном смазочном материл должно содержаться не менее 15% нефти компании “Севернефть”. - спрос на данный тип смазочного материала не превышает 120000т.Составим целевую функцию. Затраты нефтеперерабатывающего завода на закупку нефти у поставщиков:  - затраты на покупку нефти у компании “Севернефть” - затраты на покупку нефти у компании “Афройл”Прибыль, получаемая предприятием, от продажи смазочных материалов:  - прибыль от продажи смазочного материала “Люкс” - прибыль от продажи смазочного материала “Стандарт”Таким образом,  После раскрытия скобок и приведения подобных слагаемых, получим результирующее уравнение целевой функции: - это прибыль предприятия, которую необходимо максимизировать.Математическая модель: 0,81 -0,085 ≥00,77 -0,13 ≥0-0,23 +0,64 ≤00,9 +0,85 ≤1000000,9 +0,85 ≤120000 , , , ≥0 →maxЧтобы избежать необходимости в использовании двухэтапного симплекс-метода умножим ограничения вида «больше или равно» на (-1). Таким образом, в математической модели задачи будут присутствовать только ограничения вида «меньше или равно», что позволяет решать ее обычным симплекс-методом. Математическая модель: -0,81 +0,085 ≤0-0,77 +0,13 ≤0-0,23 +0,64 ≤00,9 +0,85 ≤1000000,9 +0,85 ≤120000 , , , ≥0 →max |