Методы составления первоначальных опорных планов
Метод северо-западного угла используют для нахождения произвольного опорного плана транспортной задачи.
Схема метода: 1) Полагают верхний левый элемент матрицы X
x11 = min(a1,b1).
Возможны три случая:
а) если a1 < b1, то х11 = a1 и всю первую строку, начиная со второго элемента, заполняют нулями.
б)если a1 > b1ь то х11 = b1 а все оставшиеся элементы первого столбца заполняют нулями.
в)если a1 = b1 то х11 = a1= b1 и все оставшиеся элементы первых столбца и строки заполняют нулями.
На этом один шаг метода заканчивается.
) Пусть проделано к шагов, (к) - й шаг состоит в следующем.
Определяют верхний левый элемент незаполненной части матрицы X. Пусть это элемент xλµ (λ + µ = к + λ).
Тогда полагают xXil = min(аλ,bµ), где
aλ(k)=aλ-
и bµ(k)=bµ-
(1.3)
Если aλ < bµ, то заполняют нулями λ-ю строку начиная с (µ +
1) -го элемента. В противном случае заполняют нулями оставшуюся часть µ
- го столбца. Метод минимального элемента позволяет построить начальный опорный план транспортной задачи и является вариантом метода северо-западного угла, учитывающим специфику матрицы С = (Cij)m,n. В отличие от метода северо-западного угла данный метод позволяет сразу получить достаточно экономичный план и сокращает общее количество итераций по его оптимизации.
Схема метода: элементы матрицы С нумеруют, начиная от минимального в порядке возрастания, а затем в этом же порядке заполняют матрицу Х°.
Пусть элементом с минимальным порядковым номером оказался элемент xij°.
Тогда полагают xij°= min(ai, bj)
Возможны три случая:
а) если min(ai, bj) = а;, то оставшуюся часть i-й строки заполняют нулями;
б) если min(ai, bj) = bj, то оставшуюся часть j-ro столбца заполняют нулями.
в) если ai = bj, то оставшуюся часть строки и столбца заполняют нулями.
Далее этот процесс повторяют с незаполненной частью матрицы. Пусть элементом с k-м порядковым номером оказался xλµ.
Тогда xλµ =min(aλ, bµ),где
aλ(k)=aλ-(g) g=1…k-1
bµ(k)=bµ-(u) u=1…k-1 (1.4)
Возможны три случая:
а) aλ(k)< bµ(k)', тогда xλµ(k) = aλ(k) и оставшуюся часть строки λ заполняют нулями;
б) aλ(k)> bµ(k), тогда xλµ(k) = bµ(k) и остаток столбца µ з
аполняют нулями;
в) aλ(k) = bµ(k), тогда оставшуюся часть строки λ и столбца µ заполняют нулями.[4]