Нахождение оптимального решения

С помощью методов построения первоначального опорного плана можно получить вырожденный или невырожденный опор­ный план. Построенный план транспортной задачи как задачи линейного программирования можно было бы довести до оптимального с помощью симплексного метода. Однако из-за громоздкости симплексных таблиц, со­держащих тп неизвестных, и большого объема вычислительных работ для получения оптимального плана используют более простые методы. Наиболее часто применяются метод потенциалов (модифицированный распредели­тельный метод) и метод дифференциальных рент.

Метод потенциалов. Этот первый точный метод решения транспортной задачи предложен в 1949 году Кантаровичем А. В. И Гавуриным М. К. по существу он является детализацией метода последовательного улучшения плана применительно к транспортной задаче. Метод потенциалов позволяет определить отправляясь от некоторого опорного плана перевозок построить решение транспортной задачи за конечное число шагов (итераций).

Алгоритм нахождения решения транспортной задачи этим методом основан на соотношении между прямой и двойственной задачами.

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

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

если (где c_ij - стоимость перевозки из пункта i в пункт j) (8)

Поскольку система (8) содержит уравнений и m+n неизвестных, то одну из них можно задать произвольно (например, приравнять к нулю). После этого из уравнений (8) определяются остальные потенциалы и для каждой из свободных клеток вы­числяются величины c_i,j’ = u_{i +} v_j - c_i,j.

Если оказалось, что все c_i,j’ отрицательны, то план оп­тимален. Если же хотя бы в одной свободной клетке c_i,j’ > 0, то план не яв­ляется оптимальным и для включения в базис выбирается небазисная переменная, имеющая самую большую положительную оценку c_i,j’ (опорная клетка).

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

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

Цикл пересчета представляет собой замкнутую ломаную линию состоящую из горизонтальных и вертикальных линий, концы которых лежат в заполненных клетках. Ломаная линия начинается и заканчивается в опорной клетке. Узел в опорной клетке считается положительным, следующий - отрицательный, и так далее чередуясь. Берется минимальное по абсолютной величине значение в отрицательных клетках. Эта клетка и будет соответствовать базисной переменной, выводимой из базиса. Во всех отрицательных клетках это значение отнимается, в положительных прибавляется. Получили новый план перевозок.

Если ломаная линия, образующая цикл, пересекается, то точки самопересечения не являются вершинами.

Процесс улучшения плана продолжается до тех пор, пока не будет получен план, в котором все c_i,j’ отрицательны.

Пример нахождения оптимального плана

(См. Пример нахождения опорного плана.)

Рассчитаем потенциалы пунктов отправки и пунктов доставки и _. Для этого составьте систему для заполненных клеток плана перевозок: _. Решим данную систему, полагая =0.

2. Вычислим коэффициенты изменения стоимости для незаполненных клеток плана: c_i,j’ = u_{i +} v_j - c_i,j.

Таблица 2

Поставщики и их ресурсы

Потребители и их спрос

B1
	33

B2
	13

B3
	27

B4
	17

A1
	27

14
0	27

28
-7	0

21
-2	0

28
-13	0

0

A2
	20

10	[-6]
0	6

17
0	13

15	[+6]
0	1

24
-13	0

-4

A3
	43

14	[+6]
6	0

30
-3	0

25	[-6]
0	26

21
0	17

6

14

21

19

15

Стоимость перевозок по данному плану составляет: 1681.

F=14 *27 + 28* 0 + 21*0 + 28*0 + 10 *6 + 17 *13 + 15*1 + 24 *0 + 14 *0 + 30 *0 +25*26 + 21 *17 =1681

Получим потенциалы и _.. Рассчитаем коэффициенты изменения стоимости перевозок.

Составим цикл пересчета: Опорная клетка: (3:1) , далее (3:3) [-6], (2:3) [+6], (2:1) [-6]. Количество единиц изменения плана: 6. Потенциалы, коэффициенты и цикл пересчета указаны в таблице 2. Получим следующий план перевозок (Табл.3).

Таблица 3.

Поставщики и их ресурсы

Потребители и их спрос

B1
	33

B2
	13

B3
	27

B4
	17

A1
	27

14	[-20]
0	27

28
-1	0

21	[+20]
4	0

28
-7	0

0

A2
	20

10
-6	0

17
0	13

15
0	7

24
-13	0

-10

A3
	43

14	[+20]
0	6

30
-3	0

25	[-20]
0	20

21
0	17

0

14

27

25

21

Стоимость перевозок по данному плану составляет: 1645.

F=14 *27 + 28* 0 + 21*0 + 28*0 + 10 *0 + 17 *13 + 15*7 + 24 *0 + 14 *6 + 30 *0 +25*20 + 21 *17 =1645

Получим потенциалы и . Рассчитаем коэффициенты изменения стоимости перевозок. Составим цикл пересчета: Опорная клетка: (1:3) , далее (1:1) [-20], (3:1) [+20], (3:3) [-20]. Количество единиц изменения плана: 20 Потенциалы, коэффициенты и цикл пересчета указаны в таблице 3. Получим следующий план перевозок (Табл.4).

Таблица 4.

Поставщики и их ресурсы

Потребители и их спрос

B1
	33

B2
	13

B3
	27

B4
	17

A1
	27

14
0	7

28
-5	0

21
0	20

28
-7	0

0

A2
	20

10
-2	0

17
0	13

15
0	7

24
-9	0

-6

A3
	43

14
0	26

30
-7	0

25
-4	0

21
0	17

0

14

23

21

21

Стоимость перевозок по данному плану составляет: 1565.

F=14 *7 + 28* 0 + 21*20 + 28*0 + 10 *0 + 17 *13 + 15*7 + 24 *0 + 14 *26 + 30 *0 +25*0 + 21 *17 =1565

Получим потенциалы и . Рассчитаем коэффициенты изменения стоимости перевозок. Потенциалы и коэффициенты указаны в таблице 4. Полученный план оптимальный, т.к. все коэффициенты изменения стоимости отрицательны или равны нулю.