Реферат: Задача исследования операций. Предмет и задачи исследования операций в экономике. Основные понятия теории исследования операций Правильные определения понятия исследование операций

Исследование операций

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

Исследование операций - применение математических, количественных методов для обоснования решений во всех областях целенаправленной человеческой деятельности. Исследование операций начинается тогда, когда для обоснования решений применяется тот или другой математический аппарат. Операция - всякое мероприятие (система действий), объединённое единым замыслом и направленное к достижению какой-то цели (напр., мероприятия задач 1-8, указанных ниже, будут операциями). Операция всегда является управляемым мероприятием, то есть зависит от человека, каким способом выбрать параметры, характеризующие её организацию (в широком смысле, включая набор технических средств, применяемых в операции). Решение (удачное, неудачное, разумное, неразумное) - всякий определённый набор зависящих от человека параметров. Оптимальное - решение, которое по тем или другим признакам предпочтительнее других. Цель исследования операций - предварительное количественное обоснование оптимальных решений с опорой на показатель эффективности . Само принятие решения выходит за рамки исследования операций и относится к компетенции ответственного лица (лиц). Элементы решения - параметры, совокупность которых образует решение: числа, векторы, функции, физические признаки и т. д. Если элементами решения можно распоряжаться в определённых пределах, то заданные («дисциплинирующие») условия (ограничения) фиксированы сразу и нарушены быть не могут (грузоподъёмность, размеры, вес). К таким условиям относятся средства (материальные, технические, людские), которыми человек вправе распоряжаться, и иные ограничения, налагаемые на решение. Их совокупность формирует множество возможных решений .

Примеры: Составляется план перевозок грузов из пунктов отправления А 1 , А 2 , …, А m в пункты назначения В 1 , В 2 , …, В n . Элементы решения - числа x ij , показывающие, какое количество груза будет отправлено из i-го пункта отправления А i в j-й пункт назначения В j . Решение - совокупность чисел x 11 , x 12 , …, x m1 , x m2 , …, x mn

Не до конца ясно будущее соотношение между ИО и теорией (сложных) систем .

Типичные задачи

Взяты из разных областей практики

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

Некоторые примеры формулировок задач, имеющих отношение к ИО:

Задачи составления расписания, диспетчеризации такие как Open Shop Scheduling Problem, Flow Shop Scheduling Problem, Job Shop Scheduling Problem (англ. en:Job shop scheduling ) и т. д.

Характерная особенность исследования операций - системный подход к поставленной проблеме и анализ. Системный подход является главным методологическим принципом исследования операций. Он заключается в следующем. Любая задача, которая решается, должна рассматриваться с точки зрения влияния на критерии функционирования системы в целом. Для исследования операций характерно то, что при решении каждой проблемы могут возникать новые задачи. Важной особенностью исследования операций есть стремление найти оптимальное решение поставленной задачи (принцип «оптимальности»). Однако на практике такое решение найти невозможно по таким причинам:

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

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

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

История

В начале войны боевое патрулирование самолетов союзников для обнаружения кораблей и подводных лодок противника носило неорганизованный характер. Привлечение к планированию специалистов по исследованию операций позволило установить такие маршруты патрулирования и такое расписание полетов, при которых вероятность оставить объект незамеченным была сведена до минимума. Полученные рекомендации были применены для организации патрулирования над Южной Атлантикой с целью перехвата немецких кораблей с военными материалами. Из пяти вражеских кораблей, прорвавших блокаду, три были перехвачены на пути из Японии в Германию, один был обнаружен и уничтожен в Бискайском заливе и лишь одному удалось скрыться благодаря тщательной маскировке.

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

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

В США внедрение методов исследования операций в практику управления экономикой происходило несколько медленнее - но и там многие концерны вскоре стали привлекать специалистов такого рода для решения проблем, связанных с регулированием цен, повышением производительности труда, ускорением доставки товаров потребителям и пр. Лидерство в области применения научных методов управления принадлежало авиационной промышленности, которая не могла не идти в ногу с растущими требованиями к ВВС. В 1950-1960-е годы на Западе создаются общества и центры исследования операций, выпускающие собственные научные журналы, большинство западных университетов включает эту дисциплину в свои учебные планы.

Наибольший вклад в формирование и развитие новой науки сделали Р. Акоф , Р. Беллман , Дж. Данциг , Г. Кун, Т. Саати (англ.) русск. , Р. Чермен (США), А. Кофман, Р. Форд (Франция) и др.

Важная роль в создании современного математического аппарата и развития многих направлений исследования операций принадлежит Л. В. Канторовичу , Б. В. Гнеденко, М. П. Бусленко, В. С. Михалевичу, Н. Н. Моисееву, Ю. М. Ермолаеву, Н. З. Шору и др.

За выдающийся вклад в разработку теории оптимального использования ресурсов в экономике академику Л. В. Канторовичу вместе с профессором Т. Купмансом (США) в 1975 году присвоена Нобелевская премия в экономике.

См. также

Примечания

Литература

