Вырожденный план транспортной задачи

Пункты назначения Пункты Отправления

Запасы груза

Потребности в грузе

Вырожденнымпланом транспортной задачи называется такой допустимый план, в котором количество базисных клеток меньше (m+n–1), где m и n количество пунктов отправления и назначения соответственно.

Начальное допустимое решение задачи, приведенной в табл. 28, получено методом минимального элемента и содержит 5 базисных клеток вместо (4 + 5 - 1) = 8.

Таблица 28

Вырожденный план

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

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

Рассмотрим эту ситуацию на примере задачи в табл. 29. Для того чтобы соединить ломаной линией базисные клетки A₁В₂, A₂В₁, A₃В₃, A₄В₂, A₄В₄, A₄В₅ можно поставить нулевые перевозки, например, в клетки A₁В₁ и A₃В₁.

Таблица 29

Снятие вырождения

Алгоритм расстановки базисных клеток с нулевой перевозкой может быть легко сформулирован при помощи метода коррекции запасов и заявок. Если в полученном допустимом решении какая-либо перевозка, например x_RS, одновременно и полностью выполняет ограничения и по пункту отправления A_R, и по пункту назначения B_S, то либо запасы а_R либо заявки b_S этих пунктов должны подвергнуться такой коррекции, чтобы появились недостающие базисные перевозки.

Рассмотрим метод коррекции для допустимого решения, построенного при помощи метода минимального элемента и приведенного в табл. 30. Выполнение перевозок x₂₂=100, x₃₃= 75, x₁₅= 50 позволяет одновременно удовлетворить ограничениям по а₂ и b₂, по а₃ и b₃, по а₁ и b₅ соответственно.

Клетку A₂В₂, нельзя соединить ломаной линией с другими базисными клетками, так как ни строка A₂, ни столбец В₂ не содержат других базисных клеток. Увеличим, например, заявку пункта В₂ на малую величину ε (b₂ = 100 + ε) и внесем это изменение в табл. 30. Недостающие ε единиц груза присвоим перевозке x₄₂. Перевозка x₄₂ имеет наименьший тариф в строке A₄. Выбор клетки A₄В₂, позволит связать ломаной линией столбец В₂ и строку A₄. Теперь для выполнения ограничения по а₄ необходимо, например, а₄ увеличить на ε (а₄= 100 + ε) или перевозку x₄₄ и заявку b₄ уменьшить на ε (x₄₄ = 60 - ε, b₄ = 60 - ε). В табл. 30 записан последний вариант.

Далее рассмотрим перевозку x₃₃. Клетка A₃В₃, — единственная базисная клетка и в строке A₃, и в столбце В₃. Ее нельзя соединить ломаной линией с другими базисными клетками. Увеличим, например, запасы в пункте A₃ на ε единиц. «Лишние» ε единиц груза приписываются перевозке x₃₂. Эта перевозка характеризуется минимальным тарифом в строке A₃, и новая базисная клетка позволит соединить клетку A₃В₃, с базисными клетками в столбце В₂ и далее в строке A₄. Для того, чтобы ограничения выполнялись, необходимо либо скорректировать заявку b₂ увеличив ее на 2ε единиц (b₂ = 100 + 2ε), либо уменьшить на ε единиц перевозку x₂₂ и запасы пункта отправления а₂ (x₂₂ = 100 - ε, а₂ = 100 - ε). В табл. 30 реализовано последнее.

Повторяя аналогичные рассуждения, для перевозки x₁₅ увеличим, например, запасы а₁ на ε (а₁ = 50 + ε) и занесем в клетку A₁В₁, ε единиц (x₁₁ = ε). Для выполнения ограничения увеличим заявку b₁ на ε единиц (b₁ = 40 + ε).

Таблица 30

Вырожденная задача, метод коррекции

Пункты назначения Пункты Отправления	B₁	B₂	B₃	B₄	B₅	Запасы груза
A₁	ε			12	18	50+ ε
А₂		100- ε				100- ε
A₃		12 ε				75+ ε
A₄		11 ε		60- ε
Потребности в грузе	40+ ε	100+ ε		60- ε		225+ ε

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

Лекция 6.

Транспортная задача по критерию времени

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

В транспортной задаче по критерию времени оптимальным планом перевозок Х(x_ij) называется та продолжительность перевозок, которая минимальна .

