Комбинаторные методы

Алгоритм Джонсона для задачи упорядочения работ в 2-х канальной системе.

Алгоритм включает следующие этапы:

1.поиск наименьшего элемента

В таблице исходных данных находят минимальный элемент и отмечают его точкой.

2.перестановка информации

Определяем местоположение минимального элемента , если он относится к первому пункту обслуживания то соответствующий столбец ставим на первое место , если ко второму то на последнее место календарного плана.

Если одинаковые мин.элементы находятся в 2-х строках, то информация с мин. Временем обрабатывается на первом пункте ставши на первое место с мин. элементом во второй строке на последнее место. Если оба мин.элемента находятся в первой (второй) строке, то на первое место ставится информация с большим (меньшим) временем обработки на втором (первом) пункте обслуживания.

3.вычеркивание из таблицы столбца отмеченного точкой и переход к пункту 1 до тех пор пока не будет исчерпан весь список информации.

4.выписать оптимальное решение .

5.определение оптимального значения целевой функции

При этом графически для оптимального решения определяется мин.время работы и простоя 2-го пункта обслуживания.

Венгерский алгоритм включает следующие этапы:

1.приведение исходной матрицы ;

В каждой строке исходной матрицы отыскиваем минимальный элемент и вычитаем его из всех элементов соответствующей строки и получаем новую матрицу.

Аналогичные операции осуществляются по столбцам.

2.поиск оптимального решения ;

В приведенной матрице отыскиваем одну из строк имеющую меньше всего нулей. Один из нулей этой строки отмечаем точкой и вычеркиваем все остальные нули этой строки и того столбца, где ноль находится. Аналогичную операцию проводим пока не останется непомеченных и не вычеркнутых нулей. Если точками отмечено n нулей, то назначение полное и переходим к пункту 5, иначе переходим к пункту 3.

3.поиск минимального набора строк и столбцов, содержащих нули. Для этого отмечают точкой.

a)все строки, в которых ни одного отмеченного точкой нуля.

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

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

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

4.перестановка нулей;

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

5.выписать оптимальное назначение.

6.определить минимальное значение целевой функции.