Текстовые фрагменты публикации
ПРАКТИКУМ
ПО МЕТОДАМ
ОПТИМИЗАЦИИ
Учебное пособие
Москва
ВУЗОВСКИЙ УЧЕБНИК
ИНФРА-М
2015
О.А. Сдвижков
Сдвижков О.А.
Практикум по методам оптимизации. — М.: Вузовский учебник:
ИНФРА-М, 2015. — 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.290.2я7
Материалы, отмеченные знаком
, доступны
в электронно-библиотечной системе znanium
С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
ВВедение
Данное учебное пособие подготовлено в Российском государ-
ственном университете туризма и сервиса по дисциплине «Мате-
матические методы оптимизации решений» учебных планов бака-
лавров по направлениям 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,
Фрагмент текстового слоя документа размещен для индексирующих роботов.
Для полноценной работы с документом, пожалуйста, перейдите в
ридер.
