Транспортная задача (лекция)

Лекция № 3

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

Содержание лекции:

1. Постановка задачи.
2. Математическая модель задачи.
3. Метод северо-западного угла.
4. Метод наименьшего элемента.
5. Метод Фогеля.
6. Метод потенциалов.

1. 1.      Постановка задачи

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

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

Пусть имеется т поставщиков однородного продукта, которые могут поставить а₁ a₂, ..., а_т единиц этого продукта, и имеется п потребителей с потребностями b?, b₂, ..., b_n  единиц. Известна стоимость с_jk перевозки единицы продукта от j-го поставщика к  k-му потребителю. Требуется спланировать перевозки этого продукта от поставщиков к потребителям так, чтобы удовлетворить потребности всех потребителей, а суммарные затраты на перевозки при этом были бы наименьшими.

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

Транспортную задачу обычно задают в специальной, так называемой распределительной таблице, которая имеет следующий вид:

Говорят, что имеет место открытая модель транспортной задачи, если суммарные ресурсы поставщиков не равны суммарным потребностям потребителей, т.е. если

Если

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

Разрешимой является только закрытая модель или сбалансированная транспортная задача. Чтобы решить несбалансированную транспортную задачу необходимо её сбалансировать, т. е. свести к закрытой модели. В случае, когда запасы в пунктах отправления превосходят потребности всех пунктов назначения, необходимо ввести фиктивного потребителя с потребностью в грузе равной разности общих запасов и общих потребностей. Так как введённый потребитель фиктивный, то все истинные тарифы доставки груза полагают равными нулю.

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

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

Найдем  30+40+30=100,  25+25+30=80.

Так как   , то имеем открытую модель транспортной задачи. Вводим фиктивного поставщика с ресурсом     и получаем закрытую модель транспортной задачи:

1. 2.      Математическая модель задачи

Пусть переменная х_ik (i = 1, 2, ..., т, k = 1, 2,..., п) означает количество продукта, перевозимого от i-го поставщика к k-му потребителю. Тогда суммарные затраты на перевозки продукта от всех поставщиков ко всем потребителям равны

.                           (1)

Необходимо, чтобы величина f была минимальной.

Учтем ограничения задачи. Так как мы имеем закрытую модель, то от каждого поставщика будет вывезен продукт в объеме ресурса этого продукта. Следовательно,

  (i = 1, 2, ..., т).             (2)

Аналогично, каждому потребителю будет доставлен груз в объеме его потребности. Тогда

      (k = 1, 2,..., п).          (3)

Наконец, очевидно, что

х_ik ³0    (i = 1, 2, ..., т, k = 1, 2,..., п).       (4)       

Как видим, задача (1)-(4) есть задача линейного программирования. Поэтому такую задачу можно решать симплексным методом. Но такой метод решения данной задачи довольно громоздкий, так как в транспортной задаче может быть очень большое число переменных. 

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

Один из таких методов есть метод потенциалов. Как и в симплексном методе, этот метод позволяет решать транспортную задачу, последовательно переходя от одного (опорного) решения к другому. Поэтому возникает проблема построения исходного плана перевозок.

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

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

Процесс заполнения каждой клетки распределительной таблицы происходит следующим образом. Находятся два числа, соответствующие рассматриваемой клетке (i, k), - это величина b^*_k неудовлетворенной потребности потребителя и величина а^*_i остаточного ресурса поставщика, которые вычисляются по формулам

а^*_i =а_i -,  b^*_k =b_k -.

Тогда назначаемое количество х_ik перевозимого продукта от i-го поставщика к k-му потребителю будет равно наименьшему из найденных чисел, т.е.

min{ а^*_i , b^*_k ).

Эта величина и записывается в рассматриваемую клетку (i k).

Ясно, что начальное значение  а^*_i =а_i  (i= 1, 2, ..., т) и b^*_k =b_k  (k=1,2,...,n).

После заполнения рассматриваемой клетки (i,k) либо величина неудовлетворенной потребности b_k, либо величина остаточного ресурса а_i поставщика становится равной нулю. В этом случае говорят, что k-й столбец (i-я строка) «закрывается», а i-я строка (k-й столбец) остается «открытой» («открытым») для заполнения. Переходим вдоль открытой строки (открытого столбца) к рассмотрению соседней (i, k+1) клетки (соответственно (i+1, k) клетки).

