Метод потенциалов. .
Наиболее трудоемким в распределительном методе является расчет коэффициентов gij при алгебраическом суммировании по циклу пересчета, поэтому более рациональным является использование метода потенциалов для расчета gij в выражении целевой функции через свободные переменные xij. Суть метода: поставим каждому из m источников сырья потенциал ui, а каждому из n потребителю vj. Всего получилось m+n потенциалов. Рассмотрим некоторую базисную переменную xkl.
В матрице стоимости в этой ячейке стоит ckl. Составим уравнение uk + vl = ckl. Таким образом, мы получим n+m-1 уравнений относительно n+m неизвестных потенциалов. Поскольку одна переменная «лишняя», мы можем ее выбрать произвольно (например, положим u1=0). Рассмотрим теперь уравнения, в которые входит u0, из них легко определим входящие в них потенциалы vк. Теперь рассматриваем те уравнения, в которые входят уже найденные us, изкоторых находим новые потенциалы vк и т.д. по цепочке определим все потенциалы.
Теорема. Для любой свободной клетки имеет место равенство:
Дополнив распределительный метод методом потенциалов получаем эффективный метод решения ТЗЛП.
|
