PODSTAWY OPTYMALIZACJI

WIELOKRYTERIALNEJ

(WYKŁAD ROZSZERZONY)

prof. dr hab. inż. Andrzej AMELJAŃCZYK

INSTYTUT SYSTEMÓW INFORMATYCZNYCH

WYDZIAŁ CYBERNETYKI WAT

WARSZAWA - 2012

WOJSKOWA AKADEMIA
TECHNICZNA

im. Jarosława Dąbrowskiego

2

Wojskowa Akademia Techniczna

12.12.2021

3. PRZESTRZENIE Z RELACJĄ

(R – PRZESTRZENIE)

(PRZESTRZENIE RELACYJNE)

WOJSKOWA AKADEMIA
TECHNICZNA

im. Jarosława Dąbrowskiego

3

Wojskowa Akademia Techniczna

12.12.2021

PRZESTRZENIE Z RELACJĄ

(R – PRZESTRZENIE)

(PRZESTRZENIE RELACYJNE)

NIECH

- ZBIÓR, KTÓRY NAZYWAĆ BĘDZIEMY PRZESTRZENIĄ

- ZBÓR MOŻLIWYCH PODZBIORÓW

NIECH , ZBIÓR

NAZYWAĆ BĘDZIEMY RELACJĄ

 

DEFINICJA 1

PRZESTRZENIĄ Z RELACJĄ (R – PRZESTRZENIĄ, PRZESTRZENIĄ RELACYJNĄ)
NAZYWAĆ BĘDZIEMY PARĘ UPORZADKOWANĄ

 

WOJSKOWA AKADEMIA
TECHNICZNA

im. Jarosława Dąbrowskiego

4

Wojskowa Akademia Techniczna

12.12.2021

PRZESTRZENIE Z RELACJĄ c.d.

KAŻDY ZBIÓR GENERUJE ZBIÓR RELACJI DWUCZŁONOWYCH CZYLI, TYM
SAMYM ZBIÓR PRZESTRZENI RELACYJNYCH

JEŚLI JEST RELACJĄ PORZĄDKU TO PRZESTRZEŃ RELACYJNĄ NAZYWAMY
PRZESTRZENIĄ UPORZĄDKOWANĄ (QASIUPORZĄDKOWANĄ, LINIOWO
UPORZADKOWANĄ itp.)

NIECH - PEWIEN PODZBIÓR

ZBIOREM UPORZĄDKOWANYM NAZYWAMY PARĘ UPORZĄDKOWANĄ

– RELACJA ZWROTNA, ANTYSYMETRYCZNA I PRZECHODNIA

 

WOJSKOWA AKADEMIA
TECHNICZNA

im. Jarosława Dąbrowskiego

5

Wojskowa Akademia Techniczna

12.12.2021

PRZYKŁAD 1
DANY JEST STOŻEK

ORAZ ZBIÓR , STOŻEK GENERUJE RELACJĘ

Rys. 1 Zbiór uporządkowany

UWAGA 1
CZASAMI PISZEMY: LUB LUB
UWAGA 2

 

PRZESTRZENIE Z RELACJĄ c.d.

L

C

B

A

E

D

�

1

 

�

2

 

WOJSKOWA AKADEMIA
TECHNICZNA

im. Jarosława Dąbrowskiego

6

Wojskowa Akademia Techniczna

12.12.2021

WŁASNOŚCI ZBIORÓW W PRZESTRZENI Z RELACJĄ

NIECH

- PRZESTRZEŃ Z RELACJĄ

O ZBIORACH ZAKŁADAMY JEDYNIE, ŻE SĄ NIEPUSTE

 

ZBIORY JAKO PODZBIORY PRZESTRZENI Z RELACJĄ POSIADAJĄ

SZCZEGÓLNE WŁASNOŚCI ORAZ SZCZEGÓLNE ELEMENTY ZWANE

ELEMENTAMI EKSTREMALNYMI.

 

DLA PRZYPADKU GDY JEST RELACJĄ PORZĄDKU ISTNIEJE WIELE DEFINICJI

TYCH WŁASNOŚCI (ELEMENTÓW) I ODPOWIEDNICH TWIERDZEŃ (TEORIA

PRZESTRZENI UPORZĄDKOWANYCH).

 

