Линейная алгебра и математическое программирование (стр. 3 из 4)

Для клетки (1,2) :

1 + 2 = 15, 1 = 0, 2 = 15

Для клетки (2,2) :

2 + 2 = 10, 2 = -5, 2 = 15

Для клетки (2,4) :

2 + = 6, 2 = -5, 4 = 11

Для клетки (2,5) :

2 + = 4, 2 = -5, 5 = 9

Для клетки (3,3) :

+ = 10, 3 = 0, 3 = 10

Найденные значения потенциалов заносим в таблицу. Вычисляем оценки свободных клеток:

Δ13 =

1 + 3 – с 13 = 0 + 10 – 18 = - 8 0

Δ14 =

1 + – с 14 = 0 + 11 – 16 = - 5 0

Δ15 =

1 + – с 15 = 0 + 9 – 8 = 1 0

Δ21 =

+ – с 21 = -5 + 5 – 6 = -6 0

Δ23 =

+ – с 23 = -5 + 10 – 15 = -10 0

Δ31 =

+ – с 31 = 0 + 5 – 25 = -20 0

Δ34 =

+ – с 34 = 0 + 11 – 15 = -4 0

Δ35 =

+ – с 35 = 0 + 9 – 18 = -9 0

Получили одну оценку Δ15 = 1

0 следовательно, исходное решение не является оптимальным и его можно улучшить.

Переход от одного решения транспортной задачи к другому.

Наличие положительной оценки свободной клетки (

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

Для свободной клетки Δ15 = 1

0 строится цикл (цепь, многоугольник), все вершины которого, кроме одной, находятся в занятых клетках; углы прямые, число вершин четное. Около свободной клетки цикла ставится знак (+), затем поочередно проставляют знаки (-) и (+). У вершин со знаком (-) выбирают минимальный груз, его прибавляют к грузам, стоящим у вершин со знаком (+), и отнимают от грузов у вершин со знаком (-). В результате перераспределения груза получим новое решение. Это решение проверяем на оптимальность, и так далее до тех пор, пока не получим оптимальное решение.

Х₂ =

Стоимость перевозки при исходном решении составляет

f₂ = 175 * 5 + 215 * 10 + 10 * 20 + 240 * 10 + 160 * 6 + 175 * 8 + 25 * 4 = 8085.

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

bi ai		1	2	3	4	5
		175	225	240	160	200	𝛼i
1	350	5175	15	18	16	8175	0
2	400	6	10215	15	6160	425	-4
3	250	25	2010	10240	15	18	0
𝛽i	5	14	10	10	8

Для клетки (1,1) :

1 + 1 = 5, 1 = 0, 1 = 5

Для клетки (1,5) :

1 + 5 = 8, 1 = 0, 5 = 8

Для клетки (2,5) :

2 + = 4, = -4, = 8

Для клетки (2,4) :

2 + = 6, 2 = -4, 4 = 10

Для клетки (2,2) :

2 + = 10, 2 = -4, = 14

Для клетки (3,3) :

+ = 10, 3 = 0, 3 = 10

Найденные значения потенциалов заносим в таблицу. Вычисляем оценки свободных клеток:

Δ12 =

1 + – с 12 = 0 + 14 – 15 = - 1 0

Δ13 =

1 + – с 13 = 0 + 10 – 18 = - 8 0

Δ14 =

1 + – с 14 = 0 + 10 – 16 = - 6 0

Δ21 =

+ – с 21 = -4 + 5 – 6 = - 5 0