Основные типы задач системотехники

1. Основные типы задач системотехники В зависимости от степени определенности элементов решения различают следующие типы задач системотехники: 1. Простейшие (элементарные) – все элементы решения и результат определяются однозначно и точно. Решаются обычными методами математики, физики, механики и пр.; 2. Хорошо структурированные (разработанные) - все элементы решения определяются однозначно и точно, но возможно получение бесконечного множества результатов, один из которых – искомый оптимальный. Решаются специальными математическими методами (исследования операций, оптимизации, принятия решений) и т.д.; 3. Плохо структурированные – как минимум один из элементов решения является случайной величиной. Решаются с помощью методов теории вероятностей и моделирования систем; 4. Не структурированные – на начальном этапе элементы решения полностью не известны и цель задачи не вполне определена. Решаются такие задачи либо путем упрощения и сведением их к 1-3 типам, либо поэтапно, с уточнением элементов решения на каждом этапе. 2. Понятие об исследовании операций Среди задач системотехники, представляющих практический интерес, наиболее методически разработанными являются хорошо структурированные задачи, в частности задачи по исследованию операций (ИО). Первые публикации по исследованию операций относятся к 40-м годам ХХ века, в которых методы применены для анализа и исследования военных операций. Отсюда и возникло название дисциплины. В послевоенные годы ИО получило широкое распространение и в мирных областях человеческой деятельности. С его помощью сегодня вырабатываются решения в промышленности, на транспорте, в городском хозяйстве и т. п. В 1957 г. появляется монография выдающегося американского математика Р. Беллмана, положившая начало методу динамического программирования. Большой вклад в развитие методов оптимизации подобных задач внесла группа советских математиков во главе с Л. С. Понтрягиным. Инженерная деятельность тесно связана с совокупностями объектов, которые принято называть сложными системами, которые характеризуются многочисленными и разнообразными по типу связями между элементами системы и наличием у системы функции назначения, которой нет у составляющих ее частей. Понятие ИО является составной частью системного анализа и обозначает математическую дисциплину, охватывающую исследование математических моделей для выбора величин, оптимизирующих заданную математическую функцию (критерий). Математическая основа ИО –это методы моделирования принятия решения в сложной системе и общие способы работы с этими моделями, например: • теория игр – метод моделирования оценки воздействия принятого решения на систему. • теория вероятности – метод, который при принятии решений опирается на определение значения вероятности наступления определенных событий с последующим выбором наиболее предпочтительного среди возможных; • методы линейного программирования: в процессе управления одной из главных является задача нахождения оптимального решения из всех имеющихся вариантов. Для достижения этого решения необходимо наличие определенных ресурсов: финансовых, трудовых, материальных, временных и т.д. Поэтому оптимальным вариантом решения будет являться тот, при котором поставленная цель будет достигнута. Несмотря на качественные различия решаемых задач, все они сводятся к выбору наилучшего способа действия, варианта, параметров конструкции и т.д. Появление таких методов связывают с выходом в 1939 г. монографии Л. В. Канторовича «Математические методы в организации и планировании производства», где впервые была поставлена и решена задача линейного программирования – частный случай общей задачи математического программирования. Американским математиком Д. Данцигом был построен алгоритм симплексного метода для линейных программ. 3. Основные элементы решения задачи ИО Операция – это система действий с единым замыслом, ресурсами и направленное к достижению определенной сформулированной цели. Цель — это запланированный результат деятельности, на получение которого направлены ресурсы. Чаще всего цель или цели оформляются в форме требуемых значений различных количественно измеряемых показателей эффективности (ПЭ). Модель — условный образ реального объекта (операции), отражающий его существенные свойства — физический или абстрактный: карта, схема, формула, уравнение, система уравнений или неравенств, сеть и т.д. Решение – это какой-то конкретный выбор из ряда возможностей. Допустимые решения - те решения, которые удовлетворяют наложенным в задаче ограничениям. Оптимальными решениями – являются те допустимые решения, которые по тем или иным критериям предпочтительнее других и обеспечивают экстремальные значения ПЭ. Эффективность операции — степень ее приспособленности к выполнению задачи, часто измеряется вероятностью выполнения задачи, количественно выражается значением целевой функции (ЦФ). Критерий эффективности (КЭ) – правило, обеспечивающее получение итогового результата исследования. Большие промышленные, экономические и военные системы с середины прошлого века стали пристально изучаемым объектом в научных исследованиях особенно в области управления системами. 4. Процессы, рассматриваемые в задачах ИО • Процессы обслуживания Такие процессы подразумевают наличие клиента, требующего обслуживания. Процесс обслуживания при этом характеризуется явлением ожидания. Задача заключается в том, чтобы регулировать появление клиентов или определять объем и организацию обслуживания с тем, чтобы свести к минимуму ожидания и расходы. Для решения описанной задачи с ожиданиями применима теория очередей. Для задачи определения порядка обслуживания клиентов применима теория расписаний. • Процессы распределения Подобные процессы возникают, когда, во-первых существует ряд операций, которые необходимо выполнить, и ряд различных путей их выполнения, во-вторых, нет в наличии ресурсов или средств, обеспечивающих выполнение каждой из этих операций наиболее эффективным образом. Задача заключается в соединении операций и ресурсов таким образом, чтобы добиться максимального общего эффекта. Для получения решения применимы теория линейного программирования и другие виды математического программирования. • Процессы управления запасами Проблемы, связанные с запасами, порождают процессы, требующие следующих решений: во-первых, сколько заказывать (производить или покупать) и во-вторых, когда заказывать. Эти решения требуют регулирования запасов: заказ или переоборудование; дефицит или задержка; изменение уровня производства или закупок. Для получения решений используются теории линейного, динамического и квадратичного программирования. • Процессы замены Существуют два основных класса, связанных с видами износа оборудования: 1) устаревание и уменьшение эффективности в результате длительного срока службы; 2) полный выход из строя. Для устаревающих видов оборудования задача заключается в установлении времени замены с тем, чтобы сократить расходы на новое оборудование, на ремонт и эксплуатацию старого или расходы, связанные со снижением производительности оборудования. Задача относительно оборудования полностью вышедшего из строя ­– определить какие элементы следует заменить и как часто их менять с тем, чтобы снизить расходы на оборудование, на замену частей и другие затраты, связанные с выходом из строя. • Состязательные процессы Процессы, в которых участвуют две или более стороны, как правило, с противоположными интересами называют состязательными. Эффективность решения одной стороны может оказаться сниженной в связи с решением другой стороны. Ситуацию с таким процессом часто называют игрой. Игры характеризуются количеством участников, правилами игры, сформулированными с учетом всех возможных допустимых действий, некоторым множеством конечных состояний (выигрыш, проигрыш, ничья и т. п.) Решение задач в состязательных процессах обеспечивается теорией игр. 5. Классификация задач ИО • По зависимости параметров задачи от времени: 1. Статическая задача - принятие решения происходит при условии, что все параметры задачи заранее известны и не изменяются во времени. 2. Динамическая задача- процессе принятия решения параметры задачи изменяются по времени. Процедура принятия решения осуществляется поэтапно и может быть представлена и виде процесса, зависящего от времени. • По зависимости от достоверности информации о задаче: 1. Детерминированная задача - все параметры задачи заранее известны. Для решения детерминированных задач в основном применяются методы математического программирования. 2. Недетерминированная задача -не все параметры задачи заранее известны. Оптимальное решение недетерминированной задачи ИО отыскать практически невозможно. Можно получить лишь некоторое приемлемое решение. 3. Стохастическая задача. Не все параметры задачи заранее известны, но имеются статистические данные о неизвестных параметрах (вероятности, функции распределения, математические ожидания и т. д.). Для отыскания оптимального решения стохастической задачи применяется один и из следующих приемов: - сведение к детерминированной задаче (неизвестные параметры заменяются их средними значениями). - «оптимизация в среднем» (вводится и оптимизируется некоторый статистический критерий). 4. Задача в условиях полной неопределенности. Статистические данные о неизвестных параметрах отсутствуют. Задачи ИО в условиях неопределенности в основном изучаются в рамках теории игр. • По виду критерия оптимальности: Наиболее распространенные критерии оптимальности заключаются в оптимизации (минимизации либо максимизации) одной или нескольких ЦФ. Задача оптимизации ЦФ на заданном множестве допустимых числовых решений называется задачей математического программирования. В задачах ИО присутствуют в общем случае несколько критериев. Такие задачи называются многокритериальными. Критерии могут оказаться противоречивыми, т. e. решение, лучшее по определенному признаку, может оказаться худшим по другому признаку. Например, минимизация стоимости и максимизации качества товара почти всегда противоречивы. В этом случае задача отыскания решения, предпочтительного по всем признакам, будет некорректной, т. e. не будет иметь ни одного решения. Наиболее изученными являются однокритериальные задачи математического программирования (с одной ЦФ): 1) Задачи линейного программирования. ЦФ -линейная, множество допустимых решений – выпуклый многогранник. 2) Задачи квадратичного программирования. ЦФ-квадратичная, а множество допустимых решений – выпуклый многогранник. 3) Задачи стохастического программирования. Это задачи линейного программирования с неизвестными числовыми параметрами, о которых имеются статистические данные. 4) Задачи дискретного программирования. Множество допустимых решений – дискретное множество. 5) Задачи целочисленного программирования. Множество допустимых решений – целые числа. В настоящее время сложилось несколько типовых методических задач по исследованию операций: составление расписаний (сетевой график), транспортная (поиск оптимального маршрута), распределительная и т.д. 6. Задачи по составлению расписаний Основными понятиями таких задач являются понятия события и работы. Работа – это некоторый процесс, приводящий к достижению определенного результата, требующий затрат каких-либо ресурсов и имеющий протяженность во времени. По количеству затрачиваемого времени работа может быть: действительной, т. е. требующей затрат времени; фиктивной, т. е. формально не требующей затрат времени и представляющей связь между какими-либо работами. Событие – это момент времени, когда завершаются одни работы и начинаются другие. Событие представляет собой результат проведенных работ и, в отличие от работ, не имеет протяженности во времени. Взаимосвязь работ и событий, необходимых для достижения конечной цели проекта, изображается с помощью сетевого графика (сетевой модели). На сетевом графике работы изображаются стрелками, которые соединяют вершины, изображающие события. Начало и окончание любой работы описываются парой событий, которые называются начальным и конечным событиями. Рис.1. Любое событие может считаться наступившим только тогда, когда закончатся все входящие в него работы. Поэтому работы, выходящие из некоторого события, не могут начаться, пока не будут завершены все работы, входящие в это событие. Важное значение для анализа сетевых моделей имеет понятие пути. Путь – это любая последовательность работ в сетевом графике, в котором конечное событие одной работы совпадает с начальным событием следующей за ней работы. Построение сети является первым шагом решения задачи. Вторым шагом является расчет сетевой модели, который выполняют прямо на сетевом графике, пользуясь простыми правилами. Сетевые графики составляются на начальном этапе планирования проекта. Вначале проект разбивается на отдельные работы, составляется перечень работ и событий, устанавливаются логические связи и последовательность выполнения работ, оценивается продолжительность выполнения работ. Затем составляется сетевой график по следующим правилам: • В сетевом графике не должно быть тупиковых событий (кроме завершающего), т. е. таких, за которыми не следует ни одной работы. • Не должно быть событий (кроме исходного), которым не предшествует хотя бы одна работа. • В сетевом графике не должно быть циклов. • Любые два события связаны не более чем одной работой. • Сетевой график должен быть упорядочен. Упорядочение сетевого графика заключается в таком расположении событий и работ, при котором для любой работы предшествующее ей событие расположено левее и имеет меньший номер по сравнению с завершающим эту работу событием. На рис. 2 представлены примеры построения начала сетевого графика: рис. 2 (а) – для варианта с одной исходной работой (работа а), рис. 2 (б) – для варианта с тремя исходными работами. Рис.2. В процессе дальнейшего построения сетевого графика необходимо придерживаться следующих правил: • Если работа «г» должна выполняться только после выполнения работы «а», то на графике это изображается в виде последовательной цепочки работ и событий (рис. 3). Рис.3. • Если для выполнения работ «г» и «е» необходим результат одной и той же работы, например «в», то график должен иметь следующий вид (рис. 4): Рис.4. • Если для выполнения работы «е» необходимы результаты работ «в» и «г» то график должен иметь следующий вид (рис. 5): Рис.5. • Если выполнение какой-либо работы (например, «е») возможно только после получения совокупного результата двух или более параллельно выполняемых работ (например, «в» и «г»), а выполнение другой работы (например, «д») – после получения результата только одной из них (например, «в»), то в сетевом графике необходимо ввести дополнительное событие и фиктивную работу (пунктир) (рис.6). Рис.6. • В сети не должно быть замкнутых контуров, состоящих из взаимосвязанных работ, создающих замкнутую цепь (например, цепочка работ «д», «г» на рис. 7). Рис.7. Данная ситуация свидетельствует об ошибке при составлении перечня работ и определении их взаимосвязей. В таком случае необходимо проанализировать исходные данные и либо перенаправить работу, создающую цикл, в другое событие, либо совсем исключить. На рис. 8 представлена ситуация когда работа «г» является частью общего результата. Рис.8.