Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
МЕТОД ІДЕАЛЬНОЇ ТОЧКИ.
Метод використовує множину Парето, яка у даному випадку складається з допустимих точок завдання, які не можуть бути «зрушені» в межах допустимої множини з поліпшенням відразу за обома критеріями.
Метод ідеальної точки полягає у знаходженні на границі Парето точки, найближчої до точки утопії, що задається ОПР. Зазвичай ОПР формулює мету у вигляді бажаних значення показників, і часто в якості координат цільової точки вибирається поєднання найкращих значень всіх критеріїв (зазвичай ця точка не реалізується при заданих обмеженнях, тому її і називають точкою утопії).
Приклад.
Нехай на множині ω площині (x, y), яка визначається системою нерівностей
задані дві лінійні функції:
|
U = x + y + 2 |
(1) |
Потрібно знайти рішення задачі
U → max, V → max
Рішення.
Розглянемо рішення цієї задачі методом ідеальної точки.
Множина ω являє собою п'ятикутник (рис. 7), вершини якого мають наступні координати:
A (0; 0), B (0, 2), C (2, 2), D (4; 1), E (4; 0).
Рис. 7.
У силу лінійності критеріїв U і V п'ятикутник ABCDE переходить в п'ятикутник A* B* C* D* E* (рис. 8), координати вершин якого обчислюються за формулами (1):
A* (2, 6), B* (4, 4), C* (6; 6), D* (7; 9), E* (6; 10).
Рис. 8.
Знаходимо кордон Парето. Це відрізок D* E*. Точка утопії M* (7; 10) вважається заданою (її координати суть найбільше значення U і V).
Потрібно знайти на множині Парето точку, найближчу до точки утопії M*. З малюнка видно, що шукана точка повинна лежати на відрізку D* E*. Проведемо через точки D* і E* пряму. Нехай
α U + β V = γ
- Її рівняння. Щоб відшукати конкретні значення параметрів α, β і γ, підставимо в нього координати обох точок D* і E*. Отримаємо
6α +10 β = γ,
7α +9 β = γ.
Віднімаючи з першої рівності другу, після простих перетворень прийдемо до співвідношення
- Α + β = 0,
звідки
α = β.
Покладемо α = β = 1. Тоді γ = 16 і
U + V = 16
- Шукане рівняння прямої.
За умовою задачі нам потрібно визначити на прямий
U + V = 16
точку M 0 (U 0, V 0), відстань якої від точки M* (7; 10) мінімально, тобто вирішити екстремальну задачу:
z = (U - 7) 2 + (V - 10) 2 → min.
Так як U = 16 - V, то останнє співвідношення можна переписати у вигляді
z = (9 - V) 2 + (V - 10) 2 → min ..
Звівши у квадрат і приводячи подібні, отримуємо, що
z = 2V 2 - 38V + 181 → min ..
Це рівняння описує параболу з вершиною
Тоді
U 0 = 16 - V 0 = 16-9,5 = 6,5.
Ідеальна точка
M 0 (6,5; 9,5)
Відповідні значення x і y легко знаходяться із системи лінійних рівнянь
6,5 = x + y + 2
9,5 = x - y + 6
Маємо
x = 4, y = 0,5.
Зауваження. Ми розглянули задачу, в якій
Ф (x, y) → max, Ψ (x, y) → max.
На практиці часто зустрічаються випадки, коли вимоги виглядають по-іншому -
Ф (x, y) → max, Ψ (x, y) → min,
Ф (x, y) → min, Ψ (x, y) → min,
Функція
Θ =-Ψ
має наступним властивістю: вона досягає найбільшого значення в точності в тих точках, де функція Ψ приймає найменше значення, і навпаки. Іншими словами, умови
Ψ (x, y) → min і Θ (x, y) → max
рівносильні. Тому, помінявши в разі необхідності знак у критерію на протилежний, ми можемо звести будь-яку двухкрітеріальную задачу до вже розглянутої.
PAGE 3