Численные методы многомерной безусловной оптимизации.

Этот параграф посвящен методам решения задачи (2.1) в случае произвольной размерности пространства R ^N (N £ 1). Будут рассмотрены две группы классических методов минимизации. Первую группу составляют так называемые методы спуска. Наиболее важным среди методов второй группы является метод Ньютона и его модификации.

1. Направления убывания и общая схема методов спуска. Многие методы минимизации относятся к числу методов спуска. В методах спуска направление движения к минимуму на каждом шаге выбирается из числа направлений убывания минимизируемой функции.

Определение 2.2. Говорят, что вектор = (h ₁, h ₂,..., h_n) задает направление убывания функции f в точке x, если существует такое число a₀ > 0, что

f (x + a ) < f (х)

при всех 0 < a < a₀. Сам вектор также называют направлением убывания. Множество всех направлений убывания функции f в точке x будем обозначать через U (x, f).

Таким образом, если любой достаточно малый сдвиг из x внаправлении вектора приводит к уменьшению значения функции f, то Î U (x, f).

Заменив неравенство, фигурирующее в определении направления убывания, на противоположное, получим определение направления возрастания.

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

Теорема 2.4. Достаточное условие. Пусть функция f дифференцируемая в точке х Î R ⁿ. Если вектор удовлетворяет условию

то ` h Î U (x, f).

Необходимое условие. Если ` h Î U (х, f), то (Ñ f (x), ` h) £ 0.

Другими словами, теорема 2.4 утверждает, что вектор ` h задает направление убывания функции f, если он составляет тупой угол с вектором градиента f, указывающим, как известно из курса высшей математики, направление наискорейшего возрастания функции f. Доказательство этой теоремы можно найти в книге [1].

Итак, пусть требуется решить задачу (2.1):

f (x) ® min, x Î R ⁿ.

В cлучае n = 2 решению этой задачи можно дать геометрическую иллюстрацию. Уравнению x ₃ = f (x ₁, x ₂) соответствует поверхность в трехмерном пространстве. Если функция f (x) достигает локального минимума в точке, то поверхность x ₃ = f (x ₁, x ₂) в некоторой окрестности точки x * имеет форму чаши.

Геометрическая интерпрeтация двумерной задачи минимизации основана на понятии линии уровня. Напомним, что линиями уровня функции f (х ₁, х ₂) называют семейство линий плоскости R ², накоторых функция принимает постоянное значение. Если функция f (x) имеет в R ² единственную точку локального минимума x* = (x ₁*, x ₂*), то такая функция называется мономодальной. Взаимное расположение ее линий уровня имеет вид, изображенный на рис. 2.3. Мультимодальными называются функции, которые имеют более одного экстремума. Такова, например, функция f (x) = ((x ₁)² + (x ₂)² + 1)² - 4(x ₁)², имеющая две точки минимума (1, 0) и (-1, 0). Линиями уровня этой функции являются так называемые овалы Кассини, изображенные на рис. 2.4.

Рис. 2.3. Рис 2.4.

Общая идея методов спуска состоит в следующем. Чтобы найти точку x * локального минимума функции f (x), строят последовательность точек { x ^{( k )}} (k = 0, 1, 2, …), сходящуюся к точке х*, таким образом, чтобы последовательность значений функции f (х ^{( k )}) была монотонно убывающей и ограниченной:

f (x ⁽⁰⁾) ³ f (x ⁽¹⁾) ³ … ³ f (x ^(k)) ³ … ³ f (x *).

Геометрически алгоритм решения задачи (2.1) в случае двух переменных напоминает спуск на дно чаши (рис. 2.5). Это мотивирует название “методы спуска”.

Для различных методов спуска сначала выбирают начальную точку последовательности х ⁽⁰⁾ (рис. 2.5). Дальнейшие приближения x ^{( k )} определяются соотношениями.

x ^{(k +1)} = x ^(k) + a ^k ` h ^(k) (k = 0, 1, 2, …), (2.13)

где ` h ^{( k )} – вектор направления убывания, a ^k – положительная скалярная величина, называемая длиной шага.

Рис. 2.5.

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

1. Методы прямого поиска. Методы прямого поиска относятся к алгоритмам нулевого порядка, в которых используются только значения целевой функции. Мы рассмотрим подробно только один из них, а именно, метод покоординатного спуска или метод Гаусса-Зейделя. Практика показала, что этот метод эффективен и применим для широкого круга приложений.

Решение задачи (2.1) методом покоординатного спуска осуществляется по следующей общей схеме.

Выбирают произвольно начальную точку х ⁽⁰⁾ из области определения функции f (х). Приближения х ^{( k )} определяются соотношениями (2.13), где вектор направления убывания ` h ^{( k )} – это единичный вектор, коллинеарный какому-либо из координатных направлений; величина a ^k является решением задачи одномерной минимизации

f (x ^(k) + t ` h ^(k)) ® min, t Î R. (2.14)

Решение этой задачи может определяться, в частности, каким-либо из методов, описанных в предыдущем параграфе. Таким образом, задача поиска минимума функции нескольких переменных сводится к последовательности задач одномерной минимизации (2.14) по переменной t на отрезках n -мерного пространства, проходящих через точки x ^{( k )} в направлении векторов ` h ^{( k )}.

Детальная реализация общей схемы в двумерном случае дает траекторию приближения к точке x*, состоящую из звеньев ломаной, соединяющих точки x ^{( k )}, ` x <sup>( k )</sup>, x <sup>( k +1)</sup>, ` x ^{( k + 1)} (k = 0, 1, 2, …) (рис. 2.6). При k = 0, исходя из начальной точки x ⁽⁰⁾ = (x ₁⁽⁰⁾, x ₂⁽⁰⁾), находим точку` x <sup>(0)</sup> = (` x ₁⁽⁰⁾, ` x <sub>2</sub><sup>(0)</sup>) минимума функции одной переменной f (x <sub>1</sub>, x <sub>2</sub><sup>(0)</sup>); при этом f (` x ⁽⁰⁾) £ f (x ⁽⁰⁾). Затем находим точку минимума x ⁽¹⁾ функции f (` x <sup>(0)</sup>, x <sub>2</sub>) по второй координате. Далее делаем следующий шаг вычислений при k =1. Полагаем, что исходной точкой расчета является х <sup>(1)</sup>. Фиксируя вторую координату точки х <sup>(1)</sup>, находим точку минимума ` х ⁽¹⁾ = (` х <sub>1</sub><sup>(1)</sup>, ` х ₂⁽¹⁾) функции f (х ₁, х ₂⁽¹⁾) одной переменной х ₁; при этом f (` х <sup>(1)</sup>) £ f (х <sup>(1)</sup>) £ f (х <sup>(0)</sup>). Точку х <sup>(2)</sup> получают, минимизируя целевую функцию f (` х ₁⁽¹⁾, х ₂) вновь на координате х ₂ при фиксированной координате ` х ₁⁽¹⁾ точки х ⁽¹⁾ и т. д.

Условием прекращения вычислительной процедуры при достижении заданной точности e может служить неравенство

|| х ^{( k +1)} - х ^{( k )} || < e. (2.15)

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

3. Градиентные методы. В предыдущем пункте речь шла о методах, позволяющих получить решение задачи на основе использования только значений целевой функции. Важность прямых методов несомненна, поскольку в ряде практических инженерных задач информация о значениях целевой функции является единственной надежной информацией, которой располагает исследователь. С другой стороны, при использовании даже самых эффективных прямых методов для получения решения иногда требуется чрезвычайно большое количество вычислений значений функции. Это обстоятельство наряду с совершенно естественным стремлением реализовать возможности нахождения стационарных точек (т. е. точек, удовлетворяющих необходимому условию оптимальности первого порядка (2.2)) приводит к необходимости рассмотрения методов, основанных на использовании градиента целевой функции. Указанные методы являются итерационными и реализуются в виде последовательных алгоритмов.

Далее везде будем считать, что ¦(x) и Ñ ¦(x) существуют и непрерывны. Кроме того, предполагается, что компоненты градиента могут быть записаны в аналитическом виде или с достаточно высокой точностью найдены с помощью численных методов.

Все описываемые ниже методы основаны на итерационной процедуре, реализуемой в соответствии с формулой (2.13), где вектор ` h <sup>( k )</sup> строится с помощью антиградиента функции ¦ в точке x <sup>( k )</sup>, т. е. вектора -Ñ ¦(x <sup>( k )</sup>), задающего направление наискорейшего убывания целевой функции ¦. Способ определения ` h ^{( k )} и a ^k на каждой итерации характеризует особенности применяемого метода.

Метод наискорейшего спуска (метод Коши).

Пусть снова требуется решить задачу безусловной оптимизации

Исходя из некоторой начальной точки x ⁽⁰⁾, строим последовательность приближений

где

||Ñ f (x ^{( k )})|| - длина вектора градиента Ñ ¦(х ^{( k )}), длина шага a ^k вычисляется путем решения задачи одномерной минимизации

с помощью какого-нибудь из методов, описанных в §2 настоящей главы. Условием окончания вычислительной процедуры является выполнение неравенства (2.15).

На рис. 2.7 показана траектория поиска точки минимума методом наискорейшего спуска в двумерном случае - ломаная с началом в точке х ⁽⁰⁾, заканчивающаяся в точке, близкой к точке х * локального минимума. Отрезок ломаной, соединяющий точки х ^{( k )} и х ^{( k +1)}, k = 0, 1, 2, …, параллелен вектору градиента функции f (x) в точке х ^{( k )}, ориентированного перпендикулярно линии уровня функции, проходящей через точку х ^{( k )}.

Метод наискорейшего спуска сходится быстрее, чем методы прямого поиска. Однако скорость его сходимости при решении ряда практических задач остается недопустимо низкой. Это вполне объяснимо, поскольку cкорость изменения переменных непосредственно зависит от длины вектора градиента ||Ñ ¦(x ^{( k )})||, которая стремится к нулю, и отсутствует механизм ускорения движения к точке минимума на последних итерациях. Одно из главных преимуществ этого метода связано с его устойчивостью. Метод обладает важным свойством, которое заключается в том, что при достаточно малой длине шага a ^k на всех итерациях выполняется неравенство ¦(x ^{( k+ 1)}) £ ¦(x ^{( k )}). Благодаря этому свойству метод наискорейшего спуска, как правило, позволяет существенно уменьшить значение целевой функции при движении из точек, расположенных далеко от точки минимума, и поэтому часто используется при реализации градиентных методов в качестве начальной процедуры.

Метод Ньютона.

Нетрудно видеть, что в методе наискорейшего спуска применяется «наилучшая» локальная стратегия поиска очередного приближения на каждой итерации с использованием градиента. Однако движение в направлении, противоположном градиенту, приводит в точку минимума лишь в том случае, когда линии уровня целевой функции ¦ представляют собой окружности. Таким образом, эта стратегия может оказаться неприемлемой для некоторых нелинейных функций. Для того, чтобы построить более общую стратегию поиска, следует привлечь информацию о вторых производных целевой функции.

Разложим целевую функцию в ряд Тейлора в точке х ^{( k )}:

Здесь верхний индекс Т означает транспонирование; Ñ ²¦(x ^{( k )}) - матрица Гессе (Гессиан) функции ¦, элементами этой матрицы размерности n ´ n являются вторые производные ¶²¦/¶ x_i ¶ x_j; D х - вектор приращения с координатами D х_i = x_i - x_i ^{( k )}. Отбрасывая все члены разложения третьего порядка и выше, получим квадратичную аппроксимацию ¦(х):

Функцию `¦(х; х ^{( k )}) будем называть аппроксимирующей функцией, построенной в точке х ^{( k )}. На основе квадратичной аппроксимации функции ¦(х) построим последовательность итераций таким образом, чтобы градиент аппроксимирующей функции во вновь выбираемой точке х ^{( k+ 1)} обращался в ноль. Имеем

Отсюда

где (Ñ ²¦(х ^{( k )}))^-1 - матрица, обратная к матрице Гессе.Таким образом, мы получаем итерационную схему

которая и называется методом Ньютона.

Анализ сходимости метода Ньютона показывает (см., например в книгах [1, 2, 4]), что при выполнении некоторого (достаточно общего) условия регулярности целевой функции ¦(х) метод Ньютона имеет квадратичную скорость сходимости, т. е. выполняется неравенство

(2.16)

где положительная постоянная С связана с матрицей Гессе Ñ ²¦. Легко видно, что метод Ньютона сходится всякий раз, когда начальное приближение х ⁽⁰⁾ выбирается из условия

(2.17)

Действительно, при таком выборе х ⁽⁰⁾ величина q = С || x ⁽⁰⁾ - x* || < 1. Отсюда и из (2.16) вытекает, что при каждом k ³ 1

Так как q < 1, правая часть этого неравенства стремится к нулю при k ® ¥. Квадратичная скорость сходимости объясняется тем обстоятельством, что метод основан на квадратичной аппроксимации.

Таким образом, сходимость метода Ньютона возможна лишь для хорошего начального приближения х ⁽⁰⁾. При этом условие (2.17), гарантирующее сходимость, труднопроверяемо, так как фигурирующая в нем константа, как правило, неизвестна. Сложность отыскания нужного начального приближения является недостатком метода Ньютона.

В силу названных причин применение классического метода Ньютона далеко не всегда приводит к успеху. Многочисленные модификации направлены на то, чтобы, сохраняя основное достоинство метода Ньютона - его быструю сходимость, уменьшить трудоемкость и ослабить требования к выбору начального приближения.

Перспективным в этом плане оказывается подход, при котором строится аппроксимация матрицы (Ñ ²¦(х))^-1 на основе информации о значениях градиентов Ñ ¦(х ^{( k )}), Ñ ¦(х ^{( k- 1)}), …. Получающиеся при этом методы являются алгоритмами первого порядка, тогда как метод Ньютона относится к алгоритмам второго порядка.

Квазиньютоновские методы.

Предположим, что целевая функция ¦ дважды непрерывно дифференцируема. Построим последовательность итераций по формуле

Матрицу Н_k будем выбирать таким образом, чтобы она в некотором смысле аппроксимировала матрицу (Ñ ²¦(х))^-1. Заметим, что согласно известной формуле Тейлора из курса высшей математики

с точностью до величины, пропорциональной квадрату расстояния между х ^{( k )} и х ^{( k+ 1)}. Отсюда, предполагая, что матрица Ñ ²¦(х) обратима, имеем

где D х ^{( k )} = х ^{( k+ 1)} - х ^{( k )}, D y ^{( k )} = Ñ ¦(х ^{( k )}) -Ñ ¦(х ^{( k+ 1)}). Поэтому естественно потребовать, чтобы для матрицы Н_{k+ 1} , приближающей матрицу (Ñ ²¦(х))^-1, выполнялось условие

Это условие носит название квазиньютоновского. Оно лежит в основе целого ряда методов аппроксимации матрицы Гессе. Соответствующие методы минимизации, для которых на каждом шаге выполняется квазиньютоновское условие, также называются квазиньютоновскими.

Для вычисления матрицы H_{k+ 1} обычно используют рекурентное соотношение вида

где D H_k - какая-нибудь матрица, обеспечивающая выполнение квазиньютоновского условия. Например, формула

реализует известный и широко применяемый метод Дэвидона- Флетчера - Пауэла [2]. Здесь и далее используются обозначения: (u, v) - скалярное произведение векторов u = (u ₁, ¼, u_m), v = (v ₁, ¼, v_n),

Можно показать, что при соответствующих предположениях

H_k - (Ñ ²¦(х ^{( k )}))^-1 ® 0 при x ^{( k )} ® x ^*, причем скорость сходимости сверхлинейна.

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

Численная аппроксимация градиентов.

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

где d > 0. Такая аппроксимация непосредственно основывается на определении частной производной и при достаточно малых значениях d дает вполне удовлетворительные результаты. Выбор d осуществляется в зависимости от вида ¦(х), координат точки ` х и требуемой точности вычислений.

За счет дополнительного вычисления значений функции можно повысить точность аппроксимации путем использования центральной разделенной разности

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

4. О других методах безусловной оптимизации. Изложенные в данной главе методы, разумеется, не исчерпывают всего многообразия методов безусловной оптимизации, разработанных к настоящему времени. Многие полезные методы не рассмотрены из-за ограниченного объема издания. К ним относятся, в частности, метод сопряженных направлений и метод соряженных градиентов. Они весьма подробно изложены во многих книгах (см., например, [1, 2]). Кроме того, существует много различных градиентных методов первого порядка, отличающихся от метода наискорейшего спуска способом выбора длины шага на каждой итерации, например, дробление шага и другие [1], а также большое количество модификаций метода Ньютона. Из методов прямого поиска помимо метода сопряженных направлений отметим эвристические методы нулевого порядка (метод вращения системы координат [1], симплексный метод или метод поиска по симплексу [1, 2]). Они основаны на эвристических (т. е. интуитивных, не обоснованных строго) соображениях. Их можно применять в ситуациях, когда применение более совершенных методов невозможно или нецелесообразно, например, когда значения целевой функции вычисляются со значительными погрешностями или нет необходимости в высокой точности решения и т. д.

Контрольные вопросы и задания

2.1. Сформулируйте задачу безусловной оптимизации.

2.2. Каковы необходимые и достаточные условия оптимальности в задачах одномерной безусловной оптимизации?

2.3. В чем состоит свойство унимодальности функций?

2.4. Сформулируйте утверждение, на которое опираются все методы одномерной минимизации.

2.5. Опишите алгоритм, позволяющий найти начальный отрезок локализации минимума.

2.6. В чем состоят преимущества и недостатки методов дихотомии, Фибоначчи и золотого сечения?

2.7. В чем состоит суть интерполяционных методов минимизации?

2.8. Дайте определение направления убывания. Сформулируйте необходимые и достаточные условия направления убывания.

2.9. В чем состоит общая идея методов спуска? Укажите хотя бы один метод, являющийся методом спуска.

2.10. Что такое моно- и мультимодальные функции?

2.11. Какие из методов, описанных в данной главе, относятся к алгоритмам нулевого, первого и второго порядка?

2.12. Каковы преимущества и недостатки метода Ньютона?

2.13. В чем состоит главная идея квазиньютоновских методов?

2.14. Определите хотя бы один отрезок унимодальности функции f (x) = x - 2 x ² + 0, 2 x ⁵.

2.15. Минимизируйте функцию ¦(х) = 3 х ² + 12/ х ³ -5 на отрезке 0.5£ х £ 2.5, используя (а) метод дихотомии, (б) метод золотого сечения, (в) метод Фибоначчи, (г) метод парабол. В каждом случае проведите по четыре вычисления значений функции. Сравните результирующие отрезки локализации минимума.

2.16. Рассмативается функция Розенброка ¦(х) = 100(х ₂-(х ₁)²)² + (1- х ₁)² и начальная точка х ⁽⁰⁾= (-1.2, 0). Найдите точку локального минимума этой функции, пользуясь методом покоординатного спуска, с точностью до 0.2.

2.17. В процессе поиска точки минимума функции Розенброка (см. предыдущее упражнение) получены две первые точки х ⁽⁰⁾= (-1.2, 1), х ⁽¹⁾= (-1.3, 1.07). Определите направление поиска из точки х ⁽¹⁾, пользуясь следующими градиентными методами: (а) методом наискорейшего спуска, (б) методом Ньютона.

2.18. Требуется выбрать размеры прямоугольного бункера без крышки таким образом, чтобы бункер имел объем 10 м³, а его стоимость была минимальной. Основание бункера изготавливается из деревянных плит cтоимостью 10руб./м², а остальная часть бункера - из листового металла стоимостью 25 руб./м². Воспользуйтесь ограничением на объем бункера для того, чтобы исключить одну переменную из целевой функции, и решите получаемую в результате задачу безусловной оптимизации с двумя переменными с помощью метода Гаусса-Зейделя.

2.19. На какой высоте над центром круглого стола радиуса а следует поместить электрическую лампочку, чтобы освещенность края стола была наибольшей? Яркость освещения выражается формулой I = (k sinj)/ r ², где j - угол наклона лучей, r – расстояние источника света от освещаемой площадки, k – сила источника света. Сформулируйте задачу безусловной оптимизации и решите ее методом золотого сечения с точностью до 0, 1.

Глава 3. ЛиНЕЙНОЕ ПРОГРАММИРОВАНИЕ.

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

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

§1. Задачи линейного программирования и их свойства.

Задачи линейного программирования (ЗЛП) обладают рядом особенностей, позволивших разработать специальные высокоэффективные методы их решения. Но прежде чем приступать к описанию конкретных вычислительных процедур, необходимо сформулировать основные формы задач линейного программирования и изучить их свойства. Так же как и в предыдущих главах, мы будем рассматривать только задачу минимизации (вопрос о сведении задачи нахождения максимума к задаче минимизации уже обсуждался в §1 главы 1).

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

Постановка общей задачи линейного программирования(общая ЗЛП):

найти минимум линейной целевой функции

f (x) = c ₁ x ₁ + c ₂ x ₂ +... + c_n x_n (3.1)

на допустимом множестве Х Ì R ⁿ точек, удовлетворяющих условиям:

a ₁₁ x ₁ + a ₁₂ x ₂ +... + a _{1 n} x_n ³ b ₁,

a ₂₁ x ₁ + a ₂₂ x ₂ +... + a _{2 n} x_n ³ b ₂,

............................. (3.2)

a_{l 1} x ₁ + a_{l 2} x ₂ +... + a_{l n} x_n ³ b_l,

a_{l +1, 1} x ₁ + a_{l +1, 2} x ₂ +... + a_{l +1, n} x_n = b_{l +1},

............................

a_{m 1} x ₁ + a_{m 2} x ₂ +... + a_{m n} x_n = b_m (m ³ l),

и

(3.3)

Ограничения (3.3) называют условиями неотрицательности или тривиальными ограничениями. Вообще говоря, эти условия могут рассматриваться как частный случай ограничений типа неравенств (3.2), но в силу особой структуры их обычно записывают отдельно.

Определение 3.1. Условие вида

а_{j 1} x ₁ + a_{j 2} x ₂ +... + a_jn x_n ³ b_j, (3.4)

содержащееся среди ограничений (3.2), называется нежестким ограничением, если существует точка х ⁽⁰⁾ = (х ₁⁽⁰⁾,..., х_n ⁽⁰⁾) такая, что

a_{j 1} x ₁⁽⁰⁾ +... + a_jn x_n ⁰ > b_j.

В противном случае условие (3.4) называется жестким ограничением.

Понятие жесткости применимо и к ограничениям (3.3). Согласно определению 3.1 условия неотрицательности являются нежесткими. Кроме того из контекста определения следует, что любая точка множества Х удовлетворяет жесткому ограничению только со знаком равенства. Поэтому его можно переписать как ограничение типа равенства. Так что мы можем считать жесткими ограничения (3.2) типа равенства и нежесткими ограничения (3.2) типа неравенства.

Определение 3.2. Нежесткое ограничение называется существенным, если существует точка х ⁽¹⁾ = (х ₁⁽¹⁾,..., х_n ⁽¹⁾), удовлетворяющая всем остальным ограничениям (3.2), (3.3) и не принадлежащая множеству Х. В противном случае нежесткое ограничение называется несущественным.

Несущественные ограничения могут быть исключены из системы условий, определяющих множество Х. Более того, в некоторых случаях их необходимо исключать, т. к. они являются одной из причин зацикливания численных алгоритмов при реализации на ЭВМ.

Вообще любую задачу линейного программирования на минимум с ограничениями типа неравенств, направленных в ту или иную сторону, можно представить в форме (3.1) – (3.3). Нередко при моделировании тех или иных практических ситуаций возникают ограничения типа (3.2) со знаком “£ ”, т.е.

a_{i 1} x ₁ + a_{i 2} x ₂ +... + a_in x_n £ b_i.

Например, так могут быть заданы ограничения мощности производства или ограничения на потребляемые ресурсы. Нетрудно видеть, что эти ограничения приводятся к виду (3.2) простым умножением левой и правой части неравенств на (-1).

Пример 3.1 Множество X задается условиями:

1) -4 x ₁ + 2 x ₂ + x ₃ ³ -2, 2) 4 x ₁ - 4 x ₂ - x ₃ ³ -5,

