Алгоритм метода потенциалов

из "Математические методы моделирования экономических систем Изд2 "

Наиболее распространенным методом решения транспортных задач является метод потенциалов. [c.272]
Описанная процедура повторяется несколько раз (итераций), пока не будет найдено оптимальное решение. Вычислительный алгоритм для каждой итерации не меняется. [c.273]
Начальный план можно составить одним из перечисленных выше методов. Воспользуемся наиболее простым методом — методом северо-западного угла. В соответствии с этим методом загрузка клеток (распределение объемов пунктов отправления по пунктам назначения) начинается с верхней левой клетки ( северо-западная часть таблицы) и продолжается вниз и вправо (по диагонали). [c.273]
Результаты начального плана и расчета потенциалов представлены в табл. 8.3. [c.274]
В этой клетке намечаем одну из вершин контура и далее по вышеизложенным правилам строим контур, вершины которого будут находиться в клетках (3-1) - (1-1) - (1-2) - (2-2) - (2-3) -— (3—3). Вершины контура последовательно подразделяем на загружаемые (3) и разгружаемые (Р), начиная с вершины максимальной неоптимальности + (табл. 8.3). [c.276]
Перераспределение ресурсов по контуру осуществляется с целью получения оптимального плана. В процессе перераспределения ресурсов по контуру в соответствии с условием неотрицательности переменных Ху ни одно из этих значений не должно превратиться в отрицательное число. Поэтому анализируют только клетки, помеченные знаком Р, из которых выбирают клетку с минимальным объемом перевозок. В нашем примере Хт п = min 40 40 40 = 40. Следовательно, клетки (1-1), (2-2), (3-3) полностью разгружаются. В клетке (1-2) загрузка увеличится на 40 и достигнет 60, в клетке (2—3) загрузка составит 40 + 40 = 80, и клетка (3-1) загрузится на 40 (табл. 8.4). [c.276]
Проверяем условие N=m + n — L Б нашем примере т = 3, я = 4, а число загруженных клеток равно 4, т. е. условие не выполняется и 6 4. В процессе перераспределения ресурсов произошла полная разгрузка трех клеток, а мы должны освободить только одну клетку. В этом случае следует в две клетки проставить нули (нулевой ресурс) и считать условно их загруженными. Например, в клетки (1—1) и (3—3) проставим нулевой ресурс (рис. 8.4). Получение нового плана (итерации) осуществляется в том же порядке, который был рассмотрен выше, т. е. [c.276]
Ниже приведены расчеты по второй итерации и оптимальный план. [c.277]
Клетку (2—4) необходимо загрузить. [c.278]
В соответствии с перераспределением ресурсов по контуру получаем табл. 8.5, для которой вновь рассчитываем потенциалы а,- и Ру, и последовательность вычислений повторяется. [c.278]
Для распределения, полученного в табл. 8.5, условие а,- + Ру выполняется, следовательно, план - оптимальный. [c.278]
Таким образом, построением начального плана с последующим расчетом двух итераций получено оптимальное решение по прикреплению пунктов отправления грузов к пунктам назначения. [c.278]

Вернуться к основной статье