Pareto set, programare liniară, exemple ale soluțiilor
Să presupunem că avionul (sau spațiu) dat un set de puncte se numește punctul M. Un punct interior M. în cazul în care există o vecinătate a acestui punct, care constă în întregime dintr-un anumit set de puncte.
Dacă în orice moment există o vecinătate a punctului ca aparținând sau care nu aparțin setului M, atunci punctul este numit un punct de delimitare a setului.
Setul tuturor punctelor de frontieră din multitudinea de M este marginea sa. Acest lucru este ilustrat prin fig. 1.
Dacă setul M nu conține oricare dintre punctele sale limită, este numit deschis (adică, fiecare punct al unui set deschis este intern).
Dacă setul M conține toate punctele sale limită, se spune să fie închis. În viitor, vom lua în considerare doar seturi închise.
Dacă setul M nu conține oricare dintre punctele sale limită, este numit deschis (adică, fiecare punct al unui set deschis este intern).
Dacă setul M conține toate punctele sale limită, se spune să fie închis. În viitor, vom lua în considerare doar seturi închise.
Luați în considerare pe set M. Fie P planul - un punct arbitrar al setului. Este posibil într-un număr de M se deplasează punctul P, până la un punct apropiat de acesta, astfel încât, în același timp, a crescut atât coordonatele sale? Dacă P - punct interior, atunci o astfel de mișcare este posibilă. Dacă P - punctul de delimitare, atunci această mișcare nu este întotdeauna posibil. Acest lucru este ilustrat prin fig. 2
Mișcarea necesară a punctelor P1. P2. P3, P4 este posibil, și nici unul dintre punctele de ambele segmente P5 P6 și P7 P8. și arc P6 P7 o astfel de circulație nu poate fi supus. Într-adevăr, în cazul în care vă deplasați oriunde
- vertical P6 segment P5 poate crește doar punctul de L2 coordonatei (L1 coordonate, astfel, rămâne neschimbat);
- Intervalul orizontal P7 P8 poate crește numai coordonatei L1 (L2 de coordonate, astfel, rămâne neschimbat);
- creștere cu arc P6 P7 presupune diminuarea uneia coordonate diferite.
Astfel, fiecare punct al M se încadrează într-una din cele trei clase.
- Prima clasă conține puncte, fiecare dintre care pot fi deplasate, astfel încât, la aceasta a crescut atât coordonatele și punctul în sine rămâne în setul M (în această clasă cuprinde toate punctele interioare ale M și unele dintre punctele sale limită (de exemplu, P2)).
- A doua clasă cuprinde puncte, fiecare dintre acestea pot fi deplasate într-o multitudine de M numai dacă creșterea doar una dintre coordonatele sale, menținând în același timp a doua valoare (punctul unui segment de linie verticală și un punct de P5 P6 P7 P8 segment orizontal).
- A treia categorie conține puncte, fiecare dintre acestea pot fi deplasate într-o multitudine de M numai când reducerea a cel puțin una dintre coordonatele (arc P6 P7).
O pluralitate de a treia clasă se numește punctele de delimitare (o multitudine de) un set dat de Pareto M. Se spune adesea că limita Pareto set M - este un set de puncte de la care nu se pot deplasa la „nord“, „est“ și „nord-est“, stau într-o varietate de M. Se crede că cea mai bună soluție a unei probleme multicriteriale trebuie căutată printre setul Pareto . Prin urmare, construcția Pareto adesea considerat un prim pas necesar în rezolvarea oricărei probleme multiobiectiv.