Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Алгоритм метода потенциалов
Предположим, у нас имеется некоторый план перевозок. Производим следующие действия: 1. Для каждого поставщика и каждого потребителя найдем потенциалы и по следующим правилам: а) ; б) для каждой загруженной клетки должно выполняться равенство . Другими словами, по загруженным клеткам составляем, затем решаем систему уравнений 2. Для каждой незагруженной клетки вычисляем разность . Если разности неотрицательны, процесс решения прекращается – имеющийся план перевозок оптимальный. Если же найдется хотя бы одна разность , то среди всех отрицательных значений выберем наибольшее по модулю и в соответствующей клетке поставим знак «+». 3. В имеющейся распределительной таблице построим замкнутый контур одного из видов а) ; б) ; в) с углами в загруженных клетках и в этой клетке со знаком «+». На практике при построении такого контура можно руководствоваться следующими правилами: нужно «выйти» из клетки, помеченной знаком «+»; «передвигаться» только по горизонтали и вертикали; «поворачивать» только в загруженных клетках и только на 90о; «вернуться» в клетку со знаком «+». При этом следует иметь в виду, что, во-первых, стараться «обойти» все загруженные клетки не нужно; во-вторых, «проходить», не «поворачивая», можно как через загруженные, так и через незагруженные клетки, важно только «поворачивать» в загруженных клетках; в-третьих, такой замкнутый контур всегда существует и является единственным. 4. «Обходя» построенный контур в каком-нибудь направлении, в его углах ставим поочередно знаки «–» и «+», при этом «обход» начинаем из клетки, которую мы пометили знаком «+» на шаге 2 данного алгоритма. Обратите особое внимание на то, что знаки «–» и «+» ставятся только в клетках, в которых контур «поворачивает». Признаком правильности расстановки этих знаков может служить то, что на любых двух соседних «поворотах» знаки должны быть различными. 5. Строим следующую распределительную таблицу, в которую перенесем без изменений, во-первых, тарифы перевозок, во-вторых, загрузки клеток, не помеченных знаками «–» и «+». Новые загрузки клеток со знаками «–» и «+» найдем по следующим правилам. Среди загрузок клеток со знаком «–» выберем минимальную, затем выбранную минимальную загрузку нужно в клетках со знаком «+» прибавить, а в клетках со знаком «–» отнять от имеющихся там загрузок. При этом хотя бы в одной из клеток со знаком «–» появится нулевая загрузка. Если такая клетка со знаком «–» с нулевой загрузкой одна, то в новой таблице в данной клетке нулевую загрузку не пишем; если же таких клеток несколько, в новой таблице нулевую загрузку не пишем только в одной из этих клеток, а именно, в клетке с максимальным тарифом. 6. Снова вычисляем потенциалы и (см. шаг 1) и т. д. Процесс продолжается до тех пор, пока все разности (см. шаг 2) не окажутся неотрицательными.
|