Cтраница 3
В задачах оптимального планирования нефтеперерабатывающих производств система ограничений (2.18) является смешанной и включает как равенства, так и неравенства. В совместной системе в конечном счете все искусственные переменные должны быть выведены из начального базиса. При решении задач с фиксированными коэффициентами несовместность системы ограничений, которая в принципе может быть устранена учетом условий варьируемости, может выявиться на некоторой г-й итерации. Данное обстоятельство и может быть использовано для улучшения эффективности расчетной процедуры. [31]
Этот этап является первой повторяющейся частью программы. Он автоматически пропускается машиной, когда все искусственные переменные исключены. Итерации, состоящие в исключении искусственных переменных, образуют первый шаг ( фаза /) вычисления. Искусственные переменные с самого начала различаются с помощью специальных индексов, которые приписываются элементам вектора р; по мере исключения искусственных переменных эти индексы в элементах вектора ( р) уничтожаются. Создание вектора [ / г ] состоит в формировании в зоне 4 вектора, компоненты которого равны нулю для элементов вектора ( 5), не имеющих специального индекса, и очень большие по модулю отрицательные величины для всех тех элементов вектора ( 5), которые имеют эти индексы. Таким образом, при последующем вычислении вектора [ dj выбору искусственных переменных отдается предпочтение. [32]
Назначение этого слагаемого состоит в том, чтобы в ходе решения задачи (11.5) - (11.7) вывести искусственные переменные из состава базисных. Если в результате решения задачи окажется, что искусственные переменные входят в состав базисных и их значения не равны нулю, то это означает, что ограничения (11.2) несовместны. [33]
В этой задаче начальное допустимое базисное решение всегда имеется и легко находится. Дальнейшие вычисления можно проводить двумя путями: сохраняя искусственные переменные до конца ( вводя строку коэффициентов при gz или задавая для конкретных задач достаточно большое реальное gz) или первоначально решив вспомогательную задачу минимизации суммы искусственных переменных. [34]
В ходе вычислений искусственные переменные исключаются. Система не имеет решения, если нельзя исключить все искусственные переменные. Число неисключенных искусственных переменных определяет невязки неудовлетворенных уравнений. [35]
Если существует допустимое решение исходной задачи, то очевидно, что данная вспомогательная задача минимизации имеет решение с наименьшим значением, равным нулю. Иначе говоря, допустимое решение исходной задачи получается только тогда, когда все искусственные переменные равны нулю. Иными словами, некоторые dj остаются базисными в оптимальном решении вспомогательной задачи. [36]
Задача максимизации путем умножения коэффициента оценки на - 1 может быть превращена в задачу минимизации. Было найдено, что V должно быть равно нулю; так как это будет в большинстве случаев, то опустим все неосновные искусственные переменные и сосредоточимся на первоначальной целевой функции. [37]
Вырожденность базиса практически не влияет на число итераций, требуемое для нахождения решения задачи линейного программирования. Опыт показывает, что при решении большинства практических задач число итераций, необходимое для получения окончательного результата, лежит в пределах от i.5 m до Зт, где т - число ограничений ( Данная оценка справедлива лишь в том случае, если исходный базис содержит только свободные или искусственные переменные. [38]
Как видно из данной таблицы, дальнейшее улучшение решения невозможно, так как во 2 - й индексной строке не оказалось отрицательных элементов. Следовательно, достигнуто оптимальное решение Л1 - задачи. Но искусственные переменные 5 и хв не выведены из базиса, следовательно, исходная задача не имеет решения, так как система ограничений ее несовместна в области допустимых решений. [39]
Как видно из данной таблицы, дальнейшее улучшение решения невозможно, так как во 2 - й индексной строке не оказалось отрицательных элементов. Следовательно, достигнуто оптимальное решение М - задачи. Но искусственные переменные хь и xs не выведены из базиса, следовательно, исходная задача не имеет решения, так как ее система ограничений несовместна в области допустимых решений. [40]
Если ограничения задачи ЛП несовместны ( т.е. они не могут выполняться одновременно), то задача не имеет допустимых решений. Такая ситуация не может возникнуть, если все неравенства, составляющие систему ограничений, имеют тип с неотрицательными правыми частями, так как в этом случае дополнительные переменные могут составить допустимое решение. Для других типов ограничений используются искусственные переменные. И хотя в оптимальном решении все искусственные переменные в силу штрафов равны нулю, такой исход возможен только тогда, когда задача имеет непустое пространство допустимых решений. В противном случае в оптимальном решении будет присутствовать хотя бы одна положительная искусственная переменная. [41]
Поскольку искусственную часть целевой функции и косвенной стоимости можно отделить от действительной части этих чисел, в таблицу вводится дополнительная строка. Пять таблиц, помещенные на стр. Обратите внимание, что, пока искусственные переменные присутствуют в решении, в базис следует вводить вектор с максимальной искусственной частью косвенной стоимости. Поскольку искусственные переменные нельзя повторно вводить в базис, мы их удалим из таблиц, как только они исчезнут. Элементы, обведенные кружками, - это опорные элементы. [42]
Сформулированная задача решается следующим образом. Определяют любое начальное базисное решение задачи (18.1) - (18.3) и вычисляют матрицу, обратную матрице В, составленной из базисных векторов. Если начальный базис найти трудно, то вводят искусственные переменные. [43]
Наиболее общим способом построения начального допустимого базисного решения задачи ЛП является использование искусственных переменных. Эти переменные в первой итерации играют роль дополнительных остаточных переменных, но на последующих итерациях от них освобождаются. Разработано два тесно связанных между собой метода нахождения начального решения, которые используют искусственные переменные: М - метод5 и двухэтапный метод. [44]
Однако возможна ситуация, когда в конце первого этапа искусственные переменные останутся в базисе, но будут иметь нулевые значения. В этом случае такие переменные при необходимости будут формировать часть начального базисного решения для второго этапа. При этом необходимо так изменить вычисления, выполняемые на втором этапе, чтобы искусственные переменные никогда не смогли принять положительные значения ни в каких итерациях симплекс-метода. [45]