Cтраница 3
Симплексный метод называют методом быстрейшего подъема вдоль ребер. Имеются в виду ребра многогранника n - мерного пространства, образованного системой ограничений задачи. [31]
W-i U Wz играют роль уставок и непосредственно используются при решении задачи оперативного управления в качестве известных параметров модели - ограничений по ресурсам на сутки Ran и оперативно-суточных плановых заданий Рт. С учетом указанных при выделении задачи оперативно-календарного планирования мероприятий, направленных на обеспечение совместности системы ограничений задачи оперативного управления, такой подход обеспечивает согласование на двух нижних уровнях временной иерархии. [32]
Затем описанная процедура повторяется с очередной задачей линейного программирования, система ограничений которой содержит на одно неравенство больше, чем исходная задача. Решение полученной задачи вновь проверяется на целочиеленность, и, если возникает необходимость, к системе ограничений задачи вновь добавляется линейное неравенство. Если правило формирования дополнительных ограничений разработано удовлетворительно, то через некоторое число этапов процедура завершится. Будет найдено решение целочисленной задачи либо очередная система линейных неравенств окажется противоречивой. В последнем случае будет зафиксирована несовместимость условий исходной задачи. [33]
Рассмотрим теперь случай несовместности, выявленной при решении задачи линейного программирования ( модуль С1) на каком-либо шаге решения общей задачи оперативно-календарного планирования. Если и это не приведет к поиску оптимального решения на всем горизонте планирования, констатируется несовместность системы ограничений задачи оперативно-календарного планирования, и дальнейший поиск решения осуществляется после коррекции задачи человеком. [34]
Рассмотрим теперь вопросы о численном решении задачи линейного программирования, которую в дальнейшем будем считать невырожденной. Прежде всего, это означает, что система уравнений (2.5) линейно независима ( rang Л л), а система ограничений задачи (2.1) - совместна. Таким образом, мы предположили, что многогранное множество, описываемое системой ограничений задачи (2.1), имеет угловые точки. [35]
Решив задачу симплексным методом, получим Q ( 117 44; 73 75; 61; 61; 61; 68; 98; 117 08) - несимметричное решение. Подставив вектор Q ( 117 08; 68 98; 61; 61; 61; 73 75; 117 44) в систему ограничений задачи, убеждаемся, что он является ее решением. [36]
Из рис. 1.2 видно, что максимальное значение целевая функция принимает в любой точке отрезка АВ. На рис. 1.3 изображен случай, когда целевая функция не ограничена сверху на множестве допустимых решений, а на рис. 1.4 - случай, когда система ограничений задачи несовместна. [37]
Существует группа алгоритмов ( методов) решения задаялинейного программирования, основанных на том, что сначала отыскивается оптимальный план, хотя бы удовлетворяющий некоторым из ограничений; он проверяется на допустимость и постепенно доводится до такого состояния, когда одновременно удовлетворяет критерию оптимальности и является допустимым с точки зрения всей системы ограничений задачи. Такой принцип в известном смысле противоположен методам последовательного улучшения допустимого решения, описанным в ст. Базисное решение ( опорный план), когда вначале определяется некоторый допустимый базисный план, а затем он постепенно улучшается, пока не становится оптимальным. [38]
Однако при практическом использовании точных математических методов в том приложении, какое им дано в указанных выше работах, встречаются известные трудности. Во-первых, в имеющихся математических моделях задачи построения производственной программы не учитывается ряд важных планово-организационных требований таких, например, как необходимость непрерывного и равномерного производства одного изделия в смежных месяцах, необходимость концентрации производства конструктивно-однородных изделий и др. Во-вторых, алгоритмы и методы, полнее учитывающие реальные производственные условия, требуют значительного увеличения системы ограничений задачи. При этом для большинства реальных задач разрешаемая матрица имеет столь значительную размерность, операция с которой требует применения весьма мощных ЭВМ. [39]
Действительно, если газопроводная система содержит точку с нулевым узловым расходом газа, то для всех участков системы, связанных с такой точкой, соответствующие неравенства (5.2.2) будут тождественно совпадать. Более того, эти неравенства совпадают для всех участков, которые могут быть соединены цепью, проходящей через точки с нулевыми узловыми расходами. Поэтому в системе ограничений задачи достаточно сохранить лишь одно неравенство типа (5.2.2) для одного из таких одновременно идентифицируемых участков системы. [40]
Аналогичные зависимости могут быть получены, когда меж-цу основными аппаратами системы находятся промежуточные гмкости, согласующие их работу. Чтобы сформировать эти модели, необходимо в систему ограничений задачи синтеза одно-продуктовой системы с промежуточными емкостями ( см. предыдущий раздел) внести индекс i, соответствующий номеру продукта. Если продукты при этом производятся последовательно, то в условии выполнения плана появится знак суммы. [41]
Однако при решении инженерных задач переменные могут иногда принимать и отрицательные значения. Система ( 2) вместе с условиями неотрицательности называется системой ограничений задачи. [42]
Рассмотрим теперь вопросы о численном решении задачи линейного программирования, которую в дальнейшем будем считать невырожденной. Прежде всего, это означает, что система уравнений (2.5) линейно независима ( rang Л л), а система ограничений задачи (2.1) - совместна. Таким образом, мы предположили, что многогранное множество, описываемое системой ограничений задачи (2.1), имеет угловые точки. [43]
Так, задачи V и VI могут решаться 1 раз в месяц без коррекции величин qkt в течение месяца, если в такой коррекции не-возникает необходимость, а VII - еженедельно, причем каждый раз используется график суточных пропускных способностей qi t, рассчитанный в начале месяца. Таким образом, согласование задач оперативно-календарного планирования в течение месяца, как правило, реализуется заданной последовательностью их решения без использования итераций. Обратная связь от задачи VII к V, изображенная на рис. V-5, соответствует случаю, когда система ограничений задачи VII оказывается несовместной. При этом организуется итерационный цикл, в котором информация о несовместности инициирует коррекцию решения задач V и VI. [44]
Как видно, задачи ( 66) - ( 68) и ( 69) - ( 71) образуют симметричную пару двойственных задач. Решение прямой задачи дает оптимальный план производства изделий А, В и С, а решение двойственной - оптимальную систему оценок сырья, используемого для производства этих изделий. Чтобы найти решение этих задач, следует сначала отыскать решение какой-либо одной из них. Так как система ограничений задачи ( 66) - ( 68) содержит лишь неравенства вида, то лучше сначала найти решение этой задачи. [45]