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

Пример.

Четыре предприятия данного экономического района для производства продукции используют три вида сырья. Потребности в сырье каждого из предприятий соответственно равны 120, 50, 190 и 110 ед. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны 160, 140, 170 ед. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

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

(61)

При данном плане перевозок общая стоимость перевозок составит

(62)

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

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

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

После того как проделаны m+n-2 описанных выше шагов, получают задачу с одним пунктом отправления и одним пунктом назначения. При этом остается свободной только одна клетка, а запасы оставшегося пункта отправления будут равны потребностям оставшегося пункта назначения. Заполнив эту клетку, тем самым делают последний шаг и получают искомый опорный план. На некотором шаге может оказаться, что потребности очередного пункта назначения равны запасам очередного пункта отправления. В этом случае также временно исключают из рассмотрения либо столбец, либо строку. Таким образом, либо запасы соответствующего пункта отправления, либо потребности данного пункта назначения считают равными нулю. Этот нуль записывают в очередную заполняемую клетку. Указанные выше условия гарантируют получение m+n-1 занятых клеток, в которых стоят компоненты опорного плана, что является исходным условием для проверки последнего на оптимальности и нахождения оптимального плана.

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

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

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

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

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

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

Теорема 1.14. Если для некоторого опорного плана транспортной задачи существуют такие числа α₁, α₂,…, α_m и β₁, β₂,…, β_n, что

и, то - оптимальный план транспортной задачи.

Определение 1.17. Числа α_i и β_j называются потенциалами соответственно пунктов назначения и пунктов потребления.

Алгоритм нахождения решения транспортной задачи состоит в следующем. Пусть одним из методов найден опорный план транспортной задачи. Для каждого из пунктов назначения и отправления определяют потенциалы α_i и β_j. Эти числа находят из системы уравнений, где - тарифы, стоящие в заполненных клетках таблицы условий транспортной задачи.

Так как число заполненных клеток равно n+m-1, то система с n+m неизвестными содержит n+m-1уравнений. Предположим, что α₁ = 0, и последовательно найдем из оставшихся уравнений остальные значения неизвестных. После того, как все потенциалы найдены, для каждой из свободных клеток определяют числа. Если среди этих чисел нет положительных, то оптимальный план найден. Если же для некоторой свободной клетки, то исходный опорный план не является оптимальным и необходимо перейти к новому опорному плану. Для этого рассматривают все свободные клетки, для которых, и среди данных чисел выбирают максимальное. Клетку, которой это число соответствует, следует заполнить.

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

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

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

Примеры циклов.

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

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

2. В данную свободную клетку переносят меньшее из чисел x_ij, стоящих в минусовых клетках. Одновременно это число прибавляют к соответствующим числам, стоящим в плюсовых клетках, и вычитают из чисел, стоящих в минусовых клетках. Клетка, которая ранее была свободной, становится занятой, а минусовая клетка, в которой стояло минимальное из чисел x_ij, считается свободной.

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

Дата добавления: 2014-01-15