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

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

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

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

х₁₁ = min(a₁,b₁).

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

а) если a₁ < b₁, то х₁₁ = а₁ и всю первую строку, начиная со второго элемента, заполняют нулями;

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

в) если a₁ = b₁, то х₁₁ = а₁ = b₁, и все оставшиеся элементы первых столбца и строки заполняют нулями.

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

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

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

и

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

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

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

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

Тогда полагают х_ij⁰ = min(a_i, b_j).

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

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

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

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

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

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

Тогда , где

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

а) , тогда и оставшуюся часть строки заполняют нулями;

б) , тогда и остаток столбца заполняют нулями;

в) , тогда оставшуюся часть строки и столбца заполняют нулями.