Метод минимального элемента

В таблице из всех значений стоимостей выбираем наименьшее и в клетку с наименьшей стоимостью записываем меньшее из чисел и . Исключа­ем из рассмотрения строку i, если запас вывезен полностью; или столбец j, если спрос удовлетворен полностью; или и строку и столбец, если = . Среди остальных стоимостей снова выбираем наименьшую и заполняем соответствующую клетку таблицы. Таким же образом продолжаем заполнять клетки таблицы, пока не будет найдено опорное решение.

Пример 1:

Рассмотрим метод на примере, исходные данные которого представлены табл.1.

Поставщики	Потребители	Запас
Спрос

Таблица 2.

Поставщики	Потребители	Запас
Спрос

Циклом или замкнутым контуром, называется замкнутая ломаная, 1)содержащая четное число вершин, 2)повороты звеньев производятся только под прямым углом, 3)каждое звено соединяет минимум 2 клетки строки (столбца). Циклы могут быть самой разнообразной конфигурации, однако они должны удовлетворять данным условиям.

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

С учетом сказанного, опорное решение транспортной задачи должно быть ацикличным.

Дата добавления: 2014-01-11