Формирование исследования операций как самостоятельной ветви прикладной математики относится к периоду 40-х и 50-х годов

Вид материалаДокументы

Содержание


Система является замкнутой, если никакое воздействие извне не влияет на устойчивость и развитие системы, и незамкнутой в противн
Постановка задачи.
Формализация задачи.
Нахождение метода решения.
Проверка и корректировка модели.
Реализация найденного решения на практике.
В качестве таких примеров приведем несколько классических экономико-математических моделей и задач, которые могут быть сформулир
Транспортная задача.
Задачи сетевого планирования и управления (СПУ)
Задачи массового обслуживания
Задачи управления запасами
Подобный материал:
Введение


Формирование исследования операций как самостоятельной ветви прикладной математики относится к периоду 40-х и 50-х годов. Последующие полтора десятилетия были отмечены широким применением полученных фундаментальных теоретических результатов к разнообразным практическим задачам. В результате исследование операций приобрело черты классической прикладной научной дисциплины, без которой немыслимо базовое экономическое образование.

Среди первых исследований в данном направлении может быть названа работа Л. В. Канторовича «Математические методы организации и планирования производства», вышедшая в 1939 г. Канторович стал в 1975 г. лауреатом Нобелевской премии за свои работы по оптимальному использованию ресурсов в экономике. В зарубежной литературе отправной точкой обычно считается вышедшая в 1947 г. работа Данцига, посвященная решению линейных экстремальных задач.

Следует отметить, что не существует жесткого, устоявшегося и общепринятого определения предмета исследования операций. Часто при ответе на данный вопрос говорится, что «исследование операций представляет собой комплекс научных методов для решения задач эффективного управления организационными системами».

Природа систем, фигурирующих в приведенном определении под именем «организационных», может быть самой различной, а их общие математические модели находят применение не только при решении производственных и экономических задач, но и в биологии, социологических исследованиях и других практических сферах. Кстати, само название дисциплины связано с применением математических методов для управления военны­ми операциями.

СИСТЕМЫ

В науке со второй половины 20 века укоренился так называемый «системный подход», ставший ведущим методом современного научного познания. В самой общей формулировке это означает, что каждый объект принадлежит некоторой системе объектов, обладает в рамках этой системы некоторым смыслом (ролью), т.е. несет в себе некоторую информацию, и должен рассматриваться в контексте этой системы. Из этого следует, в частности, что объект нельзя преобразовывать, не затронув при этом других объектов. Этот метод становится на сегодняшний день ведущим в науке.

Основу такого системного подхода заложил своими трудами великий ученый Норберт Винер. Он создал новое направление в науке - кибернетику (теории управления), где ввел понятия системы, замкнутой и незамкнутой, и заложил основные принципы анализа устойчивости и развития систем.

Система является замкнутой, если никакое воздействие извне не влияет на устойчивость и развитие системы, и незамкнутой в противном случае

Переход к системному подходу и системному анализу продиктован всем течением жизни современного человека. Еще сто лет назад мир казался человеку огромным и возможности по его освоению и преобразованию безграничными. Но двадцатый век заставил человека задуматься – развитие технологий шагнуло вперед с такой скоростью, что теперь действия человека угрожают уничтожением всему миру и самому человеку, в частности. Пришло осознание, что все в мире взаимосвязано, и любое воздействие изменяет окружающую среду. Так, что переход к системному исследованию является объективно обоснованным.

В рамках таких систем можно рассматривать отдельное предприятие, регион, город, муравейник, биржу, рынок и т.д.

В принципе, из общего понятия систем, как взаимосвязанных объектов, рассматриваемых как единое целое, выделяется класс систем, назовем их организационными, в которых можно выделить цель этой системы. В частности, в качестве цели может быть сохранение или развитие системы (страна, регион), получение максимальной прибыли (производство), эффективное распределение средств, экономия и т.п., для достижения которых возможно целенаправленное воздействие.

Поговорим о задачах, решаемых средствами исследования операций. Под операцией мы будем понимать любое планируемое мероприятие.

ПРИМЕРЫ

Для обеспечения высокого качества выпускаемых изделий организуется система выборочного контроля. Требуется выбрать такие формы его организации, чтобы обеспечить необходимое качество при минимальных расходах (размеры контрольных партий, частоту проверки, правила отбраковки и т.д.).

Для реализации сезонных товаров организуется сеть временных торговых точек. Требуется выбрать параметры сети – число точек, их размещение, количество персонала, чтобы обеспечить максимальную экономическую эффективность распродажи.

Необходимо провести массовое медицинское обследование населения. На обследование выделены деньги, оборудование, персонал. Требуется разработать такой план обследования – установить число медпунктов, их размещение и т.д., чтобы максимально выявить заболевших.

Необходимо отметить также задачи о планировании производства (использовании ресурсов), о смесях, о максимальной загрузке оборудования, о посеве, о раскрое материала, о коммивояжере, транспортную задачу, в которых требуется найти решение, когда некоторый критерий эффективности – прибыль, выручка, затраты - принимает максимальное или минимальное значение.

Все эти задачи, несмотря на их разнообразие, имеют общие черты. В каждом случае речь идет о некотором управляемом мероприятии, преследующем определенную цель. В каждом случае заданы некоторые условия проведения этого мероприятия, в рамках которых следует принять решение – такое, чтобы выбранный критерий был наиболее эффективен.

В первой задаче решением будет выбор размера контрольной партии, частоты проверок, правил отбраковки, во второй – количество точек продаж и персонала и т.д.

Важнейшим инструментом исследования организационных систем является моделирование. В частности, в случае решения задач исследования операций – математическое моделирование, т.е. моделирование в виде математических формул, графиков, таблиц и т.п.

Несмотря на многообразие задач организационного управления, при их решении можно выделить некоторую общую последовательность этапов, через которые проходит любое операционное исследование.
  1. Постановка задачи.

Первоначально задачу формулируют с точки зрения заказчика. Во время анализа системы задача постепенно уточняется. Определяются объект и цель исследования. Происходит формализация цели управления объектом, выделение возможных управляющих воздействий (управляющих переменных и параметров), влияющих на достижение сформулированной цели, а также описание системы ограничений на управляющие воздействия.
  1. Формализация задачи.

Построение математической модели, т. е. перевод сконструированной содержательной модели в ту форму, в которой для ее изучения может быть использован математический аппарат.
  1. Нахождение метода решения.

Для нахождения оптимального решения в зависимости от структуры задачи применяют те или иные методы теории оптимальных решений, называемые также методами математического программирования.
  1. Проверка и корректировка модели.

В сложных системах, к которым относятся системы организационного типа, модель лишь частично отражает реальный процесс. Поэтому необходима проверка степени соответствия или адекватности модели и реального процесса. Проверку производят сравнением предсказанного поведения с фактическим при изменении значений внешних неуправляемых воздействий. Корректировка может потребовать дополнительных исследований объекта, уточнения структуры математической модели, многочисленных изменений переменных. Таким образом, 4 этапа многократно повторяются, пока не будут достигнуто удовлетворительное соответствие между выходами объекта и модели.
  1. Реализация найденного решения на практике.

Внедрение можно рассматривать как самостоятельную задачу, применив к ней системный подход и анализ.

Сам процесс математического моделирования в исследовании операций является, с одной стороны, очень важным и сложным, а с другой — практически не поддающимся научной формализации процессом. Заметим, что неоднократно предпринимавшиеся попытки выделить общие принципы создания математических моделей приводили либо к декларированию рекомендаций самого общего характера, трудноприложимых для решения конкретных проблем, либо, наоборот, к появлению рецептов, применимых в действительности только к узкому кругу задач. Поэтому более полезным представляется знакомство с техникой математического моделирования на конкретных примерах.

Мы постараемся получить общее представление о типах задач, изучаемых в исследовании операций, методах их решения и принципиальных идеях, лежащих в основе этих методов.

В качестве таких примеров приведем несколько классических экономико-математических моделей и задач, которые могут быть сформулированы на их основе.


Простейшая задача производственного планирования (оптимального использования ресурсов).

Общий смысл задач этого класса сводится к следующему.

Предприятие выпускает n различных изделий. Для их производства требуется m различных видов ресурсов (сырья, материалов, рабочего времени и т.п.). Ресурсы ограничены, их запасы в планируемый период составляют, соответственно, b1, b2,..., bm условных единиц.

Известны также технологические коэффициенты aij, которые показывают, сколько единиц i-го ресурса требуется для производства единицы изделия j-го вида (   ).

Прибыль, получаемая предприятием при реализации изделия j-го вида, равна cj.

В планируемом периоде значения величин aij, bi и cj остаются постоянными.

