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

Відноситься до задач лінійного програмування. В загальному вигляді транспортна задача може бути сформульована в наступному вигляді:

В заданих m пунктах виробництва (фабриках, заводах) А₁, А₂, ..., А_m виготовляється деякий однорідний продукт в кількостях а₁, а₂, ..., а_m . Цю продукцію необхідно доставити в n заданих пунктів призначення (склади, магазини) В₁, В₂, ..., В_n в кількостях b₁, b₂, …, b_n. Вартість перевозки одиниці вантажу з пункту а_і в пункт b_j відома і дорівнює с_ij, а відповідна кількість вантажу, який перевозиться з пункту а_і в пункт b_j позначають x_ij.

Сукупність m´n чисел x_ij , тобто матрицю називають планом перевозок, а матрицю матрицею транспортних витрат.

План називається допустимим, якщо числа x_ij задовольняють наступним умовам:

x_ij ³ 0 (i =1, m; j = 1, n )

в яких перші m рівнянь означають, що з кожного пунктах виробництва вивозиться весь виготовлений продукт, а останні n рівнянь означають, що потреби всіх споживачів повністю задовольняються.

Транспортна задача полягає в знаходженні серед допустимих планів x_ij такого, який мінімізував би загальну вартість перевозок, тобто треба знайти оптимальний план перевозок, при якому весь продукт з пунктів виробництва буде вивезено, а запити споживачів повністю задоволені і сумарні транспортні витрати були б мінімальні.

В загальному вигляді умова транспортної задачі виглядає таким чином:

Задана матриця перевозок:

С_{ij =}

Знайти матрицю транспортних витрат:

X_ij =