проблема транспортной задачи была впервые формализована в

Ответ от Ѐуся Гафурова[активный]

Математическая модель транспортной задачи:
F = ∑∑cijxij, (1)
при условиях:
∑xij = ai, i = 1,2,…, m, (2)
∑xij = bj, j = 1,2,…, n, (3)
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
12345Запасы
14925323
24621825
36234517
Потребности1410161015
Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 23 + 25 + 17 = 65
∑b = 14 + 10 + 16 + 10 + 15 = 65
Занесем исходные данные в распределительную таблицу.
12345Запасы
14925323
24621825
36234517
Потребности1410161015
Этап I. Поиск первого опорного плана.
1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
12345Запасы
1492[16]53[7]23
24[14]621[10]8[1]25
362[10]345[7]17
Потребности1410161015
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 2*16 + 3*7 + 4*14 + 1*10 + 8*1 + 2*10 + 5*7 = 182
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.