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

Модель ТЗ называют закрытой, если суммарный объем груза, имеющегося у поставщиков, равен суммарному спросу потребителей, т. е. выполняется равенство

.

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

или ,

то модель задачи называют открытой.

Для разрешимости ТЗ с открытой моделью необхо­димо преобразовать ее в закрытую. Так, при выполне­нии первого условия необходимо ввести фиктивный (п+1)-й пункт назначения В_п+1, т. е. в матрице задачи предусматривается дополнительный столбец. Спрос фик­тивного потребителя полагают равным небалансу, т. е.

,

а все соответствующие тарифы – одинаковыми, чаще всего равными нулю.

Аналогично при выполнении второго условия вводится фиктивный поставщик.

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

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

Построение опорных планов, а также преобразование их будем производить непосредственно в распределительной таблице. Если в плане перевозок переменная х _ik равна некоторому числу а ≠ 0, то это число записываем в соот­ветствующую клетку (i; k) и считаем ее занятой или ба­зисной, если же х _ik = 0, то клетку (i; k) оставляем свобод­ной. При этом число занятых опорным планом клеток в соответствии с теоремой 11.2 должно быть равно т+п-1, а остальные тп - (т+п-1) = (т-1) (п-1) клеток бу­дут свободными.

Рассмотрим правило «северо-западного угла». Сущ­ность его состоит в следующем. Пользуясь табл. 11.1, будем распределять груз, начиная с загрузки левой верхней, условно называемой северо-западной, клет­ки (1; 1), двигаясь затем от нее по строке вправо или по столбцу вниз. В клетку (1; 1) занесем меньшее из чисел a₁, b₁, т. е. x₁₁ = min (a₁, b₁). Если a₁> b₁, т. е. x₁₁ = b₁ и пер­вый потребитель В₁ будет полностью удовлетворен. В дальнейшем 1-й столбец таблицы в расчет не принима­ется; в нем переменные х _ik =0 для i=2, т.

Двигаясь вправо по первой строке таблицы, заносим в соседнюю клетку (1; 2) меньшее из чисел a₁-b₁, и b₂, т. е. x₁₂ = min (a₁-b₁, b₂). Если a₁-b₁< b₂, то запасы первого поставщика исчерпаны и первая строка таблицы в дальнейшем в расчет не принимается. Переходим к аналогичному распределению запаса груза второго по­ставщика.

Если a₁< b₁, т. е. x₁₁ = a₁. При этом запас первого поставщика будет исчерпан, а потому х _ik =0 для k=2, п. Первая строка из дальнейшего рассмотрения исключается. Переходим к распределению запасов второго поставщика. В клетку (2; 1) заносим наименьшее из чисел (а₂, b₁- а₁).

Заполнив таким образом клетку (1; 2) или (2; 1), переходим к загрузке следующей клетки по второй строке либо по второму столбцу. Процесс распределения по вто­рой, третьей и последующим строкам (столбцам) произво­дится аналогично распределению по первой строке или первому столбцу до тех пор, пока не исчерпаются ресурсы. Последней заполняется клетка (т; п).

Проиллюстрируем правило «северо-западного угла» на примере.

Пример 11.1. Составить план перевозок зерна из районов А1, А2, А3 и А4, в которых запасы составляют соответственно 800, 700, 1000 и 500 тыс.ц, на три элеватора В1, В2 и В3 мощностью 1000, 1100 и 900 тыс.ц. Затраты на перевозку 1 ц зерна из районов на элеваторы приведены в табл. 11.2.

 

Таблица 11.2

Районы	Элеваторы			Запас в районе
	В1	В2	В3
	Затраты на перевозку 1 ц, руб.
А1	3	5	6	800
А2	7	2	4	700
А3	4	3	5	1000
А4	6	4	7	500
Мощность элеватора	1000	1100	900	3000

 

Решение. Установим характер задачи. Поскольку

800+700+1000+500=1000 + 1100+900=3000,

