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