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

Транспортная задача является одной из важнейших частных задач линейного программирования. Название свое задача получила потому, что впервые была сформулирована и поставлена для решения вопроса о наиболее рациональном планировании перевозок на транспорте. Название это условно, так как с ее помощью можно решать разнообразные задачи из различных отраслей производства и не обязательно связанных с перемещением. Методы решения транспортной задачи широко применяют на автомобильном, железнодорожном и других видах транспорта для планирования перевозок различных грузов. Это объясняется их простотой и экономическим эффектом, который они дают. Планы перевозок, разработанные на основе алгоритма транспортной задачи, как правило, на 12—18% экономичнее планов, составленных без применения математических методов.

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

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

Сформулируем транспортную задачу.

В лесозаготовительном объединении имеются А₁, А₂,......, Аm лесозаготовительных предприятий {ЛЗП), вырабатывающих технологическую щепу в объеме Q₁, Q₂,.... Qm тысяч кубометров в год. Технологическая щепа должна быть доставлена потребителям (ЦБК) В₁, В₂, ….., Вn, имеющим соответственно объемы потребления Y₁, Y₂. … Yn тысяч ку­бометров в год. Стоимость доставки щепы с каждого ЛЗП каждому потребителю определяется матрицей стоимостей:

(1.1)

Объем выработки щепы всеми ЛЗП равен объему потребления всеми ЦБК:

(1.2)

или

(1.3)

Необходимо определить такое распределение доставки щепы от ЛЗП к потребителям, чтобы общая стоимость транспортных затрат была минимальной:

(1.4)

или

(1.5)

При этом необходимо, чтобы соблюдались условия:

1. Суммарный объем щепы, вывозимой с каждого ЛЗП потребителям, должен равняться его мощности:

(1.6)

или

(1.7)

где i=1,2,……m.

2. Суммарный объем щепы, доставляемой на каждый ЦБК от ЛЗП, должен равняться его потребности:

(1.8)

или

(1.9)

где j=1,2,……n.

3.Объемы доставки щепы не могут быть отрицательными, но могут равняться нулю:

(1.10)

4.Уже известное (1.3)

Математически сформулированная транспортная задача ли­нейного программирования имеет m+n+ 2 уравнений, и m·n+1 неизвестных.

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

Найти минимум функции

(1.11)

При заданных условиях:

(1.12)

(1.13)

(1.14)

(1.15)

Функция называется целевой функцией или

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