Циклы в транспортной таблице

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

1) в этом наборе не менее трех клеток;

2) любые две последовательные клетки данного набора, включая последнюю и первую, расположены в одном ряду (строке или столбце) таблицы;

3) никакие три последовательные клетки этого набора не находятся в одном и том же ряду таблицы.

3. Построение начального плана

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

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

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

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

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

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

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

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

Пример. Для транспортной задачи с условиями , , построить планы методами северо-западного угла и наименьшей стоимости и сравнить значения целевой функции на этих планах.

Решение. Данная задача с правильным балансом, так как . Запишем ее условия в виде таблицы и построим ее план методом северо-западного угла.

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

		–	–
–
–

Теперь заполняем левую верхнюю свободную клетку таблицы, куда помещаем .

		–	–
–
–	–

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

		–	–
–			–
–	–

Оставшиеся запасы третьего поставщика в количестве 45 единиц распределяем между третьим и четвертым потребителями .

		–	–
–			–
–	–

Общая стоимость этого плана: .

–	–
	–	–
–			–

Общая стоимость этого плана: .

4. Критерий оптимальности плана

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

для всех таких, что и

для всех таких, что .

5. Проверка плана транспортной задачи на оптимальность

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

Проверка этого плана на оптимальность состоит из следующих этапов.

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

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

3. Проверка плана на оптимальность. Для каждой свободной клетки транспортной таблицы вычисляем величину .

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

Пример 1. Для транспортной задачи , , , , , , исследовать на оптимальность план перевозок, построенный методом наименьшей стоимости.

Решение. Сначала, используя метод наименьшей стоимости, находим план данной задачи. Этот план записан в таблице.

	–
–1	–	–
–1			–

Для проверки построенного плана на оптимальность находим потенциалы поставщиков из системы

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

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

Для каждой свободной клетки таблицы вычисляем . Получаем , , , .

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

Дата добавления: 2015-06-30; просмотров: 215; Нарушение авторских прав

Мы поможем в написании ваших работ!