Обзор методов решения однокритериальных статических детерминированных задач принятия решений

При определении возможных методов решения любой задачи принятия решений следует исходить из анализа ее математической модели. Как видно из рассмотрения математической модели ((5.1), (5.2), (5.4)) общей постановки однокритериальной статической детерминированной задачи принятия решений, она полностью совпадает с общей постановкой задачи математического программирования (МП). Поэтому весь богатый арсенал методов, разработанных для решения задач МП, может и должен быть использован для решения задачи принятия решений рассматриваемого класса. Для этого проводится обзор методов решения рассматриваемого класса задач с точки зрения МП.

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

Датой возникновения МП в литературе, особенно переводной, обычно называют 1947 г., когда американским математиком Джорджем Данцигом, работавшим в составе группы исследователей по заданию ВВС США над решением некоторых типов экстремальных задач, был разработан численный метод решения задачи линейного программирования (ЛП), являющейся частным случаем обшей задачи МП. Метод получил название симплекс-метода. Открытие этого метода стало толчком к бурному росту интереса к теории и практике МП[1].

Общая задача МП может быть сформулирована следующим образом. Требуется найти значения п переменных х,, х2, ..., х„, которые удовлетворяют системе из т соотношений:

(х,, х2,..., х„ ){<, =, >} Ь.,, / е 1, т, (5.5)

где величины b, есть заданные константы; g, — заданные функции, и они максимизируют функцию:

Соотношения (5.6) в задачах МП называются ограничениями. Совокупность этих ограничений образует область Q. х допустимых значений переменных хь х2, ..., х/(. Очевидно, что эта область не должна быть пуста. В противном случае исчезла бы свобода (хотя и ограниченная) в выборе значений переменных, которая позволяет сравнивать значения функции F в разных точках и определять искомый максимум и которая составляет принципиальную отличительную особенность задач МП.

Для краткости изложения в дальнейшем будем пользоваться следующей условной формой записи задачи МП в постановке (5.5), (5.6):

где X = (хьх2,..., хп) — «-мерный вектор искомых переменных.

К задаче МП (5.5), (5.6) можно отнести следующие общие замечания.

  • 1. В каждом отдельном ограничении из системы ограничений (5.5) сохраняется только один из знаков <,=,>, причем разные ограничения могут иметь разные знаки.
  • 2. Величины пит, где п — количество переменных в задаче, а т — количество ограничений, в общей задаче МП между собой не связаны и могут принимать любые значения при условии п > 1, т > 0, причем т может быть меньше, больше или равна п, т. е. т {<, =, >} п. Исключение составляет случай, когда все т ограничений (5.5) являются строгими равенствами; в этом случае величины пит должны быть связаны соотношением 0 < т < п, т. е. количество уравнений связи должно быть не больше количества переменных. В частном случае т может быть и нулем, так что общая постановка (5.5), (5.6) включает и случай, когда все ограничения (5.5) отсутствуют.
  • 3. В задачах МП различают и обычно по-разному оформляют два вида ограничений: областные и функциональные. Каждое областное ограничение относится только к одной переменной, ограничивая область ее изменения. Областное ограничение может иметь, например, следующий вид:

Областное ограничение (5.8) представляет собой простейший частный случай ограничения (5.5), когда функция g, (А) имеет простейший вид: g, (X) = Xj.

В задачах МП встречаются и так называемые двусторонние областные ограничения:

Одно двустороннее ограничение равносильно двум односторонним ограничениям, имеющим вид, подобный (5.8), а именно:

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

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

5. В отдельных задачах МП в качестве ограничений дополнительно к (5.11) может фигурировать условие, согласно которому некоторые или все переменные могут применить лишь некоторые дискретные значения, например только целочисленные. Это условие может иметь в частном случае такой вид:

где Ду — некоторая константа.

Условия, подобные (5.12), можно назвать требованиями дискретности или ограничениями на непрерывность переменных. Если в частном случае в условии (5.12) Ду = 1, то оно превращается в требование целочисленности переменных:

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

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

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

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

I. Классические задачи МП (классические задачи оптимизации). Это

задачи, которые удовлетворяют совокупности следующих требований: 1) непрерывность критериальной функции F (X) и функциональных ограничений g, (X) и наличие у них непрерывных частных производных по крайней мере второго порядка; 2) отсутствие среди функциональных ограничений неравенств, что влечет требование т (X) п; 3) отсутствие областных ограничений и требований неотрицательности; 4) отсутствие требований дискретности переменных.

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

