Метод потенциалов для решения транспортной задачи (стр. 1 из 3)

РЕФЕРАТ

по дисциплине МАТЕМАТИЧЕСКИЕ ОСНОВЫ ПРОГРАММИРОВАНИЯ

на тему: «Метод потенциалов для решения транспортной задачи»

Москва, 2010

1. Решение транспортной задачи

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

Iэтап. Нахождение начального допустимого решения.

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

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

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

I этап. Определение начального допустимого решения

Для сбалансированной транспортной задачи существует только m+ n - 1 независимых уравнений. Таким образом, начальное базисное допустимое решение должно иметь m+n-1 базисных переменных.

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

1. Правило "северо-западного угла"

При нахождении опорного плана транспортной задачи методом "северо-западного угла" на каждом шаге рассматривают первый из оставшихся пунктов отправления и первый из оставшихся пунктов назначения. Заполнение транспортной таблицы начинается с левого верхнего угла (северо-западного), двигаясь далее по строке вправо или по столбцу вниз (увеличение i, увеличение j). Переменной Х₁₁ приписывают максимальное значение, допускаемое ограничениями на спрос и запасы.

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

Исходный опорный план, построенный по правилу "северо-западного угла", обычно оказывается весьма далеким от оптимального, так как при его формировании не учитывается стоимость перевозок (величина с_ij). Более совершенным правилом является правило "минимального элемента".

2.Правило "минимального элемента"

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

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

3.Метод аппроксимации Фогеля.

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

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

Алгоритм решения транспортной задачи методом аппроксимации Фогеля следующий:

I этап. Определение начального допустимого плана.

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

2. Для каждого столбца таблицы необходимо упорядочить элементы стоимости перевозок c_ij по возрастанию. Далее необходимо определить величину штрафа столбца.

3. Определить строку (или столбец), имеющую (имеющий) наибольший штраф по всем штрафам строк и столбцов, а в ней (в нем) — элемент с минимальной величиной стоимости перевозок с_ij. Зафиксировать индексы (i, j) этого элемента.

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

5. Скорректировать величины а_i и b_jи вычеркнуть строку i, если а_i = 0, или столбец j, если b_j = 0.

6. Проверить, все ли величины а_iи b_j. равны нулю, если да, то окончить вычисления; в противном случае взять в качестве исходной оставшуюся часть таблицы и перейти к шагу 3.

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

II этап. Определение вводимой в базис переменной ("метод потенциалов").

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

1. Каждой строке i и столбцу j транспортной таблицы ставится в соответствие числа u_i и v_j, называемые потенциалами. Они должны для каждой базисной переменной х_ij текущего решения удовлетворять условию u_i + v_j = с_ij. Эти условия приводят к системе, состоящей из m + n - 1 уравнений (так как имеется всего m + n - 1 базис-переменных), в которых фигурируют m + n неизвестных. Значение потенциалов определяют из этой системы уравнений, придавая одному из них произвольное значение (например, u_i = 0).

2. Определяются оценки c_ijдля небазисных переменных в соответствии с соотношением:

с_ij = u_i+ v_j – с_ij

3.

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

4.

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

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

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

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

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