Постановка задачи линейного программирования

Найти максимум функции

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

Такая форма задачи линейного программирования называется канонической формой.

Не ограничивая общности, можем считать, что все числа Этого можно добиться, умножая ограничения, где на -1.

Множество допустимых решений задачи

X = { }

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

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

Множество крайних точек многогранника X соответствует множеству допус­тимых базисных решений системы, и при этом одному базисному решению соот­ветствует одна крайняя точка многогранника.

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

1. Определение начального базисного решения.

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

2.2. Задача безусловной оптимизации

Общая постановка задачи безусловной оптимизации представляется следующим образом.

Дана дважды непрерывно дифференцируемая функция , определенная на множестве . Требуется исследовать функцию на экстремум, т. е. определить точки ее локальных минимумов и максимумов.

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

Для определенности рассмотрим задачу поиска безусловного локального ми­нимума:

Численное решение этой задачи, как правило, связано с построением последо­вательности { } точек, обладающих свойством убывания целевой функции:

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

Начальная точка поиска задается исходя из физического содержания решае­мой задачи и наличия априорной информации о положении точек экстремума.

Приемлемое направление спуска должно удовлетворять условию = 0, 1,...,

где - градиент непрерывно-дифференцируемой функции в точке , обес­печивающему убывание целевой функции . Примером приемлемого направле­ния спуска является направление вектора антиградиента: .

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

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

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

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

2. Методы первого порядка, использующие информацию о первых производ­ных функции ).

2.3. Задача условной оптимизации

Общая постановка задачи условной оптимизации представляются следующим об­разом.

Даны дважды непрерывно дифференцируемая целевая функция и функции ограничений , определяющие множество допустимых решений X. Требуется исследовать функцию ) на экстремум, т. е. оп­ределить точки х* X ее локальных минимумов и максимумов на множестве X. или где

целые числа.

При условии рассматриваемая задача является общей задачей, и она на­зывается задачей со смешанными ограничениями.

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

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

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

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

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

К описанной группе методов относятся метод проекции градиента и метод возможных направлений Зойтендейка. В методе Зойтендейка на каждой итерации строится возможное направление спуска и затем проводится оптимизация вдоль этого направления.