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

УДК 519.816 
 
К47 

Р е ц е н з е н т  
канд. техн. наук, доц. А.П. Смирнов 

Клемперт В.М. 
К47  
Теория систем и системный анализ: Лаб. практикум. – М.: 
МИСиС, 2005. – 105 с. 

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

© Московский государственный институт

стали и сплавов (Технологический  
университет) (МИСиС), 2005 

СОДЕРЖАНИЕ 

Введение................................................................................................4 
Основные понятия и определения ......................................................5 
Лабораторная работа 1. Линейное программирование.....................9 
Лабораторная работа 2. Динамическое программирование ...........39 
Лабораторная работа 3. Системы на основе Марковских цепей....54 
Лабораторная работа 4. Системы массового обслуживания..........63 
Лабораторная работа 5. Оценка надежности систем.......................75 
Лабораторная работа 6. Конфликтные системы..............................88 
Лабораторная работа 7. Сетевые процессы......................................95 
 

Введение 

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

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

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

QS к сумме свойств qi составляющих ее элементов 

1

n

S
i
i

Q
q

=

⎛
⎞
< ±
⎜
⎟
>
⎜
⎟
⎝
⎠
∑
 и 

невыводимость из элементов свойств целого. С одной стороны, существует зависимость каждого элемента, свойства и отношения системы от его места, функций внутри целого. Понятие целостности 
системы перенесено в теорию систем из биологии, где под целостностью живого организма (системы) понимают единство его реакций 
на внешние воздействия. С другой стороны, 
(
)
S
i
Q
f q
=
, т.е. система 
является функцией составляющих ее элементов. 
Целостность характеризуется рядом свойств и особенностей. 
Многогранность целостности выражается понятиями: 
– дифференциация – отражает свойство расчлененности целого. 
Дифференциация обеспечивает большее разнообразие, большую живучесть образования; 
– интеграция – противоположное понятие, объединение совокупностей в единое образование; 
– симметрия и асимметрия − характеризуют степень соразмерности в пространственных и временных рядах системы. Центральная 
симметрия обеспечивает быструю передачу информации, быстрое 
приспособление системы к возмущающим воздействиям. Симметрия 
относительно оси выражается в наличии групп параллельных объектов. Такая симметрия обеспечивает повышение пропускной способности системы и увеличение ее жизнеспособности; 
– структурность − возможность описания системы через установление ее структуры, т.е. сети связей и отношений системы; обусловленность поведения системы поведением ее отдельных элементов и свойствами ее структуры; 
– взаимозависимость системы и среды (система формирует и 
проявляет свои свойства в процессе взаимодействия со средой, являясь при этом ведущим активным компонентом взаимодействия); 
– иерархичность − каждый компонент системы в свою очередь 
может рассматриваться как система, а исследуемая в данном случае 

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

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

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

Лабораторная работа 1 

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ 

(2 часа) 

1.1 Цель работы 

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

1.2. Теоретическое введение 

Линейному программированию в практикуме отведено проведение одной из лабораторных работ − ознакомление с основной задачей линейного программирования (ОЗЛП) или одной из специальных 
задач линейного программирования, широко применяемой в практике − транспортной задачей. Специальными задачами называют такие, 
матрицы условий которых обладают определенными структурными 
особенностями, позволяющими упростить метод решения. 
ОЗЛП формулируется следующим образом. Требуется найти максимум (или минимум) линейной функции n переменных x1, x2, ..., xn:: 

 
L = L (x1, x2,..., xn ) = c1 x1 + c2 x2 +...+ cn xn 
(1.1) 

при ограничениях, наложенных на переменные x1, x2, ..., xn  

 

11 1
12 2
1
1

21 1
22 2
2
2

1 1
2 2

...
,

...
,

.......................................

...
.

n n

n n

m
m
mn n
m

a x
a x
a x
b

a x
a
x
a
x
b

a
x
a
x
a
x
b

+
+
+
=

+
+
+
=

+
+
+
=

 

(1.2)

 

Требования неотрицательности переменных выделяют в отдельную систему ограничений: 

 
x1 ≥ 0, xn ≥ 0. 

В задачах линейного программирования число n переменных 
больше числа m уравнений системы. В таком случае система имеет 
бесчисленное множество решений. Для получения единственного 
решения избыточному числу (n − m) переменных системы придают 

произвольные значения и тогда эти переменные называют свободными. Переменные, соответствующие числу m строк матрицы, называют базисными. 
Линейную функцию − критерий качества выбранных переменных 
− принято называть линейной формой задачи, а множество наборов 
переменных (x1, x2, .., xn:), удовлетворяющих ограничениям − областью определения задачи линейного программирования или областью определения ее линейной формы.  
Систему равенств и неравенств, порождающую область определения задачи, называют системой условий задачи.  
Таблицу A 

 

11
12
1

21
22
2

1
2

