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