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

УДК 519.82 

К48 

К48 
Клемперт В.М. Теория систем и системный анализ: Учебное 
пособие для практических занятий. – М.: МИСиС, 2001. –100 с. 

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

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

КЛЕМПЕРТ Виктор Моисеевич 

ТЕОРИЯ СИСТЕМ И СИСТЕМНЫЙ АНАЛИЗ 

Учебное пособие 
для практических занятий студентов специальности 3514 

Рецензент доц. А.П. Смирнов 

Редактор Т.А. Кравченко 

Объем 100 стр. 
Тираж  40 экз. 

Заказ 902 
Цена “C” 
Регистрационный   № 292 

Московский государственный институт стали и сплавов, 
119991, Москва, Ленинский пр-т, 4 
Отпечатано в типографии издательства «Учеба» МИСиС, 
117419, Москва, ул. Орджоникидзе, 8/9 

ОГЛАВЛЕНИЕ 

Введение....................................................................................................5 
1. Линейное программирование..............................................................6 

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

1.1.1. Общие положения..............................................................6 
1.1.2. Геометрическая интерпретация  
задач линейного программирования........................................10 
1.1.3. Решение задачи линейного  
программирования симплекс-методом....................................13 
1.1.4. Задачи для самостоятельного решения..........................23 
1.1.5. Вопросы для самопроверки ............................................27 

1.2. Транспортная задача ..................................................................28 

1.2.1. Постановка задачи ...........................................................28 
1.2.2. Транспортная задача с правильным балансом..............28 
1.2.3. Метод потенциалов .........................................................37 
1.2.4. Задача выбора...................................................................42 
1.2.5. Задачи для самостоятельного решения..........................44 
1.2.6. Вопросы для самопроверки ............................................45 

1.3. Многоиндексные транспортные задачи ...................................46 

1.3.1. Постановка задачи ...........................................................46 
1.3.2. Пример решения четырехиндексной  
транспортной задачи .................................................................49 
1.3.3. Вопросы для самопроверки ............................................57 

2. Динамическое программирование....................................................58 

2.1. Общие положения ......................................................................58 
2.2. Процессы распределения ресурсов...........................................60 

2.2.1. Постановка задачи ...........................................................60 
2.2.2. Одномерный процесс распределения ресурсов ............61 
2.2.3. Двумерный процесс распределения ресурсов...............66 
2.2.4. Трехмерный процесс распределения ресурсов.............71 
2.2.5. Задачи для самостоятельного решения..........................73 

2.3. Оптимальные траектории ..........................................................73 

2.3.1. Постановка задачи ...........................................................74 
2.3.2. Вопросы для самопроверки ............................................77 

2.4. Задачи целочисленного программирования ............................77 

2.4.1. Постановка задачи ...........................................................78 
2.4.2. Задачи для самостоятельного решения..........................85 

3 

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

2.5.1. Постановка транспортной задачи...................................86 
2.5.2. Транспортная задача с неизменной 
стоимостью перевозки единицы груза.....................................88 
2.5.3. Транспортная задача с  
переменной стоимостью перевозки единицы груза ...............93 
2.5.4. Вопросы для самопроверки ............................................97 

Рекомендуемая литература....................................................................99 

4 

ВВЕДЕНИЕ 

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

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

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

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

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

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

5 

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

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

1.1.1. Общие положения 

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

 
a1x1 + a2x2 +...+ anxn = b , 

где a1, a2, ... an – произвольные действительные числа. 

Набор значений переменных x1 = λ1, x2 = λ2, ... xn = λn удовлетворяет заданному уравнению, если в результате подстановки этих 
значений переменных в данное уравнение оно превращается в арифметическое тождество. 

Предположим, что задана система m линейных уравнений относительно n переменных x1, x2, ... xn. В общем случае такую систему 
можно записать в следующем виде: 

 
a11x1 + a12x2+...+a1nxn = b1; 

 
a21x1 + a22x2 +...+ a2nxn = b2; 

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

 
am1x1 + am2x2 +...+ amnxn = bm. 

Коэффициенты aij при переменных в системе образуют m 
строк и n столбцов и называются матрицей системы. Если матрицу 
пополнить столбцом свободных членов, то получим новую матрицу. 
Эта матрица содержит, очевидно, m строк и n + 1 столбцов и называется расширенной матрицей системы. 

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

6 

матрица такой системы называется квадратной, а сама система имеет 
единственное решение. 

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

Основная задача линейного программирования (ОЗЛП) формулируется следующим образом. 

Требуется найти максимум (или минимум) линейной функции n переменных x1, x2, ...., xn

 
L = L (x1, x2, ...., xn) = c1x1 + c2x2 + .... + cnxn

при следующих ограничениях, наложенных на переменные 
x1, x2, ...., xn: 

 
a11x1 + a12x2 + a1nxn = b1; 

 
a21x1 + a22x2 + a2nxn = b2; 

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

 
am1x1 + am2x2 + amnxn = bm; 

 
x1 > = 0, xn > =0, 