3) - x ₂ + 5x₃ ³ -10, 4) 2 x ₂ ³ 3, 5) -2 x ₁ + x ₂ + x ₃ = 1.

Определим, какие из ограничений являются жесткими, какие – существенными. Складывая условия 1), 2), 4), получаем 0 £ 0. Следовательно, в условиях 1), 2), 4) стоит знак равенства, и они жесткие. Решая получившуюся при этом систему уравнений 1), 2), 5), найдем х ₁ = 1/4, х ₂ = 3/2, х ₃=0. Эта точка удовлетворяет условию 3) со знаком неравенства. Значит, ограничение 3) нежесткое. Но множество Х состоит только из одной точки (1/4, 3/2, 0), поэтому ограничение 3) несущественное.

Расмотрим теперь другие виды ЗЛП.

Определение 3.3. Общая ЗЛП называется основной ЗЛП, если допустимое множество Х задано только ограничениями (3.2) типа неравенств, т.е. Х: a_{i 1} x ₁ + a_{i 2} x ₂ +_… + a_in x_n ³ b_i, i = 1, 2, _…, m.

Фактически основная ЗЛП – это одна из форм записи общей ЗЛП. Задачу линейного программирования можно также сформулировать в канонической форме.

Определение 3.4. Канонической ЗЛП(КЗЛП) называется задача минимизации целевой функции (3.1) на допустимом множестве Х, заданном ограничениями

