5.2. Нахождение исходного опорного решения

Клетки, в которые поместим грузы, называются занятыми, им соответствуют базисные переменные опорного решения. Остальные клетки незанятые, или пустые, им соответствуют свободные переменные. В верхнем правом углу каждой клетки будем записывать тарифы.

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

Нулевые поставки помещают в незанятые клетки с учётом наименьшего тарифа таким образом, чтобы в каждых строке и столбце было не менее чем по одной занятой клетке.

5.3. Определение эффективного варианта доставки изделий к потребителю

На складах А₁, А₂, А₃ имеются запасы продукции в количествах 90, 400, 110 т соответственно. Потребители В₁, В₂, В₃ должны получить эту продукцию в количествах 140, 300, 160 т соответственно. Найти такой вариант прикрепления поставщиков к потребителям, при котором сумма затрат на перевозки была бы минимальной. Расходы по перевозке 1 т продукции заданы матрицей (усл. ед.)

Проверим, является ли данная транспортная задача закрытой:

т,

т,

Следовательно, данная транспортная задача закрытая. Найдём исходное опорное решение по методу минимального тарифа.

Таблица 5.2

b j ai		1	2	3
		140	300	160
1	90	2 90	5	2
2	400	4	1 300	5 100
3	110	3 50	6	8 60

Число занятых клеток в табл. 5.2 равно m+ n – 1 = 3 + 3 – 1 = 5, т. е. задача невырожденная. Получили исходное решение: Х₁ = .

Стоимость перевозки при исходном оперном решении составляет

усл. ед.

5.4. Проверка найденного опорного решения на оптимальность

Найденное исходное опорное решение проверяется на оптимальность методом потенциалов по следующему критерию: если опорное решение транспортной задачи является оптимальным, то ему соответствует система т + п действительных чисел u_i и v_j, удовлетворяющих условиям u_i+v_j-c_ij≤0 для свободных клеток.

Числа u_i и v_j называют потенциалами. В распределительную таблицу добавляют строку v_j и столбец u_i. Потенциалы u_i и v_j находят из равенства , справедливого для занятых клеток. Одному из потенциалов даётся произвольное значение, например , тогда остальные потенциалы определяются однозначно.

Обозначим . Эту оценку называют оценкой свободных клеток. Если , то опорное решение является оптимальным. Если хотя бы одна из оценок , то опорное решение не является оптимальным и его можно улучшить, перейдя от одного опорного решения к другому. Проверим найденное опорное решение на оптимальность. Полагая , запишем это значение в последнем столбце таблицы и проставим остальные потенциалы, ориентируясь только на занятые клетки.

Таблица 5.3

b j ai		1	2	3	ui
		140	300	160
1	90	2 90	5	2	0
2	400	4	1 300	5 100	-2
3	110	3 50	6	8 60	1
vj		2	3	7

Рассмотрим занятую клетку первой строки, которая расположена в первом столбце (1, 1), для неё выполняется условие , откуда . Это значение запишем в последней строке таблицы. Далее надо рассматривать ту из занятых клеток таблицы, для которой один из потенциалов известен.

Рассмотрим занятую клетку (3, 1): , откуда .

Для клетки (3, 3):

Для клетки (2, 3):

Для клетки (2, 2):

Найденные значения потенциалов заносим в таблицу.

Вычисляем оценки свободных клеток.

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