Вычислительная задачи линейного программирования

В ряде случаев применение эвристического программирования для решения некоторых научно-технических экономических и производственных задач (как, например, задача балансирования сборочного конвейера) дает существенный выигрыш в отличие от иопользования методов линейного, целочисленного линейного ил№ динамического программирования, применение которых -связано с такими вычислительными трудностями, которые делают нереальным решение этих задач на ЭВМ в практически приемлемые сроки. [c.161]

Решение задач линейного программирования при достаточно большом числе переменных в исходной постановке задачи, как правило, требует применения цифровых вычислительных машин. При этом весьма важное значение приобретают вопросы организа- [c.446]

Минимизация этой функции производится методом ветпей и границ. Задача составления расписания в наиболее общих случаях относится к числу трудно формализуемых, и обычно расписания составляют, исходя из особенностей конкретной оптимизируемой системы известную трудность представляет также решение задач теории расписаний. По содержанию эти задачи относятся к классу комбинаторных, для которых сущсстненное значение имеет размерность. Как правило, размерность ладач составления оптимальных расписаний настолько велика, что решать их простым перебором вариантов не представляется возможным даже на современных быстродействующих вычислительных машинах. Поэтому для снижения размерности прибегают к различного рода эвристическим приемам или используют. методы направленного перебора (ветвей и границ). Часто задачи составления расписаний сводятся к задачам целочисленного линейного программирования (в том числе многоиндексного), для решения которых используются широко известные методы отсечения или ветвей и границ. Рассмотрим несколько примеров составления оптимальных расписаний. [c.300]

Основной метод решения общей задачи линейного программирования — так называемый симплекс-метод, состоящий из алгоритма отыскания какого-нибудь решения среди решений системы линейных неравенств (39), т. е. вершины многогранника О и алгоритма последовательного перехода от полученного уже решения системы (39) к новому решению, для которого форма (38) имеет большее (меньшее) значение до получения оптимального решения. Основу вычислительной схемы симплекс-метода составляют преобразования таблицы исходных данных, организованных на базе модифицированных жордановых исключений. Схематизированное преобразование таблицы определяет основной шаг симплекс-метода. [c.60]

Для решения задач линейного программирования имеется практически универсальный алгоритм — симплексный метод, позволяющий за конечное число итераций находить оптимальное решение подавляющего большинства практически важных задач. Тип используемых ограничений (равенства или неравенства) не сказывается на возможности применения указанного алгоритма. Дополнительной проверки на оптимальность для получаемых решений не требуется. Как правило, практические задачи линейного программирования отличаются весьма значительным числом независимых переменных. Поэтому для их решения обычно используют вычислительные машины, необходимая мощность которых определяется размерностью решаемой задачи. [c.33]

Следует отметить, что значение линейного программирования не исчерпывается решением задач только указанных типов. Сообщается , что в методах решения задач так называемого выпуклого программирования существенным образом используется вычислительный аппарат линейного программирования. Кроме того, иногда при рассмотрении сложного нелинейного объекта иногда удается представить его математическое описание в некоторых локальных областях изменения независимых переменных приближенными линейными соотношениями. Это позволяет свести исходную задачу оптимизации к задаче линейного программирования. Тем самым становится возможным применять его математический аппарат, который в настоящее время разработан достаточно подробно и при наличии цифровой вычислительной машины обеспечивает решение оптимальных задач весьма высокой размерности. [c.413]

Среди известных разделов математического программирования наиболее развито и закончено линейное программирование. Термин линейное означает прямую пропорциональную зависимость между переменными. Разработано множество вычислительных методов, позволяющих решать на ЭВМ задачи линейного программирования, насчитывающие сотни и тысячи переменных, неравенств и уравнений. [c.57]

Вычислительным методом для решения такой задачи служит типовой алгоритм методов линейного программирования, в том числе симплексного метода, т. е. метода последовательного улучшения производственной программы с помощью итерирования. За исходную точку расчетов принимается некоторый план производства по каждому изделию и затем в последовательном порядке изменяются значения прироста переменных. [c.266]

Выбор подхода к составлению пакета определяется несколькими факторами, среди которых можно выделить частоту использования программы, тип описания процесса, квалификацию пользователя. Как правило, проблемно-ориентированные пакеты программ разрабатываются для расчета процессов с детерминированным математическим описанием и в дальнейшем регулярно используются. Они более совершенны с точки зрения автоматизации вычислительных действий и не требуют глубоких знаний в области вычислительной техники и программирования. При использовании методо-ориентированных пакетов программ для решения конкретной задачи необходимо формировать рабочую программу из элементов пакета в соответствии с алгоритмом решения, добавляя недостающие. Например, для решения задачи линейного программирования необходимо, помимо настройки стандартных программ, задать функцию с соответствующими ограничениями. [c.46]

В оптимальном решении значение искусственной переменной xn+ni+i должно быть в точности равно нулю, для чего необходимо, чтобы базисный вектор, соответствующий этой переменной, был исключен из окончательного базиса. При использовании симплексного метода в этом случае необходимо предусмотреть специальный контроль за исключением базисного вектора, отвечающего искусственной переменной хп+т+1, что вносит определенные неудобства при решении задач линейного программирования на вычислительных машинах. [c.439]

При выводе основных соотношений симплексного метода допускалось, что любые т векторов из общего числа n + m + 1 векторов AJ и В, составляющих матрицу ограничений, линейно независимы. При решении практических задач данное требование, как правило, обычно выполняется. Поэтому рассмотренный выше алгоритм симплексного метода служит основой подавляющего большинства программ, составленных для решения задач линейного программирования на вычислительных машинах. . [c.454]

Эти обстоятельства иногда позволяют использовать принцип двойственности в задачах линейного программирования для сокращения объема вычислений в процессе решения задачи и экономии необходимого объема запоминающих устройств вычислительной машины. Поскольку результаты решения исходной и двойственной задач совпадают, можно так выбрать представление решаемой задачи, чтобы обеспечить выполнение матричных операций с матрицами меньшего порядка. При этом руководствуются правилом если число независимых переменных п в исходной задаче меньше числа ограничений т, то имеет смысл решать двойственную задачу, поскольку вместо операций с матрицами порядка т будут производиться операции с матрицами порядка п (согласно числу ограничений двойственной задачи). [c.464]

Вместе с тем использование приближенных методов решения экстремальных комбинаторных задач, таких, как случайный поиск или какое-то приоритетное правило, основанное на особенностях задачи, здесь осложнено тем, что расчет критерия оптимальности для каждого плана-графика Г/ требует решения задачи линейного программирования, что в свою очередь связано с огромными вычислительными тру ностями. [c.216]

Общая задача линейного программирования не может быть решена обычными методами классического анализа. Поэтому для ее решения применяются специальные методы, дающие вычислительную схему, которая позволяет за конечное число шагов (итераций) найти оптимальное решение. Для решения указанных задач могут быть использованы следующие математические методы 1) последовательного улучшения, 2) распределительный, 3) модифицированный распределительный, 4) разрешающих множителей, 5) матричный, 6) симплекс метод, [c.188]

Задачи составления оптимального расписания запуска оборудования в схеме в целом и в каждой из ее стадий сложны с вычислительной точки зрения и принадлежат к числу так называемых универсальных дискретных задач. Это означает, что они эквивалентны по сложности, например, общей задаче целочисленного линейного программирования, или задаче о коммивояжере . В настоящее время неизвестны эффективные алгоритмы для их точного решения. Для приближенного решения задачи составления расписания для ГАПС применяется метод ветвей и границ, который заключается в следующем. [c.536]

Решение большинства задач линейного программирования, имеющих практическое применение, требует огромного количества сложных вычислений, которое возможно в основном с помощью электронно-вычислительных машин, обладающих быстродействием, точностью и большой памятью. Расчеты при решении обычных даже небольших задач линейного программирования требуют больших затрат ручного труда. Вычислительные машины такие задачи часто решают за несколько минут. Кроме того, машины весьма надежны, имеют контрольные устройства, которые гарантируют точность получаемых расчетов на всех этапах решения задачи. [c.202]

Задача линейного программирования содержит большое количество информации, которая должна быть при работе вручную где-то сохранена. В таких условиях можно сделать какие-то упущения. Вычислительные машины с их огромной памятью хранят либо всю информацию о заДаче, либо ее основную часть. [c.202]

В общем случае указанные вычислительные задачи решаются методами математической теории оптимальных процессов, а при замене дифференциальных уравнений равновесия (или совместности деформаций) системой линейных алгебраических уравнений — методами линейного программирования с использованием соответствующих стандартных или специальных подпрограмм для ЭВМ. [c.330]

В области линейного программирования достаточно хорошо зарекомендовал себя симплексный метод (и его модификации). Таким образом, выбор метода здесь не сложен. Гораздо больше времени приходится затрачивать на четкую формулировку задачи, корректировку параметров математических моделей с целью их наибольшей адаптации экспериментальным данным, и анализ результатов вычислений. Поэтому здесь полезно использовать диалоговые вычислительные системы. [c.234]

Применение теории рециркуляции позволяет решить все эти задачи с большой точностью, использовать современную вычислительную технику (что служит основой для автоматизации производственных процессов), а также широко применить методы линейного программирования. [c.10]