a_{i 1} x ₁ + a_{i 2} x ₂ + _… + a_in x_n = b_i, i =1, _…, m, (m £ n),

x_j ³ 0, j = 1, 2, _…, n.

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

Общая идея перехода от общей ЗЛП к КЗЛП cостоит в следующем.

Ограничения в виде неравенств (3.2) преобразуются в уравнения за счет введения фиктивных неотрицательных переменных x_i, i = n+ 1, _…, n+l, которые входят в целевую функцию с коэффициентом 0; переменные, на которые не наложено условие неотрицательности, представляются в виде разности двух новых неотрицательных переменных:

х_j = x_j ¢ - x_j ¢ ¢, (x_j ¢ ³ 0, x_j ¢ ¢ ³ 0).

Фиктивные переменные х_i добавляются в неравенства (3.2) с отрицательным знаком.

Проиллюстрируем применение описанных выше рекомендаций на примере.

Пример 3.2. Пусть задана общая ЗЛП с целевой функцией

f (x) = 5 x ₁ + 3 x ₂ + x ₃ + 2 x ₄ - x ₅

и допустимым множеством X, определенным системой уравнений и неравенств

2 х ₁ + 4 х ₂ + 5 х ₃ = 7

3 х ₂ - 4 х ₃ + 5 х ₄ + 4 х ₅ ³ -2,

