Закрытая и открытая модели транспортной задачи

 

Транспортная задача, в которой имеет место равенство (18), называется закрытой.

Если для ТЗ выполняется одно из условий:

 

(19)

или

,

(20)

то задачу называют открытой.

Для разрешимости ТЗ с открытой моделью необходимо преобразовать ее в закрытую.

Если суммарный запас продукта превышает общий спрос, т. е. выполняется условие (19), то в рассмотрение вводится фиктивный (n + 1)-й пункт потребления B_{n+ 1} (в матрице задачи предусматривается дополнительный столбец) со спросом, равным небалансу, т. е. , и одинаковыми тарифами, полагаемыми обычно равными нулю. Теперь условие разрешимости выполняется, а величина целевой функции остается прежней, поскольку цены на дополнительные перевозки равны нулю. При этом грузы, которые должны быть перевезены в пункт B_{n+ 1}, фактически останутся в пункте отправления.

Если же общий спрос потребителей больше суммарного запаса продукта, т. е. выполняется условие (20), то вводится фиктивный (m + 1)-й пункт отправления A_{m+ 1}(в матрице задачи предусматривается дополнительная строка) с запасом продукта .

Тарифы на доставку продукта фиктивным поставщиком предполагаются, как и в предыдущем случае, равными нулю, что не отразится на целевой функции.

Теорема 9 (о ранге матрицы). Ранг матрицы А (матрица системы ограничений (16)) транспортной задачи на единицу меньше числа уравнений r (A) = m + n – 1.

4.3. Построение исходного опорного плана

 

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

Клетки, в которых стоят отличные от нуля x_ij, называют загруженными,остальные – свободными.

План, содержащий m + n – 1 загруженную клетку, называется не-вырожденным. Если число занятых клеток будет меньше, чем m + n – 1, то построенный план вырожден.

Правило “северо-западного угла”. Первой загружается клетка (1; 1), условно называемая северо-западной. Если закрывается строка, то следующей загружается клетка (2; 1); если же закрывается столбец, то следующей загружается клетка (1; 2). Итак, каждый раз загружается клетка, соседняя либо по строке, либо по столбцу (в зависимости от конкретных данных задачи), до тех пор, пока не исчерпаются ресурсы. Последней будет загружена клетка (m; n). В результате загруженные клетки расположатся вдоль диагонали (1; 1)–(m; n), поэтому способ “северо-западного угла” называют еще диагональным способом.

Существенным недостатком способа “северо-западного угла” является игнорирование при загрузке клеток тарифов c_ij, поэтому построенный опорный план обычно оказывается весьма далеким от оптимального.

Правило “минимального элемента” (“минимальной стоимости”). В первую очередь заполняется клетка с минимальным значением тарифа. При этом в клетку записывается максимально возможное значение поставки. Затем из рассмотрения исключают строку, соответствующую поставщику, запасы которого полностью израсходованы, или столбец, соответствующий потребителю, спрос которого полностью удовлетворен. После этого из оставшихся клеток таблицы снова выбирают клетку с наименьшим тарифом. Процесс распределения заканчивается, когда все запасы поставщиков исчерпаны, а спрос потребителей полностью удовлетворен. В результате получаем опорный план, который должен содержать m + n – 1 загруженных клеток. В процессе заполнения таблицы могут быть одновременно исключены строка и столбец. Так бывает, когда полностью исчерпывается запас груза и полностью удовлетворяется спрос. В этом случае и в случае вырожденного плана в свободные клетки надо записать число 0 – “нуль-загрузку” (“базисный” нуль), условно считая такую клетку занятой (обычно клетки, которым соответствует наименьший тариф).

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

Циклом называется набор клеток матрицы планирования, в котором две и только две соседние клетки расположены в одном столбце или в одной строке, причем последняя клетка находится в той же строке (или столбце), что и первая. (О циклах более подробно будет сказано далее.)

Поскольку при заполнении таблицы учитываются величины тарифов, то, как правило, построенный план оказывается ближе к оптимальному, нежели построенный способом “северо-западного угла”.

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

Теорема 10 (теорема о потенциалах). Если план ТЗ является оптимальным, то ему соответствует система из m + n чисел , ,удовлетворяющих условиям для и для .

Числа , называются потенциалами соответственно i - го поставщика и j - го потребителя.

На теореме 10 основан метод решения ТЗ, названный методом потенциалов.

Метод потенциалов

Сущность этого метода состоит в следующем. После того, как найден первоначальный невырожденный план перевозок, каждому поставщику A_i (каждой строке) ставится в соответствие некоторое число , а каждому потребителю B_j (каждому столбцу) – некоторое число . Числа u_i, v_j – потенциалы A_i и B_j (u_i, v_j произвольного знака).

Согласно теореме о потенциалах, числа u_i и v_j выбирают так, чтобы в любой загруженной клетке их сумма равнялась тарифу этой клетки, т. е.

.

(21)

Так как всех занятых клеток должно быть m + n – 1, а чисел u_i и v_j должно быть m + n, то для нахождения потенциалов u_i, v_j получаем систему из m + n – 1 уравнений (21) с m + n неизвестными. В этой системе уравнений на одно меньше, чем неизвестных, поэтому один потенциал можно задать произвольно, например равным нулю. Тогда остальные потенциалы определяются однозначно.

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

 

.

(22)

 

При этом S_ij – оценка свободной клетки.

Если для всех свободных клеток оценки S_ij ³ 0, то опорный план перевозок является оптимальным.

Если хотя бы для одной из клеток S_ij < 0, то план неоптимален, и нужно переходить к новому плану.

 

 

4.5. Переход к новому плану

 

порядок перехода к новому плану следующий:

1. Клетка, для которой значение S_ij минимально, является перспективной и подлежит загрузке. Если таких клеток несколько, то берем любую.

2. Для выбранной перспективной клетки строим цикл, т. е. составляем замкнутый контур, по которому следует перераспределить груз. Цикл строится лишь для свободной клетки. Если из занятых клеток образуется цикл, то план перевозок не является опорным. Контур представляет собой замкнутую ломаную линию, состоящую из горизонтальных и вертикальных направленных отрезков (пересекаются под прямым углом), соединяющих середины клеток, из которых одна (именно перспективная) свободна, а все остальные загружены. В цикле всегда четное число клеток. Для каждой свободной клетки такой контур существует и является единственным. Точка, в которой меняется направление контура (горизонтальное на вертикальное или наоборот), называется вершиной цикла. В одной строке или одном столбце могут находиться две и только две вершины.

Точки самопересечения контура вершинами не являются.

Некоторые примеры циклов приведены на рис. 7.

 

рис. 7

 

3. Расставим поочередно знаки “+” и “–” в вершинах цикла. В перспективной клетке ставим знак “+”; затем, двигаясь по вершинам цикла, ставим поочередно знаки “–” и “+”, пока не придем к исходной вершине.

4. В клетках, соответствующих “отрицательным” вершинам, отыскивается наименьший груз (обозначим его q), который “перемещается” по клеткам цикла, т. е. прибавляется к поставкам x_ij в клетках со знаком “+” (включая свободную) и вычитается в клетках со знаком “–”.

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

Процесс продолжается, пока не получится оптимальный план перевозок. В результате остается подсчитать минимальные расходы (z _min).

Примечание. Если все S_ij > 0, то полученный оптимальный план единственный. В случае, если хотя бы одна оценка S_ij = 0, имеем бесчисленное множество оптимальных планов с одним и тем же значением целевой функции.

 

4.6. Алгоритм решения транспортной задачи
методом потенциалов

 

приведем алгоритм метода потенциалов:

1. Условие задачи записывают в форме распределительной таблицы.

2. Сравнивают общий запас продукта с суммарным спросом и в случае нарушения равенства (18) вводят фиктивного поставщика (потребителя).

3. Строят начальный опорный план по одному из правил.

4. Вычисляют потенциалы поставщиков и потребителей u_i и v_j , решив систему уравнений типа (21).

5. Вычисляют оценки S_ij для всех свободных клеток по формуле (22). Если оценки всех свободных клеток неотрицательны, то исследуемый план является оптимальным, и остается подсчитать транспортные расходы. Если же среди оценок есть отрицательные, то выбирают клетку с наименьшей отрицательной оценкой и переходят к следующему пункту алгоритма.

6. Загружают выделенную в предыдущем пункте свободную клетку (пункт 4.5), получают новый опорный план и возвращаются к пункту 4 алгоритма.

Пример 8. Решить транспортную задачу методом потенциалов, для которой известно, что a_i – запас груза i -го поставщика, b_j – потребность j -го потребителя, C = (c_ij) – матрица затрат на перевозку одной единицы груза:

 

a 1 = 12; a 2 = 3; a 3 = 10;

b 1 = 14; b 2 = 10; b 3 = 6;

.

 

Решение

Поместим все данные задачи в табл. 14.

 

 

Таблица 14

bj
ai

 

 

Проверим, сколько единиц однородного продукта содержат поставщики (12 + 3 + 10 = 25) и сколько единиц однородного продукта нужно доставить потребителям (14 + 10 + 6 = 30).

