11. Общая характеристика транспортной задачи

Условие: Однородный груз сосредоточен у m поставщиков в объемах a₁, a₂, ... a_m. Данный груз необходимо доставить n потребителям в объемах b_1, b₂ ... b_n. Известны C_ij , i=1,2,...m; j=1,2,...n — стоимости перевозки единиц груза от каждого i-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок, при котором запасы всех поставщиков вывозятся полностью, запросы всех потребителей удовлетворяются полностью, и суммарные затраты на перевозку всех грузов являются минимальными.

Исходные данные транспортной задачи записываются в виде таблицы:

Исходные данные задачи могут быть представлены в виде:

• вектора А=(a₁,a₂,...,a_m) запасов поставщиков

• вектора B=(b₁,b₂,...,b_n) запросов потребителей

• матрицы стоимостей:

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

Переменными (неизвестными) транспортной задачи являются x_ij , i=1,2,...,m j=1,2,...,n — объемы перевозок от i-го поставщика каждому j-му потребителю. Эти переменные могут быть записаны в виде матрицы перевозок:

Так как произведение C_ij*X_ij определяет затраты на перевозку груза от i-го поставщика j-му потребителю, то суммарные затраты на перевозку всех грузов равны:

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

Система ограничений задачи состоит из двух групп уравнений. Первая группа из m уравнений описывает тот факт, что запасы всех m поставщиков вывозятся полностью и имеет вид:

Вторая группа из n уравнений выражает требование удовлетворить запросы всех n потребителей полностью и имеет вид:

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

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

Такая задача называется задачей с правильным балансом, а модель задачи закрытой. Если же это равенство не выполняется, то задача называется задачей с неправильным балансом, а модель задачи — открытой.

Математическая формулировка транспортной задачи такова: найти переменные задачи X=(x_ij), i=1,2,...,m; j=1,2,...,n, удовлетворяющие системе ограничений (цифра 2 на математической модели) , (3), условиям неотрицательности (4) и обеспечивающие минимум целевой функции (1)

Пример 34.1

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

Решение: 1. Вводим переменные задачи (матрицу перевозок): 2. Записываем матрицу стоимостей:

3. Целевая функция задачи равняется сумме произведений всех соответствующих элементов матриц C и X.

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

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

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

Необходимо также учитывать, что перевозки не могут быть отрицательными:

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

12. Построение первоначального опорного плана

Для определения опорного плана существует несколько методов: метод северо-западного угла (диагональный метод), метод наименьшей стоимости (минимального элемента), метод двойного предпочтения и метод аппроксимации Фогеля.

Кратко рассмотрим каждый из них.

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

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

3. Метод двойного предпочтения. Суть метода заключается в следующем. В каждом столбце отмечают знаком «√» клетку с наименьшей стоимостью. Затем то же проделывают в каждой строке. В результате некоторые клетки имеют отметку «√√». В них находится минимальная стоимость, как по столбцу, так и по строке. В эти клетки помещают максимально возможные объемы перевозок, каждый раз исключая из рассмотрения соответствующие столбцы или строки. Затем распределяют перевозки по клеткам, отмеченным знаком «√». В оставшейся части таблицы перевозки распределяют по наименьшей стоимости.

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