- •«Математические модели и методы исследования операций» Аснина а.Я., Аснина н.Г.
- •Тема 1. Оптимизация на сетях.
- •Построение математической модели.
- •Метод потенциалов для сетевой транспортной задачи.
- •Тема 2. Сети без контуров. Свойства сетей без контуров.
- •Задачи о кратчайшем и критическом пути.
- •Метод решения задач о кратчайшем и критическом пути.
- •Тема 3. Задачи, сводящиеся к задачам о кратчайшем и критическом пути. Задача о замене оборудования.
- •Задача оптимизации временной структуры проекта.
- •Тема 4. Теория расписаний. Общие положения
- •Задача о назначениях
- •Самостоятельная работа.
- •Система конвейерного типа с двумя приборами
- •Конвейерная система с тремя и более приборами
- •Самостоятельная работа.
- •Библиографический список
Задача о назначениях
Постановка задачи:
Вербальная модель
Пусть имеется n – приборов (станков) и n – требований (деталей). Каждое требование может обслуживаться (каждая деталь может обрабатываться) на любом из приборов.
– длительность
обслуживания i-го
требования на приборе j.
Требуется распределить все требования по приборам так, чтобы на каждый прибор попало ровно одно требование и, чтобы среднее время обслуживания было минимальным.
Математическая модель
Введем
,
если i-е
требование обслуживается j-м
прибором;
,
если i-е
требование не обслуживается.
Ограничения:
,
(4.2)
каждое требование обслуживается ровно одним прибором.
,
(4.3)
каждый прибор обслуживает ровно одно требование.
Целевая функция имеет вид
.
Замечание.
Так как коэффициент
не влияет на положение оптимальной
точки, то целевую функцию можно заменить
на функцию
,
(4.4)
где
.
Способ задания задачи о назначениях и ее анализ.
Как
видно из математической модели
(4.1)-(4.4), задача о назначениях является
транспортной задачей с квадратной
матрицей
,
в которой для всех i
и j,
,
поэтому, чтобы задать задачу о назначениях,
достаточно только задать квадратную
матрицу С.
Заметим,
что задача о назначениях является
транспортной задачей, если ограничение
(4.2) заменить ограничением
.
Возникает вопрос, если исправленную
задачу решить методом потенциалов, то
будет ли решение удовлетворять
ограничению (4.2).
Однако
известно, что транспортная задача с
целыми правыми частями имеет целочисленное
решение. Правые части задачи о назначениях
равны единице, то есть целым числам,
значит, и все
также целые числа, при этом из (4.2)-(4.3)
следует, что все
,
следовательно, они могут принимать
значения только ноль и единица.
Отсюда любое допустимое решение задачи о назначениях может быть представлено в виде квадратной матрицы Х, в которой в каждом столбце и каждой строке имеется по одной единице. Все остальные элементы матрицы равны нулю. Например, матрица Х может иметь вид (рис. 4.1).
Х= |
|
1 |
|
|
1 |
|
|
|
|
|
|
1 |
|
|
|
|
|
1 |
Рис. 4.1
То
есть матрица Х
имеет ровно n
ненулевых элементов. Если решать задачу
методом потенциалов, то базисное решение
х
должно иметь (2n-1)
базисную компоненту, и так как число
единиц равно n,
то базисное решение должно быть дополнено
(n-1)
нулем. Отсюда следует, что базисное
решение является сильно вырожденным,
а это является существенной помехой
для использования метода потенциалов
(
часто будет равно нулю). Поэтому для
решения задачи о назначениях может
быть предложен другой метод, существенно
использующий тот факт, что ненулевые
компоненты решения равны единице. В
этом случае матрицу Х
можно вообще не задавать, а на матрице
С
пометить (крышкой) элементы, которым
соответствуют единичные компоненты
матрицы Х.
Тогда значение целевой функции будет
равно
.
Рассмотрим свойства матрицы С.
Свойство
1.
Если из всех элементов одной строки
или одного столбца матрицы С вычесть
одно и то же число
,
то оптимальное решение новой задачи
будет совпадать с оптимальным решением
исходной задачи, а оптимальное значение
целевой функции новой задачи уменьшится
по сравнению с оптимальным значением
целевой функции исходной задачи на
величину
:
.
Свойство
2.
Без ограничения общности мы можем
считать, что
.
Свойство
3.
Пусть все
и существуют
,
тогда, если удается найти допустимое
решение
такое, что все
соответствуют
,
то полученное допустимое решение
оптимально.
Определение . Пусть все элементы матрицы С больше или равны нулю и существуют . Нули матрицы С называются независимыми, если они стоят в разных строках и столбцах матрицы С.
Так как любое допустимое решение задачи о назначениях имеет n единиц, стоящих в разных строках и столбцах, то, как следует из Свойства 3, для того, чтобы могло быть найдено оптимальное решение задачи о назначениях, надо, чтобы матрица С имела n независимых нулей. Отсюда следует, что для нахождения оптимального решения необходимо воспользовавшись свойством 1, путем вычитания из строк и столбцов некоторых чисел, получить новую матрицу С, имеющую n независимых нулей. Этот метод называется Венгерским методом.
Венгерский метод.
Венгерский метод состоит из четырех этапов:
Этап 1. Приведение матрицы.
Этап
2.
Подсчет
–
числа независимых нулей.
Этап 3. Преобразование матрицы С с целью получения новых нулей.
Этап 4. Поиск независимых нулей и получение оптимального решения.
Блок-схема последовательности выполнения этапов Венгерского метода приведена на рис. 4.2
Рис.4.2. Блок-схема выполнения этапов Венгерского метода
Рассмотрим каждый этап подробно.
Этап 1. Приведение матрицы
Определение. Матрица С называется приведенной, если она имеет в каждой строке и в каждом столбце, по крайней мере, один ноль.
Матрица С легко приводится с помощью первого свойства, то есть вычитанием из строк и столбцов минимального элемента.
Алгоритм выполнения первого этапа
Шаг
0.
.
Шаг
1.
В каждой строке определяется
.
Шаг
2.
Для всех
полагают
.
Шаг
3.
.
Шаг
4.
Для каждого j
полагают
.
Шаг
5.
Для всех
полагают
.
Шаг
6.
.
Шаг 7. Переход ко второму этапу.
Этап 2. Подсчет k – числа независимых нулей
Пусть мы хотим вычеркнуть независимые нули горизонтальными или вертикальными линиями. Заметим, что никакие два независимых нуля нельзя вычеркнуть одной горизонтальной или вертикальной линией, так как они стоят в разных столбцах и строках. То есть если мы хотим вычеркнуть все независимые нули горизонтальными и (или) вертикальными линиями, то число этих линий будет совпадать с числом независимых нулей. Отсюда следует, что для того чтобы определить, сколько независимых нулей имеет матрица С, достаточно все нули матрицы С вычеркнуть минимально возможным числом горизонтальных и (или) вертикальных линий.
Рассмотрим следующую матрицу (рис. 4.3):
0 |
0 |
0 |
0 |
0 |
|
|
|
0 |
|
|
|
0 |
|
|
|
Рис. 4.3
Эта матрица является приведенной, так как в каждой строке и в каждом столбце имеется, по крайней мере, один ноль. При этом все нули могут быть вычеркнутыми двумя линиями: вертикальной и горизонтальной, - то есть эта матрица имеет всего два независимых нуля (рис. 4.4)
0 |
0 |
0 |
0 |
0 |
|
|
|
0 |
|
|
|
0 |
|
|
|
Рис. 4.4
Отсюда сформулируем алгоритм второго этапа.
Алгоритм выполнения второго этапа
Шаг 1. Отыскивается строка, содержащая один ноль. Этот ноль вычеркивается вертикальной линией. Процесс продолжается, пока может быть найдена строка, содержащая один ноль.
Шаг 2. Отыскивается столбец, содержащий один ноль. Этот ноль вычеркивается горизонтальной линией. Процесс продолжается, пока может быть найден столбец, содержащий один ноль.
Шаг 3. Просматриваются невычеркнутые элементы матрицы С.
Шаг
4.
Если среди невычеркнутых
имеются
,
то переход
к Шагу 7.
Иначе Шаг 5.
Шаг 5. Подсчитывается число линий k.
Шаг
6. Если
,
то переход к четвертому этапу. Если
,
то переход к третьему этапу.
Шаг
7.
Просматриваются строки матрицы С
и подсчитывается
,
где
– число невычеркнутых нулей в i-й
строке (
).
Шаг
8.
Просматриваются столбцы матрицы С
и подсчитывается
,
где
– число невычеркнутых нулей в j-м
столбце.
Шаг
9.
Если
,
то выбирается строка, содержащая
нулей, и все нули вычеркиваются
вертикальными линиями. Переход к Шагу
1.
Шаг
10.
Если
,
то выбирается столбец, содержащий
,
невычеркнутых нулей и все нули
вычеркиваются горизонтальными линиями.
Переход к Шагу
2.
Замечание. В случае выхода на восьмой, девятый или десятые шаги, алгоритм, к сожалению, не гарантирует получение минимального числа линий, так как эти шаги являются эвристическими. Студенты могут попробовать предложить свои подходы к вычеркиванию нулей для случаев, когда их более одного в строке или столбце.
Этап 3. Преобразование матрицы С с целью получения новых нулей
Третий
этап осуществляется, если полученное
на втором этапе число независимых нулей
недостаточно, поэтому необходимо
преобразовать матрицу так, чтобы
получить новые нули. Пометим через
те элементы матрицы С,
которые вычеркнуты одной линией, через
- те элементы, которые вычеркнуты
одновременно горизонтальной и
вертикальной линиями, невычеркнутые
элементы
помечать не будем.
Алгоритм выполнения третьего этапа
Шаг
1.
Найдем
(из невычеркнутых
).
Шаг 2. Элементы матрицы С преобразуются по следующему правилу:
(для
невычеркнутых),
(для
вычеркнутых одной линией),
(для
вычеркнутых одновременно двумя линиями).
Шаг
3.
.
Шаг 4. Переход ко второму этапу.
???Задание для самостоятельной работы:
Показать,
что приведенный алгоритм есть формализация
преобразования матрицы с помощью (
)
шагов, основанных на первом свойстве
матрицы С.
Этап 4. Поиск независимых нулей и получение оптимального решения
Алгоритм четвертого этапа подобен алгоритму второго этапа, однако имеет некоторые модификации.
Алгоритм выполнения четвертого этапа.
Шаг
1.
В матрице размера (
)
помечаются места всех нулей.
Шаг
2.
.
Шаг
3.
Отыскивается строка, содержащая один
ноль. Этот ноль выделяется, а соответствующие
строка и столбец вычеркиваются.
.
(Процесс продолжается пока существует
строка, содержащая один ноль.)
Шаг
4.
Если
,
то переход к Шагу
11. Иначе Шаг
5.
Шаг 5. Отыскивается столбец, содержащий один ноль. Этот ноль выделяется, а соответствующие строка и столбец вычеркиваются. . (Процесс продолжается пока существует столбец, содержащий один ноль.)
Шаг 6. Если , то переход к Шагу 11. Иначе Шаг 7.
Шаг 7. Просматриваются строки и определяется – число невычеркнутых нулей в i-й строке.
Шаг 8. Просматриваются строки и определяется – число невычеркнутых нулей в j-м столбце.
Шаг
9.
Если
,
то выбирается строка, содержащая
нулей, один из нулей выделяется, а строка
и столбец вычеркиваются.
.
Переход к Шагу 3.
Шаг
10.
Если
,
то выбирается столбец, содержащий
нулей, один из нулей выделяется, а строка
и столбец вычеркиваются.
.
Переход к Шагу 3.
Шаг
11.
На исходной матрице С
помечаются элементы
соответствующие помеченным нулям.
Шаг 12. Вычисляется целевая функция
.
Шаг
13.
Сравнивается
и S.
Эти значения должны совпасть. Проверяется
выполнение равенство
= S
Пример 4.1 Дана матрица С (рис. 4.5). Решить задачу о назначениях.
3 |
6 |
|
8 |
10 |
15 |
|
8 |
9 |
10 |
12 |
16 |
2 |
|
10 |
12 |
14 |
15 |
5 |
6 |
9 |
10 |
10 |
|
1 |
2 |
3 |
|
5 |
6 |
5 |
6 |
7 |
9 |
|
12 |
Рис. 4.5
Этап 1
Шаг 0. S=0.
Шаг 1 (рис. 4.6).
|
|
|
|
|
|
|
3 |
6 |
|
8 |
10 |
15 |
3 |
|
8 |
9 |
10 |
12 |
16 |
4 |
2 |
|
10 |
12 |
14 |
15 |
2 |
5 |
6 |
9 |
10 |
10 |
|
5 |
1 |
2 |
3 |
|
5 |
6 |
1 |
5 |
6 |
7 |
9 |
|
12 |
5 |
Рис.4.6
Шаг 2. Из строк матрицы вычитаем соответствующее (рис. 4.7)
0 |
3 |
1 |
5 |
7 |
12 |
0 |
4 |
5 |
6 |
8 |
12 |
0 |
2 |
8 |
10 |
12 |
13 |
0 |
1 |
4 |
5 |
5 |
6 |
0 |
1 |
2 |
3 |
4 |
5 |
0 |
1 |
2 |
4 |
5 |
7 |
Рис. 4.7
Шаг 3. S=0+20=20.
Шаг 4 (рис. 4.8).
|
0 |
3 |
1 |
5 |
7 |
12 |
|
0 |
4 |
5 |
6 |
8 |
12 |
|
0 |
2 |
8 |
10 |
12 |
13 |
|
0 |
1 |
4 |
5 |
5 |
6 |
|
0 |
1 |
2 |
3 |
4 |
5 |
|
0 |
1 |
2 |
4 |
5 |
7 |
|
0 |
1 |
1 |
3 |
4 |
5 |
Рис. 4.8
Шаг 5. Из каждого столбца вычитаем соответствующее (рис. 4.9)
0 |
2 |
0 |
2 |
3 |
7 |
0 |
3 |
4 |
3 |
4 |
7 |
0 |
1 |
7 |
7 |
8 |
6 |
0 |
0 |
3 |
2 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
2 |
Рис.4.9
Шаг 6. S=20+0+1+1+3+4+5=34.
Этап 2
Подсчет k – числа независимых нулей (рис. 4.10)
0 |
2 |
0 |
2 |
3 |
7 |
0 |
3 |
4 |
3 |
4 |
7 |
0 |
1 |
7 |
7 |
8 |
6 |
0 |
0 |
3 |
2 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
2 |
Рис. 4.10
переход
к Этапу 3.
Этап 3
Шаг 1. с=1.
Шаг 2. Элементы матрицы С (рис. 4.10)преобразуются по следующему правилу:
(для невычеркнутых),
(для вычеркнутых одной линией),
(для вычеркнутых одновременно двумя линиями).
0 |
2 |
0 |
1 |
2 |
6 |
0 |
3 |
4 |
2 |
3 |
6 |
0 |
1 |
7 |
6 |
7 |
5 |
0 |
0 |
3 |
1 |
0 |
0 |
1 |
1 |
2 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
Рис.4.11
Шаг
3.
.
Переход к этапу 2.
Этап 2
Подсчет k – числа независимых нулей (рис. 4.12)
0 |
2 |
0 |
1 |
2 |
6 |
0 |
3 |
4 |
2 |
3 |
6 |
0 |
1 |
7 |
6 |
7 |
5 |
0 |
0 |
3 |
1 |
0 |
0 |
1 |
1 |
2 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
Рис.4.12
.
Выбираем столбец.
.
Переход к этапу 3.
Шаг 1. с=1.
Шаг 2. Аналогично предыдущей итерации (рис. 4.13).
0 |
1 |
0 |
0 |
1 |
5 |
0 |
2 |
4 |
1 |
2 |
5 |
0 |
0 |
7 |
5 |
6 |
4 |
1 |
0 |
4 |
1 |
0 |
0 |
2 |
1 |
3 |
0 |
0 |
0 |
1 |
0 |
2 |
0 |
0 |
1 |
Рис. 4.13
Шаг
3.
.
Переход к этапу 2 (рис. 4.14).
0 |
1 |
0 |
0 |
1 |
5 |
0 |
2 |
4 |
1 |
2 |
5 |
0 |
0 |
7 |
5 |
6 |
4 |
1 |
0 |
4 |
1 |
0 |
0 |
2 |
1 |
3 |
0 |
0 |
0 |
1 |
0 |
2 |
0 |
0 |
1 |
Рис . 4.14
.
Переход к этапу 4 (рис. 4.15).
0 |
|
|
0 |
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
0 |
|
|
0 |
|
|
|
|
|
0 |
0 |
|
0 |
|
0 |
|
|
Рис. 4.15
Переносим места выделенных нулей на исходную матрицу С. Получаем
.
