Введение. 
Решение транспортных задач

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

Под названием транспортная задача объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены известным симплексным методом. Однако обычная транспортная задача имеет большое число переменных и решение ее симплексным методом громоздко. С другой стороны матрица системы ограничений транспортной задачи весьма своеобразна, поэтому для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить последовательность опорных решений, которая завершается оптимальным решением.

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

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

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

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

Построение оптимального плана методом северо-западного угла.

Здесь в верхнем правом углу клеток записана стоимость перевозки.

Заполнять таблицу первоначального опорного плана начинаем с клетки а₁b₁ — это северо-западный угол.

Закрываем потребности b₁ поставкой из а₁ и этот столбец исключаем из дальнейшего рассмотрения. Остаток груза из а₁ отправляем потребителю b₂ и строку а₁ исключаем из дальнейшего рассмотрения. Затем весь груз из а₂ отправляем в b₂, исключая строку а₂ и частью груза из а₃ закрываем потребность b₂, исключая столбец b₂. Далее закрываем потребность b₃ поставкой из а₃, а остаток груза из а₃ отправляем потребителю b₄. Груз из а₄ отправляем потребителю b₄. Опорный план составлен.

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

Z₁ = 95· 17 + 10•12 + 70•11 + 80•19 + 135•22 + 25?27 + 85?7 = 8265 д.е.

Число заполненных клеток должно быть m + n -1 = 4 + 4 — 1 = 7, что так и есть, т. е. план не вырожден.

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

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

V₁ = C₁₁ — U₁ = 17 — 0 = 17; V₂ = C₁₂ — U₁ = 12 — 0 = 12; U₂ = C₂₂ — V₂ = 11 — 12 = -1;

U₃ = C₃₂ — V₂ = 19 — 12 = 7; V₃ = C₃₃ — U₃ = 22 — 7 = 15; V₄ = C₃₄ — U₃ = 27 — 7 = 20.

U₄ = C₄₄ — V₄ = 7 — 20 = -13;

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

Eij = Cij — (Vj + Ui) (вписаны в левый нижний угол) Е₁₃ = С₁₃ — (V₃ + U₁) = 17 — (15 + 0) = 2; Е₁₄ = С₁₄ — (V₄ + U₁) = 21 — (20 + 0) = 1;

Е₂₁ = С₂₁ — (V₁ + U₂) = 6 — (17 — 1) = -10; Е₂₃ = С₂₃ — (V₃ + U₂) = 20 — (15 — 1) = 6;

Е₂₄ = С₂₄ — (V₄ + U₂) = 28 — (20 — 1) = 9; Е₃₁ = С₃₁ — (V₁ + U₃) = 10 — (17 + 7) = -14;

Е₄₁ = С₄₁ — (V₁ + U₄) = 18 — (17 — 13) = 14; Е₄₂ = С₄₂ — (V₂ + U₄) = 14 — (12 — 13) = 15;

Е₄₃ = С₄₃ — (V₃ + U₄) = 23 — (15 — 13) = 21;

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

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

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

Z₂ = 15· 17 + 90•12 + 70•11 + 80•10 + 135•22 + 25?27 + 85?7 = 7145 д.е.

что меньше первого плана на 1120 ден. ед.

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

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

Его цена:

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

что меньше второго плана на 195 ден. ед.

Этот план оптимальный, т.к. все характеристики свободных клеток положительны.

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