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

4.1. Формализация распределительной задачи

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

Имеется m поставщиков А₁, А₂, … , А_m с запасами груза соответственно a₁, a₂, …, a_m и n потребителей В₁, В₂, …, В_n с потребностями соответственно

b₁, b₂, …, b_n. Стоимость перевозки единицы груза от i-го поставщика к j-му потребителю составляет с_ij. Необходимо организовать план перевозок груза (x_ij) от поставщиков к потребителям, чтобы полностью удовлетворить спрос потребителей, вывезти все запасы поставщиков и при этом стоимость перевозок была минимальной.

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

Таблица 1

Потреби-тели Постав-щики	В1	В2	…	Вn	Запасы
А1	с11 х11	с12 х12	…	с1n х1n	a1
А2	с21 х21	с22 х22	…	с2n х2n	a2
…	…	…	…	…	…
Аm	сm1 хm1	сm2 хm2	…	сmn хmn	am
Потребности	b1	b2	…	bn	Σai = Σbj

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

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

Поскольку от i-го поставщика к j-му потребителю запланировано перевезти х_ij единиц груза, стоимость данной перевозки составит с_ijх_ij. Стоимость всего плана выразится двойной суммой :

.

Систему ограничений получим из следующих условий задачи:

1. Все запасы должны быть вывезены:

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

2. Все потребности должны быть удовлетворены:

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

3. Обратные перевозки не имеют смысла:

x_ij  0 (i = 1, 2,…, m; j = 1, 2,…, n).

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

Введем следующую терминологию.

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

Совокупность значений X = {x_ij, i = 1,…, m, j = 1,…, n} называется планом перевозок.

Допустимый план X называется опорным, если в нем отличны от нуля не более чем r = m + n – 1 элементов, а остальные элементы равны нулю.

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

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

Тарифом называется стоимость перевозки единицы груза от i-го поставщика к j-му потребителю.

План транспортной задачи, содержащий не менее m+n–1 ненулевых компонент, называют невырожденным.

Для построения первоначального опорного плана, содержащего не более m+n–1 ненулевых компонентов, можно использовать метод «северо-западного угла» и метод наилучшего элемента.