16. Тз. Построение исходного базисного плана.
Допустимый план х = (x1,...,xn)T называется базисным планом задачи (4.1), если у него найдется n — m нулевых компонент и при этом остальным компонентам хj1,..., хjm будут соответствовать линейно независимые столбцы матрицы А: Aj1,…,Ajm . Набор этих столбцов называется базисом этого базисного плана. Если у базисного плана т положительных компонент, т.е хj1>0,... Xjm >0, то он называется невырожденным. В противном случае, т.е. если у него положительных компонент меньше, то его называют вырожденным.
<С,х>—> max, Ах = b, х >= Оn,
где х = (x1,...,xn) T принадл . Rn .c = (с1,...,сn) T принадл . Rn, , b = (b1,...,bm) принадл . Rm . Матрица А размерности m на n.
Метод северо-западного угла. Назначение перевозок хij начинаем с верхней левой клетки (северо-западного угла) таблицы. Положим х11 — min (а1, b1). Если a1>b1 то Х11= b1 вычеркиваем из матрицы столбец j = 1, так как спрос первого потребителя полностью удовлетворен. Если a1<b1 то х11 = а1, вычеркиваем строку i=1, так как в этом случае полностью исчерпаны запасы первого поставщика. Если а1 = b1 то вычеркиваем и строку i = 1, и столбец j=1 одновременно. Вычеркнув ряд, соответствующий min (a1, b1) скорректируем запасы и потребности первого поставщика и первого потребителя на величину x11. С оставшейся матрицей поступим аналогично предыдущему. Продолжая действовать по этой схеме, исчерпаемзапасы поставщиков и удовлетворим запросы потребителей. На последнем шаге процесса получится матрица 1 х 1, в которой одновременно вычеркиваем и строку, и столбец. Метод северо-западного угла не учитывает матрицу тарифов, поэтому начальный план может оказаться далеким от оптимального. Более близким к оптимальному обычно является план, построенный методом минимальной стоимости.
Метод минимальной стоимости. Находим min cij =сi0j0 . Аналогично предыдущему способу, если а i0> bi0 . то xi0j0=bj0 , вычеркиваем столбец j0, запасы поставщика i0 корректируем, т. е. считаем равными ai0 - xi0j0 если я а i0< bi0, то xi0j0=ai0, вычеркиваем строку i0, запасы потребителя j0 считаем равными bj0- xi0j0 ,если же а i0 = b jo , то xi0j0=аi0 =bj0. , вычеркиваем и строку i=i0 и столбец j=j0 одновременно. Вычеркнув один из рядов матрицы и скорректировав запасы либо поставщика, либо потребности получателя на величину xi0j0 оставшейся матрицей меньшего размера поступаем аналогично предыдущему. На последнем шаге в матрице 1 х 1 одновременно убираем и строку, и столбец. Построенный начальный план перевозок должен быть базисным, т. е. число назначенных перевозок Хij должно быть равно m + n -1. Если это условие не выполняется, а условие общего баланса выполнено, то построенный начальный план — вырожденный. Для построения базисного плана в исходный план вводят нулевые перевозки так, чтобы не образовывался замкнутый контур из назначенных перевозок. Заполнение клеток нулем не влияет на экономическую оценку решения, но оно необходимо для получения начального базисного плана и для поиска оптимального решения.
Замкнутым контуром (циклом) в матрице называется непрерывная замкнутая ломаная линия, вершины которой находятся в загруженных клетках матрицы, а звенья расположены вдоль строк и столбцов. Причем в каждой вершине замкнутого контура встречаются ровно два звена; одно из них располагается по строке, другое — по столбцу, таким образом, звенья образуют прямой угол. Если замкнутый контур образует самопересекающаяся ломаная линия, то точки ее самопересечения вершин не образуют. Примеры некоторых замкнутых контуров показаны на рисунке 2.1.
Рисунок 2.1 - Примеры форм замкнутых контуров
При правильном построении плана перевозок, начиная с любой незагруженной клетки можно построить лишь один замкнутый контур.
17. ТЗ. Метод потенциалов.
Этот первый точный метод решения транспортной задачи предложен в 1949 году Кантаровичем А. В. И Гавуриным М. К. по существу он является детализацией метода последовательного улучшения плана применительно к транспортной задаче. Он позволяет, отправляясь от некоторого допустимого решения, получить оптимальное решение за конечное число итераций. Общая схема отдельной итерации такова.
По допустимому решению каждому пункту задачи сопоставляется число, называемое его предварительным потенциалом. Пунктам Аi соответствуют числа ui, пунктам Bj - числа vj. Они выбираются таким образом, чтобы их разность на k-й итерации была равна Сij - стоимости перевозки единицы продукции между пунктами Аi и Вj:
Если разность предварительных потенциалов для каждой пары пунктов Аi, Вj не превосходит Сij, то полученный план перевозок является решением задачи. В противном случае указывается способ получения нового допустимого плана, связанного с меньшими транспортными издержками. За конечное число итераций находится оптимальный план задачи.
Рассмотрим подробнее процесс определения потенциалов текущего плана транспортной задачи. Потенциал первого пункта потребления принимаем равным нулю
Теперь, зная его, мы можем определить потенциалы для всех пунктов производства, связанных с первым пунктом ненулевыми перевозками.
Для свободных клеток транспортной таблицы вычисляются величины
называемые разностями потенциалов. В таблице они выписаны для всех небазисных клеток под ценами.
Разность потенциалов можно трактовать как увеличение цены продукта при его перевозке из пункта i в пункт j.
Процесс «улучшения» плана состоит в определении вводимой и выводимой клеток, в чем прослеживается содержательная аналогия с соответствующими пунктами симплекс-процедур.
Выводимая клетка определяется с помощью так называемой цепочки преобразования плана, описывающей характер перераспределения грузовых потоков. В соответствии со свойствами транспортной задачи для невырожденного базисного плана в текущей таблице можно образовать замкнутую цепочку, состоящую только их вертикальных и горизонтальных звеньев, одной из вершин которой является выбранная свободная клетка, а остальные — занятые клетки.
В построенной цепочке, начиная с вводимой клетки (которая считается первой), помечаются вершины: нечетные — знаком «+», а четные знаком «—». Знаком «+» отмечаются те клетки, в которых объемы перевозок должны увеличиться (таковой, в частности, является клетка, вводимая в план, поскольку она должна стать базисной). Знаком «—» — те клетки, в которых перевозки уменьшаются с целью сохранения баланса. Среди множества клеток, помеченных знаком «—», выбирается клетка с наименьшим значением.
Она и становится кандидатом на вывод, т. к. уменьшение объема перевозок на большую величину может привести к отрицательным значениям xi,j в других «минусовых» клетках. Затем производится пересчет плана по цепочке: к объемам перевозок в клетках, помеченных знаком «+», добавляется объем q, а из объемов клеток, помеченных знаком «—», он вычитается. В результате ввода одной клетки и вывода другой получается новый базисный план, для которого на следующей итерации описанные выше действия повторяются.
Завершая разговор о методе потенциалов, следует отдельно остановиться на ситуации возникновения вырожденного плана. Возможность получения вырожденного плана уже отмечалась при описании метода северо-западного угла. Нетрудно заметить, что вырожденный план также может получиться на этапе преобразования текущего плана по цепочке: если одинаковое минимальное значение будет достигнуто сразу на нескольких клетках, помеченных знаком «—», то при вычитании перемещаемого по цепочке объема в новом плане будет меньше чем m + n-1 ненулевых компонент.
Способ преодоления вырожденности в транспортной задаче весьма прост, а именно: предлагается дополнить текущий план необходимым количеством нулевых клеток (фиктивными перевозками) таким образом, чтобы они позволяли рассчитать полную систему потенциалов, и далее действовать в соответствии с правилами описанного выше алгоритма.