Числаui являются потенциалами строк, аvj – потенциалами столбцов. Из теоремы следует, что для того, чтобы план был оптимальным, необходимо выполнение следующих условий:

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

u_i + v_j = с_{i j}; (4.6)

б) для каждой незанятой клетки сумма потенциалов должна быть меньше или равна удельной стоимости перевозки, стоящей в этой клетке:

u_i + v_j с_{i j}. (4.7)

Если хотя бы одна незанятая клетка не удовлетворяет условию (б), то план не оптимален.

Рассчитаем потенциалы для плана перевозок в таблице 4.3. Запишем условия (4.6), справедливые для занятых клеток таблицы:

u₁ + v₂ = 3

u₂ + v₁ = 2

u₂ + v₂ = 5 (4.8)

u₂ + v₃= 3

u₂ + v₄ = 9

u₃ + v₄= 3

Получили систему m + n – 1=6 уравнений с m+ n =7 неизвестными. Уравнений на одно меньше, чем неизвестных, поэтому система является неопределённой(имеет бесконечное множество решений). Потенциалы являются абстрактными объектами, т.е. не имеют физического смысла. Для проверки оптимальности плана нам важно знать их соотношения, а не точные значения. Поэтому один из потенциалов определяют произвольно, т.е. равным любому числу. Чаще всего принимают

u₁ = 0,

тогда остальные потенциалы легко находятся из системы (4.8).

Таблица 4.4 – Опорный план с расчетом потенциалов

Предприятия	Потребители
	b1 = 15	b2 = 40	b3 = 25	b4 = 20
A1 а1=30	7	- 3 30	6	+ 4	0
A2 а2=60	2 15	5 10 +	3 25	9 - 10	2
A3 а3=10	8	1	7	3 10	-4
	0	3	1	7

Проверим условие оптимальности для незанятых клеток. Для клетки (1,4) условие (4.7) не выполняется, т.е.

u₁+v₄ = 0+7 >4.

Пометим эту клетку «» и будем называть «плохой».

Таким образом, опорный план не является оптимальным из-за существования «плохой» клетки. В этом случае логично заполнить эту клетку некоторой поставкой, тогда условие оптимальности (4.6) будет выполнено для нее автоматически при расчете потенциалов.

6 П е р е р а с п р е д е л е н и е п о с т а в о к

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

А. Строим «маршрут» перераспределения по правилам:

– начальная вершина маршрута находится в «плохой» клетке;

– все остальные вершины лежат в заполненных клетках;

– все углы маршрута – прямые.

По перечисленным правилам можно построить единственный маршрут. Он может иметь конфигурацию, квадрата, прямоугольника, многоугольника (рисунок 4.1).

Б. В вершинах маршрута расставляем знаки: «+» – в начальную вершину, «- » – в соседнюю, далее знаки чередуются (таблица 4.4).

В.Выбираем величину перепоставки. Она равна минимуму поставок, расположенных в клетках маршрута со знаком «-»:

.

Теперь можно построить следующий план перевозок: в вершины маршрута со знаком «+» добавляется перепоставкаП, а из вершин с «-» она вычитается (таблица 4.5). Далее по известным правилам рассчитываем потенциалы строк и столбцов нового плана и проверяем его на оптимальность.

Таблица 4.5 – План перевозок (первая итерация)

Предприятия	Потребители
	b1 = 15	b2 = 40	b3 = 25	b4 = 20
A1 а1 = 30	7	- 3 20	6	+ 4 10	0
A2 а2 = 60	2 15	5 20	3 25	9	2
A3 а3=10	8	1 +	7	3 - 10	-1
	0	3	1	4

План перевозок, полученный после первой итерации также неоптимален, поскольку для клетки (3,2) не выполняется условие (4.7). Снова выполняем перераспределение поставок (вторая итерация) и получаем следующий план перевозок (таблица 4.6).

Таблица 4.6 – План перевозок (вторая итерация)

Предприятия	Потребители
	b1 = 15	b2 = 40	b3 = 25	b4 = 20
A1 а1 = 30	7	3 10	6	4 20	0
A2 а2 = 60	2 15	5 20	3 25	9	2
A3 а3=10	8	1 10	7	3 10	-2
	0	3	1	4

План, представленный в таблице 4.6, удовлетворяет условиям (4.6)-(4.7) и, следовательно, является оптимальным.