где b1 ... bn – свободные члены, представляющие собой ограничения, 
наложенные на решение задачи. 

Введем некоторые определения. 
Линейную функцию – критерий качества выбранных переменных – принято называть линейной формой задачи, а множество 
наборов переменных (x1, x2, ...., xn), удовлетворяющих ограничениям 
– областью определения задачи линейного программирования или 
областью определения ее линейной формы. 

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

Таблицу 

7 

 
, 

⎟⎟
⎟
⎟
⎟
⎟
⎟

⎠

⎞

⎜⎜
⎜
⎜
⎜
⎜
⎜

⎝

⎛

=

−
−
−

mn
m
m

n
l
m
l
m
l
m

n

n

a
a
a

a
a
a

a
a
a

a
a
a

A

2
1

,
2
,
,1

2
22
21

1
12
11

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

составленную из коэффициентов системы условий, называют матрицей условий задачи. 

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

Каждый столбец Aj матрицы условий называют вектором условий задачи. 

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

В векторной форме условия задачи имеют следующий вид: 

 
A1x1 + A2x2 + .... + Anxn <= B. 

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

Каждый план X = (x1, x2, ...., xn) задачи определяет конкретное 
значение ее линейной формы: когда речь идет о задачах, связанных с 
максимизацией линейной формы, чем больше это значение, тем 
лучше данный план. 

План X* = (x1

*, x2

*, ...., xn

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

 
L(X*) >= L(X) 

для любого плана X задачи. 

Естественно, что для задач минимизации линейной формы 
условие оптимальности принимает следующий вид: 

 
L(X*) <= L(X) 

для любого плана X задачи. 

8 

В зависимости от вида системы условий решение ОЗЛП приводит к одному из следующих случаев. 

Случай 1. Условия противоречивы и не существует набора 
чисел x1, x2, ...., xn, удовлетворяющего всем условиям задачи, т. е. задача не имеет ни одного плана. 

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

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

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

 
L = c1x1 + c2x2+ .... + cnxn

при системе условий 

 
a11x1 + a12x2 + .... + a1nxn = b1; 

 
am1x1 + am2x2 + ... + amnxn = bm; 

 
x1 >= 0, xn >= 0. 

Система условий может быть представлена и в векторном виде: 

 
A1x1 + A2x2 + .... + Anxn = B, 

где Aj и B – вектор условий и вектор ограничений задачи, соответственно. 

9 

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

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

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

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

Начнем с задачи линейного программирования, линейная 
форма которой содержит только одно переменное: 

 
L = c x, 

а система условий имеет вид 

 
a x < = b (a, b > 0), x >= 0. 

Линейная форма геометрически выражается отрезком прямой 
на оси ординат (рис. 1.1). Переменная величина x геометрически выражается отрезком прямой на оси абсцисс. Искомая область определения рассматриваемой задачи расположена на линии вектора OB, 
что характеризует одномерность задачи. Вектор расположен под углом α = arctg c к оси абсцисс. 

10 

α

b/a
x

L

α

b/a
x

L

O

B

Рис. 1.1. Изменение линейной формы в одномерной задаче 

Линейная форма достигает своих экстремальных (наибольших и наименьших) значений на концах отрезка [0, b/a], на котором 
она определена, согласно условиям задачи. Решение задачи максимизации достигается на правом конце отрезка, а решение задачи минимизации – на его левом конце. 

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

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

 
L = x1 + x2 ----> max 

при условиях 

 
0,6x1 + 1,1x2 <= 900; 

 
0,8x1 + 0,2x2 <= 520; 

 
40x1 + 90x2 <= 70000; 

 
0,72x1 <= 400; 

 
0,225x1 + 0,16x2 <= 200; 

 
x1 >= 0; x2 >= 0. 

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

11 

Наметим область определения линейной формы задачи 
(Рис. 1.2). Поместим в плоскости прямоугольную систему координат 
с осями Ox1 и Ox2 В плоскости проведем прямые 1, 2, 3, 4, 5, описываемые уравнениями 
 
0,6x1 + 1,1x2 = 900; 

 
0,8x1 + 0,2x2 = 520; 

 
40x1 + 90x2 = 70000; 

 
0,72x1 = 400; 

 
0,225x1 + 0,16x2 = 200, 

соответственно. 

x1

x2

0
5

4
3
2

1

S’

M’

S

M

A

B
C
D
E

F

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

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

Линейная форма задачи геометрически изображается с помощью прямой S'M' , уравнение которой L = x1 + x2. 

Прямая S'M' пересекает многоугольник OABCDEF. Для решения задачи необходимо передвигать линию параллельно самой 
себе вверх до достижения предельного положения SM, в котором 
прямая может содержать только граничные точки (вершины) много
12