Хемди А. Таха. Введение в исследование операций = Operations Research: An Introduction. - М .: Вильямс, 2007. - 912 с. - ISBN 0-13-032374-8
Дегтярёв Ю. И. Исследование операций: учебник для вузов по специальности АСУ. - М .: Высшая школа, 1986.
Грешилов А. А. Математические методы принятия решений. - М .: МГТУ им. Н.Э. Баумана, 2006. - 584 с. - ISBN 5-7038-2893-7

Ссылки

Исследование операций в каталоге ссылок Open Directory Project (dmoz).

Wikimedia Foundation . 2010 .

Смотреть что такое "Исследование операций" в других словарях:

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

Прикладное направление кибернетики, используемое для решения организационных (в т. ч. экономических) задач (распределения ресурсов, управления запасами, упорядочения и согласования и др.). Главный метод системный анализ целенаправленных действий… … Большой Энциклопедический словарь

Исследование операций - прикладное направление кибернетики, используемое для решения практических организационных (в том числе экономических) задач. Это комплексная научная дисциплина. Круг проблем, изучаемых ею, пока недостаточно… … Экономико-математический словарь

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

ИССЛЕДОВАНИЕ ОПЕРАЦИЙ - метод изучения, анализа и оценки операций, их количественных и качественных показателей. Исследует ход и исход операций с учетом принимаемых решений, количественных и качественных характеристик соотношения сил и средств, способов боевого… … Война и мир в терминах и определениях

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

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

Прикладное направление кибернетики, используемое для решения организационных (в т. ч. экон.) задач (распределения ресурсов, управления запасами, упорядочения и согласования и др.). Гл. метод системный анализ целенаправленных действий (операций) и … Естествознание. Энциклопедический словарь

ИССЛЕДОВАНИЕ ОПЕРАЦИЙ - направление в экономико математических методах, основанное на моделировании математических процессов и явлений. И.о. предполагает системный подход, состоящий в поиске существенных взаимодействий при оценке деятельности или стратегии любой части… … Большой экономический словарь

ИССЛЕДОВАНИЕ ОПЕРАЦИЙ - направление в исследовании и проектировании СЧМ, основанное на математическом моделировании процессов и явлений. И. о. предполагает системный подход, состоящий в поиске существующих взаимодействий при оценке деятельности или стратегии любой части … Энциклопедический словарь по психологии и педагогике Подробнее

Под операцией мы будем понимать любое мероприятие (или систему действий), объединенное единым замыслом и направленное к достижению определенной цели.

Примеры операций.

1. Система мероприятий, направленная к повышению надежности технического устройства.
2. Отражение воздушного налета средствами ПВО.
3. Размещение заказов на производство оборудования.
4. Разведывательный поиск группы самолетов в тылу противника.
5. Запуск группы искусственных спутников Земли для установления системы телевизионной связи.
6. Система перевозок, обеспечивающая снабжение ряда пунктов определенного вида товарами.

Операция всегда является управляемым мероприятием, т. е. от нас зависит выбрать тем или другим способом какие-то параметры, характеризующие способ ее организации. «Организация» здесь понимается в широком смысле слова, включая и выбор технических средств, применяемых в операции. Например, организуя отражение воздушного налета средствами ПВО, мы можем, в зависимости от обстановки, выбирать тип и свойства применяемых технических средств (ракет, установок) или же, при заданных технических средствах, решать только задачу рациональной организации самой процедуры отражения нa^eтa (распределение целей между установками, количество ракет, направляемых на каждую цель и т. д.).

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

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

Основная задача исследования операций--предварительное количественное обоснование оптимальных решений.

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

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

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

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

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

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

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

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

Будем в дальнейшем обозначать показатель эффективности буквой W.

Конкретный вид показателя эффективности W, которым следует пользоваться при численной оценке эффективности, зависит от специфики рассматриваемой операции, ее целевой направленности, а также от задачи исследования, которая может быть поставлена в той или другой форме.

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

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

Рассмотрим ряд примеров, в каждом из которых показатель эффективности W выбран в соответствии с целевой направленностью операции.

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

Пример 2 Группа истребителей поднимается в воздух для перехвата одиночного самолета противника Цель операции -- сбить самолет. Показатель эффективности -- вероятность поражения (сбития) самолета

Пример 3. Ремонтная мастерская занимается обслуживанием машин; ее рентабельность определяется количеством машин, обслуженных в течение дня. Показатель эффективности -- среднее число машин, обслуженных за день («среднее» потому, что фактическое число случайно)

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

Пример 5. Предпринимается ряд мер по повышению надежности электронной цифровой вычислительной машины (ЭЦВМ). Цель операции -- уменьшить частоту появления неисправностей («сбоев») ЭЦВМ, или, что равносильно, увеличить средний промежуток времени между сбоями («наработку на отказ»). Показатель эффективности -- среднее время безотказной работы ЭЦВМ (или среднее относительное время исправной работы).

Пример 6. Проводится борьба за экономию средств при производстве определенного вида товаров. Показатель эффективности--количество (или среднее количество) сэкономленных средств.