Классические задачи МП, в свою очередь, подразделяются на два подкласса по признаку отсутствия или наличия ограничений: задачи отыскания безусловного экстремума и задачи отыскания условного экстремума с ограничениями типа равенств.

1а. Задачи отыскания безусловного экстремума. В этих задачах отсутствуют ограничения на область допустимых значений вектора переменных X = (*!, ..., х„), т. е. отсутствуют функции g, (А). Следовательно, область Q. (X) совпадает со всем «-мерным пространством переменных.

Постановка задачи имеет следующий вид:

16. Задачи отыскания условного экстремума с ограничениями типа равенств. Постановка задачи выглядит так:

Задачи типа (5.15) в результате применения метода множителей Лагранжа сводятся к предыдущей задаче — задаче безусловной оптимизации (5.14).

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

Корни системы уравнений (5.16) называются стационарными', эти точки «подозрительны» на предмет нахождения в них экстремума (максимума или минимума) функции F (X). Признаком существования максимума в стационарной точке является выполнение в ней достаточных условий максимума функции.

Процедура решения задачи безусловной оптимизации (5.14) классическим методом состоит из следующих этапов: 1) решение системы уравнений (5.16) в целях определения всех стационарных точек; 2) анализ тем или иным способом стационарных точек в целях выявления всех максимумов функции F (X); 3) сравнение максимальных значений функции F (X) в целях определения ее глобального максимума.

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

II. Неклассические задачи МП (неклассические задачи оптимизации). В неклассических задачах МП на значения вектора управления X — (Xj), кроме функциональных ограничений вида:

где gj (X) — функция, обычно накладываются ограничения на знак, выражающие требование неотрицательности всех или некоторых компонент вектора X:

В дальнейшем обзоре для простоты будем считать, что требование (5.17) предъявляется ко всем п компонентам вектора X, т. е. р — п. Если в частном случае это не так, то всегда за счет введения дополнительных переменных можно перейти к случаю р = п.

Общая постановка неклассической непрерывной (т. е. не имеющей требований дискретности) задачи МП обычно записывается в следующем виде:

Заметим, что многие авторы публикаций по МП задачи МП отождествляют лишь с неклассическими задачами (5.17), выделяя классические задачи (5.14), (5.15) в особый класс задач оптимизации.

Неклассические задачи МП обычно подразделяют на два подкласса: специальные и неспециальные.

Па. К специальным задачам МП относят такие, для которых в силу каких-то специфических особенностей их критериальных функций и функциональных ограничений разработаны специальные методы решения. Пример специальной задачи МП — задача ЛП. Специфическая особенность этой задачи — линейность критериальной функции и функциональных ограничений.

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

Траектория поиска экстремума при решении задачи линейного программирования симплекс-методом

Рис. 5.1. Траектория поиска экстремума при решении задачи линейного программирования симплекс-методом

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

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

Свойство универсальности прямых методов поиска экстремума вовсе не означает, что эти методы эффективнее специальных. В частности, специальные методы в силу их специфической приспособленности к задаче надежно гарантируют нахождение экстремума функции. Например, в теории МП строго доказано, что симплекс-метод гарантирует в задаче ЛП точное нахождение экстремума критериальной функции за конечное число шагов. Существует верхняя оценка количества опорных решений для задачи ЛП: С" = (т + п)/тп, где п — количество переменных в задаче; т — количество ограничений; С; — количество сочетаний из + п) по п. Поскольку перебор всех опорных решений гарантирует нахождение оптимального решения, то, очевидно, количество шагов симплекс-алгоритма не должно существенно превышать величину С ". Следует иметь в виду, что задача ЛП может быть решена и прямыми методами поиска экстремума, однако при этом не гарантируется точное нахождение оптимального решения за конечное количество шагов поиска.

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

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

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