-3 х ₁ +5 х ₃ - 6 х ₄ + 2 х ₅ ³ -4,

x ₁ ³ 0, x ₃ ³ 0, x ₅ ³ 0.

Тогда в соответствии со сформулированными правилами эквивалентная каноническая задача будет иметь вид:

f ₁(x ¢) = 5 x ₁ + 3 x ₂¢ - 3 x ₂¢ ¢ + x ₃ + 2 x ₄¢ - 2 x ₄¢ ¢ - 2 x ₅ + 0× x ₆ + 0× x ₇ ® min

на множестве Х ¢:

2 x ₁ + 4 x ₂¢ - 4 x ₂¢ ¢ + 5 x ₃ = 7,

3 x ₂¢ - 3 x ₂¢ ¢ - 4 x ₃ + 5 x ₄¢ - 5 x ₄¢ ¢ + 4 x ₅ - x ₆ = -2,

-3 x ₁ + 5 x ₃ - 6 x ₄¢ + 6 x ₄¢ ¢ + 2 x ₅ - x ₇ = -4,

x ₁ ³ 0, x ₂¢ ³ 0, x ₂¢ ¢ ³ 0, x ₃ ³ 0, x ₄¢ ³ 0, x ₄¢ ³ 0, x ₅ ³ 0,