Во всех рассмотренных примерах показатель эффективности, каков бы он ни был, требовалось обратить в максимум («чем больше, тем лучше»). Вообще, это не обязательно: в исследовании операций часто пользуются показателями, которые требуется обратить не в максимум, а в минимум («чем меньше, тем лучше»). Например, в примере 4 можно было бы в качестве показателя эффективности взять «вероятность тоге, что появившийся самолет не будет обнаружен» -- этот показатель желательно сделать как можно меньше. В примере 5 за показатель эффективности можно было бы принять «среднее число сбоев за сутки», которое желательно минимизировать. Если оценивается какая-то система, обеспечивающая наведение снаряда на цель, то в качестве показателя эффективности можно выбрать среднее значение «промаха» снаряда (расстояния от траектории до центра цели), которое желательно сделать как можно меньше. Наряд средств, выделяемых на выполнение какой-либо задачи, тоже желательно сделать минимальным, равно как и стоимость предпринимаемой системы мероприятий. Таким образом, во многих задачах исследования операций разумное решение должно обеспечивать не максимум, а минимум некоторого показателя.

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

1. Предмет и задачи исследования операций в экономике. Основные понятия теории исследования операций.

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

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

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

Исследование операций - наука, занимающаяся разработкой и практическим применением методов наиболее оптимального управления организационными системами.

Операцией называется всякое мероприятие (система действий), объединенное единым замыслом и направленное к достижению какой-то цели.

Цель исследования операций - предварительное количественное обоснование оптимальных решений.

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

Параметры, совокупность которых образует решение, называются элементами решения.

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

Показатель эффективности - количественная мера, позволяющая сравнивать разные решения по эффективности.

2. Понятие о сетевом планировании и управлении. Сетевая модель процесса и ее элементы.

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

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

Основные понятия сетевой модели:

Событие, работа, путь.

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

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

Продолжительность пути определяется суммой продолжительностей составляющих его работ.

3. Построение и упорядочивание сетевого графика.

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

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

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

Работа - это производственный процесс, требующий затрат времени, труда и материальных ресурсов, который при его выполнении приводит к достижению определенных результатов.

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

В сетевом графике применяются временные, стоимостные и другие характеристики работ.

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

Стоимость работы - это прямые затраты, необходимые для ее выполнения, зависящие от длительности и условий выполнения этой работы.

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

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

Событие - это факт окончания одной или нескольких работ, необходимый и достаточный для начала одной или нескольких последующих работ. Каждому событию присваивается номер, называемый кодом. Каждая работа определяется двумя событиями: кодом начального события, обозначаемого i и кодом конечного события, обозначаемого буквой j.

События, не имеющие предшествующих работ, называются начальными; события, не имеющие последующих - конечными.

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

2 При построении сети решаются вопросы:

Какие работы (работу) необходимо выполнить, чтобы начать данную работу;

Какие работы целесообразно выполнять параллельно с данной работой;

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

4 Форма графика должна быть простой и зрительно легко воспринимаемой.

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

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

4. Критический путь сетевого графика. Резервы времени. Ранние и поздние сроки событий и работ в сетевом графике.

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

Критический путь обозначается на сетевом графике утолщенными или двойными линиями (стрелками).

Особое значение при составлении сетевого графика имеют два понятия:

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

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

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

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

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

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

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

5. Динамическое программирование. Принцип оптимальности и управления Беллмана.

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

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

Главным недостатком метода является, говоря словами Беллмана, «проклятие размерности» - его сложность катастрофически возрастает с увеличением размерности задачи.

6. Задача о распределении средств между предприятиями.

Можно сказать, что процедурапостроения оптимального управления методом динамического программирования распадается на две стадии:предварительную и окончательную. На предварительной стадии для каждого шага определяется УОУ зависящее от состояния системы (достигнутого в результате предыдущих шагов), и условно оптимальный выигрыш на всех оставшихся шагах, начиная с данного, также зависящий от состояния. На окончательной стадии определяется (безусловное) оптимальное управление для каждого шага. Предварительная (условная) оптимизация производится по шагам в обратном порядке: от последнего шага к первому; окончательная (безусловная) оптимизация — также по шагам, но в естественном порядке: от первого шага к последнему. Из двух стадий оптимизации несравненно более важной и трудоемкой является первая. После окончания первой стадии выполнение второй трудности не представляет: остается только "прочесть" рекомендации, уже заготовленные на первой стадии.

7. Постановка задачи линейного программирования.

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

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

Критерием является MAX цена очередного продукта из интересуемой группы f.

Управляемыми переменными величинами являются цены всех продуктов из группы f.

Ограничениями в нашей задаче прогнозирования с использованием обобщенного непараметрического метода, являются:

a) система неравенств (ограничения рациональности поведения потребителя) (см. 4.2. Прогнозирование в рамках обобщенного непараметрического метода);

