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

Транспортные модели (задачи) – специальный класс задач линейного программирования. Эти модели часто описывают перемещение (перевозку) какого-либо товара из пункта отправления (исходный пункт, например место производства) в пункт назначения (склад, цех, грузохранилище). Назначение транспортной задачи – определение объемов перевозок из пунктов отправления в пункты назначения с минимальной суммарной стоимостью перевозок. При этом должны учитываться ограничения, накладываемые на объемы грузов, имеющихся в пунктах отправления (предложения), и ограничения, учитывающие потребность грузов в пунктах назначения (спрос). В транспортной модели предполагается, что стоимость перевозки по какому-либо маршруту прямо пропорциональна объему груза, перевозимого по этому маршруту. В общем случае транспортную модель можно применять для описания ситуаций, связанных с управлением запасами, управлением движением капиталов, составлением расписаний, назначением персонала и др.

На рис. 2.3 показано представление транспортной задачи в виде сети с т пунктами отправления и п пунктами назначения, которые показаны в виде узлов сети. Дуги, соединяющие узлы сети, соответствуют маршрутам, связывающим пункты отправления и назначения. С дугой (i, j), соединяющей пункт отправления i с пунктом назначения j, соотносятся два вида данных: (1) стоимость с_ij перевозки единицы груза из пункта i в вы пункт j и (2) количество перевозимого груза х_ij. Объем грузов в пункте отправления i равен а_i, а объем грузов в пункте назначения j – b_j Задача состоит в определении неизвестных величин х_ij, минимизирующих суммарные транспортные расходы и удовлетворяющих ограничениям, накладываемым на объемы грузов в пунктах отправления (предложения) и пунктах назначения (спрос).

Рисунок 2.3 – Транспортная задача в виде сети

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

Алгоритм решения транспортной задачи будет проиллюстрирован на следующем примере.

Пример

Транспортная компания занимается перевозкой грузов от трех пунктов отправления к четырем пунктам назначения. На рис. 2.4 показаны возможности отгрузки (предложения) пунктов отправления (сладов) (в тоннах) и потребности (спрос) пунктов назначения (заводы) (также в тоннах), а также стоимость перевозки продукции одной машиной от складов к заводам. Стоимость перевозок с_ij приведена в сотнях гривен.

В данной задаче требуется определить структуру перевозок между складами и заводами с минимальной стоимостью. Для этого необходимо найти объемы перевозок х_ij между i -м складом и j -м заводом.

Рисунок 2.4 – Исходные данные для решения транспортной задачи

Последовательность шагов алгоритма решения транспортной задачи в точности повторяет аналогичную последовательность этапов симплексного алгоритма.

Шаг 1. Определяем начальное базисное допустимое решение, затем переходим к выполнению второго шага.

Шаг 2. На основании условия оптимальности симплекс-метода среди всех небазисных переменных определяем вводимую в базис. Если все небазисные переменные удовлетворяют условию оптимальности, вычисления заканчиваются; в противном случае переходим к третьему шагу.

Шаг 3. С помощью условия допустимости симплекс-метода среди текущих базисных переменных определяем исключаемую. Затем находим новое базисное решение. Возвращаемся ко второму шагу. Рассмотрим каждый описанный шаг в отдельности.

Общая транспортная модель с т пунктами отправления и п пунктами назначения имеет т + п ограничений в виде равенств, по одному на каждый пункт отправления и назначения. Поскольку транспортная модель всегда сбалансирована (сумма предложений равна сумме спроса), одно из этих равенств должно быть избыточным. Таким образом, транспортная модель имеет т + п –1 независимых ограничений, отсюда вытекает, что началь­ное базисное решение состоит из т + п – 1 базисных переменных. Например, начальное решение в примере содержит 3+4–1=6 базисных переменных.

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

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

2. Метод наименьшей стоимости.

3. Метод Фогеля.

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

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

Выполнение начинается с верхней левой ячейки (северо-западного угла) транспортной таблицы, т.е. с переменной х₁₁.

Шаг 1. Переменной х₁₁ присваивается максимальное значение, допускаемое ограничениями на спрос и предложение.

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

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

Если применить описанную процедуру к задаче из примера, получим начальное базисное решение, показанное на рис.2.5. На этом рисунке стрелками показана последовательность определения базисных переменных.

Рисунок 2.5 – Метод северо-западного угла

Получено следующее начальное базисное решение:

Соответствующая суммарная стоимость перевозок равна

.

Метод наименьшей стоимости.

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

Применим метод наименьшей стоимости к задаче из примера.

1. Ячейка (1:2) имеет наименьшую в таблице стоимость (=2). Наибольшее значение, которое можно присвоить переменной х₁₂, равно 15. В этом случае удовлетворяются ограничения, соответствующие первой строке и второму столбцу. Вычеркиваем второй столбец, предложение первой строки и спрос второго столбца принимают нулевые значения.

2. Следующей ячейкой с наименьшей стоимостью в незачеркнутой части таблицы будет (З:1). Присвоим переменной х₃₁, значение 5 и вычеркнем первый столбец. Ограничение по предложению, соответствующее третьей строке, станет равным 10– 5 = 5.

3. Продолжая процедуру, последовательно присваиваем переменной х₂₃ значение 15, переменной х₁₄ – значение 0; далее находим х₃₄ = 5 и х₂₄ = 10.

Процесс поиска начального решения представлен на рис.2.6. Стрелками показана последовательность присвоения переменным значений.

Итак, получили следующее начальное базисное решение (состоящее из 6 переменных):

Соответствующее значение целевой функции равно

Рисунок 2.6 – Метод наименьшей стоимости

Отсюда следует, что полученное методом наименьшей стоимости начальное решение лучше, чем начальное решение, представленное методом северо-западного угла (сравните данное значение целевой функции с аналогичным значением из примера).

Метод Фогеля.

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

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

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

Шаг 3. 1) Если не вычеркнута только одна строка или только один столбец с нулевым спросом или предложением, вычисления заканчиваются.

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

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

4) Во всех остальных случаях необходимо перейти к шагу 1.

Применим метод Фогеля к задаче из примера. На рис. 2.7 показан первый набор вычисленных штрафов.

Рисунок 2.7 – Метод Фогеля. Первый набор вычисленных штрафов

Поскольку третья строка имеет наибольший штраф (= 10) и в этой строке наименьшая стоимость содержится в ячейке (3:1), присваиваем переменной х₃₁ значение 5. В этом случае полностью выполняется ограничение первого столбца, его вычеркиваем. Новый набор пересчитанных штрафов показан на рис. 2.8.

Рисунок 2.8 – Метод Фогеля. Пересчитанные значения штрафов

Теперь первая строка имеет наибольший штраф (= 9). Поэтому мы присваиваем значение 15 переменной х₁₂, которой соответствует минимальная стоимость в первой строке. В этом случае одновременно выполняются ограничения и для первой строки, и для второго столбца. Вычеркнем второй столбец, положив объем предложений, соответствующий первой строке, равным нулю.

Продолжая этот процесс, находим, что на следующем шаге вторая строка будет иметь наибольший штраф (20; 9; 11). Поэтому переменной х₂₃ присваиваем значение 15. В результате будет вычеркнут третий столбец, во второй строке останется нереализованным предложение объемом в 10 единиц. Остается невычеркнутым только четвертый столбец с положительным неудовлетворенным спросом объемом в 15 единиц. Применяя метод наименьшей стоимости к этому столбцу, последовательно получаем х₁₄ = 0, х₃₄ = 5 и х₂₄ = 10.

Соответствующее значение целевой функции равно

.

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