Методические указания по курсовой работе для студентов специальности 22. 02 Автоматизированные системы (стр. 12 из 13)

Будем выполнять действия в такой последовательности:

а) пометим символом (§) все те строки, которые не содержат ни одного подчеркнутого двойной чертой нуля;

б) отметим каждый столбец, который содержит вычеркнутый нуль, хотя бы в одной из помеченных строк;

в) отметим каждую строку, которая имеет подчеркнутый двойной чертой нуль, хотя бы в одном из помеченных столбцов;

г) будем повторять поочередно (б) и (в) до тех пор, пока не останется строк или столбцов, которые еще можно пометить.

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

В нашем примере помечена строка 1; столбцов, которые следовало бы отметить, нет.

Таблица 5.8

1	2	3	4	5
1	13	7	0,5	0,5	6,5	§
2	11.5	8,5	2	0	5
3	7,5	7,5	6	6	0
4	0	0	5,5	12,5	7,5
5	8,5	1,5	0	7	12

ЭТАП 4. ЗАВЕРШЕНИЕ ЭТАПА 3

Отметим заливкой каждую непомеченную строку и каждый помеченный столбец. Это даст нам минимальное число строк и столбцов, которые содержат все перечеркнутые или подчеркнутые двойной чертой нули. В рассматриваемом примере необходимо отметить заливкой строки 2,3,4,5 и не отмечать заливкой столбцов.

Таблица 5.9

1	2	3	4	5
1	13	7	0,5	0,5	6,5	§
2	11,5	8,5	2	0	5
3	7,5	7,5	6	6	0
4	0	0	5,5	12,5	7,5
5	8,5	1,5	0	7	12

ЭТАП 5. ПЕРЕМЕЩЕНИЕ НЕКОТОРЫХ НУЛЕЙ

Рассмотрим ту часть таблицы, которая состоит из неотмеченных заливкой элементов, и возьмем наименьшее число в ней. Вычтем это число из элементов неотмеченных заливкой столбцов и прибавим к элементам отмеченных заливкой строк.

Отметим, что это можно сделать, исходя из основной идеи венгерского метода, согласно которой оптимальное решение задачи не нарушается при уменьшении (или увеличении всех элементов

строки таблицы (или ее столбца) на одну и ту же величину .

В рассматриваемом примере по-прежнему неотмеченными заливкой элементами являются элементы строки 1; наименьший элемент этой строки равен 0,5. Поэтому вычтем 0,5 из всех элементов столбцов 1,2,3,4,5 и прибавим 0,5 к элементам строк 2,3,4,5. Если формально рассмотреть эти действия, т.е. вычитание и сложение, то следует отметить, что фактически выполнено вычитание 0,5 из элементов строки 1. Тем самым получим таблицу 5.10.

Таблица 5.10

1	2	3	4	5
1	12,5	6,5	0	0	6
2	11,5	8,5	2	0	5
3	7,5	7,5	6	6	0
4	0	0	5,5	12,5	7,5
5	8,5	1,5	0	7	12

ЭТАП 6. ПОЛУЧЕНИЕ ОПТИМАЛЬНОГО РЕШЕНИЯ ИЛИ ВЫПОЛНЕНИЕ ОЧЕРЕДНОГО ШАГА

Будем в новой, полученной на этапе 5, таблице, которая содержит числа

, искать оптимальное решение, как это представлено в описании этапа 2. Если при этом получим оптимальное решение, то процесс заканчивается. Если это не так, то повторим этапы 3,4 и 5. Затем, при необходимости, вернемся к этому этапу еще раз.

Повторим этап 2 в рассматриваемом примере получим таблицу 5.11.

Таблица 5.11

1	2	3	4	5
1	12,5	6,5	0	0	6	§
2	11,5	8,5	2	0	5	§
3	7,5	7,5	6	6	0
4	0	0	5,5	12,5	7,5
5	8,5	1,5	0	7	12	§
§	§

Таблица 5.11 содержит новые перечеркнутые и подчеркнутые двойной чертой нули. И так как мы получили четыре подчеркнутых двойной чертой нуля, количество которых не равно размерности нашей таблицы, то переходим к этапу 3.

Преследуя учебные цели, опишем более или менее подробно последующие поэтапные действия. Пометим символом (§) строку 1, как строку, которая не содержит ни одного подчеркнутого двойной чертой нуля. Отметим символами (§) столбцы 3 и 4, каждый из которых содержит перечеркнутый нуль в помеченной строке 1. Отметим строки 2 и 5, как строки, каждая из которых имеет подчеркнутый двойной чертой нуль, в каждом из помеченных столбцов.

Отметим заливкой каждую непомеченную строку и каждый помеченный столбец, т.е. в нашем случае это строки 3 и 4, а столбцы также 3 и 4, но это не более чем совпадение.

Рассмотрим часть таблицы, которая неотмечена заливкой и возьмем наименьшее в ней, т.е. здесь 1.5 и вычтем это число из элементов столбцов 1,2 и 5, как из неотмеченных заливкой столбцов и строк. Тем самым мы получим таблицу 5.12.

Таблица 5.12

1	2	3	4	5
1	11	5	0	0	4,5	§
2	10	7	2	0	3,5	§
3	7,5	7,5	7,5	7,5	0
4	0	0	7	14	7,5	§
5	7	0	0	7	10,5	§
§	§	§	§

Применим к таблице 5.12 действия этапа 2 и получим, что число подчеркнутых двойной чертой не равно размерности матрицы, т.е. пяти. Тем самым переходим к этапу 3. Затем в таблице 5.12 отметим заливкой непомеченную строку 3 и помеченные столбцы 2,2,3,4. Оформим результаты действий в виде таблицы 5.13.

Таблица 5.13

1	2	3	4	5
1	11	5	0	0	4,5	§
2	10	7	2	0	3,5	§
3	7,5	7,5	7,5	7,5	0
4	0	0	7	14	7.5	§
5	7	0	0	7	10,5	§
§	§	§	§

Переходим к этапу 5, т.е. из части таблицы, которая не отмечена заливкой выделим наименьший элемент, т.е.

и вычтем его значение из элементов неотмеченных заливкой столбцов, т.е. из элементов столбца 5 и прибавим к элементам отмеченных заливкой строк, т.е. к элементам строки 3. Получим таблицу 5.14.