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

Цель работы: построить план перевозок деталей со всех складов в полном объеме во все магазины, полностью удовлетворив спрос, так, чтобы суммарные транспортные расходы были минимальны.

Условие:

Имеется 4 склада и 4 магазина. Таблица стоимости перевозки детали со склада a_i в магазин b_j:

Таблица потребности магазинов в деталях (начальный план):

Ограничения:

где x_ij – кол-во деталей, отправляемых со склада i в магазин j, a_i – объем деталей на складе, b_j – спрос магазина. Это значит, что со складов все детали должны быть вывезены и потребность магазинов должна быть удовлетворена.

Целевая функция:

,

где c_ij – стоимость доставки детали со склада i в магазин j.

Потенциал Р(3) = 0.

Порядок выполнения работы:

Оптимальный план строится с помощью метода потенциалов. Данный метод является итерационным. Каждая итерация состоит из следующих действий:

1. Вычисляется значение целевой функции по текущему плану.

Здесь значение целевой функции равно 1330.

1. Вычисляются потенциалы Q (для каждой строки) и P (для каждого столбца) по формулам:

Q(i) = C(i,j) – P(j)

P(j) = C(i,j) – Q(i)

(По условию, потенциал Р(3) = 0).

1. Вычисляются невязки для каждой ячейки по формуле:

G(i,j) = C(i,j) – Q(i) – P(i)

Если в таблице не существует отрицательных невязок – текущий план оптимален (выход из итерационного процесса).

Данный план неоптимален.

1. Если в п.3 текущий план признан неоптимальным, необходимо построить новый. Для этого:
1. Определяются координаты ячейки с наименьшей невязкой (перевозка, вводимая в базис).
2. Из всех перевозок удаляются те, которые не образуют цикл.

1. Перевозки, входящие в цикл, в таблице помечаются знаками "+" и "–" так, чтобы у соседних ячеек таблицы знаки чередовались.
2. Из перевозок со знаком "-" находится перевозка с наименьшим количеством деталей.

1. В клетках со знаком "+" добавляется количество деталей найденной выше перевозки. В клетках со знаком "-" это количество вычитается. Затем для модифицированного плана выполняется новая итерация, т.е. переход на п.1.

В данном задании для нахождения оптимального плана пришлось выполнить 6 итераций. Были получены следующие значения целевой функции:

Был получен следующий оптимальный план доставки:

Этот план удовлетворяет ограничениям (суммы по столбцам и строкам не изменились, т.е. со складов все детали вывозятся и потребность магазинов удовлетворяется). При этом целевая функция (суммарные транспортные расходы) минимальна (ее значение равно 990).

Поиск по сайту: