Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

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

Покупка
Основная коллекция
Артикул: 280900.06.01
Доступ онлайн
от 300 ₽
В корзину
Частному лицу
Бумажная книга
1 513 ₽
Купить
Купить в составе основной коллекции от 1 490 ₽
В учебное пособие вошли задачи линейного программирования, динамического программирования, оптимизации на графах, управления запасами, теории массового обслуживания и теории игр. Приведены постановки основных задач, их математические модели, алгоритмы решений и образцы решения типовых задач. По всем темам есть задания для самостоятельного решения и ответы. Главы заканчиваются контрольными заданиями, содержащими параметры, которые можно использовать для получения индивидуальных заданий. Традиционные методы решений дополнены информационными технологиями, включая режим онлайн, с помощью специально разработанных макросов MS Excel, загруженных на сайты автора. Пособие ориентировано на студентов направлений «Экономика» и «Менеджмент», но будет полезно студентам и других направлений, на которых изучаются математические методы, применяемые в экономике, а также всем, кто интересуется информационными технологиями обработки экономических данных.

Практикум по методам оптимизации: Краткий обзор для студентов и специалистов

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

Линейное программирование: Основы и методы решения

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

Оптимизация на графах: Алгоритмы и приложения

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

Динамическое программирование: Решение многошаговых задач

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

Системы массового обслуживания: Анализ и оптимизация

Четвертая глава посвящена системам массового обслуживания (СМО). Рассматриваются основные понятия СМО, включая каналы обслуживания, заявки, интенсивность потока заявок и интенсивность обслуживания. Рассматриваются одноканальные и многоканальные закрытые и открытые СМО, а также методы расчета их характеристик, таких как финальные вероятности, пропускная способность, среднее число заявок в системе и среднее время ожидания.

Оптимизация запасов: Формула Уилсона и другие методы

Пятая глава посвящена оптимизации запасов. Рассматривается формула Уилсона для определения оптимального объема заказа, а также методы учета дефицита и разрывных цен.

Матричные игры: Теория и приложения

Шестая глава посвящена матричным играм. Рассматриваются основные понятия теории игр, включая платежную матрицу, максиминные и минимаксные стратегии, седловую точку и цену игры. Рассматриваются методы решения игр 2 × 2, а также игры 2 × n и m × 2. Также рассматривается сведение задач теории игр к задачам линейного программирования и применение надстройки "Поиск решения" для их решения.

Текст подготовлен языковой моделью и может содержать неточности.

187

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

Сдвижков, О. А. Практикум по методам оптимизации : учебное пособие / О.А. Сдвижков. — Москва : Вузовский учебник : ИНФРА-М, 2022. — 200 с. + Доп. материалы [Электронный ресурс]. - ISBN 978-5-9558-0372-2. - Текст : электронный. - URL: https://znanium.ru/catalog/product/1852206 (дата обращения: 19.11.2026). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов
ПРАКТИКУМ 
ПО МЕТОДАМ 
ОПТИМИЗАЦИИ 
 
 Учебное пособие
Москва
ВУЗОВСКИЙ УЧЕБНИК
ИНФРА-М
2022
О.А. Сдвижков


Сдвижков О.А. 
Практикум по методам оптимизации : учебное пособие / 
О.А. Сдвижков. — Москва : Вузовский учебник : ИНФРА-М, 2022. 
— 200 с. + Доп. материалы [Электронный ресурс].
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. Задачи линейного программирования. Многие экономические 
задачи приводят к задачам, называемым задачами линейного программирования, в которых надо найти максимум (минимум) линейной функции, называемой целевой функцией, при линейных ограничениях. 
Основной задачей линейного программирования (ОЗЛП) называется задача
	
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)


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,


Доступ онлайн
от 300 ₽
В корзину
Частному лицу
Бумажная книга
1 513 ₽
Купить
Купить в составе основной коллекции от 1 490 ₽