Решить транспортную задачу. Обозначения – запасы груза в i-м пункте отправления

Запасы

6 7 3 5 100
1 2 5 6 150
3 10 20 4 50
Потребности 75 80 60 85 Х
Проверим необходимое и достаточное условие разрешимости задачи:
,
.
Т.к. , то модель транспортной задачи является закрытой, а, следовательно, разрешимой. Число складов , а потребителей .
Используя метод северо-западного угла, построим опорный план транспортной задачи. Начинаем заполнять план в верхнего левого угла.
Рассмотрим элемент :
.
Скорректируем таблицу:
Запасы

6 7 3 5 100-75=25
Х 2 5 6 150
Х 10 20 4 50
Потребности 75-75=0 80 60 85 Х
Рассмотрим элемент :
.
Скорректируем таблицу:
Запасы

6 7 Х Х 25-25=0
Х 2 5 6 150
Х 10 20 4 50
Потребности 0 80-25=55 60 85 Х
Рассмотрим элемент :
.
Скорректируем таблицу:
Запасы

6 7 Х Х 0
Х 2 5 6 150-55=95
Х Х 20 4 50
Потребности 0 55-55=0 60 85 Х
Рассмотрим элемент :
.
Скорректируем таблицу:
Запасы

6 7 Х Х 0
Х 2 5 6 95-60=35
Х Х Х 4 50
Потребности 0 0 60-60=0 85 Х
Рассмотрим элемент :
.
Скорректируем таблицу:
Запасы

6 7 Х Х 0
Х 2 5 6 35-35=0
Х Х Х 4 50
Потребности 0 0 0 85-35=50 Х
Рассмотрим элемент :
.
Скорректируем таблицу:
Запасы

6 7 Х Х 0
Х 2 5 6 0
Х Х Х 4 50-50=0
Потребности 0 0 0 50-50=0 Х
Найденный опорный план:
Значение целевой функции :
.
Для проверки оптимальности опорного плана найдем предварительные потенциалы , :
, , ,
, , ,
, , ,
, , ,
, , ,
, , .

6[75] 7[25] 3 5 0
1 2[55] 5[60] 6[35] 0
3 10 20 4[50] 0
0 0 0 0 Х
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых:
, ,
, ..
Выбираем максимальную оценку свободной клетки , в которую поставим знак «+» . В остальные вершины многоугольника поставим чередующиеся знаки:
Запасы

6[75] 7[25][–] 3[+] 5 100
1 2[55][+] 5[60][-] 6[35] 150
3 10 20 4[50] 50
Потребности 75 80 60 85 Х
Полученный цикл: .
Наименьшая ячейка зо знаком «–»: .
Скорректируем значения в ячейках цикла:
Запасы

6[75] 7 3[25] 5 100
1 2[80] 5[35] 6[35] 150
3 10 20 4[50] 50
Потребности 75 80 60 85 Х
Новый опорный план:
Для проверки оптимальности опорного плана найдем предварительные потенциалы , :
, , ,
, , ,
, , ,
, , ,
, , ,
, , .

6[75] 7 3[25] 5 0
1 2[80] 5[35] 6[35] 0
3 10 20 4[50] 0
0 0 0 0 Х
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых:
, ,
, ..
Выбираем максимальную оценку свободной клетки , в которую поставим знак «+». В остальные вершины многоугольника поставим чередующиеся знаки:
Запасы

6[75][–] 7 3[25][+] 5 100
1[+] 2[80] 5[35][–] 6[35] 150
3 10 20 4[50] 50
Потребности 75 80 60 85 Х
Полученный цикл: .
Наименьшая ячейка зо знаком «–»: .
Скорректируем значения в ячейках цикла:
Запасы

6[40] 7 3[60] 5 100
1[35] 2[80] 5 6[35] 150
3 10 20 4[50] 50
Потребности 75 80 60 85 Х
Новый опорный план:
Для проверки оптимальности опорного плана найдем предварительные потенциалы , :
, , ,
, , ,
, , ,
, , ,
, , ,
, , .

6[40] 7 3[60] 5 0
1[35] 2[80] 5 6[35] 0
3 10 20 4[50] 0
0 0 0 0 Х
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых:
, ,
Внайденную свободную клетку ставим знак «+»