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


Метод Северо-западного угла используют для нахождения произвольного опорного плана транспортной задачи.
Схема метода: 1) Полагают верхний левый элемент матрицы X
x 11 = min(a 1 ,b1)
Возможны три случая:
а)если a1 < b1, то х111 и всю первую строку начиная со второго элемента заполняют нулями.
б)если a1 > b1, то Х11=b1, а все оставшиеся элементы первого столбца заполняют нулями.
в)если a1 = b1, то х11 = a 1 = b 1 , и все оставшиеся элементы первых столбца и строки заполняют нулями.
На этом один шаг метода заканчивается.
2) Пусть уже проделано к шагов, кm-й шаг состоит в следующем.
Определяют верхний левый элемент незаполненной части матрицы X. Пусть это элемент хl, m.
Тогда полагают хl,m  = min(аkl, bkm),
где
аkl = al - Σxlj
bkm = bm - Σxim
Если аkl < bkm, то заполняют нулями l -ю строку начиная с (m + 1)-го элемента. В противном случае заполняют нулями оставшуюся часть m-го столбца.

Метод минимального элемента позволяет построить начальный опорный план транспортной задачи и является вариантом метода северо­западного угла, учитывающим специфику матрицы С=(cij)m,n. В отличие от метода северо-западного угла данный метод позволяет сразу получить достаточно экономичный план и сокращает общее количество итераций по его оптимизации.
Схема метода: элементы матрицы С нумеруют начиная от минимального в порядке возрастания, а затем в этом же порядке заполняют матрицу Х0.
Пусть элементом с минимальным порядковым номером оказался элемент x0ij .
Тогда полагают x 0 ij = min (ai, bj)
Возможны три случая:
а) если min (ai, bj) = ai, то оставшуюся часть i-й строки заполняют нулями;
б) если min (a1, b1) = bj, то оставшуюся часть j-ro столбца заполняют нулями.
в) если ai = bj, то оставшуюся часть строки и столбца заполняют нулями.
Далее этот процесс повторяют с незаполненной частью матрицы.
Пусть элементом с k -м порядковым номером оказался хklm. Тогда хklm = min(akl, bkm),
где
а k l = al - Σxglj, g = 1..l-1
bkm = bm - Σxuim, u = 1..k-1
Возможны три случая:
а) аkl < bkm, тогда хklm = аkl и оставшуюся часть строки l заполняют нулями;
б) аkl > bkm, тогда хklm = bkm и остаток столбца m заполняют нулями;
в) аk = bkm, тогда оставшуюся часть строки l и столбца m заполняют нулями.

загрузка...