Контрольная работа: Метод потенциалов для решения транспортной задачи

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 этап. Определение вводимой в базис переменной ("метод потенциалов").

--> ЧИТАТЬ ПОЛНОСТЬЮ <--