МЕТОД ПОТЕНЦИАЛОВ

Предварительно введем некоторые понятия.

1. Любую совокупность клеток распределительной таблицы называют набором.

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

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

Необходимо различать базисные и небазисные клетки распределения таблицы ТЗ. Базисные клетки – это те клетки таблицы, в которых назначены перевозки. Количество базисных клеток должно быть равно . Небазисные клетки пусты с точки зрения перевозок.

Заметим, если количество базисных клеток меньше , то ТЗ называют вырожденной.

Для устранения процедуры вырожденности в состав базисных клеток включают небазисные, назначая в них нулевые перевозки.

Если набор базисных клеток не содержит ни одного цикла, то план ТЗ называется ациклическим.

ТЕОРЕМА (ОБ ОПТИМАЛЬНОМ ПЛАНЕ ТЗ).

Запишем математическую модель ТЗ

(4)

По отношению к задаче (1) – (4) составим двойственную задачу

(5)

(все переменные неотрицательны)

Учитывая, что U_i и V _j могут иметь любые знаки и для аналогичных двойственных переменных с разностью потенциалов, переменным U_i присваивают знак «–», тогда двойственная задача приобретает вид

(7)

(8)

Поиск по сайту: