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

Пример 1:

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

Решение от преподавателя:

Проверим необходимое и достаточное условие разрешимости задачи. 
∑a = 40 + 30 + 10 = 80 
∑b = 20 + 21 + 7 + 24 + 8 = 80 
Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой. 
Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи. 

Значение целевой функции для этого опорного плана равно: 
F(x) = 3*21 + 11*19 + 3*20 + 15*2 + 8*8 + 2*7 + 8*3 = 464 
Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным. 
Улучшение опорного плана. 
Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0. 
u₁ + v₂ = 3; 0 + v₂ = 3; v₂ = 3 
u₁ + v₄ = 11; 0 + v₄ = 11; v₄ = 11 
u₂ + v₄ = 15; 11 + u₂ = 15; u₂ = 4 
u₂ + v₁ = 3; 4 + v₁ = 3; v₁ = -1 
u₂ + v₅ = 8; 4 + v₅ = 8; v₅ = 4 
u₃ + v₄ = 8; 11 + u₃ = 8; u₃ = -3 
u₃ + v₃ = 2; -3 + v₃ = 2; v₃ = 5 

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij 
(1;3): 0 + 5 > 4; ∆₁₃ = 0 + 5 - 4 = 1 > 0 
(2;2): 4 + 3 > 4; ∆₂₂ = 4 + 3 - 4 = 3 > 0 
(2;3): 4 + 5 > 7; ∆₂₃ = 4 + 5 - 7 = 2 > 0 
max(1,3,2) = 3 
Выбираем максимальную оценку свободной клетки (2;2): 4 
Для этого в перспективную клетку (2;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». 

Цикл приведен в таблице (2,2 → 2,4 → 1,4 → 1,2). 
Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 4) = 2. Прибавляем 2 к объемам грузов, стоящих в плюсовых клетках и вычитаем 2 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план. 

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0. 
u₁ + v₂ = 3; 0 + v₂ = 3; v₂ = 3 
u₂ + v₂ = 4; 3 + u₂ = 4; u₂ = 1 
u₂ + v₁ = 3; 1 + v₁ = 3; v₁ = 2 
u₂ + v₅ = 8; 1 + v₅ = 8; v₅ = 7 
u₁ + v₄ = 11; 0 + v₄ = 11; v₄ = 11 
u₃ + v₄ = 8; 11 + u₃ = 8; u₃ = -3 
u₃ + v₃ = 2; -3 + v₃ = 2; v₃ = 5 

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij 
(1;3): 0 + 5 > 4; ∆₁₃ = 0 + 5 - 4 = 1 > 0 
Выбираем максимальную оценку свободной клетки (1;3): 4 
Для этого в перспективную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». 

Цикл приведен в таблице (1,3 → 1,4 → 3,4 → 3,3). 
Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 3) = 7. Прибавляем 7 к объемам грузов, стоящих в плюсовых клетках и вычитаем 7 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план. 

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0. 
u₁ + v₂ = 3; 0 + v₂ = 3; v₂ = 3 
u₂ + v₂ = 4; 3 + u₂ = 4; u₂ = 1 
u₂ + v₁ = 3; 1 + v₁ = 3; v₁ = 2 
u₂ + v₅ = 8; 1 + v₅ = 8; v₅ = 7 
u₁ + v₃ = 4; 0 + v₃ = 4; v₃ = 4 
u₁ + v₄ = 11; 0 + v₄ = 11; v₄ = 11 
u₃ + v₄ = 8; 11 + u₃ = 8; u₃ = -3 

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_j ≤ c_ij. 
Минимальные затраты составят: F(x) = 3*19 + 4*7 + 11*14 + 3*20 + 4*2 + 8*8 + 8*10 = 451