Постановка и основные свойства транспортной задачи

Рефераты / Экономико-математическое моделирование / Постановка и основные свойства транспортной задачи

Формальное описание алгоритма. I. Определяют верхний левый элемент матрицы Х:

Возможные три случая: а) если то и всю первую строку, начиная со второго элемента, заполняют нулями; б) ес

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

то

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

Находим

на этом один шаг метода заканчивается.

2. Пусть уже проделано k шагов. (k+1) – й шаг состоит в следующем. Определяют верхний левый элемент незаполненной части матрицы Х. Пусть это будет элемент

причем

, (1.27)

где

(1.28)

Если , то заполняем нулями строку , начиная с ( +1) – го элемента. В противном случае заполняем нулями столбец , начиная с элемента ( +1). Если , то заполняем нулями остаток строки и столбца . Далее вычисляем . На этом (k+1) – й шаг заканчивается. Описанный процесс повторяется до тех пор, пока матрица Х не будет заполнена полностью.

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

Этот метод является вариантом метода северо-западного угла, учитывающим специфику матрицы транспортных затрат С=. В отличие от метода северо-западного угла данный метод позволяет сразу получить достаточно экономичный план, сокращая общее количество итераций по его дальнейшей оптимизации.

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

Пусть элементом с минимальным порядковым номером оказался . Возможные три случая: а) если , то оставшуюся часть -й строки заполняем нулями; б) если , то оставшуюся часть -го столбца заполняем нулями; в) если , то оставшуюся часть -й строки и -го столбца заполняем нулями.