Линейное программирование с ограничениями

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

Исключение ограничений типа равенств в исходной постановке задачи линейного программирования. Наличие т—т. ограничений типа равенств (УП1,6в) в исходной постановке задачи линейного [c.418]

Если в исходной постановке оптимальной задачи линейного программирования имеются ограничения типа равенств (УП1,6в), то их можно прямо включить в ограничения (УП1,42). При этом следует только принимать во внимание, что число дополнительных переменных уже не равно числу ограничений т, а определяется числом неравенств т. . [c.423]

Общие замечания относительно решения задачи линейного программирования с ограничениями типа равенств, полученными введением дополнительных переменных. С учетом ограничений тииа уравнений (УП1.42) уже можно говорить о решении оптимальной задачи как о совокупности неотрицательных значений переменных [c.423]

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

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

Нахождение оптимума функции (V,5) при нелинейных ограничениях (V,6a) связано со значительными вычислительными трудностями, которые осложнены наличием булевых переменных (V,66). Поэтому желательно нелинейные ограничения заменить ограничениями в виде линейных неравенств, что позволит использовать некоторые методы дискретного линейного программирования. Для этого необходимо осуществить следующие преобразования в приведенной ниже последовательности. [c.205]

Изложенная методика позволяет преобразовать нелинейные уравнения математической модели обобщенной гипотетической стр>"ктуры НПЗ к виду, удобному для решения методами дискретного или целочисленного линейного программирования. Преобразование нелинейных уравнений (представляющих уравнения математической модели структуры НПЗ) в линейные сопровождается перечислением всех возможных альтернативных вариантов технологической схемы НПЗ, что может привести к резкому увеличению размеров задачи. Так, для рассмотренных выше 25 технологических процессов нефтепереработки преобразование [без учета ограничений (У,21а)] приводит к задаче дискретного программирования, содержащей более 10 независимых дискретных переменных. [c.214]

Решают две граничные задачи линейного программирования (ЗЛП) первую задачу решают с дополнительным ограничением Хк = [c.222]

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

Для решения задачи линейного программирования (4.3.12) — (4.3.14) в [64] применяется специальная итерационная процедура, нестандартность которой заключается в том, что она требует задания такого набора векторов, выпуклая комбинация которых хорошо аппроксимировала бы множество допустимых вариаций OU. Кроме того, необходимо задание ограничений на коэффициенты линейной комбинации, аппроксимирующей вариацию управления ou t), i T. Значения этих коэффициентов определяют также окрестность управления u t), t .T, в которой линеаризованная задача (4.3.9) — (4.3.11) является допустимым приближением исходной задачи, т. е. линейные члены разложения функционала остаются главными. [c.196]

Для решения задачи (4.3.11) —(4.3.13) можно применить и другие алгоритмы линейного программирования [61, 66], которые хорошо учитывают специфику ограничений этой задачи. Рассмотрим иной способ решения задачи (4.3.8) — (4.3.10), не требующий ее сведения к задаче линейного программирования и строящий выпуклые комбинации вариации Ьи непосредственно в пространстве управлений. Пусть (г + 1)-мерная вектор-функция y t) = yo t),yi t).....yr t)) является решением системы [c.196]

Задача линейного программирования сводится к нахождению экстремума линейной функции нескольких независимых переменных с учетом ограничений в виде системы линейных неравенств, в которые входят независимые переменные. При этом предполагается, что значения независимых переменных не отрицательны [74, 75]. [c.181]

Допустимым решением задачи линейного программирования называется вектор л = ( 1, 2,. .., Хп), удовлетворяющий ограничениям типа (У.5) и условиям неотрицательности (У.б). [c.183]

Прямая и двойственная задачи линейного программирования интересны как теоретически, так и практически. В табл. V.2, где показаны эти двойственные отношения, параметры Лх,. .., я, являются двойственными переменными. Важно отметить, что существует прямое отношение между я и исходным ограничением i с правой частью bi, а также между переменной / в исходной задаче и ограничением / в двойственной (с правой частью ). В табл. V.3 указаны эти отношения. Величина Ai в табл. V.3 обозначает -ю строку матрицы А. [c.191]

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

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

Таким образом, в рассматриваемой системе для целей оптимизации ХТС комплексно используются идеи линейного программирования, методы однопараметрического и многопараметрического поисков и методы учета ограничений (метод модифицированной функции Лагранжа, метод приведенного градиента). [c.236]

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

