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

1. Формулировка транспортной задачи

2. Математическая модель транспортной задачи

3. Необходимое и достаточное условия разрешимости транспортной задачи

4. Свойство системы ограничений транспортной задачи

5. Опорное решение транспортной задачи

6. Методы построения начального опорного решения

6.1 Построение первоначального плана по способу северо-западного угла

6.2 Построение первоначального плана по способу минимального элемента

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

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

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

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

11. Алгоритм решения транспортной задачи методом потенциалов

11.1 Предварительный шаг

11.2 Общий повторяющийся шаг

12. Транспортная задача с ограничениями на пропускную способность

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

14. Применение транспортной задачи для решения экономических задач

Заключение

Список использованной литературы

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

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

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

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

Весьма типичной задачей, решаемой с помощью линейного программирования, является транспортная задача. (1)

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

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

Исходная информация:

M_{i -} количество единиц груза в i-м пункте отправления (i = 1, 2, …, k);

N_j - потребность в j-м пункте назначения (j = 1, 2, …, l) (в единицах груза);

a_ij - стоимость перевозки единицы груза из i-гo пункта в j-й.

Обозначим через x_ij планируемое количество единиц груза для перевозки из i-ro пункта в j-й.

В принятых обозначениях:

 - общая (суммарная) стоимость перевозок;

 - количество груза, вывозимого из i-ro пункта;

 - количество груза, доставляемого в j-и пункт.

В простейшем случае должны выполняться следующие очевидные условия:

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

найти

при условиях

;

;

Эта задача носит название замкнутой (закрытой, сбалансированной) транспортной модели.

Заметим, что условие  является естественным условием разрешимости замкнутой транспортной задачи.

Более общей транспортной задачей является так называемая открытая (несбалансированная) транспортная модель:

найти

при условиях

Ясно, что в этой задаче не предполагается, что весь груз, накопленный в i-м пункте, должен быть вывезен. (3)

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

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

Здесь показатели a_ij означают затраты на перевозку единицы груза от i-го поставщика (i=1,2,…,k) к j-тому потребителю (j=1,2,…,l), M_i - мощность i-того поставщика в планируемый период, N_j - спрос j-того потребителя на этот же период. Обозначим через x_ij поставку (количество груза), которая планируется к перевозке от i-того поставщика к j-тому потребителю. Математически задача сводится к нахождению минимума целевой функции, выражающей суммарные затраты на перевозку груза, т.е. функции

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

(1)

Если к этим ограничениям добавить еще одно:

,(2)

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

Задачам, в которых ограничение (2) отсутствует, т.е.

,

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

Отметим некоторые особенности экономико-математической модели транспортной задачи.

Система ограничений (1) сразу имеет вид уравнений, поэтому отпадает необходимость вводить добавочные переменные.

Матрица коэффициентов при переменных в системе (1) состоит только из единиц и нулей.

Система ограничений (1) включает k уравнений, связывающих поставки i-того поставщика с мощностью M_i (i=1,2,…,k) этого поставщика, и l уравнений, связывающих поставки j-тому потребителю со спросом N_j (j=1,2,…,l) этого потребителя. Заметим, что число k равно числу строк исходной таблицы, а число l - числу столбцов.

Число переменных x_ij, входящих в целевую функцию и в систему уравнений (1), равно произведению kl, т.е. числу клеток таблицы.

Таким образом, система ограничений (1) есть система из k+l уравнений с kl переменными.

Любое решение транспортной задачи (x₁₁, x₁₂,…, x_kl) называется распределением поставок. Так как поставки не могут быть отрицательными, то речь идет только о допустимых решениях.

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

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

Ограничение (1) и условия неотрицательности переменных, исключающие обратные перевозки x_ij>0; i= 1, 2, …, k; j= 1, 2,., l.

Эти условия образуют систему ограничений. Любой план, компоненты которого удовлетворяют этой системе, будет допустимым.

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

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

.

Равенство  является необходимым условием совместности ограничений задачи.

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

Действительно, пусть . Рассмотрим такие числа:

Убедимся, что эти числа образуют допустимый план. Для этого достаточно проверить, что они удовлетворяют всем ограничениям задачи.

Просуммируем эти числа по индексу i:

.

Но величины N_j, от индекса i не зависят и их можно вынести за знак суммы. В результате

или

,

Следовательно, взятые числа удовлетворяют группе уравнений (1).

Просуммируем эти числа по индексу j:

Вынося постоянные M_i и  за знак суммы и имея в виду, что , получаем

или в развернутом виде

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

Равенство запасов потребностям есть необходимое и достаточное условие совместности и, следовательно, разрешимости транспортной задачи. (5)

Согласно теореме о структуре координат опорного плана задачи линейного программирования, в невырожденном опорном плане должно содержаться r отличных от нуля координат, где r - ранг системы ограничений

.

