Добро пожаловать на наш портал !

Методы компьютерного моделирования экономических процессов

Алгоритм метода потенциалов для транспортной задачи

Алгоритм метода потенциалов для транспортной задачи. Критерий (3.8)-(3.9) положен в основу одного из методов решений транспортной задачи, получившего название метода потенциалов. Впервые он был предложен в 1949г. Л. В. Канторовичем и М. К. Гавуриным. Позже на базе общих идей линейного программирования аналогичный метод был предложен Дж. Данцигом.

Точно так же как транспортная задача является частным случаем задачи ЛП, так и метод потенциалов, вообще говоря, может трактоваться как разновидность симплексных процедур. Он представляет собой итеративный процесс, на каждом шаге которого рассматривается некоторый текущий базисный план, проверяется его оптимальность, и при необходимости определяется переход к «лучшему» базисному плану.

Алгоритм начинается с выбора некоторого допустимого базисного плана (методы его построения были рассмотрены в п. 3.1.2). Если данный план не вырожденный, то он содержит m + n -1 ненулевых базисных клеток, и по нему можно так определить потенциалы ui и vj, чтобы для каждой базисной клетки (т. е. для той, в которой хi,j > 0) выполнялось условие

Поскольку система (3.10) содержит m+n-1 уравнение и m+n неизвестных, то один из потенциалов можно задать произвольно (например, приравнять vj или ui к нулю). После этого остальные неизвестные ui и vj определяются однозначно.