Линейная алгебра и математическое программирование
которое запишем в виде
матрицы
Х1 =
Стоимость перевозки при исходном
решении составляет
f1 = 175 * 5 + 175 * 15 + 40 * 10 + 160
* 6 + 200 * 4 + 10 * 20 + 240 * 10 = 8260.
Проверим найденное решение транспортной задачи на
оптимальность Найденное
исходное решение проверяется на оптимальность методом потенциалов по следующему
критерию: если решение транспортной задачи является оптимальным, то ему
соответствует система m+n ( 5 + 3 = 8 ) действительных чисел 
и 
, удовлетворяющих условиям 
для занятых клеток и 
– для свободных клеток.
Числа 
и 
называются
потенциалами. В распределительную таблицу добавляют столбец 
и строку 
.
Потенциалы 
и 
находят из равенства 
, справедливого для занятых клеток. Одному из
потенциалов дается произвольное значение, например 
, тогда остальные потенциалы определяются
однозначно. Так, если известен потенциал 
, то 
; если известен потенциал , то 
.
Обозначим 
. Эту оценку называют оценкой свободных
клеток. Если 
, то опорное
решение является оптимальным. Если хотя бы одна из оценок 
, то решение не является оптимальным и его
можно улучшить, перейдя от одного решения к другому.
Проверим найденное
решение на оптимальность, добавив в распределительную таблицу, приведенную
ниже, столбец 
и строку 
.
Полагая 
, запишем это значение в последнем столбце
таблицы.
|
 bi
ai
|
1 |
2 |
3 |
4 |
5 |
|
| 175 |
225 |
240 |
160 |
200 |
𝛼i
|
| 1 |
350
|
5
175
|
15
175
|
18 |
16 |
8 |
0 |
| 2 |
400 |
6 |
10
40
|
15 |
6
160
|
4
200
|
-5 |
| 3 |
250 |
25 |
20
10
|
10
240
|
15 |
18 |
0 |
|
|
𝛽i
|
5 |
15 |
10 |
11 |
9 |
|
Для клетки (1,1) : 
1 + 
1 = 5, 1 = 0, 1 = 5
Для клетки (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 строится цикл (цепь, многоугольник), все вершины которого, кроме
одной, находятся в занятых клетках; углы прямые, число вершин четное. Около
свободной клетки цикла ставится знак (+), затем поочередно проставляют знаки
(-) и (+). У вершин со знаком (-) выбирают минимальный груз, его прибавляют к
грузам, стоящим у вершин со знаком (+), и отнимают от грузов у вершин со знаком
(-). В результате перераспределения груза получим новое решение. Это решение
проверяем на оптимальность, и так далее до тех пор, пока не получим оптимальное
решение.
Х2 =
Стоимость перевозки при
исходном решении составляет
f2 = 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 |
5
175
|
15 |
18 |
16 |
8
175
|
0 |
| 2 |
400 |
6 |
10
215
|
15 |
6
160
|
|