б) требование неотрицательности управляемых переменных (в нашей задаче прогнозирования мы потребуем, чтобы цены на продукты из группы f не опустились ниже 80% от значений цен в последней временной точке) ;

в) бюджетное ограничение в виде равенства - требование постоянства суммы затрат на покупку продуктов из группы f (с учетом 15% инфляции, например).

8. Графический метод решения задач линейного программирования.

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

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

Найти минимальное значение функции

(2.1) Z = С1х1+С2х2

a11x1 + a22x2 b1

(2.2)a21x1 + a22x2 b2

aM1x1 + aM2x2 bM

(2.3) х1 0, х2 0

Допустим, что система (2.2) при условии (2.3) совместна и ее многоугольник решений ограничен. Каждое из неравенств (2.2) и (2.3), как отмечалось выше, определяет полуплоскость с граничными прямыми: ai1x1 + ai2x2 + ai3x3 = bi,(i = 1, 2, ..., n), х1=0, х2=0. Линейная функция (2.1) при фиксированных значениях Z является уравнением прямой линии: С1х1 + С2х2 = const. Построим многоугольник решений системы ограничений (2.2) и график линейной функции (2.1) при Z = 0 (рис. 2.1). Тогда поставленной задаче линейного прграммирования можно дать следующую интерпретацию. Найти точку многоугольника решений, в которой прямая С1х1 + С2х2 = const опорная и функция Z при этом достигает минимума.

Значения Z = С1х1 + С2х2 возрастают в направлении вектора N =(С1, С2), поэтому прямую Z = 0 передвигаем параллельно самой себе в направлении вектора Х. Из рис. 2.1 следует, что прямая дважды становится опорной по отношению к многоугольнику решений (в точках А и С), причем минимальное значение принимает в точке А. Координаты точки А (х1, х2) находим, решая систему уравнений прямых АВ и АЕ.

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

Случай 1. Прямая С1х1 + С2х2 = const, передвигаясь в направлении вектора N или противоположно ему, постоянно пересекает многоугольник решений и ни в какой точке не является опорной к нему. В этом случае линейная функция не ограничена на многоугольнике решений как сверху, так и снизу (рис. 2.2).

Случай 2. Прямая, пере-двигаясь, все же становится опорной относительно многоу-гольника решений (рис. 2.2, а - 2.2, в). Тогда в зави-симости от вида области ли-нейная функция может быть ограниченной сверху и неограниченной снизу (рис. 2.2, а), ограниченной снизу и неограниченной сверху (рис. 2.2, б), либо ограниченной как снизу, так и сверху (рис. 2.2, в).

9. Симплекс- метод.

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

Этот метод является универсальным, применимым к любой задаче линейного программирования в канонической форме. Система ограничений здесь - система линейных уравнений, в которой количество неизвестных больше количества уравнений. Если ранг системы равен r, то мы можем выбрать r неизвестных, которые выразим через остальные неизвестные. Для определенности предположим, что выбраны первые, идущие подряд, неизвестные X1, X2, ..., Xr. Тогда наша система уравнений может быть записана как

Симплекс-метод основан на теореме, которая называется фундаментальной теоремой симплекс-метода. Среди оптимальных планов задачи линейного программирования в канонической форме обязательно есть опорное решение ее системы ограничений. Если оптимальный план задачи единственен, то он совпадает с некоторым опорным решением. Различных опорных решений системы ограничений конечное число. Поэтому решение задачи в канонической форме можно было бы искать перебором опорных решений и выбором среди них того, для которого значение F самое большое. Но, во-первых, все опорные решения неизвестны и их нужно находить, a, во-вторых, в реальных задачах этих решений очень много и прямой перебор вряд ли возможен. Симплекс-метод представляет собой некоторую процедуру направленного перебора опорных решений. Исходя из некоторого, найденного заранее опорного решения по определенному алгоритму симплекс-метода мы подсчитываем новое опорное решение, на котором значение целевой функции F не меньше, чем на старом. После ряда шагов мы приходим к опорному решению, которое является оптимальным планом.

10. Постановка транспортной задачи. Методы определения опорных планов.

Имеется m пунктов отправления («поставщиков») и n пунктов потребления («потребителей») некоторого одинакового товара. Для каждого пункта определены:

ai - объемы производства i -го поставщика, i = 1, …, m;

вj - спрос j-го потребителя, j= 1,…,n;

сij - стоимость перевозки одной единицы продукции из пункта Ai- i-го поставщика, в пункт Вj - j-го потребителя.

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

Требуется найти план перевозок, при котором бы полностью удовлетворялся спрос всех потребителей, при этом хватало бы запасов поставщиков и суммарные транспортные расходы были бы минимальными.

Под планом перевозок понимают объем перевозок, т.е. количество товара, которое необходимо перевезти от i-го поставщика к j-му потребителю. Для построения математической модели задачи необходимо ввести m·n штук переменных хij, i= 1,…, n, j= 1, …, m, каждая переменная хij обозначает объем перевозок из пункта Ai в пункт Вj. Набор переменных X = {xij} и будет планом, который необходимо найти, исходя из постановки задачи.

