Алгоритм решения ТЗЛП методом потенциалов

Алгоритм решения ТЗЛП методом потенциалов

1. Нахождение (составление) опорного плана

Для нахождения опорного плана целесообразно использовать один из приближенных методов:

метод северо-западного угла;

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

2. Расчет потенциалов строк и столбцов

Определение потенциалов строк и столбцов осуществляется по базисным переменным опорного плана. Обязательной процедурой при этом является проверка следующего условия:

, ( 1 )

где m – количество пунктов отправлений (баз);

n - количество пунктов назначения (объектов, потребителей);

БК – количество так называемых базовых клеток (в которые были сделаны назначения при составлении опорного плана перевозок).

Специфика метода потенциалов состоит в том, что для проверки опорного (базисного) плана на оптимальность в каждом столбце и строке определяются значения потенциалов U_i и V_j .

3. Определение потенциалов свободных клеток и проверка плана на оптимальность

В ходе данной процедуры определяются индексы свободных клеток a_ij, показывающие как изменится значение целевой функции, если соответствующая этой клетке переменная x_ij будет переведена из свободных в базисные.

, ( 2 )

План является оптимальным, если потенциалы свободных клеток будут удовлетворять условию

. ( 3 )

12 Следующая ⇒