Сформируем транспортную задачу по критерию времени. Допустим, заданы M пунктов отправления A₁, A₂, …, A_M, в которых сосредоточены запасы в количествах a₁, a₂, …, a_M, и N пунктов назначения B₁, B₂, …, B_N подавших заявки на груз в количествах b₁, b₂, …, b_N, и время транспортировок t_ij из пункта A_i в пункт В_j (). Необходимо за наименьшее время Т () организовать перевозки груза из A_i в В_j так, чтобы из каждого пункта отправления A_i весь запас груза а_i был вывезен:

и в каждый пункт назначения В_j весь груз в соответствии с потребностями b_j был ввезен:

и перевозки не должны быть обратными x_ij>0

Выразим продолжительность перевозок T через время t_ij конкретных перевозок x_ij. План перевозок считается выполненным в тот момент, когда заканчивается самая длительная из всех перевозок, т. е. продолжительность плана перевозок Т определяется максимальной длительностью t_ij ненулевых перевозок. Следовательно, необходимо найти план перевозок Х(x_ij) удовлетворяющий условию

Транспортная задача по критерию времени не является задачей линейного программирования, так как целевая функция Т не является линейной функцией переменных x_ij.

Без ограничения общности можно считать, что рассматриваемая транспортная задача сбалансирована: . Если это не так, то транспортную задачу всегда можно сбалансировать, пропорционально уменьшая избыточные запасы а_i, (заявки b_j) или вводя фиктивный пункт отправления A_Ф, (назначения В_Ф) с запасами (заявками ) для недостающих заявок (запасов) и считая, что эти дополнительные перевозки происходят в течение очень большого промежутка времени t_Ф.

Решение транспортной задачи по критерию времени может быть получено методом запрещенных клеток. Этот метод состоит из двух этапов:

• на первом, находится начальный допустимый план;

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

Пример. В таблице (табл. 30) в правый верхний угол каждой клетки вписано время соответствующей перевозки t_ij.

Для определения начального допустимого плана перевозок можно использовать, например, метод северо-западного угла или метод наименьшего элемента. Допустимое решение x₅₂, x₃₁, x₄₂, x₄₃, x₁₃, x₂₁, x₆₅, x₂₄ (перевозки x_ij перечислены в порядке их определения) получено методом наименьшего элемента и указано в табл. 31. Время найденного плана перевозок T равно t₂₄ = 8.

Таблица 31

Метод запрещенных клеток

Для уменьшения Т необходимо перевозку x₂₄ поместить в клетки, которым соответствуют перевозки с t_ij<t₂₄. Более быстрый план Х(x_ij) не может содержать перевозки с t_ij > t₂₄, поэтому из дальнейшего рассмотрения исключим все такие клетки, перечеркнув их. При изменении допустимого плана перевозок Х(x_ij) с сохранением имеющихся ограничений также используется приятие цикла транспортной таблицы, введенное выше. Однако в отличие от распределительного метода или метода потенциалов положительные вершины цикла могут опираться на клетки с нулевыми перевозками. Для переноса x₂₄ в другие клетки пометим клетку A₂В₄, знаком « - » и построим из нее цикл. Вершины этого цикла — клетки A₅В₄, A₅В₂, A₂В₂ помечены соответственно знаками плюс и минус. Минимальное значение, на которое можно произвести сдвиг по циклу x₂₄=75.

Таблица 32

Второй шаг метода запрещенных клеток

Новый, более быстрый план перевозки указан в табл. 32. Его время Т равно t₆₄= 7, поэтому из дальнейшего рассмотрения из табл. 32 вычеркнем все клетки t_ij = 8. Построим цикл из клетки A₆В₄. Вершинами цикла являются клетки A₆В₄, A₆В₂, A₅В₂ и A₅В₄. В цикле делаем сдвиг на 25 единиц. Результат записан в таблицу 33. Время найденного плана перевозок T = 6. Вычеркнем из дальнейшего рассмотрения клетки таблицы с t_ij=7. Анализ табл. 33 позволяет сделать вывод о том, что создать более быстрый план с T < 6 нельзя.

Таблица 33

Результат оптимизации

Пункты назначения Пункты отправления	B₁	В₂	В₃	В₄	В₅	Запасы
А₁
А₂
А₃
А₄
А₅
А₆
Потребности