Алгоритм метода потенциалов [c.272]
Полученные с помощью этого алгоритма сбалансированные планы поставок ресурсов и услуг могут быть в дальнейшем оптимизированы стандартными методами (потенциалов, венгерским и др.) [c.107]
Алгоритм решения транспортной задачи методом потенциалов. [c.75]
На основании данных о производстве основных видов нефтепродуктов, грузообороте нефтебаз и размещении емкости МСХ нефтепродуктов решается задача выбора рационального вида транспорта нефтепродуктов от НПЗ к нефтебазам. В общем случае эта задача нелинейна. Разработан алгоритм, сводящий решение исходной нелинейной задачи к последовательному решению ряда линейных задач методом потенциалов. Для решения задачи организуется итерационная процедура, строится избыточная трубопроводная сеть. На каждой итерации рассматривается совмещенная сеть (избыточная трубопроводная и железнодорожная) и определяется оптимальное распределение грузопотоков между видами транспорта. В качестве экономического критерия при сравнении различных способов [c.41]
Соответствующая задача сводится к сетевой транспортной задаче с дополнительными ограничениями (,СТЗ ДО), где условия СТЗ полностью определяются сетью (графом) задачи, а дополнительные ограничения формируются по информации о связующих дугах. При этом число дополнительных ограничений равно (А —1)7, где / — число цепочек в (7 + 1)-й подсети. Для решения возникающей задачи могут быть использованы специальные алгоритмы и программы решения СТЗ ДО. Следует подчеркнуть, что в этих алгоритмах существенно используется структура матрицы СТЗ ДО, т. е. на каждой итерации операции преобразования обратной матрицы строятся в соответствии с методом потенциалов решения СТЗ. [c.70]
Таким образом, задача сводится к кусочно-линейному программированию на сети. Учитывая специфику матрицы этой задачи, удалось разработать специальный алгоритм [15], основанный на совмещении общего метода кусочно-линейного программирования и метода потенциалов для решения СТЗ. [c.72]
В настоящее время разработано множество различных алгоритмов решения Т.з. распределительный метод, метод потенциалов, дельта-метод, венгерский метод, метод дифференциальных рент, способ двойного предпочтения, различные сетевые методы. Они относительно просты, по ним составлены десятки программ для различных вычислительных машин. Во многих снабженческих, транспортных и других организациях во всем мире с их помощью рассчитываются маршруты доставки материалов на строительные площадки, планы длительного прикрепления поставщиков металлопроката к потребителям, планы перевозок топлива. Задачи эти часто усложняются разного рода дополнительными условиями напр., в них включается расчет не только себестоимости перевозок, но и себестоимости производства продукции (производственно-транспортная задача), оптимизируется совместно доставка взаимозаменяемых видов продукции (скажем, различных кровельных материалов), оптимизируется доставка грузов с промежуточными базами (складами). Кроме того, следует учитывать, что экономико-математическая модель Т.з. позволяет описывать множество ситуаций, весьма далеких от проблемы перевозок, в частности, находить оптимальное размещение заказов на производство изделий с разной себестоимостью. [c.367]
Главным в методе, естественно, является основной алгоритм. Этот алгоритм, как отмечалось, характеризуется соединением идей общего метода КЛП [28. Глава седьмая] и метода потенциалов для решения СТЗ ЛП [28. Глава первая]. Не рассматривая этот алгоритм в рамках данной книги, подчеркнем, что он достаточно строго описан в [41], а в [47] работа этого алгоритма показана на примере. [c.158]
Существует много частных способов (например, способ Фогеля, методы потенциалов, дифференциальных рент, способ Лебедева — Тихомирова, венгерский метод и др.), а также универсальных методов (например, алгоритм симплекс-метода) решения задач линейного программирования с такого рода условиями. Представляет интерес, как сам результат вычисления, так и его интерпретация. [c.246]
Первый вариант — отсутствие складов. В этом случае решается классическая транспортная задача закрепления п потребителей за т поставщиками. Расстояние между объектами определяется как корень квадратный из суммы квадратов разностей их координат, см. формулу (11.9). Для распределения объемов перевозок используется ускоренный алгоритм Фогеля с последующим поиском оптимального варианта — минимума транспортной работы методом потенциалов. [c.398]
Для решения подобных задач рассмотренный ранее метод потенциалов непригоден. Эти задачи решаются с помощью специального алгоритма. [c.292]
В описанном алгоритме, как и в случае с матричной транспортной задачей, мы не гарантированы от возникновения вырожденного потока. Как уже упоминалось выше, такому потоку будет соответствовать несвязная опора. Для преодоления вырожденности рекомендуется включить в текущий план фиктивные компоненты с нулевыми объемами так, чтобы соответствующие им дуги дополняли опору до остова сети. Построенный таким способом план позволяет выполнить все действия, входящие в стандартную итерацию метода потенциалов. [c.127]
Существующий алгоритм решения транспортных задач (метод потенциалов) предполагает, что ЦФ стремится к минимуму. Однако существуют ситуации, когда в рамках транспортной модели требуется максимизировать ЦФ, например, общий доход, объем продаж, прибыль, качество выполняемых работ и т.д. В этом случае в модель вместо искомой ЦФ L(X) вводится ЦФ LI(X)=-L(X), в которой тарифы умножаются на (-1). [c.64]
Для построения оптимального плана перевозок используется метод потенциалов, который является формой симплекс-алгоритма. [c.62]
Первым этапом этого алгоритма является начальное распределение (составление начального плана перевозок). Для этого имеется ряд методов северо-западного угла, наименьших стоимостей, аппроксимаций Фогеля и др. Второй этап — построение системы потенциалов на основе равенства (25.33), а третий — проверка начального плана на оптимальность, причем в случае его неоптимальности переходят к четвертому этапу, содержание которого заключается в реализации так называемых циклов перераспределения плана прикрепления потребителей к поставщикам, после чего переходят опять к третьему этапу. Совокупность процедур четвертого и третьего этапов образует одну итерацию, и эти итерации повторяются, пока план перевозок не окажется оптимальным по критерию (25.29) [c.526]
Алгоритм метода потенциалов для закрытой транспортной задачи детально описан в ряде учебных пособий1. [c.526]
Алгоритм метода потенциалов для транспортной задачи. Критерий (3.8)-(3.9) положен в основу однюго из методов решений транспортной задачи, получившего название метода потенциалов. Впервые он был предложен в 1949г. Л. В. Канторовичем и М. К. Гавуриным. Позже на базе общих идей линейного программирования аналогичный метод был предложен Дж. Данцигом. [c.115]
Помимо алгоритма метода потенциалов существуют некоторые его разновидности. Так, в иностранной литературе как указано выше, широко известен метод МОДИ (модифицированный распределительный метод). В СССР этот метод многие экономисты именуют методом коэффициентов. Отличие этого метода заключается в способе расчета коэффициентов. [c.218]
Некоторые из них не связаны непосредственно с алгоритмом симплексного метода, как, например, метод потенциалов для решения транспортной задачи другие же в качестве составных элементов используют вычислительные процедуры симплексного метода. В качестве примера последних можно привести метод Гомори (метод отсечений) для решения задач линейного целочисленного программирования. [c.524]
Во-вторых, специфика зависимости величины минимума расхода электроэнергии на перекачку от ее объема (в соответствии с принципом 1 это и отображено в критерии оптимальности) такова, что эта зависимость выражается кусочно-линейной выпуклой (вниз) функцией. Это позволило построить точный, быстро сходящийся алгоритм решения задачи, являющейся обобщением метода потенциалов решения сетевой транспортной задачи линейного программирования (СТЗ ЛП) для случая кусочно-линейного выпуклого функционала [41, 47]. Для построения экономико-математической модели задачи введем обозначения г — номер вершины сети 3 (г, s) —дуга сети между вершинами г и s R(E) — множество вершин (дуг) сети Rir(R r< R) [R2t(R2r z zR) подмножество вершин сети, из которых выходят дуги, входящие в r-ю вершину (в которые входят дуги, выходящие из г-й вершины) ur(vr) — объем поступления (потребления) нефти в r-й вершине за плановый период . х — объем перекачки нефти по дуге (г, s) за плановый период ars(Prs) — нижний (верхний) предел значений xrs frs(xrs) — функция зависимости расхода электроэнергии от объема перекачки для дуги (г, s). [c.156]
Завершая разговор о методе потенциалов, следует отдельно остановиться на ситуации возникновения вырожденного плана. Возможность получения вырожденного плана уже отмечалась при описании метода северо-западного угла. Нетрудно заметить, что вырожденный план также может получиться на этапе преобразования текущего плана по цепочке если одинаковое минимальное значение будет достигнуто сразу на нескольких клетках, помеченных знаком — , то при вычитании перемещаемого по цепочке объема в новом плане будет меньше чем т+n-l ненулевых компонент. Способ преодоления вырожденности в транспортной задаче весьма прост, а именно предлагается дополнить текущий план необходимым количеством нулевых клеток (фиктивными перевозками) таким образом, чтобы они позволяли рассчитать полную систему потенциалов, и далее действовать в соответствии с правилами описанного выше алгоритма. Фактически здесь мы имеем дело не с чем иным, как с аналогом метода возмущений для транспортной задачи как частного случая ЗЛП. К taKOMy выводу легко прийти, если положить, что добавляемые фиктивные клетки содержат некоторый малый объем 8. [c.120]
Алгоритм начинается с выбора некоторого допустимого базисного плана (методы его построения были рассмотрены в п. 3.1.2). Если данный план не вырожденный, то он содержит т + п-1 ненулевых базисных клеток, и по нему можно так определить потенциалы щ и v-, чтобы для каждой базисной клетки (т. е. для той, в которой xitj > 0) выполнялось условие [c.115]
Смотреть страницы где упоминается термин Алгоритм метода потенциалов
: [c.273]Смотреть главы в:
Математические методы моделирования экономических систем Изд2 -> Алгоритм метода потенциалов