Транспортная задача

Этот способ заключается  в следующем.

1. Располагаем все клетки  таблицы в очередь по мере  возрастания тарифов, начиная  с минимального.

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

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

Полученный план будет ациклическим и будет состоять не более чем  из k+l-1 компонент. Этот план и принимаем за исходный. Он будет лучше плана, построенного по способу северо-западного угла, и для нахождения оптимума потребуется меньше вычислений. [5]

7. Переход от  одного опорного решения к  другому

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

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

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

Для свободной клетки с строится цикл (цепь, многоугольник), все вершины которого, кроме одной, находятся в занятых клетках; углы прямые, число вершин четное. Около свободной клетки цикла ставится знак (+), затем поочередно проставляют знаки (-) и (+). У вершин со знаком (-) выбирают минимальный груз, его прибавляют к грузам, стоящим у вершин со знаком (+), и отнимают от грузов у вершин со знаком (-). В результате перераспределения груза получим новое опорное решение. Это решение проверяем на оптимальность и т.д. до тех пор, пока не получим оптимальное решение. [7]

8. Распределительный  метод

Распределительный метод  решения транспортной задачи отличается от метода потенциалов некоторым  изменением вычислительного процесса и иным (по форме) критерием оптимальности.

Алгоритм распределительного метода заключается в следующем.

1. Отыскиваем первоначальный  ациклический план, содержащий (k+l-1) компонент (при недостатке компонент дописываем нули).

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

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

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

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

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

Для ручного счета более  удобен метод потенциалов. Однако на распределительном методе основаны некоторые другие способы решения  задач, что и вызывает необходимость  его изучения. [5]

9. Метод потенциалов

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

Основная часть макета выделена двойными линиями. Она содержит kЧl клеток. Каждая клетка в этой части обозначается символом (i, j). Например, клетка, стоящая во второй строке и первом столбце, будет обозначена (2, 1). Макет содержит в себе матрицу тарифов. Назначение строки v_j и столбца u_i будет выяснено в дальнейшем.

Прежде чем приступить к изложению метода, рассмотрим некоторые  предварительные понятия.

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

Пример цепи приведен в  табл.2.

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

Если последняя клетка цепи расположена в одном ряду с первой, то такая замкнутая цепь называется циклом. Некоторые разновидности  циклов показаны в табл.3.

Теорема. Пусть в макете (или матрице) из k строк и l столбцов произвольно отмечено k+l клеток, причем k+l Ј kl. В этом случае всегда можно построить цикл, вершины которого лежат в отмеченных клетках (может быть не во всех).

Замечание. Числа k и l целые, и для них не всегда будет выполнено неравенство k+l Ј kl. Если одно из этих чисел - единица, это неравенство не выполняется. Например, при k=3, l=1 имеем 3 + 1 > 3·1. Однако при k=2 и l=2 будет 2+2 = 2·2, а при k и l, одновременно больших двух, неравенство всегда выполняется.

Условие k+l Ј kl исключает случаи матриц с одной строкой или одним столбцом, в которых вообще цикла построить нельзя.

Доказательство. Рассмотрим минимальный возможный случай: k=2, l=2 (табл.4).

В макете надо выбрать k+l = 4, т.е. все 4 клетки. Для этого случая теорема справедлива: выбранные клетки образуют цикл.

Возьмем теперь любые k>2, l>2. Доказательство будем вести методом математической индукции.

Допустим, теорема справедлива  для макета, у которого сумма строк  и столбцов на единицу меньше взятых нами (k+l). Докажем, что при этом предположении теорема будет справедлива для принятых (k+l).

Первый случай. Среди  отмеченных клеток имеется одна клетка, единственная в ряду (строке или  столбце) (табл.5).

Откажемся от этой клетки, исключим эту строку из рассмотрения. Тогда придем к таблице, у которой  строк на единицу меньше, а число  столбцов сохранилось. Число строк  в сумме с числом столбцов будет  меньше (k+l) на одну единицу, но и число отмеченных клеток уменьшится на одну. Для этого случая можно построить цикл по принятому допущению. Этот цикл возьмем и для нашей таблицы, так как в соответствии с оговоркой вершины цикла могут быть и не вo всex отмеченных клетках.

Второй случай. Нет таких  ситуаций, когда клетка одна. В каждой строке (столбце) больше чем одна клетка (или нет ни одной) (табл.6).

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

Выше было показано, что  теорема справедлива для k=2, l=2, т.е. для k+l=4. По доказанному она справедлива для случаев: k+l=5, т.е. k+l>4; k+l=6, т.е. k+l>5; k+l>6 и т.д., т.е. для любого макета.

Допустимый план Х (x_ij) называется ациклическим (нециклическим), если набор клеток с отличными от нуля компонентами плана x_ij>0 не содержит ни одного цикла.