x ₆ ³ 0, x ₇ ³ 0.

Нетрудно заметить, что “платой“ за переход от общей формы задачи линейного программирования к канонической является рост ее размерности (количества переменных), что при прочих равных условиях является фактором, усложняющим процесс решения.

2. Основные свойства ЗЛП и ее геометрическая интерпретация. Введем некоторые понятия, широко применяемые при решении задач, как линейного, так и нелинейного программирования. Допустимое множество Х общей ЗЛП образует так называемое многогранное множество. Каждое из равенств (3.2) задает гиперплоскость в R ⁿ, а каждое из неравенств определяет полупространство в R ⁿ, ограниченное соответствующей гиперплоскостью. Если множество X не пусто, то оно выпукло.

Определение 3.5. Множество М векторов (точек) пространства R ⁿ называется выпуклым, если оно содержит отрезок прямой, соединяющей две его любые точки. Другими словами, из того, что [F1] х Î М и у Î М следует, что l х +(1-l) х Î М для любого l, 0 £ l £ 1.

Ограниченное многогранное множество называют многогранником.

Определение 3.6. Точка х ⁰ выпуклого многогранного множества М называется его угловой точкой, если она не лежит ни на каком отрезке, соединяющем какие-либо две точки множества М.

Угловые точки многогранника называются его вершинами.

