7.2.1.3 Метод потенциалов

Метод потенциалов является модификацией симплекс-метода решения задачи линейного программирования применительно к транспортной задаче. Он позволяет, отправляясь от некоторого допустимого решения, получить оптимальное решение за конечное число итераций. Общая схема отдельной итерации такова. По допустимому решению каждому пункту задачи сопоставляется число, называемое его предварительным потенциалом. Пунктам А_i соответствуют числа u_i, пунктам B_j ‑ числа v_j. Они выбираются таким образом, чтобы их разность на k-й итерации была равна С_ij - стоимости перевозки единицы продукции между пунктами А_i и В_j:

v_j[k] – u_i[k] C_ij, i 1, ..., m; j 1, …, п. (7.33)

Если разность предварительных потенциалов для каждой пары пунктов А_i, В_j не превосходит С_ij, то полученный план перевозок является решением задачи. В противном случае указывается способ получения нового допустимого плана, связанного с меньшими транспортными издержками. За конечное число итераций находится оптимальный план задачи.