Пример ациклического  плана приведен в табл.7,

где точки обозначают клетки, в которых x_ij >0 (x_ij<0 недопустимы по смыслу задачи). Как покажем ниже, среди ациклических планов есть оптимальный.

Если в ациклическом плане Х (x_ij) число положительных компонентов

N = k + l - 1 (остальные компоненты - нули), то элементы a_ij матрицы тарифов из набора клеток, в которых расположены x_ij >0, будем называть Х-отмеченными.

Если же число положительных  компонент плана N < k + l - l, то к клеткам, занятым положительнымиx_ij добавляем недостающие до (k+l-1) из нулевых клеток, лишь бы присоединенные клетки вместе с уже взятыми не допускали циклов. Тарифы a_ij всех взятых клеток, равно как и сами клетки, включаются в число Х-отмеченных.

Больше (k + l - 1) число компонент ациклического плана не может быть: , так как уже при N=k+l по доказанной выше теореме всегда из выбранных клеток можно построить цикл.

Теорема 2 (основная теорема). Если для некоторого плана Х= (x_ij) _k?l транспортной задачи можно подобрать систему из k+l чисел u₁, u₂,…, u_i,…, u_k; v_l, v₂,…, v_j,…, v_l, удовлетворяющую следующим условиям: v_j - u_i Ј a_ij для всех i = 1, 2,., k; j = 1, 2,., l, а для x_ij>0 (x_ij (-X)) v_j - u_i = a_ij, то план Х будет оптимальным.

Числа u_i, v_j называются потенциалами пунктов отправления и пунктов назначения; условия v_j - u_i Јa_ij и v_j - u_i = a_ij называют условиями потенциальности плана Х.

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

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

Доказательство. Допустим, что для некоторого плана Х (x_ij) условия потенциальности выполнены, т.е. существует такая система чисел u_i и v_j, которая удовлетворяет условиям v_j - u_i = a_ij и v_j - u_i Ј a_ij(табл.8).

Иными словами, пусть план Х потенциален. Докажем, что этот план будет оптимальным. План Х дает значение функционалу

.

Так как мы еще не знаем, оптимален план Х или нет, то возьмем заведомо оптимальный план Х' (xў_ij)и посмотрим, какое значение он доставляет функционалу:

(транспортные расходы  минимальны). Выполняются ли условия  потенциальности для плана Х' - неизвестно, но каждой клетке (i, j) макета 8, исходя из потенциальности плана Х, соответствует неравенство v_j - u_i Ј a_ij или, наоборот, a_ij ? v_j - u_i. Возьмем из каждой клетки макета соответствующийх'_ij, умножим его на левую и правую части последнего неравенства и сложим. Получим неравенство

.

Двойную сумму в правой части обозначим для краткости  буквой S:

,

ее можно переписать в виде разности двух двойных сумм:

.

Преобразуем эти суммы  следующим образом. Первая из них  в развернутом виде дает

или

.

Аналогично вторую двойную  сумму можно записать так:

.

Тогда равенство запишется  в иной форме:

.

Но есть сумма компонент  плана по j-му столбцу, она

равна потребности j-ro пункта назначения

.

Аналогично есть сумма  компонент плана, взятая по i-й строке, она равна запасам в i-м пункте отправления

.

Эти равенства сумм компонент  по строке и столбцу соответственно запасам и потребностям будут  выполняться для любого допустимого  плана, в том числе и для  взятого в самом начале плана Х (x_ij):

Поэтому для любых допустимых планов будем иметь

и в написанном выше равенстве  суммы xў_ij можно заменить соответствующими суммами x_ij:

Теперь вернемся к форме  записи

.

В плане Х (x_ij) по условию его потенциальности для каждой положительной компоненты x_ij> 0 выполняется равенство v_j - u_i = a_ij.

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

.

Подставляя в

,

приходим к неравенству

или z_min ? z_X. Иными словами, транспортные расходы по плану Х меньше или равны минимальным расходам. Но меньше минимальных они быть не могут, остается только равенство z_X = z_min.. План Х доставляет минимальные издержки, т.е. он оптимален, что и требовалось доказать.

Таким образом, если план потенциален, то он оптимален. Это и является тем  критерием, по которому судят об оптимальности  плана.

Справедливо и обратное положение: если план оптимален, то он о6язательно потенциален. Это условие (необходимость) принимается без  доказательства. [5]

10. Особенности  решения транспортных задач с  неправильным балансом

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

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

Для решения задачи поступаем  следующим образом.

Первый случай. .

В математическую модель транспортной задачи введем фиктивный (l+l) - й пункт назначения. Для этого в матрице задачи предусмотрим один столбец, для которого потребность будет равна излишку груза: