На три базы поступил однородный груз в количествах a₁, a₂, a₃. Груз требуется перевезти в четыре пункта в объеме b₁, b₂, b_3, b₄. Спланировать перевозки так, чтобы их общая стоимость была минимальной, весь груз был вывезен. Матрица тарифов с_ij , запасы и потребности указаны в таблице.

Вариант 5

Решение задачи получим с помощью калькулятора.

Проверим необходимое и достаточное условие разрешимости задачи.

∑a = 120 + 80 + 60 = 260

∑b = 100 + 70 + 70 + 20 = 260

Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.

Занесем исходные данные в распределительную таблицу.

Этап I. Поиск первого опорного плана.

1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел a_i, или b_j.

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

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

Искомый элемент равен 1

Для этого элемента запасы равны 60, потребности 20. Поскольку минимальным является 20, то вычитаем его.

x₃₄ = min(60,20) = 20.

Искомый элемент равен 2

Для этого элемента запасы равны 120, потребности 100. Поскольку минимальным является 100, то вычитаем его.

x₁₁ = min(120,100) = 100.

Искомый элемент равен 3

Для этого элемента запасы равны 40, потребности 70. Поскольку минимальным является 40, то вычитаем его.

x₃₃ = min(40,70) = 40.

Искомый элемент равен 4

Для этого элемента запасы равны 20, потребности 30. Поскольку минимальным является 20, то вычитаем его.

x₁₃ = min(20,30) = 20.

Искомый элемент равен 5

Для этого элемента запасы равны 80, потребности 70. Поскольку минимальным является 70, то вычитаем его.

x₂₂ = min(80,70) = 70.

Искомый элемент равен 6

Для этого элемента запасы равны 10, потребности 10. Поскольку минимальным является 10, то вычитаем его.

x₂₃ = min(10,10) = 10.

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

2. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F(x) = 2*100 + 4*20 + 5*70 + 6*10 + 3*40 + 1*20  = 830

Этап II. Улучшение опорного плана.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₁ = 2; 0 + v₁ = 2; v₁ = 2

u₁ + v₃ = 4; 0 + v₃ = 4; v₃ = 4

u₂ + v₃ = 6; 4 + u₂ = 6; u₂ = 2

u₂ + v₂ = 5; 2 + v₂ = 5; v₂ = 3

u₃ + v₃ = 3; 4 + u₃ = 3; u₃ = -1

u₃ + v₄ = 1; -1 + v₄ = 1; v₄ = 2

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_j ≤ c_ij.

Минимальные затраты составят:

F(x) = 2*100 + 4*20 + 5*70 + 6*10 + 3*40 + 1*20  = 830

Анализ оптимального плана.

Из 1-го склада необходимо груз направить в 1-й магазин (100), в 3-й магазин (20)

Из 2-го склада необходимо груз направить в 2-й магазин (70), в 3-й магазин (10)

Из 3-го склада необходимо груз направить в 3-й магазин (40), в 4-й магазин (20)

Решение было получено и оформлено с помощью сервиса:

Транспортная задача