Зенкевич Н.А. Практикум по исследованию операций
Подождите немного. Документ загружается.
Зенкевич Н. А., Губар Е. А.
ПРАКТИКУМ
ПО ИССЛЕДОВАНИЮ ОПЕРАЦИЙ
Учебное пособие для студентов, обучающихся по специальности
”
Прикладная математика и информатика“
Санкт-Петербург
2007 г.
c
° Зенкевич Николай Анатольевич, кандидат физ.-мат. наук, доцент
Губар Елена Алексеевна, кандидат физ.-мат. наук, старший преподаватель, 2007.
Оглавление
1 Линейное программирование 7
1.1 Общая задача линейного программирования . . . . . . . . . . . . . . . . . . 7
1.1.1 Стандартная задача линейного программирования . . . . . . . . . . 8
1.1.2 Каноническая задача линейного программирования . . . . . . . . . 9
1.2 Формализация задачи линейного программирования . . . . . . . . . . . . . 10
1.2.1 Формализация проблемы как задачи ЛП . . . . . . . . . . . . . . . . 10
1.2.2 Пример формализации задачи ЛП . . . . . . . . . . . . . . . . . . . 11
1.2.3 Построение математической модели . . . . . . . . . . . . . . . . . . . 11
1.2.4 Геометрический (графический) способ решения задачи линейного
программирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2.5 Пример графического решения задачи . . . . . . . . . . . . . . . . . 14
1.2.6 Задачи для самостоятельного решения . . . . . . . . . . . . . . . . . 17
1.3 Прямой симплекс-метод для задачи максимизации . . . . . . . . . . . . . . 20
1.3.1 Эквивалентные преобразования . . . . . . . . . . . . . . . . . . . . . 20
1.3.2 Примеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.3.3 Вспомогательные построения симплекс-метода . . . . . . . . . . . . 21
1.3.4 Алгоритм прямого симплекс-метода . . . . . . . . . . . . . . . . . . . 23
1.3.5 Задачи для самостоятельного решения . . . . . . . . . . . . . . . . . 26
1.4 Двухфазный симплекс-метод . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.4.1 Алгоритм двухфазного симплекс-метода. . . . . . . . . . . . . . . . . 28
1.4.2 Задачи для самостоятельного решения . . . . . . . . . . . . . . . . . 31
1.5 Двойственность в линейном программировании . . . . . . . . . . . . . . . . 34
1.6 Двойственный симплекс-метод . . . . . . . . . . . . . . . . . . . . . . . . . . 38
1.6.1 Задачи для самостоятельного решения . . . . . . . . . . . . . . . . . 42
3
4 Оглавление
2 Задачи транспортного типа 45
2.1 Формулировка транспортной задачи . . . . . . . . . . . . . . . . . . . . . . 45
2.2 Каноническая транспортная модель . . . . . . . . . . . . . . . . . . . . . . . 46
2.3 Методы нахождения начального опорного плана . . . . . . . . . . . . . . . 47
2.3.1 Метод северо-западного элемента . . . . . . . . . . . . . . . . . . . . 47
2.3.2 Метод минимального элемента . . . . . . . . . . . . . . . . . . . . . . 48
2.3.3 Приближенный метод Фогеля (ПМФ) . . . . . . . . . . . . . . . . . . 48
2.3.4 Прямая и двойственная транспортная задача . . . . . . . . . . . . . 49
2.3.5 Метод потенциалов решения транспортной задачи . . . . . . . . . . 49
2.4 Примеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
2.5 Задачи для самостоятельного решения . . . . . . . . . . . . . . . . . . . . . 63
2.6 Задача о назначениях . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
2.6.1 Формулировка задачи о простых назначениях. . . . . . . . . . . . . 65
2.6.2 Формулировка задачи об оптимальных назначениях. . . . . . . . . . 65
2.6.3 Математическая формулировка задачи об оптимальных назначениях. 66
2.6.4 Каноническая форма задачи о назначениях . . . . . . . . . . . . . . 66
2.6.5 Двойственная задача об оптимальных назначениях. . . . . . . . . . 66
2.6.6 Алгоритм решения задачи. . . . . . . . . . . . . . . . . . . . . . . . . 67
2.6.7 Задача о назначениях. Венгерский метод. . . . . . . . . . . . . . . . 70
2.6.8 Задачи для самостоятельного решения . . . . . . . . . . . . . . . . . 73
3 Сети 75
3.1 Задача о максимальном потоке . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.1.1 Основные определения . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.1.2 Постановка задачи. Свойства. . . . . . . . . . . . . . . . . . . . . . . 77
3.1.3 Алгоритм нахождения максимального потока в сети. . . . . . . . . . 78
3.1.4 Пример решения задачи о максимальном потоке. . . . . . . . . . . . 79
3.2 Задача минимизации сети . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
3.3 Задачи для самостоятельного решения . . . . . . . . . . . . . . . . . . . . . 87
4 Дискретное программирование 89
4.1 Схема метода ветвей и границ . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.1.1 Алгоритм метода ветвей и границ в задаче линейного целочислен-
ного программирования . . . . . . . . . . . . . . . . . . . . . . . . . . 91
Оглавление 5
4.1.2 Пример . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
4.1.3 Задачи для самостоятельного решения . . . . . . . . . . . . . . . . . 98
4.2 Задача о коммивояжере . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
4.2.1 Алгоритм . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
4.2.2 Пример 4.2.1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
4.2.3 Задачи для самостоятельного решения . . . . . . . . . . . . . . . . . 109
5 Динамическое программирование 113
5.1 Многошаговый управляемый детерминированный процесс принятия реше-
ния. Уравнение Беллмана . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
5.2 Общая схема метода . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
5.3 Задача распределения капиталовложений . . . . . . . . . . . . . . . . . . . 118
5.4 Задача о загрузке . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
5.5 Задача календарного планирования трудовых ресурсов . . . . . . . . . . . 124
5.6 Задача о кратчайшем пути . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
5.7 Задача о двух станках . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
5.7.1 Алгоритм решения задачи о двух станках. . . . . . . . . . . . . . . . 130
5.7.2 Пример . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
5.8 Задачи для самостоятельного решения . . . . . . . . . . . . . . . . . . . . . 132
6 Использование пакетов прикладных программ 135
6.1 Решение оптимизационных задач средствами Excel . . . . . . . . . . . . . . 135
6.1.1 Задача линейного программирования . . . . . . . . . . . . . . . . . . 135
6.1.2 Реализация математической модели в табличной форме . . . . . . . 136
6.1.3 Транспортная задача . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
6.1.4 Решение транспортной задачи средствами Excel . . . . . . . . . . . . 142
6.2 Решение оптимизационных задач средствами LINGO . . . . . . . . . . . . . 146
6.2.1 Начальные сведения о пакете LINGO . . . . . . . . . . . . . . . . . . 147
6.2.2 Первый способ решения задачи ЛП в LINGO . . . . . . . . . . . . . 147
6.2.3 Второй способ решения задачи ЛП в LINGO . . . . . . . . . . . . . 151
6.2.4 Транспортная задача . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
6.2.5 Решение транспортной задачи при помощи пакета LINGO . . . . . . 155
6.2.6 Задача коммивояжера . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
6.2.7 Решение модели о минимизации сети . . . . . . . . . . . . . . . . . . 161
6 Оглавление
6.3 Решение оптимизационных задач с использованием Maple . . . . . . . . . . 163
Глава 1
Линейное программирование
1.1 Общая задача линейного программирования
С математической точки зрения задача линейного программирования (ЛП) – это задача
нахождения наибольшего (наименьшего) значения линейной функции многих перемен-
ных при линейных ограничениях типа равенств (или неравенств), когда на переменные
есть (или нет) ограничения на знак. Поэтому общая задача ЛП максимизации может
быть записана в виде:
max z = max(c
1
x
1
+ c
2
x
2
+ . . . + c
n
x
n
);
(1.1.1)
a
i1
x
1
+ a
i2
x
2
+ . . . + a
in
x
n
≤ b
i
, i =
1, k;
a
i1
x
1
+ a
i2
x
2
+ . . . + a
in
x
n
= b
i
, i = k + 1, m;
x
j
≥ 0, j = 1, p, p ≤ n,
x
j
≥≤ 0, j = p + 1, n
(1.1.2)
Общая задача минимизации имеет следующий вид:
min z = min(c
1
x
1
+ c
2
x
2
+ . . . + c
n
x
n
);
(1.1.3)
a
i1
x
1
+ a
i2
x
2
+ . . . + a
in
x
n
≥ b
i
, i =
1, k;
a
i1
x
1
+ a
i2
x
2
+ . . . + a
in
x
n
= b
i
, i = k + 1, m;
x
j
≥ 0, j =
1, p, p ≤ n,
x
j
≥≤ 0, j = p + 1, n.
(1.1.4)
7
8 Глава 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
Здесь
x
i
− переменные задачи;
z = c
1
x
1
+ c
2
x
2
+ . . . + c
n
x
n
− целевая функция;
a
i1
x
1
+ a
i2
x
2
+ . . . + a
in
x
n
≥ b
i
a
i1
x
1
+ a
i2
x
2
+ . . . + a
in
x
n
≤ b
i
− ограничение типа неравенства;
a
i1
x
1
+ a
i2
x
2
+ . . . + a
in
x
n
= b
i
− ограничение типа равенства;
x
j
≥ 0 − условие неотрицательности переменной x
j
(стандартное ограничение
на знак переменной);
c
j
, a
ij
, b
i
− заданные параметры.
1.1.1 Стандартная задача линейного программирования
Если в задаче максимизации ЛП все ограничения являются неравенствами типа ≤, а
на все переменные наложено стандартное ограничение на знак ≥ 0, то такая задача ЛП
называется стандартной задачей максимизации:
max z = max(c
1
x
1
+ c
2
x
2
+ . . . + c
n
x
n
);
(1.1.5)
a
i1
x
1
+ a
i2
x
2
+ . . . + a
in
x
n
≤ b
i
, i =
1, m;
x
j
≥ 0, j = 1, n.
(1.1.6)
Часто используется стандартная экономическая интерпретация для задачи макси-
мизации. Фирма производит n видов продуктов (j – индекс вида продукта), исполь-
зуя при производстве m типов ресурсов (i – индекс типа ресурса), c
j
– прибыль от
реализации единицы j-ого вида продукта; a
ij
– потребности в ресурсе (i-ого типа для
создания единицы продукта j-ого вида), b
i
– запас ресурса i-го типа в плановый пе-
риод, X = (x
1
, x
2
, ..., x
n
) – план выпуска продукции в заданный период. Тогда задача
(1.1.5), (1.1.6) – может быть интерпретирована как задача нахождения плана произ-
водства X
∗
= (x
∗
1
, . . . , x
∗
n
), максимизирующего суммарную прибыль от реализации всех
видов продукции в плановый период при ограниченных запасах ресурсов.
Если в задаче минимизации ЛП все ограничения являются неравенствами типа ≥,
а на все переменные наложено стандартное ограничение на знак ≥ 0, то такая задача
называется стандартной задачей минимизации:
1.1. ОБЩАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 9
min z = min(c
1
x
1
+ c
2
x
2
+ . . . + c
n
x
n
)
(1.1.7)
a
i1
x
1
+ a
i2
x
2
+ . . . + a
in
x
n
≥ b
i
, i =
1, m
x
j
≥ 0, j =
1, n
(1.1.8)
Здесь возможна следующая интерпретация пусть X = (x
1
, x
2
, ..., x
n
) - план выпуска
продукции (x
j
– объем выпуска продукции j-го вида). Вся произведенная продукция про-
дается на m рынках. Обозначим через b
i
– м инимальные общие потребности в продуктах
i-го рынка, a
ij
– часть продукции j-го вида, продаваемая на i-ом рынке, c
j
– удельные
затраты на производство продукции j-го вида. Тогда задача (1.1.7), (1.1.8) – может быть
проинтерпретирована как задача нахождения плана производства X
∗
= (x
∗
1
, ..., x
∗
n
), ми-
нимизирующего общие затраты при рыночных ограничениях на поставки продукции.
1.1.2 Каноническая задача линейного программирования
Канонической называется такая задача ЛП, которая состоит в нахождении максимально-
го или минимального значения целевой функции при условии, что все ограничения явля-
ются равенствами, а на все переменные наложено стандартное ограничение
на знак ≥ 0.
Каноническая задача линейного программирования имеет вид:
а) для задачи максимизации:
max z = max(c
1
x
1
+ c
2
x
2
+ . . . + c
n
x
n
);
(1.1.9)
a
i1
x
1
+ a
i2
x
2
+ . . . + a
in
x
n
= b
i
, i =
1, m;
x
j
≥ 0, j = 1, n.
(1.1.10)
а) для задачи минимизации:
min z = min(c
1
x
1
+ c
2
x
2
+ . . . + c
n
x
n
);
(1.1.11)
a
i1
x
1
+ a
i2
x
2
+ . . . + a
in
x
n
= b
i
, i =
1, m;
x
j
≥ 0, j = 1, n.
(1.1.12)
Определение 1.1.1 Вектор X = (x
1
, x
2
, ..., x
n
), удовлетворяющий всем ограничениям
задачи ЛП, называется допустимым решением или планом этой задачи ЛП. Множе-
ство всех допустимых решений задачи ЛП будем обозначать через M, M ⊂ R
n
.
10 Глава 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
Определение 1.1.2 Допустимое решение X
∗
= (x
∗
1
, x
∗
2
, ..., x
∗
n
) задачи ЛП, на котором
целевая функция задачи достигает наибольшее (наименьшее) значение, называется оп-
тимальным решением этой задачи ЛП.
Определение 1.1.3 Число z
∗
= max
X∈M
CX (z
∗
= min
X∈M
CX) будем называть значением
задачи максимизации (минимизации) ЛП, здесь под CX понимается скалярное произ-
ведение векторов C = (c
1
, . . . , c
n
) и X = (x
1
, . . . , x
n
).
Определение 1.1.4 Решить задачу ЛП – означает найти оптимальное решение
X
∗
∈ M этой задачи и ее значение z
∗
(z
∗
).
1.2 Формализация задачи линейного программирова-
ния
Одной из проблем применения методов линейного программирования является коррект-
ное написание математической постановки задачи по ее описательной модели (форма-
лизация задачи).
1.2.1 Формализация проблемы как задачи ЛП
• Понять проблему, составить описательную модель задачи;
• Идентифицировать основные переменные задачи;
• Выбрать некоторую количественную меру эффективности для целевой функции;
• Представить эту меру эффективности как линейную функцию относительно основ-
ных переменных;
• Идентифицировать и представить все ограничения как линейные выражения от-
носительно основных переменных;
• Собрать количественные данные или сделать соответствующие оценки для всех
параметров модели.