Мы не будем заниматься интерпретацией или свойствами задачи линейного программирования, не будем говорить и о методах ее решения, отметим лишь тот факт, что, кроме методов решения общей задачи линейного программирования, разработано значительное число методов и стандартных программ, предназначенных для решения ее различных частных случаев. Мы рассмотрим два наиболее распространенных класса задач линейного программирования транспортную задачу и обобщенную транспортную (распределительную) задачу. [c.151]
Эта задача проще общей задачи линейного программирования, поскольку ее ограничения имеют весьма специальный вид. Интересно, что к транспортной задаче сводятся проблемы планирования экономических объектов разного типа. Поэтому были предприняты значительные усилия по построению эффективных методов решения транспортной задачи, и эти усилия увенчались успехом. В настоящее время умеют решать задачи транспортного типа значительно быстрее и с большим числом неизвестных, чем обычные задачи [c.151]
Данная задача оптимизации является обобщенной транспортной задачей, так что эффективные методы ее решения существуют и могут быть использованы на практике. [c.164]
Отметим, что помимо методов решения общей задачи линейного программирования разработано значительное число методов и стандартных программ, предназначенных для решения ее различных частных случаев. Опишем наиболее распространенные специальные задачи линейного программирования транспортную задачу и обобщенную транспортную (распределительную) задачу. [c.57]
Эта задача проще общей задачи линейного программирования, поскольку ее ограничения имеют весьма специальную форму. Важно отметить, что к транспортной задаче сводятся проблемы планирования экономических объектов разного типа. Поэтому были предприняты значительные усилия по построению эффективных методов решения транспортной задачи и эти усилия увенчались успехом. В настоящее время задачи транспортного типа удается решить значительно быстрее и с большим числом неизвестных, чем обычные задачи линейного программирования. Само название этой задачи связано с ее происхождением она возникла из задачи оптимальной перевозки грузов. [c.57]
Транспортная задача и задача о назначениях - это частные задачи линейного программирования. Для них в принципе могут быть использованы общие методы решения ЛП-задач (например, симплекс-метод). Однако даже для относительно простых транспортных задач и задач о назначениях характерно большое число переменных решения. Для транспортных задач, имеющих практическое значение, применение таких общих методов может стать неэффективным. Вместе с тем особенности структуры данных и ограничений транспортной задачи обусловливают возможность применения специальных высокоэффективных алгоритмов ее решения. [c.118]
Введение в транспортную задачу или в задачу о назначениях не свойственных им дополнительных ограничений приводит к тому, что эффективные "транспортные" методы решения таких задач (метод "северо-западного угла", циклические перестановки и т.п.) перестают быть применимыми. В этом случае задача будет решаться с помощью общих алгоритмов решения ЛП-задач (например, симплекс-методом). Помимо того что эти методы менее эффективны, они не могут гарантировать целочисленного решения, которое обычно предполагается в транспортной задаче и абсолютно необходимо в задаче о назначениях. Прямо е требование [c.143]
Транспортная задача, в которой имеет место равенство (25.32), называется закрытой и в качестве ЗЛП может быть решена с помощью симплексного метода. Однако благодаря особенностям переменных задачи и системы ограничений разработаны специальные, менее громоздкие методы ее решения. [c.525]
Оказывается, для того, чтобы решить маршрутную задачу с помощью транспортной модели, нужно принять в качестве однородного груза... пустые вагоны, направляемые от пункта выгрузки к пунктам погрузки. Полученное распределение, которое без труда находится на основе транспортной задачи, и дает решение задачи об оптимальной маршрутизации, так как оно определяет пути следования вагонов. Практическое применение транспортной задачи для решения задач оптимальной маршрутизации получило особенное распространение на автотранспорте. В ряде крупных городов производится ежедневный расчет рациональных маршрутов на ЭВМ и на их основе пишутся наряды для значительного процента автомашин. В некоторых небольших автохозяйствах эту методику хорошо освоили и регулярно используют сами диспетчеры. Это позволяет в ряде случаев снижать холостой пробег на 20—40%. Об эффекте ее применения убедительно свидетельствует и такой любопытный факт. В одном автохозяйстве, где проводился эксперимент по введению наилучшей маршрутизации транспорта, шоферы, ездившие по оптимальным маршрутам, найденным с помощью метода. потенциалов, имели на своих машинах отличительные флажки. Через несколько дней после начала эксперимента шоферы наглухо припаяли флажки к машинам, так как они стремились и впредь получать математические наряды. Большая эффективность работы этих машин была выгодна не только для автохозяйства в целом, но и для каждого и,з водителей. [c.43]
Транспортная задача является представителем класса задач линейного программирования и поэтому обладает всеми качествами линейных оптимизационных задач, но одновременно она имеет и ряд дополнительных полезных свойств, которые позволили разработать специальные методы ее решения. [c.110]
Для отдельных видов экономических задач созданы специальные методы, значительно сокращающие объем вычислений при их решении. К числу таких задач относится так называемая транспортная задача. Эта задача была поставлена в СССР, и поиски ее решения были связаны с необходимостью получения наиболее рационального плана перевозок. [c.194]
Наука управления зародилась в Англии во время второй мировой войны, когда группа ученых получила задание на решение сложных военных проблем, таких, как оптимальное размещение сооружений гражданской обороны и огневых позиций, оптимизация глубины подрыва противолодочных бомб и конвоя транспортных караванов. В 50-60-е гг. методология была обновлена, преобразована в целый ряд специфических методов и стала все более широко применяться для решения проблем в промышленности и принятия решений в разных ситуациях. Сегодня модели и методы науки управления используются для решения таких задач, как регулирование транспортных потоков в городах и оптимизация графика движения в аэропортах, составление графиков работы классов и аудиторий в университетах, управление запасами в супермаркетах и универмагах, разработка новых видов продукции, распределение расходов на рекламу различных видов продукции, планирование материального обеспечения, распределение оборудования и трудовых ресурсов для производства разных изделий на заводе, составление графика игр в высшей бейсбольной лиге на сезон. [c.220]
Зависимость отдельных составляющих целевой функции от числа пунктов разгрузки, включенных в какой-либо вариант внешнего транспортного обеспечения и условно рассматриваемых как непрерывные функции в области целочисленных величин числа пунктов разгрузки пгв, представлена на рис. 27. Как видно из рисунка, с увеличением числа пунктов разгрузки возрастают суммарные затраты на их организацию и уменьшаются транспортные расходы по доставке труб к месту работ. Следовательно, целевая функция как сумма указанных составляющих имеет экстремум при некотором значении числа пунктов разгрузки. Учитывая нелинейную зависимость функционала и его отдельных составляющих от числа вводимых пунктов разгрузки и искомых переменных, для решения поставленной задачи не могут быть применены классические методы математического программирования (например,. линейного). Как известно из курса высшей математики, математическое программирование — область математики, разрабатывающая теорию и методы решения многомерных экстремальных задач с ограничениями, т. е. задач на экстремум функции многих переменных с ограничениями на область изменения этих переменных. Само название программирование взято из линейного программирования, где оно обычно обозначает распределение наилучшим образом ограниченных ресурсов для достижения поставленных целей. Следовательно, термин программирование здесь можно заменить термином планирование . [c.145]
Фаза регулирования. Здесь решаются функциональные задачи (рис.7.7) календарного планирования и диспетчирования производства, т. е. на основе информации и принятых решений в фазе анализа происходит оперативное воздействие на параметры производственного процесса. Для формального описания задач регулирования привлекаются методы и модели календарного и сетевого планирования, транспортные модели и модели оперативного управления. Результатной информацией этой фазы являются календарные и сетевые графики производства продукции, маршруты, алгоритмы диспетчирования. [c.273]
Соответствующая задача сводится к сетевой транспортной задаче с дополнительными ограничениями (,СТЗ ДО), где условия СТЗ полностью определяются сетью (графом) задачи, а дополнительные ограничения формируются по информации о связующих дугах. При этом число дополнительных ограничений равно (А —1)7, где / — число цепочек в (7 + 1)-й подсети. Для решения возникающей задачи могут быть использованы специальные алгоритмы и программы решения СТЗ ДО. Следует подчеркнуть, что в этих алгоритмах существенно используется структура матрицы СТЗ ДО, т. е. на каждой итерации операции преобразования обратной матрицы строятся в соответствии с методом потенциалов решения СТЗ. [c.70]
СУДЕБНАЯ ЭКСПЕРТИЗА - исследование, проводимое экспертом в порядке, предусмотренном процессуальным законодательством, для установления по материалам уголовного или гражданского дела фактических данных и обстоятельств. Основанием для проведения СУДЕБНОЙ ЭКСПЕРТИЗЫ служит постановление лица, производящего дознание, следователя, прокурора, определение суда о назначении экспертизы. В ходе СУДЕБНОЙ ЭКСПЕРТИЗЫ на основании специальных научных познаний и исследований, необходимых для экспертизы материалов уголовного либо гражданского дела, устанавливаются факты, обстоятельства. Предмет экспертизы предопределяется вопросами, поставленными следователем или судом. Объектом экспертизы могут быть вещественные доказательства, части трупа, обстановка места происшествия, сравнительные образцы и т.д. Судебные экспертизы проводятся при помощи определенных приемов и с использованием разнообразных технических средств, с учетом предмета экспертизы. Для различных видов СУДЕБНОЙ ЭКСПЕРТИЗЫ разработана специальная методика, т.е. комплекс методов, которые реализуются в определенной последовательности - по этапам исследования, очередности решения частных задач для определения целого и т.п. Проводимые в следственно-судебной практике экспертизы классифицируются по их предмету, объекту, методике исследования и т.д. По степени общности задач, предмета, объектов, методик исследования различают экспертизы криминалистические, инженерно-транспортные, медицинские и психофизиологические, биологические, планово-экономические, в т.ч. бухгалтерские, экологические, инженерно-технические (в их числе можно назвать пожарно-технические, строительно-технические, по технике безопасности и др.). [c.215]
Метод коэффициентов интенсивности основан на замене однократного решения нелинейной задачи развития и размещения с дискретными переменными многократным решением серии обычных линейных транспортных задач с непрерывными переменными. Переход от одной транспортной задачи к другой осуществляется взаимосвязанным изменением мощности и соответствующих ей удельных производственных затрат для какого-либо одного пункта производства. [c.151]
Целью транспортных методов является определение наилучших путей перевозки грузов из нескольких пунктов снабжения в несколько пунктов назначения (потребления), обеспечивающих наименьшие суммарные затраты по производству и транспортировке товаров. Обычно рассматриваются мощности каждого из источников товаров и потребности в этих товарах каждого из пунктов потребления. Каждая фирма, имеющая сеть поставщиков и потребителей, сталкивается с такой задачей. Хотя линейное программирование и может быть использовано для ее решения, более эффективными все-таки являются специальные методы решения транспортной задачи. Как и в линейном программировании, процесс решения транспортной задачи с использованием специальных методов начинается с определения допустимого начального решения, которое затем шаг за шагом улучшается до оптимума. Транспортные методы чрезвычайно просты для решения вручную . [c.213]
Модель (1) — (4) и ее конкретная реализация (5) — (15) — есть классическая транспортная задача линейного программирования. Найдем численное решение задачи (5) — (15) методом потенциалов. [c.254]
Большие объемы перевозимых автотранспортом строительных материалов, широкая их номенклатура и значительное количество грузоотправителей и грузополучателей предопределяют мно жество вариантов по их увязке между собой. Выбрать из них наиболее эффективный можно только при помощи современных математических методов и электронно-вычислительных машин (ЭВМ). Задача с большим числом пунктов производства и потребления продукции при сложной системе транспортной сети, называемая транспортной, решается методом линейного программирования с применением ЭВМ. Кроме транспортных затрат, для минимизации задачи могут быть использованы показатели времени перевозки, расстояния транспортировки и др. С помощью линейного программирования решаются также задачи по формированию веерных и кольцевых маршрутов, определению кратчайших расстояний перевозок и др. Решение таких задач позволяет определить объемы поставок, расстояние транспортировки, стоимость производства продукции с учетом мощности предприятий, наличие порожняковых пробегов, состояние дорог и скорость движения на различных ее участках. [c.337]
ЗАДАЧА О КРАТЧАЙШЕМ ПУТИ (shortest route problem) — задача о нахождении на ориентированном графе пути наименьшей длины между двумя заданными его вершинами Длиной пути такого графа называется сумма длин дуг, составляющих этот путь 3 о к п возникает чаще всего при решении транспортных задач, дискретных задач программирования динамического и др В сетевых методах планирования и управления алгоритмы решения 3 о к п используют для нахождения критического пути Известно несколько эффективных методов ее решения Так, для анализа трансп сетей применяют алгоритм, основанный на методе последовательного анализа вариантов [c.69]
Рост масштабов и сложности задач управления, повсеместное внедрение принципа разделения труда и вытекающего из него принципа делегирования части полномочий по принятию решений исполнителям (принцип неокончательности и свободы принятия решений) со временем потребовали решительного снижения ошибок в выборе наилучшего решения. Это, в свою очередь, привело к необходимости обобщить опыт и знания, предложить теорию, которая их превратила бы в стройную систему научных взглядов на управление и разработку решений. Родилась парадигма "рациональных решений". Принципы, заложенные в парадигму рациональных решений, предполагают прежде всего моделирование реальной ситуации, т. е. представление ее в упрощенном для изучения виде с сохранением всех значимых характеристик и связей. После моделирования ситуации моделируют цель, формируя и измеряя требуемые результаты. Это расчленило процесс на более простые фазы, позволило распараллелить работы по разработке решений, на порядок снизить ошибки в принятии решения. Парадигма "рациональных решений" по мере своего развития претерпела ряд изменений. Вначале она делала акцент на использование чисто формальных методов, основанных на "физических измерениях". При этом родились такие классические постановки задач и методы исследования операций, как "транспортная задача", "задача массового обслуживания", "задачи сетевого планирования", "управления запасами", "задача о назначении" и др. Правда, перечисленные формальные задачи и методы не всегда оказывались хорошо приспособлены к практическим делам. Это зачастую приводило к нелепостям и разочарованиям. Самые большие неудачи этой науки связаны с пробле- [c.65]
При значительных размерах задачи Ю. Ю. Фипксль-штейн предложил специальный метод ее решения, основанный на многократном применении алгоритма транспортной задачи1. Метод этот итеративный и в настоящем пособии не рассматривается. [c.248]
Предлагаемое пособие написано на основе зарубежных и отечественных журнальных публикаций, а также оригинального материала и легло в основу лекций, прочитанных автором студентам 3-4 курсов математико-механического факультета Уральского госуниверситета, специализирующимся на применении математических методов и информатики в экономике. В пособие включены основные факты из качественной теории конечномерных вариационных неравенств и задач о дополнительности, а также краткий обзор методов их решения, главным образом тех, что используют свойства монотонности входящих в постановки отображений. Отдельно разобран случай линейной задачи о дополнительности и рассмотрены конечные методы ее решения. Приведены разнообразные экономические приложения, в том числе модели равновесия в транспортных сетях и модель общего экономического равновесия Вальраса. [c.3]
Становление современного математического аппарата оптимальных экономических решений началось в 40-е годы, благодаря первым работам Н. Винера, Р. Беллмана, С. Джонсона, Л. Канторовича. Задача линейного программирования впервые математически сформулирована Л. В. Канторовичем в 1939 г. на примере задачи раскроя материалов для Ленинградского фанерного треста. В 1947 г. Дж. Данциг предложил универсальный алгоритм решения задач линейного программирования, названный им симплекс-методом. В 1941 г. Хичкок и независимо от него в 1947 г. Купсман формулируют транспортную задачу, в 1945 г. Стиглер — задачу о диете. В 1952 г. было проведено первое успешное решение задачи линейного программирования на ЭВМ Sea в Национальном бюро стандартов США. [c.102]
Составление планов перевозок нефтепродуктов по железным дорогам с помощью экономико-математических методов и ЭВМ — это только первый этап решения транспортной задачи в условиях функционирования АСУнефтеснаб. В данном случае за пункты отгрузки нефтепродуктов принимаются места их производства, т. е. нефтеперерабатывающие заводы, перевалочные нефтебазы, расположенные по берегам морей и рек, железнодорожные пункты налива магистральных нефтепродуктопрово-дов, при этом затраты на доставку нефтепродуктов в указанные пункты водным и трубопроводным транспортом, а также расходы на перевалку не учитываются. [c.231]
СТОХАСТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ [sto hasti programming] — раздел математического программирования, совокупность методов решения оптимизационных задач вероятностного характера. Это означает, что либо параметры ограничений (условий) задачи, либо параметры целевой функции, либо и те и другие являются случайными величинами (содержат случайные компоненты). В ст. "Транспортная задача ", напр., приведена детерминированная модель. В стохастической постановке та же задача будет более близкой к реальности. Рассмотрим одно условие (заданный объем спроса) и допустим, что спрос Ъ. потребителя j — случайная величина b(w), где w — характеристика распределения этой величины. Тогда в одних случаях (при одних ее реализациях) возникает ущерб от неудовлетворенного спроса — "штраф за дефицит", в других, наоборот, потребитель получает излишний груз и, следовательно, тратит дополнительные средства на хранение и перевозку. Все это усложняет решение задачи, т.е. нахождение оптимального варианта прикрепления поставщиков к потребителям. [c.348]
ЗАДАЧА О ПЕРЕВОЗКАХ С ПРОМЕЖУТОЧНЫМИ ПУНКТАМИ (transshipment problem) — обобщенная транспортная задача, когда для каждого пункта потребления составляется ур-ние баланса материального 3 о п с п п можно представить в сетевом виде Она является прикладной задачей программирования линейного Для ее решения применяются симплекс-метод, методы графов теории 3 о п с п п применяется при управлении процессами транспортирования грузов через промежуточные базы либо транспортирования сырья с промежуточной переработкой, напр заготовка металлолома у поставщиков, перевозка, переработка его на пунктах промежуточной обработки (прессование и вывоз потребителям — металлургическим заводам) См также Сетевые методы планирования и управления [c.69]
Во-вторых, специфика зависимости величины минимума расхода электроэнергии на перекачку от ее объема (в соответствии с принципом 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]
Формаль ю-математич. особенности модели транспортной задачи, позволяющие применить к ее решению Р. м. л. п. (более простой, чем, напр., симплексный метод), относятся к характеру ограничений, наложенных на значения переменных. Эти особенности заключаются в следующем а) ограничения носят двухсторонний характер, напр., в транспортной задаче — по наличию грузов в пунктах отправления и по потребности в них в пунктах назначения в производственной задаче — по наличной производственной мощности (производительности) оборудования и по потребности в разных видах продукции и т. п. вследствие этого каждая переменная Хц входит в 2 уравнения в сочетании каждый раз с другими переменными б) все переменные. ЗГу входят в уравнения — ограничения с коэффициентом 7, т. е. все эти уравнения представляют простые суммы переменных, взятых в различных сочетаниях. [c.405]
При огромном количестве различного рода энергетич. потребителей, с одной стороны, при различных условиях н экономич. показателях добычи и реализации топливно-энергетич. ресурсов по отдельным районам и месторождениям, с другой стороны, множественности и разнохарактерности транспортных связей между потребителями и источниками энергетич. ресурсов и т. д. решение задачи оптимизации Т.-э. б. требует, как правило, применения методов математич. анализа к эконэмич. расчетам и использования электронно-вычислительной техники. При этом, ввиду нелинейного характера ряда экономич. зависимостей, характеризующих добычу и использование топливно-энергетич. ресурсов и очень сложных зависимостей между экономикой технологич. и энергетич. процессов, обобщающее решение этой задачи пока еще не найдено. Но используемые в СССР частные приближенные решения по оптимизации Т.-э. б. позволили значительно улучшить, теоретически и экономически обосновать перспективные планы развития всех отраслей энергетич. х-ва (см. Топливный баланс оптимальный). А. М. Некрасов, А. Я. Ризник, Е. О. Штейнгауа. [c.208]
Условие Xtj — 1 или 0, вообще говоря, сильно усложняет задачу и делает невозможным непосредственное применение методов линейного программирования. Далее мы будем специально рассматривать такие задачи в параграфе, посвященном целочисленному программированию. Что же касается задачи о назначениях, то для нее доказано, что можно заменить условие я, 7=1 или 0 на более простое 0 < Xij -< . Точнее говоря, если мы будем, как обычно, применять алгорифм решения транспортной задачи, то в данном случае он автоматически приведет к целым x/j, т. е. к реше нию задачи в ее первоначальной постановке. Таким образом, оказывается, что задача о назначениях также, по существу, описывается моделью транспортной задачи. [c.47]
Легко заметить, что задача о кратчайшем пути является частным случаем транспортной задачи в сетевой постановке (или, что то же самое, задачи об оптимальном потоке). Для этого достаточно присвоить вершине s единичный запас, вершине t единичную потребность, все остальные вершины положить нейтральными, а дугам присвоить неограниченные пропускные способности. Однако, как правило, более рациональным оказывается использование конкретных свойств данной задачи и решение ее специальными (частными) методами. К их числу относится, например, метод Минти, основные идеи которого мы изложим ниже. [c.129]
Смотреть страницы где упоминается термин Транспортная задача и методы ее решения
: [c.213] [c.270] [c.347]Смотреть главы в:
Математические исследования операций в экономике -> Транспортная задача и методы ее решения