Транспортная задача. В общем случае транспортная задача рассматривается как разработка наиболее экономичной структуры перевозки однотипной продукции из нескольких пунктов

В общем случае транспортная задача рассматривается как разработка наиболее экономичной структуры перевозки однотипной продукции из нескольких пунктов отправления в несколько пунктов назначения. Величина транспортных расходов задается с помощью тарифов на перевозку единицы груза. Транспортную задачу можно представить в виде сети с n пунктами отправления и m пунктами назначения.

a_n n m

На приведенной иллюстрации используются следующие обозначения:

- а_1, …, а_n – объемы предложений;

- b₁, …, b_m – объемы спроса;

- с_i,j – стоимость перевозки единицы груза из пункта i в пункт j;

- х_i,j – объем перевозки единицы груза из пункта i в пункт j.

Цель задачи – найти план перевозок Х=(х_i,j), минимизирующий суммарные затраты. Приведем математическую модель транспортной задачи:

при ограничениях

, i = 1, …, n,

, j = 1, …, m,

х_{i , j} ³ 0, i = 1, …, n; j = 1, …, m.

Для решения транспортной задачи исходные данные удобно представлять в виде матрицы планирования.

В соответствии с приведенной математической моделью, имеет место равенство суммарных предложения и спроса:

.

Очевидно, в реальности такая ситуация встречается далеко не всегда. Однако для решения любой транспортной задачи следует добиться этого равенства (искусственно, специальным образом). Если данное равенство выполняется, то такая задача называется сбалансированной (закрытой), в противном случае – несбалансированной (открытой). В том случае, если исходная транспортная задача не является сбалансированной, ее следует сбалансировать, то есть привести к закрытой форме. Для этого необходимо ввести фиктивные пункты назначения или предложения.

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

Стоимость доставки единицы груза из любого пункта предложения в фиктивный пункт назначения принимают равной 0: с_ф = 0.

Если суммарный спрос превышает суммарное предложение, то вводят фиктивный пункт предложения, который формально восполняет недостаток предложения:

Стоимость доставки единицы груза из фиктивного пункта предложения в любой пункт назначения принимают равной 0: с_ф = 0.

Решение транспортных задач проводится в два этапа: первоначальный и основной. На первоначальном этапе получают допустимое базисное решение, которое также называют опорным планом перевозок. Допустимое базисное решение удовлетворяет всем условиям задачи, кроме, быть может, оптимальности. Опорный план перевозок предполагает выполнение не более чем m + n – 1 поставок (заметим, что m + n – 1 – число линейно независимых ограничений системы ограничений). Можно показать, что всегда найдется такое оптимальное решение транспортной задачи, в котором количество поставок (занятых клеток в матрице планирования) также не превосходит числа m + n – 1. Поэтому оптимальный план перевозок ищут среди опорных планов.

Для нахождения первоначального решения используют методы северо-западного угла, наименьшей стоимости, Фогеля и др. Все эти методы предполагают решение одной задачи – построение начального опорного плана. Однако качество начального решения зависит от того, какой метод был использован для его получения. Как правило, метод северо-западного угла (очень простой в применении) дает решение, более далекое от оптимального плана поставок, по сравнению с методами наименьшей стоимости и Фогеля.

На основном этапе проводится последовательное улучшение начального опорного плана перевозок. В результате получается оптимальное базисное решение (оптимальный план перевозок), которое и является окончательным результатом для поставленной транспортной задачи. На основном этапе применяются распределительный метод, метод потенциалов и др.

Не нашли, что искали? Воспользуйтесь поиском: