Задачи распределительного типа, решаемые в землеустройстве

Итерация 1.

Шаг 1.

Значение целевой функции равно:

Z = 60*2 + 4*30 + 60*6 + 60*4 +60*4 +2*90 = 1260 у.е.

Проверим план на вырожденность по следующей формуле:

=m+n-1.

В нашем примере m=3, n=4, а число загруженных клеток 6, т.е. 6=6. Таким образом, план невырожден.

ШАГ 2. Проверяю план на оптимальность.

Проверяю методом потенциалов при которой каждый i-строки (I поставщик) устанавливается потенциал Ui, который можно интерпретировать как цену продукта пункта поставщика, а к каждому столбцу j-го потребителя устанавливается потенциал Vj , который можно интерпретировать как цену продукта у потребителя. Простейший случай: цена пункта потребителя равна цене продукта поставщика + расходы перевозок.

Vj = Ui + Cij

Потенциал первой строки равен 0.

Таблица 5.3 Транспортная схема 1

Затем определяю при оптимальности распределения через их оценки dij = ( Ui + Cij )- Vj. Условием оптимальности распределения служит условие не отрицательности оценок свободных клеток матрицы перевозок.

0 4 8

dij = 4 0 0 -2

-4 -2 0 0

План требует улучшения.

ШАГ 3. Выполняю процесс улучшения плана.

Клетку (3;1) нужно загрузить за счет перераспределения ресурсов из других загруженных клеток. В таблице 3 эту клетку помечаем знаком Х, так как здесь в начальном плане находится вершина максимальной неоптимальности. Маршрут представлен в таблице 3.3.