Это условие для решения закрытых и открытых транспортных задач (ЗТЗ).

Очевидно, что для разрешимости задачи 1 необходимо, чтобы суммарный спрос не превышал объема производства у поставщиков:

Если это неравенство выполняется строго, то задача называется «открытой» или «несбалансированной», если же , то задача называется «закрытой» транспортной задачей, и будет иметь вид (2):

Условие сбалансированности.

Это условие для решения закрытых транспортных задач (ЗТЗ).

11. Алгоритм решения транспортной задачи.

Применение алгоритма требует соблюдения ряда предпосылок:

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

2. Запас продуктов в каждом пункте производства должен быть известен.

3. Потребности в продуктах в каждом пункте потребления должны быть известны.

4. Общее предложение должно быть равно общему спросу.

Алгоритм решения транспортной задачи состоит из четырех этапов:

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

Этап 2. Проверка полученного распределения ресурсов на оптимальность

Этап 3. Если полученное распределение ресурсов не является оптимальным, то ресурсы перераспределяются, снижая стоимость транспортировки.

Этап 4. Повторная проверка оптимальности полученного распределения ресурсов.

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

12. Модели управления запасами.

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

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

Итак, в зависимости от характера спроса модели управления запасами могут быть

детерминированными;

вероятностными.

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

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

Наиболее простым является случай детерминированного статического спроса на продукцию. Однако такой вид потребления на практике встречается достаточно редко. Наиболее сложные модели - модели нестационарного типа.

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

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

процесс пополнения запаса. Может быть мгновенным либо распределенным во времени;

наличие ограничений по оборотным средствам, складской площади т.п.

13. Системы массового обслуживания (СМО) и показатели их эффективности.

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

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

Системы массового обслуживания могут быть одноканальными или многоканальными.

Каждая СМО предназначена для обслуживания (выполнения) некоторого потока заявок (требований), поступающих на вход системы большей частью не регулярно, а случайные моменты времени. Обслуживание заявок, в этом случае, также длится не постоянное, заранее известное время, а случайное время, которое зависит от многиx случайных, порой неизвестных нам, причин. После обслуживания заявки канал освобождается и готов к приему следующей заявки. Случайный характер потоказаявок и времени их обслуживания приводит к неравномерной загруженности СМО: в иное время на входе СМО могут скапливаться необслуженные заявки, что приводит к перегрузке СМО, а иногда при свободных каналах на входе СМО заявки не будет, что приводит к недогрузке СМО, т.е. к простаиванию ее каналов. Заявки, скапливающиеся на входе СМО, либо «становятся» в очередь, либо по причине невозможности дальнейшего пребывания в очереди покидают СМО необслуженными.

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

14. Уравнения динамики для вероятностных состояний (уравнения Колмогорова). Предельные вероятности состояний.

Формально дифференцируя уравнение Колмогорова—Чепмена по s при s = 0 получаем прямое уравнение Колмогорова:

Формально дифференцируя уравнение Колмогорова — Чепмена по t при t = 0 получаем обратное уравнение Колмогорова

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

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

На рис. показаны граф состояния и переходов, удовлетворяющие поставленному условию: из любого состояния система рано или поздно может перейти в любое другое состояние. Условие не будет выполняться при изменении направления стрелки 4—3 на графе рис, а на противоположное.

Допустим, что поставленное условие выполнено, и, следовательно, предельные вероятности существуют:

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

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

15. Процесс гибели и размножения.

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

Потоками размножения λi(t) будем называть пуассоновские потоки, ведущие к увеличению функции X(t). Соответственно μi(t) - потоки гибели, ведущие к уменьшению функции X(t).

Составим по графу уравнения Колмогорова:

Если поток с конечным числом состояний:

Система уравнений Колмогорова для процесса гибели и размножения с ограниченным числом состояний имеет вид:

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

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

16. Системы массового обслуживания с отказами .

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

Следует отметить, что в данном случае количество каналов равно 1 (). Этот канал принимает пуассоновский поток заявок, интенсивность которого равняется . Время оказывает влияние на интенсивность:

Если заявка прибыла в канал, который в данный момент не является свободным, она получает отказ и больше не числится в системе. Обслуживание заявок осуществляется в течение случайного времени , распределение которого реализуется в соответствии с показательным законом с параметром :

17. Системы массового обслуживания с ожиданием .

Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания.

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

Будем нумеровать состояния СМО по числу заявок, находящихся в системе (как обслуживаемых, так и ожидающих обслуживания):

—канал свободен;

—канал занят, очереди нет;

— канал занят, одна заявка стоит в очереди;

—канал занят, k - 1 заявок стоят в очереди;

— канал занят, т заявок стоят в очереди.

18. Методы принятия решений в условиях конфликта. Матричные игры. Чистые и смешанные стратегии игр.