Рассмотрим процедуру построения исходного плана перевозок на примере.

Пример 1

На три станции А?, А₂, А₃ прибыл некоторый однородный груз, который необходимо перевезти четырем заказчикам В?, В₂, Вз, В₄.

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

Требуется спланировать перевозки груза так, чтобы суммарная стоимость перевозки была наименьшей.

Сначала заполняем клетку (1, 1). Этой клетке соответствуют значения, а₁ =300, b₁ = 250. Следовательно, в рассматриваемую клетку назначаем количество перевозимого груза по данному маршруту, равное min {300,250} = 250.

Так как в результате заполнения клетки (1, 1) 1-й столбец закрывается, а 1-я строка открыта, мы переходим к рассмотрению клетки (1,2). Данной клетке соответствуют значения, а₁ = 300-250=50, b₂ = 200. Следовательно, в рассматриваемую клетку назначаем количество перевозимого груза по данному маршруту, равное min{50, 200} = 50. В  результате заполнения клетки (1, 2) 1-я строка закрывается, а 1-й столбец открыт, переходим к рассмотрению клетки (2,2). Данной клетке соответствуют значения, а₂ = 320, b₂ = 200-50=150. Следовательно, в рассматриваемую клетку назначаем min{320, 150} = 150. В  результате заполнения клетки (2, 2) 2-й столбец закрывается, а 2-я строка открыта, переходим к клетке (2,3).  В рассматриваемую клетку назначаем min{320-150=170, 290} = 170. В  результате заполнения клетки (2, 3) 2-я строка закрывается, а 3-й столбец открыт, переходим к клетке (3,3). В клетку (3,3) назначаем min{380, 290-170=120} = 120. Таким образом, 3-й столбец закрывается, а 3-я строка открыта, переходим к последней клетке (3,4), в которую назначаем min{380-120=260, 260} = 260. В  результате заполнения этой клетки  3-я строка и 4-й столбец закрываются.

Построенный исходный план перевозок представлен в следующей таблице:

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

Заполненную распределительную таблицу следует проверить на вырожденность.  Заметим, что всякий построенный план перевозок должен занимать в распределительной таблице т + n - 1 клеток. Такой план называется невырожденным. Если число занятых клеток распределительной таблицы не равно т + n - 1, то для продолжения решения задачи опорный план необходимо дополнить введением фиктивной перевозки, т. е. занять нулём одну из свободных клеток. Направляем нулевую перевозку в ту клетку, которая не образует с другими занятыми клетками таблицы замкнутого прямоугольного контура.

Таким образом, в нашем примере мы должны иметь 3+4-1 = 6 занятых клеток.

Оценим суммарную стоимость построенного плана:

 = 10·250+4·50+8·150+11·170+7·120+9·260=8950.

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

Пример 2

Задана следующая транспортная задача:

Требуется составить исходный план перевозок по правилу северо-западного угла.

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

x₁₁=min(50; 100)=50 – потребности В1 удовлетворены;

x₁₂=min(50; 100-50=50)=50 – запасы А1 исчерпаны и потребности В2 удовлетворены.

После заполнения второй клетки распределительной таблицы одновременно закрываются как 1-я строка, так и 2-й столбец. Поставим базисный нуль в 1-й закрытой строке:

x₁₃=min(100; 0)=0;

x₂₃=min(100; 100)=100 – запасы А2 исчерпаны и потребности В3 удовлетворены.

После заполнения клетки (2, 3) грузом x₂₃ =100 снова имеем одновременное закрытие строки и столбца. В этом случае мы поставим базисный нуль в 3-м закрытом столбце:

x₃₃=min(0; 100)=0;

x₃₄=min(100; 100)=100  – запасы А3 исчерпаны и потребности В4 удовлетворены.

Проверка числа занятых клеток (3+4-1 = 6) показывает, что исходный план перевозок является невырожденным, а это значит, что исходный план перевозок составлен верно.

1. 4.      Метод наименьшего элемента

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

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

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

Заполнение рассматриваемой клетки происходит так же, как по правилу северо-западного угла - назначаемое количество х_ik перевозимого продукта равно наименьшему из найденных чисел: min{ а^*_i , b^*_k }.

