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

В общем виде транспортную задачу можно сформулировать следующим образом: в т пунктах отправления А₁...,А_т находится однородный груз, количество которого равно соответственно a₁...a_m единиц. Данный груз необходимо доставить потребителям B₁,..., B_n спрос которых— b₁, ...,b_n. Стоимость перевозки единицы груза из i-го (i = от 1 до m) пункта отправления в j-й (j от 1 до п) пункт назначения равна с_i,j. Необходимо составить план перевозок, который полностью удовлетворяет спрос потребителей в грузе, и при этом суммарные транспортные издержки минимальны.

Математически транспортную задачу можно записать так:

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

Модель транспортной задачи называют закрытой (сбалансированной), если суммарный объем груза, имеющегося у поставщиков, равен суммарному спросу потребителей, т. е. выполняется равенство:

Если для транспортной задачи выполняется одно из условий:

то модель задачи называют открытой (несбалансированной).

Для разрешимости транспортную задачу с открытой моделью следует преобразовать в закрытую.

Так, если выполняется условие т о необходимо ввести фиктивный (n + 1)-й пункт назначения В _п+1, т. е. в матрицу задачи вводится дополнительный столбец.