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

ЛЕКЦИЯ 3

ТРАНСПОРТНАЯ ЗАДАЧА

Постановка задачи. Математическая модель задачи. Характерные особенности транспортной задачи. Методы составления первоначального плана перевозок. Метод потенциалов. Оценочная матрица. Цикл пересчета.

Транспортная задача – это задача о наиболее экономном плане перевозок однородного продукта или взаимозаменяемых продуктов из пунктов производства (отправления) в пункты потребления (назначения).

Транспортная задача является частным типом задачи линейного программирования и формулируется следующим образом. Имеется m пунктов отправления (или пунктов производства) А_i …, А_m, в которых сосредоточены запасы однородных продуктов в количестве a₁, ..., а_m единиц. Имеется n пунктов назначения (или пунктов потребления) В₁, ..., В_m, потребность которых в указанных продуктах составляет b₁, ..., b_n единиц. Известны также транспортные расходы С_ij, связанные с перевозкой единицы продукта из пункта.A_i в пункт В_j, i 1, …, m; j 1, ..., n. Предположим, что

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

Пусть х_ij - количество единиц продукта, поставляемого из пункта А_i в пункт В_j. Подлежащие минимизации суммарные затраты на перевозку продуктов из всех пунктов производства во все пункты потребления выражаются формулой:

Рекомендуемые материалы

                                                                                                   (1)

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

                                                                                  (2)

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

                                                                                 (3)

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

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

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

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

2. Ограничения являются равенствами.

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

                                                                                                 (4)

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

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

Строки транспортной таблицы соответствуют пунктам производства, а столбцы – пунктам потребления. Все клетки таблицы (кроме тех, в которых указаны обозначения поставщиков и их запасы и обозначения потребителей и их потребности) содержат информацию о перевозке из i-го пункта в j-й. В правом верхнем углу находится цена перевозки единицы продукта, а в левом нижнем – значение объема перевозимого груза для данных пунктов (если предполагается перевозка по данному маршруту). Клетки, в которых находятся отличные от нуля перевозки, называются занятыми, остальные свободными.

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

Решение транспортной задачи начинается с построения допустимого базисного плана. Наиболее простой способ его нахождения основывается на так называемом методе северо-западного угла. Суть метода состоит в последовательном распределении всех запасов, имеющихся в первом, втором и т.д. пунктах производства, по первому, второму и т.д. пунктам потребления. Каждый шаг распределения сводится к попытке полного исчерпания запасов в очередном пункте производства или к попытке полного удовлетворения потребностей в очередном пункте потребления. Построение допустимого начального плана, согласно методу северо-западного угла, начинается с левого верхнего угла транспортной таблицы. Для очередной клетки, расположенной в строке i и столбце j, рассматриваются значения нераспределенного запаса в i-ом пункте производства и неудовлетворенной потребности j-ом пункте потребления, из них выбирается минимальное и назначается в качестве объема перевозки между данными пунктами. После этого значения нераспределенного запаса и неудовлетворенной потребности в соответствующих пунктах уменьшаются на данную величину:

Метод северо-западного угла. Пусть условия транспортной задачи заданы табл. 1.

                                                                                                          табл. 1.

Не учитывая стоимости перевозки единицы груза, начинаем удовлетворение потребностей первого потребителя В₁, за счет запаса поставщика A₁. Для этого сравниваем а₁ = 220 с b₁ = 200, а₁ больше b₁, поэтому записываем в левый нижний угол клетки A₁B₁ 200 ед. Потребности первого потребителя полностью удовлетворены, поэтому остальные клетки первого столбца строки прочеркиваем. Сравниваем этот остаток с потребностями В₂: так как 20 < 200, то 20 ед. записываем в клетку А₁В₂ и поскольку запасы А₁ полностью израсходованы оставшиеся клетки в первой строке прочеркиваем.

Потребности В₂ остались неудовлетворенными на 180 ед. Удовлетворяем эти потребности В₂ за счет поставщика А₂. После этого у поставщика А₂ остались 290 – 180 = 110 ед. груза. Из  этого остатка полностью удовлетворяем потребителя В₃: 100 < 110, записываем 100 ед. в клетку А₂В₃ и, так как запасы А₂ израсходованы не полностью, остаток 110 – 100 = 10 отправляем потребителю В₄, записав в клетку А₂В₄ 10 ед. Теперь запасы А₂ полностью израсходованы. Потребности В₄ остались неудовлетворенными на 90 ед. Удовлетворяем их за счет поставщика А₃ и переходим к потребителю В₅, которого полностью удовлетворяем за счет остатка 340 – 90 =250 ед. у поставщика А₃. и т.д. Процесс продолжаем до тех пор, пока не удовлетворим всех потребителей за счет запасов поставщиков. На этом построение первоначального опорного плана заканчивается, т.к. все запасы полностью вывезены, а все потребности полностью удовлетворены.

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