7 З а п и с ь о п т и м а л ь н о г о п л а н а и вычисление

минимальной стоимости перевозок

Оптимальный план перевозок. От предприятияA₁ 10единиц продукции следует доставить потребителю B₂ и 20единиц – потребителюB_4. От предприятияA₂15единиц продукции нужно перевезти потребителюB₁,20единиц – потребителюB₂,25единиц – потребителюB₃. От предприятия

A₃груз должен поступить потребителюB₂в количестве10 единиц.

Минимальная суммарная стоимость перевозок

3·10 + 20·4 +15·2 + 20·5 + 25·3 +10·1 = 325 (денежных единиц).

Задача 4.2. Требуется перевезти груз от трех поставщиков четырем потребителям, при этом суммарная стоимость доставки должна быть минимальной. Исходные данные для составления плана перевозок приведены в таблице 4.7.

Таблица 4.7 – Исходные данные к задаче 4.2

Поставщики	Потребители
	b1 = 50	b2 = 100	b3 = 150	b4 = 200
A1 а1 = 50	1	6	8	12
A2 а2 = 300	16	10	8	6
A3 а3=100	4	1	9	11

РЕШЕНИЕ.

1 Проверим условие замкнутости

.

Условие замкнутости не выполняется (открытая транспортная задача), поэтому в таблицу 4.7 вводим строку фиктивного поставщика с запасом продукции

.

В фиктивную строку записываем нулевые удельные стоимости поставок (таблица 4.8).

2 Составим математическую модель.

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

.

Балансовые условия:

;

;

;

;

;

;

;

.

3 Составим опорный план методом минимального элемента(таблица 4.8)

Таблица 4.8 – Опорный план по методу минимального элемента в строке

Поставщики	Потребители
	b1 = 50	b2 = 100	b3 = 150	b4 = 200
A1 а1 = 50	1 50	6	8	12
A2 а2 = 300	16	10	8 100	6 200
A3 а3=100	4	1 100	9	11
AФ аФ=50	0	0	0 50	0

4 Проверим опорный план на невырожденность..

Опорный план – вырожденный, так как число занятый клеток

.

5 Проверим оптимальность плана методом потенциалов.

Для выполнения условия невырожденности плана не хватает двух заполненных клеток. Поэтому в клетки (3,1) и (4,2) запишем нулевые поставки и будем считать их занятыми. Теперь можно вычислить потенциалы строк и столбцов (таблица 4.9).

Таблица 4.9 – Расчет потенциалов опорного плана

Поставщики	Потребители
	b1 = 50	b2 = 100	b3 = 150	b4 = 200
A1 а1 = 50	1 50	6	8	12	0
A2 а2 = 300	16	10	8 100	6 200	10
A3 а3=100	4 - 0	1 100 +	9	11	3
AФ аФ=50	0 +	0 0 -	0 50	0	2
	1	-2	-2	-4

План неоптимальный, так как для клетки (4,1) не выполняется условие оптимальности, т.е.

u₄+v₁ = 1+2 >0.

6 Выполним перераспределение поставок.

Для клетки (4,1) строим маршрут перераспределения; в вершинах маршрута чередуются знаки «+» и «-» (таблица 4.9). Величина перепоставки равнанулю. Перепоставку вычитаем из клеток с «-» и прибавляем к клеткам с «+». Новый план перевозок представлен в таблице 4.10.

Таблица 4.10 – Оптимальный план перевозок

Поставщики	Потребители
	b1 = 50	b2 = 100	b3 = 150	b4 = 200
A1 а1 = 50	1 50	6	8	12	0
A2 а2 = 300	16	10	8 100	6 200	7
A3 а3=100	4 - 0	1 100	9	11	3
AФ аФ=50	0 0	0	0 50	0	-1
	1	-2	1	-1

Полученный план удовлетворяет условиям оптимальности.

7 Запишем оптимальный план перевозок.

От поставщика A₁ 50единиц груза следует направить потребителю B_1. От поставщикаA₂100единиц груза нужно перевезти потребителюB₃,200единиц – потребителюB₄. От поставщикаA₃груз должен поступить потребителюB₂в количестве100 единиц. Извне (фиктивный поставщик)50 единиц груза следует привезти потребителюB₃.

Минимальная суммарная стоимость перевозок

1·50 + 8·100 +6·200 +0·4 + 1·100 + 0·0 + 0·50 = 2150.