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

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

.

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

.

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

, i = 1, 2, ..., m.

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

, j = 1, 2, ..., n.

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

, (6.1)

, i = 1, 2, ..., m, (6.2)

, j = 1, 2, ..., n, (6.3)

, i = 1, 2, ..., m; j = 1, 2, ..., n. (6.4)

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

. (6.5)

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

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

, i = 1, 2, ..., m; j = 1, 2, ..., n,

удовлетворяющие системе ограничений (6.2), (6.3), условиям неотрицательности (6.4) и обеспечивающие минимум целевой функции (6.1).

Математическая модель транспортной задачи может быть записана в векторном виде. Для этого рассмотрим матрицу А системы уравнений-ограничений задачи (6.2), (6.3):

. (6.6)

Сверху над каждым столбцом матрицы указана переменная задачи, коэффициентами при которой являются элементы соответствующего столбца в уравнениях системы ограничений. Каждый столбец матрицы А, соответствующий переменной , является вектором-условий задачи и обозначается через . Каждый вектор имеет всего m + n координат и только две из них, отличные от нуля, равны 1. Первая единица вектора стоит на i-м месте, а вторая единица на (m + j)-м месте, т. е.

номер

координаты

.

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

, (6.7)

, (6.8)

, i = 1, 2, ..., m; j = 1, 2, ..., n. (6.9)

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

Т а б л и ц а 6.2

Решение. Вводим переменные задачи (матрицу перевозок)

.

Запишем матрицу стоимостей

.

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

.

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

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

Это означает, что запасы поставщиков вывозятся полностью.

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

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

, i = 1, 2, ..., m; j = 1, 2, ..., n.

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

Найти переменные задачи, обеспечивающие минимум функции

и удовлетворяющие системе ограничений

и условиям неотрицательности

, i = 1, 2, ..., m; j = 1, 2, ..., n.