Практикум по методам оптимизации

ПРАКТИКУМ 
ПО МЕТОДАМ 

ОПТИМИЗАЦИИ 

Учебное пособие

Москва

ВУЗОВСКИЙ УЧЕБНИК

ИНФРА-М

О.А. Сдвижков

2020

Сдвижков О.А.

Практикум по методам оптимизации : учеб. пособие / 

О.А. Сдвижков. — М. : Вузовский учебник : ИНФРА-М, 2020. — 
200 с. + Доп. материалы [Электронный ресурс; Режим доступа: http://
www.znanium.com].

ISBN 978-5-9558-0372-2 (Вузовский учебник)
ISBN 978-5-16-009846-3 (ИНФРА-М, print)
ISBN 978-5-16-101355-7 (ИНФРА-М, online)

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

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

УДК 65.0(076.5)
ББК 65.290.2я7

Материалы, отмеченные знаком 
, 

доступны в электронно-библиотечной системе Znanium.com

С27

ISBN 978-5-9558-0372-2 (Вузовский учебник)
ISBN 978-5-16-009846-3 (ИНФРА-М, print)
ISBN 978-5-16-101355-7 (ИНФРА-М, online)

© Вузовский учебник, 2015

УДК 65.0(076.5)
ББК 
65.290.2я7

 
С27

ФЗ 

№ 436-ФЗ

Издание не подлежит маркировке 
в соответствии с п. 1 ч. 2 ст. 1

ВВедение

Данное учебное пособие подготовлено в Российском государ
ственном университете туризма и сервиса по дисциплине «Математические методы оптимизации решений» учебных планов бакалавров по направлениям 080100.62 «Экономика», 080200.62 «Менеджмент». Основной особенностью пособия является то, что в нем 
рассматриваются не только традиционные методы решения типовых задач, но и современные — информационные, включая режим 
онлайн. 

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

Традиционные методы дополнены сведениями по технологиям 

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

Для решения оптимизационных задач в режиме онлайн сети Ин
тернет, а такой подход является самым рациональным, так как он 
требует от пользователя только ввода начальных данных, обработка 
выполняется автоматически, применяются специально разработанные автором макросы MS Excel [10], размещенные, в частности, на 
сайте http://oas.ucoz.com. 

Вместо этого сайта, созданного в конструкторе Ucoz, можно вос
пользоваться «созданным в блокноте» сайтом http://oas.aiq.ru. Понятно, что ими ресурсы Интернета, поддерживающие онлайн решения задач оптимизации, не ограничиваются. Многие оптимизационные задачи (транспортная, коммивояжера и др.) можно решать 
онлайн и на других сайтах, причем число таких сайтов, как и число 
задач, охватываемых ими, неуклонно растет. 

Главная страница сайта http://oas.ucoz.com показана на рис. 1.

Рис. 1

Гиперссылка Информация о сайте приводит к наименованиям 

поддерживаемых разделов, команда «Математические методы экономики» открывает список поддерживаемых моделей, в том числе 
оптимизационных. Начало списка показано на рис. 2.

Рис. 2

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

Например, гиперссылка Balance вызывает окно (рис. 3).

Рис. 3

Команда «Открыть» открывает книгу MS Excel, содержащую мак
рос и справку по применению, остается следовать указаниям. В частности, после запуска макроса Balance.xls на исполнение появляется 
диалоговое окно (рис. 4).

Рис. 4

Кстати, аналогичным образом применяются программные ре
сурсы сайта http://discmath.ucoz.ru.

В основном макросы разрабатывались в MS Excel 2003, но они 

поддерживаются и в более высоких версиях MS Excel.

Пособие ориентировано на студентов направлений «Экономика» 

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

ГлаВа 1 
линеЙнОе ПРОГРаММиРОВание

1.1.  
ОснОВная задача лП

1. Задачи линейного программирования. Многие экономические 

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

Основной задачей линейного программирования (ОЗЛП) назы
вается задача

z
c
c x
c x
c x
n
n
=
+
+
+
+
→
0
1
1
2
2
...
max,
(1.1)

a x
b

x

ij
j

j

n

i

j

