Методы линейного программирования для решения транспортной задачи

Перепишем баланс после первой операции (изменятся и потребности, и запасы). В первой строке остальные клетки можно прочеркнуть, так как весь груз пошел в первый пункт.

Второй тур начинаем опять с северо-западного угла. Удовлетворяем оставшуюся потребность первого пункта назначения, доставив туда (N1-Ml) единиц груза из второго пункта отправления. Если потребность первого пункта удовлетворен

а полностью, остальные клетки в первом столбце прочеркиваем. Переписываем баланс после второй операции.

Снова начинаем с северо-западного угла, удовлетворяем потребность второго пункта назначения и т.д., пока справа и снизу не будут стоять нули, т.е. весь груз распределен и потребности удовлетворены. Полученный внутри таблицы план будет допустимым. Его и берем в качестве исходного.

Второй этап предварительного шага: определение системы потенциалов.

Потенциал приписывается каждому пункту отправления (обозначается ui) и каждому пункту назначения (vj). Всего потенциалов k+l чисел. Они вносятся в специально отведенные для этого строку и столбец макета.

Для Х-отмеченных тарифов aij, число которых всегда равно (k + l - 1), должны выполняться равенства vj - ui = aij. Эти равенства и будут служить теми уравнениями, из которых находятся потенциалы. Однако таких уравнений будет только (k + l - 1), а неизвестных в системе (k + l), т.е. на единицу больше. Такая система уравнений имеет бесчисленное множество решений, любое из которых годится для нашей цели. Чтобы найти какое-то одно решение, значение одного потенциала выбираем произвольно. Остальные потенциалы определяем из решения системы. Третий этап предварительного шага: испытание плана или системы потенциалов на потенциальность. Потенциальность заключается в том, чтобы неравенство vj - ui < aij выполнялось для всех без исключений клеток. При этом Х-отмеченные клетки проверять не надо, так как потенциалы подобраны из условия выполнения в них равенства.

Выделяем положительные разности dij:

dij = vj - ui - aij > 0.

На этом предварительный шаг закончен.

11.2 Общий повторяющийся шаг

Общий шаг выполняется в такой последовательности.

1. Из положительных разностей dij находим наибольшую разность di0j0:

diojo = mах (vj - ui - aij > 0).

Пусть этот максимум имеет место для клетки (i0, j0). Включаем эту клетку в набор Х-отмеченных (k + l - 1) клеток. Клеток становится (k+l), а для такого их количества всегда можно построить цикл. Этот цикл будет в данной ситуации единственным.

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

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

3. Выбираем наименьшее значение перевозки в клетках отрицательной полуцепи (xij) - . Пусть оно равно Q:

min (xij) - = Q.

Если таких значений несколько, берем одно из них, безразлично какое.

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

Процесс сдвига меняет план, но план остается допустимым.

Действительно, допустимый план обеспечивает баланс в строках и столбцах; всякий план, не нарушающий этот баланс, будет допустимым. Любой цикл, по которому производится сдвиг, содержит в каждом ряду (строке, столбце) по две вершины. В одну клетку добавляем Q, а из другой вычитаем Q, и баланс не нарушается. Следовательно, план, найденный в результате сдвига, останется допустимым.

После сдвига в клетке отрицательной полуцепи с минимальной перевозкой будет стоять нуль, а в клетке (i0, j0), включенной в набор, окажется число Q. Первую клетку из плана исключаем, а вторую включаем; план остается по-прежнему ациклическим, так как единственный имевшийся цикл нарушается исключением клетки.

Полученный после сдвига план можно записать следующим образом:

5. для полученного после сдвига плана составляем новую систему потенциалов. Эти новые потенциалы можно вычислить так же, как это делалось в предварительном шаге, а можно найти исправлением уже имеющейся системы.

Для занятых клеток должны выполняться равенства .

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

Затем испытываем другие занятые клетки и корректируем последовательно остальные потенциалы. Изменению подвергаются, как правило, не все числа, и такой порядок сокращает расчеты.

6. Производим исследование новой системы на потенциальность, т.е. исследование найденного плана на оптимальность. Для этого проверяем выполнение неравенств vj - ui ≤ aij для всех незанятых клеток. Если для них неравенства выполняются, то система потенциальна и план оптимален, т.е. решение закончено. Если для каких-то клеток неравенства не выполняются, вычисляем разности dij и делаем снова общий шаг и т.д., до тех пор, пока не будет получен оптимальный план. Вырождение в транспортной задаче проявляется в том, что среди (k+l-1) Х-отмеченных клеток оказывается клетка с нулевой перевозкой. Если эта клетка не попадает в цикл, на нее не обращаем внимания. Если она попадает в положительную полуцепь цикла, то на следующем шаге вместо нуля получим в этой клетке положительное число. Если же нулевая клетка оказывается в отрицательной полуцепи, то Q=0, т.е. сдвиг надо делать на число нуль. Такой нулевой сдвиг плана не меняет, но нуль переходит в другую клетку, меняется набор Х-отмеченных клеток и система потенциалов. Это дает возможность на очередном шаге осуществить уже не нулевой сдвиг и изменить план в сторону его улучшения. Контроль вычислений осуществляется таким образом. В процессе решения задачи на каждом шаге полученный план проверяется на допустимость. Для этого компоненты плана суммируются по строкам и столбцам; суммы должны равняться соответственно запасам и потребностям пунктов. Окончательный (оптимальный) план проверяется по формуле, вытекающей из доказательства основной теоремы:

,

 Скачать реферат