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

Лексикографический критерий

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

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

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

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

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

Пусть имеется стратегия X1, которой соответствует вектор значений частных критериев (F1(X1), F2(X1),…,Fm(X1)). Все частные критерии образующие векторный критерий F=(F1, F2, …, Fm),строго упорядочены по важности. При сравнении пары стратегий в первую очередь используется первый критерий F1 и лучшей считается та стратегия, для которой значение этого критерия меньше (больше, если находят максимум). Если значение первого критерия для обеих стратегий оказываются равными, то применяется второй критерий F2, и предпочтение отдаётся той стратегии, для которой его значение меньше (больше), если второй критерий не позволяет выделить лучшую стратегию, привлекается третий частный критерий, и т.д. до Fm.

Если же значение каждого частного критерия для рассматриваемых стратегий оказываются равными, то эти стратегии считаются эквивалентными, т.е. равноценными в смысле векторного критерия F.

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

1) F1(X1) < F1(X2);
2) F1(X1) = F1(X2), F2(X1)<F2(X2);
∙
∙ (1)
∙
m) Fi(X1) = Fi(X2), i=1, 2, , m-1, Fm(X1)<Fm(X2).

Стратегии X1 и X2 эквивалентны (X1~X2), если выполнено условие

F(X1) = F(X2) (2).

Опр. Стратегия X1 лексикографически не хуже чем стратегия X2 (X1X2), если выполнено одно из условий (1) или (2).

Опр. Оптимальной называется такая стратегия X*, которая не хуже любой другой стратегии X, т.е. если (X*X).

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

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

Зам. Лексикографическое упорядочивание часто используется для установления правил старшинства, приоритета и т.д. Очень много примеров можно найти в спорте: достаточно вспомнить определение победителей в соревнованиях по хоккею, футболу, шахматным турнирам и т.д. Например, 1) первое место занимает команда, набравшая наибольшее количество очков;

2) если одинаковое количество очков, то чемпионом будет сборная, имеющая лучший результат (очкам) во встречах между этими командами;

3) разница между забитыми и пропущенными шайбами;

4) отношение забитых шайб к пропущенным;

5) по буллитам;

6) подбрасывается монета.