28. Методы составления первоначальных опорных планов

Метод северо-западного угла используют для нахождения произвольного опорного плана транспортной задачи.

Схема метода:

1) Полагают верхний левый элемент матрицы Х

Х11 = min (a1, b1).

Возможны три случая:

А) если a1 < b1, то х11 = а1 и всю первую строку, начиная со второго элемента, заполняют нулями;

Б) если a1 > b1, то х11 = b1, а все оставшиеся элементы первого столбца заполняют нулями;

В) если a1 = b1, то х11 = а1 = b1, а все оставшиеся элементы первых столбца и строки заполняют нулями.

2) Пусть проделано k шагов, -й шаг состоит в следующем.

Определяют верхний левый элемент незаполненной части матрицы Х. Пусть это элемент .

Тогда полагают где

и .

Если , то заполняют нулями -ю строку начиная с -го элемента.
В противном случае заполняют нулями оставшуюся часть -го столбца.

Метод минимального элемента позволяет построить начальный опорный план транспортной задачи и является вариантом метода северо-западного угла, учитывающим специфику матрицы С = (сij)m, n. В отличие от метода северо-западного угла данный метод позволяет сразу получить достаточно экономичный план и сокращает общее количество итераций по его оптимизации.

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

Пусть элементом с минимальным порядковым номером оказался элемент хij0.

Тогда полагают хij0 = min(ai, bj).

Возможны три случая:

А) если min(ai, bj) = ai, то оставшуюся часть i-й строки заполняют нулями;

Б) если min(ai, bj) = bj, то оставшуюся часть j-го столбца заполняют нулями;

В) если аi = bj, то оставшуюся часть строки и столбца заполняют нулями.

Далее этот процесс повторяют с незаполненной частью матрицы.

Пусть элементом с k-ым порядковым номером оказался .