Курсовая работа СМО Гангур. Курсовая работа методы решения задач оптимизации по дисциплине Методы оптимизации Направление подготовки
Метод идеальной точки состоит в отыскании на границе Парето точки, ближайшей к точке утопии, задаваемой ЛПР. Обычно ЛПР формулирует цель в виде желаемых значений показателей, и часто в качестве координат целевой точки выбирается сочетание наилучших значений всех критериев (обычно эта точка не реализуется при заданных ограничениях, поэтому ее и называют точкой утопии).
В этом разделе лекции мы подробно рассмотрим метод идеальной точки на следующем конкретном примере.
Пусть на множестве ω плоскости (OXY) определяемом системой неравенств:
0≤x≤4;
0≤y≤2;
x+2y≤6;
Заданы две линейные функции:
Требуется найти решение задачи
U = Φ (x, y) → max, V = Ψ (x, y) → max,(x, y) ω.
Множество ω представляет собой пятиугольник ABCDE, вершины которого имеют следующие координаты: A (0,0), B (0,2), C (2,2), D (4,1), E (4,0).
Рисунок 1 – Метод идеальной точки.
В силу линейности критериев U и V пятиугольник ABCDE на плоскости OXY переходит в пятиугольник A*B*C*D*E* на плоскости OUV, координаты вершин которого вычисляются по следующим формулам (3):
E*=(U(E), V(E)) = (U (4,0), V (4,0)) = (6,10).
Теперь находим границу Парето: это отрезок D*E*. Точка утопии М*(7,10) считается заданной (ее координаты равны, соответственно, наибольшим значениям U и V). Из (Рис. 2) ясно, что UM*=UD*=7, VM*=VE*=10 в системе координат OUV.
Рисунок 2 – Построение границы Парето множества Ω.
Требуется найти на множестве Парето точку, ближайшую к точке утопии М*. Из рисунка 2 видно, что искомая точка должна лежать на отрезке D*E*. Проведем через точки D* и Е* прямую (D* E*). Найдем уравнение этой прямой. Пусть уравнение прямой (D* E*) в системе координат (OUV) имеет вид:
α∙U+β∙V = γ.
Чтобы отыскать конкретные значения параметров α, β и γ, подставим в него координаты обеих точек – и D*,и Е*.
Получим следующую систему уравнений.
(D*): α∙7+β∙9=γ,
(E*): α∙6+β∙10=γ.
Вычитая из первого равенства второе, после простых преобразований придем к соотношению:
Положим α=β=1, тогда γ=16.
Следовательно, искомое уравнение прямой (D*E*):
U+V=16.
Напомним, как найти расстояние между точками, заданными своими координатами в декартовой прямоугольной системе координат.
Пусть M1(U1, V1) и M2(U2, V2) – две точки на плоскости (OUV). Для того чтобы найти расстояние между ними, достаточно вычислить длину гипотенузы построенного прямоугольного треугольника.
Воспользовавшись теоремой Пифагора, получим для гипотенузы |M1M2| построенного прямоугольного треугольника:
|M1M2| 2 = (U2 – U1) 2 +(V2 – V1) 2 .
По условию задачи нам нужно определить на прямой (D*E*), заданной уравнением
точку М 0 (U 0 , V 0 ), расстояние которой от точки М*(7,10) минимально, то есть решить экстремальную задачу:
f (U, V) = (U – 7) 2 +(V– 10) 2 →min.
Так как U = 16 – V, то последнее соотношение можно переписать в виде:
f(U(V), V) ≡ F(V) = (9 –V) 2 +(V– 10) 2 →min.
Отсюда, возводя в квадрат и приводя подобные, получаем:
F(V)=2V 2 – 38V+181 → min.
Это уравнение описывает параболу с вершиной (V 0 , F(V 0 )), где координата V 0 находится из условия равенства нулю производной: F`(V)= 4V – 38 =0. То есть V 0 =19/2, тогда
F(V 0 ) = 2(19/2) 2 – 38∙19/2+181=1/2.
Таким образом, идеальная точка М 0 (U 0 , V 0 ) находится на расстоянии √F(V 0 ) = 1/√2 от точки утопии М*(7,10) (Рис. 3). Чтобы найти координату U 0 , рассмотрим уравнение прямой (D*E*), на которой лежит идеальная точка М 0 (U 0 , V 0 ):
U+V=16.
Отсюда, U 0 +V 0 =16.
Следовательно, U 0 +19/2=16, U 0 =16 – 19/2=13/2.
Таким образом, M 0 = (13/2; 19/2).
Рисунок 3 – Нахождение идеальной точки.
Возвращаясь к системе координат OXY, заметим, что соответствующие значения x 0 и y 0 легко находятся из системы линейных уравнений:
U 0 = x 0 +y 0 – 6,
V 0 = x 0 – y 0 +2.
Здесь мы воспользовались равенствами:
U 0 = U (x 0 , y 0 ),
V 0 = V (x 0 , y 0 ).
13/2= x 0 +y 0 + 6,
19/2= x 0 – y 0 +2.
Складывая уравнения, получим:
16=2x 0 + 8, то есть x 0 =4.
Вычитая из первого уравнения второе уравнение, получим:
— 3=2y 0 – 4, то есть y 0 =1/2.
Значит, идеальная точка на плоскости OXY имеет координаты: (4; 1/2).
Постройте любой пятиугольник ABCDE, все вершины которого лежат на окружности. Выполните необходимые измерения и вычислите его периметр.
Как быстро выучить стихотворение наизусть? Запоминание стихов является стандартным заданием во многих школах.
Как научится читать по диагонали? Скорость чтения зависит от скорости восприятия каждого отдельного слова в тексте.
Как быстро и эффективно исправить почерк? Люди часто предполагают, что каллиграфия и почерк являются синонимами, но это не так.
Как научится говорить грамотно и правильно? Общение на хорошем, уверенном и естественном русском языке является достижимой целью.
Постройте пятиугольник ABCDE, вершины которого имеют координаты: А(-5; 4);С(0; 6); С(5; 4); D(6; 0); Е(0; -4). Проведите диагонали АС
Как быстро выучить стихотворение наизусть? Запоминание стихов является стандартным заданием во многих школах.
Как научится читать по диагонали? Скорость чтения зависит от скорости восприятия каждого отдельного слова в тексте.
Как быстро и эффективно исправить почерк? Люди часто предполагают, что каллиграфия и почерк являются синонимами, но это не так.
Как научится говорить грамотно и правильно? Общение на хорошем, уверенном и естественном русском языке является достижимой целью.