=∑
≤

≥







1

0

,

,

i
m
=1, .
(1.2)

Например, такой является задача

z
x
x
=
+
→
2
3
1
2
max ,
(1.3)

3
2
11

2
9

2
5
0
0

1
2

1
2

1

1
2

x
x

x
x

x
x
x

+
≤

+
≤

≤
≥
≥










,

,

,
,
.

(1.4)

Введением m дополнительных (фиктивных, балансовых) пере
менных xn i
+  задача (1.1, 1.2) приводится к виду, называемому кано
ническим:

z
c
c x
c x
c x
n
n
=
+
+
+
+
→
0
1
1
2
2
...
max,
(1.5)

a x
x
b

x

ij
j

j

n

n i
i

j

=

+
∑
+
=

≥







1

0

,

.

(1.6)

Переменные x j  называются свободными, а переменные xn i
+  — 

базисными. В частности, канонический вид задачи (1.3, 1.4)

z
x
x
=
+
→
2
3
1
2
max,
(1.7)

3
2
11

2
9

2
5

0
0

1
2
3

1
2
4

1
5

1
5

x
x
x

x
x
x

x
x

x
x

+
+
=

+
+
=

+
=

≥
≥










,

,

,

,...,
.

(1.8)

Свободные переменные — x
x
1
2
,
,  базисные переменные — 

x
x
x
3
4
5
,
,
.

Базисным решением ОЗЛП, заданной в виде (1.5, 1.6), называется 

такое решение, в котором свободные переменные равны нулю.

Базисное решение ОЗЛП называется опорным, если в нем базис
ные переменные неотрицательны.

В теории ЛП доказывается, что если экстремум функции z суще
ствует, то он достигается на опорном решении.

Опорное решение ОЗЛП, на котором целевая функция z прини
мает максимальное значение, называется оптимальным планом.

Так как min
max(
)
z
z
= −
−
, то каждая задача ЛП на минимум 

z
c
c x
i
i

i

n

=
+
→

=∑
0

1

min

приводится к задаче на максимум

w
z
c
c x
i
i

i

n

= − = −
−
→

=∑
0

1

max

(поэтому достаточно ограничиться рассмотрением основной задачи 
ЛП). Например, задача

z
x
x
=
+
→
4
6
1
2
min,
(1.9)

3
9

2
8

6
12

0
0

1
2

1
2

1
2

1
2

x
x

x
x

x
x

x
x

+
≥

+
≥

+
≥

≥
≥










,
,
,

,

(1.10)

приводится к задаче

w
z
x
x
= − = −
−
→
4
6
1
2
max,

−
−
≤ −

−
−
≤ −

−
−
≤ −

≥
≥










3
9

2
8

6
12

0
0

1
2

1
2

1
2

1
2

x
x

x
x

x
x

x
x

,
,
,

,
.

Ее канонический вид

w
z
x
x
= − = −
−
→
4
6
1
2
max,
(1.11)

−
−
+
= −

−
−
+
= −

−
−
+
= −

≥
≥

 3
9

2
8

6
12

0
0

1
2
3

1
2
4

1
2
5

1
5

x
x
x

x
x
x

x
x
x

x
x

,
,
,

,...,
.








(1.12)

2. Полные жордановы исключения. Матрица коэффициентов при 

переменных в ограничениях-равенствах (1.5) имеет вид

a a
a

a
a
a

n

n

11
12
1

21
22
2

1 0
0

0 1
0

…
…

…
…

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

a
a
a
m
m
mn
1
2
0 0
1
…
…



















(1.13)

Каждой переменной в ней соответствует свой столбец, базисным 

переменным xn i
+ соответствуют единичные столбцы (все нули, кроме 

одного элемента 1). Однако каждую переменную x j  можно сделать 
базисной вместо переменной xn i
+ , если an i j
+
≠ 0.  Например, если 

a11
0
≠ ,  то можно сделать переменную x1 базисной, исключая из ба
зисных переменных xn+1,  для этого необходимо выполнить следующие преобразования.

Разделить первую строку матрицы (1.13) на a11:

1
1
0
0

0
1
0

12
11
1
11
11

