Методы линейного программирования для решения транспортной задачи (стр. 5 из 6)
На этом предварительный шаг закончен.
11.2 Общий повторяющийся шаг
Общий шаг выполняется в такой последовательности.
1. Из положительных разностей dij находим наибольшую разность di0j0:
diojo = mах (vj - ui - aij > 0).
Пусть этот максимум имеет место для клетки (i0, j0). Включаем эту клетку в набор Х-отмеченных (k + l - 1) клеток. Клеток становится (k+l), а для такого их количества всегда можно построить цикл. Этот цикл будет в данной ситуации единственным.
Действительно, набор Х-отмеченных клеток является ациклическим. Добавим к нему одну клетку и предположим, что для нее можно построить два цикла. В этом случае всегда можно выделить цикл с вершинами, принадлежащими исходному набору, что противоречит условию его ацикличности. Поэтому такой цикл существует только один и задача заключается в его выделении.
2. Означиваем цикл, т.е. расставляем знаки в его вершинах. В исходной клетке (включаемой в набор) ставим плюс. Двигаемся по ходу или против хода часовой стрелки и ставим знаки попеременно минус, плюс, - пока не придем к исходной вершине. Так как количество вершин в цикле четно, направление движения безразлично. В результате получим так называемый означенный цикл, клетки которого делятся поровну на клетки положительной полуцепи и клетки отрицательной полуцепи.
3. Выбираем наименьшее значение перевозки в клетках отрицательной полуцепи (xij) - . Пусть оно равно Q:
min (xij) - = Q.
Если таких значений несколько, берем одно из них, безразлично какое.
4. Из перевозок каждой клетки отрицательной полуцепи вычитаем Q, а к перевозкам каждой клетки положительной полуцепи прибавляем Q. Эта операция называется сдвигом по циклу на величину Q.
Процесс сдвига меняет план, но план остается допустимым.
Действительно, допустимый план обеспечивает баланс в строках и столбцах; всякий план, не нарушающий этот баланс, будет допустимым. Любой цикл, по которому производится сдвиг, содержит в каждом ряду (строке, столбце) по две вершины. В одну клетку добавляем Q, а из другой вычитаем Q, и баланс не нарушается. Следовательно, план, найденный в результате сдвига, останется допустимым.
После сдвига в клетке отрицательной полуцепи с минимальной перевозкой будет стоять нуль, а в клетке (i0, j0), включенной в набор, окажется число Q. Первую клетку из плана исключаем, а вторую включаем; план остается по-прежнему ациклическим, так как единственный имевшийся цикл нарушается исключением клетки.
Полученный после сдвига план можно записать следующим образом:
5. для полученного после сдвига плана составляем новую систему потенциалов. Эти новые потенциалы можно вычислить так же, как это делалось в предварительном шаге, а можно найти исправлением уже имеющейся системы.
Для занятых клеток должны выполняться равенства
.Поэтому берем в таблице клетку, занятую в результате сдвига, и исправляем для нее потенциалы так, чтобы их разность равнялась тарифу. Лучше изменять один из них - тот, который стоит в строке или столбце с меньшим числом занятых клеток.
Затем испытываем другие занятые клетки и корректируем последовательно остальные потенциалы. Изменению подвергаются, как правило, не все числа, и такой порядок сокращает расчеты.
6. Производим исследование новой системы на потенциальность, т.е. исследование найденного плана на оптимальность. Для этого проверяем выполнение неравенств vj - ui ≤ aij для всех незанятых клеток. Если для них неравенства выполняются, то система потенциальна и план оптимален, т.е. решение закончено. Если для каких-то клеток неравенства не выполняются, вычисляем разности dij и делаем снова общий шаг и т.д., до тех пор, пока не будет получен оптимальный план. Вырождение в транспортной задаче проявляется в том, что среди (k+l-1) Х-отмеченных клеток оказывается клетка с нулевой перевозкой. Если эта клетка не попадает в цикл, на нее не обращаем внимания. Если она попадает в положительную полуцепь цикла, то на следующем шаге вместо нуля получим в этой клетке положительное число. Если же нулевая клетка оказывается в отрицательной полуцепи, то Q=0, т.е. сдвиг надо делать на число нуль. Такой нулевой сдвиг плана не меняет, но нуль переходит в другую клетку, меняется набор Х-отмеченных клеток и система потенциалов. Это дает возможность на очередном шаге осуществить уже не нулевой сдвиг и изменить план в сторону его улучшения. Контроль вычислений осуществляется таким образом. В процессе решения задачи на каждом шаге полученный план проверяется на допустимость. Для этого компоненты плана суммируются по строкам и столбцам; суммы должны равняться соответственно запасам и потребностям пунктов. Окончательный (оптимальный) план проверяется по формуле, вытекающей из доказательства основной теоремы:
,при этом контролируются и потенциалы. [5]
12. Транспортная задача с ограничениями на пропускную способность
Транспортная задача с ограниченными пропускными спосо6ностями коммуникаций решается с дополнительным ограничением:
, где dij - пропускная способность звена (i, j) в единицу времени. Математическая модель задачи такова: 
,при ограничениях
Эта задача разрешима при выполнении условий
.Для транспортной задачи с ограниченными пропускными способностями справедливы следующие условия оптимальности полученного решения:
[8]13. Транспортная задача по критерию времени
Кроме транспортной задачи по критерию стоимости существует задача транспортного типа по критерию времени. Постановка такой задачи состоит в следующем.
Дана матрица времени (tij) kl, где tij - время на перевозку груза из i-того пункта отправления в j-тый пункт назначения. Матрица перевозок грузов (xij) kl, где xij - количество перевозимого груза из i-того пункта отправления в j-тый пункт назначения. Известно также наличие груза Mi и спрос на него Nj,
. Требуется определить такой план перевозок, при котором весь груз будет доставлен потребителям в кратчайший срок.Постановка транспортной задачи по критерию времени отличается от транспортной задачи по критерию стоимости лишь целевой функцией.
Если в задаче по критерию стоимости определялись минимальные транспортные издержки, то при решении задачи по критерию времени следует определить наименьший промежуток времени, за который груз будет доставлен потребителю. Решение такой задачи очень важно в случае доставки скоропортящегося продукта.
Исходный опорный план можно получить по правилам "северо-западного угла", "минимального элемента", приближенным методом. Далее просматриваем все занятые клетки и в них выбираем максимальное время t, за которое осуществляется опорный план перевозок, т.е. Т=max (tij), где клетки (i; k) занятые. Каждому плану перевозок будет соответствовать вполне определенное значение Т, зависящее от плана, т.е. T=f (x). Следовательно, нужно найти такой план доставки груза потребителям, для которого Т будет минимальным.
Определив максимальное значение Т для исходного плана, просматриваем ту клетку, для которой t=Т=max (tij). Например, такой клеткой является (p, q). Для этой клетки строится цикл, который включает в себя занятые и свободные клетки. Таких циклов может быть несколько. Однако при построении его следует учесть условия. Занятая клетка (p, q), для которой tiq = Т будет нечетной, следующая клетка по часовой или против часовой стрелки - четная, следующая - нечетная и т.д. Цикл состоит из двух полуциклов - четного и нечетного. Для нечетных клеток цикла обязательно должна быть загрузка больше нуля, а для четных - время меньше Т. Свободные клетки, для которых время tij> Т, прочеркиваются и в расчет не принимаются.
Построив цикл для разгрузочной клетки (p, q), для которой t (p, q) = Т, определяем наименьшую загрузку в нечетных клетках цикла. Полученное количество груза вычитается из грузов нечетных клеток и добавляется к числам четных клеток цикла. При этом может оказаться, что после смещения по циклу клетка (p, q) не разгрузится, тогда снова строится цикл и производится разгрузка клетки до тех пор, пока количество груза не станет равным нулю. После разгрузки клетки, имеющей максимальный промежуток времени, получаем новый план перевозок, для которого отыскивается разгрузочная клетка и снова производится процедура построения цикла и смещения груза по циклу. Процесс продолжается до тех пор, покуда можно будет строить разгрузочные циклы. В случае невозможности построить такой цикл в полученных занятых клетках плана выбираем максимальное время, которое и будет искомым по реализации оптимального плана. [9]