Под названием транспортная задача объединяется широкий круг задач с единой матетической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены известным симплексным методом. Однако, обычная транспортная задача имеет большое число переменных и решение ее симплексным методом громозко. С другой стороны матрица системы ограничений транспортной задачи весьма своеобразна, поэтому для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить последовательность опорных решений, которая завершается оптимальным решением.
Общая характеристика транспортной задачи
Условие:
Однородный груз сосредоточен у m поставщиков в объемах a1, a2, ... am.
Данный груз необходимо доставить n потребителям в объемах b1, b2 ... bn.
Известны Cij , i=1,2,...m; j=1,2,...n – стоимости перевозки единиц груза от каждого i-го поставщика каждому j-му потребителю.
Требуется составить такой план перевозок, при котором запасы всех поставщиков вывозятся полностью, запросы всех потребителей удовлетворяются полностью, и суммарные затраты на перевозку всех грузов являются минимальными.
Исходные данные транспортной задачи записываются в виде таблицы:
Исходные данные задачи могут быть представлены в виде:
- вектора А=(a1,a2,...,am) запасов поставщиков
- вектора B=(b1,b2,...,bn) запросов потребителей
- матрицы стоимостей:
Математическая модель
Переменными (неизвестными) транспортной задачи являются xij , i=1,2,...,m j=1,2,...,n – объемы перевозок от i-го поставщика каждому j-му потребителю.
Эти переменные могут быть записаны в виде матрицы перевозок:
Так как произведение Cij*Xij определяет затраты на перевозку груза от i-го поставщика j-му потребителю, то суммарные затраты на перевозку всех грузов равны:
По условию задачи требуется обеспечить минимум суммарных затрат.
Следовательно, целевая функция задачи имеет вид:
Система ограничений задачи состоит из двух групп уравнений.
Первая группа из m уравнений описывает тот факт, что запасы всех m поставщиков вывозятся полностью и имеет вид:
Вторая группа из n уравнений выражает требование удовлетворить запросы всех n потребителей полностью и имеет вид:
Учитывая условие неотрицательности объемов перевозок математическая модель выглядит следующим образом:
В рассмотренной модели транспортной задачи предполагается, что суммарные запасы поставщиков равны суммарынм запросам потребителей, т.е.:
Такая задача называется задачей с правильным балансом, а модель задачи закрытой. Если же это равенство не выполняется, то задача называется задачей с неправильным балансом, а модель задачи – открытой.
Математическая формулировка транспортной задачи такова: найти переменные задачи X=(xij), i=1,2,...,m; j=1,2,...,n, удовлетворяющие системе ограничений (цифра 2 на математической модели) , (3), условиям неотрицательности (4) и обеспечивающие минимум целевой функции (1)
Составить математическую модель транспортной задачи, исходные данные которой приведены в таблице 34.2
Решение:
1. Вводим переменные задачи (матрицу перевозок):
2. Записываем матрицу стоимостей:
3. Целевая функция задачи равняется сумме произведений всех соответствующих элементов матриц C и X.
Данная функция, определяющая суммарные затраты на все перевозки, должна достигать минимального значения.
4. Составим систему ограничений задачи.
Сумма всех перевозок, стоящих в первой строке матрицы X, должна равняться запасам первого поставщика, а сумма перевозок во второй строке матрицы X равняться запасам второго поставщика:
Это означает, что запасы поставщиков вывозятся полностью.
Суммы перевозок, стоящих в каждом столбце матрицы X, должны быть равны запросам соответствующих потребителей:
Это означает, что запросы потребителей удовлетворяются полностью.
Необходимо также учитывать, что перевозки не могут быть отрицательными:
Ответ: Таким образом, математическая модель рассматриваемой задачи записывается следующим образом:
Найти переменные задачи, обеспечивающие минимум целевой функции (1) и удовлетворяющие системе ограничений (2) и условиям неотрицательности (3).