WOJSKOWA AKADEMIA
TECHNICZNA

im. Jarosława Dąbrowskiego

7

Wojskowa Akademia Techniczna

12.12.2021

WŁASNOŚCI ZBIORÓW W PRZESTRZENI Z RELACJĄ

NA POTRZEBY OGÓLNEJ TEORII OPTYMALIZACJI NIE BĘDZIEMY
ZAKŁADALI, ŻE JEST PORZĄDKIEM
BĘDZIE DOWOLNYM PODZBIOREM

MODELEM PREFERENCJI

DECYZYJNYCH

 

ELEMENT NAMNIEJSZY ZBIORU JEST „POPRZEDNIKIEM” WSZYSTKICH
POZOSTAŁYCH ELEMENTÓW ZE ZBIORU

 

DEFINICJA 2

ELEMENT NAZYWAĆ BĘDZIEMY ELEMENTEM NAJMNIEJSZYM ZBIORU JEŚLI
DLA KAŻDEGO ZBIÓR WSZYSTKICH ELEMENTÓW NAJMNIEJSZYCH ZBIORU

OZNACZAĆ BĘDZIEMY SYMBOLEM

 

WOJSKOWA AKADEMIA
TECHNICZNA

im. Jarosława Dąbrowskiego

8

Wojskowa Akademia Techniczna

12.12.2021

PRZYKŁAD 2

Rys. 2 Zbiór

Rys. 3 Zbiór

 

PRZESTRZENIE Z RELACJĄ c.d.

L

1

C

B

A

E

D

�

1

 

�

2

 

F

G

L

2

C

B

A

E

D

�

1

 

�

2

 

F

G

WOJSKOWA AKADEMIA
TECHNICZNA

im. Jarosława Dąbrowskiego

9

Wojskowa Akademia Techniczna

12.12.2021

PRZYKŁAD 3

BARDZO CZĘSTO (SZCZEGÓLNIE, GDY JEST PORZĄDKIEM)
ZBIÓR JEST PUSTY

Rys. 4 Zbiór

 

PRZESTRZENIE Z RELACJĄ c.d.

L

C

B

A

E

D

�

1

 

�

2

 

y

WOJSKOWA AKADEMIA
TECHNICZNA

im. Jarosława Dąbrowskiego

10

Wojskowa Akademia Techniczna

12.12.2021

PRZYKŁAD 4

Rys. 5 Zbiór

 

PRZESTRZENIE Z RELACJĄ c.d.

L

y

�

1

 

�

2

 

WOJSKOWA AKADEMIA
TECHNICZNA

im. Jarosława Dąbrowskiego

11

Wojskowa Akademia Techniczna

12.12.2021

WŁASNOŚCI ZBIORÓW W PRZESTRZENI Z RELACJĄ

DEFINICJA 2
ELEMENT NAZYWAĆ BĘDZIEMY ELEMENTEM MINIMALNYM ZBIORU JŻELI
NIE ISTNIEJE WŚRÓD POZOSTAŁYCH ELEMENTÓW ZBIORU TAKI ELEMENT,
ŻE .
ZBIÓR WSZYSTKICH ELEMENTÓW MINIMALNYCH ZBIORU

OZNACZAĆ

BĘDZIEMY SYMBOLEM

ELEMENT MINIMALNYM ZBIORU TO TAKI ELEMENT DLA KTÓREGO NIE
ISTNIEJE WŚRÓD POZOSTAŁYCH ELEMRNTÓW ZBIORU ELEMENT, KTÓRY
BYŁBY JEGO POPRZEDNIKIEM.
UWAGA 3
JEŚLI JEST PORZADKIEM TO ZACHODZI:

a)

b)

 

WOJSKOWA AKADEMIA
TECHNICZNA

im. Jarosława Dąbrowskiego

12

Wojskowa Akademia Techniczna

12.12.2021

WŁASNOŚCI ZBIORÓW W PRZESTRZENI Z RELACJĄ

ZBIORY , MOŻNA TRAKTOWAĆ JAKO WARTOŚCI NASTĘPUJĄCYCH FUNKCJI
(ODWZOROWAŃ):

ELEMENTY ZBIORÓW ORAZ NAZYWAMY ELEMENTAMI EKSTREMALNYMI
ZBIORU W PRZESTRZNI Z RELACJĄ (CZASAMI NAZYWAMY JE
CHARAKTERYSTYKAMI WEWNĘTRZNYMI ZBIORU ).