Перечислим основные типы специальных неклассических задач МП.

1. Задачи ЛП. Они характеризуются тем, что функции F (X) и g, (X) являются линейными по X.

Общая постановка задачи ЛП может быть представлена в таком виде:

где b-„ Cj, а^ — заданные постоянные величины.

Все остальные задачи МП, не сводимые к постановке (5.18), являются нелинейными задачами МП.

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

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

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

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

2. Задачи квадратичного программирования. Они характеризуются квадратичной зависимостью критериальной функции F (X) и линейной зависимостью функциональных ограничений g, (X) от X.

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

где bh С), ai}, dJk заданные постоянные величины.

Примеры выпуклых (вогнутых) и .S'-образных функций

Рис. 5.2. Примеры выпуклых (вогнутых) и .S'-образных функций

Для решения задач этого типа разработаны специальные методы, базирующиеся на теории Куна — Таккера.

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

Приведем некоторые определения, касающиеся выпуклых функций. Выпуклая (вогнутая) функция одной переменной ф (А) обладает следующим свойством: каждая ее дуга лежит не ниже (не выше) своей хорды (рис. 5.2а, 5.26). Функция, представленная на рис. 5.2в, не является ни вогнутой, ни выпуклой, так как на участке ЛВ хорда лежит выше дуги, а на участке ВС — ниже. Подобные функции часто называют б'-образными.

Функция многих переменных F (X), где X — «-мерный вектор, называется выпуклой, если для произвольных «-мерных векторов Хх и Х2 и любого скаляра X из интервала 0 > X > 1 выполняется условие:

В задачах выпуклого программирования часто используются следующие свойства функций: 1) сумма выпуклых функций есть выпук-

t

лая функция, т. е. функция F(X) = ^akfk(X) выпукла, если ак> 0 и

к = 1

функции fk (X) выпуклы для всех k&,t; 2) линейная и квадратичная функции являются выпуклыми.

Общая постановка задачи выпуклого программирования по форме совпадает с общей постановкой (5.17) неклассической задачи МП. Для решения задач выпуклого программирования успешно применяются методы возможных направлений.

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

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

или

)

В случае (5.22) функция F называется аддитивной, а в случае (5.23) — мультипликативной сепарабельной.

п

В (5.23) символ означает произведение п функций.

i= |

Постановка задачи выглядит так:

Для решения подобных задач может быть использован метод динамического программирования Веллмана.

5. Задачи геометрического программирования. В задачах этого класса критериальная функция и функциональные ограничения относятся к разряду так называемых позиноминалъных. Простейшим позино- мом является функция ф (.X), где Х= (х,, х2,..., х„), которая может быть представлена так:

где с и я, — некоторые константы.

В задачах геометрического программирования к величинам с и х2 предъявляется требование положительности, т. е. с > 0 и Xj > 0. Требование положительности коэффициента с привело к появлению приставки «пози» в слове «позином». Благодаря положительности х} выражение xf определено и для дробных степеней а}.

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

где ск > 0.

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

6. Задачи дискретного программирования. Сюда может быть отнесена любая задача МП, в которой есть дополнительное ограничение на вектор управления X, состоящее в требовании, чтобы все (полностью дискретные задачи) или некоторые (частично дискретные задачи) компоненты вектора X принимали только дискретные неотрицательные значения, т. е.

где п — размерность вектора Х Ак некоторый дискрет (положительная величина).

Частным случаем задач дискретного программирования являются задачи целочисленного программирования. В них Ак = 1.