Матричная игра - это конечная игра двух игроков с нулевой суммой, в которой задаётся выигрыш игрока 1 в виде матрицы (строка матрицы соответствует номеру применяемой стратегии игрока 2, столбец - номеру применяемой стратегии игрока 2; на пересечении строки и столбца матрицы находится выигрыш игрока 1, соответствующий применяемым стратегиям).

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

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

Первый игрок имеет m стратегий i = 1,2,...,m, второй имеет n стратегий j = 1,2,...,n. Каждой паре стратегий (i,j) поставлено в соответствие число аij, выражающее выигрыш игрока 1 за счёт игрока 2, если первый игрок примет свою i-ю стратегию, а 2 - свою j-ю стратегию.

Каждый из игроков делает один ход: игрок 1 выбирает свою i-ю стратегию (i=), 2 - свою j-ю стратегию (j=), после чего игрок 1 получает выигрыш аij за счёт игрока 2 (если аij

Каждая стратегия игрока i=; j = часто называется чистой стратегией.

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

Таким образом, если игрок 1 имеет m чистых стратегий 1,2,...,m, то его смешанная стратегия x- это набор чисел x = (x1,..., xm) удовлетворяющих соотношениям

xi³ 0 (i= 1,m), =1.

Аналогично для игрока 2, который имеет n чистых стратегий, смешанная стратегия y- это набор чисел

y = (y1, ..., yn), yj ³ 0, (j = 1,n), = 1.

Так как каждый раз применение игроком одной чистой стратегии исключает применение другой, то чистые стратегии являются несовместными событиями. Кроме того, они являются единственными возможными событиями.

Чистая стратегия есть частный случай смешанной стратегии. Действительно, если в смешанной стратегии какая-либо i-я чистая стратегия применяется с вероятностью 1, то все остальные чистые стратегии не применяются. И эта i-я чистая стратегия является частным случаем смешанной стратегии. Для соблюдения секретности каждый игрок применяет свои стратегии независимо от выбора другого игрока.

19. Геометрический метод решения матричной игры.

Решение игр размера 2xn или nx2 допускает наглядную геометрическую интерпретацию. Такие игры можно решать графически.

На плоскости XY по оси абсцисс отложим единичный отрезок A1A2 (рисунок 5.1). Каждой точке отрезка поставим в соответствие некоторую смешанную стратегию U = (u1, u2). Причем расстояние от некоторой промежуточной точки U до правого конца этого отрезка - это вероятность u1 выбора стратегии A1, расстояние до левого конца - вероятность u2 выбора стратегии A2. Точка А1 соответствует чистой стратегии А1, точка А2 - чистой стратегии А2.

В точках А1 и А2 восстановим перпендикуляры и будем откладывать на них выигрыши игроков. На первом перпендикуляре (совпадающем с осью OY) покажем выигрыш игрока А при использовании стратегии А1, на втором - при использовании стратегии A2. Если игрок А применяет стратегию A1, то его выигрыш при стратегии B1 игрока B равен 2, а при стратегии B2 он равен 5. Числам 2 и 5 на оси OY соответствуют точки B1 и B2. Аналогично на втором перпендикуляре найдем точки B"1 и B"2 (выигрыши 6 и 4).

Соединяя между собой точки B1 и B"1, B2 и B"2, получим две прямые, расстояние от которых до оси OX определяет средний выигрыш при любом сочетании соответствующих стратегий.

Например, расстояние от любой точки отрезка B1B"1 до оси OX определяет средний выигрыш игрока A при любом сочетании стратегий A1 и A2 (с вероятностями u1 и u2) и стратегии B1 игрока B.

Ординаты точек, принадлежащих ломаной B1MB"2 определяют минимальный выигрыш игрока A при использовании им любых смешанных стратегий. Эта минимальная величина является наибольшей в точке М, следовательно, этой точке соответствует оптимальная стратегия U* = (,), а ее ордината равна цене игры v.

Координаты точки M найдем, как координаты точки пересечения прямых B1B"1 и B2B"2.

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

Составим уравнения прямых для нашей задачи.

Прямая B1B"1: = или y = 4x + 2.

Прямая B2B"2: = или y = -x + 5.

Получим систему: y = 4x + 2,

Решим ее: 4x + 2 = -x + 5,

x = 3/5, y = -3/5 + 5 = 22/5.

Таким образом, U = (2/5, 3/5), v = 22/5.

20. Биматричные игры.

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

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

21. Статистические игры. Принципы и критерии принятия решений в условиях полной и частичной неопределенности.

В исследовании операций принято различать три типа неопределенностей:

неопределенность целей;

неопределенность наших знаний об окружающей обстановке и действующих в данном явлении факторах (неопределенность природы);

неопределенность действий активного или пассивного партнера или противника.

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

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

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

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

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

Другим крайним случаем может быть неопределенность нестохастического вида (по выражению Е.С.Вентцель - "дурная неопределенность"), при которой никаких предположений о стохастической устойчивости не существует. Наконец, можно говорить о промежуточном типе неопределенности, когда решение принимается на основании каких-либо гипотез о законах распределения случайных величин. При этом ЛПР должен иметь в виду опасность несовпадения его результатов с реальными условиями. Эта опасность несовпадения формализуется с помощью коэффициентов риска.

Принятие решений в условиях риска может быть основано на одном из следующих критериев:

критерий ожидаемого значения;

комбинации ожидаемого значения и дисперсии;

известного предельного уровня;

наиболее вероятного события в будущем.

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

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

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

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

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

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

Иногда операция, сопровождаемая случайными факторами, преследует такую цель А , которая может быть либо достигнута полностью, либо не достигнута совсем (типа «да – нет»). Тогда в качестве показателя эффективности выбирают вероятность достижения этой цели p (A ). (Если p (A ) = 0 или 1, то приходим к известной в кибернетике задаче «черного ящика».)

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

1.3. Общая постановка задачи исследования операций

Задачи исследования операций делятся на две категории: а) прямые и б) обратные.