Так как 25 < 30, т. е. , то имеем открытую модель транспортной задачи.

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

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

 

.

 

Все тарифы на доставку продукта фиктивным поставщиком равны нулю: .

Имеем ТЗ закрытого типа, которую решаем методом потенциалов (табл. 15).

Построим первоначальный (опорный) план методом “минимального элемента” (табл. 16).

 

 

Таблица 15

	bj
	ai

 

Таблица 16

	bj
	ai

 

В результате получаем матрицу перевозок

 

 

План X ₁ является невырожденным (m + n – 1 = 4 + 3 – 1 = 6). Общая стоимость перевозки грузов по этому плану составит

 

z ₁ = 1 × 7 + 0 × 5 + 1 × 3 + 4 × 7 + 5 × 3 + 0 × 5 = 53.

 

Потенциалы поставщиков и потребителей определены непосредственно на рис. 8.

	7 –	5 +
	7 +		3 –
5		5 –	· +

Рис. 8

 

Имеют место следующие оценки свободных клеток:

 

S 13 = 2 – (–3 + 5) = 0;	S 32 = 6 – (0 + 3) = 3 > 0;
S 21 = 3 – (– 4 + 4) = 3 > 0;	S 41 = 0 – (–3+ 4) = –1 < 0;
S 22 = 4 – (– 4 + 3) = 5 > 0;	S 43 = 0 – (–3 + 5) = –2 < 0.

 

Так как S ₄₁ < 0 и S ₄₃ < 0, то план является неоптимальным. Наиболее потенциальной и перспективной является клетка (4; 3). Строим для клетки (4; 3) цикл непосредственно на рис. 8. В цикл войдут клетки (4; 3), (3; 3), (3; 1), (1; 1), (1; 2), (4; 2). Проставим знаки “+” и “–” в цикле поочередно, начиная со свободной клетки. Наименьшее количество груза, стоящее в вершинах цикла с отрицательным знаком, – . В результате смещения по циклу получим новый план (рис. 9).

Для этого плана определяем новые потенциалы и оценки свободных клеток:

 

S 13 = 2 – (0 + 0) = 2 > 0;	S 32 = 6 – (3 + 0) = 3 > 0;
S 21 = 3 – (1 + 1) = 1 > 0;	S 33 = 5 – (3 + 0) = 2 > 0;
S 22 = 4 – (1 + 0) = 3 > 0;	S 41 = 0 – (0 + 1) = –1 < 0.

 

	4 –	8 +		u 1 = 0
				u 2 = 1
				u 3 = 3
5	+ ·	–		u 4 = 0
	v 1 = 1	v 2 = 0	v 3 = 0

 

Рис. 9

 

Так как S ₄₁ < 0, то план является неоптимальным. Строим для клетки (4; 1) цикл непосредственно на рис. 9. В цикл войдут клетки (4; 1), (1; 1), (1; 2), (4; 2). Проставим знаки в цикле. В отрицательных вершинах построенного для клетки (4; 1) цикла наименьшее количество груза – .

После смещения по циклу 2 единиц груза получим новый план перевозок (рис. 10).

 

				u 1 = 0
				u 2 = 0
				u 3 = 3
				u 4 = –1
	v 1 = 1	v 2 = 0	v 3 = 1

Рис. 10

 

Как и для предыдущего плана перевозок, все потенциалы поставщиков и потребителей определены на рис. 10. Имеют место следующие оценки свободных клеток:

 

S 13 = 2 – (0 + 1) = 1 > 0,	S 32 = 6 – (3 + 0) = 3 > 0,
S 21 = 3 – (0 + 1) = 2 > 0,	S 33 = 5 – (3 + 1) = 1 > 0,
S 22 = 4 – (0 + 0) = 4 > 0,	S 42 = 0 – (–1 + 0) = 1 > 0.

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

 

.

 

значение целевой функции составит

 

(усл. ед.).

 

Загрузка x ₄₁ = 2 и x ₄₃ = 3 для фиктивного поставщика указывает на остаток нераспределенного груза в размере 5 ед. у потребителей B ₁ и B ₃.

Ответ: усл. ед.

Вопросы для самоконтроля

1. Экономико-математическая модель транспортной задачи.

2. Теорема о существовании допустимого плана.

3. Закрытая и открытая модели транспортной задачи.

4. Построение исходного опорного плана (правило “северо-западного угла”, “минимального элемента”).

5. Экономическая интерпретация метода потенциалов решения транспортной задачи.

6. Переход к новому плану (построение замкнутого контура).

7. Алгоритм метода потенциалов.