Требуется составить такой план выпуска продукции, при реализации которого прибыль предприятия была бы наибольшей.

Транспортная задача.

Рассмотрим проблему организации перевозки некоторого продукта между пунктами его производства, количество которых равно m, и n пунктами потребления. Каждый i-й пункт производства характеризуется запасом продукта аi  0, а каждый j-и пункт потребления — потребностью в продукте bj  0. Сеть дорог, соединяющая систему рассматриваемых пунктов, моделируется с помощью матрицы С размерности m на n, элементы которой сi,j представляют собой нормы затрат на перевозку единицы груза из пункта производства i в пункт потребления j. План перевозки груза в данной транспортной сети представляется в виде массива элементов размерности mn:

Задача состоит в минимизации затрат на перевозку грузов.

Общим для рассмотренных выше задач является то, что в них стоит проблема поиска наибольшего или наименьшего (оптимального) значения некоторой функции, отражающей цель управления системой, или, как еще говорят, целевой функции. Поиск оптимального значения осуществляется на некотором подмножестве допустимых значений переменных, описывающих состояние этой системы, именуемом множеством допустимых планов. Область допустимых планов формируется на основе условий проведения операций, как правило, представленных в модели в виде неравенств.

Пусть на некотором множестве D определена функция f(x) . Напомним, что точка х*, принадлежащая D (х*D), называется точкой глобального максимума, если для любого x  D выполняется неравенство f(x)
Необходимо отметить, что далеко не всегда весь комплекс целей и задач, стоящий перед моделируемым объектом, может быть выражен в форме некоторой целевой функции. Более того, осознание и осмысление этой проблемы стало своего рода переломным этапом в истории развития исследования операций как науки, положившим конец многим необоснованным ожиданиям и одновременно давшим толчок к развитию новых направлений, связанных с методами многокритериальной оптимизации. Однако следует иметь в виду, что все они базируются на фундаменте методов однокритериальной оптимизации, без ясного понимания которых невозможна работа с более сложным математическим аппаратом.

Мощным инструментом разрешения подобного рода задач стали специальные методы поиска экстремума, составляющие содержание раздела исследования операций, который называется математическое программирование. В данном случае понятие программирование употребляется в смысле планирование (в отличие от программирования для ЭВМ).

В свою очередь, в зависимости от вида решаемых задач, в математическом программировании выделяют такие области, как линейное, нелинейное, дискретное, динамическое, геометрическое, стохастическое программирование.

Множество других задач исследования операций может быть разбито на ряд классов.

Задачи сетевого планирования и управления (СПУ) рассматривают соотношения между сроками крупного комплекса операций (работ) и моментами начала всех операций комплекса. Эти задачи состоят в нахождении минимальных продолжительностей комплекса операций, оптимального соотношения величин стоимости и сроков их выполнения.

СПУ используется при разработке крупных народнохозяйственных комплексов, при планировании научных исследований, при конструкторской и технологической подготовке производства новых видов изделий, при строительстве и реконструкции, капитальном ремонте основных фондов и т.д.

Задачи массового обслуживания посвящены изучению и анализу систем с очередями заявок или требований и состоят в определении показателей эффективности работы систем, например, в определении числа каналов обслуживания, времени обслуживания и т.п. Примерами таких систем являются телефонные системы, ремонтные мастерские, вычислительные комплексы, билетные кассы, магазины и т.д.

Задачи управления запасами состоят в отыскании оптимальных значений уровня запасов и размера заказа. С увеличением уровня запасов, с одной стороны, увеличиваются затрат на их хранение, но, с другой стороны, уменьшаются потери вследствие возможного дефицита продукта.

Они имеют важное народохозяйственное значение. Правильное и своевременное определение оптимальной стратегии управления запасами, а также нормативного уровня запасов позволяет высвободить значительные оборотные средства, замороженные в виде запасов, что в конечном счете повышает эффективность использования ресурсов.

Задачи распределения ресурсов, задачи ремонта и замены оборудования, задачи составления расписания (календарного планирования), задачи выбора маршрута – вот неполный перечень задач, рассматриваемых в исследовании операций.

Среди моделей исследования операций необходимо отметить модели принятия оптимальных решений в конфликтных ситуациях, изучаемые теорией игр. В задачах теории игр необходимо выработать рекомендации по разумному поведению участников конфликта, определить их оптимальные стратегии.



Исследование операций – лекция 1