UWAGA 4
PROBLEM ISTNIENIA (NIE ISTNIENIA) ELEMENTÓW EKSTREMALNYCH
ZBIORU WYNIKA Z WŁASNOŚCI ZBIORU I RELACJI .

 

WOJSKOWA AKADEMIA
TECHNICZNA

im. Jarosława Dąbrowskiego

13

Wojskowa Akademia Techniczna

12.12.2021

PRZESTRZENIE Z RELACJĄ c.d.

L

2

�

1

 

�

2

 

PRZYKŁAD 5

Rys. 6 Brak elementów minimalnych Rys. 7

 

L

1

C

B

A

E

D

�

1

 

�

2

 

F

C

B

A

E

D

F

WOJSKOWA AKADEMIA
TECHNICZNA

im. Jarosława Dąbrowskiego

14

Wojskowa Akademia Techniczna

12.12.2021

PRZYKŁAD 6

Rys. 8

 

PRZESTRZENIE Z RELACJĄ c.d.

L

C

B

A

E

D

�

1

 

�

2

 

F

WOJSKOWA AKADEMIA
TECHNICZNA

im. Jarosława Dąbrowskiego

15

Wojskowa Akademia Techniczna

12.12.2021

WŁASNOŚCI ZBIORÓW W PRZESTRZENI Z RELACJĄ

DEFINICJA 6
ELEMENT NAZYWAĆ BĘDZIEMY ELEMENTEM NAJWIĘKSZYM ZBIORU JEŚLI DLA
KAZDEGO
ZBIÓR WSZYSTKICH ELEMENTÓW NAJWIĘKSZYCH ZBIORU OZNACZAĆ BĘDZIEMY
SYMBOLEM

DEFINICJA 7
ELEMENT NAZYWAĆ BĘDZIEMY ELEMENTEM MAKSYMALNYM ZBIORU JEŚLI WŚRÓD
POZOSTAŁYCH ELEMRNTÓW ZBIORU NIE ISTNIEJE TAKI, KTÓRY BYŁBY JEGO
NASTĘPNIKIEM.
ZBIÓR WSZYSTKICH ELEMENTÓW MAKSYMALNYCH OZNACZAĆ BĘDZIEMY SYMBOLEM

UWAGA 5
JEŚLI JEST RELACJĄ PORZĄDKU TO ZACHODZI:

a)

b)

 

WOJSKOWA AKADEMIA
TECHNICZNA

im. Jarosława Dąbrowskiego

16

Wojskowa Akademia Techniczna

12.12.2021

PRZYKŁAD 7

Rys. 9

Rys. 10

 

PRZESTRZENIE Z RELACJĄ c.d.

L

1

C

B

A

E

D

�

1

 

�

2

 

G

F

L

2

C

B

A

E

D

�

1

 

�

2

 

F

G

WOJSKOWA AKADEMIA
TECHNICZNA

im. Jarosława Dąbrowskiego

17

Wojskowa Akademia Techniczna

12.12.2021

WŁASNOŚCI ZBIORÓW W PRZESTRZENI Z RELACJĄ

ELEMENTY NAJWIĘKSZE I MAKSYMALNE ZBIORU NAZYWAMY ELEMENTAMI
EKSTREMALNYMI BIORU

.

TWERDZENIE 1
JEŚLI TO DLA DOWOLNEGO ZACHODZI:

a)
b)
c)
d)

TWERDZENIE 2

JEŚLI

()

TO

()

TWERDZENIE 3
JEŚLI JEST ANTYSYMETRYCZNA TO:

a)
b)

 

WOJSKOWA AKADEMIA
TECHNICZNA

im. Jarosława Dąbrowskiego

18

Wojskowa Akademia Techniczna

12.12.2021

OGRANICZENIA I KRESY ZBIORÓW W PRZESTRZENI Z

RELACJĄ

NIECH
DEFINICJA 8
OGRANICZENIEM DOLNYM ZBIORU NAZYWAĆ BĘDZIEMY TAKI ELEMENT ŻE DLA
KAŻDEGO .
SYMBOLEM