Для понимания сути численных методов линейного программирования полезно разобраться в том, что представляет собой ЗЛП с геометрической точки зрения. Рассмотрим следующий пример. Пусть дана задача минимизации целевой функции

f (x) = 3 x ₁ – x ₂ ® min

на допустимом множестве

X = { Î R ² | x ₁ + x ₂ £ 6, x ₁ - x ₂ £ 2, x ₁ £ 3, x ₁ ³ 0, x ₂ ³ 0}.

Так как количество переменных в неравенствах, задающих допустимое множество, равно двум, то его можно изобразить на координатной плоскости (см. рис. 3.1).

Рис.3.1.

На рис. 3.1 показано, что каждое неравенство определяет некоторую полуплоскость. Соответствующие области для каждого ограничения отмечены штрихами. Пересечениеданных полуплоскостей является допустимым множеством задачи. Поведение целевой функции f (x) = 3 x ₁ + x ₂ в рамках двумерной иллюстрации может быть охарактеризовано с помощью линий уровня. Для линейной функции двух переменных f (x) = c ₁ x ₁ + c ₂ x ₂ линия уровня представляет собой прямую, определяемую уравнением c ₁ x ₁ + c ₂ x ₂ = const. Нормальный вектор этой прямой ` с = (с <sub>1</sub>, с <sub>2</sub>) одновременно является и градиентом функции ¦. Тогда вектор -` с указывает направление убывания этой функции (рис. 3.1).

