Транспортная задача. Описание и примеры применения метода потенциалов

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

Рассмотрим транспортную задачу, которую можно сформулировать следующим образом.

В m пунктах отправления А₁, А₂,..., А_m, которые в дальнейшем будем называть поставщиками, имеются запасы некоторого продукта, равное a_i (i = 1, 2,..., m) единиц. Данный продукт потребляется в n пунктах В₁, B₂,..., В_n, которые будем называть потребителями. Объем потребления в j-м пункте обозначим b_j (j = 1, 2,..., n). Известны расходы на перевозку единицы продукта из пункта A_i в пункт B_j, которые равны с_ij и приведены в матрице транспортных расходов С = (с_ij).

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

Обозначим количество продукта, перевозимого из пункта A_i в пункт B_j, через Х_ij. Целевая функция задачи будет иметь вид (1.7.1)

а ограничения выглядят следующим образом: (1.7.2) (1.7.3)x_ij ≥ 0.

Условия (1.7.2) означают полное удовлетворение спроса во всех пунктах потребления; условия (1.7.3) определяют полный вывоз продукции от всех поставщиков.

Мы будем рассматривать так называемую закрытую транспортную задачу, в которой выполняется условие баланса (1.7.4)

Если баланс (1.7.4) не выполняется, задачу корректируют путем ввода или фиктивного потребителя, или фиктивного поставщика, который компенсирует диссбаланс.

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

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

v_j = u_i + c_ij. (1.7.5)

Первым этапом алгоритма является составление начального распределения (начального плана перевозок).

Вторым этапом служат построение системы потенциалов на основе равенства (1.7.5) и проверка начального плана на оптимальность.

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

При решении транспортной задачи методом потенциалов используют таблицу вида 1.7.1.

Таблица 1.7.1

1. Начальный базисный план перевозок.

При условии баланса (1.7.4) ранг системы линейных уравнений (1.7.2), (1.7.3) равен m + n - 1; таким образом из общего числа mn неизвестных базис (задачи линейного программирования) должен иметь размерность m + n - 1. Поэтому любой допустимый базисный план перевозок, должен иметь ровно m + n - 1 заполненную клетку, которые будем называть базисными в отличие от остальных свободных клеток.

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

Такой подход будет гарантировать, что базисных клеток будет ровно m+n–1. Если при заполнении некоторой (не последней) клетки одновременно удовлетворяются мощности и поставщика, и потребителя, то вычеркивается, например, только строка, а в соответствующем столбце заполняется незанятая клетка так называемой «нулевой поставкой», после чего вычеркивается и столбец. Для идентификации клетки обычно в скобках указываются номера ее строки и столбца.

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

Пример составления начального распределения данным методом показан в табл. 1.7.2: заполняется клетка (1;1) и вычеркивается первый столбец, заполняется клетка (1;2) и вычеркивается первая строка; заполняется клетка (2; 2) и вычеркивается второй столбец; заполняется клетка (2;3) и вычеркивается вторая строка; заполняется клетка (3;3) и вычеркивается третий столбец; наконец, заполняется клетка (3:4) и вычеркиваются последние строка и столбец. Число занятых клеток равно m + n – 1 = 3 + 4 – 1 = 6. Суммарные затраты на реализацию данного плана перевозок составят

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

2. Проверка оптимальности полученного плана перевозок. Вычислим потенциалы u_i для каждой строки матрицы перевозок, i = 1, …,m, и показатели v_j для каждого столбца, j = 1,…,n.

Потенциалы подбираются таким образом, чтобы для заполненной клетки (i;j) выполнялось равенство (1.7.5). Совокупность уравнений вида (1.7.5), составленных для всех заполненных клеток (всех базисных неизвестных), образует систему m + n - 1 линейных уравнений с m+n неизвестными u_i и v_j. Эта система всегда совместна, причем значение одного из неизвестных можно задавать произвольно (например, u₁ = 0), тогда значения остальных неизвестных находятся из системы однозначно.

Рассмотрим процесс нахождения потенциалов для базисного начального распределения по методу северо-западного угла, представленного в табл. 1.7.2. Задав u₁ = 0 и используя формулу (1.7.5) для заполненных клеток (1;1) и (1;2), находим v₁= 4 и v₂ = 5. Зная v₂, по заполненной клетке (2;2) находим u₂ = 2, а зная u₂, по заполненной клетке (2;3) находим v₃= 8. Зная v₃, по заполненной клетке (3;3) находим u₃ = 1, а затем по заполненной клетке (3;4) находим v₄ = 5. Результаты представлены в табл. 1.7.4, где потенциалы поставщиков приведены в последнем столбце, а потенциалы потребителей – в последней строке.

Смысл знаков "+" и "-", поставленных в табл. 1.7.4, пояснен далее при описании этапа 3 метода потенциалов.

Аналогичные результаты для начального распределения по методу наименьших стоимостей, приведенного в табл. 1.7.3, представлены в табл. 1.7.5.

Чтобы оценить оптимальность распределения, для всех клеток (i;j) матрицы перевозок определяются их оценки, которые обозначим через d_ij, по формуле:

d_ij =(u_i+c_ij)-v_j. (1.7.6)

Используя ранее принятую интерпретацию, выражение (u_i+c_ij) можно трактовать как сумму цены продукта у поставщика и стоимости перевозки; эта сумма путем вычитания сравнивается с ценой продукта у соответствующего потребителя v_j. Очевидно, оценки заполненных клеток равны нулю (цена потребителя покрывает цену поставщика и стоимость перевозок). Таким образом, об оптимальности распределения можно судить по величинам оценок свободных клеток. Если оценка некоторой свободной клетки отрицательна, это можно интерпретировать так: цена, предлагаемая соответствующим потребителем, больше суммы цены поставщика и стоимости перевозки, т.е. если бы эта клетка была занята, то можно было бы получить дополнительный экономический эффект. Следовательно, условием оптимальности распределения служит условие неотрицательности оценок свободных клеток матрицы перевозок.

3. Улучшение неоптимального плана перевозок. Чтобы улучшить неоптимальный план перевозок, выбирается клетка матрицы перевозок с отрицательной оценкой; если таких клеток несколько, то обычно (но необязательно) выбирается клетка с наибольшей по абсолютной величине отрицательной оценкой. Например, для распределения, представленного в табл. 1.7.4, такой клеткой может служить клетка (1;3) (см. матрицу оценок (1.7.7)).

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

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

Поиск по сайту: