Транспортная Задача Линейного Программирования

Под названием транспортная задача объединяется широкий круг задач с единой матетической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены известным симплексным методом. Однако, обычная транспортная задача имеет большое число переменных и решение ее симплексным методом громозко. С другой стороны матрица системы ограничений транспортной задачи весьма своеобразна, поэтому для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить последовательность опорных решений, которая завершается оптимальным решением.

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

Условие:
Однородный груз сосредоточен у 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 потребителей полностью и имеет вид:

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

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

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

• Примеры Решения Задач Линейного Программирования
• Двойственная Задача Линейного Программирования
• Транспортные Задачи Линейного Программирования