Прямые задачи отвечают на вопрос: чему будет равен показатель эффективности Z , если в заданных условиях y  Y будет принято некоторое решение x  X . Для решения такой задачи строится математическая модель, позволяющая выразить показатель эффективности через заданные условия и решение, а именно:

где
заданные факторы (исходные данные),

управляющие переменные (решение),

Z – показатель эффективности (целевая функция),

F – функциональная зависимость между переменными.

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

Если вид зависимости F известен, то показатель Z находится прямой подстановкой ив данный функционал.

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

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

Требуется найти такое решение
при котором показатель эффективностиZ = opt :

Эта формула читается так: Z есть оптимальное значение
взятое по всем решениям, входящим в множество возможных решенийX .

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

И.Н. Слинкина

Учебное пособие для студентов педагогических вузов

по специальности «Информатика»

Шадринск, 2003

Слинкина И.Н.

Исследование операций. Учебно-методическое пособие. – Шадринск: изд-во Шадринского государственного педагогического института, 2002. - 106 с.

Слинкина И.Н. – кандидат педагогических наук

В учебном пособии представлена теоретическая часть курса «Исследование операций». Оно предназначено для студентов очного и заочного отделений факультетов, реализующих специальность «Информатика».

Вопросы к блокам по курсу «Исследование операций» 5

1.1. Предмет и задачи исследования операций 7

1.2. Основные понятия и принципы исследования операций 8

1.3. Математические модели операций 10

1.4. Понятие линейного программирования 12

1.5. Примеры экономических задач линейного программирования. Задача о наилучшем использовании ресурсов 13

1.6. Примеры экономических задач линейного программирования. Задача о выборе оптимальных технологий 15

1.7. Примеры экономических задач линейного программирования. Задача о смесях 16

1.8. Примеры экономических задач линейного программирования. Транспортная задача 17

1.9. Основные виды записи задач линейного программирования 19

1.10. Способы преобразования 21

1.11. Переход к канонической форме 22

1.12. Переход к симметричной форме записи 25

2.1. Геометрическая интерпретация задачи линейного программирования 28

2.2. Решение задач линейного программирования графическим методом 29

2.3. Свойства решений задачи линейного программирования 34

2.4. Общая идея симплексного метода 35

2.5. Построение начального опорного плана при решении задач линейного программирования симплексным методом 36

2.6. Признак оптимальности опорного плана. Симплексные таблицы 40

2.7. Переход к нехудшему опорному плану. 44

2.8. Симплексные преобразования 46

2.9. Альтернативный оптимум (признак бесконечности множества опорных планов) 51

2.10. Признак неограниченности целевой функции 52

2.11. Понятие о вырождении. Монотонность и конечность симплексного метода. Зацикливание 53

2.12. Понятие двойственности для симметричных задач линейного программирования 54

3.1. Несимметричные двойственные задачи 57

3.2. Открытая и закрытая модели транспортной задачи 61

3.3. Построение начального опорного плана. Правило "Северо-западного угла" 63

3.4. Построение начального опорного плана. Правило минимального элемент 64

3.5. Построение начального опорного плана. Метод Фогеля 64

3.6. Метод потенциалов 65

3.7. Решение транспортных задач с ограничениями по пропускной способности 69

3.8. Примеры задач дискретного программирования. Задача о контейнерных перевозках. Задача о назначении 71

3.9. Сущность методов дискретной оптимизации 72

3.10. Задача выпуклого программирования 74

3.11. Метод множителей Лагранжа 75

3.12. Градиентные методы 77

4.1. Методы штрафных и барьерных функций 78

4.2. Динамическое программирование. Основные понятия. Сущность методов решения 79

4.3. Стохастическое программирование. Основные понятия 81

4.4. Матричные игры с нулевой суммой 83

4.5. Чистые и смешанные стратегии и их свойства 85

4.6. Свойства чистых и смешанных стратегий 88

4.7. Приведение матричной игры к ЗЛП 92

4.8. Задачи теории массового обслуживания. Классификация систем массового обслуживания 94

4.9. Потоки событий 96

4.10. Схема гибели и размножения 97

4.11. Формула Литтла 99

4.12. Простейшие системы массового обслуживания 101