21
22
2

a
a
a
a
a

a
a
a

n

n

/
/
/

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

…
…

…
…

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

a
a
a
m
m
mn
1
2
0
0
1
…
…



















.

Последовательно умножать первую строку на a
a
am
21
31
1
,
,
,
…
 и вы
читать из 2-й, 3-й, …, m-й строки, что приводит к матрице, для которой переменная x1 является базисной:

1
1
0
0

0

12
11
1
11
11

22
21 12
11
2
21 1
11

a
a
a
a
a

a
a a
a
a
a a
a

n

n
n

/
/
/

/
/

…
…

…
−
−
− a
a
21
11
1
0
/

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

…

.....

/
/
/
0
0
1
2
1 12
11
1 1
11
1
11
a
a a
a
a
a a
a
a
a
m
m
mn
m
n
m
−
−
−


















…
… 

.

В общем случае, алгоритм включения в базис переменной xr  и 

исключения из базиса переменной xs  имеет следующий вид.

1. Строка s делится на элемент asr ≠ 0;
2. В столбце r все элементы, кроме asr

н =1,  заменяются нулями 

(исключаются);

3. Все остальные элементы новой матрицы пересчитываются по 

правилу

a
a
a
a
a

a

ij

ij
sr
sj
ir

sr

н =
⋅
−
⋅
.

Этот алгоритм называется алгоритмом полных жордановых исклю
чений, а правило пересчета — правилом прямоугольников, так как элементы числителя правой части являются вершинами прямоугольника:

a
a

a
a

sr
sj

ir
ij

−

−

|
|

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

Например, пусть требуется сделать переменную x1 базисной, ис
ключая ее из 2-го и 3-го уравнений системы:

2
3
6

3
5
6
4
11

4
3
8
5
25

1
2
3
4

1
2
3
4

1
2
3
4

x
x
x
x

x
x
x
x

x
x
x
x

+
+
+
=

+
+
+
=

+
+
+
=







,

,
.


Составляется расчетная таблица:

Т а б л и ц а  1 . 1

bi
x1
x2
x3
x4
К

6
2
1
3
1
13

11
3
5
6
4
29

25
4
3
8
5
45

По правилу прямоугольников элементы первой строки делим 

на 2, во второй строке вместо 11 пишем (
)/
11 2
6 3
2
2
⋅ − ⋅
=
, вместо 3 

ставим 0, вместо 5 пишем (
)/
/
5 2 1 3
2
7 2
⋅ − ⋅
=
и т.д., что приводит к 

следующей таблице:

Т а б л и ц а  1 . 2

bi
x1 
x2
x3
x4
К

3
1
1/2
3/2
1/2
13/2

2
0
7/2
3/2
5/2
19/2

13
0
1
2
3
19

Так как значения контрольного столбца равны суммам остальных 

элементов строк, то расчеты проведены правильно, получили систему

x
x
x
x

x
x
x

x
x
x

1
2
3
4

2
3
4

2
3
4

0 5
1 5
0 5
3

3 5
1 5
2 5
2

2
3
13

+
+
+
=

+
+
=

+
+
=


,
,
,
,

,
,
,
,
.





задачи для самостоятельного решения
1.1.1. Найти по системе ограничений базисное решение (будет 

ли оно опорным?):

x
x

x
x

x
x

x
x

2
4

3
4

1
4

4
5

3
6
3

2
5
4

+
=

+
=

−
=

−
=










,
,
,
.

1.1.2. Привести к основной задаче линейного программирования:
а) z
x
x
=
+
−
→
5
2
3
1
2
max,

2
4

10

2
0
0

1
2

1
2

1

1
2

x
x

x
x

x
x
x

+
≥

+
≤

≥
≥
≥










,
,

,
,
;

б) z
x
x
=
−
+
→
4
2
3
1
2
min,

x
x

x
x

x
x

x
x
x

1
2

1
2

1
2

2

1
2

4
6

3
2
24

10
0
0

+
≥

−
≤

+
≤

≤
≥
≥














,
,

,

,
,
;

в) z
x
x
x
x
=
+
−
−
→
1
2
4
5
2
3
min,