Для решения этой задачи существует теорема, приводимая без доказательства Всегда можно найти оптимальное (базисное) решение транспортной задачи, в которой число корреспонденции не будет превышать т + п — 1 . В ряде случаев можно получить несколько оптимальных решений, которые дадут минимум транспортных расходов. [c.285]
Известно более 10 различных методов решения транспортной задачи. Рассмотрим два метода построения начального плана транспортной задачи, связанные с улучшением начального плана. В зависимости от того, как построен начальный план грузовых перевозок, зависит количество итераций, т. е. последовательных приближений. При этом оптимальное решение можно обеспечить при любом его построении. Вместе с тем следует учитывать экономию времени, особенно при решении этих задач ручным счетом. Метод наименьшей стоимости показан в табл. 38, в левом верхнем углу приведена стоимость перевозок, а в нижнем правом — объем перевозок. Находим минимальный элемент, который расположен в клетке 1 — 1. В эту клетку помещаем максимально возможный объем перевозок — 5 единиц. Первую строку из дальнейшего рассмотрения исключаем. [c.285]
В настоящее время разработано несколько математических методов решения транспортных задач. [c.83]
Таким образом, можно при решении транспортной задачи [c.8]
Эта задача проще общей задачи линейного программирования, поскольку ее ограничения имеют весьма специальный вид. Интересно, что к транспортной задаче сводятся проблемы планирования экономических объектов разного типа. Поэтому были предприняты значительные усилия по построению эффективных методов решения транспортной задачи, и эти усилия увенчались успехом. В настоящее время умеют решать задачи транспортного типа значительно быстрее и с большим числом неизвестных, чем обычные задачи [c.151]
Транспортные модели двух описанных здесь типов называются открытыми. Методы решения транспортных задач [c.155]
Возможны и другие усложнения транспортных задач. Конечно, все модификации, рассмотренные нами здесь, могут встречаться в транспортных моделях совместно, что не мешает сводить эти модели с помощью некоторых приемов к транспортной задаче замкнутого типа. Сейчас мы перейдем к рассмотрению одного вопроса также из области перевозок грузов, который, однако, к решению транспортной задачи уже не сводится. [c.157]
Эта задача проще общей задачи линейного программирования, поскольку ее ограничения имеют весьма специальную форму. Важно отметить, что к транспортной задаче сводятся проблемы планирования экономических объектов разного типа. Поэтому были предприняты значительные усилия по построению эффективных методов решения транспортной задачи и эти усилия увенчались успехом. В настоящее время задачи транспортного типа удается решить значительно быстрее и с большим числом неизвестных, чем обычные задачи линейного программирования. Само название этой задачи связано с ее происхождением она возникла из задачи оптимальной перевозки грузов. [c.57]
Рассмотрим один вопрос, который также связан с перевозками грузов, однако к решению транспортной задачи уже не сводится. Пусть используется транспорт нескольких типов, обслуживающий несколько маршрутов, причем перевозки по каждому из маршрутов заданы заранее. Известно, сколько груза может перевезти единица транспорта каждого типа на каждом из маршрутов и сколько единиц транспорта каждого типа имеется. Сформулируем модель в математической форме. Пусть Хц — количество транспорта z -го вида на /-м маршруте (г = 1,. . ., /г / — 1,. . ., т) Кц — количество груза, который может перевезти единица г-го транспорта на у -м маршруте Ъ, — количество груза, который необходимо перевезти на /-м маршруте я, — число единиц транспорта г-го вида. Тогда условия полной перевозки груза будут иметь вид [c.184]
По-видимому, на все вместе. Но, с другой стороны, если возможности дороги между пунктами IV и V будут исчерпаны, то часть грузов можно будет перевозить по другим дорогам. Однако при. этом изменится величина затрат при перевозке единицы груза, так что в матричной постановке величина с,-3- окажется зависимой от Xtj и задача станет нелинейной. Хотя все эти трудности перехода к матричной постановке задачи перевозки грузов все-таки можно преодолеть при помощи разнообразных искусственных приемов, многие исследователи предпочитают решать задачи в сетевой постановке, не переходя к матричной. Алгоритмы решения транспортной задачи были преобразованы к форме, пригодной для решения задач на сети. Сформулируем транспортную задачу в сетевой постановке в математической форме. [c.187]
При решении транспортных задач методом потенциалов прежде всего необходимо построить исходный план перевозки грузов, в котором все мощности будут использованы, а потребности удовлетворены. Это возможно в случае общего баланса спроса и предложения. Выдвинем также некоторые дополнительные требования к исходному плану [c.189]
Материал, изложенный в данном параграфе, дает лишь общее представление о решении транспортных задач методом потенциалов. Подробное изложение этого метода дано, например, в [28]. [c.191]
Решение транспортной задачи распределительным методом было дано в третьем издании учебника Теория экономического анализа ( Финансы и статистика , 1996). [c.163]
При решении транспортной задачи процесс нахождения решения идет по той же самой цепочке, что используется при симплексном методе. Первоначально находится некое решение , которое затем проверяется на оптимальность. Если результат отрицательный, то мы ищем лучшее решение, что продолжается до тех пор, пока не будет найдено оптимальное решение. Этот метод повтора показан на диаграмме, представленной на рис. 8.17. [c.288]
С помощью метода решения транспортных задач предложите маршруты перевозки партий компьютерных систем, которые минимизируют общий километраж. [c.298]
С помощью метода решения транспортных задач найдите оптимальные маршруты перемещения требуемых товаров с целью максимизации ожидаемой прибыли. [c.302]
Складские площади если складские площади в разных местах ограничены, то перемещение необходимого количества товаров согласно распределению, полученному методом решения транспортных задач, возможно, придется разнести по определенным периодам. [c.303]
С помощью метода решения транспортных задач определите маршруты, по которым следует направлять товары, с тем чтобы минимизировать общие расходы. [c.306]
Анализ движения информации позволяет оценить оптимальность построения информационных потоков предприятия, выявить неоправданные ходы, излишние пересечения, дублирования информации. В особых случаях возможно составление и решение транспортной задачи. [c.184]
Для осуществления формализации обозначим начало таких траекторий индексом /, а конец — /. Тогда направление перемещения соответствующих объемов по данной траектории естественно обозначить парой (/, /). При этом ресурсы, потребляемые элементами, а также сами элементы в общем случае могут иметь различную природу в физической систем элементы - это атомы или молекулы, а ресурсы - энергия рассматриваемой системы в информационной системе элементы — это коды различных символов, а ресурс — общая длина передаваемого сообщения в экономической системе, например при решении транспортных задач, элементы — это объемы некоторого продукта, а ресурс — стоимость его доставки от пунктов производства до пунктов потребления. [c.102]
Венгерский метод в классическом варианте применим только для замкнутой модели транспортной задачи. Поэтому при разработке алгоритмов решения транспортной задачи с открытой или полуоткрытой системой ограничений исследовались и были определены эффективные методы предварительного построения замыкания исходной модели с последующим применением венгерского метода. В общем случае схема решения такой задачи представляет собой двухэтапную процедуру, где на первом этапе определяется замыкание модели, а на втором по замыканию модели отыскивается оптимум задачи. [c.135]
Рассмотрим эволюцию решения транспортной задачи и проследим ее движение от простого к сложному. [c.218]
Однако уже с появлением двух поставщиков, расположенных в различных районах страны, сразу же появляются первые трудности в решении транспортной задачи. Здесь уже требуется расчет и сравнение нескольких вариантов, чтобы не допустить встречных и излишне дальних перевозок (рис. 12,б, в). [c.218]
Выходом из создавшегося положения может быть применение в этой области деятельности нефтеснабсбытовых организаций экономико-математических методов и электронно-вычислительной техники. Решение транспортной задачи вполне поддается моделированию и, как показал опыт работы, при наличии необходимых исходных данных ЭММ и ЭВТ позволяют решать сложные транспортные задачи и выбирать из большого числа вариантов оптимальный вариант прикрепления потребителей к поставщикам. [c.221]
Для упрощения решения транспортной задачи целесообразно агрегировать потребителей в зависимости от грузопотоков того или иного нефтепродукта. Иногда один и тот же потребитель может входить в различные пункты агрегирования в зависимости от вида и сорта получаемого нефтепродукта. [c.230]
Математическая постановка сводится к многопродуктовой многоэтапной транспортной задаче линейного программирования с учетом внутригодовой динамики потребления и сезонности работы автомобильного и речного транспорта [2]. Так как модель задачи является одной из модификаций транспортной задачи линейного программирования, то она может быть решена любым из алгоритмов решения транспортной задачи. Матрица такой задачи включает в себя Т блоков, каждый из которых моделирует условия многоэтапной, многопродуктовой транспортной задачи линейного программирования для одного временного отрезка года. [c.77]
Алгоритм решения транспортной задачи методом потенциалов. [c.75]
Алгоритмы решения транспортных задач широко освещены в научной и учебной литературе. Достаточно полно они изложены в книге д-ра эконом, наук Е. П. Нестерова Транспортные задачи линейного программирования (М., Транспорт , 1971). [c.17]
Мощности НПЗ увязываются с техническими возможностями строительства и переработки, суммарным спросом на нефтепродукты у прикрепленных нефтебаз. Стоимость переработки нефти на НПЗ учитывается на связях МН — НПЗ и НПЗ — НБ. В настоящее время большинство нефтепродуктов с НПЗ на нефтебазы доставляется железнодорожным или водным транспортом. В общем случае стоимость перевозки по железной дороге можно считать линейно зависящей от. количества перевозимого продукта, поэтому задачу оптимального закрепления агрегированных пунктов потребления за НПЗ можно решать методами линейного программирования. На стадии закрепления укрупненных пунктов потребления за НПЗ учитываются только транспортные расходы. В результате решения транспортной задачи линейного программирования для каждого района выделяется группа заводов, обеспечивающих его нефтепродуктами. [c.40]
Указанная модель не относится к разряду классических транспортных моделей, так как совокупность неизвестных уцг входит в состав не двух групп балансовых зависимостей (потребление и производство), а трех, включая сюда условие подачи по трубопроводу. Следовательно, сложность отыскания оптимального плана перевозок определяется не только большой размерностью указанной задачи, но и нестандартностью схемы, в результате чего нельзя применять традиционные методы решения транспортных задач. [c.62]
Представленные задачи можно решить >по алгоритму решения транспортной задачи. Наиболее целесообразно применение методов блочного программирования. [c.134]
Детально с методами решения транспортных задач с помощью математического алгорр тма можно познакомиться в специальной литературе [6, 27, 30, 32]. [c.84]
Заметим, что на сети, изображенной на рис. 16, груз из пункта / может быть перевезен в пункт IX по разным дорогам. Если бы мы захотели перейти к матричной форме транспортной задачи, то нам надо было бы заранее решить, по какому из маршрутов мы повезем груз. Если пропускная способность каждой из дорог не ограничена, то переход к матричной форме не вызовет затруднений при относительно простой сети. В более сложных сетях этот вопрос можно решить с помощью специально предназначенных для этого алгоритмов. Если же пропускная способность некоторых участков сети дорог ограничена, то возникают осложнения следующего рода. Пусть по участку дороги от пункта IV до пункта V можно провезти не более 30 единиц груза. Но по этой дороге мы можем везти груз и из пункта / в пункты V, VIII и IX, и из пункта /// в пункт VI. Спрашивается, на какие из перевозок мы должны наложить ограничения при переходе к матричной постановке По-видимому, на все вместе. Но, с другой стороны, если возможности дороги между пунктами IV и V будут исчерпаны, часть грузов можно будет перевозить по другим дорогам. Однако при этом изменится величина затрат на перевозки единицы груза, так что в матричной постановке величина сц оказывается зависимой от ху, и задача становится нелинейной. Хотя все эти трудности перехода к матричной постановке задачи перевозки грузов все-таки можно преодолеть при помощи разнообразных искусственных приемов, многие предпочитают решать задачи в сетевой постановке, не переходя к матричной. Алгоритмы решения транспортной задачи были преобразованы к форме, пригодной для решения задач сразу на сети. К сожалению, эти алгоритмы более громоздки, чем алгоритмы решения транспортной задачи в матричной постановке. Есть и другие недостатки сетевой постановки задачи, есть и ряд дополнительных преимуществ, [c.160]
Решение транспортных задач методом потенциалов. Продемонстрируем метод решения транспортных задач в сетевой постановке, так называемый метод потенциалов. Он был предложен Л. В. Канторовичем в начале сороковых годов п является первым методом решения транспортных задач. Интересно отметить, что метод с самого начала предназначался для решения транспортных задач в сетевой постановке и только впоследствии был преобразован к матричной форме. Метод потенциалов является одним из способов реализации общего принципа решения задач линейного программирования — принципа последовательного улучшения плана, о котором мы уже говорили в 4 гл. 1. [c.189]
В годы советской власти проблеме оптимизации объема оборотных средств практически не уделялось внимания. Несмотря на нормирование оборотных средств, вполне обыденным было накопление сверхнормативных запасов и, как следствие, потери от уценки, утруски, усушки, морального и физического устаревания и т.п. Внедрение элементов систем оптимального управления запасами носило достаточно редкий характер. В качестве примера можно упомянуть об имевшем место в начале 80-х годов эксперименте в розничной торговле города Клайпеды, связанном с внедрением так называемой технологии контейнерной доставки товаров, или торговли с колес , когда за счет оптимизации товаропотоков между оптовыми и розничными предприятиями практически исключалось накопление товарных запасов на складах магазинов и торгов. Были также отдельные попытки оптимизации ресурсопотоков с помощью решения транспортной задачи. [c.318]
Операторы 7 и 11 представляют собой подалгоритмы, выполняющие вычисления по стандартной программе решения транспортной задачи. [c.236]
В работе расмотрены все важнейшие направления количественного анализа хозяйственой деятельности предприятий (основы теоретической статистики и теории вероятностей, применение корреляционно-регрессионного метода для изучения взаимосвязей экономических явлений и процессов). Кроме того, в работе изложена статистическая методология решения конкретных менеджерских и маркетинговых задач (управления проектами, управления запасами, анализа доходности финансовых вложений). Применение линейного программирования в экономике показано в работе на основе решения транспортной задачи. Просим обратить внимание, что в предложенных автором практических примерах в качестве временных периодов приводятся 1997 и 1998 г. В реальности же, с точки зрения статистической обработки информации, эти сведения никак не могут быть сейчас представлены, так как в научный оборот поступают сведения только за 1996 г. [c.5]
При получении решений оптимизации с помощью симплексного метода или методов решения транспортных задач их необходимо интерпретировать с точки зрения реальности и практического смысла. Так, возьмем задачу, которую мы уже рассматривали в этой главе относительно соотношения объемов выпуска различных моделей холодильников в компании Стенлюкс . На первом этапе мы определили количество каждой из моделей, которое необходимо производить, чтобы максимизировать прибыль при наличии ограничений по сырью и рабочему времени. Полученное решение дало оптимальное количество по производству каждой из моделей. В этом примере мы установили, что ежедневно необходимо производить 375 холодильников модели А470 и 937 холодильников модели А370, чтобы получить в итоге валовую прибыль в 82 470 долл. США. Полученные результаты необходимо проанализировать в свете ряда дополнительных факторов, и не всегда принимать их за данность. Так, прежде чем принять окончательное решение по оптимальному соотношению объемов выпуска, руководителю может потребоваться оценить эти результаты с учетом дополнительной информации. При этом необходимо учесть следующие факторы [c.302]
Аналогичным образом при решении транспортных задач необходимо учесть дополнительные факторы, которые могут повлиять на окончательное распределение. Мы рассмотрели транспортную задачу компании Стенлкжс , связанную с перемещением коммерческих холодильных установок с трех производств в три центра сбыта. С помощью соответствующих приемов мы получили распределение установок по транспортным потокам, которые минимизирует транспортные расходы. Однако необходимо учесть еще и другие факторы, в частности [c.303]
Базы производственно-технического обслуживания создаются в пунктах наибольшей концентрации объектов бурения скважин, добычи и промысловой подготовки нефти, обустройства нефтяных месторождений и вспомогательных производств. Их количество зависит в основном от территориальной разобщенности этих объектов. Как правило, базы должны быть приближены к обслуживаемым объектам. Для обслуживания наиболее отдаленных объектов могут быть организованы складские хозяйства или филиалы баз. В отдельных случаях могут создаваться специализированные складские хозяйства не только для данного, но и всего нефтяного района, разрабатываемого объединением. Подобные вопросы определяются решением транспортных задач и выбором оптимального варианта, обеспечивающего минимум транспортных расходов и затрат на содержание специализированного склада. Цехи и участки по оказанию производственных услуг создаются при районных базах, позволяющих наиболее рационально использовать транспортные средства в оба конца. Так, например, при доставке спрессованных обсадных колонн из цеха по опрессовке %необходимо учитывать вывоз с буровых отработанных бурильных, нефтепроводных, водо- и газопроводных труб. [c.39]
Составление планов перевозок нефтепродуктов по железным дорогам с помощью экономико-математических методов и ЭВМ — это только первый этап решения транспортной задачи в условиях функционирования АСУнефтеснаб. В данном случае за пункты отгрузки нефтепродуктов принимаются места их производства, т. е. нефтеперерабатывающие заводы, перевалочные нефтебазы, расположенные по берегам морей и рек, железнодорожные пункты налива магистральных нефтепродуктопрово-дов, при этом затраты на доставку нефтепродуктов в указанные пункты водным и трубопроводным транспортом, а также расходы на перевалку не учитываются. [c.231]
Следующий этап решения транспортной задачи при помощи АСУ — прикрепление потребителей к поставщикам с учетом работы всех видов транспорта, так называемая многотранспортная и многопродуктовая задача. Эта весьма сложная и трудоемкая задача, требующая сбора, подготовки и обработки большого числа разнообразной информации. При решении этой задачи должны быть учтены затраты на транспортирование каждого вида нефтепродуктов всеми видами магистрального транспорта, затраты на перевалку нефтепродуктов, пропускная способность транспортных средств и пунктов перевалки и т. п. Особенно это касается светлых нефтепродуктов, таких как автомобильный бензин, дизельное топливо, осветительный и технический керосины, которые одновременно могут транспортироваться и по магистральным нефтепродуктопроводам и перевозиться по железной дороге и водным транспортом. Наиболее характерными для решения многотранспортной и многопродуктовой задачи являются такие пункты, как Уфа и Куйбышев. [c.231]
Следующий, третий и еще более сложный вариант решения транспортной задачи — это прикрепление потребителей к поставщикам с учетом не только всех видов транспорта, но и с учетом загрузки нефтеперерабатывающих заводов. Сокращение дальности перевозок нефтепродуктов зависит не только от степени рациональности этих перевозок, но и от распределения производства нефтепродуктов по нефтеперерабатывающим заводам. Известно, что одним из важных условий сокращения дальности перевозок является максимальное приближение производства нефтепродуктов к районам их потребления. За последние 25—30 лет в этом направлении в Советском Союзе проведена значительная работа. Если до 1950 г. основными центрами производства нефтепродуктов были Баку, Грозный, Уфа, Куйбышев, Саратов, Москва, Краснодар, Гурьев, Красноводск, Хабаровск, Орск, в то время как их потребление распространялось по всей территории страны, то в настоящее время нефте- [c.232]
С развитием и внедрением АСУ, решением задач различной степени сложности, накоплением опыта работы промышленных, транспортных и снабсбытовых организаций в условиях функционирования АСУ задача по оптимальной загрузке производства, с учетом транспортного фактора, с помощью АСУ будет решена. Это третий этап решения транспортной задачи, когда в условия будут заложены данные, характеризующие мощность нефтеперерабатывающих заводов по выработке необходимых для народного хозяйства нефтепродуктов, себестоимость их производства и затраты на транспортировку нефтепродуктов до районов потребления. С решением этой задачи в рамках АСУ загрузка нефтеперерабатывающих заводов будет полностью подчинена потребностям народного хозяйства в нефтепродуктах как по времени их производства (сезонности), так и по территории их использования, т. е. производство должно быть более дифференцированным в зависимости от сезонности потребления того или иного нефтепродукта, а также от районов максимального потребления. Решение подобной задачи даст экономический эффект не только для отдельной отрасли, а для народного хозяйства в целом. [c.233]
М205. Модифицированный распределительный метод решения транспортной задачи линейного программирования. [c.23]
Р е и г о М. Программа для решения транспортной задачи.— Программа для ЭЦВМ Минск-22 . Таллин, 1969, вып. 8. [c.86]
Описанная модель представляет собой сетевую параметрическую задачу. Для ее решения используется. метод, условно называемый комбинированным. Он представляет собой итерационный процесс, являющийся синтезом метода Форда-Фалкер-сона для решения задачи о максимальном потоке с венгерским методом решения транспортной задачи. Поскольку сеть формализована, объем дуговой информации значительно сокращается. Программа, реализующая указанный алгоритм, составлена на языке Фортран для машины БЭСМ-6. [c.57]
Смотреть страницы где упоминается термин Решение транспортной задачи
: [c.69] [c.260] [c.224]Смотреть главы в:
Организация и планирование кислородного производства -> Решение транспортной задачи