По-видимому, на все вместе. Но, с другой стороны, если возможности дороги между пунктами IV и V будут исчерпаны, то часть грузов можно будет перевозить по другим дорогам. Однако при. этом изменится величина затрат при перевозке единицы груза, так что в матричной постановке величина с,-3- окажется зависимой от Xtj и задача станет нелинейной. Хотя все эти трудности перехода к матричной постановке задачи перевозки грузов все-таки можно преодолеть при помощи разнообразных искусственных приемов, многие исследователи предпочитают решать задачи в сетевой постановке, не переходя к матричной. Алгоритмы решения транспортной задачи были преобразованы к форме, пригодной для решения задач на сети. Сформулируем транспортную задачу в сетевой постановке в математической форме. [c.187]
В сетевой постановке транспортной задачи — пункт производства (в отличие от пункта потребления, называемого стоком). [c.137]
Такие задачи математически бывают представлены в двух видах в сетевой и в матричной постановке. Будучи основанными на принципах транспортной задачи линейного программирования, они очень сложны и решаются специальными, обычно многостадийными приемами с использованием эвристических элементов. [c.290]
Сетевая постановка производственно-транспортной задачи 290 [c.487]
Необходимость в таком предварительном этапе отпадает при сетевой постановке задачи, так как транспортная сеть непосредственно моделируется в задаче с помощью аппарата теории графов. Каждая вершина графа соответствует поставщику, потребителю или транзитному пункту, каждая дуга — участку транспортной сети. Решение задачи в сетевой постановке позволяет выбрать в увязке с многими показателями и оптимальные маршруты перевозки для каждой пары поставщик—потребитель . [c.144]
Рассмотрим транспортную задачу в сетевой постановке. [c.145]
Модель транспортной задачи в сетевой постановке будет выглядеть следующим образом. [c.145]
Каковы особенности транспортной задачи в сетевой постановке [c.175]
Транспортная задача в сетевой постановке [c.288]
Вырождение плана транспортной задачи в сетевой постановке проявляется в том, что при полном использовании запасов и полном удовлетворении потребностей количество стрелок оказывается меньше чем /п + и - 1, где л - поставщики, а т - потребители. [c.291]
Приведенные формулировки задач специально даны в столь абстрактном виде, что позволяет подчеркнуть их универсальность. К очевидной сфере их приложения относится организация грузоперевозок в транспортной сети. В таких моделях вершины i трактуются как пункты, соединенные сетью дорог, и характеризуются потребностями в некотором продукте (bt <0) или его запасами (bt >0). Задачи определения плана, минимизирующего затраты на перевозки, которые с математической точки зрения полностью идентичны (З.П)-(ЗЛЗ), (3.14), также называют транспортными задачами в сетевой постановке. [c.123]
Метод потенциалов для транспортной задачи в сетевой постановке. Рассмотрим задачу определения оптимального потока X в некоторой сети (/, Д G), для которого [c.124]
Для решения транспортной задачи в сетевой постановке (3.15)—(3.17) также может быть применен метод потенциалов, который является обобщением описанного выше метода потенциалов для транспортной задачи в матричной постановке. [c.125]
Теперь дадим краткое описание схемы метода потенциалов для транспортной задачи в сетевой постановке. [c.125]
Покажите, что транспортная задача в матричной постановке является частным случаем транспортной задачи в сетевой постановке. [c.135]
Дайте определение понятия остов сети . Какая связь существует между остовом сети и базисом транспортной задачи в сетевой постановке [c.135]
Теперь попытаемся подойти к задаче перевозки грузов с несколько иных позиций. Описанный ранее способ формулировки задачи перевозки состоял в том, что мы считали возможной перевозку грузов из каждого пункта-отправителя в каждый из пунктов-потребителей и знали матрицу удельных затрат сц на эти перевозки. Мы представляли себе, что каждый из пунктов-отправителей связан с пунктом-потребителем отдельной дорогой с характерными именно для нее затратами на перевозки. Если же мы взглянем на карту местности, на которой расположены интересующие нас населенные пункты, то увидим, что дороги соединяют не каждый из них с каждым непосредственно, что некоторые из путей, связывающих два пункта, проходят через другие пункты. Более того, окажется возможным провезти груз из одного пункта в другой несколькими путями. Поэтому задачу перевозки грузов часто формулируют не в матричной постановке, как принято называть подход, описанный ранее в этом параграфе, а в так называемой сетевой постановке. Очень простая транспортная сеть приведена на рис. 16. Внутри каждого кружка римской цифрой изобра- [c.159]
Заметим, что на сети, изображенной на рис. 16, груз из пункта / может быть перевезен в пункт IX по разным дорогам. Если бы мы захотели перейти к матричной форме транспортной задачи, то нам надо было бы заранее решить, по какому из маршрутов мы повезем груз. Если пропускная способность каждой из дорог не ограничена, то переход к матричной форме не вызовет затруднений при относительно простой сети. В более сложных сетях этот вопрос можно решить с помощью специально предназначенных для этого алгоритмов. Если же пропускная способность некоторых участков сети дорог ограничена, то возникают осложнения следующего рода. Пусть по участку дороги от пункта IV до пункта V можно провезти не более 30 единиц груза. Но по этой дороге мы можем везти груз и из пункта / в пункты V, VIII и IX, и из пункта /// в пункт VI. Спрашивается, на какие из перевозок мы должны наложить ограничения при переходе к матричной постановке По-видимому, на все вместе. Но, с другой стороны, если возможности дороги между пунктами IV и V будут исчерпаны, часть грузов можно будет перевозить по другим дорогам. Однако при этом изменится величина затрат на перевозки единицы груза, так что в матричной постановке величина сц оказывается зависимой от ху, и задача становится нелинейной. Хотя все эти трудности перехода к матричной постановке задачи перевозки грузов все-таки можно преодолеть при помощи разнообразных искусственных приемов, многие предпочитают решать задачи в сетевой постановке, не переходя к матричной. Алгоритмы решения транспортной задачи были преобразованы к форме, пригодной для решения задач сразу на сети. К сожалению, эти алгоритмы более громоздки, чем алгоритмы решения транспортной задачи в матричной постановке. Есть и другие недостатки сетевой постановки задачи, есть и ряд дополнительных преимуществ, [c.160]
Решение транспортных задач методом потенциалов. Продемонстрируем метод решения транспортных задач в сетевой постановке, так называемый метод потенциалов. Он был предложен Л. В. Канторовичем в начале сороковых годов п является первым методом решения транспортных задач. Интересно отметить, что метод с самого начала предназначался для решения транспортных задач в сетевой постановке и только впоследствии был преобразован к матричной форме. Метод потенциалов является одним из способов реализации общего принципа решения задач линейного программирования — принципа последовательного улучшения плана, о котором мы уже говорили в 4 гл. 1. [c.189]
Предлагаемый порядок оперативного планирования рассчитан на широкое применение электронно-вычислительной техники. Разработанные экономико-математические модели могут быть реализованы на ЭВМ по стандартным программам. На первом этапе планирования в Главном вычислительном центре АСУнефтеснаб РСФСР предлагается решать сетевую транспортную задачу линейного программирования с дополнительными ограничениями, на втором этапе в кустовых вычислительных центрах этой организации — многопродуктовую транспортную задачу линейного программирования в матричной постановке. [c.33]
СТОК [sink point] — 1. Термин теории графов то же, что завершающее (конечное) событие в сетевом графике. См. Событие, Сетевое планирование и управление. 2. В сетевой постановке транспортной задачи — пункт потребления (в отличие от пункта производства, называемого источником). [c.347]
Рост масштабов и сложности задач управления, повсеместное внедрение принципа разделения труда и вытекающего из него принципа делегирования части полномочий по принятию решений исполнителям (принцип неокончательности и свободы принятия решений) со временем потребовали решительного снижения ошибок в выборе наилучшего решения. Это, в свою очередь, привело к необходимости обобщить опыт и знания, предложить теорию, которая их превратила бы в стройную систему научных взглядов на управление и разработку решений. Родилась парадигма "рациональных решений". Принципы, заложенные в парадигму рациональных решений, предполагают прежде всего моделирование реальной ситуации, т. е. представление ее в упрощенном для изучения виде с сохранением всех значимых характеристик и связей. После моделирования ситуации моделируют цель, формируя и измеряя требуемые результаты. Это расчленило процесс на более простые фазы, позволило распараллелить работы по разработке решений, на порядок снизить ошибки в принятии решения. Парадигма "рациональных решений" по мере своего развития претерпела ряд изменений. Вначале она делала акцент на использование чисто формальных методов, основанных на "физических измерениях". При этом родились такие классические постановки задач и методы исследования операций, как "транспортная задача", "задача массового обслуживания", "задачи сетевого планирования", "управления запасами", "задача о назначении" и др. Правда, перечисленные формальные задачи и методы не всегда оказывались хорошо приспособлены к практическим делам. Это зачастую приводило к нелепостям и разочарованиям. Самые большие неудачи этой науки связаны с пробле- [c.65]
Мы рассмотрели транспортную задачу в матричной, или шахматной постановке. Такое название этой постановки связано с тем, что информация о расстояниях и грузопотоках задана в виде шахматной таблицы-матрицы. Нередко, однако, приходится сталкиваться и с другой формой транспортной задачи — транспортной задачей в сетевой постановке. Если при матричной постановке задачи предполагаются известными затраты по транспорти- [c.53]
Легко заметить, что задача о кратчайшем пути является частным случаем транспортной задачи в сетевой постановке (или, что то же самое, задачи об оптимальном потоке). Для этого достаточно присвоить вершине s единичный запас, вершине t единичную потребность, все остальные вершины положить нейтральными, а дугам присвоить неограниченные пропускные способности. Однако, как правило, более рациональным оказывается использование конкретных свойств данной задачи и решение ее специальными (частными) методами. К их числу относится, например, метод Минти, основные идеи которого мы изложим ниже. [c.129]