Параллельно с разработкой вычислительного оборудования развивались к методы решения, которые в настоящее время объединены под названием анализа деятельности или исследования операций. Согласно фор.мальному определению эта группа методов основывается на использований научных и математических принципов для решения задач, связанных с деловой, промышленной и правительственной деятельностью. Ценность ее заключается главным образом в помощи руководящим деятелям путем отыскания рациональных основ для принятия решений. Метод исследования операций получил развитие как самостоятельная отрасль знания во время второй мировой войны, когда многочисленным группам ученых и инженеров пришлось решать много сложных проблем, связанных с военной обстановкой. Однако многие из методов и концепций исследования и анализа операций применялись прогрессивными руководящими деятелями уже давно. В нефтеперерабатывающей промышленности широко используются три наиболее распространенных метода исследования операций, а именно а) моделирование, б) линейное программирование и в) метод множественных регрессий. Эти методы представляли бы лишь небольшую ценность для нефтеперерабатывающей промышленности, если бы не появились вычислительные машины. Это объясняется громадным объемом вычислений, которые приходится выполнять, колоссальным количеством данных, которые необходимо анализировать, и динамическим характером задач, возникающих в области нефтепереработки. [c.7]

Уравнение рентабельности завершает математическую модель. По- еле того как оно составлено, решение его весьма просто. В задачи дан-ной статьи не входит приводить какие-либо методы решения, так как эта тема весьма широко освещена в современной литературе [5] с появлением высокопроизводительных вычислительных машин, способных решать задачи методом линейного программирования, фактически применяемый метод решения не играет существенной роли. [c.17]

Линейное программирование — раздел математики — не следует смешивать с программированием (составлением программ) для решения задач на электронных цифровых вычислительных машинах. [c.254]

В последнее время для решения многомерных экстремальных задач (при наличии ограничений на области изменения переменных) применяют методы математического программирования. В наибольшей степени разработаны методы линейного программирования, предусматривающие нахождение экстремума линейных и целевых функций. Следует отметить, что зависимости полезного эффекта и затрат от параметров элементов проектных решений системы пожарной защиты, как правило, нелинейны, что требует использования специальных методов нелинейного программирования, реализация которых возможна лишь при использовании современных электронно-вычислительных машин. [c.99]

Используется вариант простого алгоритма линейного программирования, разработанного для решения транспортных задач вычислительными машинами и в простейших случаях вручную. Применен метод итерации. При 200 пунктах требуется проверка приблизительно 20 тыс. пар расстояний за каждую итерацию на все требуется примерно 200 итераций по 20 сек (приблизительно 1 ч). При сложных задачах можно предварительно исключить многие пары пунктов как заведомо невыгодные для включения в один рейс. [c.390]

Полученная оценка памяти вычислительной машины (УП1,218) должна при(гнматься во внимание при программировании рассмотренного алгоритма решения задач линейного программировании на конкретной машине. Разумеется, что ири этом нужно также учитьшать объем памяти, зани1маемой программой вычислений, кото )ый уже зависит от особенностей используемой машины и искусства программиста. [c.459]

Для отыскания оптимального решения прямым методом перебора возможных решений с их проверкой по величине критерия оптимальности и по выполнению условий (VIII, 35) и (VIII, 36) не-обх9Димо решить n+m систем п уравнений. При достаточно больших значениях пит число Ст+п может быть настолько велико, что поиск решения потребует значительного времени даже при наличии "современных вычислительных машин. Поэтому прямые методы поиска оптимального решения практически исчерпываются случаями решения задач линейного программирования, содержащих не более чем 2 — 3 независимых переменных при сравнительно небольшом числе ограничений. [c.416]

Полученная оценка памяти вычислительной машины (VIII, 218) должна приниматься во внимание при программировании рассмотренного алгоритма решения задач линейного программирования [c.453]

Агрегация сетевой модели предприятия не уменьшает вычислительных трудностей настолько, чтобы комбинаторную задачу поиска оптимальных параметров дуг агрегированной сетевой модели можно было решать сразу для всех дуг сети, рассчитывая затем пропускные способности агрегированных дуг по соотношениям ( 11.16), ( 1.1), ( 1.2) на каждом интервале горизонта планирования и решая задачу линейного программирования для агрерированной сети. Поэтому здесь целесообразно применить метод последовательной оптимизации, основанный на аппроксимации критерия ( 11.20). [c.218]

Амирагов К. А. Задачи линейного программирования с переменными технологическими коэффициентами. Вопросы вычислительной математики и вычислительной техники (Труды ВЦ АН АзССР), т. 3, 1965, с. 110—124. Антропов М. В., Зуев А. А., Крейндель Я. И., Меньшов В. Н., Шен-брот И. М. Система оптимального оперативно-календарного планирования ремонтов основного оборудования химического завода. — Химическое и нефтяное мапшностроение , 1968, № 11, с. 25—27. [c.282]

