Задача линейного программирования

Отметим, что основные затраты машинного времени на реализацию алгоритма связаны с анализом чувствительности. Анализ чувствительности методом приращений требует л+1 раз обращаться к математической модели объекта. Первое обращение производится при значении вектора управляемых параметров 1)э и позволяет вычислить г//(1)д), фигурирующие в (6.51). Каждое последующее обращение позволяет вычислить очередную строку матрицы чувствительности и в итоге дает значения Uji. Теперь полностью определена линеаризованная модель объекта (6.53). Манипулирование ею при решении задач линейного программирования не требует заметных затрат машинного времени. [c.296]

Если в сформулированной задаче ограничения (6.64) отсутствуют, то имеет место классическая задача линейного программирования, если ограничения (6.64) имеются и р = т, то данная задача является полностью целочисленной, при р<т задача является частично целочисленной. [c.308]

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

Заметим, что текущее решение задачи линейного программирования не удовлетворяет ограничению (6.69), поскольку значение Xm+i=—fib,) строго отрицательно. [c.312]

Найти оптимальное решение задачи линейного программирования (6,61)—(6.63) без условия целочисленно-сти (6.64). [c.312]

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

Метод ветвей и границ основан на решении некоторого множества задач линейного программирования, Границы [c.313]

Алгоритм решения задачи целочисленного программирования методом ветвей и границ заключается в следующем. На каждой итерации (обозначим номер итерации через t) имеются нижняя оценка F K) оптимального значения целевой функции и список задач линейного программирования, подлежащих решению. Процедура решения состоит в последовательном улучшении оценки F (X) и приближении ее к оптимальному значению [c.314]

ГО вида, получаемых из -ои партии по /-му варианту х - — число единиц -ой партии, раскраиваемое по/-му варианту г — количестве полных комплектов заготовок. Решаем задачу линейного программирования г - шах при ограничениях [c.48]

Для упрощения анализа в работе [5] была дискретизирована задача, причем допустимое расположение узлов фермы было ограничено точками прямоугольной сетки, расположенными на горизонтальных расстояниях I и вертикальных расстояниях h (рис. 2, а). Оказалось, что при этом оптимизация сводится к задаче линейного программирования. Оптимальное очертание зависит от значений отношений hjl и PjQ. На рис. 2, б — 2, г представлены очертания при hll = l и P/Q = 0 0,5 2,0. [c.91]

Методы линейного программирования. Методы линейного программирования предназначены для решения специального подкласса задач типа Д, в котором целевые функции и функции ограничений линейно связаны с параметрами оптимизации [83]. Типичную задачу линейного программирования для случая максимизации целевой функции можно сформулировать так (назовем ее задачей Е) [c.238]

Рис. П.1. Схема интерпретации задачи линейного программирования

Выбор наилучших величин S с учетом всех видов ограничений (равенств и неравенств) в малой окрестности Zn можно осуществлять по аналогии с методами локальной аппроксимации. Простейшая линейная аппроксимация с помощью разложения в ряде Тейлора приводит к выражениям типа (П.15) для целевой функций и ограничений. Учитывая постоянство функций и частных производных, определенных в фиксированной точке Zh, и подставляя полученные выражения Но к Hj в задачу Д, получаем следующую задачу линейного программирования (назовем ее Ж) [c.249]

Рнс. п.9. Схема целочисленной задачи линейного программирования [c.259]

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

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

Теперь задача формулируется так найти max F из выражения (9.49) при условиях (9.50). Это задача линейного программирования. В данном случае она [c.206]

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

Последовательно для каждого возмущения (i = 1, N] осуществляется оптимальная корректировка рассматриваемого варианта развития ЭК решением задачи линейного программирования [c.407]

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

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

Формализация (17.9) является каноническим представлением задачи линейного программирования [14]. Такая задача эффективно решается при помощи симплекс-метода с использованием соответствующих стандартных программ для ЭВМ. В результате решения совокупности стандартных задач линейного программирования (17.9), отвечающих локальным областям параметров, определяется оптимальный вектор Р<,пт этих параметров, соответствующий минимальному значению критерия эффективности вида (17.8). Полученное решение может быть уточнено при помощи локальных методов поиска экстремума [81]. [c.276]

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

Задачу линейного программирования можно интерпретировать геометрически. В многомерном евклидовом пространстве с координатами Xj ограничения (2.24), (2.25) определяют некоторый выпуклый многогранник Q. Значение целевой функции (2.23) в некоторой точке можно рассматривать как уклонение этой точки от гиперплоскости [c.65]

Таким образом, геометрический смысл задачи линейного программирования заключается в отыскании такой точки в многограннике, которая наиболее (или наименее) уклонена от плоскости (2.27). Ясно, что эта точка совпадает с одной из его вершин. [c.65]

Заметим, что диаграмма возможных состояний в сущности является геометрической интерпретацией основной задачи линейного программирования [67], наиболее наглядной при ее рассмотрении в двумерном или трехмерном пространстве. [c.81]

