Метод потенциалов для решения транспортной задачи
РЕФЕРАТ
по дисциплине МАТЕМАТИЧЕСКИЕ ОСНОВЫ ПРОГРАММИРОВАНИЯ
на тему: «Метод потенциалов для решения транспортной задачи»
Москва, 2010
1. Решение транспортной задачи
Так как транспортная задача является задачей линейного программирования, то основные этапы ее решения будут такими:
Iэтап. Нахождение начального допустимого решения.
IIэтап. Выделение из небазисных переменных вводимой в базис переменной (метод потенциалов). Если все небазисные переменные удовлетворяют условию оптимальности, то следует закончить вычисления; в противном случае — перейти к III этапу.
IIIэтап. Выбор выводимой из базиса переменной (используя условия допустимости) из числа переменных текущего базиса; затем нахождение нового базисного решения и возвращение ко II этапу.
Для лучшего понимания метода потенциалов, рассмотрим подробнее все этапы решения транспортной задачи, учитывая ее специфику.
I этап. Определение начального допустимого решения
Для сбалансированной транспортной задачи существует только m + n - 1 независимых уравнений. Таким образом, начальное базисное допустимое решение должно иметь m+n-1 базисных переменных.
Начальное базисное решение транспортной задачи получают непосредственно из транспортной таблицы. Для этого можно использовать три процедуры.
1. Правило "северо-западного угла"
При нахождении опорного плана транспортной задачи методом "северо-западного угла" на каждом шаге рассматривают первый из оставшихся пунктов отправления и первый из оставшихся пунктов назначения. Заполнение транспортной таблицы начинается с левого верхнего угла (северо-западного), двигаясь далее по строке вправо или по столбцу вниз (увеличение i, увеличение j). Переменной Х>11> приписывают максимальное значение, допускаемое ограничениями на спрос и запасы.
После этого вычеркивают соответствующий столбец или строку, фиксируя этим, что остальные переменные вычеркнутого столбца (строки) полагаются равными нулю. Если ограничения выполняются одновременно, то можно вычеркнуть либо строку, либо столбец. Процесс завершается тогда, когда будет присвоено значение переменной х>min>.
Исходный опорный план, построенный по правилу "северо-западного угла", обычно оказывается весьма далеким от оптимального, так как при его формировании не учитывается стоимость перевозок (величина с>ij>). Более совершенным правилом является правило "минимального элемента".
2.Правило "минимального элемента"
В методе "северо-западного угла" на каждом шаге потребность первого из оставшихся пунктов назначения удовлетворяется за счет запасов первого из оставшихся пунктов отправления. Очевидно, что выбор пунктов назначения и отправления целесообразно производить, ориентируясь на стоимость перевозок, а именно на каждом шаге следует выбирать какую-либо клетку, отвечающую минимальному тарифу (если таких клеток несколько, то следует выбирать любую из них), и рассматривать пункты назначения и отправления, соответствующие выбранной клетке.
Правило "минимального элемента" заключается в том, чтобы перевозить максимально возможные объемы из пунктов отправления маршрутами минимальной стоимости. Заполнение таблицы начинаем с клетки, которой соответствует наименьшая стоимость перевозки (элемент c>ij>) из всей таблицы. Переменной этой клетки х>ij> присваивается максимально возможное значение с учетом ограничений. Затем остаток по столбцу или строке помещается в клетку того же столбца или строки, которой соответствует следующее по величине значение с>ij> и т. д. Иными словами, последовательность заполнения клеток определяется по величине с>ij>, а помещаемая в этих клетках величина х>ij> такая же, как и в правиле "северо-западного угла".
3.Метод аппроксимации Фогеля.
При определении оптимального плана транспортной задачи методом аппроксимации Фогеля на каждой итерации по всем столбцам и по всем строкам находят разность между двумя записанными в них минимальными тарифами. Эти разности записывают в специально отведенных для этого строке и столбце условий задачи. Среди указанных разностей выбирают максимальную. В строке (или столбце), которой данная разность соответствует, определяют минимальный тариф. Клетку, в которой он записан, заполняют на данной итерации.
Этот метод дает наилучшее начальное приближение, часто оказывающееся оптимальным планом.
Алгоритм решения транспортной задачи методом аппроксимации Фогеля следующий:
I этап. Определение начального допустимого плана.
Для каждой строки таблицы необходимо упорядочить элементы стоимости перевозок c>ij> по возрастанию. Определить величину "штрафа" строки как разность значений второго и первого элемента в ранжированном ряду.
Для каждого столбца таблицы необходимо упорядочить элементы стоимости перевозок c>ij> по возрастанию. Далее необходимо определить величину штрафа столбца.
Определить строку (или столбец), имеющую (имеющий) наибольший штраф по всем штрафам строк и столбцов, а в ней (в нем) — элемент с минимальной величиной стоимости перевозок с>ij>. Зафиксировать индексы (i, j) этого элемента.
Присвоить наибольшее значение из допустимых (с учетом ограничений) переменной х>ij>, индексы которой соответствуют шагу 3.
Скорректировать величины а>i> и b>j> и вычеркнуть строку i, если а>i> = 0, или столбец j, если b>j> = 0.
Проверить, все ли величины а>i> и b>j>. равны нулю, если да, то окончить вычисления; в противном случае взять в качестве исходной оставшуюся часть таблицы и перейти к шагу 3.
Как правило, применение метода аппроксимации Фогеля позволяет получить либо опорный план, близкий к оптимальному, либо сам оптимальный план.
II этап. Определение вводимой в базис переменной ("метод потенциалов").
Отметим, что "метод потенциалов" эквивалентен принципу решения задачи линейного программирования и использованию условия оптимальности в симплекс-методе. Сначала находят опорный план транспортной задачи, а затем его улучшают до получения "оптимального плана". Содержание "метода потенциалов" заключается в следующем:
Каждой строке i и столбцу j транспортной таблицы ставится в соответствие числа u>i> и v>j>, называемые потенциалами. Они должны для каждой базисной переменной х>ij> текущего решения удовлетворять условию u>i> + v>j> = с>ij>. Эти условия приводят к системе, состоящей из m + n - 1 уравнений (так как имеется всего m + n - 1 базис-переменных), в которых фигурируют m + n неизвестных. Значение потенциалов определяют из этой системы уравнений, придавая одному из них произвольное значение (например, u>i> = 0).
Определяются оценки c>ij> для небазисных переменных в соответствии с соотношением:
с
>ij>
= u>i>
+
v>j>
– с>ij>
Если
все оценки с>ij>
отрицательны, то найденное решение
оптимально, в противном случае необходимо
определить новую вводимую в базис
переменную.
Вводимой
в базис переменной является небазисная
переменная, имеющая самую большую
положительную оценку с>ij>.
Наиболее эффективным методом определения вводимой переменной является метод дифференциальных рент. Если при определении оптимального плана транспортной задачи методом потенциалов сначала находился какой-нибудь ее опорный план, а затем он последовательно улучшался, то при нахождении решения транспортной задачи методом дифференциальных рент сначала наилучшим образом распределяют между пунктами назначения часть груза (так называемое условно оптимальное распределение) и на последующих итерациях постепенно уменьшают общую величину нераспределенных поставок.
Первоначальный вариант распределения груза определяют следующим образом. В каждом из столбцов таблицы данных транспортной задачи находят минимальный тариф. Найденные числа заключают в кружки, а клетки, в которых стоят указанные числа, заполняют. В них записывают максимально возможные числа. В результате получают некоторое распределение поставок груза в пункты назначения. Это распределение в общем случае не удовлетворяет ограничениям исходной транспортной задачи. Поэтому в результате последующих шагов следует постепенно сокращать нераспределенные поставки груза так, чтобы при этом общая стоимость перевозок оставалась минимальной. Для этого сначала определяют избыточные и недостаточные строки.
Строки, соответствующие поставщикам, запасы которых полностью распределены, а потребности пунктов назначения, связанных с данными потребителями запланированными поставками, не удовлетворены, считаются недостаточными. Эти строки иногда называют также отрицательными. Строки, запасы которых исчерпаны не полностью, считаются избыточными. Иногда их называют также положительными.
После того как определены избыточные и недостаточные строки, для каждого из столбцов находят разности между числом в кружке и ближайшим к нему тарифом, записанным в избыточной строке. Если число в кружке находится в положительной строке, то разность не определяют. Среди полученных чисел находят наименьшее. Это число называется промежуточной рентой. После определения промежуточной ренты переходят к новой таблице. Эта таблица получается из предыдущей таблицы прибавлением к соответствующим тарифам, стоящим в отрицательных строках, промежуточной ренты. Остальные элементы остаются прежними. При этом все клетки новой таблицы считают свободными. После построения новой таблицы начинают j заполнение ее клеток. Теперь уже число заполняемых клеток на одну больше, чем на предыдущем этапе. Эта дополнительная клетка находится в столбце, в котором была записана промежуточная рента. Все остальные клетки находятся по одной в каждом из столбцов и в них записаны наименьшие для данного столбца числа, заключенные в кружки. Заключены в кружки и два одинаковых числа, стоящих в столбце, в котором в предыдущей таблице, была записана промежуточная рента.
Поскольку в новой таблице число заполняемых клеток больше, чем число столбцов, то при заполнении клеток следует пользоваться специальным правилом, которое состоит в следующем. Выбирают некоторый столбец (строку), в котором имеется одна клетка с помещенным в ней кружком. Эту клетку заполняют и исключают из рассмотрения данный столбец (строку). После этого берут некоторую строку (столбец), в которой имеется одна клетка с помещенным в ней кружком. Эту клетку заполняют и исключают из рассмотрения данную строку (столбец). Продолжая так, после конечного числа шагов заполняют все клетки, в которых помещены кружки с заключенными в них числами. Если к тому же удается распределить весь груз, имеющийся в пунктах отправления, между пунктами назначения, то получают оптимальный план транспортной задачи. Если же оптимальный план не получен, то переходят к новой таблице. Для этого находят избыточные и недостаточные строки, промежуточную ренту и на основе этого строят новую таблицу. При этом могут возникнуть некоторые затруднения при определении знака строки, когда ее нераспределенный остаток равен нулю. В этом случае строку считают положительной при условии, что вторая заполненная клетка, стоящая в столбце, связанном с данной строкой еще одной заполненной клеткой, расположена в положительной строке.
После конечного числа описанных выше итераций нераспределенный остаток становится равным нулю. В результате получают оптимальный план данной транспортной задачи.
III этап. Определение переменной, выводимой из базиса (построение цикла).
Процедура построения цикла эквивалентна использованию условия допустимости в симплекс-методе.
Строится замкнутый цикл, соответствующий вводимой переменной. Он состоит из последовательности горизонтальных и вертикальных связанных отрезков, концами которых должны быть базисные переменные (за исключением тех концов, которые относятся к вводимой в базис переменной). Для каждого базисного решения и соответствующей небазисной переменной можно построить лишь один цикл.
Нечетным вершинам цикла (начиная с вводимой в базис переменной) присваивается знак "+", четным – "-" (будем называть эти клетки плюсовыми и минусовыми).
Определяется выводимая из базиса переменная, которой является одна из базисных переменных, расположенных в вершинах цикла, отмеченных знаком "-" и имеющих наименьшее значение.
Формируется новое допустимое базисное решение. Для этого переменные, находящиеся в вершинах цикла, соответствующим образом корректируются, а именно уменьшаются или увеличиваются на величину вводимой в базис переменной в зависимости от знака вершины цикла.
Описанный выше переход от одного опорного плана транспортной задачи к другому ее опорному плану называется сдвигом по циклу пересчета. Следует отметить, что при сдвиге по циклу пересчета число занятых клеток остается неизменным и равным (n + m - 1).
Однако при определении опорного плана или в процессе решения задачи может быть получен вырожденный опорный план. Чтобы избежать зацикливания, следует соответствующие нулевые элементы опорного плана заменить сколь угодно малым числом ε и решать задачу как невырожденную. В оптимальном плане такой задачи необходимо считать ε = 0.
транспортный задача алгоритм фогель цикл
2. Пример практического решения задачи оптимального планирования
Перевозки товаров различными транспортными средствами в ряде случаев приводят к таким нежелательным явлениям, как порожние пробеги, простои, встречные и нерациональные перевозки. Для их исключения используются методы оптимального планирования перевозок, в частности такая экономико-математическая модель, как транспортная задача.
Простейшим примером транспортной задачи является задача о планировании перевозок некоторого продукта из конечного числа пунктов отправления в конечное число пунктов назначения при обеспечении минимальных затрат на выполнение данной операции.
Пример: Три поставщика некоторого товара располагают следующими запасами: первый – 120 единиц, второй – 100 единиц, третий – 80 единиц. Товар должен быть перевезен трем потребителям: спрос первого – 90 единиц; спрос второго – 90 единиц; спрос третьего – 120 единиц. Известны также показатели затрат (c>ij>) на перевозку единицы товара от каждого поставщика к каждому потребителю.
Требуется составить оптимальный план перевозок, приводящий к наименьшим затратам на выполнение данной операции.
Под планом перевозок понимается матрица
-
X>11>
X>12>
X>13>
X>21>
X>22>
X>23>
X>31>
X>32>
X>33>
в которой х>ij> количество единиц товара, планируемого к перевозке от поставщика с номером i к потребителю с номером j.
Для решения задачи исходные данные удобно свести в таблицу:
-
Поставщики
Возможности поставщиков
Потребители и их спрос
1
2
3
90
90
120
1
120
7
6
4
2
100
3
8
5
3
80
2
3
7
Каждую клетку таблицы пометим двойным индексом (i, j). Первый (i) – номер поставщика, второй (j) – номер потребителя.
Числа на пересичении стоимости перевозок и обозначаются с>ij>.
Математическая постановка данной задачи имеет вид: найти минимум целевой функции (показателя эффективности)
Z= 7х>11> + 6х>12> + 4х>13> + Зх>21> + 8х>22> + 5х>23> + +2х>31> +3х>32> + 7х>33> при ограничениях:
n n n
Σx>1>>j> =120; Σx>2>>j> =100; Σx>3>>j> =80;
j=i j=i j=i
m m m
Σx>i>>1> =90; Σx>i>>1> =90; Σx>i>>1> =120; х>ij>>0
i=l i=l i=l
Транспортная задача относится к классу задач линейного программирования. Решение таких задач обычно связано с получением опорного (допустимого) плана и последующим его улучшением.
Опорный план может быть получен различными методами. Рассмотрим метод минимального элемента, или метод наименьших.
В соответствии с методом наименьших затрат выберем в таблице клетку, имеющую наименьший показатель затрат, т. е. клетку (3,1). Произведем поставку в эту клетку, равную 80 единицам, поскольку первому потребителю требуется .90 единиц, а у третьего поставщика в наличии лишь 80 единиц. Первому потребителю необходимо еще 10 единиц товара. Он может получить их или от первого, или от второго поставщика. Так как показатель затрат в клетке (2,1) меньше, чем в клетке (1,1), то записываем 10 единиц в клетку (2,1).
Второй поставщик, отдав 10 единиц, будет располагать 90 единицами. Их можно направить второму или третьему потребителю. В связи с тем, что показатель затрат в клетке (2, 3) меньше, чем в клетке (2, 2), направим их третьему потребителю. Недостающие 30 единиц третий потребитель получит от первого поставщика.
Оставшиеся у первого поставщика 90 единиц запишем в клетку (1, 2) и, тем самым, удовлетворим спрос второго потребителя.
На этом распределение можно считать законченным.
-
Поставщики
Возможности поставщиков
Потребители и их спрос
1
2
3
90
90
120
1
120
7
6
90
4
30
2
100
3
10
8
5
90
3
80
2
80
3
7
Получив опорный план, необходимо оценить соответствующую ему стоимость перевозок (показатель эффективности или целевую функцию). Для плана, полученного методом наименьших затрат, Z = 1300 ед.
Следующим этапом решения задачи, независимо от того, каким методом был найден опорный план, является последовательное его улучшение до получения оптимального распределения. С этой целью каждому поставщику товаров поставим в соответствие потенциалы А>1>, А>2>, А>3> и запишем их в дополнительном столбце, а каждому потребителю – потенциалы B>1>, В>2>, В>3>, которые запишем в дополнительной строке. Один из потенциалов, например A>1> приравняем к нулю, а остальные найдем с использованием:
А>ij> = А>i> + В>j>
Запишем данное соотношение для всех заполненных клеток (Х>ij> > 0) и определим А>2>, А>3>, В>1>, В>2>, В>3>. Для незаполненных клеток (Х>ij> = 0) запишем аналогичную зависимость, левую часть которой принято называть псевдостоимостью.
C>ij> = A>i>+B>j>
Условие оптимальности плана заключается в том, что для каждой свободной клетки (X>ij> = 0)
С>ij><С>ij>.
Найдем
для свободных клеток разности Δ>ij>
= С>ij>
– C>ij>
Поскольку
одна из разностей, соответствующая
клетке (3,2), отрицательна, то улучшение
плана начинаем именно с нее.
-
Поставщики
Возможности поставщиков
Потребители и их спрос
A>i>
1
2
3
90
90
120
1
120
72
6
90
4
30
0
2
100
3
10
87
5
90
2
3
80
2
80
36
74
4
B>j>
7
6
3
Заметим, что если отрицательных разностей несколько, то первой выбирается клетка, для которой разность по абсолютной величине больше.
Догрузим клетку (3, 2), поставив в нее знак плюс (+), и составим цепь пересчета по правилу: цепь пересчета строится в виде прямоугольника, одна из вершин которого находится в свободной клетке (3, 2), а остальные – в занятых; все углы должны быть прямыми; в одной строке и в одном столбце не должно быть более двух вершин; всем вершинам приписываются чередующиеся знаки (плюс – догрузить, минус – разгрузить).
-
Поставщики
Возможности поставщиков
Потребители и их спрос
A>i>
1
2
3
90
90
120
1
120
72
6-90
4+
30
0
2
100
3+10
87
5-
90
2
3
80
2-
80
3+6
74
4
B>j>
7
6
3
Из клеток со знаком минус (-) выбирается наименьшая величина груза min (80, 90, 90) = 80 и перемещается последовательно по клеткам построенной цепи: 80 единиц добавляются в клетки со знаком плюс и изымаются из клеток со знаком минус. Таким образом, получаем новый план перевозок. Применив к нему рассмотренную выше методику, можно убедиться, что этот план является оптимальным.
-
Поставщики
Возможности поставщиков
Потребители и их спрос
1
2
3
90
90
120
1
120
7
6
10
4
110
2
100
3
90
8
5
10
3
80
2
3
80
7
В общем случае математическая постановка транспортной задачи имеет вид:
,
при ограничениях
В рассмотренном примере
т.е. возможности поставщиков равны суммарному спросу потребителей. Транспортные задачи подобного вида называют закрытыми. Задачи, для которых это условие не выполняется представляют собой открытые задачи. Для решения открытых задач их приводят к закрытому виду путем введения фиктивного поставщика или фиктивной потребителя с возможностями по поставке или спросом, определяемыми по формуле
В остальном методика решения задачи остается неизменной.
Список использованной литературы
Математическое программирование. Учебное издание. Под общей редакцией К.В. Балдина, авторы К.В. Балдин, Н.А. Брызгалов, А.В. Рукосуев. Москва: «Издательско-торговая корпорация «Дашков и К», 2010.