Составление начального варианта прикрепления. При решении транспортной задачи в сетевой форме с помощью ЭВМ начальная схема перевозок выбирается произвольно. При составлении схемы перевозок вручную исходный вариант может быть получен для всего полигона либо для его отдельных частей с помощью простейших методов прикрепления метода попарного сравнения вариантов, метода разниц, метода круговой зависимости, но с расчетом недопущения явно встречных и излишне дальних перевозок и др. [c.148]
Для решения транспортной задачи в сетевой постановке (3.15)—(3.17) также может быть применен метод потенциалов, который является обобщением описанного выше метода потенциалов для транспортной задачи в матричной постановке. [c.125]
Соответствующая задача сводится к сетевой транспортной задаче с дополнительными ограничениями (,СТЗ ДО), где условия СТЗ полностью определяются сетью (графом) задачи, а дополнительные ограничения формируются по информации о связующих дугах. При этом число дополнительных ограничений равно (А —1)7, где / — число цепочек в (7 + 1)-й подсети. Для решения возникающей задачи могут быть использованы специальные алгоритмы и программы решения СТЗ ДО. Следует подчеркнуть, что в этих алгоритмах существенно используется структура матрицы СТЗ ДО, т. е. на каждой итерации операции преобразования обратной матрицы строятся в соответствии с методом потенциалов решения СТЗ. [c.70]
В настоящее время разработано множество различных алгоритмов решения Т.з. распределительный метод, метод потенциалов, дельта-метод, венгерский метод, метод дифференциальных рент, способ двойного предпочтения, различные сетевые методы. Они относительно просты, по ним составлены десятки программ для различных вычислительных машин. Во многих снабженческих, транспортных и других организациях во всем мире с их помощью рассчитываются маршруты доставки материалов на строительные площадки, планы длительного прикрепления поставщиков металлопроката к потребителям, планы перевозок топлива. Задачи эти часто усложняются разного рода дополнительными условиями напр., в них включается расчет не только себестоимости перевозок, но и себестоимости производства продукции (производственно-транспортная задача), оптимизируется совместно доставка взаимозаменяемых видов продукции (скажем, различных кровельных материалов), оптимизируется доставка грузов с промежуточными базами (складами). Кроме того, следует учитывать, что экономико-математическая модель Т.з. позволяет описывать множество ситуаций, весьма далеких от проблемы перевозок, в частности, находить оптимальное размещение заказов на производство изделий с разной себестоимостью. [c.367]
При этом для каждого СП формируются и решаются сетевые транспортные задачи линейного программирования, подобные этапным задачам в детерминированном методе. Такая задача для каждого СП может решаться дважды — до и после проверки на реалистичность полученного при этом условно-оптимального плана. Если эта проверка показала плохое использование в этом плане некоторых существующих ГП, то в условия данной задачи вводятся дополнительные ограничения на величину соответствующих потоков. В результате нового решения задачи определяется реальный условно-оптимальный план, который и учитывается в дальнейшем при формировании зоны неопределенности . Все эти планы могут дополнительно группироваться с целью получения набора альтернативных вариантов развития ГСС, образующих зону неопределенности . Такая группировка может [c.152]
Метод оптимального планирования является естественным развитием идеи ограниченного перебора реализуемых планов. Он предполагает проведение сравнительного анализа всех допустимых реализуемых планов и выбора из них оптимального, с позиции критерия системы, плана. Практическое применение процедур оптимального планирования требует решения ряда проблем. Так, необходимо иметь формализованные описания целевой функции и модели ограничения системы, нужно уметь выбирать среди множества всех допустимых планов оптимальный. Решение первой задачи лежит в сфере построения математических моделей различных элементов народного хозяйства. Проблема эта частично уже рассматривалась нами в предыдущих главах. Разработка конструктивных алгоритмов поиска оптимальных планов является предметом математического программирования. Как правило, практическое использование этих методов требует выполнения большой вычислительной работы и использования уже не счетов и арифмометров, а мощных и современных ЭВМ. Хорошо развитая к настоящему времени теория, широкий набор теоретически и эмпирически обоснованных алгоритмов уже в настоящее время дают возможность на практике решать широкий класс задач оптимального планирования. Здесь могут быть названы транспортные задачи, задачи размещения предприятий, задачи календарного планирования, задачи сетевого планирования и многие другие. Достигнутые в этом направлении успехи и имеющиеся проблемы хорошо известны из литературы по оптимальному планированию и математическому программированию [c.62]
Различия между транспортными задачами в матричной и сетевой формах весьма незначительны, так как методы их решения основаны на одних и тех же идеях (метод потенциалов). [c.289]
Фаза регулирования. Здесь решаются функциональные задачи (рис.7.7) календарного планирования и диспетчирования производства, т. е. на основе информации и принятых решений в фазе анализа происходит оперативное воздействие на параметры производственного процесса. Для формального описания задач регулирования привлекаются методы и модели календарного и сетевого планирования, транспортные модели и модели оперативного управления. Результатной информацией этой фазы являются календарные и сетевые графики производства продукции, маршруты, алгоритмы диспетчирования. [c.273]
Решение транспортных задач методом потенциалов. Продемонстрируем метод решения транспортных задач в сетевой постановке, так называемый метод потенциалов. Он был предложен Л. В. Канторовичем в начале сороковых годов п является первым методом решения транспортных задач. Интересно отметить, что метод с самого начала предназначался для решения транспортных задач в сетевой постановке и только впоследствии был преобразован к матричной форме. Метод потенциалов является одним из способов реализации общего принципа решения задач линейного программирования — принципа последовательного улучшения плана, о котором мы уже говорили в 4 гл. 1. [c.189]
Описанная модель представляет собой сетевую параметрическую задачу. Для ее решения используется. метод, условно называемый комбинированным. Он представляет собой итерационный процесс, являющийся синтезом метода Форда-Фалкер-сона для решения задачи о максимальном потоке с венгерским методом решения транспортной задачи. Поскольку сеть формализована, объем дуговой информации значительно сокращается. Программа, реализующая указанный алгоритм, составлена на языке Фортран для машины БЭСМ-6. [c.57]
В нашей стране отдельные разработки и методы логистики (определение максимального размера запасов, расчеты сетевых моделей критического пути, методы решения транспортных задач и др.), давно и хорошо известные в экономической теории, находили применение на практике. Однако некомплексное, разобщенное их использование, неразвитость оперативной информационной связи и компьютерной переработки данных слабо отражались на эффективности локальных и глобальных систем управления материальными, информационными и денежными потоками. [c.16]
ЗАДАЧА О КРАТЧАЙШЕМ ПУТИ (shortest route problem) — задача о нахождении на ориентированном графе пути наименьшей длины между двумя заданными его вершинами Длиной пути такого графа называется сумма длин дуг, составляющих этот путь 3 о к п возникает чаще всего при решении транспортных задач, дискретных задач программирования динамического и др В сетевых методах планирования и управления алгоритмы решения 3 о к п используют для нахождения критического пути Известно несколько эффективных методов ее решения Так, для анализа трансп сетей применяют алгоритм, основанный на методе последовательного анализа вариантов [c.69]
Решение возникающей задачи может быть осуществлено при помощи алгоритмов решения СТЗ ДО (однако их применение требует дополнительного обеспечения специальными приемами связности графа задачи) и алгоритмов, учитывающих блочный характер матрицы СТЗ. В статье [12] рассмотрены соответствующие модификации алгоритма К. В. Кима и известного метода декомпозиции. Вычислительные аспекты рассмотренных сетевых задач обсуждаются в статье [16]. В частности, соответствующие графы могут иметь большую размерность вследствие многократного дублирования (по числу продуктов) вершин и дуг исходной транспортной сети, однако на практике существует возможность существенного уменьшения этой размерности. В статье даются сравнительные оценки этих моделей для случая, когда возможно применение их обеих. Результаты весьма огра--ниченного эксперимента показали некоторую предпочтительность более частной модели. [c.71]
ЗАДАЧА О ПЕРЕВОЗКАХ С ПРОМЕЖУТОЧНЫМИ ПУНКТАМИ (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.403]
Рост масштабов и сложности задач управления, повсеместное внедрение принципа разделения труда и вытекающего из него принципа делегирования части полномочий по принятию решений исполнителям (принцип неокончательности и свободы принятия решений) со временем потребовали решительного снижения ошибок в выборе наилучшего решения. Это, в свою очередь, привело к необходимости обобщить опыт и знания, предложить теорию, которая их превратила бы в стройную систему научных взглядов на управление и разработку решений. Родилась парадигма "рациональных решений". Принципы, заложенные в парадигму рациональных решений, предполагают прежде всего моделирование реальной ситуации, т. е. представление ее в упрощенном для изучения виде с сохранением всех значимых характеристик и связей. После моделирования ситуации моделируют цель, формируя и измеряя требуемые результаты. Это расчленило процесс на более простые фазы, позволило распараллелить работы по разработке решений, на порядок снизить ошибки в принятии решения. Парадигма "рациональных решений" по мере своего развития претерпела ряд изменений. Вначале она делала акцент на использование чисто формальных методов, основанных на "физических измерениях". При этом родились такие классические постановки задач и методы исследования операций, как "транспортная задача", "задача массового обслуживания", "задачи сетевого планирования", "управления запасами", "задача о назначении" и др. Правда, перечисленные формальные задачи и методы не всегда оказывались хорошо приспособлены к практическим делам. Это зачастую приводило к нелепостям и разочарованиям. Самые большие неудачи этой науки связаны с пробле- [c.65]
Легко заметить, что задача о кратчайшем пути является частным случаем транспортной задачи в сетевой постановке (или, что то же самое, задачи об оптимальном потоке). Для этого достаточно присвоить вершине s единичный запас, вершине t единичную потребность, все остальные вершины положить нейтральными, а дугам присвоить неограниченные пропускные способности. Однако, как правило, более рациональным оказывается использование конкретных свойств данной задачи и решение ее специальными (частными) методами. К их числу относится, например, метод Минти, основные идеи которого мы изложим ниже. [c.129]