Построенный план является невырожденным, так как он содержит точно т + п – 1=3 + 5 – 1=7 занятых клеток.

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

Найдем общую стоимость составленного плана как сумму произведений объемов перевозок, стоящих в левом углу занятых клеток, на соответствующие стоимости в этих же клетках:

Z=200´10+20´1+180´7+100´10+10´6+90´2+250´5=5770 ед.

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

Метод минимальной стоимости. Суть метода заключается в том, что в транспортной таблице находят клетку (i, j) с наименьшей стоимостью перевозок и помещают в эту клетку меньшее из чисел a_i или b_j. Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы (a_i < b_j), либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены(a_i > b_j), либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя (a_i = b_j). В последнем случае в смежную с заполненной (справа по строке или ниже по столбцу) необходимо поместить нуль, чтобы не получить вырожденный план перевозок. В оставшейся части транспортной таблицы снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.

План, составленный для табл.1,  состоит из семи перевозок, следовательно, является невырожденным опорным планом. Определим его стоимость:

Z=120´1+100´1+50´7+200´2+90´11+80´5+160´5=3160 (ед.).

Стоимость плана перевозок значительно меньше по сравнению с предыдущим планом, следовательно, он ближе к оптимальному.

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

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

В методе потенциалов каждой строке и каждому столбцу транспортной таблицы ставятся в соответствия числа (потенциалы) u_i и v_j. Для каждой занятой клетки потенциалы u_i и v_j должны удовлетворять условию

                                 c_ij = u_i; + v_j                           (*)

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

Шаг 1. Получение начального плана перевозок по методу "северо-западного угла", минимального элемента или любым другим методом.

Шаг 2. Проверка плана на невырожденность. Общее число занятых клеток для невырожденного плана должно быть равно m+n–1. Систему потенциалов можно построить только для невырожденного плана перевозок.

Шаг 3. Проверка плана на оптимальность.

Шаг 3.1. Определение потенциалов строк и столбцов. Для этого приравнивают нулю потенциал какой-либо строки или столбца и вычисляют по формуле (*) потенциалы u_i и v_j остальных строк и столбцов, используя для вычислений только занятые клетки.

Шаг 3.2. Построение оценочной матрицы. Элементы оценочной матрицы (для всех без исключения клеток) определяют по формуле

z_ij = c_ij – (u_i + v_j)

Если оценочная матрица не содержит отрицательных элементов, то полученный план оптимален. Бели хотя бы один элемент оценочной матрицы меньше 0, то план может быть улучшен. Переход к шагу 4.

Шаг 4. Улучшение плана.

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

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

Шаг 4.2. Построение цикла пересчета.

Заполнение клетки, выбранной на шаге 4.1, происходит следующим образом. Строят цикл, начинающийся и заканчивающийся в выбранной свободной клетке, содержащий в качестве вершин заполненные клетки таблицы и состоящий из горизонтальных и вертикальных отрезков. При этом в каждой клетке таблицы, являющейся вершиной цикла, соединяют обязательно горизонтальный и вертикальный отрезки. В свободной клетке условно ставят знак "+", а в остальных вершинах цикла, чередуясь, ставят "–" и "+". Затем происходит перераспределение продукции по циклу. Для этого выбирают клетку со знаком "–", которой соответствует наименьшее число единиц продукции. Это значение прибавляют к значениям, стоящим в клетках со знаком "+", и отнимают от значений, стоящих в клетках со знаком "–". При таком перераспределении общий баланс не изменяется. Свободная клетка заполняется. А клетка со знаком "–" , которой соответствует наименьшее количество продукции, становится свободной. Для проверки нового плана на оптимальность переходят к шагу 2.

Пример 1. Для транспортной задачи (см. табл. 2) составим первоначальный план перевозок по методу минимального элемента и дополним ее столбцом U_i и строкой V_j ,  куда будем записывать потенциалы строк и столбцов.

                                                                                                             табл. 2.

Определим потенциалы столбцов и строк. Выбираем строку, которая содержит наибольшее количество занятых клеток (строка А₃), и полагаем u₃ = 0. В строке A₃ три занятых клетки (A₃B₂, A₃B₃ и A₃B₅), которые связывают соответственно потенциал u₃ с потенциалами v₂, v₃, v₅. Определим эти потенциалы: v₂ = c₃₂ – u₃ = 5 – 0 = 5, v₃ = c₃₃ – u₃ = 3 - 0 = 3, v₅ = c₃₅ – u₃ = 5 – 0 = 5.

