Транспортная задача линейного программирования (ТЗЛП)

Зададим матрицу данных
2 3 3 3 26 А
7 6 2 5 46 В
3 2 3 5 30 С
1 2 3 1 42 Д
40 22 38 44
А В С Д
Проверяем задачу на сбалансированность
40+22+38+44 = 144
26+46+30+42 = 144
Задача является сбалансированной.
Далее, поочередно будем решать задачу с определением минимальных тарифов.
2 3 3 3 26 – 26 = 0 А
7 6 2 5 46-38 = 8 – 8 = 0 В
3 2 3 5 30 – 22 = 8 – 8 = 0 С
1 2 3 1 42-40 = 2 – 2=0 Д
40-40 = 0 22 – 22 = 0 38 – 38 = 0 44-2 = 42-26 =
16 – 8 = 8 – 8 = 0
А В С Д
В итоге получим матрицу
2 3 3 3 (26) 26 А
7 6 2(38) 5(8) 46 В
3 2(22) 3 5(8) 30 С
1(40) 2 3 1(2) 42 Д
40 22 38 44
А В С Д
Число занятых клеток соответствует условию m+n-1 = 7, таким образом опорный план является невырожденным.
Определим стоимость перевозки:
Стоимость = 3*26+2*38+5*8+5*8+2*22+1*10+1*2 = 320 ден. ед.
Далее, проведем улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы αi, βj. по занятым клеткам таблицы, в которых αi + βj = cij, полагая, что α1 = 0.
α1 + β4 = 3; 0 + β4 = 3 ⇒ β4 = 3
α2 + β4 = 5; 3 + α2 = 5 ⇒ α2 = 2
α2 + β3 = 2; 2 + β3 = 2 ⇒ β3 = 0
α3 + β4 = 5; 3 + α3 = 5 ⇒ α3 = 2
α3 + β2 = 2; 2 + β2 = 2 ⇒ β2 = 0
α4 + β4 = 1; 3 + α4 = 1 ⇒ α4 = -2
α4 + β1 = 1; -2 + β1 = 1 ⇒ β1 = 3
2 3 3 3 (26) α1 = 0 А
7 6 2(38) 5(8) α2 = 2 В
3 2(22) 3 5(8) α3 = 2 С
1(40) 2 3 1(2) α4 = -2 Д
β1 = 3 β2 = 0 β3 = 0 β4 = 3
А В С Д
Видим, что опорный план не является оптимальным из-за наличия свободных клеток, когда αi+ βj> cij.
(1; 1) 0 + 3 > 2; ∆11= 0 + 3 - 2 = 1 > 0
(3; 1) 2 + 3 > 3; ∆31= 2 + 3 - 3 = 2 > 0
максимум (1, 2) = 2
Выбираем максимальную оценку свободной клетки (3;1): 3
Для этого в перспективную клетку (3;1) изменим знак +, а в остальных вершинах многоугольника поставим поочередно минус плюс минус.
Данную итерацию повторим несколько раз для определения оптимального варианта
2 3 3 3 (26) α1 = 0
α1 = 0 А
7 6 2(38) 5(8) α2 = 2
α2 = 2 В
3+(8) 2(22) 3 5(8)-(0) α3 = 2
α3 = 0 С
1(40)-(32) 2 3 1(2)+(10) α4 = -2
α4 = -2 Д
β1 = 3
β1 = 3 β2 = 0
β2 = 2 β2 = 0
β2 = 0 β4 = 3
β4 = 3
А В С Д
Итерация для определения потенциалов 1
α1 + β4 = 3; 0 + β4 = 3 ⇒β4 = 3
α2 + β4 = 5; 3 + α2 = 5 ⇒ α2 = 2
α2 + β3 = 2; 2 + β3 = 2 ⇒β3 = 0
α4 + β4 = 1; 3 + α4 = 1 ⇒ α4 = -2
α4 + β1 = 1; -2 + β1 = 1 ⇒ β1 = 3
α3 + β1 = 3; 3 + α3 = 3 ⇒ α3 = 0
α3 + β2 = 2; 0 + β2 = 2 ⇒ β2 = 2
Итерация для определения потенциалов 2
α1 + β4 = 3; 0 + β4 = 3 ⇒ β4 = 3
α2 + β4 = 5; 3 + α2 = 5 ⇒ α2 = 2
α2 + β3 = 2; 2 + β3 = 2 ⇒ β3 = 0
α3 + β4 = 5; 3 + α3 = 5 ⇒ α3 = 2
α3 + β2 = 2; 2 + β2 = 2 ⇒ β2 = 0
α4 + β4 = 1; 3 + α4 = 1 ⇒ α4 = -2
α4 + β1 = 1; -2 + β1 = 1 ⇒ β1 = 3
Проверка плана на оптимальность показывает, что имеются свободные клетки