Экономико-математические методы и модели

Стоимость перевозок по данному плану составляет: 7300 тыс. руб.

Решим задачу с применением метода потенциалов.

Для этого плана можно определить платежи (ai и bj ), так, чтобы в каждой базисной клетке выполнялось условие :

ai + bj = с

i,j (*)

Уравнений (*) всего m + n - 1, а число неизвестных равно m + n. Следовательно, одну из этих неизвестных можно задать произвольно (например, равной нулю). После этого из m + n - 1 уравнений (*) можно найти остальные платежи ai , bj , а по ним вычислить псевдостоимости: ui,j= ai + bj для каждой свободной клетки.

Если оказалось, что все эти псевдостоимости не превосходят стоимостей ui,j  с

i,j ,

то план потенциален и, значит, оптимален. Если же хотя бы в одной свободной клетке псевдостоимость больше стоимости (как в нашем примере), то план не является оптимальным и может быть улучшен переносом перевозок по циклу, соответствующему данной свободной клетке. Цена этого цикла ровна разности между стоимостью и псевдостоимостью в этой свободной клетке.