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

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

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

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

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

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

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

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

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

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

1) F₁(X₁) < F₁(X₂);
2) F₁(X₁) = F₁(X₂), F₂(X₁)<F₂(X₂);
∙
∙ (1)
∙
m) F_i(X₁) = F_i(X₂), i=1, 2,, m-1, F_m(X₁)<F_m(X₂).

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

F(X₁) = F(X₂) (2).

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

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

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

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

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

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

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

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

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

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

Дата добавления: 2017-01-13