По-видимому, на все вместе. Но, с другой стороны, если возможности дороги между пунктами IV и V будут исчерпаны, то часть грузов можно будет перевозить по другим дорогам. Однако при. этом изменится величина затрат при перевозке единицы груза, так что в матричной постановке величина с,-3- окажется зависимой от Xtj и задача станет нелинейной. Хотя все эти трудности перехода к матричной постановке задачи перевозки грузов все-таки можно преодолеть при помощи разнообразных искусственных приемов, многие исследователи предпочитают решать задачи в сетевой постановке, не переходя к матричной. Алгоритмы решения транспортной задачи были преобразованы к форме, пригодной для решения задач на сети. Сформулируем транспортную задачу в сетевой постановке в математической форме. [c.187]
Такие задачи математически бывают представлены в двух видах в сетевой и в матричной постановке. Будучи основанными на принципах транспортной задачи линейного программирования, они очень сложны и решаются специальными, обычно многостадийными приемами с использованием эвристических элементов. [c.290]
Матричная постановка производственно-транспортной задачи 290 [c.473]
До сих пор мы рассматривали транспортные задачи в матричной форме. Каждое пересечение строки и столбца этой матрицы соответствует транспортному маршруту, связывающему данную пару пунктов поставщик—потребитель . Реально на транспортной сети таких маршрутов может быть несколько. Поэтому при матричной постановке необходимо заранее, до составления и решения задачи, выбрать из нескольких возможных один маршрут для каждой пары пунктов поставщик—потребитель . Чаще такой выбор осуществляется довольно просто — по кратчайшим расстояниям, по минимуму транспортных затрат или же берутся так называемые рациональные направления перевозок. Реже, хотя это и более обоснованно, решаются специальные задачи по выбору маршрутов. [c.144]
Транспортная задача в матричной постановке и ее свойства. Вернемся к транспортной задаче в матричной постановке, о которой мы уже упоминали при рассмотрении вопросов построения математических моделей. Напомним, что данная задача сводится к определению такого плана перевозок некоторого продукта из пунктов его производства в пункты потребления (, -,/ X который минимизирует целевую функцию [c.109]
Для решения транспортной задачи в сетевой постановке (3.15)—(3.17) также может быть применен метод потенциалов, который является обобщением описанного выше метода потенциалов для транспортной задачи в матричной постановке. [c.125]
Покажите, что транспортная задача в матричной постановке является частным случаем транспортной задачи в сетевой постановке. [c.135]
Задачи с разрывными целевыми функциями. Как уже упоминалось выше, многие экономические системы характеризуются наличием так называемых постоянных затрат, которые должны быть произведены независимо от объема производства. Учет в моделях этих и подобных факторов приводит к появлению в них целевых функций, не обладающих свойством непрерывности. В качестве примера может быть приведена транспортная задача с фиксированными доплатами. Она отличается от транспортной задачи в матричной постановке, рассмотренной в главе 3, тем, что в ней затраты по перевозке груза из r -го пункта производства в /-и пункт потребления определяются как [c.141]
Теперь попытаемся подойти к задаче перевозки грузов с несколько иных позиций. Описанный ранее способ формулировки задачи перевозки состоял в том, что мы считали возможной перевозку грузов из каждого пункта-отправителя в каждый из пунктов-потребителей и знали матрицу удельных затрат сц на эти перевозки. Мы представляли себе, что каждый из пунктов-отправителей связан с пунктом-потребителем отдельной дорогой с характерными именно для нее затратами на перевозки. Если же мы взглянем на карту местности, на которой расположены интересующие нас населенные пункты, то увидим, что дороги соединяют не каждый из них с каждым непосредственно, что некоторые из путей, связывающих два пункта, проходят через другие пункты. Более того, окажется возможным провезти груз из одного пункта в другой несколькими путями. Поэтому задачу перевозки грузов часто формулируют не в матричной постановке, как принято называть подход, описанный ранее в этом параграфе, а в так называемой сетевой постановке. Очень простая транспортная сеть приведена на рис. 16. Внутри каждого кружка римской цифрой изобра- [c.159]
Заметим, что на сети, изображенной на рис. 16, груз из пункта / может быть перевезен в пункт IX по разным дорогам. Если бы мы захотели перейти к матричной форме транспортной задачи, то нам надо было бы заранее решить, по какому из маршрутов мы повезем груз. Если пропускная способность каждой из дорог не ограничена, то переход к матричной форме не вызовет затруднений при относительно простой сети. В более сложных сетях этот вопрос можно решить с помощью специально предназначенных для этого алгоритмов. Если же пропускная способность некоторых участков сети дорог ограничена, то возникают осложнения следующего рода. Пусть по участку дороги от пункта IV до пункта V можно провезти не более 30 единиц груза. Но по этой дороге мы можем везти груз и из пункта / в пункты V, VIII и IX, и из пункта /// в пункт VI. Спрашивается, на какие из перевозок мы должны наложить ограничения при переходе к матричной постановке По-видимому, на все вместе. Но, с другой стороны, если возможности дороги между пунктами IV и V будут исчерпаны, часть грузов можно будет перевозить по другим дорогам. Однако при этом изменится величина затрат на перевозки единицы груза, так что в матричной постановке величина сц оказывается зависимой от ху, и задача становится нелинейной. Хотя все эти трудности перехода к матричной постановке задачи перевозки грузов все-таки можно преодолеть при помощи разнообразных искусственных приемов, многие предпочитают решать задачи в сетевой постановке, не переходя к матричной. Алгоритмы решения транспортной задачи были преобразованы к форме, пригодной для решения задач сразу на сети. К сожалению, эти алгоритмы более громоздки, чем алгоритмы решения транспортной задачи в матричной постановке. Есть и другие недостатки сетевой постановки задачи, есть и ряд дополнительных преимуществ, [c.160]
Решение транспортных задач методом потенциалов. Продемонстрируем метод решения транспортных задач в сетевой постановке, так называемый метод потенциалов. Он был предложен Л. В. Канторовичем в начале сороковых годов п является первым методом решения транспортных задач. Интересно отметить, что метод с самого начала предназначался для решения транспортных задач в сетевой постановке и только впоследствии был преобразован к матричной форме. Метод потенциалов является одним из способов реализации общего принципа решения задач линейного программирования — принципа последовательного улучшения плана, о котором мы уже говорили в 4 гл. 1. [c.189]
Предлагаемый порядок оперативного планирования рассчитан на широкое применение электронно-вычислительной техники. Разработанные экономико-математические модели могут быть реализованы на ЭВМ по стандартным программам. На первом этапе планирования в Главном вычислительном центре АСУнефтеснаб РСФСР предлагается решать сетевую транспортную задачу линейного программирования с дополнительными ограничениями, на втором этапе в кустовых вычислительных центрах этой организации — многопродуктовую транспортную задачу линейного программирования в матричной постановке. [c.33]
Рассмотренная нами постановка транспортной задачи но- сит название матричной или шахматки . (Название связано [c.41]
Мы рассмотрели транспортную задачу в матричной, или шахматной постановке. Такое название этой постановки связано с тем, что информация о расстояниях и грузопотоках задана в виде шахматной таблицы-матрицы. Нередко, однако, приходится сталкиваться и с другой формой транспортной задачи — транспортной задачей в сетевой постановке. Если при матричной постановке задачи предполагаются известными затраты по транспорти- [c.53]