заключаем, что данная ТЗ обладает закрытой моделью. В клетку (1; 1) табл. 5.3 помещаем x₁₁ = min (800, 1000) =800 тыс. ц зерна. Весь запас зерна района А1 отгружен на элеватор В1. Недостающее количество зерна на элеватор В1 поставляется из района А2: в клетку (2; 1) поме­щаем x₂₁ = min (700, 1000 - 800) =200 тыс. ц. В этом случае мощность элеватора В1 будет полностью использована. Остаток зерна района А2 отправляем на элеватор В2: в клетку (2; 2) помещаем x₂₂ = min (700 - 200, 1100) =500 тыс. ц зерна. Запас зерна района А2 исчерпан, и пере­ходим к перевозке зерна района А3. В клетку (3; 2) помещаем x₃₂ = min (1000, 1100 - 500) = 600 тыс. ц зерна. Мощность элеватора В2 полностью использована. Поставку зерна производим на элеватор В3. В клетку (3; 3) помещаем x₃₃ = min (900, 1000 - 600) =400 тыс. ц зерна. Отгрузка зерна из района А3 полностью произведена. Производим от­грузку зерна из района А4. В клетку (4; 3) помещаем x₄₃ = min (500, 900 - 400) =500 тыс. ц зерна. В результате полной отгрузки зерна на элеваторы получили план перевозок X₁ (табл. 11.3).

 

 

Таблица 11.3

Районы	Элеваторы			Запас в районе
	В1	В2	В3
	Затраты на перевозку 1 ц, руб.
А1	3	5	6	800
	800
А2	7	2	4	700
	200	500
А3	4	3	5	1000
		600	400
А4	6	4	7	500
			500
Мощность элеватора	1000	1100	900	3000

Суммарные расходы на перевозку зерна составят:

f( X₁) = 3*800+7*200+2*500+3*600+3*400+7*500=12 100 руб.

Рассмотрим правило «минимального элемента». Сущ­ность его состоит в следующем. Просматриваются тарифы табл. 11.1 и в первую очередь заполняется клетка с мини­мальным значением тарифа. При этом в клетку записы­вается максимально возможное значение поставки. Затем из рассмотрения исключают строку, соответствующую по­ставщику, запасы которого полностью израсходованы, или столбец, соответствующий потребителю, спрос которого полностью удовлетворен. После этого из оставшихся кле­ток таблицы снова выбирают клетку с наименьшим тари­фом. Процесс распределения заканчивается, когда все запасы поставщиков исчерпаны, а спрос потребителей полностью удовлетворен. В результате получаем опорный план, который должен содержать т+п-1 загруженных клеток. В процессе заполнения таблицы могут быть одно­временно исключены строка и столбец. Так бывает, когда полностью исчерпывается запас груза и полностью удовле­творяется спрос (вырожденная задача). В этом случае в свободные клетки надо записать число 0 - «нуль-за­грузка», условно считая такую клетку занятой. Однако число 0 записывается в те свободные клетки, которые не образуют циклов с ранее занятыми клетками.

Пример 11.2. Проиллюстрируем правило «минимального элемента» для транспортной задачи, представленной табл. 11.2, и сравним значения целевых функций для планов, получен­ных по правилу «северо-западного угла» и правилу «ми­нимального элемента».

Решение. Просматривая табл. 11.2, замечаем, что минимальные затраты на перевозку зерна соответствуют маршруту А2-В2, поэтому в клетку (2; 2) табл. 5.4 помещаем x₂₂ = min (700, 1100) =700 тыс. ц зерна. В этом случае вторая строка таблицы в дальнейшем в расчет не принимается, так как запас зерна в районе А2 полностью доставлен на элеватор В2.

Просматриваем оставшиеся клетки таблицы. Наименьшие тарифы имеют клетки (1; 1), (3; 2) – 4. В клетку (1; 1) помещаем x₁₁ = min (800, 1000) = 800 тыс. ц, а в клетку (3; 2) x₃₂ = min (1000, 1100 - 700) =400 тыс. ц.

Далее по величине тарифа следует загружать клетки (3; 1), (4; 2),
(2; 3). Однако в результате загрузки клеток (1; 1), (2; 2), (3; 2) запас зерна в районах А1 и А2 и частично в районе А4 исчерпан. Мощность элеватора В2 полностью использована, а мощность элеватора В1 использована на
800 тыс. ц. Поэтому помещаем необходимое количество зерна в клетку (3; 1): x₃₁ = min (1000 - 400, 1000 - 800) = 200 тыс. ц. После этого мощность элева­тора В1 полностью использована. Остался элеватор В3, который может принять зерно из районов А3 и А4. В районе А3 осталось зерна

1000 – 400 - 200=400 тыс. ц,

а в районе А4 - 500 тыс. ц. В клетки (3; 3); (4; 3) помещаем необходимые количества зерна: x₃₃=400 тыс. ц, x₃₄=500 тыс. ц.

 

Таблица 11.4

Районы	Элеваторы			Запас в районе
	В1	В2	В3
	Затраты на перевозку 1 ц, руб.
А1	3	5	6	800
	800
А2	7	2	4	700
		700
А3	4	3	5	1000
	200	400	400
А4	6	4	7	500
			500
