Современные формы исследования операций. Основные понятия исследования операций
Исследование операций
Исследование операций (ИО) (англ. 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. Предмет и задачи исследования операций.
§ 1. Что такое исследование операций и чем оно занимается.
§ 2. Основные понятия и принципы исследования операции.
§ 3. Математические модели операций.
Глава 2. Разновидности задач исследования операций и подходов к их решению.
§ 4. Прямые и обратные задачи исследования операций. Детерминированные задачи.
§ 5. Проблема выбора решения в условиях неопределенности.
§ 6. Многокритериальные задачи исследования операций. «Системный подход».
Глава 3. Линейное программирование.
§ 7. Задачи линейного программирования.
§ 8. Основная задача линейного программирования.
§ 9. Существование решения 03ЛП и способы его нахождения.
§ 10. Транспортная задача линейного программирования.
§ 11. Задачи целочисленного программирования. Понятие о нелинейном программировании.
Глава 4. Динамическое программирование.
§ 12. Метод динамического программирования.
§ 13. Примеры решения задач динамического программирования.
§ 14. Задача динамического программирования в общем виде. Принцип оптимальности.
Глава 5.Марковские случайные процессы.
§ 15. Понятие о марковском процессе.
§ 16. Потоки событий.
§ 17. Уравнения Колмогорова для вероятностей состояний. Финальные вероятности состояний.
Глава 6. Теория массового обслуживания.
§ 18. Задачи теории массового обслуживания. Классификация систем массового обслуживания.
§ 19. Схема гибели и размножения. Формула Литтла.
§ 20. Простейшие системы массового обслуживания и их характеристики.
§ 21. Более сложные задачи теории массового обслуживания.
Глава 7. Статистическое моделирование случайных процессов (метод Монте-Карло).
§ 22. Идея, назначение и область применимости метода.
§ 23. Единичный жребий и формы его организации.
§ 24. Определение характеристик стационарного случайного процесса по одной реализации.
Глава 8. Игровые методы обоснования решении.
§ 25. Предмет и задачи теории игр.
§ 26. Антагонистические матричные игры.
§ 27. Методы решения конечных игр.
§ 28. Задачи теории статистических решении.
ПРЕДМЕТ И ЗАДАЧИ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ
Основные понятия и принципы исследования операций
В этом параграфе мы познакомимся с терминологией, основными понятиями и принципами науки «исследование операций».
Операцией называется всякое мероприятие (система действий), объединенное единым замыслом и направленное к достижению какой-то цели (все мероприятия, рассмотренные в пунктах 1 - 8 предыдущего параграфа, являются «операциями»).
Операция есть всегда управляемое мероприятие, т. е. от нас зависит, каким способом выбрать некоторые параметры, характеризующие её организацию. «Организация» здесь понимается в широком смысле слова, включая набор технических средств, применяемых в операции.
Всякий определенный выбор зависящих от нас параметров называется решением. Решения могут быть удачными и неудачными, разумными и неразумными. Оптимальными называются решения, по тем или другим признакам предпочтительные перед другими. Цель исследования операций - предварительное количественное обоснование оптимальных решений.
Иногда (относительно редко) в результате исследования удается указать одно-единственное строго оптимальное решение, гораздо чаще - выделить область практически равноценных оптимальных (разумных) решений, в пределах которой может быть сделан окончательный выбор.
Заметим, что само принятие решения выходит за рамки исследования операции и относится к компетенции ответственного лица, чаще - группы лиц, которым предоставлено право окончательного выбора и на которых возложена ответственность за этот выбор. Делая выбор, они могут учитывать, наряду с рекомендациями, вытекающими из математического расчета, еще ряд соображений (количественного и качественного характера), которые этим расчетом не были учтены.
Непременное присутствие человека (как окончательной инстанции, принимающей решение) не отменяется даже при наличии полностью автоматизированной системы управления, которая, казалось бы, принимает решение без участия человека. Нельзя забывать о том, что само создание управляющего алгоритма, выбор одного из возможных его вариантов, есть тоже решение, и весьма ответственное. По мере развития управляющих автоматов функции человека не отменяются, а просто перемещаются с одного, элементарного, уровня на другой, высший. Кроме того, ряд автоматизированных систем управления предусматривает в ходе управляемого процесса активное вмешательство человека.
Те параметры, совокупность которых образует решение, называются элементами решения. В качестве элементов решения могут фигурировать различные числа, векторы, функции, физические признаки и т. д. Например, если составляется план перевозок однородных грузов из пунктов отправления А 1 ,А 2 ,…, А m в пункты назначения В 1 ,В 2 , ..., В n , то элементами решения будут числа x ij , показывающие, какое количество груза будет отправлено из 1-го пункта отправления А i в j -й пункт назначения В j . Совокупность чисел x 11 , x 12, …, x 1 n , …, x m 1 , x m 2 , …, x mn образует решение.
В простейших задачах исследования операций количество элементов решения может быть сравнительно невелико. Но в большинстве задач, имеющих практическое значение, число элементов решения очень велико, в чем читатель может убедиться, попытавшись самостоятельно выделить и «назвать по имени» элементы решения в примерах 1 - 8 предыдущего параграфа. Для упрощения мы будем всю совокупность элементов решения обозначать одной буквой x и говорить «решение х».
Кроме элементов решения, которыми мы, в каких-то пределах, можем распоряжаться, в любой задаче исследования операций имеются еще и заданные, «дисциплинирующие» условия, которые фиксированы с самого начала и нарушены быть не могут (например, грузоподъемность машины; размер планового задания;
весовые характеристики оборудования и т. п.). В частности, к таким условиям относятся средства (материальные, технические, людские), которыми мы вправо распоряжаться, и иные ограничения, налагаемые на решение. В своей совокупности они формируют так называемое «множество возможных решений».
Обозначим это множество опять-таки одной буквой X, а тот факт, что решение х принадлежит этому множеству, будем записывать в виде формулы: х X (читается: элемент х входит в множество X).
Речь идет о том, чтобы в множестве возможных решений Х выделить те решения х (иногда - одно, а чаще - целую область решений), которые с той или другой точки зрения эффективнее (удачнее, предпочтительнее) других. Чтобы сравнивать между собой по эффективности разные решения, нужно иметь какой-то количественный критерий, так называемый показатель эффективности (его часто называют «целевой функцией»). Этот показатель выбирается так, чтобы он отражал целевую направленность операции. «Лучшим» будет считаться то решение, которое в максимальной степени способствует достижению поставленной цели. Чтобы выбрать, «назвать по имени» показатель эффективности W, нужно, прежде всего, спросить себя: чего мы хотим, к чему стремимся, предпринимая операцию? Выбирая решение, мы, естественно, предпочтем такое, которое обращает показатель эффективности W в максимум (или же в минимум). Например, доход от операции хотелось бы обратить в максимум; если же показателем эффективности являются затраты, их желательно обратить в минимум. Если показатель эффективности желательно максимизировать, мы это будем записывать в виде W => mах, а если минимизировать - W => min.
Очень часто выполнение операции сопровождается действием случайных факторов («капризы» погоды, колебания спроса и предложения, отказы технических устройств и т. д.). В таких случаях обычно в качестве показателя эффективности берется не сама величина, которую хотелось бы максимизировать (минимизировать), а ее среднее значение (математическое ожидание).
В некоторых случаях бывает, что операция, сопровождаемая случайными факторами, преследует какую-то вполне определенную цель А, которая может быть только достигнута полностью или совсем не достигнута (схема «да-нет»), и никакие промежуточные результаты нас не интересуют. Тогда в качестве показателя эффективности выбирается вероятность достижения этой цели Р (А ). Например, если ведется стрельба по какому-то объекту с непременным условием уничтожить его, то показателем эффективности будет вероятность уничтожения объекта.
Неправильный выбор показателя эффективности очень опасен. Операции, организованные под углом зрения неудачно выбранного критерия, могут привести к неоправданным затратам и потерям (вспомним хотя бы пресловутый «вал» в качестве основного критерия оценки хозяйственной деятельности предприятий).
Для иллюстрации принципов выбора показателя эффективности вернемся опять к примерам 1 - 8 § 1, выберем для каждого из них естественный показатель эффективности и укажем, требуется его максимизировать или минимизировать. Разбирая примеры, нужно иметь в виду, что не во всех из них выбор показателя эффективности однозначно диктуется словесным описанием задачи, так что по этому вопросу возможны расхождения между читателем и автором.
1. План снабжения предприятий. Задача операции - обеспечить снабжение сырьем при минимальных расходах на перевозки. Показатель эффективности R - суммарные расходы на перевозки сырья за единицу времени, например, месяц (R => min).
2. Постройка участка магистрали. Требуется так спланировать строительство, чтобы закончить его как можно скорее. Естественным показателем эффективности было бы время завершения стройки, если бы оно не было связано со случайными факторами (отказы техники, задержки в выполнении отдельных работ). Поэтому в качестве показателя эффективности можно выбрать среднее ожидаемое время Т окончания стройки (Т => min).
3. Продажа сезонных товаров. В качестве показателя эффективности можно взять среднюю ожидаемую прибыль П от реализации товаров за сезон (П => mах).
4. Снегозащита дорог. Речь идет о наиболее выгодном экономически плане снегозащиты, поэтому в качестве показателя эффективности можно выбрать средние за единицу времени (например, за год) расходы R на содержание и эксплуатацию дорог, включая расходы, связанные как с сооружением защитных устройств, так и с расчисткой дорог и задержками транспорта (R => min).
5. Противолодочный рейд. Так как рейд имеет вполне определенную цель А - уничтожение лодки, то в качестве показателя эффективности следует выбрать вероятность Р (A ) того, что лодка будет уничтожена.
6. Выборочный контроль продукции. Естественный показатель эффективности, подсказанный формулировкой задачи, это средние ожидаемые расходы R на контроль за единицу времени, при условии, что система контроля обеспечивает заданный уровень качества, например, средний процент брака не выше заданного (R => min).
7. Медицинское обследование. В качестве показателя эффективности можно выбрать средний процент (долю) Q больных и носителей инфекции, которых удалось выявить (Q => шах).
8. Библиотечное обслуживание. В формулировке задачи сознательно допущена некоторая нечеткость:
неясно, что значит «наилучшее обслуживание абонентов» или «удовлетворение их запросов в максимальной мере». Если о качестве обслуживания судить по времени, которое запросивший книгу абонент ждет ее получения, то в качестве показателя эффективности можно взять среднее время Т ожидания книги читателем, подавшим на нее заявку (Т => min). Можно подойти к вопросу и с несколько иных позиций, выбрав в качестве показателя эффективности среднее число М книг, выданных за единицу времени (М => mах).
Рассмотренные примеры специально подобраны настолько простыми, чтобы выбор показателя эффективности был сравнительно нетруден и прямо диктовался словесной формулировкой задачи, ее (почти всегда) однозначной целевой направленностью. Однако на практике это далеко не всегда бывает так. В этом читатель может убедиться, попытавшись, например, выбрать показатель эффективности работы городского транспорта. Что взять в качестве такого показателя? Среднюю скорость передвижения пассажиров по городу? Или среднее число перевезенных пассажиров? Или среднее количество километров, которое придется пройти пешком человеку, которого транспорт не может доставить к нужному месту? Тут есть над чем поразмыслить!
К сожалению, в большинстве задач, имеющих практическое значение, выбор показателя эффективности не прост и решается неоднозначно. Для сколько-нибудь сложной задачи типично положение, когда эффективность операции не может быть исчерпывающим образом охарактеризована одним единственным числом - на помощь ему приходится привлекать другие. С такими «многокритериальными» задачами мы познакомимся в § 6.
Примеры решения задач динамического программирования
В этом параграфе мы рассмотрим (и даже решим до конца) несколько простых (до крайности упрощенных) примеров задач динамического программирования
1. Прокладка наивыгоднейшего пути между двумя пунктами. Вспомним задачу 4 предыдущего параграфа и решим ее до конца в крайне (и намеренно) упрощенных условиях. Нам нужно соорудить путь, соединяющий
два пункта А и В, из которых второй лежит к северо-востоку от первого. Для простоты допустим,. что прокладка пути состоит из ряда шагов, и на каждом шаге мы можем двигаться либо строго на восток, либо строго на север; любой путь из А в В представляет собой ступенчатую ломаную линию, отрезки которой параллельны одной из координатных осей (рис. 13.1). Затраты на сооружение каждого из таких отрезков известны. Требуется проложить такой путь из А в В, при котором суммарные затраты минимальны.
Как это сделать? Можно поступить одним из двух способов: либо перебрать все возможные варианты пути, и выбрать тот, на котором затраты минимальны (а при большом числе отрезков это очень и очень трудно!); либо разделить процесс перехода из А в В на отдельные шаги (один шаг - один отрезок) и оптимизировать управление по шагам. Оказывается, второй способ несравненно удобнее! Тут, как и везде в исследовании операций, сказываются преимущества целенаправленного, организованного поиска решения перед наивным «слепым» перебором.
Продемонстрируем, как это делается, на конкретном примере. Разделим расстояние от А до В в восточном направлении, скажем, на 7 частей, а в северном - на 5 частей (в принципе дробление может быть сколь угодно мелким). Тогда любой путь из А в В состоит из т = 7 + 5 == 12 отрезков, направленных на восток или на север (рис. 13.2). Проставим на каждом из отрезков число, выражающее (в каких-то условных единицах) стоимость прокладки пути по этому отрезку. Требуется выбрать такой путь из А в В, для которого сумма чисел, стоящих на отрезках, минимальна.
Будем рассматривать сооружаемый путь как управляемую систему S, перемещающуюся под влиянием управления из начального состояния А в конечное В. Состояние этой системы перед началом каждого шага будет характеризоваться двумя координатами: восточной (х) и северной (у), обе - целочисленные (0 х 5 7, 0 у 5). Для каждого из состояний системы (узловой точки прямоугольной сетки на рис. 13.2) мы должны найти условное оптимальное управление: идти нам из этой точки на север (управление «с») или на восток (управление «в»). Выбирается это управление так, чтобы стоимость всех оставшихся до конца шагов (включая данный) была минимальна. Эту стоимость мы по-прежнему будем называть «условным оптимальным выигрышем» (хотя в данном случае это не «выигрыш», а «проигрыш») для данного состояния системы S перед началом очередного шага.
Процедуру условной оптимизации будем разворачивать в обратном направлении - от конца к началу. Прежде всего произведем условную оптимизацию последнего, 12-го шага. Рассмотрим отдельно правый верхний угол нашей прямоугольной сетки (рис. 13.3). Где мы можем находиться после 11-го шага? Только
 |
там, откуда за один (последний) шаг можно попасть в В, т. е. в одной из точек В 1 или В 2 . Если мы находимся в точке В 1 , у нас нет выбора (управление вынужденное): надо идти на восток, и это обойдется нам в 10 единиц. Запишем это число 10 в кружке у точки В 1 , а оптимальное управление покажем короткой стрелкой, исходящей из В 1 и направленной на восток. Для точки В 2 управление тоже вынужденное (север), расход до конца равен 14, мы его запишем в кружке у точки В 2 . Таким образом, условная оптимизация последнего шага сделана, и условный оптимальный выигрыш для каждой из точек В 1 , В 2 найден и записан в соответствующем кружке.
Теперь давайте оптимизировать предпоследний (11-й) шаг. После предпредпоследнего (10-го) шага мы могли оказаться в одной из точек С 1 , С 2 , С 3 (рис. 13.4). Найдем для каждой из них условное оптимальное управление и условный оптимальный выигрыш. Для точки С 1 управление вынужденное: идти на восток;
обойдется это нам до конца в 21 единицу (11 на данном шаге, плюс 10, записанных в кружке при В 1). Число 21 записываем в кружке при точке С 1 . Для точки С 2 управление уже не вынужденное: мы можем идти как на восток, так и на север. В первом случае мы затратим на данном шаге 14 единиц и от В 2 до конца - еще 14, всего 28 единиц. Если пойдем на север, затратим 13 + 10, всего 23 единицы. Значит, условное оптимальное управление в точке С 2 - идти на север (отмечаем это стрелкой, а число 23 записываем в кружке у С 2), Для точки С 3 управление снова вынужденное («с»), обойдется это до конца в 22 единицы (ставим стрелку на север, число 22 записываем в кружке при С 3 ).
Аналогично, «пятясь» от предпоследнего шага назад, найдем для каждой точки с целочисленными координатами условное оптимальное управление («с» или «в»), которое обозначим стрелкой, и условный оптимальный выигрыш (расход до конца пути), который запишем в кружке. Вычисляется он так: расход на данном шаге складывается с уже оптимизированным расходом, записанным в кружке, куда ведет стрелка. Таким образом, на каждом шаге мы оптимизируем только этот шаг, а следующие за ним - уже оптимизированы. Конечный результат процедуры оптимизации показан на рис. 13.5.
Таким образом, условная оптимизация уже выполнена: в какой бы из узловых точек мы ни находились, мы уже знаем, куда идти (стрелка) и во что нам обойдется путь до конца (число в кружке). В кружке при точке А записан оптимальный выигрыш на все сооружение пути из А в В:
W* = 118.
Теперь остается построить безусловное оптимальное управление - траекторию, ведущую из А и В самым дешевым способом. Для этого нужно только «слушаться стрелок», т. е. прочитать, что они предписывают делать на каждом шаге. Такая оптимальная траектория отмечена на рис. 13.5 дважды обведенными кружками. Соответствующее безусловное оптимальное управление будет:
х* = (с, с, с, с, в, в, с, в, в, в, в, в),
т. е. первые четыре шага мы должны делать на север, следующие два - на восток, затем опять один на север и остальные пять - на восток. Задача решена.
Заметим, что в ходе условной оптимизации мы можем столкнуться со случаем, когда оба управления для какой-то точки на плоскости являются оптимальными, т. е. приводят к одинаковому расходу средств от этой точки до конца, Например, в точке с координатами (5; 1) оба управления «с» и «в» являются оптимальными и дают расход до конца равным 62. Из них мы произвольно выбираем любое (в нашем случае мы выбрали «с»; с тем же успехом мы могли бы выбрать «в»). Такие случаи неоднозначного выбора оптимального управления постоянно встречаются в динамическом программировании; в дальнейшем мы специально отмечать их не будем, а попросту выберем произвольно любой из равноценных вариантов. От этого произвола, разумеется, может зависеть оптимальное управление всем процессом, но не оптимальный выигрыш. Вообще, в задачах динамического программирования (как и в задачах линейного) решение далеко не всегда единственное.
А теперь вернемся к началу и попробуем решить задачу «наивным» способом, выбирая на каждом шаге, начиная с первого, самое выгодное (для этого шага) направление (если таких два, выбираем любое). Таким способом мы получим управление
х = (с, с, в, в, в, в, с, в, в, в, с, с).
Подсчитаем расходы для этой траектории. Они будут равны W =10 +12 +8+10 +11 +13 +15+8 + +10+9+8+14=128, что безусловно больше, чем W* = 118. В данном случае разница не очень велика, но в других она может быть существенной.
В решенной выше задаче условия были намеренно до крайности упрощены. Разумеется, никто не будет вести железнодорожный путь «по ступенькам», перемещаясь только строго на север или строго на восток. Такое упрощение мы сделали для того, чтобы в каждой точке выбирать только из двух управлений: «с» или «в». Можно было бы вместо двух возможных направлений ввести их несколько и, кроме того, взять шаги помельче; принципиального значения это не имеет, но, разумеется, усложняет и удлиняет расчеты.
Заметим, что задачи, сходные с рассмотренной выше, очень часто встречаются на практике: например, при выборе наискорейшего пути между двумя точками или наиболее экономного (в смысле расхода горючего) набора скорости и высоты летательным аппаратом.
Сделаем одно попутное замечание. Внимательный читатель, вероятно, заметил, что в нашей задаче точки А и В (начало и конец) в принципе ничем друг от друга не отличаются: можно было бы строить условные оптимальные управления не с конца к началу, а с начала к концу, а безусловные - в обратном направлении. Действительно, это так: в любой задаче динамического программирования «начало» и «конец» можно поменять местами. Это совершенно равносильно описанной ранее методике в расчетном отношении, но несколько менее удобно при словесном объяснении идеи метода: легче аргументировать, ссылаясь на «уже сложившиеся» условия к началу данного шага, чем на те, которые еще «предстоят» после этого шага. По существу же оба подхода совершенно равносильны.
2. Задача о распределении ресурсов. Метод динамического программирования позволяет с успехом решать многие экономические задачи (см., например, ). Рассмотрим одну из простейших таких задач. В нашем распоряжении имеется какой-то запас средств (ресурсов) К, который должен быть распределен между т предприятиями П 1 , П 2 , ..., П m . Каждое из предприятий П i при вложении в него каких-то средств х приносит доход, зависящий от x , т. е. представляющий собой какую-то функцию (x ). Все функции (x ) (i = 1, 2, ..., т) заданы (разумеется, эти функции - неубывающие). Спрашивается, как нужно распределить средства К. между предприятиями, чтобы в сумме они дали максимальный доход?
Эта задача легко решается методом динамического программирования.. Хотя в своей постановке она не содержит упоминания о времени, можно все же операцию распределения средств мысленно развернуть в какой-то последовательности, считая за первый шаг вложение средств в предприятие П 1 , за второй - в П 2 и т. д.
Управляемая система S в данном случае - средства или ресурсы, которые распределяются. Состояние системы S перед каждым шагом характеризуется одним числом S - наличным запасом еще не вложенных средств. В этой задаче «шаговыми управлениями» являются средства х 1 , х 2 , ..., х 3 , выделяемые предприятиям. Требуется найти оптимальное управление, т. е. такую совокупность чисел х 1 , х 2 , ..., х m , при которой суммарный доход максимален:
(13.1)
Решим эту задачу сначала в общем, формульном виде, а потом - для конкретных числовых данных. Найдем для каждого i -го шага условный оптимальный выигрыш (от этого шага и до конца), если мы подошли к данному шагу с запасом средств S. Обозначим условный оптимальный выигрыш W i (S), а соответствующее ему условное оптимальное управление - средства, вкладываемые в i -е предприятие, - x i (S).
Начнем оптимизацию с последнего, т - го шага. Пусть мы подошли к этому шагу с остатком средств S. Что нам делать? Очевидно, вложить всю сумму S целиком в предприятие П m . Поэтому условное оптимальное управление на m -м шаге: отдать последнему предприятию все имеющиеся средства S, т. е.
а условный оптимальный выигрыш
W m (S)= (S).
Задаваясь целой гаммой значений S (располагая их достаточно тесно), мы для каждого значения S будем знать x m (S) и W m (S). Последний шаг оптимизирован.
Перейдем к предпоследнему, (т - 1)-му шагу. Пусть мы подошли к нему с запасом средств S. Обозначим W m -1 (S) условный оптимальный выигрыш на двух последних шагах: (m - 1)-м и m -м (который уже оптимизирован). Если мы выделим на (m - 1)-м шаге (m - 1)-му предприятию средства х, то на последний шаг останется S - х. Наш выигрыш на двух последних шагах будет равен
,
и нужно найти такое х, при котором этот выигрыш максимален:
Знак означает, что берется максимальное значение по всем х, какие только возможны (вложить больше, чем S, мы не можем), от выражения, стоящего в фигурных скобках. Этот максимум и есть условный оптимальный выигрыш за два последних шага, а то значение х, при котором этот максимум достигается,- условное оптимальное управление на (т- 1)-м шаге.
и соответствующее ему условное оптимальное управление x i (S) - то значение х, при котором этот максимум достигается.
Продолжая таким образом, дойдем, наконец, до 1-го предприятия П 1 . Здесь нам не нужно будет варьировать значения S; мы точно знаем, что запас средств перед первым шагом равен К:
Итак, максимальный выигрыш (доход) от всех предприятий найден. Теперь остается только «прочесть рекомендации». То значение х, при котором достигается максимум (13.4), и есть оптимальное управление на 1-м шаге. После того как мы вложим эти средства в 1-е предприятие, у пас их останется К- . «Читая» рекомендацию для этого значения S, выделяем второму предприятию оптимальное количество средств:
,
и т. д. до конца.
А теперь решим численный пример. Исходный запас средств К = 10 (условных единиц), и требуется его оптимальным образом распределить между пятью предприятиями (т = 5). Для простоты предположим, что вкладываются только целые количества средств. Функции дохода (х ) заданы в таблице 13.1.
Таблица 13.1
| х | |||||
| 0,5 1,0 1,4 2,0 2,5 2,8 3,0 3,0 | 0,1 0,5 1,2 1,8 2,5 2,9 3,5 3,5 | 0,6 1,1 1,2 1,4 1,6 1,7 1,8 1,8 | 0,3 0,6 1,3 1,4 1,5 1,5 1,5 1,5 | 1,0 1,2 1,3 1,3 1,3 1,3 1,3 1,3 |
В каждом столбце, начиная с какой-то суммы вложений, доходы перестают возрастать (реально это соответствует тому, что каждое предприятие способно «освоить» лишь ограниченное количество средств).
Произведем условную оптимизацию так, как это было описано выше, начиная с последнего, 5-го шага. Каждый раз, когда мы подходим к очередному шагу, имея запас средств S, мы пробуем выделить па этот шаг то или другое количество средств, берем выигрыш па данном шаге по таблице 13.1, складываем с уже оптимизированным выигрышем на всех последующих шагах до конца (учитывая, что средств у нас осталось уже меньше, как раз на такое количество средств, которое мы выделили) и находим то вложение, на котором эта сумма достигает максимума. Это вложение и есть условное оптимальное управление на данном шаге, а сам максимум - условный оптимальный выигрыш.
В таблице 13.2 даны результаты условной оптимизации по всем шагам. Таблица построена так: в первом столбце даются значения запаса средств S, с которым мы подходим к данному шагу. Далее таблица разделена на пять пар столбцов, соответственно номеру шага. В первом столбце каждой пары приводится значение
Таблица 13.2
| S | i=5 | i=4 | i=3 | i=2 | i=1 | |||||
| x 5 (S ) | W 5 (S ) | x 4 (S ) | W 4 (S ) | x 3 (S ) | W 3 (S ) | x 2 (S ) | W 2 (S ) | x 1 (S ) | W 1 (S ) | |
| 1,0 1,2 1,3 1,3 1,3 1,3 1,3 1,3 1,3 1,3 | 1,0 1,3 1,6 2,3 2,5 2,6 2,7 2,8 2,8 2,8 | 1,0 1,6 2,1 2,4 2,9 3,4 3,6 3,7 3,9 4,1 | 1,0 1,6 2,1 2,4 2,9 3,5 4,1 4,6 5,1 5,6 | 5,6 |
условного оптимального управления, во втором - условного оптимального выигрыша. Таблица заполняется слева направо, сверху вниз. Решение на пятом - последнем - шаге вынужденное: выделяются все средства;
па всех остальных шагах решение приходится оптимизировать. В результате последовательной оптимизации 5-го, 4-го, 3-го, 2-го и 1-го шагов мы получим полный список всех рекомендаций по оптимальному управлению и безусловный оптимальный выигрыш W* за всю операцию - в данном случае он равен 5,6. В последних двух столбцах таблицы 13.2 заполнена только одна строка, так, как состояние системы перед началом первого шага нам в точности известно:
S 0 = К = 10. Оптимальные управления на всех шагах выделены рамкой. Таким образом, мы получили окончательный вывод: надо выделить первому предприятию две единицы из десяти, второму - пять единиц, третьему - две, четвертому - ни одной, пятому - одну единицу. При этом распределении доход будет максимален и равен 5,6.
Чтобы читателю было понятно, как заполняется таблица 13.2, продемонстрируем это на одном образце расчета. Пусть, например, нам нужно оптимизировать решение х 3 (7)- как поступать на третьем шаге, если мы подошли к нему с запасом средств S = 7, и сколько максимум мы можем выиграть на всех оставшихся
Таблица 13.3
| x | 7 - x | W 4 (7 - x ) | +W 4 (7 - x ) | |
| 1,8 1,7 1,6 1,4 1,2 1,1 0,6 | 1,0 1,3 1,6 2,3 2,5 2,6 2,7 | 1,8 2,7 2,9 3,0 3,5 3,2 2,7 |
шагах, включая третий? Предположим, что все шаги после третьего (4-й и 5-й) уже оптимизированы, т. е. заполнены две первые пары столбцов таблицы 13.2. Найдем x 3 (7) и W 3 (7). Для этого составим вспомогательную табличку (см. таблицу 13.3). В первом ее столбце перечислены все возможные вложения х на третьем шаге, не превосходящие S = 7. Во втором столбце - то, что останется после такого вложения от запаса средств S = 7. В третьем столбце - выигрыш на третьем шаге от вложения средств х в третье предприятие заполняется по столбцу ( таблицы 13.1). В четвертом столбце - оптимальный выигрыш на всех оставшихся шагах (четвертом и пятом) при условии, что мы подошли к четвертому шагу с оставшимися средствами (заполняется по столбцу i = 4 таблицы 13.2). В пятом столбце - сумма двух выигрышей: шагового и оптимизированного дальнейшего при данном вложении х в третий шаг.
Из всех выигрышей последнего столбца выбирается максимальный (в таблице 13.3 он равен W 3 (7) = 3,6, а соответствующее управление х (7) = 2).
Возникает вопрос: а что если во вспомогательной таблице типа 13.3 максимум достигается не при одном x , а при двух или больше? Отвечаем: совершенно все равно, какое из них выбрать; от этого выигрыш не зависит. Вообще, в задачах динамического программирования решение вовсе не должно быть единственным (мы об этом уже упоминали).
3. Задача о загрузке машины. Пользуясь методом динамического программирования, можно с успехом решать ряд задач оптимизации, описанных в главе 3, в частности, некоторые задачи целочисленного программирования. Заметим, что целочисленность решений, так затрудняющая задачи линейного программирования, в данном случае не усложняет, а наоборот, упрощает процедуру (как нам ее упростила целочисленность вложений в предыдущей задаче).
В качестве примера рассмотрим задачу о загрузке машины (мы уже упоминали о пей в предыдущей главе): имеется определенный набор предметов П 1 , П 2 ,..., П n (каждый в единственном экземпляре); известны их веса q 1 , q 2 , ..., q n и стоимости с 1 , с 2 , ..., с n . Грузоподъемность машины равна Q. Спрашивается, какие из предметов нужно взять в машину, чтобы их суммарная стоимость (при суммарном весе Q) была максимальна?
И.Н. Слинкина
Учебное пособие для студентов педагогических вузов
по специальности «Информатика»
Шадринск, 2003
Слинкина И.Н.
Исследование операций. Учебно-методическое пособие. – Шадринск: изд-во Шадринского государственного педагогического института, 2002. - 106 с.
Слинкина И.Н. – кандидат педагогических наук
В учебном пособии представлена теоретическая часть курса «Исследование операций». Оно предназначено для студентов очного и заочного отделений факультетов, реализующих специальность «Информатика».
© Шадринский государственный педагогический институт
© Слинкина И.Н., 2002
Вопросы к блокам по курсу «Исследование операций» 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).
Задача исследования операций
Введение……………………………………………………………………...3
1. Основные понятия и определения исследования операций……..……..5
2. Общая постановка задачи исследования операций…………..…………6
Заключение……………………………………………………………….....13
Литература………………………………………………………………......14
Введение
Исследование операций - научная дисциплина, занимающаяся разработкой и практическим применением методов наиболее эффективного управления различными организационными системами.
Управление любой системой реализуется как процесс, подчиняющийся определенным закономерностям. Их знание помогает определить условия, необходимые и достаточные для осуществления данного процесса. Для этого все параметры, характеризующие процесс и внешние условия, должны быть количественно определены, измерены. Следовательно, цель исследования операций - количественное обоснование принимаемых решений по организации управления.
При решении конкретной задачи управления применение методов исследования операций предполагает:
Построение экономических и математических моделей для задач принятия решения в сложных ситуациях или в условиях неопределенности;
Изучение взаимосвязей, определяющих впоследствии принятие решений, и установление критериев эффективности, позволяющих оценивать преимущество того или иного варианта действия.
Примерами задач исследования операций, отражающих его специфику, могут служить следующие задачи.
Задача 1. Для обеспечения высокого качества выпускаемых изделий на заводе организуется система выборочного контроля. Требуется выбрать такие формы его организации - например, назначить размеры контрольных партий, указать последовательность контрольных операций, определить правила отбраковки, - чтобы обеспечить необходимое качество при минимальных расходах.
Задача 2. Для реализации определенной партии сезонных товаров создается сеть временных торговых точек. Требуется выбрать параметры сети - число точек, их размещение, количество персонала - так, чтобы обеспечить максимальную экономическую эффективность распродажи.
Задача 3. К заданному сроку необходимо провести массовое медицинское обследование группы населения с целью выявления определенных заболеваний. На обследование выделены материальные средства, оборудование, персонал. Требуется разработать такой план обследования - установить число медпунктов, их размещение, вид и количество анализов, чтобы выявить как можно больший процент из числа заболевших.
Необходимо отметить также задачи об использовании ресурсов, о смесях, об использовании мощностей, о раскрое материалов, транспортную задачу и др., в которых требуется найти решение, когда некоторый критерий эффективности (например, прибыль, выручка, затраты ресурсов и т.п.) принимает максимальное или минимальное значение.
Приведенные задачи относятся к разным областям практики, но в них есть общие черты: в каждом случае речь идет о каком-то управляемом мероприятии (операции), преследующем определенную цель. В задаче 1 - это организация выборочного контроля с целью обеспечить качество выпускаемой продукции; в задаче 2 - организация временных торговых точек с целью проведения сезонной распродажи; в задаче 3 - массовое медицинское обследование с целью определения процента заболевших.
В каждой задаче заданы некоторые условия проведения этого мероприятия, в рамках которых следует принять решение - такое, чтобы мероприятие принесло определенную выгоду. Условиями проведения операции в каждой задаче оказываются средства, которыми мы располагаем, время, оборудование, технологии, а решение в задаче 1 заключается в выборе формы контроля - размера контрольных партий, правил отбраковки; в задаче 2 - в выборе числа точек размещения, количества персонала; в задаче 3 - в выборе числа медпунктов, вида и количества анализов.
1. Основные понятия и определения исследования операций
Операция - любое управляемое мероприятие, направленное на достижение цели. Результат операции зависит от способа ее проведения, организации, иначе - от выбора некоторых параметров.
Всякий определенный выбор параметров называется решением.
Оптимальными считают те решения, которые по тем или иным соображениям предпочтительнее других. Поэтому основной задачей исследования операций является предварительное количественное обоснование оптимальных решений.
Замечание 1.Следует обратить внимание на постановку проблемы: само принятие решений выходит за рамки исследования операций и относится к компетенции ответственного лица или группы лиц, которые могут учитывать и другие соображения, отличные от математически обоснованных.
Замечание2. Если в одних задачах исследования операций оптимальным является решение, при котором некоторый критерий эффективности принимает
максимальное или минимальное значение, то в других задачах это вовсе не обязательно. Так, в задаче 2 оптимальным можно считать такое количество торговых точек и персонала в них, при котором среднее время обслуживания покупателей не превысит, например, 5 мин, а длина очереди в среднем в любой момент окажется не более 3 человек.
Для применения количественных методов исследования требуется построить математическую модель операции. При построении модели операция, как правило, упрощается, схематизируется, и схема операции описывается с помощью того или иного математического аппарата.
Модель операции - это достаточно точное описание операции с помощью математического аппарата (различного рода функций, уравнений, систем уравнений и неравенств и т.п.). Составление модели операции требует понимания сущности описываемого явления и знания математического аппарата.
Эффективность операции - степень ее приспособленности к выполнению задачи - количественно выражается в виде критерия эффективности - целевой функции. Например, в задаче об использовании ресурсов критерий эффективности - прибыль от реализации произведенной продукции, которую нужно максимизировать, в транспортной задаче - суммарные затраты на перевозку грузов от поставщиков к потребителям, которые нужно минимизировать. Выбор критерия эффективности определяет практическую ценность исследования. (Неправильно выбранный критерий может принести вред, ибо операции, организованные под углом зрения такого критерия эффективности, приводят порой к неоправданным затратам.)
2. Общая постановка задачи исследования операций
Важно усвоить методологию построения моделей задач исследования операций. Все факторы, входящие в описание операции, можно разделить на две группы:
постоянные факторы (условия проведения операции), на которые мы влиять не можем. Обозначим их через α1, α2, ... ;
зависимые факторы (элементы решения) x 1, х2, ...; которые в известных пределах мы можем выбирать по своему усмотрению.
Например, в задаче об использовании ресурсов к постоянным факторам следует отнести запасы ресурсов каждого вида, производственную матрицу, элементы которой определяют расход сырья каждого вида на единицу выпускаемой продукции каждого вида. Элементы решения - план выпуска продукции каждого вида.
Критерий эффективности, выражаемый некоторой функцией, называемой целевой, зависит от факторов обеих групп, поэтому целевую функцию Z можно записать в виде
Z = f (x1, х2, ..., α1, α2, ...)
Все модели исследования операций могут быть классифицированы в зависимости от природы и свойств операции, характера решаемых задач, особенностей применяемых математических методов.
Следует отметить, прежде всего, большой класс оптимизационных моделей. Такие задачи возникают при попытке оптимизироватьпланирование и управление сложными системами, в первую очередьэкономическими системами. Оптимизационную задачу можносформулировать в общем виде: найти переменные х1, х2, ..., х n , удовлетворяющие системе неравенств (уравнений)
g i (х1, х2, х3,..., х n )<= b i , i = 1, 2,..., n (0.1)
и обращающие в максимум (или минимум) целевую функцию, т.е.
Z = f (x1, х2, ..., x n ) - m ах (m in ) (0.2)
(Условия неотрицательности переменных, если они есть, входят в ограничения (0.1))
Рассмотрим еще одну, характерную для исследования операций задачу - классическую задачу потребления, имеющую большое значение в экономическом анализе.
Пусть имеется п видов товаров и услуг, количества которых (в натуральных единицах) x1, х2, ..., x n ,по ценам соответственно p 1, p 2, ..., p n за единицу. Суммарная стоимость этих товаров и услуг составляет ∑ p i x i .
Уровень потребления Z может быть выражен некоторой функцией Z = f (x1, х2, ..., x n ) ,называемой функцией полезности. Необходимо найти такой набор товаров и услуг x1, х2, ..., x n при данной величине доходов I, чтобы обеспечить максимальный уровень потребления, т.е.
Z = f (x1, х2, ..., x n ) - m ах (0.3)
при условии
∑ p i x i <= I (0.4)
x i >= 0 ( i = 1, 2,..., n ) (0.5)
Решения этой задачи, зависящие от цен p 1, p 2, ..., p n и величины дохода I , называются функциями спроса.
Очевидно, что рассмотренная задача потребления (0.3)-(0.5), так же как и многие другие, является частным случаем сформулированной выше общей задачи (0.1)-(0.2) на определение экстремума функции п переменных при некоторых ограничениях, т.е. задачей на условный экстремум.
В тех случаях, когда функции f и g i , в задаче (0.1)-(0.2) хотя бы дважды дифференцируемы, можно применять классические методы оптимизации. Однако применение этих методов в исследовании операций весьма ограниченно, так как задача определения условного экстремума функции я переменных технически весьма трудна: метод дает возможность определить локальный экстремум, а из-за многомерности функции определение ее максимального (или минимального) значения (глобального экстремума) может оказаться весьма трудоемким - тем более, что этот экстремум возможен на границе области решений. Классические методы вовсе не работают, если множество допустимых значений аргумента дискретно или функция Z задана таблично. В этих случаях для решения задачи (0.1)-(0.2) применяются методы математического программирования.
Если критерий эффективности Z = f (x1, х2, ..., x n ) (0.2) представляет линейную функцию, а функции g i (х1, х2, х3,..., х n ) в системе ограничений (0.1) также линейны, то такая задача является задачей линейного программирования. Если, исходя из содержательного смысла, ее решения должны быть целыми числами, то эта задача целочисленного линейного программирования. Если критерий эффективности и (или) система ограничений задаются нелинейными функциями, то имеем задачу нелинейного программирования. В частности, если указанные функции обладают свойствами выпуклости, то полученная задача является задачей выпуклого программирования.
Если в задаче математического программирования имеется переменная времени и критерий эффективности (0.2) выражается не в явном виде как функция переменных, а косвенно - через уравнения, описывающие протекание операций во времени, то такая задача является задачей динамического программирования.
Если критерий эффективности (0.2) и система ограничений (0.1) задаются функциями вида с*( x 1^α 1 )*( x 2^α 2 )...( x n ^α n ) , то имеем задачу геометрического программирования. Если функции f и (или) g i в выражениях (0.2) и (0.1) зависят от параметров, то получаем задачу параметрического программирования, если эти функции носят случайный характер, - задачу стохастического программирования. Если точный оптимум найти алгоритмическим путем невозможно из-за чрезмерно большого числа вариантов решения, то прибегают к методам эвристического программирования, позволяющим существенно сократить просматриваемое число вариантов и найти если не оптимальное, то достаточно хорошее, удовлетворительное с точки зрения практики, решение.
Из перечисленных методов математического программирования наиболее распространенным и разработанным является линейное программирование. В его рамки укладывается широкий круг задач исследования операций.
Задачи сетевого планирования и управления рассматривают соотношения между сроками окончания крупного комплекса операций (работ) и моментами начала всех операций комплекса. Эти задачи состоят в нахождении минимальных продолжительностей комплекса операций, оптимального соотношения величин стоимости и сроков их выполнения.
Задачи массового обслуживания посвящены изучению и анализу систем обслуживания с очередями заявок или требований и состоят в определении показателей эффективности работы систем, их оптимальных характеристик, например, в определении числа каналов обслуживания, времени обслуживания и т.п.
Задачи управления запасами состоят в отыскании оптимальных значений уровня запасов (точки заказа) и размера заказа. Особенность таких задач заключается в том, что с увеличением уровня запасов, с одной стороны, увеличиваются затраты на их хранение, но с другой стороны, уменьшаются потери вследствие возможного дефицита запасаемого продукта.
Задачи распределения ресурсов возникают при определенном наборе операций (работ), которые необходимо выполнять при ограниченных наличных ресурсах, и требуется найти оптимальные распределения ресурсов между операциями или состав операций.
Задачи ремонта и замены оборудования актуальны в связи с износом и старением оборудования и необходимостью его замены с течением времени. Задачи сводятся к определению оптимальных сроков, числа профилактических ремонтов и проверок, а также моментов замены оборудования модернизированным.
Задачи составления расписания (календарного планирования) состоят в определении оптимальной очередности выполнения операций (например, обработки деталей) на различных видах оборудования.
Задачи планировки и размещения состоят в определении оптимального числа и места размещения новых объектов с учетом их взаимодействия с существующими объектами и между собой.
Задачи выбора маршрута, или сетевые задачи, чаще всего встречаются при исследовании разнообразных задач на транспорте и в системе связи и состоят в определении наиболее экономичных маршрутов.
Среди моделей исследования операций особо выделяются модели принятия оптимальных решений в конфликтных ситуациях, изучаемые теорией игр. К конфликтным ситуациям, в которых сталкиваются интересы двух (или более) сторон, преследующих разные цели, можно отнести ряд ситуаций в области экономики, права, военного дела и т. п. В задачах теории игр необходимо выработать рекомендации по разумному поведению участников конфликта, определить их оптимальные стратегии.
На практике в большинстве случаев успех операции оценивается не по одному, а сразу по нескольким критериям, один из которых следует максимизировать, другие - минимизировать. Математический аппарат может принести пользу и в случаях многокритериальных задач исследования операции, по крайней мере, помочь отбросить заведомо неудачные варианты решений.
Для того чтобы из множества критериев, в том числе и противоречащих друг другу (например, прибыль и расход), выбрать целевую функцию, необходимо установить приоритет критериев. Обозначим f 1 (x), f 2 (x), ..., f n (x) (здесь х - условный аргумент). Пусть они расположены в порядке убывания приоритетов. В зависимости от определенных условий возможны в основном два варианта:
В качестве целевой функции выбирается критерий f 1 (x), обладающий наиболее высоким приоритетом;
Рассматривается комбинация
f ( x ) = ω 1 * f 1 ( x ) + ω 2 * f 2 ( x ) + …+ ω n * f n ( x ) , (0.6)
где ω 1 , ω 2 , … ω n - некоторые коэффициенты (веса).
Величина f (х) , учитывающая в определенной степени все критерии, выбирается в качестве целевой функции.
В условиях определенности ω i - числа, f i (x) - функции. В условиях неопределенности f i (x) могут оказаться случайными и вместо f i (x) в качестве целевой функции следует рассматривать математическое ожидание суммы (0.6).
Попытка сведения многокритериальной задачи к задаче с одним критерием эффективности (целевой функцией) в большинстве случаев не дает удовлетворительных результатов. Другой подход состоит в отбрасывании ("выбраковке") из множества допустимых решений заведомо неудачных решений, уступающих другим по всем критериям. В результате такой процедуры остаются так называемые эффективные (или "паретовские") решения, множество которых обычно существенно меньше исходного. А окончательный выбор "компромиссного" решения (не оптимального по всем критериям, которого, как правило, не существует, а приемлемого по этим критериям) остается за человеком - лицом, принимающим решение.
Заключение
В создание современного математического аппарата и развитие многих направлений исследования операций большой вклад внесли российские ученые Л.В. Канторович, Н.П. Бусленко, Е.С. Вентцель, Н.Н. Воробьев, Н.Н. Моисеев, Д.Б. Юдин и многие другие. Особо следует отметить роль академика Л.В. Канторовича, который в 1939 г., занявшись планированием работы агрегатов фанерной фабрики, решил несколько задач: о наилучшей загрузке оборудования, о раскрое материалов с наименьшими потерями, о распределении грузов по нескольким видам транспорта и др. Л.В. Канторович сформулировал новый класс условно-экстремальных задач и предложил универсальный метод их решения, положив начало новому направлению прикладной математики - линейному программированию.
Значительный вклад в формирование и развитие исследования операций внесли зарубежные ученые Р. Акоф, Р. Беллман, Г. Данциг, Г. Кун, Дж. Нейман, Т. Саати, Р. Черчмен, А. Кофман и др.
Методы исследования операций, как и любые математические методы, всегда в той или иной мере упрощают, огрубляют задачу, отражая порой нелинейные процессы линейными моделями, стохастические системы - детерминированными, динамические процессы - статическими моделями и т.д. Жизнь богаче любой схемы. Поэтому не следует ни преувеличивать значение количественных методов исследования операций, ни преуменьшать его, ссылаясь на примеры неудачных решений. Уместно привести в связи с этим шутливо-парадоксальное определение исследования операций, сделанное одним из его создателей Т. Саати, как "искусства давать плохие ответы на те практические вопросы, на которые даются еще худшие ответы другими методами".
Литература
1. Кремер Н. Ш., Путко Б. А., Тришин И. М., Фридман М. Н. Исследование операций в экономике: Учебное пособие для вузов - М.: ЮНИТИ, 2002.
2. Вентцель Е.С. Исследование операций. Задачи, принципы, методология - М.: Наука, 1980.
3. Горелик В.А., Ушаков И.А. Исследование операций. - М.: Машиностроение, 1986.
Следует усвоить основные понятия и определения исследования операций.
Операция - любое управляемое мероприятие, направленное на достижение цели. Результат операции зависит от способа ее проведения, организации, иначе - от выбора некоторых параметров. Всякий определенный выбор параметров называется решением. Оптимальными считают те решения, которые по тем или иным соображениям предпочтительнее других. Поэтому основной задачей исследования операций является предварительное количественное обоснование оптимальных решений.
Замечание 1
Следует обратить внимание на постановку проблемы: само принятие решений выходит за рамки исследования операций и относится к компетенции ответственного лица или группы лиц, которые могут учитывать и другие соображения, отличные от математически обоснованных.
Замечание 2
Если в одних задачах исследования операций оптимальным является решение, при котором выбранный критерий эффективности принимает максимальное или минимальное значение, то в других задачах это вовсе не обязательно. Так, в задаче оптимальным можно считать, например, такое количество торговых точек и персонала в них, при котором среднее время обслуживания покупателей не превысит, например, 5 мин, а длина очереди в среднем в любой момент окажется не более 3 человек (1, стр. 10-11).
Эффективность производственно-коммерческой деятельности в значительной степени определяется качеством решений, повседневно принимаемым менеджерами разного уровня. В связи с этим большое значение приобретают задачи совершенствования процессов принятия решений, решить которые позволяет исследование операций. Термин «исследование операций» впервые начал использоваться в 1939-1940 гг. в военной области. К этому времени военная техника и ее управление принципиально усложнилось вследствие научно-технической революции. И поэтому к началу Второй мировой войны возникла острая необходимость проведения научных исследований в области эффективного использования новой военной техники, количественной оценки и оптимизации принимаемых командованием решений. В послевоенный период успехи новой научной дисциплины были востребованы в мирных областях: в промышленности, предпринимательской и коммерческой деятельности, в государственных учреждениях, в учебных заведениях.
Исследование операций – это методология применения математических количественных методов для обоснования решений задач во всех областях целенаправленной человеческой деятельности. Методы и модели исследования операций позволяют получить решения, наилучшим образом отвечающие целям организации.
Исследование операций - это наука, занимающаяся разработкой и практическим применением методов наиболее эффективного (или оптимального) управления организационными системами.
Основной постулат исследования операций состоит в следующем: оптимальным решением (управлением) является такой набор значений переменных, при котором достигается оптимальное (максимальное или минимальное) значение критерия эффективности (целевой функции) операции и соблюдаются заданные ограничения.
Предметом исследования операций являются задачи принятия оптимальных решений в системе с управлением на основе оценки эффективности ее функционирования. Характерными понятиями исследования операций являются: модель, изменяемые переменные, ограничения, целевая функция.
Предмет исследования операций в реальности - это системы организационного управления (организации), которые состоят из большого числа взаимодействующих между собой подразделений, причем интересы подразделений не всегда согласуются между собой и могут быть противоположными.
Целью исследования операций является количественное обоснование принимаемых решений по управлению организациями.
Решение, которое оказывается наиболее выгодным для всей организации, называется оптимальным, а решение, наиболее выгодное одному или нескольким подразделениям, будет субоптимальным.
В качестве примера типичной задачи организационного управления, где сталкиваются противоречивые интересы подразделений, рассмотрим задачу управления запасами предприятия.
Производственный отдел стремится выпускать как можно больше продукции при наименьших затратах. Поэтому он заинтересован в возможно более длительном и непрерывном производстве, т. е. в выпуске изделий большими партиями, ибо такое производство снижает затраты на переналадку оборудования, а следовательно и общие производственные затраты. Однако выпуск изделий большими партиями требует создания больших объемов запасов материалов, комплектующих изделий и т. д.
Отдел сбыта также заинтересован в больших запасах готовой продукции, чтобы удовлетворить любые запросы потребителя в любой момент времени. Заключая каждый контракт, отдел сбыта, стремясь продать как можно больше продукции, должен предлагать потребителю максимально широкую номенклатуру изделий. Вследствие этого между производственным отделом и отделом сбыта часто возникает конфликт по поводу номенклатуры изделий. При этом отдел сбыта настаивает на включении в план многих изделий, выпускаемых в небольших количествах даже тогда, когда они не приносят большой прибыли, а производственный отдел требует исключения таких изделий из номенклатуры продукции.
Финансовый отдел, стремясь минимизировать объем капитала, необходимого для функционирования предприятия, пытается уменьшить количество «связанных» оборотных средств. Поэтому он заинтересован в уменьшении запасов до минимума. Как видим, требования к размерам запасов у разных подразделений организации оказываются различными. Возникает вопрос, какая стратегия в отношении запасов будет наиболее благоприятной для всей организации. Это типичная задача организационного управления. Она связана с проблемой оптимизации функционирования системы в целом и затрагивает противоречивые интересы ее подразделений.
Основные особенности исследования операций:
1. Системный подход к анализу поставленной проблемы. Системный подход, или системный анализ, является основным методологическим принципом исследования операций, который состоит в следующем. Любая задача, какой бы частной она не казалась на первый взгляд, рассматривается с точки зрения ее влияния на критерий функционирования всей системы. Выше системный подход был проиллюстрирован на примере задачи управления запасами.
2. Для исследования операций характерно, что при решении каждой проблемы возникают все новые и новые задачи. Поэтому если сначала ставятся узкие, ограниченные цели, применение операционных методов не эффективно. Наибольший эффект может быть достигнут только при непрерывном исследовании, обеспечивающем преемственность в переходе от одной задачи к другой.
3. Одной из существенных особенностей исследования операций является стремление найти оптимальное решение поставленной задачи. Однако часто такое решение оказывается недостижимым из-за ограничений, накладываемых имеющимися в наличии ресурсами (денежные средства, машинное время) или уровнем современной науки. Например, для многих комбинаторных задач, в частности задач календарного планирования при числе станков п > 4, оптимальное решение при современном развитии математики оказывается возможным найти лишь простым перебором вариантов. Тогда приходится ограничиваться поиском «достаточно хорошего», или субоптимального решения. Поэтому исследование операций один из его создателей - Т. Саати - определил как «...искусство давать плохие ответы на те практические вопросы, на которые даются еще худшие ответы другими методами».
4. Особенность операционных исследований состоит в том, что они проводятся комплексно, по многим направлениям. Для проведения такого исследования создается операционная группа. В ее состав входят специалисты разных областей знания: инженеры, математики, экономисты, социологи, психологи. Задачей создания подобных операционных групп является комплексное исследование всего множества факторов, влияющих на решение проблемы, и использование идей и методов различных наук.
Каждое операционное исследование проходит последовательно следующие основные этапы:
1) описание задачи планирования,
2) построение математической модели,
3) нахождение решения,
4) проверка и корректировка модели,
5) реализация найденного решения на практике.
Описание задачи планирования:
Задачи сетевого планирования и управления
рассматривают соотношения между сроками окончания крупного комплекса операций (работ) и моментами начала всех операций комплекса. Эти задачи состоят в нахождении минимальной продолжительности комплекса операций, оптимального соотношения величин стоимости и сроков их выполнения.
Задачи массового обслуживания посвящены изучению и анализу систем обслуживания с очередями заявок или требований и состоят в определении показателей эффективности работы систем, их оптимальных характеристик, например в определении числа каналов обслуживания, времени обслуживания и т.п.
Задачи управления запасами состоят в отыскании оптимальных значений уровня запасов (точек заказа) и размеров заказа. Особенность таких задач заключается в том, что с увеличением уровня запасов, с одной стороны, увеличиваются затраты на их хранение, но, с другой стороны, уменьшаются потери вследствие возможного дефицита запасаемого продукта.
Задачи распределения ресурсов возникают при определенном наборе операций (работ), которые необходимо выполнять при ограниченных наличных ресурсах, и требуется найти оптимальные распределения ресурсов между операциями или состав операций.
Задачи ремонта и замены оборудования актуальны в связи с износом и старением оборудования и необходимостью его замены с течением времени. Задачи сводятся к определению оптимальных сроков, числа профилактических ремонтов и проверок, а также моментов замены оборудования модернизированным.
Задачи составления расписания (календарного планирования) состоят в определении оптимальной очередности выполнения операций (например, обработки деталей) на различных видах оборудования.
Задачи планировки и размещения состоят в определении числа и места размещения новых объектов с учетом их взаимодействия с существующими объектами и между собой.
Задачи выбора маршрута, или сетевые задачи, чаще всего встречаются при исследовании разнообразных задач на транспорте и в системе связи и состоят в определении наиболее экономичных маршрутов (1, стр.15).