Переход к рассмотрению следующей клетки происходит по «открытому» столбцу или по «открытой» строке. Выбирается клетка с наименьшим значением с_ik.

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

Наименьшее значение с_ik соответствует клетке (2,1), где с₂₁ =1. В данную клетку назначаем перевозку в объеме  х₂₁=min{320,250} =250.

В результате заполнения клетки (2,1) 1-й столбец будет закрыт, а 2-я строка будет открытой. В этой строке - клетки со значениями с₂₂ = 8, с₂₃ = 11 и с₂₄ = 3. Поэтому переходим к рассмотрению клетки с наименьшим значением с₂₄ =3. В клетке (2,4) назначаем перевозку х₂₄ =min {70,260} = 70.

После заполнения клетки (2, 4) 2-я строка закрывается, а 4-й столбец распределительной таблицы остается открытым. В этом столбце имеются две доступные клетки со значениями с₁₄ = 6 и с₃₄ = 9. Выбираем клетку (1,4). В эту клетку назначаем перевозку продукции в объеме х₁₄ = min {300,190} =190.

В результате назначения перевозки по маршруту (1, 4) 4-й столбец будет закрыт, а 1-я строка будет открытой. В этой строке доступны клетки (1, 2) и (1, 3). Клетка (1, 1) недоступна, так как расположена в закрытом столбце. Выбираем клетку (1,2) с с₁₂ =4. В эту клетку назначаем перевозку x₁₂ = min{110,200}=110.

После рассмотрения клетки (1,2) 1-я строка закрывается, а 2-й столбец открыт. В этом столбце доступна только одна клетка (3, 2), так как клетка (2, 2) расположена в закрытой строке. В доступную клетку назначаем перевозку x₃₁ = min {380,90} = 90

В результате 2-й столбец закрывается, а 3-я строка открыта. В этой строке доступна только одна клетка (3, 3), так как все остальные клетки этой строки принадлежат закрытым столбцам. Назначаем перевозку x₃₃ =min {290,290} = 290 и завершаем составление исходного плана перевозок:

Проверяем правильность заполнения распределительной таблицы - число занятых клеток должно быть равным 3 + 4-1 = 6.

Оценим суммарную стоимость построенного плана:

 = 4·110+6·190+1·250+3·70+15·90+7·290=5420.

Очевидно, что полученные затраты на перевозки по плану, составленному по правилу минимального элемента, существенно ниже величины 8950 - затрат по плану, составленному по правилу северо-западного угла.

Заметим, что в общем случае можно подобрать пример, когда затраты по плану перевозок, составленному по правилу северо-западного угла, будут ниже, чем по плану, составленному по правилу минимального элемента. Поэтому в каждом отдельном случае нужно выбрать наиболее эффективное правило для конкретного примера.

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

Рассмотрим шаги получения начального решения задачи методом Фогеля.

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

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

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

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

5 шаг. Соответствующая строка или столбец вычеркивается. Если значение спроса для ячейки (i.j) равно предложению, то вычеркивается строка или столбец на выбор.

6 шаг. В оставшейся матрице для каждой строки и столбца повторяются шаги 1–5.

7 шаг. Процесс считается завершенным, когда реализовано всё предложение и полностью удовлетворён спрос, т. е. пока все грузы не будут развезены по потребителям.

Данный метод в ряде задач приводит к оптимальному плану.

Рассмотрим процедуру построения исходного плана перевозок по методу Фогеля в предыдущей задаче.

На первом шаге заполняем клетку (2, 1) (max Dc_ij = 7 и min c_ij = 1), исключаем 1-ый столбец, отметив в дополнительной строке буквой «В» факт выполнения заказа пункта B₁. Находим новые разности минимальных тарифов по строкам (в столбцах они не изменились) и max Dc_ij =5 во 2-ой строке и min c_ij = 3 в 4-ом столбце. Заполняем клетку (2, 4) и исключаем 2-ю строку и т.д. В конце остается последовательно заполнить клетки 3-ей стррки остатками потребностей в Вз и В₄. Составленный опорный план дает значение

 = 4·200+6·100+1·250+3·70+7·290+9·90=4700.

Таким образом, значение суммарной стоимости, полученной по методу Фогеля, меньше значения, полученного по методу  минимального элемента.

