Контрольная работа: Решение задач методом северо-западного угла, рапределительного, минимального и максимального элемента по строке

-

5

-

5

24

24

Потребности

25

19

24

28

S = 96

Стоимость перевозок Z = 1×21+4×7+1×19+1×3+7×21+3×4+5×24 = 350

Допустимый план методом северо-западного угла

Алгоритм состоит из двух шагов:

Предварительный шаг

Общеповторяющийся шаг

Предварительный шаг:

Находим допустимый ациклический план.

Составляем систему потенциалов.

Анализируем систему на потенциальность.

Общеповторяющийся шаг:

Положительные разности , находим наибольшую, включаем эту клетку в набор и строим на ней цикл.

Означиваем цикл.

Выбираем наименьшее значение перевозки в клетках отрицательной полуцепи.

Из перевозок в каждой клетке отрицательной полуцепи вычитаем Q, а к положительным перевозка прибавляется. Эта операция – сдвиг по циклу на величину Q.

Пересчитываем систему потенциалов.

Проверяем систему на потенциальность.

Если система не потенциальна, то переходим к пункту 1 общеповторяющегося шага.