В этой системе ограничений уравнений закрытой транспортной задачи имеется k+l-1 линейно-независимых уравнений, т.е. ранг системы ограничений равен k+l-1. (6)

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

При решении задачи линейного программирования можно поступить следующим образом: найти любое из таких "вершинных" решений, не обязательно оптимальное, и принять его за исходный пункт расчетов. Такое решение и будет базисным. Если окажется, что оно и оптимальное, расчет на этом закончен, если нет - последовательно проверяют, не будут ли оптимальными соседние вершинные точки. Ту из них, в которой план эффективнее, принимают снова за исходную точку и так, последовательно проверяя на оптимальность аналогичные вершины, приходят к искомому оптимуму. На этом принципе строятся так называемый симплексный метод решения задач линейного программирования, а также ряд других способов, объединенных общим названием "методы последовательного улучшения допустимого решения (МПУ)": метод обратной матрицы, или модифицированный симплекс-метод, метод потенциалов для транспортной задачи и другие. Они отличаются друг от друга вычислительными особенностями перехода от одного базисного решения к другому, улучшенному. (2)

В этом случае не обращают внимания на показатели затрат. Начав заполнение с клетки (1.1) - "северо-западного угла" таблицы, ступенями спускаются вниз до клетки (k, l), вычеркивая либо одну строку, либо один столбец. На последнем шаге вычеркиваются последняя (k-я) строка и последний (l-й) столбец. При практическом заполнении таблицы, вычеркивание строк и столбцов производится лишь мысленно.

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

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

Способ минимального элемента учитывает тарифы и потому позволяет найти план, более близкий к оптимальному.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основная часть макета выделена двойными линиями. Она содержит 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)

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

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

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

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

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

,

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

 min

Фиктивный потребитель обеспечивает совместность ограничений, не внося искажений в решение.

Второй случай.

Если запасов не хватает для удовлетворения потребностей, т.е. , то вводим фиктивный (k+1) - й пункт отправления, которому приписываем запас груза, равный

,

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

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

Этот шаг включает следующих три этапа.

1. Находим допустимый ациклический план.

2. Составляем систему чисел - потенциалов пунктов отправления и пунктов назначения.

3. Анализируем систему на потенциальность. Если она потенциальна (т.е. план потенциален), то найденный план оптимален. Если система не потенциальна, приступаем к общему шагу.

Первый этап: нахождение допустимого ациклического плана способом северо-западного угла.

Невзирая на тарифы, начинаем составление плана с заполнения левой верхней клетки (1,1) (с северо-западного угла).

Смотрим на запасы M₁ и потребности N₁. Если M₁ < N₁, то в клетку (1,1) вписываем M_l (т.е. отдаем пункту назначения весь запас груза из первого пункта отправления - случай в таблице). Если N₁ < M₁, то в клетку (1,1) записываем N₁, т.е. покрываем всю потребность первого пункта назначения за счет первого пункта отправления.

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

Второй тур начинаем опять с северо-западного угла. Удовлетворяем оставшуюся потребность первого пункта назначения, доставив туда (N₁-M_l) единиц груза из второго пункта отправления. Если потребность первого пункта удовлетворена полностью, остальные клетки в первом столбце прочеркиваем. Переписываем баланс после второй операции.

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

Второй этап предварительного шага: определение системы потенциалов.

Потенциал приписывается каждому пункту отправления (обозначается u_i) и каждому пункту назначения (v_j). Всего потенциалов k+l чисел. Они вносятся в специально отведенные для этого строку и столбец макета.

Для Х-отмеченных тарифов a_ij, число которых всегда равно (k + l - 1), должны выполняться равенства v_j - u_i = a_ij. Эти равенства и будут служить теми уравнениями, из которых находятся потенциалы. Однако таких уравнений будет только (k + l - 1), а неизвестных в системе (k + l), т.е. на единицу больше. Такая система уравнений имеет бесчисленное множество решений, любое из которых годится для нашей цели. Чтобы найти какое-то одно решение, значение одного потенциала выбираем произвольно. Остальные потенциалы определяем из решения системы. Третий этап предварительного шага: испытание плана или системы потенциалов на потенциальность. Потенциальность заключается в том, чтобы неравенство v_j - u_i < a_ij выполнялось для всех без исключений клеток. При этом Х-отмеченные клетки проверять не надо, так как потенциалы подобраны из условия выполнения в них равенства.

Выделяем положительные разности d_ij:

d_ij = v_j - u_i - a_ij > 0.

На этом предварительный шаг закончен.

Общий шаг выполняется в такой последовательности.

1. Из положительных разностей d_ij находим наибольшую разность d_i0j0:

d_iojo = mах (v_j - u_i - a_ij > 0).

Пусть этот максимум имеет место для клетки (i₀, j₀). Включаем эту клетку в набор Х-отмеченных (k + l - 1) клеток. Клеток становится (k+l), а для такого их количества всегда можно построить цикл. Этот цикл будет в данной ситуации единственным.

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