Транспортная задача

Пример

Имеется три поставщика и четыре потребителя некоторого товара. Запасы поставщиков, запросы потребителей, а также стоимости перевозок 1 ед. товара от каждого поставщика к каждому потребителю приведены в таблице:

	Запросы потребителей
Запасы поставщиков

Определить объемы перевозок для каждой пары «поставщик – потребитель» так, чтобы суммарные затраты на перевозку были бы минимальны.

Поскольку суммарные запросы покупателей (1200 ед. продукции) совпадают с суммарной мощностью поставщиков (1200 ед. продукции), то потребуем выполнение следующих условий:

1) мощности (запасы) всех поставщиков были реализованы,

2) запросы всех потребителей были удовлетворены,

Составим математическую модель задачи.

Пусть x_ij − объем перевозки от - го поставщика к - му потребителю

Тарифы перевозок образуют матрицу тарифов:

Используя данные в матрице, запишем целевую функцию данной задачи:

Согласно условиям 1) и 2) необходимо выполнить

а) ограничения по запасам поставщиков:

,

,

;

б) ограничения по запросам потребителей:

,

,

,

.

Дополнительное требование неотрицательности:

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

Общий вид транспортной задачи:

	Запросы потребителей
Запасы поставщиков

Определить объемы перевозок для каждой пары «поставщик – потребитель» так, чтобы суммарные затраты на перевозку были бы минимальны.

Определение. Если сумма запасов груза равна суммарной потребности в нем, т.е.

то транспортная задача называется закрытой.