Сущность транспортной задачи линейного программирования

Сущность транспортной задачи линейного программирования

В различных местах отправки имеется однородный груз, который требуется доставить в несколько пунктов назначения. Известно, сколько груза отправляется из каждого пункта и сколько груза должно поступить в пункт назначения. Причём безразлично, какой именно отправитель будет доставлять груз тому или иному получателю. Требуется так организовать перевозки, чтобы обеспечить минимальный общий пробег груза, т. е. минимизировать затраты на транспортировку.Экономико-мате­ма­тическая модель транспортной задачи представляется обычно в виде транспортной таблицы или матрицы.

Таблица 2.1

Экономико-математическая модель транспортной задачи

Примечание. А_i – название пункта отправления; В_j – название пункта назначения; a_i – производственная мощность поставщиков; b_j – спрос потребителей; m – число поставщиков; n – число потребителей; i – номер строки (i-й поставщик) i = 1…m; j – номер столбца (j-й потребитель) j = 1…n; c_ij – показатель критерия оптимальности, удельные затраты на транспортировку единицы продукции (себестоимость перевозок) от поставщика i до потребителя j;x_ij – количество продукции, перевозимое от поставщика i до потребителя j, план перевозок, распределение поставок, корреспонденция грузов.

Условия задачи в принятых обозначениях следующие.

1. Каждый поставщик должен дать ровно столько продукции, столько у него есть, т. е. сумма поставок по каждой строке должна будет равна мощности a_i этой строки:

. (2.1)

2. Каждый потребитель должен получить ровно столько продукции, сколько ему требуется, т. е. сумма поставок по каждому столбцу должна будет равна спросу b_i этого столбца:

. (2.2)

3. Из вышеприведённых условий (2.1) и (2.2) следует:

. (2.3)

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

Чтобы определить суммарные затраты на перевозки, достаточно просуммировать произведения объёмов каждой поставки на соответствующие им удельные затраты на транспортировку. План будет оптимальным, если эта сумма (целевая функция F) будет сведена к минимуму:

. (2.4)

Транспортная задача является закрытой, если соблюдается условие (2.3). Если данное условие не соблюдается, то для приведения открытой транспортной задачи к закрытому виду вводится фиктивный потребитель ФВ или фиктивный поставщик ФА. Разница между производственной мощностью и спросом относится на его счёт. Расходы по доставке груза до фиктивного потребителя или фиктивного поставщика равны нулю, так как груз фактически не перевозится.

Метод северо-западного угла

Берем «северо-западную» клетку матрицы – это клетка А₁В₁ и записываем в нее максимально возможную поставку – 40 т (объем выгрузки 40 т, ресурсы станции погрузки 100 т). Поскольку ресурсы станции погрузки А₁ не исчерпаны, следуем по первой строке вправо и записываем в клетку А₁В₂ корреспонденцию равную максимально возможной величине – 60 т. Таким образом получается, что ресурсы станции А₁ полностью использованы, однако спрос станции выгрузки В₂ не удовлетворен. Тогда от клетки А₁В₂опускаемся вниз до клетки А₂В₂ и записываем в нее поставку равную 20 т. Описанным способом следуем далее до последней «юго-западной» клетки матрицы. В результате получаем допустимый план перевозок груза. Грузооборот или функционал транспортной задачи (сумма произведений корреспонденций на расстояние, рассчитанная по табл. 2.3) составит:

F_{сев-зап.} = 40 ∙ 10 + 60 ∙ 9 + 20 ∙ 7 + 110 ∙ 13 + 20 ∙ 6 + 30 ∙ 7 + 60 ∙ 1 + + 30 ∙ 2 = 2960 ткм [см. формулу (2.4)].

После расстановки корреспонденции матрица проверяется на вырождение, т. е. должно выполняться условие

, (2.5)

где m – количество строк, n – количество столбцов, N_баз – количество базисных клеток.

Другими словами, количество клеток матрицы, содержащих корреспонденции, должно быть равно сумме строк и столбцов без единицы. В нашем случае это условие соблюдается: 8 = 4 + 5 – 1. План транспортной задачи, отвечающий условию (n + m – 1) называют базисным. Базисными также называются клетки матрицы, содержащие поставки. Клетки, в которых поставки отсутствуют, называются небазисными.

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

Наиболее предпочтительным при ручном решении транспортных задач считается метод минимальной стоимости или, как его еще называют, метод наименьшего элемента в матрице. Суть его в следующем. В транспортной матрице выбирается клетка с минимальной стоимостью (расстоянием). В нашем случае это клетка А₃В₅. В нее записывается максимально возможная поставка – это 90 т (табл. 2.4).

Таблица 2.4

Добавление нулевой поставки

Таким образом, причиной вырождения плана транспортной задачи является наличие поставщиков и потребителей с равными объемами погрузки и выгрузки или равными объемами сумм погрузки и выгрузки по нескольким станциям в разнообразных комбинациях. Такие случаи необходимо уметь находить для того, чтобы правильно определять места для нулевых поставок. В процессе решения задачи возможны случаи, когда число базисных клеток превышает величину «n + m – 1». Это означает появление ошибки вследствие того, что при построении опорного плана в какую-то клетку была введена не максимально возможная поставка.

Операция 2. Проверка плана на оптимальность.

Повторение операций 2, 3

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

Покажем дальнейшее решение задачи, основываясь на данных табл. 2.6. Результат действий второй и третьей итераций приведен в табл. 2.8.

Проверка плана на оптимальность свидетельствует о том, что для двух клеток условия оптимальности не выполняются. После перераспределения поставок по клетке А₄В₃, получаем новый план (табл. 2.9).

Таблица 2.9

Оптимальный план поставок

Проверка плана перевозок на оптимальность по условию (2.8) показала, что для всех небазисных клеток матрицы условия оптимальности выполняются. Функционал F'' оптимального плана равен 1920 ткм. Таким образом, получен план перевозок, обеспечивающий минимальный объем перевозочной работы для транспортировки всего груза между станциями погрузки и выгрузки.

Сущность транспортной задачи линейного программирования

В различных местах отправки имеется однородный груз, который требуется доставить в несколько пунктов назначения. Известно, сколько груза отправляется из каждого пункта и сколько груза должно поступить в пункт назначения. Причём безразлично, какой именно отправитель будет доставлять груз тому или иному получателю. Требуется так организовать перевозки, чтобы обеспечить минимальный общий пробег груза, т. е. минимизировать затраты на транспортировку.Экономико-мате­ма­тическая модель транспортной задачи представляется обычно в виде транспортной таблицы или матрицы.

Таблица 2.1