Фаза регулирования. Здесь решаются функциональные задачи (рис.7.7) календарного планирования и диспетчирования производства, т. е. на основе информации и принятых решений в фазе анализа происходит оперативное воздействие на параметры производственного процесса. Для формального описания задач регулирования привлекаются методы и модели календарного и сетевого планирования, транспортные модели и модели оперативного управления. Результатной информацией этой фазы являются календарные и сетевые графики производства продукции, маршруты, алгоритмы диспетчирования. [c.273]
В качестве критерия оптимальности в большинстве отраслевых задач выступает минимум затрат на заданный объем конечного продукта рассматриваемой производственной системы. Применяются экономико-математические модели разных типов динамические и статические, детерминированные и вероятностные, однопродуктовые и многопродуктовые, с дискретными и непрерывными переменными, производственные функции, производственно-транспортные задачи и, наконец, по характеру отображения хозяйственных связей —матричные и сетевые модели. [c.253]
В настоящее время разработано множество различных алгоритмов решения Т.з. распределительный метод, метод потенциалов, дельта-метод, венгерский метод, метод дифференциальных рент, способ двойного предпочтения, различные сетевые методы. Они относительно просты, по ним составлены десятки программ для различных вычислительных машин. Во многих снабженческих, транспортных и других организациях во всем мире с их помощью рассчитываются маршруты доставки материалов на строительные площадки, планы длительного прикрепления поставщиков металлопроката к потребителям, планы перевозок топлива. Задачи эти часто усложняются разного рода дополнительными условиями напр., в них включается расчет не только себестоимости перевозок, но и себестоимости производства продукции (производственно-транспортная задача), оптимизируется совместно доставка взаимозаменяемых видов продукции (скажем, различных кровельных материалов), оптимизируется доставка грузов с промежуточными базами (складами). Кроме того, следует учитывать, что экономико-математическая модель Т.з. позволяет описывать множество ситуаций, весьма далеких от проблемы перевозок, в частности, находить оптимальное размещение заказов на производство изделий с разной себестоимостью. [c.367]
Необходимость в таком предварительном этапе отпадает при сетевой постановке задачи, так как транспортная сеть непосредственно моделируется в задаче с помощью аппарата теории графов. Каждая вершина графа соответствует поставщику, потребителю или транзитному пункту, каждая дуга — участку транспортной сети. Решение задачи в сетевой постановке позволяет выбрать в увязке с многими показателями и оптимальные маршруты перевозки для каждой пары поставщик—потребитель . [c.144]
Различия между транспортными задачами в матричной и сетевой формах весьма незначительны, так как методы их решения основаны на одних и тех же идеях (метод потенциалов). [c.289]
Первая подсистема состоит из комплекса взаимосвязанных программ перспективного и годового планирования работ, почасовых монтажно-транспортных графиков, используемых для организации работы строительных предприятий, транспорта и монтажа зданий и др. Во второй подсистеме заложены задачи контроля за монтажом зданий и сооружений, работой баз снабжения и транспорта с учетом часовых и суточных графиков доставки и монтажа деталей, транспортировки комплектов материалов, контроля и анализа выполнения сетевых и поточных графиков производства работ. [c.175]
Транспортные задачи в сетевой постановке. Теперь попытаемся подойти к задаче перевозки грузов с несколько отличных позиций. Описанный ранее способ формулировки задачи перевозки состоял в том, что считалась возможной перевозка грузов из каждого пункта-отправителя в каждый из пунктов-потребителей я была известна матрица с ц удельных затрат на эти перевозки. При таком представлении каждый из пунктов-отправителей связан с пунктом-потребителем отдельной дорогой с характерными именно для нее затратами перевозки. Если же взглянуть на карту местности, на которой расположены интересующие нас пункты, то можно увидеть, что дороги соединяют большинство пунктов друг с другом не непосредственно, а проходят через другие пункты. Более того, груз из одного пункта в другой возможно провезти несколькими путями. Поэтому часто задачу перевозки грузов формулируют не в матричной постановке, как принято называть подход, описанный ранее в этом параграфе, а в так называемой сетевой постановке, основывающейся на явном представлении структуры транспортной сети. Очень простая транспортная сеть приведена на рис. 3.2, а. Внутри каждого кружка римской цифрой изображен номер этого пункта (в сетевых постановках пункты нумеруются без разделения на поставщиков и потребителей). Второе число означает мощность или спрос в этом пункте. В случае мощности перед числом стоит знак плюс, в случае спроса — минус. Около отрезков, связывающих кружки, поставлены числа, указывающие расстояние между пунктами или затраты на перевозку единицы груза по дороге между пунктами, которые эта дорога соединяет. На рисунке размеры отрезков могут не быть пропорциональны числам, стоящим около них. [c.185]
По-видимому, на все вместе. Но, с другой стороны, если возможности дороги между пунктами IV и V будут исчерпаны, то часть грузов можно будет перевозить по другим дорогам. Однако при. этом изменится величина затрат при перевозке единицы груза, так что в матричной постановке величина с,-3- окажется зависимой от Xtj и задача станет нелинейной. Хотя все эти трудности перехода к матричной постановке задачи перевозки грузов все-таки можно преодолеть при помощи разнообразных искусственных приемов, многие исследователи предпочитают решать задачи в сетевой постановке, не переходя к матричной. Алгоритмы решения транспортной задачи были преобразованы к форме, пригодной для решения задач на сети. Сформулируем транспортную задачу в сетевой постановке в математической форме. [c.187]
Функции, выполняемые протоколами уровней в различных системах, принято объединять в группы, именуемые службами. Транспортная служба обеспечивает выполнение задач, связанных с передачей информации через (сквозь) коммуникационную подсеть. Она охватывает транспортный, сетевой, канальный и физический уровни. Над ней находится абонентская служба. Эта служба располагается на прикладном, представительном и сеансовом уровнях и предназначена для обеспечения соединения прикладных процессов с транспортной службой. [c.175]
В этом случае задача ставится как сетевая транспортная, т. е. ее условия моделируются специальным графом или сетью. Принципы построения этой сети следующие. Выделяется ц -й вид транспорта, отражающий трубопроводный или другой подобный ему (с точки зрения принятых в задаче условий) транспорт. Сама сеть распадается на ( + ) подсеть, где R — число рассматриваемых продуктов. Каждая из первых 7 подсетей соответствует одному из продуктов и отражает процесс транспортировки этого продукта всеми видами транспорта (кроме ц -го) от пунктов отправления к пунктам потребления, включая перевалку этого продукта с одного вида транспорта. на другой. Последняя (7 +1)-я подсеть отображает возможность перевозки [c.69]
Соответствующая задача сводится к сетевой транспортной задаче с дополнительными ограничениями (,СТЗ ДО), где условия СТЗ полностью определяются сетью (графом) задачи, а дополнительные ограничения формируются по информации о связующих дугах. При этом число дополнительных ограничений равно (А —1)7, где / — число цепочек в (7 + 1)-й подсети. Для решения возникающей задачи могут быть использованы специальные алгоритмы и программы решения СТЗ ДО. Следует подчеркнуть, что в этих алгоритмах существенно используется структура матрицы СТЗ ДО, т. е. на каждой итерации операции преобразования обратной матрицы строятся в соответствии с методом потенциалов решения СТЗ. [c.70]
СПУ основаны на теории графов. При помощи теории графов можно решать не только задачи сетевого планирования, но и различные экстремальные задачи о размещении денежных средств, развитии транспортной сети, о перевозках и др. [c.143]
Такие задачи математически бывают представлены в двух видах в сетевой и в матричной постановке. Будучи основанными на принципах транспортной задачи линейного программирования, они очень сложны и решаются специальными, обычно многостадийными приемами с использованием эвристических элементов. [c.290]
Был предложен способ моделирования условий (6.3) — (6.8) и соответствующего линейного функционала как некоторой сетевой транспортной задачи (СТЗ). При этом условия (6.9) и (6.10) рассматривались как линейные дополнительные ограничения более общего вида на переменные, моделируемые в рамках этой СТЗ как потоки на дугах соответствующей сети. Предложенный способ моделирования позволил все рассматриваемые этапные подзадачи свести к линейным сетевым транспортным задачам, для решения которых известны алгоритмы, позволяющие достаточно быстро решать задачи большой размерности. [c.147]
При этом для каждого СП формируются и решаются сетевые транспортные задачи линейного программирования, подобные этапным задачам в детерминированном методе. Такая задача для каждого СП может решаться дважды — до и после проверки на реалистичность полученного при этом условно-оптимального плана. Если эта проверка показала плохое использование в этом плане некоторых существующих ГП, то в условия данной задачи вводятся дополнительные ограничения на величину соответствующих потоков. В результате нового решения задачи определяется реальный условно-оптимальный план, который и учитывается в дальнейшем при формировании зоны неопределенности . Все эти планы могут дополнительно группироваться с целью получения набора альтернативных вариантов развития ГСС, образующих зону неопределенности . Такая группировка может [c.152]
В экономике наиболее широко используются модели межотраслевого баланса статистические и динамические модели оптимального планирования народного хозяйства транспортной задачи размещения производства оптимального распределения выпускаемой продукции ассортимента продукции регулирования запасов сырья, материалов и готовой продукции выбора обслуживающих устройств в системах массового обслуживания, а также сетевые модели. Б. С. Бушуев. [c.107]
Экономико-математическая модель задачи в сетевой форме. После нанесения на сеть исходной информации все транспортные пункты будут разбиты на три категории отправления, назначения и свободные (т. е. не отправляющие и не получающие данный груз). Переменными при решении задачи являются xrs, т. е. размеры перевозок по каждому звену. [c.147]
Решение возникающей задачи может быть осуществлено при помощи алгоритмов решения СТЗ ДО (однако их применение требует дополнительного обеспечения специальными приемами связности графа задачи) и алгоритмов, учитывающих блочный характер матрицы СТЗ. В статье [12] рассмотрены соответствующие модификации алгоритма К. В. Кима и известного метода декомпозиции. Вычислительные аспекты рассмотренных сетевых задач обсуждаются в статье [16]. В частности, соответствующие графы могут иметь большую размерность вследствие многократного дублирования (по числу продуктов) вершин и дуг исходной транспортной сети, однако на практике существует возможность существенного уменьшения этой размерности. В статье даются сравнительные оценки этих моделей для случая, когда возможно применение их обеих. Результаты весьма огра--ниченного эксперимента показали некоторую предпочтительность более частной модели. [c.71]
При планировании развития и размещения производства применяются экономико-математические задачи разных типов. Это зависит от специфики оптимизируемой отрасли, условий информационного обеспечения, а также накопленного исследовательскими и проектными учреждениями опыта. В частности, применяются задачи динамические н статические, детерминированное и вероятностные, однопродук-j тоаые и многопродуктовые, задачи с I дискретными и непрерывными пере- мецными, производственные и производственно - транспортные и, нако-I ней,, — по характеру отображения хо- зяйствеиных связен — матричные и сетевые. [c.100]
Рост масштабов и сложности задач управления, повсеместное внедрение принципа разделения труда и вытекающего из него принципа делегирования части полномочий по принятию решений исполнителям (принцип неокончательности и свободы принятия решений) со временем потребовали решительного снижения ошибок в выборе наилучшего решения. Это, в свою очередь, привело к необходимости обобщить опыт и знания, предложить теорию, которая их превратила бы в стройную систему научных взглядов на управление и разработку решений. Родилась парадигма "рациональных решений". Принципы, заложенные в парадигму рациональных решений, предполагают прежде всего моделирование реальной ситуации, т. е. представление ее в упрощенном для изучения виде с сохранением всех значимых характеристик и связей. После моделирования ситуации моделируют цель, формируя и измеряя требуемые результаты. Это расчленило процесс на более простые фазы, позволило распараллелить работы по разработке решений, на порядок снизить ошибки в принятии решения. Парадигма "рациональных решений" по мере своего развития претерпела ряд изменений. Вначале она делала акцент на использование чисто формальных методов, основанных на "физических измерениях". При этом родились такие классические постановки задач и методы исследования операций, как "транспортная задача", "задача массового обслуживания", "задачи сетевого планирования", "управления запасами", "задача о назначении" и др. Правда, перечисленные формальные задачи и методы не всегда оказывались хорошо приспособлены к практическим делам. Это зачастую приводило к нелепостям и разочарованиям. Самые большие неудачи этой науки связаны с пробле- [c.65]
Основная задача транспортных сетей заключается в переносе информационных потоков между различными объектами (узлами сети). Сети доступа обеспечивают индивидуальную доставку информационных потоков на терминальное оборудование конкретных пользователей, т.е. передачу информации между интерфейсом узла, предоставляющего услуги, и сетевым интерфейсом каждого пользователя. Понятие доступа и сети доступа весьма многозначно и может определять как характеристики сетей или оборудования, так и места подключения средств связи, а также вызов данных из памяти компьютеров и пр. Совокупность транспортных сетей и сетей доступа образуют национальные, региональные или местные инфокоммуникационные сети. [c.174]
Теперь попытаемся подойти к задаче перевозки грузов с несколько иных позиций. Описанный ранее способ формулировки задачи перевозки состоял в том, что мы считали возможной перевозку грузов из каждого пункта-отправителя в каждый из пунктов-потребителей и знали матрицу удельных затрат сц на эти перевозки. Мы представляли себе, что каждый из пунктов-отправителей связан с пунктом-потребителем отдельной дорогой с характерными именно для нее затратами на перевозки. Если же мы взглянем на карту местности, на которой расположены интересующие нас населенные пункты, то увидим, что дороги соединяют не каждый из них с каждым непосредственно, что некоторые из путей, связывающих два пункта, проходят через другие пункты. Более того, окажется возможным провезти груз из одного пункта в другой несколькими путями. Поэтому задачу перевозки грузов часто формулируют не в матричной постановке, как принято называть подход, описанный ранее в этом параграфе, а в так называемой сетевой постановке. Очень простая транспортная сеть приведена на рис. 16. Внутри каждого кружка римской цифрой изобра- [c.159]
Заметим, что на сети, изображенной на рис. 16, груз из пункта / может быть перевезен в пункт IX по разным дорогам. Если бы мы захотели перейти к матричной форме транспортной задачи, то нам надо было бы заранее решить, по какому из маршрутов мы повезем груз. Если пропускная способность каждой из дорог не ограничена, то переход к матричной форме не вызовет затруднений при относительно простой сети. В более сложных сетях этот вопрос можно решить с помощью специально предназначенных для этого алгоритмов. Если же пропускная способность некоторых участков сети дорог ограничена, то возникают осложнения следующего рода. Пусть по участку дороги от пункта IV до пункта V можно провезти не более 30 единиц груза. Но по этой дороге мы можем везти груз и из пункта / в пункты V, VIII и IX, и из пункта /// в пункт VI. Спрашивается, на какие из перевозок мы должны наложить ограничения при переходе к матричной постановке По-видимому, на все вместе. Но, с другой стороны, если возможности дороги между пунктами IV и V будут исчерпаны, часть грузов можно будет перевозить по другим дорогам. Однако при этом изменится величина затрат на перевозки единицы груза, так что в матричной постановке величина сц оказывается зависимой от ху, и задача становится нелинейной. Хотя все эти трудности перехода к матричной постановке задачи перевозки грузов все-таки можно преодолеть при помощи разнообразных искусственных приемов, многие предпочитают решать задачи в сетевой постановке, не переходя к матричной. Алгоритмы решения транспортной задачи были преобразованы к форме, пригодной для решения задач сразу на сети. К сожалению, эти алгоритмы более громоздки, чем алгоритмы решения транспортной задачи в матричной постановке. Есть и другие недостатки сетевой постановки задачи, есть и ряд дополнительных преимуществ, [c.160]
Решение транспортных задач методом потенциалов. Продемонстрируем метод решения транспортных задач в сетевой постановке, так называемый метод потенциалов. Он был предложен Л. В. Канторовичем в начале сороковых годов п является первым методом решения транспортных задач. Интересно отметить, что метод с самого начала предназначался для решения транспортных задач в сетевой постановке и только впоследствии был преобразован к матричной форме. Метод потенциалов является одним из способов реализации общего принципа решения задач линейного программирования — принципа последовательного улучшения плана, о котором мы уже говорили в 4 гл. 1. [c.189]
Общая математическая модель такой задачи может быть представлена в виде сетевой транспортной задачи линейного1 программирования с дополнительными ограничениями. Поставленные задачи были решены на ЭЦВМ БЭСМ-4 по программе,, реализующей алгоритмы К. И. Кима. Проведенное сравнение расчетных вариантов перевозок светлых нефтепродуктов, полученных при решении задач по разным показателям критерия оптимальности, с фактическими- перевозками, имевшими место-в базисном году, показали высокую экономическую эффективность использования предлагаемой экономико-математической модели. Как видно из табл. 2, экономические показатели работы транспорта по расчетным вариантам перевозок не имеют существенных различий. По величине затрат разница между ними колеблется в пределах 0,2—1,1%. Зато разница между расчетными вариантами и фактическим значительная по отдельным периодам года расчетные варианты обеспечивают снижение затрат против фактических в среднем на 7—13%. [c.31]
СТОК [sink point] — 1. Термин теории графов то же, что завершающее (конечное) событие в сетевом графике. См. Событие, Сетевое планирование и управление. 2. В сетевой постановке транспортной задачи — пункт потребления (в отличие от пункта производства, называемого источником). [c.347]
В нашей стране отдельные разработки и методы логистики (определение максимального размера запасов, расчеты сетевых моделей критического пути, методы решения транспортных задач и др.), давно и хорошо известные в экономической теории, находили применение на практике. Однако некомплексное, разобщенное их использование, неразвитость оперативной информационной связи и компьютерной переработки данных слабо отражались на эффективности локальных и глобальных систем управления материальными, информационными и денежными потоками. [c.16]
ЗАДАЧА О КРАТЧАЙШЕМ ПУТИ (shortest route problem) — задача о нахождении на ориентированном графе пути наименьшей длины между двумя заданными его вершинами Длиной пути такого графа называется сумма длин дуг, составляющих этот путь 3 о к п возникает чаще всего при решении транспортных задач, дискретных задач программирования динамического и др В сетевых методах планирования и управления алгоритмы решения 3 о к п используют для нахождения критического пути Известно несколько эффективных методов ее решения Так, для анализа трансп сетей применяют алгоритм, основанный на методе последовательного анализа вариантов [c.69]
ЗАДАЧА О ПЕРЕВОЗКАХ С ПРОМЕЖУТОЧНЫМИ ПУНКТАМИ (transshipment problem) — обобщенная транспортная задача, когда для каждого пункта потребления составляется ур-ние баланса материального 3 о п с п п можно представить в сетевом виде Она является прикладной задачей программирования линейного Для ее решения применяются симплекс-метод, методы графов теории 3 о п с п п применяется при управлении процессами транспортирования грузов через промежуточные базы либо транспортирования сырья с промежуточной переработкой, напр заготовка металлолома у поставщиков, перевозка, переработка его на пунктах промежуточной обработки (прессование и вывоз потребителям — металлургическим заводам) См также Сетевые методы планирования и управления [c.69]
Особенностью обоих указанных методов (детерминированного и вероятностно-неопределенного) моделирования планирования развития ГСС является сведение этапных подзадач к сетевым транспортным задачам линейного программирования (СТЗ ЛП), причем основные принципы такого сведения были разработаны ранее для более широкого класса задач оптимального развития и размещения производства [43]. Такой подход плодотворен и при моделировании развития других отраслей РТЭК. Так, для решения соответствующих вероятностно-неопределенных задач с учетом транспорта ТЭР удобно использовать модели и методы стохастического программирования [115 и др.], и в рамках этого предложен [44, 51 и др.] метод сведения соответствующих задач к СТЗ [c.68]
Во-вторых, специфика зависимости величины минимума расхода электроэнергии на перекачку от ее объема (в соответствии с принципом 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]
Смотреть страницы где упоминается термин Транспортные и сетевые задачи
: [c.42] [c.161] [c.68] [c.39] [c.205] [c.59]Смотреть главы в:
Математические исследования операций в экономике -> Транспортные и сетевые задачи