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

1) Проверить выполнение условия (2.3). Если оно не выполняется, то перейти к соответствующей закрытой матричной модели ТЗ.

2) Построить невырожденный начальный опорный план (метод «минимального элемента», метод «северо-западного угла» или метод Фогеля).

3) Методом потенциалов проверить найденный план на оптимальность.

4) Если план оптимален, то задача решена.

5) Если план оптимален, но не единственен, то можно найти еще один оптимальный план.

6) Если пункты 4) – 5) алгоритма не выполняются, найти новый опорный план и перейти к пункту 3).

Замечание

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

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

Существует несколько методов построения начального опорного плана – это метод «минимального элемента», метод «северо-западного угла», метод Фогеля и другие.

 

Нахождение начального опорного плана методом

«минимального элемента»

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

Пример 2.2

По данным примера 2.1 найти начальный опорный план методом «минимального элемента».

Решение

Воспользуемся распределительной таблицей закрытой модели ТЗ (табл. 2.3). Наименьшие затраты на перевозку топлива соответствуют маршруту , поэтому заполним любую клетку столбца , например клетку (1,5) и . Таким образом, потребности в топливе потребителя удовлетворены и пятый столбец из рассмотрения исключаем, а в хранилище останется 70–10=60 т топлива. Просматриваем оставшиеся клетки таблицы. Наименьшие тарифы имеют клетки (2,4) и (3,3): . Заполняем любую из этих клеток, например клетку (2,4) и . Столбец исключаем, а в хранилище при этом останется 90–40=50 т топлива. Просматриваем оставшиеся клетки таблицы. Наименьший тариф имеет клетка (3,3). Заполним ее: и исключаем столбец , а в хранилище осталось 50–40=10 т топлива. Просматриваем оставшиеся клетки таблицы. Наименьший тариф имеет клетка (3,1): . Клетку (3,1) заполним и исключаем строку , а потребителю недостает 50–10=40 т топлива. Далее по величине тарифа заполним клетку (2,2), т.к. , при этом и исключаем строку , а потребителю недостает 70–50=20 т топлива. Далее по величине тарифа заполним клетку (1,2), т.к. и и исключаем столбец , а в хранилище осталось 60–20=40 т топлива. Заполним оставшуюся клетку (1,1): . Итак, в распределительной таблице найден невырожденный (число занятых клеток k=m+n –1=3+5–1=7) начальный опорный план (табл. 2.4).

Таблица 2.4

	Потребители	Запас топлива, т
Хранилища
Потребность в топливе, т

 

или . Значение целевой функции на найденном начальном опорном плане (транспортные издержки для этого плана):

(усл. ден. ед.)

 

Нахождение начального опорного плана методом

«северо-западного угла»

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

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

Необходимо иметь в виду, что метод северо-западного угла не учитывает тарифы перевозок, поэтому опорный план, построенный по данному методу, может быть далек от оптимального.

Пример 2.3

По данным примера 2.1 найти начальный опорный план методом «северо-западного угла».

Решение

Воспользуемся распределительной таблицей закрытой модели ТЗ (табл. 2.3).

Распределяем топливо из первого хранилища. Заполним клетку (1,1) максимально-возможным значением: . Таким образом, потребности в топливе потребителя удовлетворены и первый столбец из рассмотрения исключается, а в хранилище останется 70–50=20 т топлива. Теперь левой верхней (северо-западной) клеткой оставшейся части таблицы является клетка (1,2) и . Т.к. в первом хранилище топлива больше нет, то первая строка исключается, а потребителю недостает 70–20=50 т топлива.

Распределяем топливо из второго хранилища. Заполним клетку (2,2): . Столбец исключаем, а в хранилище осталось 90–50=40 т топлива. Теперь заполним клетку (2,3): и исключаем по своему усмотрению либо второго поставщика, либо третьего потребителя. Пусть исключили третьего потребителя. Тогда в хранилище осталось 40–40=0 т топлива. Теперь заполним клетку (2,4): и исключаем вторую строку.

