Вырожденнымпланом транспортной задачи называется такой допустимый план, в котором количество базисных клеток меньше (m+n–1), где m и n количество пунктов отправления и назначения соответственно.
Начальное допустимое решение задачи, приведенной в табл. 28, получено методом минимального элемента и содержит 5 базисных клеток вместо (4 + 5 - 1) = 8.
Таблица 28
Вырожденный план
Пункты назначения Пункты Отправления | B1 | B2 | B3 | B4 | B5 | Запасы груза |
A1 | 8 | 10 | ||||
А2 | ||||||
A3 | 4 | |||||
A4 | 6 | |||||
Потребности в грузе |
Отсутствие необходимого количества базисных клеток приводит к тому, что не из всякой свободной клетки можно построить цикл, опирающийся на базисные клетки. Для того, чтобы существовал цикл, необходимо наличие строк и столбцов, содержащих по две базисные клетки, в которых ломаной линии разрешено делать поворот. Недостающие базисные клетки определяются следующим образом: в том месте транспортной таблицы, где необходимо повернуть ломаную линию цикла, нужно выбрать подходящую свободную клетку, поместить в нее нулевую перевозку и считать эту клетку базисной. Если, в таким образом построенном цикле, базисная клетка с нулевым значением перевозки совпадает с отрицательной вершиной цикла, то по циклу переносится ноль единиц груза.
|
|
Процесс расстановки недостающих базисных клеток с нулевой перевозкой состоит в том, что эти клетки следует разместить так, чтобы все базисные клетки можно было соединить ломаной линией, углы которой кратны прямому.
Рассмотрим эту ситуацию на примере задачи в табл. 29. Для того чтобы соединить ломаной линией базисные клетки A1В 2, A2В 1, A3В 3, A4В 2, A4В 4, A4В 5 можно поставить нулевые перевозки, например, в клетки A1В 1 и A3В 1.
Таблица 29
Снятие вырождения
Пункты назначения Пункты Отправления | B1 | B2 | B3 | B4 | B5 | Запасы груза |
A1 | 8 | 10 | ||||
А2 | ||||||
A3 | 4 | |||||
A4 | 6 | |||||
Потребности в грузе |
Алгоритм расстановки базисных клеток с нулевой перевозкой может быть легко сформулирован при помощи метода коррекции запасов и заявок. Если в полученном допустимом решении какая-либо перевозка, например xRS, одновременно и полностью выполняет ограничения и по пункту отправления AR, и по пункту назначения BS, то либо запасы аR либо заявки bS этих пунктов должны подвергнуться такой коррекции, чтобы появились недостающие базисные перевозки.
Рассмотрим метод коррекции для допустимого решения, построенного при помощи метода минимального элемента и приведенного в табл. 30. Выполнение перевозок x 22=100, x 33= 75, x 15 = 50 позволяет одновременно удовлетворить ограничениям по а2 и b2, по а3 и b3, по а1 и b5 соответственно.
|
|
Клетку A2В 2, нельзя соединить ломаной линией с другими базисными клетками, так как ни строка A2, ни столбец В 2 не содержат других базисных клеток. Увеличим, например, заявку пункта В 2 на малую величину ε (b2 = 100 + ε) и внесем это изменение в табл. 30. Недостающие ε единиц груза присвоим перевозке x 42. Перевозка x 42 имеет наименьший тариф в строке A4. Выбор клетки A4В 2, позволит связать ломаной линией столбец В 2 и строку A4. Теперь для выполнения ограничения по а4 необходимо, например, а4 увеличить на ε (а4 = 100 + ε) или перевозку x 44 и заявку b4 уменьшить на ε (x 44 = 60 - ε, b4 = 60 - ε). В табл. 30 записан последний вариант.
Далее рассмотрим перевозку x 33. Клетка A3В 3, — единственная базисная клетка и в строке A3, и в столбце В 3. Ее нельзя соединить ломаной линией с другими базисными клетками. Увеличим, например, запасы в пункте A3 на ε единиц. «Лишние» ε единиц груза приписываются перевозке x 32. Эта перевозка характеризуется минимальным тарифом в строке A3, и новая базисная клетка позволит соединить клетку A3В 3, с базисными клетками в столбце В 2 и далее в строке A4. Для того, чтобы ограничения выполнялись, необходимо либо скорректировать заявку b2 увеличив ее на 2 ε единиц (b2 = 100 + 2 ε), либо уменьшить на ε единиц перевозку x 22 и запасы пункта отправления а2 (x 22 = 100 - ε, а2 = 100 - ε). В табл. 30 реализовано последнее.
Повторяя аналогичные рассуждения, для перевозки x 15 увеличим, например, запасы а1 на ε (а1 = 50 + ε) и занесем в клетку A1В 1, ε единиц (x 11 = ε). Для выполнения ограничения увеличим заявку b1 на ε единиц (b1 = 40 + ε).
Таблица 30
Вырожденная задача, метод коррекции
Пункты назначения Пункты Отправления | B1 | B2 | B3 | B4 | B5 | Запасы груза |
A1 | ε | 12 | 18 | 50+ ε | ||
А2 | 100- ε | 100- ε | ||||
A3 | 12 ε | 75+ ε | ||||
A4 | 11 ε | 60- ε | ||||
Потребности в грузе | 40+ ε | 100+ ε | 60- ε | 225+ ε |
В результате таких рассуждений в транспортной таблице заполнены недостающие три базисные клетки, все ограничения выполняются, задача сохраняет свою сбалансированность и становится невырожденной. Теперь положим ε = 0 и в дальнейших вычислениях учитываем, что в полученном допустимом решении три базисные клетки содержат нулевые перевозки.
Лекция 6.
Транспортная задача по критерию времени
Наиболее частым критерием оптимальности перевозок оказывается из суммарная стоимость z. Однако, возникают ситуации, когда в качестве критерия оптимальности необходимо использовать время Т, в течение которого все перевозки будут закончены. Так, например, при перевозке скоропортящихся продуктов зачастую важна не стоимость перевозок, а их продолжительность. Такая транспортная задача называется транспортной задачей по критерию времени.
В транспортной задаче по критерию времени оптимальным планом перевозок Х(xij) называется та продолжительность перевозок, которая минимальна .
Сформируем транспортную задачу по критерию времени. Допустим, заданы M пунктов отправления A1, A2, …, AM, в которых сосредоточены запасы в количествах a1, a2, …, aM, и N пунктов назначения B1, B2, …, BN подавших заявки на груз в количествах b1, b2, …, bN, и время транспортировок tij из пункта Ai в пункт В j (). Необходимо за наименьшее время Т () организовать перевозки груза из Ai в В j так, чтобы из каждого пункта отправления Ai весь запас груза аi был вывезен:
и в каждый пункт назначения В j весь груз в соответствии с потребностями bj был ввезен:
и перевозки не должны быть обратными xij>0
Выразим продолжительность перевозок T через время tij конкретных перевозок xij. План перевозок считается выполненным в тот момент, когда заканчивается самая длительная из всех перевозок, т. е. продолжительность плана перевозок Т определяется максимальной длительностью tij ненулевых перевозок. Следовательно, необходимо найти план перевозок Х(xij) удовлетворяющий условию
|
|
Транспортная задача по критерию времени не является задачей линейного программирования, так как целевая функция Т не является линейной функцией переменных xij.
Без ограничения общности можно считать, что рассматриваемая транспортная задача сбалансирована: . Если это не так, то транспортную задачу всегда можно сбалансировать, пропорционально уменьшая избыточные запасы аi, (заявки bj) или вводя фиктивный пункт отправления AФ, (назначения В Ф) с запасами (заявками ) для недостающих заявок (запасов) и считая, что эти дополнительные перевозки происходят в течение очень большого промежутка времени t Ф.
Решение транспортной задачи по критерию времени может быть получено методом запрещенных клеток. Этот метод состоит из двух этапов:
• на первом, находится начальный допустимый план;
• на втором, найденный план последовательно ускоряется.
Пример. В таблице (табл. 30) в правый верхний угол каждой клетки вписано время соответствующей перевозки tij.
Для определения начального допустимого плана перевозок можно использовать, например, метод северо-западного угла или метод наименьшего элемента. Допустимое решение x 52, x 31, x 42, x 43, x 13, x 21, x 65, x 24 (перевозки xij перечислены в порядке их определения) получено методом наименьшего элемента и указано в табл. 31. Время найденного плана перевозок T равно t 24 = 8.
Таблица 31
Метод запрещенных клеток
Для уменьшения Т необходимо перевозку x 24 поместить в клетки, которым соответствуют перевозки с tij < t24. Более быстрый план Х(xij) не может содержать перевозки с tij > t24, поэтому из дальнейшего рассмотрения исключим все такие клетки, перечеркнув их. При изменении допустимого плана перевозок Х(xij) с сохранением имеющихся ограничений также используется приятие цикла транспортной таблицы, введенное выше. Однако в отличие от распределительного метода или метода потенциалов положительные вершины цикла могут опираться на клетки с нулевыми перевозками. Для переноса x 24 в другие клетки пометим клетку A2В 4, знаком «-» и построим из нее цикл. Вершины этого цикла — клетки A5В 4, A5В 2, A2В 2 помечены соответственно знаками плюс и минус. Минимальное значение, на которое можно произвести сдвиг по циклу x 24=75.
|
|
Таблица 32
Второй шаг метода запрещенных клеток
Новый, более быстрый план перевозки указан в табл. 32. Его время Т равно t64 = 7, поэтому из дальнейшего рассмотрения из табл. 32 вычеркнем все клетки tij = 8. Построим цикл из клетки A6В 4. Вершинами цикла являются клетки A6В 4, A6В 2, A5В 2 и A5В 4. В цикле делаем сдвиг на 25 единиц. Результат записан в таблицу 33. Время найденного плана перевозок T = 6. Вычеркнем из дальнейшего рассмотрения клетки таблицы с tij= 7. Анализ табл. 33 позволяет сделать вывод о том, что создать более быстрый план с T < 6 нельзя.
Таблица 33
Результат оптимизации
Пункты назначения Пункты отправления | B1 | В2 | В3 | В4 | В5 | Запасы |
А1 | ||||||
А2 | ||||||
А3 | ||||||
А4 | ||||||
А5 | ||||||
А6 | ||||||
Потребности |