Этот пакет удобно использовать и для выполнения табличных расчетов. Например, построить симплексные таблицы при решении задачи линейного про-грам.мирования. При этом таблицы представляются в обычной матричной форме, а M.A.TH AD выполняет лишь роль быстрого вычислительного средства и при этом не теряется основное направление при изучении методов опти. тза-цни, как это бывает при использовании програ мм, написанных на традиционных языках программирования. Студенты самостоятельно анализируют полученные результаты расчета и выбирают направление дальнейшего преобразования таблицы. [c.216]

Рациональное размещение новых предприятий и производств существенно влияет на повышение эффективности производства. Выбор оптимального варианта осуществляют с учетом экономических, социальных и экологических факторов с применением экономико-математических методов, основанных на нахождении минимума приведенных затрат на выпуск продукции вновь строящихся предприятий. Для выбора оптимального варианта размещения предприятий широко используют модели транспортной задачи, решаемой методами линейного программирования, Совершенствование организационной структуры управления не4)теперерабатывающими предприятиями возможно путем укрупнения цехов и участков, централизации и специализации работ, концентрации функций управления вспомогательными службами, оптимизации численности инженерно-технических работников и служащих, широкого применения экономико-математических методов, электронно-вычислительной техники, организационной техники и средств связи. Необходим системный подход к проектированию структур управления. [c.328]

Более того, эти дисциплины испытывали известное взаимное влияние, обусловленное физическими аналогиями и математической общностью своих задач. Можно указать, к примеру, на монографии Дж. Б. Денниса [58], рассмотревшего принщ1п электрической аналогии для постановки и решения задач линейного и квадратичного программирования Л.А. Крумма [98, 99], предложившего еще в 1957 г. для оптимизащ1и режимов ЭЭС метод приведенного градиента, который фактически стал одним из первых общих методов выпуклого программирования Г.Е. Пухова и М.Н. Кулика [187], разработавших методы построения и использования гибридных (аналогово-цифровых) вычислительных систем, сочетающих высокое быстродействие и наглядность работы аналоговых устройств с универсализмом и точностью ЭВМ, для решения задач расчета и управления режимами как ЭЭС, так и гидравлических систем. [c.232]

Сопоставление экономической эффективности, получаемой в результате внесения минеральных удобрений, и формирование оптимального плана их распределения осуществляется на электронно-вычислительной машине с помощью методов линейного программирования. Для этого составляется матрица экономико-математической задачи по ра,зработанной математической модели процесса. [c.344]

Предполагается, что все Су, и — величины известные. Все переменные ограничены областью положительных значений от нуля включительно. Это условие известно под названием ограничение неотрицательности . Согласно терминологии линейного программирования, г — искомая функция, — составляющие результирующего вектора с и — составляющие правостороннего вектора Ь. Решение задачи ЛП основывается на стандартной программе АЬРНАС , разработанной в вычислительном центре Калифорнийского университета для машины СОС 6400. [c.31]

В дискретной задаче для расчета экономически оптимальных допусков применяют линейное программирование с дискретными переменными в общем и линейное программирование с переменными,, имеющими значение нуля или единицы известен ряд алгоритмов суммирования допусков, и могут быть использованы вычислительные машины. Из частных алгоритмов с переменными, равными либо нулю, либо единице, в отрасли эффективны алгоритмы суммирования 0—1 Балаша, Гомори. Программы этих алгоритмов предусматривают математическую модель допусков вида [c.76]

Задачи на составление планов О. и. п. м. решаются на практике симплексныл1 методом линейного программирования, по большей части с использованием цифровых электронно-вычислительных машин. [c.113]

Главными видами П. м. являются линейное программирование, нелинейное программирование, динамическое программирование (см. Программирование динамическое). П. м. следует отличать от программиропания для цифровых вычислительных машин. Последнее представляет собой реа.лиза-цию выбранного метода решения задачи в виде программы для [c.317]

Функция желательности. Задачу оптимизации процессов, ха-ракгеризующихся несколькими откликами, обычно сводят к задаче оптимизации по одному критерию с ограничениями в виде равенств или неравенств. В зависимости от вида поверхности отклика и ха-ракгера ограничений для оптимизации предлагается использовать методы неопределенных множителей Лагранжа, линейного и нелинейного программирования, ридж-анализ [10] и др. К недостаткам этих способов решения задачи оптимизации следует отнести вычислительные трудности. В частности, при описании поверхности отклика полиномами второго порядка решение задачи на условный экстремум с применением неопределенных множителей Лагранжа приводит к необходимости решать систему нелинейных уравнений. Поэтому одним из наиболее удачных способов решения задачи оптимизации процессов с большим количеством откликов является использование предложенной Харрингтоном [23] в качестве обобщенного критерия оптимизации так называемой обобщенной функции желательности О. Для построения обобщенной функции желательности О предлагается преобразовать измеренные значения от- [c.207]

Справочник химика 21

Химия и химическая технология