Решение классической транспортной задачи методом потенциалов

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Лекция

Решение КТЗ методом потенциалов

Метод потенциалов является модификацией метода последовательного улучшения плана в ЗЛП. Решение задачи включает в себя следующие этапы:

1. Построение начального опорного плана.

2. Проверка опорного плана на оптимальность.

3. Переход в случае необходимости к лучшему опорному плану.

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

Таблица 1

опорный план перевозка потенциал

Затем необходимо построить начальный опорный план.

1. Построение начального опорного плана.

Всего существует три метода отыскания начального ОП:

1) Метод северо-западного угла,

2) Метод минимального элемента,

3) Метод Фогеля.

Рассмотрим 2 первых метода.

Метод северо-западного угла.

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

а) . При этом , а все остальные перевозки из пункта производства А₁ . Это означает, что из пункта А₁ вывозится вся произведенная продукция в пункт потребления В₁, поэтому объем перевозок из А₁ другие пункты потребления равен 0 (нули в таблицу не записываются). Т.К. Из А₁ больше вывозить нечего, то первая строка таблицы вычеркивается, а потребность пункта В₁ уменьшается на величину , т.е. .

б) . При этом , а . Ресурс в А₁ уменьшается на величину , т.е. , а столбец В₁ вычеркивается, т.к. потребность пункта В₁ полностью удовлетворена.

в) . Тогда . В этом случае вычеркивается либо строка, либо столбец (но не оба сразу!). В этом случае опорный план будет являться вырожденным, и чтобы найти нулевые базисные переменные либо строка, либо столбец в таблице остаются. Если вычеркивается строка, то считаем, что в пункте потребления В₁ остается потребность, равная 0, которая в дальнейшем д.б. удовлетворена. Если же вычеркиваем столбец, то считаем, что в пункте производства А₁ остался запас, равный 0, который в дальнейшем д.б. вывезен.

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

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

Метод минимального элемента.

В отличие от метода северо-западного угла, этот метод позволяет построить начальный опорный план, более близкий к оптимальному. Суть метода заключается в том, что в распределительной таблице находится клетка () с наименьшей стоимостью перевозки . В эту клетку назначается максимально возможный объем перевозок и эта величина записывается в клетку (). При этом возможны три случая, описанные в методе сев-зап угла. В результате закрывается один ряд . В ставшейся части таблицы вновь находится клетка с минимальной стоимостью перевозок, назначаем максимально возможный объем перевозки и т.д. Через (n+m-1) шагов получается опорный план. Базисные переменные (включая нулевые) будут записаны в клетках, а небазисные равны 0 и не записаны.

2. Проверка опорного плана на оптимальность.

Запишем исходную модель КТЗ в векторной форме:

(1)

(2)

(3)

Здесь - вектор условия,

G= - вектор ресурсов.

Известно, что каждой ЗЛП соответствует двойственная задача. В двойственной задаче столько же переменных, сколько ограничений в исходной, и столько же ограничений, сколько в исходной задаче переменных.

Пусть - двойственная переменная, соответствующая i-тым ограничениям (2) (потенциал пункта А_i), - двойственная переменная, соответствующая j-тому ограничению (3) (потенциал пункта В_j). Тогда вектор двойственных переменных будет иметь вид: , а сама двойственная задача запишется в виде:

(4)

(5)

В скалярной форме эта задача запишется:

(6)

(7)

Существует теорема (без доказательства):

Для оптимальности опорного плана КТЗ необходимо и достаточно существование вектора двойственных переменных, компоненты которого удовлетворяют условию:

(8)

Причем , если - базисная переменная, и , если - небазисная переменная.

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

Т.о., для проверки опорного плана на оптимальность необходимо определить потенциалы , всех пунктов А_i и В_j. Для этого используют условие (8) для базисных переменных:

(9)

Для отыскания потенциалов , необходимо решить данную систему линейных уравнений. Уравнений в системе (9) будет (m+n-1), а кол-во неизвестных (m+n). Поэтому любой одной переменной можно придать любое значение, в том числе и нулевое. На распределительной таблице построение потенциалов производится следующим образом: полагаем для какой-либо строки i₁, содержащей базисные переменные, потенциал =0. Просматривается эта строка, и находятся базисные клетки . Для всех таких клеток из (9) можно определить потенциалы столбцов В_j :. Далее по известным потенциалам столбцов можно определить потенциалы некоторых строк. Пусть потенциал известен. Тогда просматривается столбец с номером и находятся клетки (), содержащие базисные переменные. Для всех этих клеток из (9) можно найти потенциалы строк А_i: . Продолжая этот процесс, найдутся потенциалы строк всех пунктов производства и потенциалы столбцов всех пунктов потребления.

Далее для всех клеток (i,j) содержащих небазисные переменные, вычисляются оценки . Если все , то рассматриваемый план КТЗ является оптимальным. Если хотя бы для одной клетки (k,l) справедливо , то опорный план неоптимален и необходимо перейти к лучшему опорному плану.

3. Переход к лучшему опорному плану.

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

Пусть выбрана клетка с . Соответствующая небазисная переменная =0. Объем перевозки увеличиваем пока на неизвестную величину Q.Тогда для того, чтобы не нарушить баланс строки , необходимо в строке уменьшить объем перевозки некоторой базисной переменной на эту же величину Q. Но, уменьшив ее, мы нарушаем баланс столбца , который может быть восстановлен добавлением Q к некоторой базисной переменной столбца . Нарушенный баланс строки восстанавливается уменьшением на Q некоторой другой базисной переменной строки , и т.д.

Если таким образом удается прийти к уменьшению некоторой базисной переменной столбца , то действительно можно увеличить объем перевозки в клетке . Тем самым будут найдены объемы перевозок, увеличиваемые или уменьшаемые на величину Q. Если полученные клетки соединить прямыми линиями, то получается замкнутая линия, называемая циклом. Цикл обладает следующим свойством: линия начинается и кончается в небазисной клетке , остальные вершины ломаной принадлежат строкам и столбцам таблицы, на пересечении которых находятся базисные клетки, угол между двумя соседними сторонами равен 90⁰. Такой цикл всегда существует для любой небазисной клетки и он единственный.

Пусть цикл, соответствующий клетке , построен. В клетке ставится знак «+», а далее поочередно в вершинах цикла ставятся «-», «+»… Объемы перевозок, отмеченные «+», увеличиваются, а «-» - уменьшаются на величину Q=min{}. Таким образом, величина Q прибавляется ко всем объемам перевозок, отмеченных знаком «+», и вычитается от всех объемов перевозок, отмеченных знаком «-».

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

Рис. 1

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

Размещено на Allbest.ru