...
...
,
...
...
...
...

...

n

n

m
m
mn

a
a
a
a
a
a
A

a
a
a

=
 
(1.3) 

составленную из коэффициентов при переменных в системе условий, 
называют матрицей условий задачи. Если матрицу пополнить 
столбцом свободных членов, то получим новую матрицу. Эта матрица содержит, очевидно, m строк и (n+1) столбцов и называется расширенной матрицей системы. 
Каждый столбец Aj матрицы условий называют вектором условий задачи. 
Вектор, составленный из свободных членов условий, называют 
вектором ограничений рассматриваемой задачи. 
Если система условий задачи содержит как равенства, так и неравенства, то такую систему условий называют задачей со смешанными условиями. 
Набор переменных X = (x1, x2, ..., xn), удовлетворяющий системе 
условий задачи, называется планом рассматриваемой задачи. Числа 
называются компонентами или составляющими этого плана. 
Каждый план X = (x1, x2,..., xn) задачи определяет конкретное значение ее линейной формы: когда речь идет о задачах, связанных с 
максимизацией линейной формы, чем больше это значение, тем 
лучше данный план. 
План X*= (x1*, x2*, ..., xn*), определяющий максимально возможное значение линейной формы задачи, называется оптимальным 
планом или решением задачи. В этом случае выполняется неравен

ство L (X*) ≥ L (X) для любого плана X задачи. Для задач минимизации линейной формы условие оптимальности принимает следующий 
вид: L (X*) ≤ L (X) для любого плана X задачи. 
Запись линейной формы и, главным образом, системы условий в 
разных задачах заметно различается. В одних случаях искомые переменные зависят от одного индекса, в других − от двух индексов. В одних задачах условия имеют вид равенств, в других − условия являются 
неравенствами. Ряд задач имеет смешанные условия: часть условий − 
линейные уравнения, часть − линейные неравенства. Разнообразие записи условий задач требовало бы разработки специальных методов 
решения различных классов задач и затрудняло бы исследование общих закономерностей линейного программирования. Поэтому естественно стремление свести любую задачу линейного программирования 
к наиболее простой и удобной для исследования форме. Таким форматом записи ОЗЛП является каноническая форма. 
Задача линейного программирования, записанная в общем виде, 
может быть сведена к канонической форме, когда в неравенства вводятся дополнительные неотрицательные переменные, после чего каждое неравенство превращается в равенство. В линейную форму дополнительные переменные входят с нулевыми коэффициентами. 
Математически условия транспортной задачи представлены следующим образом: 
линейная форма: 

 

1
1

min.

m
n

ij ij
i
j
W
c x

=
=
=
→
∑∑
 
(1.4) 

Система условий транспортной задачи: 

 
11
12
1
1
...
,
n
x
x
x
a
+
+
+
=
 

 
21
22
2
2
...
,
n
x
x
x
a
+
+
+
=
 

 
……………………….. 

 
1
2
...
,
m
m
mn
m
x
x
x
a
+
+
+
=
 
(1.5) 

 
11
21
1
1
...
,
m
x
x
x
b
+
+
+
=
 

12
22
2
2
...
,
m
x
x
x
b
+
+
+
=
 

 
………………………… 

 
1
2
...
.
n
n
mn
n
x
x
x
b
+
+
+
=
 

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

 

1
1

.

m
n

i
j

i
j

a
b

=
=
=
∑
∑
 
(1.6) 

В общем случае суммарный запас груза не равен суммарному 
спросу: 

 

1
1

.

m
n

i
j

i
j

a
b

=
=
<>
∑
∑
 
(1.7) 

Система, в которой общий запас груза на всех базах не равен 
суммарной потребности всех потребителей, называется открытой 
моделью или задачей с неправильным балансом. 
Баланс транспортной задачи нарушается в двух случаях: либо 
сумма запасов на базах превышает сумму спросов потребителей, либо сумма спросов превышает наличные запасы. В первом случае 
имеем избыток грузов, во втором − дефицит. 
Для решения этих задач их искусственным приемом сводят к задаче с правильным балансом (закрытой модели). 
При избытке грузов вводим в план перевозок фиктивный потребитель Bф. В таблице плана перевозок образуется дополнительный 
столбец с нулевыми стоимостями ciф в клетках и значением спроса 
bф, равным разности между суммами всех запасов и спросов. 
При дефиците грузов в план перевозок вводится фиктивная база 
Aф. В таблице плана перевозок образуется дополнительная строка с 
нулевыми стоимостями cфj в клетках и запасом aф, равным разности 
между суммами всех спросов и запасов. 
Двухиндексная транспортная задача усложняется, если перевозке 
подлежат неоднородные грузы. Задача может быть трехиндексной 
(переменные xijk, где i − различные базы, j − различные потребители, 
k − различные виды грузов). Еще более сложной (четырехиндексной)