Оставляем в транспортной сети только дуги (i, j), такие что j < bj и определяем максимальный поток в сети при ограничении [c.54]
Максимальные потоки в сети [c.266]
Теперь рассмотрим один важный частный случай линей" ной задачи на сети — так называемую задачу о максимальном потоке. Пусть в транспортной сети есть единственный пункт производства и единственный пункт потребления, соединенные между собой транспортной сетью проходящей через другие пункты, или, как принято говорить, узлы, в которых нет ни потребления, ни производства продукта (т. е. они являются перевалочными). Такую сеть можно интерпретировать, например, как сеть нефтепроводов, соединяющих место добычи нефти с местом ее переработки, или как систему линий электропередач, связывающих электростанцию с потребителем. Пункт производства часто называют источником, а пункт потребления — стоком. Подчеркнем, что, в отличие от сети, изображенной на рис. 16, здесь отрезки, соединяющие узлы магистрали, имеют направление. В этом случае множество A (k) отрезков, приходящих в узел k, не совпадает с множеством В (К) отрезков, выходящих из этого узла. [c.162]
В задаче о максимальном потоке мощность источника v, равная потреблению в пункте потребления, не считается заданной. Наоборот, в задачах такого типа требуется максимизировать величину v исходя из возможностей транспортной сети, передать все произведенное количество груза потребителю. [c.162]
Задача о максимальном потоке. Теперь рассмотрим один важ ный случай линейной задачи на сети — так называемую задачу о максимальном потоке. Пусть в транспортной сети есть всего один пункт производства и единственный пункт потребления, соединенные между собой транспортной сетью, проходящей через [c.188]
В задаче о максимальном потоке мощность источника г , равная спросу в пункте потребления, не считается заданной. Наоборот, в задачах такого типа требуется максимизировать величину у для заданной транспортной сети. [c.188]
Примерно в одно и то же время были разработаны две совершенно различные схемы уменьшения интенсивности транспортных потоков в Нью-Йорке и Лондоне. Для Нью-Йорка такая схема предусматривала установку на улицах города электронных датчиков. Подобные устройства должны были считывать номера, записанные на магнитном носителе, установленном на боковой части автомобиля, и передавать их в центральную вычислительную машину. Накапливая такие данные, машина использовала их для подготовки счетов, предъявляемых владельцам автомобилей за проезд по городу при этом размер платы должен зависеть от времени считывания номера— дня недели и времени.суток. Плата должна была достигать максимальной величины при поездках в часы наибольшей нагрузки транспортной сети. Предполагалось, что таким способом можно уменьшить интенсивность движения автомобилей в часы пик. Однако подобная система датчиков, средств связи и вычислительных устройств оказалась слишком сложной и дорогой. [c.65]
Этим же методом решена задача для Северо-Западного экономического района. Система газопроводов этого района была отражена сетью, включающей 42 дуги, 14 вершин — потребителей и 1 пункт поступления газа в систему. В задаче рассмотрена также работа шести подземных газохранилищ (ПХГ), в связи с чем рассмотрены три периода зимний — период максимального потребления газа (в этот период проводится отбор газа из ПХГ) летний — период минимального потребления газа (в этот период газ закачивается в ПХГ) межсезонный — период среднего потребления газа (в этот период работа ПХГ не учитывалась). Для каждого такого периода по результатам полученных на основе метода Монте-Карло 40 сочетаний возможных значений случайных параметров получены четыре варианта состояний природы . Таким образом, для указанного района было получено 12 вариантов развития системы газоснабжения. Выбирая максимальные потоки газа, всю указанную совокупность вариантов свели к четырем конечным. В дальнейшем рассмотрение периода последствия и построение итоговой платежной матрицы проводилось для этих четырех вариантов. Результатом выполнения всех численных расчетов в задаче явились совокупность эффективных вариантов развития системы на первый этап планового периода и платежная матрица в нескольких вариантах. [c.153]
Берем F = 6. В таблице 3.10 знаком (оо) указаны запрещенные клетки. Определяем поток максимальной величины в соответствующей транспортной сети. Единичные потоки по дугам отмечены в таблице 3.10. [c.55]
В итоге банк сможет удовлетворить комплексные потребности своих клиентов, построить комплексную систему обслуживания каждого из них, заработать имидж высокотехнологичного кредитного учреждения, обеспечить большую массу доходов от продажи связанных услуг одному клиенту (технологически связанным группам клиентов). Такая система позволяет банку сконцентрировать максимальное количество денежных и сопряженных с ними потоков клиента на банк и обеспечить свою клиентуру сетью взаимосвязанных услуг банка, чтобы у клиентов не возникало возможности перевода части своих денежных потоков в другие банки. Для этого необходимо создать координирую- [c.415]
Современные тенденции в развитии деятельности КФР заключаются в попытках захватить как можно больший контроль над материальными потоками, обеспечив тем самым максимальную прибыль компании. Это проявляется, например, в специализации снабжения и сбыта и контроле всей распределительной сети по отдельному виду продукции или в захвате рынка транспортных услуг по продвижению определенной номенклатуры грузов в территориальной зоне. При этом КФР, как правило, не являясь владельцами товаров, берут на себя только часть финансового риска, связанного сдвижением, хранением и обработкой товаров по распределительному каналу (или сети). [c.206]
Одно из основных правил логистики в физическом распределении заключается в перевозке на максимально возможное расстояние и с наибольшей частотой укрупненных продуктовых или транспортных единиц. Для достижения этой цели до конца логистической цепи необходимо консолидировать насколько это возможно все различные предметы материального потока, направляемого к конечной точке этой цепи. Примерами такой консолидации являются сортировочные станции в железнодорожных перевозках и грузовые терминалы — в автомобильных. На протяжении всей логистической сети внешней или интегрированной логистической системы должна быть обеспечена связанность и непрерывность материального потока независимо от единиц измерения продукта или транспортных единиц, участвующих в перемещении. [c.207]
Данные о потоках сообщений, поступающих на вход системы связи, являются необходимым условием для правильного определения объема технических средств связи, а в более широком плане — для создания и развития систем связи и составляющих их элементов. Этот процесс осуществляется непрерывно и носит циклический характер. Это объясняется тем, что непрерывное развитие промышленного производства, информационных сфер деятельности (банки, посредничество, адвокатура и т.д.), увеличение спроса со стороны населения требует как расширения сети путем строительства новых объектов, так и совершенствования технологии производства услуг, в том числе новых. При этом особенностью связи является строительство объектов, производственные мощности которых рассчитаны на достаточно длительную перспективу и постепенно осваиваются в соответствии с нормами, зависящими от типа объектов. При этом под производственными мощностями понимается максимально возможный объем услуг (пропущенного трафика, каналов, трактов, точек коммутации), которые можно предоставить при имеющихся у предприятия оборудовании, площадях и производственном персонале. [c.148]
Комплексная корпоративная стратегия требует [2] координированных действий. К сожалению, трудно ожидать, чтобы элементы корпорации сами по себе действовали в соответствии с общими целями. На это имеются объективные причины. Каждая коммерческая корпорация существует в связи с некоторым производственным процессом, который как можно долго обеспечивает непрерывный выход с максимальной эффективностью и, в большинстве случаев, с максимальной интенсивностью. Этот основной процесс объединяет как непосредственное производство, так и управление. Управление имеет иерархическую структуру, в то время как производство (технология) обычно потоками материалов структурируется в виде сетей. [c.161]
При рассмотрении задачи оптимального оперативного управления перевозками возникает естественный вопрос нельзя ли воспользоваться для решения задачи методами теории графов Действительно, попытки применения методов потоков на сетях для решения задачи оперативного управления нефтеснабжением делались, например, в работе [56]. Однако основные, наиболее разработанные и эффективные методы теории сетей, методы максимального потока в сетях с ограниченной пропускной способностью дуг или узлов направлены на решение проблемы максимальным -образом использовать пропускную способность сети. В задаче оперативного управления перевозкими нефтепродуктов это отвечало бы цели максимально возможного и наибыстрейшего вывоза нефтепродуктов от источников в пункты потребления. [c.101]
Для выбора баз сезонного хранения нефтепродуктов с учетом динамики потребления использовалась модель при упрощающих предположениях. Для ее решения разработан эвристический метод, базирующийся на многократном нахождении максимального потока в сети специальной структуры в сочета- [c.59]
Изложенная модель сводится к классической задаче о максимальном потоке в сетях. Первоначально для решения такой модели ОДМ применялся специально разработанный для задач о максимальном потоке алгоритм Форда-Фалкерсона [53,1]. В дальнейшем модель ОДМ реализовывалась с использованием метода внутренних точек [36], который оказался особенно уместным в связи с необходимостью решения дополнительной проблемы - пропорционального нагрузкам распределения дефицита мощности по узлам. [c.133]
Смотреть страницы где упоминается термин Максимальные потоки в сети
: [c.377] [c.25] [c.112] [c.46] [c.276] [c.104] [c.40]Смотреть главы в:
Справочник по математике для экономистов -> Максимальные потоки в сети