Нахождение оптимального распределения поставок

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

Установление оценок для всех заполненных и свободных клеток означаем оценку данного распределения поставок.

Оценим, например, распределение поставок, приведенное в таблице 6.3. Для этого перепишем эту таблицу (табл. 6.5), снабдив ее дополнительными строкой и столбцом.

В 1-м столбце дополнительной строки запишем 0. Для того чтобы оценка в заполненной клетке (3.1) равнялась нулю, в 3-й строке дополнительного столбца нужно записать – 1.

Таблица 6.4 – Перераспределение поставок

					—4
					—6
					—1
					—6
	+2	+3	+3	+3

В этом случае оценка клетки (3.1) действительно равна нулю (1 + 0 – 1)=0. Для обращения в ноль оценки клетки (4.1) нужно в 4-й строке дополнительного столбца записать -6. Далее в 5-ом столбце дополнительной строки запишем число 3 для получения нулевой оценки в клетке (4.5), во 2-й строке дополнительного столбца для получения нулевой оценки в клетке (2.5) — число — 6 и т. д., пока не заполним все столбцы дополнительной строки и все строки дополнительного столбца.

Составим новую таблицу, в каждую клетку которой вместо показателя затрат запишем оценку.

Оценки всех заполненных клеток таблицы 6.5 равны нулю. Все свободные клетки, кроме клеток (1.1), (2.1) и (4.4), имеют положительные оценки.

Вернемся к оценкам циклов, которые были установлены и подсчитаны для циклов некоторых клеток в предыдущем параграфе.

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

Таблица 6.5 – Перераспределение поставок и оценка клеток

					—1
			—1
	+1		+1

Оценки, помещенные в табллице 6.6, свидетельствуют, что первона­чальное распределение, приведенное в табл. 17.3 и 17.5, не является оптимальным, поскольку клетка (4.4) имеет отрицательную оценку и ее следует перевести в число заполненных. Цикл для этой клетки был изображен на рис. 42. Минимальная поставка в четных клетках этого цикла равна 40 ед. Эту поставку перераспределяем в цикле: в клетку (4.4) запишем эту поставку, из поставки клетки (1.4) вычтем, к поставке клетки (1.2) прибавим, а клетка (4.2) станет свободной. Поставки в остальных клетках таблицы не изменятся. Новое рас­пределение поставок запишем в табл. 17.6.

Для оценки вновь полученного распределения сделаем пересчет оценок, добиваясь, чтобы оценка во вновь заполненной клетке (4.4) обратилась в нуль. Для этого к 4-му столбцу табл. 17.6 прибавим 1. Однако эта операция «портит» нулевую оценку в клетке (1.4). Чтобы этого не произошло, вычтем 1 из всех оценок 1-й строки. Для сохранения нулевой оценки в заполненной клетке (1.2) этой строки прибавим 1 к оценкам 2-го столбца.

Таблица 6.6 – Новое перераспределение поставок

-1
					—1
+ 1

Новые оценки запишем в таблице 6.7. Оценки этой таблицы свидетельствуют о том, что и полученное распределение не оптимально. Выгодной на этом шаге является клетка (1.1). Цикл распределения для этой клетки изображен на рисунке 6.3.

Отметим, что в цикл для клетки (1.1) вовлечены другие клетки, нежели при первоначальном распределении поставок.

Рисунок 6.3 - цикл для клетки (1.1)

Минимальную поставку четных клеток, равную 10 ед., передвигаем в цикле. Новое распределение поставок запишем в таблице 6.7.

К оценкам 1-го столбца таблицы 6.7 прибавим 1, а из оценок 3-й строки вычтем 1. Полученные оценки поместим в таблицу 6.8.

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

Таблица 6.8 – Оценки клеток

Замечание. Наличие в таблице 6.8, не содержащей отрицательных оценок, нулевой оценки в незаполненной клетке (1.5) служит признаком того, что полученное оптимальное распределение поставок не является единственным. Можно перераспределить поставки в цикле для клетки (1.5) и получить еще одно оптимальное распределение поставок, но стоимость затрат при этом не изменится.

Для окончательного решения задачи следует вычислить минималь­ные затраты на перевозки. Для этого составим итоговую таблицу (табл. 6.9), в которую включим показатели затрат из таблицы 6.3 и оптимальное распределение поставок из таблицы 6.7.

Таблица 6.9 – Итоговя таблица

Находим F_min = 40 + 130 + 25 + 240 + 135 + 75 + 100 + 75 = 820 ден. ед. Значит, экономия по сравнению с первоначальным рас­пределением поставок составляет 870 - 820 = 50 ден. ед. Этот же результат можно получить и другим путем, если учесть, что переда­ча поставки в клетку (4.4) дает экономию в 40 ден. ед., а в клетку (1.1) - 10 ден. ед.

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

Как было отмечено в п. 6.1, если суммарная мощность поставщиков не равна суммарному спросу потребителей, т.е. , то модель транспортной задачи называется открытой. Здесь возможны два случая:

а) объем мощностей поставщиков меньше суммарного спроса потребителей, т. е.

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

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

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

Следует только иметь в виду, что, считая число заполненных клеток равным k + l - 1, в число поставщиков нужно включить и фиктивного поставщика.

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

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

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

Пример 6.2. Найти оптимальное распределение поставок в следующей задаче:

Таблица 6.10 – Условие к примеру 6.2

Поставщики	Мощности поставщиков	Потребители и их спрос

Решение. Суммарная мощность поставщиков 190 ед., суммарный спрос потребителей = 200 ед. Таким образом, спрос потребителей на 10 ед. превышает объем мощностей поставщиков. Введем фиктивного поставщика, записав ему мощность, равную 10 ед. Исходную таблицу дополняем еще одной строкой - строкой фиктивного поставщика. В новую таблицу (табл. 6.11) сразу же поместим дополнительные строку и столбец, чтобы записать в них числа, обращающие оценки заполненных клеток в нули. В этой же таблице проведено первоначальное распределение поставок с учетом наименьших затрат. Количество заполненных клеток соответствует норме: 4+4 - 1 = 7.

Таблица 6.11 – Распределение поставок о оценка клеток

						-2
						-2
						-1
Ф						-1
			+1	-1	+1

В таблице 6.12 оценивается первоначальное распределение поставок.

Таблица 6.12 – Распределение поставок

- 1		- 2		+2

Как следует из таблицы 6.12, распределение поставок в таблице 6.11 не является оптимальным. Две клетки (4.1) и (4.3) имеют отрицательные оценки, поэтому они являются выгодными и в них следует дать поставки.

Будем придерживаться правила: давать поставку, прежде всего в клетку, имеющую наибольшую по абсолютной величине отрицательную оценку (даже если она и не является самой выгодной).

Так как клетка (4.3) имеет большую по абсолютной величине отрицательную оценку, то строим для нее цикл (рис. 6.4).

Рисунок 6.4 – Перераспределение поставок для клетки (4.3)

Минимальная поставка четных клеток равна 10, она находится в клетке (4.4). Передвигаем эту поставку в 10 ед. в цикле. Новое распределение поставок запишем в таблицу 6.12.

Новое распределение оценивается в табллице 6.13.

Эта таблица уже не содержит отрицательных оценок, следовательно, распределение поставок, приведенное в таблице 6.12, - оптимальное. Так как нулевые оценки имеют и две свободные клетки, то оптимальное распределение не единственное.

При оптимальном распределении поставок потребитель 3 недополучит 10 ед. груза. Для подсчета минимальных затрат на перевозки составим итоговую таблицу (табл. 6.14).

Таблица 6.13 - Новое распределение поставок

Таблица 7.14 - Итоговая таблица

Таким образом - F_min = 35+15+40+120+100 + 195 = 505 ден. ед.