Распределяем топливо из третьего хранилища. Теперь заполним клетку (3,4): . Столбец исключаем, а в хранилище осталось 50–40=10 т топлива. Незаполненной осталась одна клетка (3,5) и . Итак в распределительной таблице записан невырожденный (число занятых клеток k=m+n –1=3+5–1=7) начальный опорный план (табл. 2.5).

Таблица 2.5

	Потребители	Запас топлива, т
Хранилища
Потребность в топливе, т

 

или . Значение целевой функции на найденном начальном опорном плане (транспортные издержки для этого плана):

(усл. ден. ед.)

 

Нахождение начального опорного плана методом Фогеля

Данный метод состоит из ряда однотипных шагов (этапов), на каждом из которых:

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

· в линии с наибольшей разностью заполняется максимально возможным значением клетка, соответствующая минимальному тарифу;

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

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

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

Пример 2.4

По данным примера 2.1 найти начальный опорный план методом Фогеля.

Решение

Воспользуемся распределительной таблицей закрытой модели ТЗ (табл. 2.3).

На первом этапе максимальная разность «4 » принадлежит столбцу . Заполняем клетку с минимальным тарифом в этом столбце. Это клетка (2,4) и . Столбец исключаем, а в хранилище при этом останется 90–40=50 т топлива.

На втором этапе максимальная разность «3 » принадлежит строкам и . Выбираем любую из них, например, строку . Заполняем клетку с минимальным тарифом в этой строке. Это клетка (1,5) и . Столбец исключаем, а в хранилище при этом останется 70–10=60 т топлива.

На третьем этапе максимальная разность «2 » принадлежит столбцам и . Выбираем любой из них, например, столбец . Заполняем клетку с минимальным тарифом в этом столбце. Это клетка (3,1) и . Исключаем по своему усмотрению либо третьего поставщика, либо первого потребителя. Пусть исключили первого потребителя. Тогда в хранилище осталось 50–50=0 т топлива.

На четвертом этапе максимальная разность «3 » принадлежит строке . Заполняем клетку с минимальным тарифом в этой строке. Это клетка (3,3) и . Строку исключаем, а потребителю недостает 40–0=40 т топлива.

На пятом этапе максимальная разность «2 » принадлежит строке и столбцу . Выбираем любую из этих линий, например, строку . Заполняем клетку с минимальным тарифом в этой строке. Это клетка (1,5) и . Строку исключаем, а потребителю недостает 70–50=20 т топлива.

Т.к. незаполненные клетки остались в одной линии (в строке клетки (1,2) и (1,3)), то заполняем их в порядке увеличения тарифов, т.е. сначала заполним клетку (1,3): , затем клетку (1,2) и .

Итак, в распределительной таблице найден невырожденный (число занятых клеток k=m+n –1=3+5–1=7) начальный опорный план (табл. 2.6).

Таблица 2.6

Этапы

3

2

3

–

Э т а п

4

–

2

–

–

–

–

–

ы

–

–

–

 

или . Значение целевой функции на найденном начальном опорном плане (транспортные издержки для этого плана):

(усл. ден. ед.)

Проверка на оптимальность невырожденного опорного плана методом потенциалов

1) Каждому поставщику поставим в соответствие потенциал , а каждому потребителю потенциал .

Тогда каждой занятой клетке будет соответствовать уравнение:

.

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

;

а) если все оценки положительны, то найденный опорный план оптимален и единственен ;

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

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

 

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

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

Цикл пересчета

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

Пример 2.5

По данным примера 2.1 исходя из начального опорного плана найденного в примере 2.2 решить транспортную задачу (найти оптимальный план перевозок и минимальные затраты на транспортировку всего топлива).

Решение

Воспользуемся распределительной таблицей, в которой найден начальный опорный план методом «минимального элемента» (табл. 2.4 и табл. 2.7).

Таблица 2.7

Потребители

Запас топлива, т

Хранилища

Потребность в топливе, т

 

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

Система является линейно-зависимой, для нахождения одного из частных решений присвоим одному из потенциалов любое числовое значение, например , и найдем значения остальных потенциалов:

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

Таблица 2.8

	Потребители	Запас топлива, т
