Раздел 1. Введение

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

В дальнейшем будут использоваться следующие обозначения: Кп - га-мерное евклидово пространство.

ж = (ж1,..., хп)т - вектор-столбец, элемент (точка) пространства Кп.

[ж, у] = {г | г = (1 — £)ж + £?/, О < £ < 1} — отрезок с концевыми точками хну.

(х, у) = Х)^=1 хзУз — скалярное произведение векторов хну; для его обозначения используется также запись хту. \\х\ \ = ((ж, ж))1/2 — норма вектора ж.

р(х, у) = ||ж — у\ \ — евклидово расстояние между точками хну. В(х,е) = {у | р(х, у) < е} — открытый шар радиуса е с центром в точке ж, е-окрестность точки ж.

Символ т применяется для обозначения операции транспони­рования. Наряду с вектор-столбцами в дальнейшем также ис­пользуются и вектор-строки, что в каждом случае такого исполь­зования отмечается особо.

Пусть X С Яп и ж £ Ка. Точка ж называется точкой прикосновения множества X, если для любого е > 0 множество ХПВ(х,е) непусто. Множество X всех точек прикосновения назы­вается замыканием множества X. Точка ж называется предель­ной точкой множества X, если любая е-окрестность этой точки содержит бесконечно много точек множества X. Точка ж назы­вается внутренней точкой множества X, если найдется е > О, для которого В(х,е) С X. Через гЫХ обозначается множество всех внутренних точек множества X, называемое внутренно­стью множества X. Множество X \ гЫХ является множеством всех граничных точек множества X.

Множество X называется выпуклым, если для любых двух точек ж, у из X отрезок [ж, у] содержится в X. Пересечение любого числа выпуклых множеств является выпуклым множеством.

Примеры выпуклых множеств, с которыми нам придется иметь дело в дальнейшем:

гиперплоскость : {ж | (а, ж) = а}, где а £ Ка, а £ В,; полупространство (аффинное) : {ж | (а, ж) < а}; неотрицательный ортант : К+ = {ж \х^ > 0, ] = 1,..., га}; линейное многогранное множество: {ж | Ах > Ь}, где А - (тохга)-матрица, Ь £ Кт, неравенство между векторами рассматривается покомпонентно, т.е. ж > у эквивалентно ж — у £ К^_.

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

А1Ж1 + А2ж2 + ... + Хкхк,

где А1 + ... +     = 1, А; > 0, г = 1,..., к.

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

Лемма 1.1 (Каратеодори). Если X С Яп, то любая точка из соХ представима в виде выпуклой комбинации не более чем (га + 1)-й точки множества X.

Доказательство. Пусть у = А1Ж1 + ... + А^ж^, где хг £ X, Аг- > О, г = 1,..., /г, А1 + ... + А^ = 1, и к > га + 1. Покажем, что точку у можно представить в виде выпуклой комбинации мень­шего числа точек хг. Для этого рассмотрим семейство векторов {(дг) ^ | г = Поскольку число векторов в семей-

стве больше чем их размерность, то система является линейно зависимой. Следовательно, существуют числа дг-, не все равные нулю, такие, что ^л=\ Мг'2-* = 0 и Х)?=1 т = 0.   Это позволя-

4ет при любом значении параметра I представить точку у в виде линейной комбинации у = ^^=1(Аг' + ж г-. В силу положитель­ности Аг- при достаточно малых значениях £ каждый коэффици­ент Аг- + £дг- неотрицателен и при любом £ имеет место равенство ^^=1(Аг' + £дг') = 1. Поскольку среди чисел дг- есть не равные ну­лю, то можно выбрать такое значение £, при котором, по крайней мере, один из коэффициентов в рассматриваемом представлении станет равным нулю, а остальные останутся неотрицательны­ми. Тем самым будет получено представление у в виде выпуклой комбинации с использованием меньшего числа точек. Отсюда, в частности, следует, что существует выпуклая комбинация, пред­ставляющая точку у, в которой число слагаемых не превосходит п + 1. Лемма доказана.

Примером использования данной леммы может служить дока­зательство приводимого ниже утверждения.

Лемма 1.2 Если X С Кп — компактное множество, то соХ — также компактное множество.

Доказательство.  Пусть Л = {А £ Кп+1 \ = 1> >

О, г = 1,...,га+ 1}. Рассмотрим непрерывное отображение Ф : Л X Хп+1 —т- Ка, заданное равенством

Ф(А, ж1,..., хп+1) = А1Ж1 + ... + АП+1ЖП+1.

По лемме Каратеодори Ф(ЛхХп+1) = соХ. Следовательно, явля­ясь образом компактного множества при непрерывном отображе­нии, множество соХ должно быть компактным.

Крайней точкой выпуклого множества X называется точка ж £ X, которая не может быть представлена в виде: ж = 1/2(ж1 + ж2), где Ж1, Ж2 £ X И Ж1 ф ж2.

Функция ф : Ка —т- К1 называется выпуклой, если для любых двух точек ж1, ж2 £ Ка и А £ [0,1]

^(Аж1 + (1 - А)ж2) < Щх1) + (1 - Х)ф(х2).

Для выпуклой функции ф и любого действительного числа (I мно­жество {ж | ф(х) < а1}, как нетрудно убедиться, является выпукл­ым.

Под задачей оптимизации понимается задача поиска миниму­ма (или максимума) заданной функции /(ж) на некотором множе­стве <3. При этом нередко используется краткая форма записи одного из видов:

В дальнейшем мы будем рассматривать преимущественно за­дачи минимизации, имея в виду, что задача поиска максимума функции / тривиальным образом сводится к задаче минимиза­ции функции д = — /.

Задачей математического программирования принято назы­вать задачу оптимизации, в которой множество <3 является под­множеством пространства Ка и определяется конечной системой условий - неравенств вида ф{{х) < 0, г = 1,..., т, где ф{{х) — за­данные функции. При этом функция / называется целевой функ­цией, а условия ф{{х) < 0 называются ограничениями задачи. До­пустимым решением задачи называют любой вектор ж, удовле­творяющий всем ограничениям, т.е. любой элемент множества (^) = {х \ ф{{х) < 0, г = 1,..., т}. Оптимальным решением задачи (минимизации) называют допустимое решение, минимизирующее /(ж) на множестве всех допустимых решений.

Точка х° £ (^) есть локальный минимум (оптимум) задачи, если существует такая е-окрестность В(х°,е), что функция /(ж) достигает минимума на множестве <3 П В(х°,е) в точке ж0.

Среди задач математического программирования важное ме­сто занимают задачи выпуклого программирования, в которых целевая функция / и все функции ф{ (а следовательно, и мно­жество допустимых решений О) являются выпуклыми. Задачи

 

/(ж) —т- тгп, х £ <5;

min{f(x) | ж £

этого класса обладают тем полезным свойством, что любой ло­кальный минимум является глобальным, т.е. оптимальным ре­шением задачи. Другой не менее важный класс задач (подкласс вышеупомянутого класса) составляют задачи линейного програм­мирования. В последних все функции / и ф{ являются линейными, так что множество допустимых решений С} оказывается выпукл­ым линейным многогранным множеством.