Материал, изложенный в данном параграфе, дает лишь общее представление о решении транспортных задач методом потенциалов. Подробное изложение этого метода дано, например, в [28]. [c.191]
Алгоритм решения транспортной задачи методом потенциалов. [c.75]
Существующий алгоритм решения транспортных задач (метод потенциалов) предполагает, что ЦФ стремится к минимуму. Однако существуют ситуации, когда в рамках транспортной модели требуется максимизировать ЦФ, например, общий доход, объем продаж, прибыль, качество выполняемых работ и т.д. В этом случае в модель вместо искомой ЦФ L(X) вводится ЦФ LI(X)=-L(X), в которой тарифы умножаются на (-1). [c.64]
Если баланс (25.32) не выполняется, то ограничения (25.30) или (25.31) имеют вид неравенств типа меньше или равно транспортная задача в таком случае называется открытой. Для решения открытой транспортной задачи методом потенциалов ее сводят к закрытой задаче путем ввода или фиктивного потребителя, если в неравенства превращаются условия (25.30), или фиктивного поставщика в случае превращения в неравенства ограничений (25.31). [c.526]
Решение транспортной задачи на сети осуществляется также в два этапа сначала составляется начальный вариант прикрепления, а затем обычно методом потенциалов находится оптимальный план. [c.148]
Одним из известных методов решения транспортной задачи является метод потенциалов [3]. [c.176]
Наиболее распространенным методом решения транспортных задач является метод потенциалов. [c.272]
Для решения транспортной задачи в сетевой постановке (3.15)—(3.17) также может быть применен метод потенциалов, который является обобщением описанного выше метода потенциалов для транспортной задачи в матричной постановке. [c.125]
Для решения транспортной задачи в матричной форме существуют различные методы (потенциалов, дифференциальных рент, разрешающих слагаемых). [c.202]
Перечисленные методы, наиболее часто используемые для решения транспортных задач, основаны на принципах 1) последовательного улучшения плана (потенциалов) 2) последовательного сокращения невязок, именуемых также методами условно-оптимальных планов (дифференциальных рент, разрешаемых слагаемых). [c.202]
Соответствующая задача сводится к сетевой транспортной задаче с дополнительными ограничениями (,СТЗ ДО), где условия СТЗ полностью определяются сетью (графом) задачи, а дополнительные ограничения формируются по информации о связующих дугах. При этом число дополнительных ограничений равно (А —1)7, где / — число цепочек в (7 + 1)-й подсети. Для решения возникающей задачи могут быть использованы специальные алгоритмы и программы решения СТЗ ДО. Следует подчеркнуть, что в этих алгоритмах существенно используется структура матрицы СТЗ ДО, т. е. на каждой итерации операции преобразования обратной матрицы строятся в соответствии с методом потенциалов решения СТЗ. [c.70]
Необходимо разработать такой план распределения машин по объектам, при котором суммарное время простоя техники окажется наименьшим. Это будет так называемая транспортная задача математического программирования. Одним из наиболее распространенных методов решения подобных задач является метод потенциалов. Прежде всего составляем исходный план распределения машин по объектам. [c.78]
В настоящее время разработано множество различных алгоритмов решения Т.з. распределительный метод, метод потенциалов, дельта-метод, венгерский метод, метод дифференциальных рент, способ двойного предпочтения, различные сетевые методы. Они относительно просты, по ним составлены десятки программ для различных вычислительных машин. Во многих снабженческих, транспортных и других организациях во всем мире с их помощью рассчитываются маршруты доставки материалов на строительные площадки, планы длительного прикрепления поставщиков металлопроката к потребителям, планы перевозок топлива. Задачи эти часто усложняются разного рода дополнительными условиями напр., в них включается расчет не только себестоимости перевозок, но и себестоимости производства продукции (производственно-транспортная задача), оптимизируется совместно доставка взаимозаменяемых видов продукции (скажем, различных кровельных материалов), оптимизируется доставка грузов с промежуточными базами (складами). Кроме того, следует учитывать, что экономико-математическая модель Т.з. позволяет описывать множество ситуаций, весьма далеких от проблемы перевозок, в частности, находить оптимальное размещение заказов на производство изделий с разной себестоимостью. [c.367]
Для решения задач транспортного типа наиболее удобен метод потенциалов, Представляющий собой упрощенную модификацию симплексного метода. Алгоритм метода потенциалов рассматривается на следующем примере. [c.138]
Модель (1) — (4) и ее конкретная реализация (5) — (15) — есть классическая транспортная задача линейного программирования. Найдем численное решение задачи (5) — (15) методом потенциалов. [c.254]
Различия между транспортными задачами в матричной и сетевой формах весьма незначительны, так как методы их решения основаны на одних и тех же идеях (метод потенциалов). [c.289]
Оказывается, для того, чтобы решить маршрутную задачу с помощью транспортной модели, нужно принять в качестве однородного груза... пустые вагоны, направляемые от пункта выгрузки к пунктам погрузки. Полученное распределение, которое без труда находится на основе транспортной задачи, и дает решение задачи об оптимальной маршрутизации, так как оно определяет пути следования вагонов. Практическое применение транспортной задачи для решения задач оптимальной маршрутизации получило особенное распространение на автотранспорте. В ряде крупных городов производится ежедневный расчет рациональных маршрутов на ЭВМ и на их основе пишутся наряды для значительного процента автомашин. В некоторых небольших автохозяйствах эту методику хорошо освоили и регулярно используют сами диспетчеры. Это позволяет в ряде случаев снижать холостой пробег на 20—40%. Об эффекте ее применения убедительно свидетельствует и такой любопытный факт. В одном автохозяйстве, где проводился эксперимент по введению наилучшей маршрутизации транспорта, шоферы, ездившие по оптимальным маршрутам, найденным с помощью метода. потенциалов, имели на своих машинах отличительные флажки. Через несколько дней после начала эксперимента шоферы наглухо припаяли флажки к машинам, так как они стремились и впредь получать математические наряды. Большая эффективность работы этих машин была выгодна не только для автохозяйства в целом, но и для каждого и,з водителей. [c.43]
Идея этого метода заключается в том, что вместо решения задачи с тп неизвестными отыскивают т + п — 1 неизвестных, называемых разрешающими множителями и обозначаемыми Хь Х2,. .., X,-, которые имеют такое же значение, как в транспортной задаче потенциалы. [c.268]
Решение транспортных задач методом потенциалов. Продемонстрируем метод решения транспортных задач в сетевой постановке, так называемый метод потенциалов. Он был предложен Л. В. Канторовичем в начале сороковых годов п является первым методом решения транспортных задач. Интересно отметить, что метод с самого начала предназначался для решения транспортных задач в сетевой постановке и только впоследствии был преобразован к матричной форме. Метод потенциалов является одним из способов реализации общего принципа решения задач линейного программирования — принципа последовательного улучшения плана, о котором мы уже говорили в 4 гл. 1. [c.189]
Проверка оптимальности решения транспортной задачи методом потенциалов. Идея метода потенциалов для решения транспортной задачи сводится к следующему. Представим себе, что каждый из поставщиков Z, вносит за перевозку единицы груза какую-то сумму Z, в свою очередь каждый из потребителей YJ также вносит за перевозку груза сумму YJ. Эти платежи передаются некоему третьему лицу (перевозчику). Обозначим Z,+ Yj = K,j(i = l...m j= 1... n) и будем называть величину Ки псевдостоимостью перевозки единицы груза от Z, к YJ. Заметим, что платежи Z, и Y не обязательно должны быть положительными не исключено, что перевозчик сам платит тому или другому пункту какую-то премию за перевозку. Также надо отметить, что суммарная псевдостоимость любого допустимого плана перевозок при заданных платежах (Z, и YJ, ) одна и та же и от плана к плану не меняется. [c.269]
Некоторые из них не связаны непосредственно с алгоритмом симплексного метода, как, например, метод потенциалов для решения транспортной задачи другие же в качестве составных элементов используют вычислительные процедуры симплексного метода. В качестве примера последних можно привести метод Гомори (метод отсечений) для решения задач линейного целочисленного программирования. [c.524]
В настоящее время разработано много методов решения транспортной задачи в матричной форме1. Рассмотрим решение методом потенциалов. Оно осуществляется в два этапа. На первом разрабатывается начальный вариант прикрепления, а на втором — точное решение задачи. [c.141]
Метод потенциалов (8.1.) —метод решения транспортной задачи, основанный на построении специальных характеристик-потенциалов. Необходимым и достаточным условем оптимального плана является его потенциальность. [c.344]
В пятом блоке, если при перевозке груза используется схема многие ко многим , решается транспортная задача. Для решения транспортной задачи широко применяется распределительный метод, который имеет несколько разновидностей, отличающихся в основном способом выявления оптимального решения. Наиболее известны три метода решения задач данного типа метод Хичкова метод Креко модифицированный распределительный метод, или метод потенциалов. [c.333]
Алгоритм метода потенциалов для транспортной задачи. Критерий (3.8)-(3.9) положен в основу однюго из методов решений транспортной задачи, получившего название метода потенциалов. Впервые он был предложен в 1949г. Л. В. Канторовичем и М. К. Гавуриным. Позже на базе общих идей линейного программирования аналогичный метод был предложен Дж. Данцигом. [c.115]
Необходимо также отметить, что ни в работах А. Н. Толстого, ни у Хичкока не было дано законченного метода решения рассматриваемой задачи. Первый общий метод решения транспортной задачи, получивший в дальнейшем название метода потенциалов , предложен ныне академиком Л. В. Канторовичем и опубликован в 1949 году, хотя разработан был им еще в 1941 г. [c.194]
Метод потенциалов — один из наиболее распространенных методов решения транспортной задачи. В США этот метод называют модифицированным распределительным методом, или сокращенно МОДИ. Некоторое различие между этими методами заключается в том, что вместо разности потенциалов, с которыми оперируют в методе потенциалов, принимают в методе ЛЮДИ их сумму. [c.207]
Во-вторых, специфика зависимости величины минимума расхода электроэнергии на перекачку от ее объема (в соответствии с принципом 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]
КАНТОРОВИЧ Леонид Витальевич (р.6.1.1912), советский математик и экономист, акад. АН СССР (1964 чл.-корр. 1958). Окончил Ленингр. гос. ун-т (1930). В 1930—39 работал в Ленингр. ин-те инженеров пром. строительства в 1934—60 проф. Ленингр. гос. ун-та в 1939—48 нач. кафедры Высшего инжеперно-технич. училища в 1945—60 ст. научный сотрудник, зав. отделом Ленингр. отделения математич. ин-та АН СССР и 1960—71 зам. директора, зав. математико-экономич. отделением Ин-та математики Сиб. отделения АН СССР. С 1971 зав. проблемной лабораторией Ин-та управления нар. х-вом Госкомитета по науке и технике СССР. Опубликовал начиная с 1929 большое число работ по различным областям математики и её приложений теории множеств, теории функций, функционального анализа (теория полуупорядоченных — К-пространств), приближённым методам анализа, вычислит, математике и технике. Работы К. положили начало новому разделу математики — линейному программированию и его обобщениям. Общие принципы линейного программирования изложены им в книге Математические методы организации и планирования производства (Л., 1939), дан универсальный метод их решения, а также указаны осн. типы экономич. задач, к к-рым приложимы линейно-программные модели. В частности, в его работах (1940—49) решены т. н. транспортная задача и метод потенциалов для неё. Результаты исследовании К. оставались неизвестными за рубежом и были повторены в кон. 40-х гг. амер. учёными (Т. Купманс, Дж. Данциг). В наст, время приоритет сов. науки, и в частности К., в разработке осн. принципов линейного программирования признан и за рубежом. [c.95]
Смотреть страницы где упоминается термин Решение транспортной задачи методом потенциалов
: [c.26] [c.270]Смотреть главы в:
Справочник по математике для экономистов -> Решение транспортной задачи методом потенциалов