транспортной задачи

Дата добавления: 2014-11-24 | Просмотров: 1640

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

В качестве критерия эффективности (оптимальности) берется либо минимальная стоимость перевозок, либо минимальное время доставки груза.

Пример 5. На трех оптовых базах А₁, А₂, А₃ находится однородный груз в количестве единиц. Этот груз необходимо развести четырем потребителям B₁, B₂, B₃, B₄, потребности которых в данном грузе составляют единиц, соответственно. Каждому потребителю сырье может завозиться из любой оптовой базы. Тарифы на перевозку единицы продукции от каждого поставщика А_i каждому потребителю B_j являются известными величинами и задаются матрицей стоимостей

, где

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

Решение.

1). Построение экономико-математической модели.

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

Поскольку имеются ограничения на наличие груза у поставщиков, то переменные должны удовлетворять условиям на вывоз всего груза:

Условия доставки всего груза потребителям:

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

Суммарные затраты на перевозку всего груза составят:

Итак, требуется найти такой план перевозок, удовлетворяющий системе линейных уравнений (1), (2), условию неотрицательности (3), при котором функция (4) принимает минимальное значение.

Исходные данные задачи удобно представить в виде распределительной табл. 12.

Таблица 12

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

Если общие запасы продукта у поставщиков равны общим потребностям в грузе у потребителя, т.е.

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

Для разрешимости транспортной задачи необходимо и достаточно, чтобы общие запасы в пунктах отправления были равны потребностям в грузе в пунктах назначения, т.е. выполнялось равенство (5).

Открытая модель транспортной задачи решается приведением к закрытой модели. В случае превышения суммарных запасов над потребностью, т.е. , вводится фиктивный (n+1)-й пункт потребления В_n+1 с потребностью, равной и соответствующими равными нулю тарифами: . Аналогично, при вводится фиктивный (m+1)-й пункт отправления (база А_m+1) с запасом продукта и тарифами .

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

Таблица 13

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

2).Определение базисного плана транспортной задачи.

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

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

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

Определить допустимый опорный план можно одним из методов: методом минимального тарифа, методом аппроксимации Фогеля или северо-западного угла.

Метод минимального тарифа.

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

В нашем случае минимальный тариф, равный 1, находится в клетке , т.е. в первой строке и третьем столбце (табл. 14). Так как запасы поставщика А₁ (а₁=170) меньше, чем потребности потребителя В₃ (b₃=200), то запишем значение 170 в эту клетку и исключим временно из рассмотрения базу А₁, так как запасы ее исчерпаны. Потребности поставщика B₃ стали равными 200 – 170 = 30. С экономической точки зрения это означает, что из пункта А₁ в пункт B₃ планируется перевезти сырье в количестве 170 единиц.

Таблица 14

В оставшейся таблице клетка с наименьшим тарифом находится на пересечении строки А₃ и столбца B₂, где = 2. Запасы оптовой базы А₃ больше потребностей пункта B₂, поэтому поместим в клетку 60 единиц груза. При этом пункт потребления В₂ временно исключаем из рассмотрения, так как потребности его удовлетворены полностью, запас базы А₃ считаем равными 180 – 60 = 120 (табл. 15).

Таблица 15

В оставшейся части таблицы минимальная стоимость находится в клетке . Поместим в эту клетку 30 ед. груза, удовлетворив потребности пункта B₃ (табл. 16), уменьшив запасы поставщика A₃ до 120 – 30 = 90 единиц.

Таблица 16

Затем заполняем клетку , удовлетворив потребности пункта B₁ на125 и уменьшив запасы оптовой базы A₂ до 150 – 125 = 25 единиц (табл. 17).

Таблица 17

Из оставшейся части таблицы сначала заполняем клетку , поместив 25 единиц груза, использовав полностью запасы пункта A₂, а затем оставшуюся клетку , записав значение 90 (табл. 18).

Таблица 18

В результате получим опорный план:

.

При данном плане перевозок общая стоимость составляет:

.

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

При решении задачи вручную все действия производятся на одной таблице.

Метод аппроксимации Фогеля.

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

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

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

