Программирования

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

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

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

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

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

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

Транспортная задача (или задача прикрепления поставщиков к потребителям) явилась одним из первых примеров оптимизации на линейных сетях. Уже в течение довольно длительного периода эта задача стала типовой для промышленных фирм, имеющих несколько предприятий, скла­дов, рынков сбыта или оптовых баз. Модель применяется главным образом при решении плановых задач. В этом случае стратегические решения сводятся к выбору транспортных маршрутов, по которым продукция различных предприятий доставляется на несколько складов или в различные конечные пункты назначения.

Математическая постановка транспортной задачи, как мы уже говорили ранее, имеет следующий вид (в данной математической модели обозначим значение величины потока перевозкок из истока i в сток j):

Минимизировать .

при ограничениях:

{1..m}

{1..n}.

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

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

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

 

Сток Исток			…		Запасы:
			…
			…
…	…	…	…	…	…
			…
Заявки:			…

 

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

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

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

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

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

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

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

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

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

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

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

Здесь сразу же возникает вопрос, насколько практически реализуемым и точным будет полученное числовое решение задачи. Чтобы разумно отве­тить на этот вопрос, нужно иметь в виду два обстоятельства. Прежде всего, решение, в сущности, представляет собой некоторый план распределения продуктов в течение заданного интервала времени. Иными словами, модель обеспечивает прикрепление предприятий к пунктам назначения или поставщиков к потребителям. Числовые значения величин перевозок по самой своей природе являются приближенными, поскольку в большинстве реальных случаев значения запросов в пунктах потребления представ­ляют собой лишь прогнозы потребностей на планируемый период. В связи с этим значения , полученные в процессе решения, не являются фактическими значениями количества перевозимых продуктов, а слу­жат только оценками величины будущих поставок. Рассуждая дальше, относи­тельные достоинства полученного плана необходимо сравнить с любы­ми практически реализуемыми вариантами, которые может исполь­зовать фирма, в том числе, разумеется, с принятым планом перево­зок. Учитывая эти соображения, многие фирмы могут существенно повы­сить свои доходы, приняв план перевозок, основанный на решении классической транспортной задачи.

Вернемся теперь непосредственно к рассмотрению методов решения транспортной задачи. Пусть задана некоторая классическая транспортная задача.

Предположим, что имеется n пунктов потребления (например, промышленных предприятий или типографий) П_j, j {1..n}, требующих снабжения некоторым определенным видом сырья. Потребности в сырье каждого предприятия П_j равны соответственно b_j условных единиц j {1..n}. Кроме того, имеется m складов С_i, i {1..m}, на которых хранится требуемое предприятиям сырье. На каждом складе С_i имеется в наличии запас товара в количестве a_i соответственно, i {1..m}. Склады удалены от предприятий на некоторые расстояния и связаны с ними некоторыми путями сообщений с различными тарифами на перевозку грузов (в нашем случае сырья). Будем считать, что каждый склад связан с каждым пунктом потребления некоторым единственным маршрутом с неограниченной пропускной способностью. Единица сырья, получаемая предприятием П_j со склада C_i с учетом известных тарифов на перевозки, обходится в c_ij рублей. Для простоты предположим, что все заявки выполнимы и обеспечивают отсутствие излишек на складах, т.е. сумма всех заявок в точности равна сумме всех имеющихся запасов:

.

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

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

 

Сток Исток			…		Запасы:
			…
			…
…	…	…	…	…	…
			…
Заявки:			…

 

Очевидно, что не все m + n уравнений системы ограничений транспортной задачи являются независимыми. Действительно. складывая все ограничения по заявкам и все ограничения по запасам, в силу равенства заявок и запасов, получаем доказательство того, что ранг системы ограничений r = m + n – 1. Следовательно, можно разрешить эти уравнения относительно r базисных переменных, выразив их через остальные k свободные.

k = m×n – r = m×n – m – (n – 1) = m×(n – 1) – (n – 1) Þ

k = (m – 1)×(n – 1).

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

Значения количества единиц груза, направляемых из пункта Сi в пункт Пj будем называть перевозками. Любую совокупность значений () будем называть планом перевозок, или просто планом. Тогда план будем называть допустимым, если он удовлетворяет балансовым условиям: все заявки удовлетворены и, все запасы исчерпаны.

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

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

 

Сток Исток			…		Запасы:
						…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

 

Заявки:

…

 

Ячейки таблицы с отличными от нуля перевозками условимся называть базисными, а остальные (пустые – в дальнейшем в транспортную таблицу мы будем заносить только отличные от нуля значения) свободными.

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

Нахождение опорного плана методом «северо-западного угла»

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

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

Очевидно, что в случае неравенства (или равенства) запаса на складе 1 запросу потребителя 1 возможны два варианта:

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

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

3. Склад 1 полностью удовлетворил потребности потребителя 1, при этом запас товаров на складе был полностью исчерпан. Тогда на следующей итерации алгоритма мы будем рассматривать соседнюю с юго-востока ячейку, то есть ячейку (2,2) транспортной таблицы.

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

