Построение оптимального плана методом минимального элемента

Минимальная стоимость перевозок (6) в клетке а₂b₁ — отправляем весь груз из а₂ потребителю b₁ и строку а₂ исключаем из дальнейшего рассмотрения.

Следующий минимум (7) в клетке а₄b₄ — отправляем весь груз из а₄ потребителю b₄ и строку а₄ исключаем из дальнейшего рассмотрения.

Следующий минимум (10) в клетке а₃b₁ — закрываем потребность b₁ поставкой из а₃ и столбец b₁ исключаем из дальнейшего рассмотрения.

Следующий минимум (12) в клетке а₁b₂ — весь груз из а₁ отправляем в b₂ и строку а₁ исключаем из дальнейшего рассмотрения.

Следующий минимум (19) в клетке а₃b₂ — закрываем потребность b₂ поставкой из а₃ и столбец b₂ исключаем из дальнейшего рассмотрения.

Поставкой остатка груза из а₃ закрываем потребности b₃ и b₄.

Опорный план составлен.

Стоимость перевозок по этому плану:

Z₁ = 105· 12 + 70•6 + 25•10 + 55•19 + 135•22 + 25?27 + 85?7 = 7215 д.е.

Проверяем оптимальность плана методом потенциалов, присвоив первой строке нулевой потенциал U₁ = 0. Потенциалы других строк и столбцов определяем по формулам:

U_i = C_ij — V_j; V_j = C_ij — U_i;

Определяем характеристики клеток, оставшихся свободными по формуле:

E_ij = C_ij — (V_j + U_i) (вписаны в левый нижний угол).

Среди характеристик свободных клеток есть одна отрицательная (Е₂₂ = -4), значит полученный план не оптимален.

Строим для клетки а₂b_, цикл (показан пунктиром) и перемещаем по нему наименьшую из перевозок (55), находящихся в углах цикла, смежных с этой клеткой. Получаем новый план (табл. № 2).

Очевидно, что полученный план не является оптимальным, т.к. среди характеристик свободных клеток есть отрицательные.

Далее без комментариев повторяем итерацию с перемещением перевозки (15) по циклу в клетку a₁b₄ с отрицательной характеристикой (-3). Получаем третий план (табл. № 3).

Этот план оптимальный, т.к. все характеристики свободных клеток положительны. План повторяет план, ране полученный методом северо-западного угла.

Zопт = Z_min = 6950 ден. ед.

Построение оптимального плана методом Фогеля.

При определении опорного плана методом аппроксимации Фогеля на каждой итерации по всем столбцам и по всем строкам находим разность между двумя записанными в них минимальными затратами. Эти разности записаны в специально отведенных для этого строках и столбцах для каждого шага. Среди указанных разностей выбрана максимальная. В строке (или в столбце), которой данная разность соответствует, определён минимальный тариф и клетка, в которой он записан, заполнена на данной итерации (выделено жирным шрифтом).

Например, на первом шаге в первой строке минимальные затраты 17 и 12, разность — 5, во 2-ой строке 11 и 6, разность 5, в 3-ей 19 и 10, разность 9, в 4-ой 14 и 7, разность 7.

В 1-ом столбце минимальные затраты 10 и 6, разность 4, во 2-ом 12 и 11, разность 1, в 3-ем 20 и 17, разность 3, в 4-ом 21 и 7, разность 14.

Наибольшая из этих разностей — 14 соответствует 4-му столбцу. В этом столбце минимум затрат — 7 в строке 4. Заполняем клетку а₄b₄ объёмом поставок 85 единиц, который может быть поставлен от четвёртого поставщика и строку 4 из дальнейшего рассмотрения исключаем. По аналогии заполнены остальные клетки таблицы и получен опорный план.

Цена этого плана:

Z₁ = 90•12 + 15?21 + 70•11 + 95•10 + 135•22 + 10?27 + 85?7 = 6950 д.е.

Этот полученный план является оптимальным, т.к. такой же план получен при использовании методов северо-западного угла и минимального элемента.

Задача 7.2. Решить транспортную задачу. Первичный опорный план необходимо найти тремя способами: методом северо-западного угла, методом минимальной стоимости, методом Фогеля. Для каждого найденного опорного плана, произвести перепланировку поставок с помощью метода потенциалов.

Решение: Общий объём запасов:

Общая потребность:

Т.к., то это транспортная задача открытого типа.

Для приведения её к закрытому типу вводим фиктивного потребителя с нулевой стоимостью перевозок, имеющего потребность: