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

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

b _j a_i	b₁	b₂	b₃	b₄	b₅

a₁		¹³	⁹	¹³	⁶	¹⁴
a₂		²⁰	²⁰	¹⁹	²	¹⁹
a₃		¹⁰	⁴	⁵	²	⁶
a₄		¹⁹	⁵	⁷	⁸	¹⁹
a₅		³	¹⁸	¹⁷	⁸	²

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

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

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

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

b _j a_i	b₁	b₂	b₃	b₄	b₅

a₁		¹³	⁹	¹³	⁶	¹⁴
a₂		²⁰	²⁰	¹⁹	²	¹⁹
a₃		¹⁰	⁴	⁵	²	⁶
a₄		¹⁹	⁵	⁷	⁸	¹⁹
a₅		³	¹⁸	¹⁷	⁸	²

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

b _j a_i	b₁	b₂	b₃	b₄	b₅

a₁		₁₄₅ ¹³	⁹	¹³	⁶	₁₅¹⁴
a₂		₁₅₅ ²⁰	²⁰	¹⁹	₂₄₅ ²	¹⁹
a₃		¹⁰	₂₀ ⁴	₁₈₅ ⁵	²	₆₅ ⁶
a₄		¹⁹	⁵	⁷	⁸	₅₀ ¹⁹
a₅		³	¹⁸	¹⁷	⁸	₄₀ ²

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

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

, т.е.

(ден. ед.)

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

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

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

-13	-12	-13		-14	v_i u_i
¹³	⁹	¹³	⁶	¹⁴
²⁰	²⁰	¹⁹	²	¹⁹	-7
¹⁰	⁴	⁵	²	⁶
¹⁹	⁵	⁷	⁸	¹⁹	-5
³	¹⁸	¹⁷	⁸	²

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

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

₀	_-3	₀	₁₁	₀
₀	₁	_-1	₀	_-2
₅	₀	₀	₁₅	₀
₁	_-12	_-11	₈	₀
₂	₁₈	₁₆	₂₅	₀

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

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

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

₀	_-3	₀	₁₁	₀
₀	₁	_-1	₀	_-2
₅	^II₀	₀	₁₅	^III₀
₁	^I_-12	_-11	₈	^IV₀
₂	₁₈	₁₆	₂₅	₀

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

₁₄₅ ¹³	⁹	¹³	⁶	₁₅ ¹⁴
₁₅₅ ²⁰	²⁰	¹⁹	₂₄₅ ²	¹⁹
₁₀	_II₄ ₂₀	₁₈₅ ⁵	₂	_III₆ ₆₅
₁₉	I ⁵	₇	₈	_IV ₁₉ ₅₀
³	¹⁸	¹⁷	⁸	₄₀ ²

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

₁₄₅ ¹³	⁹	¹³	⁶	₁₅¹⁴
₁₅₅ ²⁰	²⁰	¹⁹	₂₄₅ ²	¹⁹
¹⁰	⁴	₁₈₅⁵	²	₈₅ ²
¹⁹	₂₀⁵	⁷	⁸	₃₀ ¹⁹
³	¹⁸	¹⁷	⁸	₄₀ ²