Хранилища
												1)
	–				+
												6)
												5)
	+				–
Потребность в топливе, т
	2)	3)	7)	8)	4)

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

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

Составим цикл пересчета относительно клетки (1,3) и присвоим клеткам цикла знаки «+» и «–». Свободной клетке (1,3) присвоим знак «+», а дальше, по часовой стрелке, следующей клетке цикла (3,3) присвоим знак «–», затем клетке цикла (3,1) присвоим знак «+», далее клетке цикла (1,1) присвоим знак «–» (табл. 2.8).

Из клеток, помеченных знаком «–», выбираем наименьшее количество груза . Чтобы получить новый опорный план нужно прибавить значение к поставкам в клетках, помеченных знаком «+» и вычесть из поставок в клетках, помеченных знаком «–», нули при этом не записываются (табл. 2.9). Т.к. значение оказалось в двух клетках цикла (клети (1,1) и (3,3) табл. 2.8), то чтобы новый опорный план оказался невырожденным необходимо в одной из этих клеток поставить базисный ноль и считать ее занятой (табл. 2.9).

Таблица 2.9

Потребители

Запас топлива, т

Хранилища

Потребность в топливе, т

Проверим найденный план на оптимальность. Потенциалы строк и столбцов найдены непосредственно в распределительной таблице (табл. 2.9).

Найдем оценки свободных клеток:

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

Итак, получен оптимальный план:

.

Транспортные издержки для этого плана:

(усл. ден. ед.).

Итак, по оптимальному плану, необходимо из хранилища А₁ потребителю B₂ доставить 20 т топлива, потребителю B₃ – 40 т топлива; из хранилища А₂ потребителю В₂ доставить 50 т топлива, а потребителю В₄ – 40 т топлива; из хранилища А₃ доставить 50 т топлива потребителю В₁.

При этом затраты на транспортировку будут минимальными и составят 490 усл. ден. ед. Нераспределенное топливо, в размере 10 т останется в хранилище А₁.

Пример 2.6

В четырех хранилищах имеется соответственно 100, 50, 120 и 80 т картофеля. Требуется так спланировать перевозки картофеля к пяти овощным магазинам спрос которых равен соответственно 20, 120, 180, 30 и 100 т, чтобы суммарные транспортные издержки были минимальными. Известны стоимости перевозок 1 т картофеля (ден. ед.) из -го () хранилища в -й () магазин .

Требуется: а) составить математическую модель задачи; б) найти оптимальный план перевозок и минимальные транспортные издержки (решить задачу методом потенциалов исходя из начального опорного плана найденного методом «северо-западного угла»).

Решение

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

(20+120+180+30+100) – (100+50+120+80)=100.

Тарифы фиктивного поставщика равны нулю, т.е. .

Матричная модель сбалансированной задачи будет иметь вид:

 

	Магазины	Запас, т
Хранилища	В1	В2	В3	В4	В5
А1
А2
А3
А4
А5
Спрос, т

 

а) составить математическую модель задачи.

Введем переменные – количество картофеля, которое необходимо доставить из -го хранилища в -й магазин.

Целевая функция (затраты на перевозку всего картофеля) будет иметь вид:

Система ограничений задачи:

б) Найдем начальный опорный план методом «северо-западного угла» (табл. 2.10).

Таблица 2.10

Магазины

Запас, т

Хранилища

В1

В2

В3

В4

В5

А1

⇐ Предыдущая12345 Поделиться: Поиск по сайту ©2015-2024 poisk-ru.ru Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование. Дата создания страницы: 2016-04-26 Нарушение авторских прав и Нарушение персональных данных

 Поиск по сайту: Читайте также: Деталирование сборочного чертежа Когда производственнику особенно важно наличие гибких производственных мощностей? Собственные движения и пространственные скорости звезд Тема 11. Банковские риски и способы их оценки Опросник «Активность повседневной жизни» Интересно: История возникновения народной куклы Что такое концерт, специфика, классификация Роль современного учителя в повышении качества школьного образования Роль энергетики в жизни и развитии общества Обратная связь