В настоящее время разработаны методы решения некоторых дискретных задач МП в рассмотренных выше специальных случаях, например методы Гомори решения задач целочисленного ЛП. Требование дискретности хорошо сочетается с методом динамического программирования Веллмана, применяемым для решения задач с сепарабельными критериальными функциями.

Все остальные задачи МП, не сводимые к специальным задачам (т. е. неспециальные задачи), часто называют задачами нелинейного программирования.

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

Напомним здесь, что в задачах МП различают следующие виды экстремумов: безусловный абсолютный (или глобальный) максимум (минимум), безусловный относительный (или локальный) максимум (минимум), условный абсолютный максимум (минимум), условный относительный максимум (минимум). Под безусловными экстремумами понимаются экстремумы в отсутствие ограничений, под условными — экстремумы в условиях действия ограничений. Глобальным максимумом (минимумом) называется наибольший (наименьший) из всех максимумов (минимумов). Локальный экстремум — это экстремум в некоторой ограниченно малой окрестности экстремальной точки (рис. 5.3).

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

Характерной особенностью обладают и области ?1Х допустимых значений управления в задачах линейного, квадратичного и выпуклого программирования. Эти области образуются совокупностью линейных или выпуклых функциональных ограничений, а поэтому представляют собой выпуклые области в я-мерном пространстве вектора управления X. Произвольная область называется выпуклой, если

Виды экстремумов

Рис. 5.3. Виды экстремумов: а — безусловные; б — условные

Области допустимых значений управления

Рис. 5.4. Области допустимых значений управления: а — выпуклые; б — невыпуклые

вместе с двумя любыми точками, принадлежащими ей, она содержит и весь отрезок, соединяющий эти точки. На рис. 5.4а даны примеры выпуклых областей, на рис. 5.46 — областей, не являющихся выпуклыми.

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

Особенностью неспециальных задач математического программирования является их потенциальная полиэкстремальность (многоэкс- тремальность). Это означает, что оптимизируемая критериальная функция в области допустимых значений может иметь несколько (заранее неизвестно, сколько) экстремумов (локальных и глобальных). Кроме того, она может обладать сложной формой поверхности: иметь разнообразные «хребты», «овраги», «пещеры». Многоэкстремаль- ность задач нелинейного программирования может быть обусловлена сложным характером поверхности как критериальной функции, так и функциональных ограничений, приводящим, например, к много- связности области Qx допустимых значений вектора управления X. (Многосвязная область — область, состоящая из нескольких изолированных частей.)

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

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

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

Для детерминированных методов характерен «жесткий» алгоритм поиска (без случайных элементов). К детерминированным методам относятся различные градиентные методы (метод градиентов, метод наискорейшего спуска, проективный градиентный метод), метод покоординатной оптимизации (метод Гаусса — Зайделя), различные «овражные» методы и др.

40

О

а

Глава 5. Модели принятия решений в социальных группах

§ 1. Модели принятия решений в условиях определенности

Рис. 5.5. Классификационная схема однокритериальных статических детерминированных задач принятия

ЧО

решений и методов их решения

Случайные методы характеризуются наличием элемента случайности в алгоритме поиска (случайный «рабочий» шаг, случайный «пробный» шаг и т. д.). К данным методам относятся методы ненаправленного и направленного случайного поиска, методы случайного поиска с самообучением и т. п. Все указанные численные методы поиска экстремума могут быть использованы и в специальных задачах МП, т. е. задачах линейного, квадратичного и выпуклого программирования.

В соответствии с выделенными классификационными признаками задач и методов МП на рис. 5.5а и 5.56 построено классификационное «дерево» однокритериальных статических детерминированных задач принятия решений и методов их решения.

  • [1] Исторической справедливости ради следует указать, что первая обстоятельная работа по линейному программированию была выполнена еще в 1939 г. в СССР. См.:Канторович Л. В. Математические методы организации и планирования производства.Л., 1939.
 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >