Пример.

Определить оптимальный план перевозок продукции со складов в пункты потребления , если исходная транспортная таблица имеет вид:

bj ai	b1	b2	b3	b4	b5
a1		13	9	13	6	14
a2		20	20	19	2	19
a3		10	4	5	2	6
a4		19	5	7	8	19
a5		3	18	17	8	2

I. Определим, к какому типу (закрытому или открытому) относится данная задача, т.е. проверим выполнение условия (5):

,

Т.к. , то данная задача является задачей закрытого типа.

II. Определяем исходное опорное решение .

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

bj ai	b1	b2	b3	b4	b5
a1		13	9	13	6	14
a2		20	20	19	2	19
a3		10	4	5	2	6
a4		19	5	7	8	19
a5		3	18	17	8	2

2. Распределяем перевозки. Определим поток перевозок по маршрутам, образованным клетками матрицы с двумя оценками, потом используются маршруты через клетки с одной оценкой.

bj ai	b1	b2	b3	b4	b5
a1		145 13	9	13	6	1514
a2		155 20	20	19	245 2	19
a3		10	20 4	185 5	2	65 6
a4		19	5	7	8	50 19
a5		3	18	17	8	40 2

 

3. Определяем количество базисных клеток, т.е. клеток по которым осуществляется перевозка. Их должно быть .
Условие выполнено.

4. Определим расходы по формуле (4):

, т.е.

(ден. ед.)

III. Проверим план на оптимальность.

5. Определим неизвестные потенциалы строк и столбцов.

Для базисных клеток составим систему уравнений по формуле (8).

-13	-12	-13		-14	vi ui
13	9	13	6	14
20	20	19	2	19	-7
10	4	5	2	6
19	5	7	8	19	-5
3	18	17	8	2

 

 

Пусть u₁=0, тогда найдем решения системы .

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

0	-3	0	11	0
0	1	-1	0	-2
5	0	0	15	0
1	-12	-11	8	0
2	18	16	25	0

 

Т.к. матрица содержит отрицательные элементы, то план не является оптимальным.

 

7. Выбираем максимальный по модулю отрицательный элемент матрицы (-12).

8. Из клетки этого элемента строим цикл по другим выделенным элементам, вершины нумеруем.

0	-3	0	11	0
0	1	-1	0	-2
5	II 0	0	15	III 0
1	I -12	-11	8	IV 0
2	18	16	25	0

9. Найденный цикл переносим на транспортную таблицу. Из четных вершин цикла, выбираем вершину с минимальным объемом перевозок: 20; 50.
Таким образом min=20.

145 13	9	13	6	15 14
155 20	20	19	245 2	19
10	II4 20	185 5	2	III 6 65
19	I 5	7	8	IV 19 50
3	18	17	8	40 2

10. Из четных вершин этот объем вычитается, а в нечетных прибавляется.
Получаем новый план.

145 13	9	13	6	15 14
155 20	20	19	245 2	19
10	4	185 5	2	85 2
19	20 5	7	8	30 19
3	18	17	8	40 2

11. Определяем новые затраты.

, (ден. ед.)

12. Проверяем новый план на оптимальность, выполнив вновь пункты с 5 по 11.

5. Определим неизвестные потенциалы строк и столбцов.

Для базисных клеток составим систему уравнений по формуле (8).

-13		-13		-14	vi ui
13	9	13	6	14
20	20	19	2	19	-7
10	4	5	2	6
19	5	7	8	19	-5
3	18	17	8	2

Пусть u₁=0.