Практическая работа № 6.1. « Транспортная задача. Метод Северо-западного угла»

Цель работы:

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

Предположим, что существуют N потребителей и M поставщиков некоторого однородного груза, у каждого из поставщиков определенный запас этого груза (A_i единиц, i=1,2,…,M), а каждому из потребителей требуется B_j единиц груза (j=1,2,…, N). Известны также затраты c_ij на перевозку единицы груза от поставщика A_i к потребителю B_j. Требуется составить такой план перевозок от поставщиков к потребителям, чтобы суммарные затраты на перевозки оказались минимальными (при этом должны быть по возможности вывезены все запасы поставщиков и удовлетворены все запросы потребителей).

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

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

При составлении математической модели через x_ij обозначается количество единиц груза, который будет перевезен от поставщика A_i к потребителю B_j (объем перевозок от A_i к B_j). Эти значения будут вноситься в центр соответствующей ячейки.

Итак, задача ставится следующим образом. Найти объемы перевозокдля каждой пары “поставщик — потребитель ” так, чтобы:

1) мощности всех поставщиков были реализованы;

2) спросы всех потребителей были удовлетворены;

3) суммарные затраты на перевозку были бы минимальны.

Рассмотрим закрытую транспортную задачу. Являясь задачей линейного программирования, транспортная задача может быть решена симплексным методом. Однако специфичная форма системы ограничений данной задачи позволяет существенно упростить обычный симплексный метод. Модификация симплексного метода применительно к транспортной задаче называется распределительным методом.

Заметим, что суммарные запасы (30+190+250=470) равны суммарным запросам (70+120+150+130=470). Разместим в основной (незаштрихованной) части таблицы искомые объемы перевозок x_ij и перейдем к составлению математической модели. Заметим, что нумерация соответствует привычной нумерации элементов в матрицах (i – номер строки, j – номер столбца). Итак, целевая функция принимает вид

(6.1.1)

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

(6.1.2)

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

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

Построение начального опорного решения. Рассмотрим два основных приема для задач с правильным балансом. Первый из них имеет более простой алгоритм, а второй дает решение, более близкое к оптимальному (Этот прием рассмотрим в практической работе № 6. Часть 2).

Метод северо-западного угла. Основная идея заключается в том, вычисление значений x_ij начинается с верхней левой клетки (северо-западный угол таблицы). Из значений запасов и запросов, ей соответствующих (A₁ и B₁) выбираем минимальное – это и будет объем перевозок x₁₁. При этом либо удовлетворены все запросы (и тогда из рассмотрения исключается потребитель, при этом в таблице в оставшихся ячейках соответствующего столбца ставятся прочерки, а объем запасов в соответствующей строке уменьшается на это значение), либо вывезены все запасы (из рассмотрения исключается поставщик, прочерки ставятся в строке и уменьшается объем запросов). В случае, когда A₁ = B₁, вычеркивается либо строка, либо столбец (но не строка и столбец одновременно! ) Далее действия повторяются со следующей ячейкой, которая оказалась верхней левой – и так до момента, пока не окажется, что все запасы вывезены, а все запросы удовлетворены. При этом клетки, в которые попали значения x_ij,, называются занятыми.

Внимание! Во избежание ошибок необходимо убедиться в том, что число занятых клеток равно M+N-1; в противном случае построенное начальное решение не будет опорным. При этом необходимо помнить, что, в силу сформулированного правила выбора объема перевозок, в занятых клетках могут оказаться значения, равные нулю!

Пример 5.2. Ниже в таблицах 6.1.2-6.1.7 приводится пошаговое построение методом северо-западного угла начального опорного решения для закрытой задачи из примера 6.1.1.; объемы перевозок внесены в таблицы жирным курсивным шрифтом.

Итак, заняты 6 ячеек: (1;1), (2;1), (2;2), (2;3), (3;3) и (3;4) (здесь, как и всюду далее, в «адресе» ячейки первым указан номер строки, вторым – номер столбца, заголовки в нумерации не учитываются). Количество занятых ячеек совпадает с числом M+N-1=3+4-1=6. Мы построили начальное опорное решение X₁, остается найти значение целевой функции для этого опорного решения (в свободных клетках, т.е. клетках с прочерками, значение объема перевозок считается равным нулю и потому на результат вычисления не влияет):

.