Очевидно, что в силу равенства суммарных заявок (запросов) суммарным запасам на последней итерации алгоритма – ячейка (i,j) – в общем случае окажется, что i-ый склад оставшимся своим запасом полностью удовлетворит оставшийся неудовлетворенным на предыдущих итерациях запрос j-того потребителя.

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

 

Сток Исток						Запасы:

 

Заявки:

 

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

Удовлетворим пункт В₁ за счет запаса А₁, следовательно
х₁₁= 18. После этого в пункте А₁ осталось 30 единиц груза. Удовлетворим запрос пункта В₂ за счет остатка А₁, следовательно х₁₂ = 27. оставшиеся 3 единицы груза направим в пункт В₃ Þ х₁₃ = 3. В составе заявки пункта В₃ осталось неудовлетворенным 39 единиц груза. Из них 30 покроем за счет пункта А₂, чем его запас будет исчерпан, и еще 9 единиц возьмем из пункта А₃, следовательно х₂₃ = 30 и х₃₃ = 9 и т.д. Полученное решение будет не только допустимым, но и опорным.

В результате этих действий получим следующее опорное решение:

 

Сток Исток						Запасы:

 

Заявки:

 

Остановимся теперь на одной особенности плана перевозок. Речь идет о так называемом «вырожденном» плане, в котором некоторые из базисных перевозок оказываются равными 0.

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

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

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

 

Сток Исток						Запасы:

e

20-e

10+e

25-e

e

20+e

 

Заявки:

 

Особенностью этого опорного плана является то, что в нем только 6, а не 8 отличных от нуля перевозок (r = m + n – 1 = 4 + 5 – 1 = 8).

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

Улучшение плана перевозок. Цикл пересчета

Метод «северо-западного» угла позволяет отыскать допустимый план перевозок, который мы назвали опорным планом. Очевидно, что в общем случае опорный план, являясь допустимым, не является оптимальным. Для нахождения оптимального плана перевозок необходимо последовательно, пока это возможно, улучшать опорный план. В этом параграфе мы рассмотрим термины и определения, используемые при улучшении опорного плана, которые нам в дальнейшем потребуются при рассмотрении алгоритмов решения транспортной задачи.

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

 

Сток Исток						Запасы:

 

Заявки:

 

Стоимость этого плана равна:

L = 18×10 + 27×8 + 3×5 + 30×8 + 9×10 + 12×8 + 6×7 + 20×8 = 1039.

Попробуем улучшить этот план, перенеся, как показано в приведенной выше таблице, 18 единиц из клетки (1,1) в клетку (2,1) и, чтобы не нарушать баланса, перенесем те же 18 единиц из клетки (2,3) в клетку (1,3). В результате переноса мы получили новый план перевозок, который тоже будет допустимым, так как переброску груза с одного маршрута на другой мы осуществляли циклически, заботясь о сохранении баланса заявок и запасов.

 

Сток Исток						Запасы:
Заявки:

 

Таким образом, мы получили новый допустимый план, стоимость которого равна:

L = 18×6 + 27×8 + 21×5 + … = 913.

Очевидно, что полученный план перевозок по стоимости предпочтительнее первоначального опорного плана.

Из приведенной таблицы видно, что за счет циклической перестановки грузоперевозок объемом 18 единиц по маршрутам (1,1)^-, (2,1)⁺, (2,3)^-, (1,3)⁺ удалось понизить стоимость плана перевозок на 126 условных единиц стоимости.

Здесь следует обратить внимание на следующее равенство:

1039 – 913 = –126 = 18×(-10 + 6 – 8 + 5) = 18×(-7).

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

Итак, циклом в транспортной таблице назовем несколько клеток, соединенных замкнутой ломаной линией, которая в каждой клетке совершает поворот на угол, равный 90^о. Условимся помечать символами (+) те вершины ломаной линии, образующей цикл, в которых объемы перевозок увеличивается, а символом (-) те вершины цикла, в которых они уменьшаются.

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

 

Сток Исток						Запасы:
Заявки:

 

Цикл с отмеченными вершинами будем называть «означенным». Перенести какое-то количество единиц груза по означенному
циклу – это означает увеличить объемы перевозок в положительных вершинах (вершинах, помеченных символом «+») на это количество единиц и одновременно с этим уменьшить перевозки на то же количество в отрицательных вершинах (вершинах, помеченных символом «–»).

Очевидно что, при переносе любого числа единиц по циклу равновесие между запасами и заявками не меняется.

Назовем ценой (стоимостью) цикла (g) – алгебраическую сумму стоимостей, стоящих в вершинах цикла, с учетом знака этих вершин, например:

g₁ = с₂₁ – с₂₃ + с₄₃ – с₄₁,

g₂ = с₃₄ – с₃₅ + с₅₅ – с₅₄ + с₁₄ – с₁₆.