Решение транспортной задачи

Стоимость доставки единицы груза из каждого пункта отправления в соответствующие  пункты назначения задана матрицей тарифов

 

Проверим необходимое  и достаточное условие разрешимости задачи.

∑ a = 340 + 300 + 260 = 900

∑ b = 220 + 170 + 180 + 190 + 140 = 900

Занесем исходные данные в распределительную таблицу. 

 

Первая итерация заключается в определении исходного  опорного плана и проверке его  на оптимальность.

Этап I. Поиск первого  опорного плана.

1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

 

В результате получен  первый опорный план, который является допустимым, так как все грузы  из баз вывезены, потребность магазинов  удовлетворена, а план соответствует  системе ограничений транспортной задачи.

2. Подсчитаем  число занятых клеток таблицы,  их 7, а должно быть m + n - 1 = 7. Следовательно,  опорный план является невырожденным.

Значение целевой  функции для этого опорного плана  равно:

6*180 + 6*20 + 6*140 + 1*220 + 2*80 + 3*90 + 5*170  = 3540

Этап II. Улучшение опорного плана.

Шаг 1. Определяем оценку для каждой свободной клетки.

(1;1): В свободную клетку (1;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».  

 

Цикл приведен в таблице (1,1; 1,4; 3,4; 3,2; 2,2; 2,1; ).

Оценка свободной  клетки равна Δ₁₁ = 0.

(1;2): В свободную клетку (1;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».  

 

Цикл приведен в таблице (1,2; 1,4; 3,4; 3,2; ).

Оценка свободной  клетки равна Δ₁₂ = 2.

(2;3): В свободную клетку (2;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».  

 

Цикл приведен в таблице (2,3; 2,2; 3,2; 3,4; 1,4; 1,3; ).

Оценка свободной  клетки равна Δ₂₃ = -1.

(2;4): В свободную клетку (2;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».  

 

Цикл приведен в таблице (2,4; 2,2; 3,2; 3,4; ).

Оценка свободной  клетки равна Δ₂₄ = 0.

(2;5): В свободную клетку (2;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».  

 

Цикл приведен в таблице (2,5; 2,2; 3,2; 3,4; 1,4; 1,5; ).

Оценка свободной  клетки равна Δ₂₅ = -2.

(3;1): В свободную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».  

 

Цикл приведен в таблице (3,1; 3,2; 2,2; 2,1; ).

Оценка свободной  клетки равна Δ₃₁ = 2.

(3;3): В свободную клетку (3;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».