Научная электронная библиотека

Монографии, изданные в издательстве Российской Академии Естествознания

Прикладные методы оптимизации

Шукаев Д. Н.,

В.2.3. Задача математического программирования

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

X = {x/gi(x) ≤ 0, i = 1, 2, …, k, g_i(x) = 0, i = k + 1, …, m}. (В.7)

В общепринятой форме задачу математического программирования можно представить в виде

f(x) → max;

gi(x) ≤ 0, i = 1, …, k;

g_i(x) = 0, i = k + 1, …, m. (В.8)

Термин «математическое программирование» предложен Робертом Дорфманом в 1950 году [45] и теперь он объединяет линейное программирование, целочисленное программирование, квадратичное программирование, выпуклое программирование и нелинейное программирование. Математическое программирование имеет дело с оптимизацией линейной или нелинейной целевой функции при линейных и (или) нелинейных ограничениях.

В.2.3.1. Линейное программирование

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

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

(В.9)

Саму задачу в общем случае можно записать в виде:

i = 1, …, k;

i = k + 1, …, m. (В.10)

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

Для задач линейного программирования с двух индексными переменными, получившими название «транспортные задачи», с учетом специфики структуры их ограничений разработаны более эффективные методы, такие как метод потенциалов, распределительный метод и другие [37].

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

В.2.3.2. Квадратичное программирование

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

f = cx + x′Dx;

Ax ≤ b;

x ≥ 0, (В.11)

где предполагается, что х и с – вектора размерности n; A – матрица размерности m×n; D – матрица размерности n×n.

Задачи квадратичного программирования хорошо изучены и существуют достаточное количество эффективных методов их решения [25, 26, 37]. Здесь можно отметить несколько направлений, основанные на обобщении симплекс-алгоритма (например, методы Била, Баранкина – Дорфмана), на условиях Куна и Таккера (например, метод Франка – Вульфа) или на функции Лагранжа.

В.2.3.3. Выпуклое программирование

Задача оптимизации относится к выпуклому программированию, если множество ее допустимых решений Х выпукло, а целевая функция вогнута на Х. Форма записи выражений для множества допустимых решений Х и самой задачи выпуклого программирования совпадают с выражениями (В.7) и (В.8) с учетом того, что функция f(x) должна быть выпуклой, а функции gi(x) линейными и (или) выпуклыми. Для задач выпуклого программирования также разработано значительное число достаточно эффективных методов их решения. Среди них можно отметить методы возможных направлений, впервые предложенные Зойтендейком [84], метод проекции градиента, методы штрафных функций и другие.

В.2.3.4. Нелинейное программирование

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