6. Метод потенциалов

Пусть одним из рассмотренных методов найден опорный план, содержащий n+m-1 занятых клеток (в некоторых из них могут стоять нули). Поставим в соответствие каждому пункту отправления A_i некоторое число u_i (i=1,...m) и каждому пункту назначения B_j - число v_j (j=1,...,n). Эти числа назовем потенциалами, соответственно, пунктов отправления и пунктов назначения.

Вопрос об оптимальности опорного плана решает следующая теорема:

Теорема. Если для некоторого плана X* = (x_ij), (i=1,..,m; j=1,..,n) транспортной задачи выполняются условия:

1) u_i + v_j = c _ij для x_ij > 0 ( для занятых клеток),    (5)

2) u_i + v_j £ c _ij для x_ij = 0 ( для свободных клеток),     (6)

то план X* является оптимальным .

Отметим, что система (m+n-1) уравнений содержит (m+n) неизвестных u_i, v_j, и потому, приравнивая одно из них, например u₁, нулю, однозначно определим остальные неизвестные.

Для «улучшения» опорного плана (при невыполнении условия (6)) выбирают свободную клетку с max (u_i + v_j - c_ij) и строят для нее цикл пересчета (сдвига).

Циклом называют замкнутую ломаную линию, все вершины которой лежат в занятых клетках, кроме одной, расположенной в свободной клетке, подлежащей заполнению, а звенья параллельны строкам и столбцам, причем в каждой строке (столбце) лежит не более 2-х вершин. Всем вершинам поочередно приписывают знаки «+» и «-», начиная со свободной клетки.

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

DZ=l , где  - сумма тарифов в положительных вершинах,  - в отрицательных вершинах цикла.

Новый опорный план снова проверяют на оптимальность с помощью системы уравнений потенциалов.

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

Для каждой строки и каждого  столбца последней таблицы найдем потенциалы   и    соответственно. Для этого составим систему уравнений относительно каждой заполненной клетки по формуле

,

где  - стоимость перевозки из пункта А_i  в  пункт  В_j.

   Þ 

Проверим критерий оптимальности для незаполненных клеток:

 ,

где  - стоимость перевозки из пункта А_i  в  пункт  В_j в  незаполненной клетке.

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

Пример 2. Выберем для улучшения опорный план, полученный методом наименьшего элемента.

Для каждой строки и каждого  столбца последней таблицы найдем потенциалы   и    соответственно. Составим систему уравнений:

   Þ 

Проверим критерий оптимальности для незаполненных клеток:

 ,

где  - стоимость перевозки из пункта А_i  в  пункт  В_j в  незаполненной клетке.

В двух клетках (3; 1) и (3; 4) критерий оптимальности нарушается, значит, опорный план не оптимальный. Выберем клетку с максимальной разностью max(15-8=7; 17-9=8)=8. Построим цикл перераспределения перевозок для клетки (3; 4). В клетке (3; 4) поставим знак  «+», в остальных клетках цикла знаки чередуются.

В клетках со знаком «-» найдем минимальный объем перевозки:

Min(190; 90)=90,

т. е. перераспределим по циклу 90 ед. груза: в клетках со знаком «+» прибавим 90, в клетках со знаком «-» вычтем 90.

Получим новый план перевозок:

Этот план перевозок совпадает с планом, полученным методом Фогеля, который является оптимальным. Следовательно, минимальная стоимость перевозок

f_min=4070.

Следует отметить, что  цикл перераспределения перевозок может иметь вид не только прямоугольника, как в рассмотренном примере, но и вид любой замкнутой ломаной линии, как на этом рисунке:

Список литературы

1. Интрилигатор М. Математические методы оптимизации и экономическая теория. М.: Изд. Айрис-Пресс, 2002.

2. Вентцель Е.С. Исследование операций. Задачи, принципы, методология. М.: Высшая школа, 2001.

3. Глухов В.В., Медников М.Д., Коробко С.Б. Математические методы и модели для менеджмента. СПб.: Лань, 2000.

4. Красс М.С., Чупрынов Б.П. Основы математики и ее приложения в экономическом образовании. М.: Изд. ДЕЛО, 2003.

5. Ларичев О.И. Теория и методы принятия решений. М.: Логос, 2000.