OZNACZAĆ BĘDZIEMY ZBIÓR WSZYSTKICH OGRANICZEŃ DOLNYCH

ZBIORU W PRZESTRZNI Z RELACJĄ

DEFINICJA 9
OGRANICZENIEM GÓRNYM ZBIORU NAZYWAĆ BĘDZIEMY TAKI ELEMENT ŻE DLA
KAŻDEGO .
SYMBOLEM

OZNACZAĆ BĘDZIEMY ZBIÓR WSZYSTKICH OGRANICZEŃ GÓRNYCH

ZBIORU W PRZESTRZNI Z RELACJĄ

DEFINICJA 10
JEŚLI ZBÓR JEST OGRANICZONY OD DOŁU

()

ORAZ OD GÓRY

()

TO MÓWIMY, ŻE ZBIÓR JEST OGRANICZONY.

 

WOJSKOWA AKADEMIA
TECHNICZNA

im. Jarosława Dąbrowskiego

19

Wojskowa Akademia Techniczna

12.12.2021

OGRANICZENIA I KRESY ZBIORÓW W PRZESTRZENI Z

RELACJĄ

DEFINICJA 11
KRESEM DOLNYM ZBIORU W PRZESTRZNI Z RELACJĄ NAZYWAMY TAKI ELEMEN ŻE

DLA KAŻDEGO .

ZBIÓR KRESÓW DOLNYCH ZBIORU OZNACZAĆ BĘDZIEMY SYMBOLEM

JEST TO ZATEM ZBÓR ELEMENTÓW NAJWIĘKSZYCH ZBIORU OGRANICZEŃ DOLNYCH
ZBIORU

DEFINICJA 12
KRESEM GÓRNYM ZBIORU W PRZESTRZNI Z RELACJĄ NAZYWAMY TAKI ELEMEN ŻE

DLA KAŻDEGO .

ZBIÓR KRESÓW GÓRNYCH ZBIORU OZNACZAĆ BĘDZIEMY SYMBOLEM

JEST TO ZATEM ZBÓR ELEMENTÓW NAJMNIEJSZYCH ZBIORU OGRANICZEŃ DOLNYCH
ZBIORU
.

 

WOJSKOWA AKADEMIA
TECHNICZNA

im. Jarosława Dąbrowskiego

20

Wojskowa Akademia Techniczna

12.12.2021

WŁASNOŚCI ZBIORÓW W PRZESTRZENI Z RELACJĄ

ZWIĄZKI ZBIORÓW EKSTREMALNYCH Z KRESAMI ZBIORÓW

a)
b)
c)
d)

ZBIORY NAZYWAMY CHARAKTERYSTYKAMI ZEWNĘTRZNYMI
ZBIORU W PRZESTRZNI Z RELACJĄ .

WARUNKI INSTNIENIA TYCH ZBIORÓW (NIEPUSTYCH) WYNIKAJĄ Z
WŁASNOŚCI ZBIORU

ORAZ ZBIORU (RELACJI)

 

WOJSKOWA AKADEMIA
TECHNICZNA

im. Jarosława Dąbrowskiego

21

Wojskowa Akademia Techniczna

12.12.2021

PRZYKŁAD 8

Rys. 11 Kresy zbioru

Rys. 12 Kresy zbioru

,

,

,

,

,

,

 

PRZESTRZENIE Z RELACJĄ c.d.

L

1

C

B

A

E

D

�

1

 

�

2

 

F

L

2

C

B

A

E

D

�

1

 

�

2

 

F

WOJSKOWA AKADEMIA
TECHNICZNA

im. Jarosława Dąbrowskiego

22

Wojskowa Akademia Techniczna

12.12.2021

PRZYKŁAD 9

Rys. 13 Kresy zbioru

Rys. 14 Kresy zbioru

 

PRZESTRZENIE Z RELACJĄ c.d.

L

1

C

B

A

E

D

�

1

 

�

2

 

G

F

L

2

C

B

A

E

D

�

1

 

�

2

 

G

F

WOJSKOWA AKADEMIA
TECHNICZNA

im. Jarosława Dąbrowskiego

23

Wojskowa Akademia Techniczna

12.12.2021

PRZYKŁAD 10
Relacja zadana grafem

 

PRZESTRZENIE Z RELACJĄ c.d.

,

 

Rys. 15 Zadanie z grafem