Просматриваем столбцы В₂, В₃ и В₅, для которых потенциалы уже определены. В столбце В₂ имеется две занятые клетки (A₁B₂ и A₃B₂), которые связывают потенциал v₂ с потенциалами u₁ и u₃ (u₃ уже определен). Переходим к клетке A₁B₂ и определим неизвестный потенциал: u₁ = c₁₂ – v₂ = 1 – 5 = – 4. В столбце В₃ нет занятых клеток, которые бы связывали v₃ с неизвестными потенциалами строк. Переходим к столбцу В₅. В нем две занятые клетки (A₂B₅ и A₃B₅), которые связывают v₅ с потенциалами u₁ и u₃. Определим неизвестный потенциал: u₂ = c₂₅ – v₅ = 11 – 5 = 6.

Так как известные потенциалы столбцов В₂, В₃ и В₅ использованы, переходим к известным потенциалам строк А₁, А₂.

Потенциал u₁ занятой клеткой A₁B₄ связан с неизвестным потенциалом v₄. Находим этот потенциал: v₄ = c₁₄ – u₁ = 1 – (–4) = 5. Потенциал u₂ занятой клеткой A₂B₁ связан с неизвестным потенциалом v₁. Находим этот потенциал: v₁ = c₂₁ – u₂ = 2 – 6 = -4.

                                                                                                             табл. 3.

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

z_ij = c_ij – (u_i + v_j)

Так как матрица содержит отрицательные элементы, план перевозок не является оптимальным и может быть улучшен. Для улучшения первоначального плана перевозок выбираем клетку транспортной таблицы, которой соответствует наибольший по абсолютной величине отрицательный элемент оценочной матрицы. Это клетка А₂В₄, которую необходимо сделать занятой. Для этого сначала необходимо определить, сколько единиц груза должно быть перераспределено в нее.

Для определения количества единиц груза, подлежащих перераспределению, отмечаем знаком «+» незанятую клетку, которую надо загрузить. Это означает, что клетка присоединяется к занятым клеткам. В таблице занятых клеток стало т + п, поэтому появляется цикл, все вершины которого, за исключением клетки, отмеченной знаком «+», находятся в занятых клетках, причем этот цикл единственный. Отыскиваем цикл и, начиная движение от клетки, отмеченной знаком «+», поочередно проставляем знаки «–» и «+». Среди объемов перевозок, стоящих в клетках, образующих цикл и помеченных знаком «–», выбираем минимальный объем g. Вычитаем g из объемов перевозок, расположенных в клетках, которые отмечены знаком «–», и прибавляем к объемам перевозок, находящихся в клетках, отмеченных знаком «+». Если g соответствуют несколько минимальных перевозок, то при вычитании оставляем в соответствующих клетках нулевые перевозки в таком количестве, чтобы во вновь полученном опорном плане занятых клеток было т + п – 1.

В рассматриваемом примере клетку A₂B₄ отмечаем знаком «+» и для этой клетки строим цикл в следующей последовательности. Из клетки A₂B₄ проводим вертикальный отрезок в клетку A₁B₄ (больше некуда). Из клетки A₁B₄ проводим горизонтальный отрезок в клетку A₁B₂ (больше некуда). Из клетки A₁B₂ проводим вертикальный отрезок в клетку A₃B₂ (больше некуда). Из клетки A₃B₂ проводим горизонтальный отрезок в клетку A₃B₅ (клетка A₃B₃ не подходит, т.к. она единственная в третьем столбце) Из клетки A₃B₅ проводим вертикальный отрезок в клетку A₂B₅ смежную с клеткой A₂B₄. Из клетки A₂B₅ проводим горизонтальный отрезок в клетку A₂B₄ и получаем замкнутый цикл A₂B₄(метка “+”) – A₁B₄(метка “–”) – A₁B₂(метка “+”) – A₃B₂ (метка “–”) – A₃B₅(метка “+”) – A₂B₅(метка “–”) – A₂B₄(метка “+”).

Среди объемов перевозок, стоящих в клетках A₁B₄, A₃B₂, A₂B₅ помеченных знаком «–», выбираем минимальный объем g.

g = min(100, 80, 90) = 80.

Вычитаем g из объемов перевозок, расположенных в клетках, которые отмечены знаком «–», и прибавляем к объемам перевозок, находящихся в клетках, отмеченных знаком «+». В результате получаем новый план перевозок показанный в таблице табл. 7.

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

Z=200´1+20´1+200´2+80´6+10´11+100´3+240´5= 2710 (ед.).

Т.о. стоимость плана перевозок по сравнению с предыдущем снизилась на  3160 – 2710 = 450 ед.

Для плана перевозок, представленного в табл. 4 определяем потенциалы строк и столбцов и формируем оценочную матрицу:

Матрица содержит отрицательный элемент, следовательно, план перевозок может быть улучшен. Для клетки А₁В₅ транспортной таблицы, строим цикл пересчета (табл. 4). Получаем новый план перевозок (табл. 5).

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