В нашем случае для каждой строки и столбца таблицы условий найдем разности между двумя минимальными тарифами, записанными в данной строке или столбце, и поместим их в соответствующем первом дополнительном столбце или первой дополнительной строке табл. 19. Так, в строке А₁ минимальный тариф равен 1, а следующий за ним равен 2, разность между ними . Точно так же разность между минимальными тарифами в столбце В₁ равна . Вычислив аналогично все разности, видим, что наибольшая из них равна 4, что находится в столбце В₄. В этом столбце минимальный тариф записан в клетке , находящейся на пересечении строки А₁ и столбца В₄. Заполняем эту клетку. Так как потребности потребителя В₄ (b₄=115) меньше, чем запасы поставщика А₁ (а₁=170), то запишем в нее значение 115, тем самым удовлетворив потребности пункт потребления В₄. Поэтому исключим из рассмотрения столбец В₄, и будем считать запасы пункта А₁ равными ед.

Таблица 19

После этого определяем следующую клетку для заполнения. Снова находим разности между двумя минимальными тарифами в каждой из строк и столбцов оставшейся части таблицы и записываем их во втором дополнительном столбце и во второй дополнительной строке табл. 19. Наибольшая указанная разность равна 6 и соответствует строке А₁. Минимальный тариф в этой строке записан в клетке, которая находится на пересечении ее со столбцом В₃. Следовательно, заполняем эту клетку. Поместим в нее число 55, тем самым получаем, что запасы базы А₁ полностью исчерпаны, а потребности пункта потребления В₃ стали равными ед. Исключим из рассмотрения строку А₁ и определим новую клетку для заполнения. Наибольшая разность соответствует столбцу В₃. Минимальный тариф находится к клетке , помещаем в нее 145 ед. и исключаем из рассмотрения столбец В₃, так как потребности пункта потребления В₃ удовлетворены. При этом запасы пункта А₃ стали равными ед.

Продолжая итерационный процесс, последовательно заполняем клетки, находящиеся на пересечении строки А₃ и столбца В₂, строки А₂ и столбца В₁ строки А₂ и столбца В₂.

В результате получим опорный план: .

При этом плане общая стоимость перевозок такова:

.

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

3). Нахождение оптимального плана транспортной задачи.

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

, если ; (для занятых клеток)

или

, если . (для свободных клеток)

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

Для всех занятых клеток опорного плана, найденного методом минимального элемента (табл. 18), составляем уравнение вида :

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

Пусть , тогда получим:

, , ,

, , .

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

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

В данной задаче для клетки условие не выполняется, следовательно, построенный план перевозок не является оптимальным. Стоимость перевозок уменьшится, если перераспределить груз для потребителей так, чтобы некоторую его часть транспортировать из пункта A₁ в пункт B₄. В табл. 20 клетку помечаем знаком «+» и строим цикл перераспределения поставок.

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

Если ломаная линия, образующая цикл, пересекается, то точки пересечения не являются вершинами. В нашей задаче цикл имеет следующий вид (табл. 20):

Таблица 20

Поставщик	Потребитель	Запасы ai
B1	B2	B3	B4
A1					-		Å
A2
A3					+		-
		30
Потребности bj

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

1). Каждой из клеток, связанных циклом, приписываем определенный знак «+» или «-», начиная со свободной клетки. Клетки, отмеченные знаком «+» назовем загружаемой клеткой, знак «-» - разгружаемой.

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

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

Таблица 21

.

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

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

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

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

Полагая , находим, что . Далее, для свободных клеток проверяем, будут ли выполняться соотношение :

Таким образом, для клетки условие не выполняется, из чего мы заключаем, что базисный план не оптимален. Стоимость перевозок можно уменьшить, если перераспределить груз для потребителей так, чтобы некоторую его часть транспортировать из пункта А₂ в пункт В₂. Отметим клетку знаком «+» и построим цикл перераспределения (табл. 22), который начинается и заканчивается в данной клетке.

Таблица 22

Поставщик	Потребитель	Запасы ai
B1	B2	B3	B4
A1					-		+
A2
	Å		- 25
A3
	60 -	+ 120
Потребности bj

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

Таблица 23

.

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

Полагая , находим, что .

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

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

.

Минимальная общая стоимость перевозок .