А.Г.Трифонов.

Основной алгоритм.

Алгоритм симплексного метода включает в себя две фазы:

Фаза 1. - Расчет начальной основной допустимой точки.

Фаза 2. - Расчет оптимального решения согласно поставленной задаче.

Примечание. Применительно к программе linprog нельзя принимать исходную точку х0 для расчета по алгоритму симплексного метода. Если все же х0 будет передано в качестве входного аргумента, то программа linprog игнорирует эту точку х0 и расчитывает свою собственную начальную точку.

Фаза 1. При выполнении фазы 1 в данном алгоритме определяется начальное основное допустимое решение (см. определения из раздела Основные и неосновные переменные) посредством решения кусочно-правильной вспомогательной задачи линейного программирования. Целевая функция этой вспомогательной задачи является линейной штрафной функцией

,

где члены P_j(x_j) определены как

P(x) служит мерой того, как много точка х переступает нижний и верхний граничные условия. А вспомогательная задача будет

Исходная задача имеет допустимую базисную точку тогда и только тогда, когда вспмогательная задача имеет равное нулю минимальное значение.

В данном алгоритме ничальная точка для вспомогательной задачи определяется с помощью эвристического метода, который по мере необходимости добавляет неактивные и искусственные переменные. Далее согласно выбранному алгоритму эта начальная точка используется совместно с симплексным алгоритмом для решения вспомогательной задачи. Такое оптимальное решение, в свою очередь, является начальной точкой для фазы 2 основного алгоритма.

Фаза 2. Согласно фазе 2, для решения исходной поставленной задачи в данном алгоритме используется симплексный алгоритм, начиная уже с начальной стартовой точки фазы 1. На каждой итерации в данном алгоритме проводится проверка условии оптимальности и задача останавливается в случае, если текущие решения оказывается оптимальным. Если текущее решение не оптимально, то согласно данному алгоритму проводятся следующие действия:

• Выбирается одна переменная, называемая как вводимая переменная, из небазисных переменных и добавляется соответствующая колонка из небазисного вида в рассматриваемый базисный вид (в соответствии с принятыми определениями см. раздел Базисные и небазисные переменные).

• Выбирается некая переменная, (так называемая исключаемая переменная) из набора базисных переменных и из базисного набора удаляется соответствуюшая колонка.

• Проводится корректировка текущего решения и значения текущей цели.

Выбор вводимых и исключаемых переменных производится путем решения двух систем линейных уравнений, при сохранении свойства допустимости решения.

Предварительная подготовка.

В алгоритме симплексного метода используются те же самые подготовительные операции, что и в решателе задачи линейного программирования для алгоритмов большой размерности, как это отмечено в одноименном разделе. Дополнительно, в данном алгоритме используются еще две операции:

Исключаются колонки, которые имеют только один ненулевой элемент, а так же исключаются их соответствующие строчки.

Для каждого уравнения из числа ограничений , где a есть строчные елементы для Aeq, в данном алгоритме для линейной комбинации в виде rlb и rub, рассчитываются нижняя и верхняя границы. Такой подход является справедливым в случае конечных значений нижней и верхней границ. Если или rlb или rub равно b, то эта константа называется принудительным ограничением. В данном алгоритме каждый раз устанавливается некая переменная соответствующая ненулевоиу коэффициенту из , равному его верхней или нижней границе в зависимости от принудительного ограничения. Далее согласно алгоритму удаляются колонки, соответствующие этим переменным, а так же удаляются соответствующие принудительным ограничениям строчки.

Использование симлексного алгоритма.

Для того, что бы установить использование алгоритма симплексного метода, следует установить опционные параметры следующего типа

'LargeScale' в 'off' и 'Simplex' в 'on'.

options = optimset('LargeScale', 'off', 'Simplex', 'on')

Далее вызывается функция linprog с соответствующими входными опциями и аргументами. Детали использования функции linprog приведены соответсвующем разделе.

В ситуации если программа определит недопустимость или наличие неограниченнности при выполнении процедуры предварительной подготовки данных, то Linprog возвращает пустые выходные аргументы на месте x и fval. Linprog возвращает значение текущей точки в ситациях, когда

• Есть превышение максимального числа итераций.

  Будет определено, что поставленная задача является невыполнимой или не имеющей границ относительно фаз 1 и 2.