Мощность элеватора	1000	1100	900	3000

 

В результате полного распределения зерна получаем план Х₂, для которого значение целевой функции

f( X₂) = 3*800+2*700+4*200+3*400+3*400+7*500 =11 300 руб.

Сравнивая значения целевых функций для планов Х₁ и Х₂, получен­ных по правилам «северо-западного угла» и «минимального элемента», замечаем, что транспортные расходы по плану Х₂ на перевозку зерна из районов на элеваторы меньше на 800 руб.

Будет ли этот план оптимальным? Чтобы ответить на этот вопрос, необходимо знать признак оптимальности.

Теорема 11.3. Если план транспортной за­дачи является оптимальным, то ему соответствует система из m + n чисел , удовлетворяющих условиям   для  и   для

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

 

Из теоремы следует, что для оптимального плана ТЗ необходимо выполнение условий:

1) каждой занятой клетке в распределительной табли­це соответствует сумма потенциалов, равная тарифу этой клетки, т. е. ;

2) каждой свободной клетке соответствует сумма по­тенциалов, не превышающая тарифа этой клетки, т. е.

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

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

В соответствии с введенным понятием потенциалов и с учетом связей между моделями двойственных задач каж­дому поставщику (ограничению по запасам) поставим в соответствие потенциал , а каждому по­требителю (ограничению по спросу) – потенциал ,

Согласно теореме о потенциалах, каждой занятой клет­ке будет соответствовать уравнение . Так как всех занятых клеток должно быть т+п-1, т. е. на еди­ницу меньше числа потенциалов, то для определения чи­сел  необходимо решить систему из т+п-1 уравне­ний  с т+п неизвестными. Система неопреде­ленная, и, чтобы найти частные решения, одному из потен­циалов придаем произвольное числовое значение, тогда остальные потенциалы определяются однозначно. Для облегчения расчетов одному из потенциалов придают обычно значение, равное нулю.

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

.

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

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

Итак, если для опорного плана перевозок указанное условие оптимальности не выполняется, то за счет загруз­ки свободной клетки с отрицательной оценкой план пере­возок улучшается. Для наиболее перспективной свобод­ной клетки строится замкнутый цикл с вершинами в за­груженных клетках. Вершинам этого цикла условно приписываются знаки: свободной клетке – плюс, следую­щей по часовой или против часовой стрелки занятой клет­ке – минус, следующей – снова плюс и т. д. Из поставок в клетках цикла с «отрицательными» вершинами выби­рается наименьшее количество λ груза, которое и переме­щается по клеткам этого цикла: прибавляется к постав­кам в положительных вершинах и вычитается из поставок в отрицательных вершинах, в результате чего баланс цикла не нарушится.

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

Сформулируем алгоритм решения ТЗ методом потен­циалов:

1) построить опорный план по одному из правил;

2) вычислить потенциалы поставщиков и потребителей, решив систему уравнений ви­да ;

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

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

Решение. Для определения потенциалов составляем систему уравнений:

Положим, например, и₁ = 0, тогда .

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

Таблица 11.5

	1000		1100		900
800		3		5		6	и1 = 0
	800
700		7		2		4
			700
1000		4	-	3		5
	200		400		400	+
500		6		4		7
			+		500	-

 

Определим оценки свободных клеток:

Перспективной является клетка (4; 2) с оценкой –1. Строим для нее цикл непосредственно в таблице. В цикл войдут клетки (3; 2), (3; 3), (4; 3). Наименьшее количество груза, стоя­щее в вершинах цикла с отрицательным знаком, λ = min (400, 500) = 400. В результате смещения λ по циклу получим новый план (табл. 11.6).

Таблица 11.6

	1000		1100		900
800		3		5		6	и1 = 0
	800
700		7		2		4
			700	-	+
1000		4		3		5
	200				800
500		6	+	4	-	7
			400		100

 

Стоимость перевозок:

 руб.

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

Перспективной является клетка (2; 3) с оценкой –1. Строим для нее цикл непосредственно в таблице. В цикл войдут клетки (2; 2), (4; 2), (4; 3). Наименьшее количество груза, стоя­щее в вершинах цикла с отрицательным знаком, λ = min (700, 100) = 100. В результате смещения λ по циклу получим новый план (табл. 11.7).

Таблица 11.7

	1000		1100		900
800		3		5		6	и1 = 0
	800
700		7		2		4
			600		100
1000		4		3		5
	200				800
500		6		4		7
			500

Стоимость перевозок:

 руб.

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

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

Минимальные транспортные издержки для этого плана:  руб.

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

⇐ Предыдущая123456789

Поделиться: