Теория систем и системный анализ (лабораторный практикум)

G. I. hiinei





                Теория систем n системный анализ




3-е здание, переработанное и дополненное

Рекомендовано УМО по образованию в области Инфокоммуникационных технологий и систем связи в качестве учебного пособия для студентов высших учебных заведений, обучающихся по направлению подготовки 11.03.02, 11.04.02 -«Инфокоммуникационные технологии и системы связи» квалификации (степени) «бакалавр», «магистр» и 11.05.04 -«Инфокоммуникационные технологии и системы специальной связи» квалификации «специалист»








Москва
Горячая линия - Телеком 2015



�ДК 303.732.4(076)
ББК з817 я73-5
   Я 47

Рецензенты: доктор техн. наук, доцент, зав. кафедрой инфокоммуникаций Северо-Кавказского федерального университета Г. И. Линец; доктор техн. наук, профессор, профессор кафедры «Автоматизированные системы управления» филиала Московского государственного университета приборостроения и информатики в г. Ставрополе И. А. Калмыков
      Яковлев С. В.
Я 47 Теория систем и системный анализ (лабораторный практикум). Учебное пособие для вузов. — 3-е изд., перераб. и доп. — М.: Горячая линия — Телеком, 2015. — 320 с.: ил.
      ISBN 978-5-9912-0496-5.
          Рассмотрены практические вопросы применения методов системного анализа для решения хорошо структурированных, количественно выражаемых проблем. При этом использована методология исследования операций, которая состоит в построении адекватной математической модели (например, задачи линейного, динамического, нелинейного программирования, задачи теории массового обслуживания, теории игр и др.) и отыскании оптимальной стратегии управления целенаправленными действиями.
          Для студентов, бакалавров, магистров и аспирантов соответствующих специальностей, а также может быть полезно инженерам и другим научно-техническим работникам.
ББК з817 я73-5

Адрес издательства в Интернет www.techbook.ru





Все права защищены.
      Любая часть этого издания не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения правообладателя
© ООО «Научно-техническое издательство «Горячая линия - Телеком» www.techbook.ru
© С. В. Яковлев



       ВВЕДЕНИЕ







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



Введение

мирование, теория принятия решений, теория игр, имитационное моделирование, теория массового обслуживания и т. п.
   Учебное пособие состоит из пятнадцати глав, содержание которых позволяет достаточно подробно рассмотреть основополагающие принципы принятия оптимальных решений.
   В главе 1 изложены различные методы решения классических задач линейного программирования.
   Глава 2 посвящена рассмотрению особенностей нахождения двойственной задачи линейного программирования и исследованию поведения двойственных задач.
   Глава 3 содержит сведения о методах решения классической транспортной задачи и ее разновидности — задачи о назначениях.
   В главе 4 рассмотрены особенности целочисленного линейного программирования и приведены методы решения задачи коммивояжера.
   В главе 5 описываются особенности решения задачи принятия решений в условиях неопределенности с применением критериев Лапласа, Сэвиджа, Гурвица, а также минимаксного критерия.
   В главе 6 приведены сведения о задачах в условиях конфликтных ситуаций и рассмотрены различные методы решения игровых задач.
   Глава 7 посвящена рассмотрению методов решения многокритериальных задач принятия решений.
   В главе 8 рассмотрены задачи динамического программирования и приведены методы решения задачи об оптимальной загрузке.
   Глава 9 содержит сведения о моделях сетевого планирования и управления. Рассмотрены методы анализа временных и вероятностных параметров сетевого графика.
   В главе 10 проанализированы особенности проведения структурной оптимизации сетевых моделей, алгоритмы нахождения минимального остовного дерева. Рассмотрен алгоритм Дейкстры поиска кратчайшего пути.
   В главе 11 рассмотрены особенности проведения оптимизации параметров потока в сетевых моделях, алгоритмы нахождения минимального потока и минимального разреза в сети.
   Глава 12 посвящена рассмотрению марковских моделей принятия решений. Для исследования вероятностных характеристик в непрерывном времени используются уравнения Колмогорова как предельный случай дискретного марковского процесса при переходе к непрерывному времени.



�ведение

5

   В главе 13 рассмотрены оптимизационные модели в теории массового обслуживания, методы принятия решений при анализе систем массового обслуживания с отказами и очередью.
   В главе 14 описываются особенности моделей управления запасами. Представлены методы оптимизации задачи с фиксированью интервалом времени между заказами, могопродукто-вой статической задачи и стохастической задачи управления запасами.
   В главе 15 изложены методы решения задач нелинейного программирования.
   Учебное пособие содержит теоретический материал, достаточный для выполнения лабораторного практикума. Для изучения дисциплины «Теория систем и системный анализ» необходимы знания в области линейной алгебры, дискретной математики, теории вероятностей и математической статистики.
   Каждая из глав пособия содержит одну или две лабораторные работы, выполнение которых позволяет углубить понимание процессов решения оптимизационных задач. Материалы практикума дополняют теоретические сведения по дисциплине «Теория систем и системный анализ» и могут быть использованы при проведении лекций.
   При выполнении заданий лабораторного практикума используются программные продукты: табличный процессор Microsoft Excel версий 2007/2010/2013, система компьютерной алгебры PTC MathCad версий 14/15/Prime 1.0/Prime 2.0/Prime 3.0, а также текстовый редактор документов Microsoft Word версий 2007/2010/2013 или его аналог.