Если задан вид целевой функции и и известны постоянные Ь,-и С,-, то подобные задачи оптимизации с ограничениями называют математическим программированием. Если целевая функция и функции ограничения являются линейными, то задачи программирования называют задачами линейного программирования. Часто отсутствуют ограничения (т = 0) и оптимальное значение целевой функции можно найти достаточно просто методами определения экстремальных значений функции [c.68]

На последнем шаге решения задачи линейного программирования получаем матрицу существенных ограничений [c.98]

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

Все эти ограничения нри линейном программировании вводятся в задачу в виде линейных уравнений и составляют систему линейных [c.87]

Для всех варьируемых векторов Яу (/=1, Й ) формулируются и решаются следующие подзадачи линейного программирования найти а - > О (г =1,т), максимизирующие fj и удовлетворяющие ограничениям т [c.31]

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

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

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

В общем случае произвольного числа п независимых переменных наглядная геометрическая интерпретация реп1епия задачи линейного программирования отсутствует. При этом область допустимых значений независимых переменных в п-мерном пространстве является многогранником, ограниченным гиперплоскостями, уравнения которых задаются ограничениями (УП1,6) на независимые переменные. [c.418]

В рассмотренном примере У1П-2 число ограничений типа равенств было на единицу меньше числа независимых переменных исходной задачи максимизации линейной формы (VIII,21), что позволило получи ь в конечном итоге одномерную задачу, решение которой очевидно. Разумеется, что в обидем случае исключение части независимглх переменных за счет наличии в системе ограничений условий типа равенств может и не привести к существенному упрощению решении задачи. Однако при этом возможно и некоторое уменьшение чис,ла ограничений отбрасыванием более слабых неравенств из общего числа первоначальных и вновь получаемых при исключении рида переменных. Общие замечания относительно решения задачи линейного программирования с ограничениями типа неравенств. Как показано выше, задача с ограничениями ти[[а неравенств и равенств может быть сведена к задаче с ограничениями только типа неравенств, т. е. можно считать, что оптимальная задача сформулирована как задача максимизации критерия [c.421]

Иа практике случаи вырождения, о которых несколько подробнее идет речь ниже (см. стр. 459), встречаются весьма редко. Поэтому далее рассматриваются только невырожденные задачи линейного программирования, для которых оптимальное значение линейной формы достигается в одной из вершин многогранника условий, определяемой пересечением ровно п гиперплоскостей, соответствующих ограничениям (VIII,35) и (VIII,36). [c.424]

Д )угпми словами, имеется только т отличных от нуля значений переменных среди общего числа п - пг переменных, для которых задача линейного программирования сформулирована как задача оптимизации критерия (VIII,43) с учетом ограничений (VIII,42). [c.426]

Ниа е рассматривается процедура построения искусственного базиса для различных типов ограничений в оби1,ей постановке задачи линейного программирования. [c.443]

Случай 4. Среди ограничений исходной задачи линейного программирования имеются ограничения типа равенств (У111,2в). [c.446]

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

Общий объем памяти, требуемый для размещения числовой ин-фэрмации при решении задачи линейного программирования с п + т П ременцымн и т ограничениями типа (VIII,195), исключая память, [c.458]

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

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

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

Если параметры вектора не удовлетворяют требованию целочисле ност , то решение Хо декомпозируется н два jioBbix решения Xi и Х2. Если все решения, следующие за Xi и Х2, недопустимы, то осущ твляется повторная декомпозиция на базе исходного решения Ха решаются две граничные задачи линейного программирования с дополнительными ограничениями Xk = = л м1—1 и Xk2= Xko +2. Любая /-я вершина дерева вариантов решений (см. рис. 8.3) с нецелочисленным Xkt может иметь много вершин-потомков, соответствующих решениям граничных ЗЛП с дополнительными ограничениями Xk,i+ = Xkj, Xk,j+2= = 1,..., Xk,i+r= Xki + , Xk,i+r+i= Xki +2,... В процес- [c.222]

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

Наиболее часто линейное программирование применяют для решения технико-экономических задач. Суть последних состоит в нахождении набора параметров технологического процесса, который удовлетворяет ограничениям на ресурсы, плановым заданиям и максимиризует при этом доход предприятия [76, 77]. [c.195]

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

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