Таким образом с геометрической точки зрения задача минимизации сводится к определению такой точки области Х, через которую проходит линия уровня, соответствующая наименьшему из возможных значений. Последнее означает, что для нахождения точки минимума в задаче линейного программирования мы должны сначала построить линию уровня для некоторого произвольного значения целевой функции (например, f (x) = 0). Затем необходимо осуществлять параллельный перенос в направлении -` с до тех пор, пока не достигнем такой точки ­­­ x *Î X, из которой смещение в направлении вектора -` с было бы невозможно. Такой метод решения получил название графического.

На рис. 3.1 изображен частный случай, для которого решение ЗЛП достигается в одной угловой точке х * = (0, 6) множества Х. Нетрудно видеть, что возможны и другие варианты. В случае неограниченного допустимого множества X, целевая функция может неограниченно убывать, а задача - не иметь решения. Напротив, линия уровня соответствующая минимальному значению f (x), может касаться грани множества X. Тогда все точки, лежащие на этой грани являются решениями задачи.

Во всех рассмотренных иллюстрациях допустимое множество ЗЛП представлялось в виде некоторого многогранного выпуклого множества на плоскости. Такое их представление в литературе получило название первой геометрической интерпретации ЗЛП.

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

Теорема 3.1. Пусть { x* } – множество решений задачи (3.1)-(3.3). Тогда { x* } содержит хотя бы одну угловую точку допустимого множества X.

Доказательство. Чтобы не усложнять изложение, ограничимся тем случаем, когда множество X ограничено, и, следовательно, является выпуклым многогранником.

Пусть x ¹, x ², …, x^m - угловые точки множества X. Для доказательства воспользуемся следующим известным свойством ограниченных выпуклых множеств: если X - замкнутое ограниченное выпуклое множество, имеющее конечное число угловых точек, то любая точка х Î Х может быть представлена в виде выпуклой комбинации угловых точек Х. Под выпуклой комбинацией понимается следующее: любая точка х Î Х может быть представлена в виде

где l _i ³ 0, i = 1, 2, …, m; .

Пусть x * - точка в которой целевая функция f достигает минимума.Согласно сформулированному выше свойству точку х * можно представить в виде выпуклой комбинации угловых точек х ¹, х ², …, х ^m:

Так как х * - точка минимума, то для любого х Î Х

f (x *) £ f (x). (3.6)

Функция f (x) - линейная, следовательно,

(3.7)

где х^r - угловая точка, удовлетворяющая условию

Из (3.7) видно, что f (x *) ³ f (x^r). С другой стороны, cправедливо (3.6). Следовательно, f (x *) = f (x^r), т. е. существует по крайней мере одна угловая точка х^r, которая является решением задачи (3.1)-(3.3). Теорема доказана.