�лава



            1


        МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО
        ПРОГРАММИРОВАНИЯ







           Системный анализ — научный метод познания, представляющий собой последовательность действий по установлению структурных связей между переменными или элементами исследуемой системы [15]. Данный метод опирается на комплекс общенаучных, экспериментальных, естественнонаучных, статистических, математических методов.
   Результатом системных исследований является, как правило, выбор вполне определенной альтернативы — плана развития региона, параметров конструкции и т. д. Поэтому истоки системного анализа, его методические концепции находятся в тех дисциплинах, которые занимаются проблемами принятия решений — исследование операций и общая теория управления.
   Ценность системного подхода состоит в том, что рассмотрение категорий системного анализа создает основу для логического и последовательного подхода к проблеме выбора решений. Эффективность решения проблем с помощью системного анализа определяется структурой решаемых проблем. Согласно классификации, все проблемы подразделяются на три класса [15]:
   • хорошо структурированные или количественно сформулированные проблемы, в которых существенные зависимости выяснены очень хорошо;



�етоды решения задач линейного программирования

7

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



Глава 1

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



    1.1. ФОРМУЛИРОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ


          Рассмотрим пример с двумя переменными. Компания «Российские краски» производит краску для внутренних и наружных работ из сырья двух типов — М₁ и Мг (табл. 1.1) [38].

Таблица 1.1. Основные данные для задачи

                   Расход сырья (т) на 1 т краски  Максимально 
Параметры          Для наружных   Для внутренних    возможный  
Наименование          работ           работ         ежедневный 
                                                   расход сырья
Сырье М(                6               4               24     
Сырье М,                1               2               6      
Доход (тыс. у. е.)      5               4                      
  на 1 т краски                                                

   Отдел маркетинга компании ограничил ежедневное производство краски для внутренних работ до 2 т, а также поставил условие, чтобы этот вид продукции не превышал более чем на



�етоды решения задач линейного программирования

9

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



    1.2.  МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ


          Задача линейного программирования, как и любая задача исследования операций, включает три основных элемента.
   1. Переменные, которые следует определить.
   2. Целевая функция, подлежащая оптимизации.
   3. Ограничения, которым должны удовлетворять переменные.
   В нашем примере необходимо определить ежедневные объемы производства краски для внутренних и наружных работ. Обозначим их как переменные модели: хх — ежедневный объем производства краски для наружных работ; х₂ — ежедневный объем производства краски для внутренних работ.
   Используя эти переменные, строим целевую функцию Z, отражающую получение суммарного ежедневного дохода компании, который необходимо максимизировать:

Z = 5 х х + 4 х₂.
   Ограничения на сырье можно записать следующим образом:

' Используемый объем л сырья для производства < ч обоих видов краски у

Максимально возможный ^ ежедневный расход сырья J'

   Из таблицы с данными получим используемые объемы (т):
   • для сырья М[
6 х х + 4 х₂;
   • для сырья М,
1 х х + 2 х₂.

   Поскольку ежедневный расход сырья М[ и М₂ ограничен соответственно 24и6т, получаем следующие ограничения:
6Xj + 4х₂ < 24;
1X  + 2 х₇ < 6.



Глава 1

   Существует еще два ограничения по спросу на готовую продукцию. Первое из них указывает, что ежедневный объем производства краски для внутренних работ не должен превышать ежедневный объем производства краски для наружных работ более чем на 1 т, т.е. х₂~ х х < 1. Второе ограничение максимального ежедневного объема производства краски для внутренних работ 2 т запишем, как х₂ < 2. Учтем условие неотрицательности переменных: хх > 0, х₂> 0.
   Окончательно задача будет записана следующим образом:


Z = 5Xj + 4х₂ ^ max;


6х + 4х₂ < 24;
                           X   + ²х < ⁶;
■ - х + X < 1;
X < 2;

X > 0, х₂ > 0.



    1.3. ГЕОМЕТРИЧЕСКИЙ МЕТОД
        РЕШЕНИЯ ЗАДАЧИ
        ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

        Геометрический или графический способ решения задачи линейного программирования состоит из двух этапов [38]. 1. Построение пространства допустимых решений (ПДР), удовлетворяющего всем ограничениям модели.
   2. Поиск оптимального решения среди всех точек пространства допустимых решений.

        Этап 1
        Построение пространства допустимых решений
        Проведем оси координат. На горизонтальной оси будут указываться значения переменной хр а на вертикальной — х₂ (рис. 1.1). Условия неотрицательности переменных: хх > 0, х₂ > 0 показывают, что пространство допустимых решений будет лежать в первом квадранте (т.е. выше оси хх и правее оси х₂).
   Учтем оставшиеся ограничения, заменив неравенства на равенства и получив уравнения прямых. Например, неравенство 6хх + 4х₂ < 24 заменяется уравнением прямой 6хх + 4х₂ = 24.