• Когда задача не имеет предельных границ, то linprog возвращает значения x и fval относительно направления отсутствия предельных границ.

Основные и неосновные переменные.

В данном разделе дается определение таких терминов, как базис, небазис и базисное допустимое решение для задачи линейного программирования. Для данных определений примем, что поставленная задача имеет следующий стандартный вид:

(Отметим, что A и b не являются некими матрицей или вектором, определяющими неравенства в исходной задаче). Предположим, что A есть матрица размерностью m-х-n с рангом m < n и соотвествующими колонками {a₁, a₂, ..., a_n}. Примем, что является пространством колонок A, с набором индексов B = {i₁, i₂, ..., i_m} и N = {1, 2, ..., n}. N является дополнением B. Субматрица A_B есть так называемый базис, а дополнительная субматрица A_N есть так называмый небазис. x_B есть вектор базисных переменных и x_N есть вектор небазисных переменных. При выполнении каждой итерации фазы 2 данного алгоритма производится замена одной колонки текущего базиса на колонку небазиса и, соответственно, корректируются переменные x_B и x_N.

Если х есть решение системы и все небазисные переменные для x_N равны или их нижней или верхней границе, то х называется базисным решением.

Литература

[1]  Chvatal, Vasek, Linear Programming, W. H. Freeman and Company, 1983.

[2]  Bixby, Robert E., "Implementing the Simplex Method: The Initial Basis," ORSA Journal on Computing, Vol. 4, No. 3, 1992.

[3]  Andersen, Erling D. and Knud D. Andersen, "Presolving in Linear Programming," Mathematical Programming, Vol. 71, pp. 221-245, 1995.

Многокритериальная оптимизация

Достаточно часто в реальных ситуациях качество эксплуатации исследуемого объекта или системы оценивается не единственным критерием или показателем качества (см. параметрическую оптимизацию уравнение 3-1), а совокупностью таких критериев, причем представляющих одинаково значимыми. Такая постановка задачи приводит к задаче оптимизации с векторной целевой функцией , которая должна трактоваться неким определенным образом. Как правило, относительная значимость этих целей в общем неизвестна до тех пор, пока не будут определены все основные свойства системы и не будут полностью истолкованы все возможные взаимосвязи. По мере того, как число возможных целей возрастает, то, очевидно, что эти взаимосвязи образуют сложную структуру и их становятся труднее идентифицировать. В данном случае многое зависит от интуиции исследователя и его или ее умения точно выражать те или иные предпочтения в процессе оптимизации. Таким образом, стратегия построения многокритериальной оптимизации состоит, прежде всего, в способности адекватно определить постановку задачи так, что бы эта задача допускала свое решение, а также выразить необходимые предпочтения в виде числовых зависимостей и сохранив при этом реальность поставленной задачи.

Далее приводятся следующие тематические разделы:

• Введение в многокритериальную оптимизацию, где уделяется внимание множеству альтернативных методов.

• Обсуждение метода достижения цели, который можно рассматривать как задачу нелинейного программирования.

• Алгитмическое улучшение метода SQP, с целью его применения в методе достижения цели.

Введение в многокритериальную оптимизацию

Многокритериальная оптимизация представляет собой минимизацию некого вектора целей F(x), на которой могут быть наложены дополнительныеограничения или предельные значения:

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

при ограничениях

Отсюда возможно опредлить соответствующую область допустисых решений для пространства целевых функций .

В двумерном случае, как это представлено на Рисунке 3-7, вектор характеристик F(x) отображает параметрическое пространство в пространство целевых функций

Рисунок 3-7. Отображение параметрического пространства а пространство целевых функций

Точка неулучшаемого решения может быть определена как:

Определение. Точка является неулучшаемым решением, если для некоторой окрестности нет некого такого, что и

Для двухмерной интерпретации Рисугка 3-8. Множество неулучшаемых решений, Множество точек неулучшаемых решений лежит на кривой между точками С и D. Точки А и В представляют специфичические неулучшаемые точки.

Рисунок 3-8. Множество неулучшаемых решений

Точки А и В являются безусловными точками неулучшаемых решений, поскольку любое улучшение для одной цели вызывает ухудшение для другой выбранной цели , т.е.

.

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