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

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

Рассмотрим транспортную задачу:

Однородный груз сосредоточен у m поставщиков в объемах . Данный груз необходимо доставить n потребителям в объемах . Известны ( , ) — стоимости перевозки единицы груза от каждого i-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок, при котором запасы всех поставщиков вывозятся полностью, запросы всех потребителей удовлетворяются полностью и суммарные затраты на перевозку всех грузов минимальны.

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

			…
			…
			…
…	…	…	…	…
			…

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

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

(1)

, (2)

, . (3)

, , . (4)

Целевая функция задачи (1) выражает требование обеспечить минимум суммарных затрат на перевозку всех грузов. Первая группа из т уравнений (2) описывает тот факт, что запасы всех т поставщиков вывозятся полностью. Вторая группа из п уравнений (3) выражает требование полностью удовлетворить запросы всех п потребителей. Неравенства (4) являются условиями неотрицательности всех переменных задачи.

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

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

(5)

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

Для того чтобы транспортная задача линейного программирования имела решение, необходимо и достаточно, чтобы суммарные запасы поставщиков равнялись суммарным запросам потребителей (см. равенство (5)), т.е. задача должна быть с правильным балансом.

Дата добавления: 2015-07-26; просмотров: 150; Нарушение авторских прав

Мы поможем в написании ваших работ!