Вопросы к блокам по курсу «Исследование операций»

Блок 1

1. Предмет и задачи исследования операций.

2. Основные понятия и принципы исследования операций.

3. Математические модели операций.

4. Понятие линейного программирования.

5. Примеры экономических задач линейного программирования. Задача

6. Примеры экономических задач линейного программирования. Задача о выборе оптимальных технологий.

7. Примеры экономических задач линейного программирования. Задача о смесях.

8. Примеры экономических задач линейного программирования. Транспортная задача.

9. Основные виды записи задач линейного программирования.

10. Способы преобразования.

11. Переход к канонической форме.

12. Переход к симметричной форме записи.

Блок 2

1. Геометрическая интерпретация задачи линейного программирования.

2. Решение задач линейного программирования графическим методом.

3. Свойства решений задачи линейного программирования.

4. Общая идея симплексного метода.

5. Построение начального опорного плана при решении задач линейного программирования симплексным методом.

6. Признак оптимальности опорного плана. Симплексные таблицы.

7. Переход к нехудшему опорному плану.

8. Симплексные преобразования.

9. Альтернативный оптимум (признак бесконечности множества опорных планов).

10. Признак неограниченности целевой функции.

11. Понятие о вырождении. Монотонность и конечность симплексного метода. Зацикливание.

12. Понятие двойственности для симметричных задач линейного программирования.

Блок 3

1. Несимметричные двойственные задачи.

2. Открытая и закрытая модели транспортной задачи.

3. Построение начального опорного плана. Правило "Северо-западного угла".

4. Построение начального опорного плана. Правило минимального элемент.

5. Построение начального опорного плана. Метод Фогеля.

6. Метод потенциалов.

7. Решение транспортных задач с ограничениями по пропускной способности.

8. Примеры задач дискретного программирования. Задача о контейнерных перевозках. Задача о назначении.

9. Сущность методов дискретной оптимизации.

10. Задача выпуклого программирования.

11. Метод множителей Лагранжа.

12. Градиентные методы.

Блок 4

1. Метод штрафных и барьерных функций.

2. Динамическое программирование. Основные понятия. Сущность методов решения.

3. Стохастическое программирование. Основные понятия.

4. Матричные игры с нулевой суммой.

5. Чистые и смешанные стратегии.

6. Свойства чистых и смешанных стратегий.

7. Приведение матричной игры к ЗЛП

8. Задачи теории массового обслуживания. Классификация систем массового обслуживания.

9. Потоки событий.

10. Схема гибели и размножения.

11. Формула Литтла.

12. Простейшие системы массового обслуживания.

Блок 1.

Предмет и задачи исследования операций

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

Потребности практики вызвали к жизни специальные научные методы, которые удобно объединять под названием «исследование операций».

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

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

Необходимость принятия решений и проверки выдвинутой гипотезы решения математически подтверждают следующие примеры:

Задача 1. О наилучшем использовании ресурсов.

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

Задача 2. О смесях.

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

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

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

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

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

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

Основные понятия и принципы исследования операций

Определение: Операцией называется всякое мероприятие (система действий), объединенное единым замыслом и направленное к достижению какой-то цели.

Операция есть всегда управляемое мероприятие, т.е. от расчетов зависит, каким способом выбрать параметры, характеризующие ее организацию. «Организация» здесь понимается в широком смысле слова, включая набор технических средств, применяемых в операции.

Определение: Всякий определенный выбор зависящий от решающих параметров называется решением.

Определение: Оптимальными называются решения, по тем или иным причинам предпочтительные перед другими.

Цель исследования операций – предварительное количественное обоснование оптимальных решений.

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

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

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

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

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

Чтобы сравнивать между собой по эффективности разные решения, нужно иметь какой-то количественный критерий, так называемый показатель эффективности (целевая функция). Этот показатель выбирается так, чтобы он отражал целевую направленность операции. Лучшим будет считаться то решение, которое в максимальной степени способствует достижению поставленной цели. Чтобы выбрать показатель эффективности Z, нужно прежде всего определить, к чему должно привести решение задачи. Выбирая решение, предпочтение отдается такому, которое обращает показатель эффективности Z в максимум или в минимум. Например, доход от операции хотелось бы обратить в максимум; если же показателем эффективности являются затраты, их желательно обратить в минимум.

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

Задача выбора показателя эффективности решается для каждой проблемы индивидуально.

Задача 1. О наилучшем использовании ресурсов.

Задача операции – произвести максимальное количество товаров. Показатель эффективности Z – прибыль от продажи товаров при минимальных затратах на ресурсы (max Z).

Задача 2. О смесях.

Естественный показатель эффективности, подсказанный формулировкой задачи, - это цена необходимых для смеси продуктов при условии необходимости сохранения заданных свойств смеси(min Z).

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

Задача операции – обеспечить снабжение товарами потребителей при минимальных расходах на перевозки. Показатель эффективности Z – суммарные расходы на перевозки товаров за единицу времени (min Z).

Статьи по теме