Таким образом, задача сводится к задаче линейного программирования отыскание максимума линейной формы IS.W при некоторых ограничениях. [c.222]

Методы линейного программирования [4, 22]. Задача линейного программирования заключается в следующем найти значения переменных 2,. ..,Хп, которые удовлетворяют системе уравнений [c.164]

Таким образом, задача вписывания допусковой области в область работоспособности формулируется как задача линейного программирования [c.296]

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

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

Введение на шаге 3 отсекаю1дего ограничения (6.69) наряду с условием Xm+i>0 делает текущее решение задачи линейного программирования недопустимым. Отсечение [c.312]

Методы возврата. В этой группе методов имеются различные модификации. Наиболее распространенным среди них является метод ветвей и границ, который предназначен для решения частично целочисленных задач. Как и в методе отсечения, решение задачи начинается с отыскания оптимального решения задачи линейного программирования без учета условия целочисленности. Затем формируется семейство связанных, но различных задач линейного программирования. Термин возврат определяет специфический способ формирования и решения последовательности задач. [c.313]

К примеру, если при решении задачи линейного программирования получено лг1=2,6, то можно поставить и решить две задачи линейного программирования, причем в одну из них вводится согласно (6.71) условие 3 Xi Ui, а в другую — условие Li Xi Q. Предположим, что каждая из этих задач имеет оптимальное решение, удовлетворяющее условию целочисленности (6.64). Тогда решение, доставляющее большее значение целевой функции, является оптимальным решением исходной целочисленной задачи. [c.313]

На итерации t из списка выбирают и решают задачу линейного программирования. Если она не имеет допустимого решения или если полученное оптимальное значение целевой функции Р/opt (X) / <(Х), то нижняя оценка остается прежней и из списка выбирают очередную задачу для решения. Если полученное решение удовлетворяет условию целочисленности (6.64) и (X)>f<(X), то полученное оптимальное решение f/opt (X) на итерации t принимают в качестве нижней оценки для последующих итераций. Если полученное оптимальное решение -задачи линейного программирования не удовлетворяет условиям целочисленности (6.64), то выбирают нецелочисленную переменную Xj и решаемую задачу разбивают на две новые задачи линейного программирования путем введения в каждую из них по одному ограничению (6.71). [c.314]

На рис. П.9 показана схема задачи линейного программирования, на которук> наложены условия целочисленности переменных. При пренебрежении целочислен-ностью допустимая область решений заштрихована линиями, которые одновременно являются линиями равного уровня целевой функции. Оптимальное решение в этом случае достигается в точке А. При наложении условий целочисленности Ог определяется узловыми точками пунктирной решетки , принадлежащими заштрихованной области. Точка А уже является недопустимой. Из ближайших целочисленных точек Б, В, Г, Д допустимой является только точка Д. Однако округление до точки Д неправильно, так как наилучшее решение достигается в точке . Поэтому применение линейного программирования с последующим округлением опти-Zv мального решения в данном примере недопустимо. [c.259]

Решение задач в 8.2-8.4 основывается на использовании балансовых моделей, сводящихс 1 к задачам линейного программирования (ЛП), а также на использовании имитационных моделей задачи в 8.5 решаются с помощью методов потокового программирования. [c.404]

Аналогично изложенному можно представить в виде совокупности задач линейного программирования задачу параметрической оптимизации динамической модели с направленными связями но критерию эффективности (15.18). Ограниченное т-мерное пространство варьируемых параметров районируется в соответствии с выражениями (16.30). В каждой локальной области варьирования действительные части собственных значений расчетной динамической модели, принимая во внимание зависимости (16.32), представим в виде, аналогичном (17.7) [c.276]

Наиболее распространенным методом решения общей задачи линейного программирования в настоящее время является так называемый симплексный метод (симилекс-метод) [67, 187]. [c.65]

В такой формулировке (применительно к условиям предельного равновесия) при размере матрицы (2.33) или (2.34) задача линейного программирования решается с помощью ЭВМ симплекс-методом с использованием модифицированных жордановых исключений [67]. С учетом возможностей ЭВМ Минск-1 и Урал-2 при решении на основе программы симплекс-метода, составленной по алгоритму, данному в работе [67], можно иметь, соответственно, 12 и 16 расчетных сечений при размере матрицы (2.33), 19 и 26 — при размере (2.34). Здесь имелись в виду только внутренние запоминающие устройства. При расчете на БЭСМ-2 с применением магнитных барабанов возможности увеличиваются примерно до 40 расчетных сечений [99] при размере матрицы (2.33). [c.68]

Ржаницып А. Р. Двойственные задачи линейного программирования в расчете железобетонных пластинок и оболочек по предельному состоянию. В кн. III Всесоюзный съезд по теоретической и прикладной механике. Аннотации докладов . Изд. АН СССР. М., 1968. [c.126]

Если критерий представляет собой линейную функцию управлений, а ограничения являются набором линейных неравенств (уравнений) и процесс одноэтапный, то это — классическая задача линейного программирования. [c.164]

Энциклопедия по машиностроению XXL

Оборудование, материаловедение, механика и ...