Линейное программирование задачи

Задача линейного программирования в общей форме найти экстремум линейной функции [c.322]

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

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

Симплексный метод решения задач линейного программирования [c.427]

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

Синтез базовой теплообменной системы. Рассмотрим вначале случай, когда числа холодных и горячих потоков равны N = М, а число теплообменников также равно N. Покажем, что при сделанных предположениях задача синтеза ТС может быть сведена к специальной задаче целочисленного линейного программирования — задаче о назначениях [127, с. 405]. Введем двоичные переменные х-, следующим образом [c.215]

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

ПРИНЦИП ДВОЙСТВЕННОСТИ и ЗАДАЧАХ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ [c.460]

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

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

Для лучшего понимания излагаемого материала необходимо ввести понятие о задачах линейного программирования по крайней мере в двух формах. [c.322]

Постановка задач линейного программирования и их геометрическая интерпретация [c.414]

Для того чтобы привести задачу линейного программирования в общей форме к канонической, необходимо ввести так называемые дополнительные или вспомогательные переменные Хп+ъ л+2, . м п+(й—т), причем эти переменные неотрицательны. — Прим. ред. [c.322]

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

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

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

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

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

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

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

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

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

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

В задачах линейного программирования обычно иредполагается, что все независимые переменные х,- неотрицательны, т. е. вместе с условиями (VH1,2) должны также выполняться условия неотрицательности значений величии Xj [c.414]

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

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

Е5 дальнейшем предполагается, что рассматриваются такие задачи линейного программирования, для которых оптимальное значение линейной формы (VI 11,34) достигается в одной из вершин многогранника условий, описываемого неравенствами (VIII,35) и (VIII,36). [c.424]

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

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

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

В оптимальном решении значение искусственной переменной Хп+т+1 должно быть В ТОЧНОСТИ равно нулю, для чего необходимо, чтобы базисный вектор, соответствующий этой переменной, был исключен из окончательного базиса. При использовании симплексного метода в этом случае необходимо предусмотреть специальный коптрол . за исключением базисного вектора, отвечающего искусственной переменной л л+от+1> что вносит определенные неудобства при ре1ненни задач линейного программирования на вычислительных машинах. [c.445]

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

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

B i iie уже отмечалось, что основной объек в[.1числений при реше-н 1и задач линейного программирования приходится на расчеты, связанные с определением обратных матриц для получаемых на каждом шаге базисов. При использовании общих методов для задач высокой размерности, т. е. с большим числом независимых переменных, объем вычислений, приходящийся на обращение матриц порядка гп, возрастает быстрее, чем /п , что может существенно увеличить общее время решения оптимальной задачи. Поэтому представляет особый интерес применение методов вычисления обратных матриц, основанных на свойствах последовательности базисов, получаемой при использовании симплексного метода. [c.447]

В дальнейшем предполагается, что исходная постановка задачи линейного программирования представлена в форме максимизации критерия оитимальности, заданного в виде [c.453]

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

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

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

Маргинальные значения Vi , описываемые соотношениями (VI 11,223), кроме этой чисто вспомогательной роли, представляют самостоятельный интерес в связи с так называемым принципом двойственности в задачах линейного программирования. Он заклю-чается в следуюн1,ем [c.460]

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

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

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