TEORIA PODEJMOWANIA DECYZJI
całość
by prof. O. Kapliński
Str. 2
Systemy eksperckie są interaktywnymi programami komputerowymi łączącymi w sobie:
" Sądy
" Doświadczenia
" Praktyczne rady
" Intuicje
" I inne ekspertyzy
pozwalającymi uzyskać odpowiedzi dotyczące różnych zadań.
Sposób używania wiedzy!
Tradycyjne programy I dane
II program
SE mechanizm wnioskujący, który operuje na bazie wiedzy
zbiór faktów zwanych bazą wiedzy.
3-8: rys.
Str. 9
Celem jest zaprojektowanie optymalnego zestawu obiektów (spośród wielu
możliwych wariantów) ze względu na jedno lub kilka wymienionych kryteriów:
(max wydajność, min czas realizacji, min koszty, min straty, max zharmonizowanie)
oraz sporządzenie projektu technologii i organizacji robót dla przyjętego zestawu.
Problem polega na zapewnieniu takich środków aby możliwe było wznoszenie ścian z
prędkością optymalną, uwarunkowaną czasem twardnienia betonu, co wymaga kompleksowej
mechanizacji robót (aby wydajność maszyn i zespołów roboczych dostosowana była do
postępu ślizgu).
1
Str. 11
Istnieją różnice i trudności zastosowania ES projektowaniu TOB (w przeciwieństwie
do projektowania i doboru części maszyn, czy też zastosowań w diagnostyce).
Z powodu odmiennego charakteru zastosowań w projektowaniu TOB zaistniała
potrzeba wyłonienia 2 baz reguł:
" Mikroreguł- opisujących proces technologiczny
" Makroreguł- które sterują mikroregułą i które rządzą procesem projektowania.
12-16:rys
Str. 17
Problematyka TPD:
1. wg zasad racjonalnego podejmowania decyzji
2. wg sposobów decyzyjnych.
Zasada gospodarności (racjonalnego działania)
Zasady organizacji i zarządzania:
cykl działań zorganizowanych.
Czynniki optymalizacji decyzji :
a) osoba podejmująca decyzje (decydent)
b) cel działania gospodarnego
c) co najmniej 2 sposoby działania
d) informacje (środki, warunki, działanie)
e) kryterium optymalnego wyniku
Definicja- prakseologiczne kategorie:
a) wytyczony cel
b) stan spraw
c) jednolitość merytoryczna celu oraz informacji dotyczących stanu spraw
Fazy procesu decyzyjnego
Zasady dobrego współdziałania partnerów na etapie przygotowania transakcji:
" zasada swobody przepływów informacyjnych
" zasada zintegrowania czynności ofertowych
" zasada autopsji w procesach projektowych
" zasada jednolitości stosowanych wobec klienta
" zasada tożsamości osób przygotowujących i realizujących transakcje ekspresową
Zasady współdziałania partnerów na etapie realizacji transakcji ekspresowej:
" zasada jednolitości stanowisk wobec klienta
" zasada tożsamości osób przygotowujących i realizujących transakcje
" zasada jednolitej organizacji na placu budowy
" zasada centralnego zaplecza placu budowy
Dwie klasy teorii decyzji:
1. Teoria decyzji racjonalnych (TDR)
2. Psychologiczna teoria decyzji (PTD)
- Adaptacyjna teoria decyzji (ATD)
TDR: - rozwój dzięki BO
- część prokseologi
- teoria DR formułuje racjonalne (optymalne) metody rozwiązywania poszczególnych
typów zadań decyzyjnych (opierających się na pewnych postulatach racjonalności )
Postulaty dotyczące racjonalności:
" Postulat konsekwencji- głosi że, dla podjęcia decyzji racjonalnych decydent musi
uporządkować zbiór alternatyw z punktu widzenia swoich preferencji.
2
" Postulat maksymalizacji- głosi że, warunkiem koniecznym racjonalnej decyzji jest
stosowanie przez decydenta maksymalizacji, czyli wybieranie tego działania które
maksymalizuje.
Normatywna teoria decyzji: opiera się na racjonalności instrumentalnej- formułuje się
dyrektywy dotyczące optymalnych środków dla osiągnięcia optymalnych celów.
Racjonalność aksjologiczna: dyrektywy jak dobierać ale konstruktywnie.
Racjonalność metodologiczna: formułuje przepisy postępowania, które realizuje się w danym
przypadku i sytuacji, informacje jakimi dysponuje decydent należy uznać za optymalne.
Cechy charakterystyczne TDR:
1. racjonalne rozwiązania zależą od struktury zadania decyzyjnego- rodzaje parametrów i
zmiennych które w zadaniu występują jednoznacznie wyznaczają reakcje
(rozwiązania) optymalne.
2. w klasycznym sformułowaniu teoria ta jest teorią zadań decyzyjnych
3. jest teorią decyzji bez decydenta- pomija się (całkowicie lub częściowo)
charakterystykę decydenta jako układu podejmującego decyzje.
Przy formułowaniu rozwiązań optymalnych nie bierze się pod uwagę wielu ważnych
zmiennych psychologicznych takich jak: -ograniczone możliwości poznawcze
człowieka
-jego zdolności uczenia się
-szybkość przetwarzania informacji
BO- nie bierze pod uwagę zmiennych psychologicznych i socjologicznych.
4. TDR jest jednym z wariantów teorii behawiorystycznej typu S-R.
 Behawiorystyczny charakter omawianej teorii [TDR]- fakt, że nie uwzględnia ona w
odpowiednim zakresie zmiennych psychologicznych takich jak szybkość
przetwarzania informacji czy cechy osobowości, w dużym stopniu ogranicza jej
wartość praktyczną i powoduje, że wiele spośród racjonalnych rozwiązań tego typu
budzi zasadnicze wątpliwości.
- probabilistyczne uczenie się
- optymalna strategia przewidywania
- maksymalizacja wartości oczekiwanej
- strategia wszystko i nic
- strategia dopasowywania
5. Twórcy TDR opracowali zasad postępowania, które okazały się użyteczne w praktyce
i które wpływały na rozwój badań psychologicznych.
Bez znajomości tej teorii nie sposób dzisiaj prowadzić jakichkolwiek prac
empirycznych, których celem jest poznanie jak ludzie rzeczywiście podejmują
decyzje.
Psychologiczna teoria podejmowania decyzji [PTD]
Wpływ TDR:
Problistatystyka, ekonomia
Cele normatywne
Ale PTD- deskryptywne: -jak ludzie rzeczywiście dokonują wyboru?
-jak naprawdę rozwiązują oni zadania decyzyjne?
Kierunek behawiorystyczny:
Teoria behawioralna raczej do klasy teorii typu S-R
PTD jest systemem uzasadnionych twierdzeń o rozwiązywaniu przez ludzi zadań
decyzyjnych. Próbuje ona przewidzieć i wyjaśnić procesy decyzyjne.
3
Trzy istotne cechy tej teorii:
1. Przedmiot teorii PTD: są czynności decydenta w procesie rozwiązywania zadań
decyzyjnych .
Aby przewidzieć i wyjaśnić te czynności należy poznać zarówno strukturę zadań
decyzyjnych jak i ważne cechy decydenta.
Analiza zadań decyzyjnych jest ważną czynnością badawczą ponieważ ich struktura w
dużym stopniu warunkuje zachowania się człowieka
ZD są różnorodne: -sytuacje proste; -sytuacje skomplikowane
Struktura ZD { alternatywy
wartość wyników (dla podmiotu)
warunki (stan rzeczy)
sytuacje (nieustrukturalizowane)
Struktura cech decydenta { niezmienniki (cechy układu podejmującego decyzje )
skierowanie na określone cele (jedna z najważniejszych
cech decydenta)
właściwości poznawcze decydentów
Aby przewidzieć i wyjaśnić czynności decyzyjne człowieka należy poznać zarówno
strukturę zadań decyzyjnych, jak i strukturę cech decydenta.
2. System twierdzeń.
Twierdzenia teorii (5 klas):
1. tworzenie reprezentacji zadania decyzyjnego
2. użyteczność wyników (konsekwencji)  stąd ocena subiektywna wartości wyników
3. subiektywne prawdopodobieństwo stanów rzeczy determinujące wyniki
(konsekwencje) decyzji.
-przecenianie prawdopodobieństw zdarzeń o małym P
-niedocenianie pr. zdarzeń bardzo prawdopodobnych
4. twierdzenia o strategiach wyboru działania. Wybór strategii maksymalizującej
subiektywnie oczekiwaną użyteczność.
5. czynniki, które sterują procesem decyzyjnym
-środowisko zewnętrzne
-organizacja osobowości decydenta
-wpływ grupy społecznej
Np.: *im silniejsza potrzeba agresji i dominacji występuje u decydenta, tym wyższy
akceptuje on poziom ryzyka
*decyzje podejmowane kolegialnie są bardziej ryzykowne niż decyzje
indywidualne.
Wniosek: PTD stanowi system komplementarny w stosunku do teorii rozwiązań
racjonalnych [TDR]
3. Metody uzasadniania twierdzeń.
- eksperyment laboratoryjny
- modelowanie
-symulacja czynności decyzyjnych
[PTD] jest jedną z wielu teorii psychologicznych:
Szczeble ogólności decyzji
1. ogólna: t. behawiorystyczna; t. psychoanalityczna
2. średniego stopnia ogólności: teoria motywacji, teoria myślenia
3. najwyższa
4
PTD jest teorią średniego zasięgu odnoszącą się do podzbioru zadań nazywanego zadaniami
decyzyjnymi. Bardziej ogólną od niej jest teoria czynności.
Funkcje teorii:
1. funkcja predyktywna- przewidywanie zachowań człowieka (pozwala ona przewidzieć
strukturę i ukierunkowanie czynności decyzyjnych z dużym prawdopodobieństwem)
2. funkcja eksplanacyjna- polega na opisie i wyjaśnieniu wewnętrznych mechanizmów
ludzkich. Eksplanacja jest najważniejszą funkcją PTD.
Pewne twierdzenia naukowe mogą mieć dużą wartość predyktywną, a jednocześnie
nie posiadać żadnego znaczenia eksplamacyjnego
3. funkcja praktyczna PTD nie może dostarczyć gotowych i łatwych rozwiązań dot.
podejmowania decyzji
8 rodzajów zadań decyzyjnych:
Wymiary środowiska.
Podejmowanie sekwencji decyzji.
Zadania są częścią środowiska w jakim człowiek działa.
Środowisko- zarówno naturalne jak i społeczne. Można przedstawić jako przestrzeń
trójwymiarową:
- niepewność
- dynamika �!modyfikacje, przeobrażenia z biegiem czasu
- złożoność �!liczba zmiennych
�!stopień konfliktowości interesów
Główne rodzaje zadań:
Każde ZD można przedstawić jako punkt uporządkowany trójką liczb (x, y, z)
5
x- stopień niepewności
y- stopień dynamiki
z- stopień złożoności zadania decyzyjnego
8 typów zadań:
" Rogi 1,2,3,4 to zadania deterministyczne- warunki pewności, zadania nie ryzykowne.
Każda alternatywa prowadzi do jednoznacznie określonych wyników.
Zadania deterministyczne mogą być:
-proste i statyczne (róg1)
-złożone i statyczne (róg2)
-proste i dynamiczne (róg3)
-złożone i dynamiczne (róg4)
" Zadania ryzykowne- probabilistyczne (rogi 5,6,7,8)
-proste i statyczne (róg5)
-złożone i statyczne (róg6)
-proste i dynamiczne (róg7)
-złożone i dynamiczne (róg8)
Odmiany paradygmatycznego postępowania adaptacyjnego:
Zasada racjonalnego gospodarowania hipoteza ograniczonej racjonalności
Optymalizacja stany zadowalające
Hipoteza o równowadze (systemu gospodarczego) działania na osiągnięcie homeostazy
(pozycja pozwalająca istnieć, przeżyć)
Reguły procesów adaptacji (adaptory) klasy:
a) Zmiana sposobu działania zależnie od zmian otoczenia,
b) Algorytmy uczenia się,
c) Reguły optymalizacyjne
Typy problemów z psychologią punktu widzenia:
Typ I: w sytuacji początkowej S0 dane są wszystkie potrzebne informacje, tak iż rozwiązanie
problemu polega jedynie na dokonaniu ich kombinacji. Problemy te mają tylko jedno
poprawne rozwiązanie.
Typ II: sytuacja początkowa S0 zawiera również wszystkie niezbędne informacje. Jednak cel
nie jest jednoznacznie określony. Problemy te mają więcej niż jedno rozwiązanie.
Typ III: dane początkowe S0 są całkowicie lub częściowo niedostępne, jednak cel jest
określony jednoznacznie. Problemy te mają jedno poprawne rozwiązanie.
Typ IV: zarówno sytuacja początkowa jak i cel są zupełnie nieokreślone. W problemach tych
istnieje wiele poprawnych rozwiązań.
Podstawowe rodzaje problemów:
Problemy poznawcze Co jest co?
Co jest jakie?
Co od czego zależy?
Problemy decyzyjne Jakie z wielu możliwych działań wybrać?
Problemy projektowe jak co osiągnąć?
6
Zasadnicze systemy funkcjonalne człowieka:
Układ Układ Układ
orientacji decyzji wykonania
Problematykę teorii podejmowania decyzji można ująć według 2 kierunków:
1) Zasad racjonalnego podejmowania decyzji (ujęcie normatywne)
2) Sposobów decydowania.
Zasady racjonalnego podejmowania decyzji są domeną takich dyscyplin naukowych jak:
Filozofia (etyka i prakseologia)
Matematyka (logika mat., badania operacyjne, statystyka)
Cybernetyka (teoria informacji, teoria regulacji i sterowania)
Inne
f
m
i
c
Z punktu widzenia etyki decyzja dobra może być wartością subiektywną bądz
wspólną
wartością akceptowaną przez ludzi
Prakseologią nazywamy ogólną teorię sprawnego działania . wprowadza między
innymi zasady działań racjonalnych, rozpatrując znaczenia i związki zachodzące między
takimi pojęciami jak cel, dzieło, działanie, sprawca, oszczędność, marnotrawstwo, skutek itp.
W ten sposób zajmuje się ona również warunkami prawidłowych decyzji w ogóle, a zatem i
decyzji o charakterze gospodarczym.
Na decyzje gospodarcze ma wpływ wiele zjawisk, które dają się zmierzyć, czyli
wyrazić przy pomocy liczb. Daje to możliwość zastosowania metody analizy matematycznej
przy wyraz
nych korzyściach gospodarczych. Stąd takie pojęcia jak badania operacyjne lub
teoria podejmowania decyzji używane są jako pojęcia zamienne powyższego kierunku
myślowego (choć niewłaściwie).
Centralnym punktem zainteresowania matematycznego podejścia do problemów
decyzji stało się określenie decyzji optymalnej, czyli najlepszej w danych warunkach. Zasady
(cele, kryteria) optymalnej decyzji są jednak różne w różnych warunkach, a przede wszystkim
szczeblach zarządzania czy podejmowania decyzji.
Lepszym rozwiązaniem , w ujęciu np. kompleksowym jest zastosowanie aparatu
pojęciowego cybernetyki. Nie wszystkie istotne zjawiska wpływające na kształt i formę
decyzji dają się zmierzyć. Powoduje to konieczność uwzględniania w rachunku zjawisk
niewymiernych. W modelach matematycznych wielu zagadnień gospodarczych spotyka się
często specjalną zmienną oznaczającą wszystkie czynniki niewymierne. Z formalnego punktu
widzenia jest to słuszne, tym niemniej w obliczeniach przyjmuje się zazwyczaj, że
poszczególne składniki tej zmiennej dają w sumie 0 lub, że ich wartość oczekiwana równa się
0. jest to zapis formalny, który w praktyce pomijamy. Tak więc matematyczne podejście do
problemów decyzji nie rozwiązuje ich w sposób kompletny.
Określenie sposobów wg których ludzie rzeczywiście decydują stało się domeną
zainteresowania psychologii (to człowiek a nie maszyna podejmuje decyzje).
W ramach psychologicznego ujęcia decyzji wyodrębnić można trzy grupy problemów:
7
1. procesy przeddecyzyjne, czyli czynności przygotowawcze, poprzedzające podjęcie
ostatecznej decyzji,
2. procesy ściśle decyzyjne dotyczące wyboru celu i działania w oparciu o subiektywną
ich ocenę, czyli indywidualną skalę preferencji,
3. procesy podecyzyjne dotyczące samej realizacji decyzji.
Rozpatrujemy zjawiska gospodarcze
Wiele decyzji gospodarczych opiera się na zjawiskach wymiernych, co pozwala
stosować metody matematyczne. Za pomocą decyzji oddziałujemy w sposób najbardziej
bezpośredni na kształtowanie się zjawisk w czasie. Stąd decyzja jest jednym z ważnych
czynników regulacji i sterowania procesami zachodzącymi w przedsiębiorstwie. Uzasadnia to
wprowadzenie pojęć i metod cybernetyki.
Decyzję gospodarczą podejmuje człowiek uwzględniając warunki środowiskowe, w
których żyje i działa w oparciu o konkretne procesy myślowe. Stąd właśnie jest tu odwołanie
się do socjologii i psychologii.
W warunkach decyzji gospodarczych musimy jeszcze dodatkowo uwzględnić
czynniki czasu. Przyjmując za kryterium czynnik czasu, można wyodrębnić dwa zasadnicze
ujęci decyzji:
1. jako proces (str. 16)
2. jako moment (str. 17)
Określenie decyzji, procesu podejmowania decyzji i jego składowych
J. Zieliński:  decydowanie jest to dokonywanie nielosowego wyboru w działaniu .
 Decyzja jest to poczucie decydenta (czyli osoby podejmującej decyzje), że proces
decydowania został zakończony i że wskutek tego wie on już jak ma działać, a więc nie tylko
czego chce w danej sytuacji (a to znaczy także w danej chwili) lecz w przybliżeniu także jak
to zamierza osiągnąć.
R. Wynne, L. Ackoff i M. Sasjeni, D. Ramtrom
Rozpatrujemy to zagadnienie z punktu widzenia przedsiębiorstwa, które jest zespołem
ludzi działających. W kategoriach prakseologicznych działanie jest to  dowolne zachowanie
się zmierzające do osiągnięcia celów .
Cel działania definiuje się jako  świadomie lub podświadomie w danej chwili
antycypowanie przyszłe stany rzeczy uważane za pożądane, do których zmierzamy w naszym
działaniu .
Dla działania sam cel nie wystarcza, musi istnieć pewien czynnik, za pomocą którego
możemy określić w jakim stosunku względem pożądanego celu jesteśmy w danym momencie
czasu. Tym czynnikiem może być aktualny stan spraw w zakresie np. kosztów jednostek
produkcji określony na podstawie informacji wewnętrznych firmy.
Mamy zatem:
a) wytyczony cel do którego należy dążyć w pewnym przedziale czasu,
b) stan spraw w konkretnym, bieżącym momencie czasu, rozpoznany na podstawie
odpowiedniego zbioru informacji,
c) jednolitość merytoryczna celu oraz informacji dotyczących stanu spraw.
Znajomość celu i przyrównywanie do niego bieżących spraw. Istnieje często
konieczność wyboru celu ze zbioru celów możliwych, traktując dany konkretny stan spraw
jako punkt wyjścia. Konieczny jest wybór drogi postępowania ze zbioru wszystkich
możliwych sposobów, które są dostępne w danym momencie czasu. Wybór celu i drogi
postępowania powinien być nielosowy (oparty na kryteriach i przesłankach).
Wniosek:
W stosunku do określonego w czasie stanu spraw istnieje pewien szczególny typ
działania, polegający na nielosowym, czyli opartym na ustalonych kryteriach, wyborze ze
8
zbioru dopuszczalnych celów i metod postępowania konkretnego celu i metody działania
opartego na dostępnych zbiorach informacji. Działanie to nazywać będziemy decyzją w
ścisłym tego słowa znaczeniu lub krócej decyzją.
Wybór ten musi być odpowiednio przygotowany, przy czym w przygotowaniach tych
można wyodrębnić pewne stadia (fazy). Mamy wówczas do czynienia z procesem
podejmowania decyzji. Proces podejmowania decyzji jest procesem dynamicznym.
t1t2
Załóżmy, że w chwili t1 (start) system (np. przedsiębiorstwo) znajduje się w stanie S1
(pozycja ekonomiczna, techniczna, technologiczna, kadrowa, produkcyjna itp.= przekroje).
Stan S1 można przedstawić w postaci wektora:
S1=[s11,s12, s13, ..., s1n], którego poszczególne składowe oznaczają
wspomniane przekroje.
S1n oznacza że n- ta składowa wektora znajduje się w stanie nr 1.
Rozpatrzmy okres t2>t1 wówczas w t2s2
S2=[s21, s22, s23, ...,s2n]
Mogą zaistnieć 3 przypadki (przy t1t2) relacji między składowymi wektorów S1i S2:
1) Gdy s1i=s2i (i=1,2,3, ...,n) składowe wektorówS1 i S2 są identyczne. Dwa identyczne
stany w dwóch kolejnych okresach (momentach) czasu.
2) Gdy s1i`"s2i zmieniają się wszystkie składowe wektora S2.
3) Gdy s1i=s2i oraz s1j`"s2j (i`"j, i, j=1,2, ...,n) część składowych wektora S1 zmienia się,
a część pozostaje na niezmienionym poziomie.
Decyzje wydawane w przedsiębiorstwie mają na celu utrzymanie dotychczasowego
stanu (1) lub zmianą tego stanu (2 i 3) zgodnie z zamiarami osoby lub osób.
Czas jest pojęciem ciągłym, jednak stojąca do dyspozycji technika uniemożliwia
ciągłe (bez przerwy) informowanie o aktualnym stanie systemu. Obserwacja systemu ma
charakter skokowy.
Na tym tle konieczne jest uwzględnienie tzw. faz procesu decyzyjnego.
Np. P. Sveistrup (str. 29 tab. 1)
a) Sformułowanie problemu; wynikiem jest tu opis zagadnień określający zadanie i cel
rozwiązania problemu.
b) Rozwiązanie problemu; wynikiem jest opis rozwiązania ze względu na cel.
c) Wykonanie rozwiązania; jako wynik rozwiązania zrealizowanego w praktyce.
W procesie decydowania istotne są:
- wybór jednego spośród wariantów działania,
- cele i kroki wiodące do i od okresu wyboru (stadia poprzedzające wybór i
następujące po nim)
to drugie podejście lansowane jest obecnie w USA jako programowana metoda
rozwiązywania problemów, czyli tzw. heurystyczna metoda programowania.
Najsłuszniej jest rozpatrywać fazy procesu podejmowania decyzji z punktu widzenia
informacji (zbiorów informacji i ich przetwarzania), wówczas:
1. Faza procesu podejmowania decyzji polega na właściwym przetworzeniu będących do
dyspozycji informacji.
2. Faza analiza informacji.
3. Faza rozwiązanie problemu.
4. (Faza 1-3 przygotowaniem do powzięcia decyzji ostatecznej) przekazanie do
realizacji.
Proces podejmowania decyzji jest w rzeczywistości ciągłym przekształcaniem
informacji przechodzących kolejne fazy podejmowania decyzji. Procesy informacyjne leżą u
podstaw procesu decyzyjnego.
9
Miejsce i rola systemu decyzyjnego w systemie zarządzania układami
gospodarczymi
System zarządzania- planowo skonstruowany i w sposób planowy eksploatowany zbiór
działań zorganizowanych, którego celem jest zmiana jednego
wyróżnionego stanu danego układu gospodarczego w inny stan
wyróżniony, bardziej odpowiadający zarządzającemu.
Istota zarządzania polega na wieloetapowym procesie podejmowania decyzji, w
wyniku których dany układ gospodarczy zmienia swój stan wyróżniony.
W każdym systemie zarządzania i bez względu na skalę zarządzania (cała gospodarka
narodowa, przedsiębiorstwo) występują następujące podstawowe elementy:
1. system decyzyjny,
2. system informacyjny,
3. system technik przetwarzania informacji,
4. system struktur organizacyjnych.
Kolejność wynika z logicznego ciągu problemów jakie występują w systemie zarządzania.
(Ad. 1) Skoro istota zarządzania polega na wieloetapowym procesie podejmowania decyzji, w
wyniku którego dany układ gospodarczy zmienia swój stan wyróżniony to system decyzyjny
jest elementem wiodącym w systemie zarządzania układami gospodarczymi.
(Ad. 2) Aby podejmować decyzje niezbędne są do tego informacje. System informacyjny jest:
" drugim, zasadniczym elementem systemu zarządzania ,
" podporządkowany systemowi decyzyjnemu.
(Ad. 3) System technik przetwarzania informacji:
formalnie jest elementem systemu informacyjnego,
wyodrębniony (w autonomiczny element systemu zarządzania), ponieważ ma
duże znaczenie, stopień skomplikowania problemów w nim występujących,
duża ich ilość,
ma na celu:  obsłużenie w pierwszym rzędzie systemu informacyjnego i
pośrednio systemu decyzyjnego,
w systemie tym rozwiązywane są dwa podstawowe problemy:
przetwarzanie danych liczbowych, ściślej: sumowanie, mnożenie,
dzielenie, grupowanie danych, bilansowanie, rozliczanie,
obliczenia optymalizacyjne.
Pierwsze operacje dostarczają informacji do podejmowania decyzji poza systemem
optymalizacyjnym, a więc przy zastosowaniu metod podejmowania decyzji innych niż
metody matematyczne oraz dostarczają informacji do obliczeń optymalizacyjnych. Operacje
związane z obliczeniami optymalizacyjnymi stanowią bezpośrednie narzędzie podejmowania
decyzji za pomocą metod matematycznych. Zakłada się, że system ten bazuje na
elektronicznych maszynach.
(Ad. 4) System struktur organizacyjnych:
Sens każdej organizacji polega na tym, że pewną całość dzielimy na części w celu
zwiększenia efektywności działania całości. Podział całości na części jest uzależniony od
wielu czynników:
1. przyjęty system decyzyjny i informacyjny,
2. przyjęty system technik przetwarzania informacji,
3. przyjętą technologię procesu produkcyjnego,
4. sytuację kadrową.
Struktura organizacji danego układu gospodarczego jest fizycznym odbiciem
przyjętego systemu zarządzania i od jej poprawności zależy sprawność funkcjonowania
procesów zarządzania. Poszczególne elementy struktury organizacyjnej (tzw. komórki
10
organizacyjne) powinny uwzględniać zasadę, że każdy z tych elementów podejmuje
określone decyzje. Komórki organizacyjne, w których nie podejmuje się żadnych decyzji są
zbędnymi elementami struktury organizacyjnej i powodują wydłużenie torów
informacyjnych, a tym samym opóz
niają procesy decyzyjne.
Wniosek: System decyzyjny jest wiodącym elementem w systemie zarządzania. Od
poprawności konstrukcji tego elementu zależy w pierwszym rzędzie sprawność działania
całości systemu zarządzania.
System decyzyjny
Systemem (układem) będziemy nazywać planowo skonstruowaną i w sposób planowy
eksploatowaną pewną całość składającą się z połączonych elementów. Systemem decyzyjnym
dowolnego układu gospodarczego będziemy nazywać planowo skonstruowany i w sposób
planowy eksploatowany zbiór decyzji uruchamiający zbiory działań zorganizowanych, w
wyniku których układ gospodarczy osiąga główny cel działania.
System decyzyjny tym się różni od dowolnego zbioru decyzji, że jest on planowo
skonstruowany i w sposób planowy eksploatowany.
System decyzyjny jest ściśle związany z systemem informacyjnym. Stąd też niekiedy
łączy się te dwa style w system informacyjno-decyzyjny.
Wiodącym systemem dla każdego układu gospodarczego jest system decyzyjny a nie
system informacyjny. System decyzyjny powinien  wymuszać treść, ilość i jakość zbiorów
informacyjnych.
Przyjęcie innej koncepcji tworzenia systemów decyzyjnych a więc przyjęcie założenia
wiodącej roli systemu informacyjnego mogłoby w rezultacie doprowadzić do sytuacji, w
której są podejmowane tylko decyzje dla których istnieją informacje.
Każda decyzja jest informacją, a nie każda informacja jest decyzją. Decyzja jest
szczególnym przypadkiem informacji, która uruchamia działanie.
Planowane skonstruowanie i w sposób planowy eksploatowane systemu decyzyjnego
polega w pierwszym rzędzie na:
ustaleniu w sposób logiczny kolejności decyzji jakie muszą być podejmowane, aby
osiągnąć cel działania,
ustaleniu zbiorów informacji jakie muszą być dostarczone decydentom o działaniu,
aby mogli oni podjąć decyzje,
uszeregowanie w sposób logiczny kolejnych decydentów (kto kolejno podejmuje
decyzje),
ustalenie terminów podjęcia decyzji,
ustalenia nadawców i odbiorców decyzji oraz ich treści i formy, a więc ustaleniu kto i
do kogo ma przesłać decyzje, co ma stanowić treść tych decyzji i jak mają one być
sformułowane.
Miara informacji o wynikach produkcyjnych
Obserwacje wyników procesu produkcyjnego stanowi informację. Istotny jest zatem
pomiar stopnia uporządkowania ciągu wyników. Znając (po określeniu) prawdopodobieństwo
wszystkich możliwych wyników możemy się posłużyć miarami informacji H i R:
H- miara uporządkowania ciągu wyników (entropia).
Entropia mierzy ilość informacji, którą można uzyskać z ciągu wyników. Aby była ona
miarą odpowiednią, powinna przyjmować skrajne wartości, gdy dane są całkowicie
uporządkowane i całkowicie nieuporządkowane.
Przy całkowitym uporządkowaniu mamy do czynienia z podejmowaniem decyzji w
warunkach pewności (znajomość przyszłości). Przy całkowitym nieuporządkowaniu mamy do
czynienia z podejmowaniem decyzji w warunkach niepewności (kryterium Laplace a:
wszystkie zdarzenia uważa się za jednakowo prawdopodobne). Między tymi skrajnościami-
podejmowanie decyzji w warunkach ryzyka.
11
Pk = 0 Pklog2Pk = 0
Za jednostkę nieokreśloności przyjmujemy nieokreśloność zbioru E0
E1 E2
E0:
� �
(o dwóch jednako prawdopodobnych zdarzeniach elementarnych E1 i E2), mamy:
H(�,�) = -(� log2� +� log2� ) = -log2� = log22 = 1
Jednostkę tę nazywamy bitem i oznaczamy bit (skrót od binary digit binarna
jednostka). Podstawą dla wyboru takiej jednostki jest rozpowszechnione w praktyce
występowanie elementarnych dwojakich sygnałów 0 i 1.
Wielkość nieokreśloności na jedną literę przekazywanej informacji mierzona entropią
H jest więc miarą ilości informacji zawartej w jednej literze informacji. Np. przy n=4,
p1=p2=p3=p4=ź
H = log24 = 2[bit/litera],
przekazując jedną literę informacji zmniejszamy nieokreśloność o dwa bity i wobec tego ilość
przekazywanej informacji także stanowi dwa bity.
Porównywanie zbiorów
E1 E2 E3 E4
E: -większa nieokreśloność (dobra sytuacja)
ź ź ź ź
0,3
0,25 0,25 0,25 0,25
0,25
0,2
0,15
0,1
0,05
0
1234
E
E 1 E 2 E 3 E 4
E : -różne prawdopodobieństwa
0,97 0,1 0,1 0,1
0,97
1
0,75
0,5
0,25
0,1 0,1 0,1
0
1234
E'
12
Pk
Pk
 E  1 E  2 E  3 E  4
E  : - nie ma wartości pewnej
0,5 0,4 0,05 0,05
0,5
0,5
0,4
0,25
0,05 0,05
0
1234
E''
H = - p1logp1 - p2logp2 - p3logp3 -...- pklogpk -...- pnlogpn
n
H = - pklogpk (entropia zbioru)
"
k =1
jeśli pk = 0, wtedy pklogpk =0
pk- prawdopodobieństwo wystąpienia k-tego wyniku.
pk = p1 + p2 + p3 +...+ pk +...+ pn =1; 0d" pk d" 1
"
k
poprzednie równania były dla n wyników. Jeśli możliwy jest tylko jeden wynik, wówczas:
pk = 1
H = -(1)log(1) = 0.
Jest to sytuacja całkowicie uporządkowana. H przybiera wartość maksymalną, gdy
każdy z n wyników ma jednakowe prawdopodobieństwo wystąpienia. Wtedy:
1
pk = (k = 1,2,...,n)
n
1
Hmax = -log = logn
n
Jest to sytuacja całkowitego nieuporządkowania.
H
gdzie: H- zaobserwowana wartość; Hmax- maksymalna możliwa wartość
Hmax
Redundancja miara względnego stopnia nieuporządkowania.
R rzuca światło na stopień ukonstruowania sekwencji wyników, za pomocą względnych
wartości mieszczących się w granicach 0 i 1:
H
R= 1 -
Hmax
13
Pk
Przykłady obliczeń entropii i redundancji.
1.
Pk
0,50
0,40
0,30
0,20
0,10
0,00
12345
pk - log2 pk - pk log2 pk
0,1 3,3219 0,33219
0,1 3,3219 0,33219
0,3 1,7370 0,521
0,4 1,3219 0,529
0,1 3,3219 0,33219
1,0 2,04657 = H
Hmax = log2 (1/5) = 2,3219
2,04657
R = 1 - = 1  0,88 = 0,12
2,3219
2.
Pk
1,00
0,90
0,80
0,70
0,60
0,50
0,40
0,30
0,20
0,10
0,00
12345
pk - log2 pk - pk log2 pk
0,1 3,3219 0,33219
0,0
0,0
0,0
0,9 0,152 0,1368
1,0 0,4690 = H
14
Hmax = log2 (1/5) = 2,3219
0,4690
R = 1 - = 1  0,202 = 0,798
2,3219
WNIOSKI 50
Jeśli: H=0 , R=1 (jeden możliwy wynik)
H=Hmax R=0 (wszystkie stany jednakowo prawdopodobne)
R=1 podejmowanie decyzji w warunkach pewności
R=0 = = = = niepewności (Laplace)
0Pk 0,50
0,40
0,30
0,20
0,10
0,00
Dla rozkładu 1 2 3 4 5 (czasu pracy lub wielkości produkcji) R=0
Pk 1,00
0,90
0,80
0,70
0,60
0,50
0,40
0,30
0,20
0,10
0,00
1 2 3 4 5
Dla rozkładu (jednopunktowy) R=1
Pk 10,00
9,00
8,00
7,00
6,00
5,00
4,00
3,00
2,00
1,00
0,00
1 2 3 4 5 6 7 8 9 10 11
Dążymy do małego rozrzutu
W praktyce w budownictwie: R=0,07 do 0,16 ; rzadko >0,3.
Dla przykładu: Służewiec I zmiana R=0,16
II zm R=0,21
Im większe R tym produkcja sprawniejsza, więcej możemy powiedzieć na temat
wyników i planowania.
Dla R e" 0,3 produkcja sprawna (dobra)
R e" 0,5 produkcja bardzo sprawna
15
Współczynnik zmienności
Relacja między wartością średnią a rozrzutem wyników.
S
1. empirycznie: v =
x
2
S- średnie odchylenie kwadratowe S = S
x - wartość średnia (czas pracy lub produkcji)
2. teoretycznie:
�
x
ł =
EX
� = D2 X
x
D2X = �2 = EX2  (EX)2 = v2  v12
Wariancja równa jest różnicy momentu rzędu drugiego i kwadratu momentu pierwszego.
1
2
S = m2 = - x)2W (xi ) = - x)2 ni
"(xi "(xi
n
ii
1 �ł 1 2 �ł
2 2
S = �ł ni - ( ni ) �ł
"xi "xi
n n
�ł i i łł
EX= 0,1*0 + 0,1*1 + 0,3*2 + 0,4*3 + 0,1*4
0,5
= 2,3
0,4
0,4
EX2= 12*0,1 + 22*0,3 + 32*0,4 + 42*0,1=6,5
0,3
0,3
D2X= EX2  (EX)2 = 6,5-2,32 =1,21
0,2
0,1 0,1 0,1
� = D2 X =1,096
x
0,1
1,096
0
ł = = 0,477
1 2 3 4 5
2,3
x
Rozkłady częstości czasu pracy i wielkości produkcji
+ -
prawo skośny lewo skośny symetryczny
Skośność: miara asymetrii rozkładu moment centralny �3
+, gdy suma trzecich potęg dużych dodatnich odchyleń jest większa od sumy trzecich potęg
ujemnych odchyleń.
Współczynnik asymetrii:
16
�3
= - teoretycznie
"
3
k
�
m3
Sk = - empirycznie
3
S
1
m3 = - x)3ni
"(xi
n
Sk<-0,66- pożądane;
Sk<-1- dobrze;
Sk<-1,6-bardzo dobrze
Tendencja do symetryczności lub skośności wynikają z niestacjonarnego charakteru
pracy:
sezonowość,
różna liczba jednocześnie montowanych budynków,
zmianowość
Współczynnik nierównomierności �:
wartośa - max kmax
� = =
wartośa - średnia
x
dla � < 1,3 produkcja b. dobra (- projektowanie powierzchni składowych,- zasobników
rezerwowych)
Współczynnik gotowości kg:
wartośa - min a
W praktyce kg= 0,45-0,7
kg = =
wartośa - średnia
x
wskazane kg= 0,7-0,9
PODEJMOWANIE DECYZJI A TECHNIKI PRZETWARZANIA INFORMACJI
Różnego typu decyzje mają przypisany im niejako czas, który upłynąć musi od chwili
postrzeżenia problemu do wydania w stosunku do niego odpowiedniej decyzji. Istnieją
następujące zależności:
" Im decyzja jest bardziej operacyjna, tym wymaga większej ilości informacji i musi
być podjęta w krótkim czasie,
" Im bardziej decyzja staje się strategiczną, tym mniej potrzebuje informacji, ale różnią
się one zasadniczo od tych, które są niezbędne przy decyzjach operacyjnych.
Rys. 1
Moc własna robotnika wynosząca około 0,1 KM, jest w obecnych warunkach
przemysłowych wzmacniana przez stosowanie nowoczesnych maszyn i urządzeń do ok 100
KM, czyli 10000 razy. Wzrost dóbr produkowanych przez przemysł rodzi tendencję do
17
specjalizacji i koncentracji oraz rozbudowanej kooperacji. Przy wymogach jakościowych i
zużyciu środków powstają skomplikowane związki  powiązania między przedsiębiorstwami.
INFORMACJA W PROCESIE PODEJMOWANIA DECYZJI
Informacja jest czynnikiem, który zwiększa naszą wiedzę o otaczającej nas rzeczywistości.
Stopień wiedzy zależy od ilości informacji.
Wg teorii informacji brak naszej wiedzy o otaczającej nas rzeczywistości rośnie tym szybciej,
im bardziej złożony (różnorodny) jest problem, którym się interesujemy.
Teoria informacji pozwala na liczbową prezentację dowolnej informacji, stwarza z tego
pojęcia specjalnie określenie operacyjne.
" Charakterystyczne cechy informacji
1. jest czymś różnym od materii i energii, choć jest z nimi związana; informacja
może być sprawcą zdarzenia, faktu, zjawiska w przyszłości, może zachować
swój byt (istnienie) niezależnie od rzeczy (faktu), której dotyczy
2. może być przenoszona w czasie i przestrzeni, przechowywana za pomocą tzw.
nośników informacji (pismo, taśma); nośnik nie jest informacją
3. informacja jest wyrażona przez wiadomość (komunikat); każda wiadomość
jest abstrakcyjnym nośnikiem informacji
4. informacja spełnia swą rolę praktyczną wówczas, gdy kierowana jest od
nadawcy do odbiorcy i gdy odbiorca może ją otrzymać
60
W praktyce posługujemy się nie informacjami  pełnymi , ale tylko dostępnymi, które nie
zawsze pozwalają w pełni opisać interesujące nas zjawisko. Różnicę pomiędzy informacją
 pełną (pożądaną) a dostępną stanowi tzw. luka informacyjna. Luka może być większa im
bardziej złożony problem.
Rys 2
18
Proces komunikacyjny
W każdym procesie wyróżniamy:
" z
ródło informacji  wytwarza wiadomość, komunikat lub ciąg wiadomości
" nadajnik  wytwarza sygnał do przekazania przez kanał
" kanał  środek użyty do przekazania sygnału
" odbiornik  rekonstruuje wiadomość na podstawie sygnału
" język (kod) w którym informacja jest przekazana od odb do nad
" adres (osoba, rzecz) dla którego wiadomość jest przeznaczona
" szumy (zakłócenia w kanale)  suma infor nadanych `" od odebranych.
Części składowe dowolnego procesu komunikacyjnego ilustruje rys. 3.
Taki proces może zachodzić między: maszyna  maszyna; maszyna  człowiek;
człowiek  maszyna; człowiek  człowiek.
Rodzaje informacji 61
Ze względu na rodzaj przekazu informacje dzielimy na:
" potoczną, np. tryb informujący o wykonaniu
" cybernetyczną, bez treści gramatycznej; każdy typ zdania (orzekające,
pytające, rozkazujące); dowolny sposób przekazu w relacji czł  czł,
czł  masz, masz  masz.
" Selektywną, miara swobody wyboru sygnału przez nadajnik lub miara
usuwania przez sygnał niepewności odbiornika.
Podział informacji (kryterium podziału dotyczy tzw. redukcji informacji)
" Pierwotna
" Pochodna
Zmiana informacji pierwotnej na pochodną dokonuje się przez redukcję informacji
pierwotnej. Redukcją nazywamy zespół czynności polegających na selekcji lub
agregacji informacji pierwotnych.
Selekcja - polega na wyborze lub doborze informacji.
Agregacja - łączenie w całość części
Informacja syntetyzująca np. wykonanie planu przedsiębiorstwa zamyka się jedną
liczbą; jako agregat wartości wszystkich wyrobów finalnych.
19
Inne podziały informacji:
" Obiektywne i subiektywne
" Istotne  tj. części informacji
" Bezpośrednie i pośrednie
" Kryterium - forma przedstawienia informacji: (tabl. 2, str. 52)
o Pisemna
o Ustna
o Audiowizualna
" Kryterium  kierunek oddziaływania informacji
o Pochodząca z zewnątrz instytucji i kierowana do niej (polecenia,
wskazówki)
o Pochodząca z instytucji i kierowana na zewnątrz
(korespondencja)
o O całkowitym obiegu wewnętrznym (kierunek pionowy i
poziomy)
" Czynnik czasu:
o Infor. periodyczne
o Infor. ciągłe
Powszechność informacji.
Pojęcie działania w 3 znaczeniach (str. 54/55)
1. wywoływanie zmian
2. funkcjonowanie (samo działanie elementu bez skutków)
3. sprawność działania
Wartość informacji
Wraz ze wzrostem ilości informacji rośnie progresywnie (nieliniowo) koszt ich
uzyskania, zmniejsza się też luka informacyjna.
20
Wnioski z rozważań str. 68
Szybkość i niezawodność niektórych typów informacji. Tabl. 3
Szybkość Niezawodność
Wyszczególnienie
i. ustna i. pisemna i. ustna i. pisemna
Informacja
średnia niska średnia wysoka
bezpośrednia
Informacja
wysoka średnia niska średnia
pośrednia
TRANSFORMACJA
Transformacja  to zbiór działań realizowanych zgodnie z określonym zbiorem reguł.
Oto kilka części składowych transformacji, które występują zawsze, choć o innej strukturze w
zależności od przedsiębiorstwa:
" cel istnienia przedsięb. (produkcja, zysk, a sprzedaż; cele systemów, a podsystemy)
" poziom techniki i technologii
" czynnik ludzki
" decyzja  jest transformacją = przekształceniem inform. wejściowych w wyjściowe
" organizacja (hierarchiczność działań; planowanie, koordynacja, kontrola).
Fazy procesu decyzyjnego są w swej istocie kolejnymi transformacjami informacji . są one
następujące:
" analiza
" sformułowanie problemu
" rozwiązanie problemu
" podejmowanie decyzji ostatecznej.
21
Tak więc proces podejmowania decyzji jest ciągiem transformacji informacji.
Schemat procesu podejmowania decyzji (rys. 8 str. 89)
Schemat analizy informacji (rys. 9 str. 92/93)
Hierarchia problemów (rys. 10 str. 98)
Prezentacja formalna problemu (rys. 11 str. 103)
Schemat rozwiązania problemu
Decyzje:
" samorodne (odruchowe, intuicyjne)
" prognostyczne
" wyrywkowe
" optymalizacyjne (probabilistyczne)
Transformacja I stopnia:
" przyswojenie informacji
" zrozumienie
" ocena przydatności
" przechowywanie informacji
Transformacja II stopnia:
" przystosowanie informacji do jej wykorzystania w działaniu
" przewidywanie działania
" przystosowanie do warunków relacji
Zasady wyboru materiału informacyjnego
1. Zasada ścisłej konfrontacji z celem
2. Zasada najmniejszego zespołu elementów informacji
3. Zasada odpowiedzialności
4. Zasada realności (rejestracji faktów stanowiących treść zbiorczych informacji)
Zjawisko zniekształceń informacji ( SZUM ).
y
RÓDA
A socjologiczno-psychologiczne:
" Złudzenia perspektywiczne
" Złudzenia emocjonalne
" Złudzenia z nasilenia uwagi
" Rzutowanie interesu własnego na percepcje
" Mechanizm tłumienia
" Własne przewidywanie
" Uprzedzenie
" Mylenie faktów z wnioskami
" Wpływ cech osobowych informatora
y
RÓDA
A techniczno-organizacyjne:
" Streszczenie
" Dezaktualizacja
" Przeładowanie
22
5. Zasada sprawnej selekcji i agregacji informacji
6. Zasada zabezpieczenia etapowego zbierania informacji
Środki zaradcze zmniejszające lub eliminujące szumy
(zwłaszcza tam, gdzie C=>C, a środki przekazu informacji są tradycyjne)
1. mnożenie niezależnych od siebie kanałów dopływu informacji (zabezpieczenie przez
konfrontację informacji)
2. narzucenie takich form i kodów informacji, które eliminują możliwie w dużym stopniu
dezinformację (m.in. epd)
3. stosowanie kar wobec osób winnych dezinformacji
4. oddzielenie informacji problemowych (służących zarządzaniu i planowaniu) od informacji
w sprawach awansów, kar itd.
71-73: rys
BADANIA OPERACYJNE (BO)
 gałąz
wiedzy o charakterze normatywnym, technika planowania posługująca się metodami
matematycznymi, polegającymi na budowaniu modeli, które muszą spełniać dwie własności:
stanowić narzędzie dla tłumaczenia znanych faktów związanych z reprezentowanym
przez model zagadnieniem, przy warunku że sprawdzający wykaże obiektywizm
pozwalać na czynienie przewidywań związanych z reprezentowanym przez model
zagadnieniem, przy warunku że sprawdzający wykaże obiektywizm
23
U: istotą BO jest wypracowanie optymalnych decyzji.
W BO można wyróżnić 4 etapy postępowania:
1. budowanie modelu  pozwala uwzględnić wszystkie istotne elementy mogące mieć
wpływ na podejmowaną decyzję
2. rozwiązanie modelu  wyznaczenie decyzji optymalnej
3. weryfikacja modelu i uzyskanego rozwiązania  jego konfrontacja z rzeczywistością
w maksymalnym zakresie
4. opracowanie systemu kontroli   życie nie jest statyczne
Sposób ujmowania problemów w BO.
Klasyfikacja problemów (tabl. 1)
Pewność Brak pewności
(1) Ryzyko (2) Niepewność (3)
Podział zasobów Symulacja Inwestycje kapitałowe
Mieszanie składników Kolejki Przetargi
Transport Zapasy Wprowadzenie wyrobu na
Ustalenie kolejności rynek
Ścieżka krytyczna Programowanie Problemy poszukiwań
Klasyfikacja zadań optymalnych (tabl. 2)
Wg postaci funkcji, kryterium Liniowe
i ograniczeń Nieliniowe
Ciągłe
Wg postaci zmiennych
Dyskretne Całoliczbowe
Deterministyczne
Wg charakteru parametrów
Statystyczne
Statyczne
Wg ilości stopni procesów
Ciągłe
decyzyjnych Dynamiczne
Dyskretne
76-78:tekst polski; 79-90: tekst angielski
24
METODY OPTYMALIZACJI
1. ŚCISA
E:
Poszukiwania wyczerpywalne
Poszukiwania sekwencyjne
a. Dychotomiczne
b. Trójdzielne
c. Zasada złotego podziału
d. Metoda Fibonacciego
2. SYSTEMATYCZNE:
Programowanie liniowe
Metody gradientu
a. Gaussa-Seidela
b. Rossenbrocka
c. Poszukiwanie wzdłuż granic funkcji celu
3. LOSOWE
4. KOMBINOWANE
Gradientowo-losowy ograniczony simplex
5. PROGRAMOWANIE DYNAMICZNE
25
Omówienie metod
POSZUKIWANIA WYCZERPYWALNE
Dana jest funkcja jednej zmiennej f(x):
Przedział, w którym poszukujemy ekstremum tej funkcji jest równy <0;13>.
Przyjmuje się ą jako długość  przedziału niepewności , tzn. długość przedziału, do którego
sprowadza się dokładność � obliczonego punktu ekstremalnego.
Liczbę obliczeń, która pozwala na znalezienie ekstremalnej współrzędnej z dokładnością ą
wyznacza się z zależności:
2
N = -1
ą
Dla przykładu jw., przy założeniu, że � =1 mamy:
1 2
ą = = 0,078 N = -1 = 26 -1 = 25
13 0,078
Metoda jest mało efektywna dla małych ą (szczególnie kiedy obliczanie funkcji celu jest
utrudnione skomplikowaną postacią samej funkcji).
POSZUKIWANIA SEKWENCYJNE
Polegają na tym, że nie są znane a priori argumenty, dla których oblicza się funkcję celu.
Sekwencja wartości argumentów zależą od obserwacji wartości funkcji celu f(x).
Metody te nie wymagają spełnienia warunku różniczkowalności czy ciągłości, a jedynie
jednomodalności.
Sekwencję wartości argumentów, dla których oblicza się funkcję celu, określa się w różny
sposób np.:
Poszukiwania dychotomiczne
= trójdzielne
= wg zasady złotego podziału
= wg metody Fibonacciego.
26
Zestawienie efektywności poszczególnych metod, którymi policzono ten sam przykład:
LICZBA PRÓB DLA
METODA SPROWADZENIA
PRZEDZIAA
U DO ą =1
Poszukiwanie wyczerpywalne 25
Poszukiwanie dwudzielne 9
Podział na 3 części 12
Podział na 4 części 8
Zasada złotego podziału 6
Podział wg Fibonacciego 6
poszukiwania dychotomiczne:
a. poszukiwany przedział (a, b) dzieli się na połowę
b. oblicza się funkcję celu w punktach
a + b � a + b �
( + ) oraz ( - )
2 2 2 2
c. sprawdza się, czy wartość funkcji celu jest większa w punkcie A, czy w punkcie B
a + b �
d. jeżeli wartość funkcji jest większa w ( + ) to odrzuca się przedział (a, A), w
2 2
przeciwnym przypadku przedział (B, b)
e. podstawia się odpowiednie wartości za lewy i prawy koniec przedziału,
f. powtarza się postępowanie od początku
Opisany proces redukuje przedział poszukiwania w każdej iteracji w przybliżeniu do połowy
Np. obliczyć liczbę prób, która pozwoli sprowadzić przedział niepewności do
tej samej wielkości ą = 1/13= 0,078. Przyjąć dokładność 0,5. Skala � =0,039.
1- � 1- 0,039
N = 2,89ln( ) = 2,89( )
ą - � 0,078 - 0,039
N H" 9
27
 poszukiwania trójdzielne:
i. poszukiwany przedział dzieli się na 3 części:
ii. odrzuca się część  najgorszą
iii. podstawia się nowe końce przedziałów
iv. powrót do początku
Dla przykładu j.w.:
N = (-4,95)ln(ą)
N = -4,95ln(0,078) = -4,95(-2,55105) H" 12
podział na 4 przedziały:
i. przedział dzieli się na 4 równe części
ii. odrzuca się część  najgorszą
iii. podstawia się nowe końce przedziałów
iv. powrót do początku
Dla przykładu j.w.:
N = 1- 2,89ln(ą)
N = 1- 2,89ln(0,078) H" 8
28
 zasada złotego podziału:
i. oblicza się wartość funkcji w punktach odległych o 0,618 od każdego z krańców
przedziału
ii. odrzuca się część najgorszą
iii. podstawia się nowe krańce przedziału
iv. powrót do początku
Z poprzedniego liczenia pozostaje zawsze jeden punkt, co zmniejsza liczbę obliczeń funkcji
celu.
Np. obliczyć (dla przykładu jw.) konieczną liczbę przeliczeń dla
zlokalizowania ekstremum z dokładnością � = 1
N = 1- 2,08ln(ą)
N = 1- 2,08ln(0,078) H" 6
METODY GRADIENTU
Warunkiem koniecznym istnienia ekstremum funkcji w pewnym punkcie jest by pochodne
"F
cząstkowe funkcji względem zmiennych w tym punkcie = 0 , i=1,2,...,n .
"xi
Kierunek gradientu funkcji F w danym punkcie M określa kierunek największej wartości
funkcji F:
Wektor gradientu wyraża się następującą formułą:
n
r
r
"F
gradF = K = ik
"
"xk
k =1
29
r
gdzie ik - wzajemne ortogonalne wektory jednostkowe
W przypadku płaszczyzny:
r
r r
"F "F
gradF = K = i1 + i2
"x1 "x2
W punkcie M0 określamy gradient, który wyznacza punkt M1.
r
K
W punkcie, w którym gradient =0 funkcja F osiąga ekstremum.
Dana jest funkcja wyników:
f (x) = f (X1, X ,..., X ) (1)
2 n
oraz funkcje nakładów:
V1 (X1, X ,..., X )
�ł łł
2 n
�ł śł
V (X ) = Vi (X1, X ,..., X ) = ............................. (2)
2 n
�ł śł
�ł śł
m 1 2 n
�łV (X , X ,..., X )�ł
r
Funkcje (1) i (2) określone są na n-wymiarowym wektorze X o nieujemnych składowych:
r
X e" 0 , czyli: x e" 0 (dla j = 1, 2, ..., n) (3)
j
Zakładamy, że funkcje (1) i (2) są ciągłe i różniczkowalne (tzn. funkcje (1) i (2) posiadają
ciągłe pochodne cząstkowe pierwszego rzędu)
Zadanie optymalizacyje:
Wyznaczyć ekstremum (min lub max) funkcji (1) poddanej ograniczeniom (2) i (3). Zadanie
ma jednoznaczne rozwiązanie, jeśli w układzie (2) m d" n.
r
1. Składowe wektora X z (3) nazywać będziemy zmiennymi decyzyjnymi zadania
optymalizacyjnego; są to zmienne xj (dla j=1, 2, ...,n).
2. Ograniczenia typu (3) nazywać będziemy warunkami brzegowymi zad. opt.;
stwierdzają one, że zmienne decyzyjne xj (dla j=1, 2, ...,n) nie mogą przyjmować
wartości ujemnych.
3. Ograniczenia typu Vi (X1, X ,..., X ) dla i=1, 2, ..., m, zawarte w (2) nazywać
2 n
będziemy warunkami ubocznymi zad. opt.
4. Funkcję wyników typu (1) zawierającą zmienne decyzyjne tylko stopnia pierwszego
nazywać będziemy funkcją liniową, np. jest to funkcja zmiennej decyzyjnej x o
postaci:
F(x) = ax + b
30
a, b  to stałe
5. Formą liniową nazywać będziemy funkcją liniową, w której występuje wyraz wolny
od zmiennej x; jest to np. funkcja zmiennej decyzyjnej x
F(x) = ax
8. Model matematyczny zad. optym., w którym funkcja wyników (1) ma postać formy
liniowej, warunki uboczne (2) mają postać nierówności lub równań liniowych, a
warunki brzegowe są dane przez (3), nazywać będziemy modelem liniowym.
Geometryczny obraz modelu liniowego w przypadku dwuwymiarowym (X1 e" 0;
X2 e" 0 ):
9. Metody rozwiązywania zadań optym., które można aproksymować modelem
liniowym nazywać będziemy METODAMI PROGRAMOWANIA LINIOWEGO.
10. Funkcję wyników typu (1) nazywamy nieliniową, jeśli zawiera ona zmienne
decyzyjne stopnia wyższego niż pierwszy. Jest nią m.in. funkcja stopnia drugiego
zmiennej decyzyjnej x :
F(x) = ax2 + bx +c a,b,c  stałe
a `" 0
31
b b2 - 4ac
p1 = - p2 = -
2a 4a
11. Warunki uboczne typu Vi (X1, X ,..., X ) dla i=1, 2, ..., m; zawarte w (2) mogą mieć
2 n
również postać równań nieliniowych lub nierówności nieliniowych:
Obraz geometryczny układu nierówności nieliniowych : V1(X1; X2) i V2(X1; X2) oraz
obszarem rozwiązań K funkcji f(X1; X2) wyznaczonego przez ten układ nierówności
nieliniowych oraz warunki uboczne: X1, X2 e" 0
12. Model matematyczny zad. optym., w którym funkcja wyników (1) ma postać funkcji
nieliniowej, warunki brzegowe (3), a warunki uboczne (2) mają postać nierówności i
równań liniowych lub nierówności i równań nieliniowych nazywać będziemy
MODELEM NIELINIOWYM.
32
13. Metody rozwiązań zad. optym., które można aproksymować modelem nieliniowym
nazywać będziemy METODAMI PROGRAMOWANIA NIELINIOWEGO.
Programowanie nieliniowe  przykład:
Przy produkcji na rynek (a nie na zlecenie), wielkości przyszłej sprzedaży są
zmiennymi losowymi. Wprowadzenie do programowania produkcji spodziewanego
rozkładu sprzedaży prowadzi najczęściej do zadania nieliniowego.
Sprzedaż każdej ilości wyrobu X z przestrzeni rozwiązań (0; H) jest jednakowo
prawdopodobne:
33
Forma zmniejszającej się funkcji sprzedaży A(r) wyrobu X jest trójkątna:
1
A(r) = - r +1
H
Względna oczekiwana sprzedaż pewnego wyrobu X jest środkiem ciężkości
płaszczyzny; w tym przypadku:
x
e(x) = - +1
2H
W celu wykluczenia ujemnego zysku krańcowego, ograniczamy przestrzeń rozwiązań
do (0, u):
c
u = (1- )H
p
gdzie:
c  zmienne koszty produkcji wyrobu X
p  cena wyrobu
g = p - c => zysk jednostkowy (w sensie zysku marginalnego).
Oczekiwanym zyskiem jest w tym przypadku:
px2
EG = pxe(x)  cx = gx -
2H
EG
Miejsce zerowe, w którym znika zysk jednostkowy , wynosi:
x
c
Ho = 2(1- )H
p
c 1
Dokładnie dla e" mamy Ho w przestrzeni rozwiązań (0, H).
p 2
2
Ho g H
EG ma dla swoje maksimum .
2 2 p
34
EG c 1
Ilustracja przykładu EG i dla > wykres oczekiwanego zysku EG oraz
x p 2
EG
zysku jednostkowego
x
Rys str. 104
Dla większej liczby wyrobów otrzymamy stąd następujące funkcje wyniku zadania
optymalizacji produkcji:
p1x1 pn xn
EG = g1x1(1- ) + ... + gn xn (1- ) = maksimum
2g1H1 2gn H
n
jest to funkcja kwadratowa  zadanie programowania
kwadratowego
Dla stałej wartości EG wykres powyższej funkcji przedstawia elipsoidę.
Dla uproszczenia: 3 wyroby (ograniczenie): X1=X, X2=Y, X3=Z.
Mamy wtedy: x1=x, x2=y, x3=z.
Umożliwia to zapisanie następującego równania elipsoidy trójosiowej:
x2 y2 z2
+ + = 1 gdzie : a, b, c, - półosie elipsoidy (gdy a = b = c
a2 b2 c2
otrzymujemy powierzchnię kuli)
rys str 105
Widać to z następującego przekształcenia:
g1H1 gnHn
(xi - )2 (xn - )2
p1 pn
+ ...+ = 1
2H1 n gi2Hi 2Hn n gi2Hi
( - EG) ( - EG)
" "
p1 i=1 2 pi pn i=1 2 pi
35
g1H1 gnHn
Punkt środkowy elipsoidy dany jest jako: , ... ,
p1 pn
n
gi2Hi
EG może mieć wartość:
"
2 pi
i=1
g1H1 gnHn
W tym przypadku elipsa przekształca się w punkt: ( , ... , )
p1 pn
Ponieważ warunki uboczne zad. opt. określają jakiś wypukły obszar rozwiązań K,
należy najpierw stwierdzić, czy punkt środkowy elipsoidy leży w K.
Jeżeli tak jest, to zostało osiągnięte optimum. W innym przypadku należy elipsoidę tak długo
rozwijać (zmniejszając EG), aż zetknie się ona po raz pierwszy z K. Ten punkt zetknięcia
wskazuje optimum.
Rys str. 106
Jest to szczególnie prosta forma zadania (najprostsze zad. programowania kwadratowego w
ogóle). Wykres funkcji wyników można interpretować jako kulę (lub koło w przestrzeni
dwuwymiarowej), a liniowe nierówności jako wypukły obszar rozwiązań.
Programowanie kwadratowe jest obecnie najbardziej rozwiniętym działem programowania
nieliniowego.
MODEL PROGRAMOWANIA LINIOWEGO
Znalez
ć wektor X = ( x1, x2, ... , xn) maksymalizujący (minimalizujący) liniową funkcję celu:
f = (c1x1 + c2x2 + ... + cixi + & + cnxn)
który spełnia układ ograniczeń:
a11x1 + a12x2 + ... + a1nxn d" b1
a21x1 + a22x2 + ... + a2nxn d" b2
& & & & & & & & & & & &
& & & & & & & & & & & &
amx1 + am2x2 + ... + amnxn d" bm
i = 1, 2, ... , m; j = 1, 2, ... , n
b1, b2, ... , bm e" 0
xi e" 0 brak str 108
36
PROGRAMOWANIE
(modele, względnie metody rozwiązywania modeli dotyczących wyznaczania ekstremum
funkcji wielu zmiennych przy założeniu, że zostaną spełnione pewne warunki dodatkowe)
Znalez
ć taki punkt (x1, x2, ..., xn), w którym dana funkcja:
f(c1, c2, ..., cn; x1, x2, ..., xn)
osiąga maximum, przy założeniu, że współrzedne: (x1, x2, ..., xn)
spełniają układ m+n nierównośći (są rozw.):
Yi(ai1, ai2, ..., ain; x1, x2, ...,xn) d" b, i = 1, 2, ..., m
x1 e" 0, x2 e" 0, ..., xn e" 0
RYSUNEK
Zbiór punktów (x1, x2, ..., xn), których współrzędne spełniają układ nierówności (2) i (3)
nazywamy zbiorem rozw. dopuszczalnych, funkcję (1)  funkcją celu lub kryterium
optymalności programu. Punkt, w którym funkcja (1) osiąga maximum optymalnym.
WST
P DO PROGRAMOWANIA
zagadnienie komiwojażera pr. Dyskr.
zagadnienie rozmieszczenia pr. Dyskr.
zagadnienie transportowe pr. Lin.
programowanie  ogólnie
Programowanie matematyczne
" progr. liniowe �! - zadanie prymalne, zadanie dualne
- rozw. dopuszczalne oraz optymalne
- zastosow. matemat. efektu zasady min. nakładów
i środków
" progr. nieliniowe �! - PL binarne
- problematyka lokalizacji, ?????
- PL parametryczne
- PL w liczbach całkowitych ?????
- PL  zadanie transportowe ?????
" progr. sieciowe
" progr. binarne
" progr. kwadratowe
" progr. wypukłe
" progr. dynamiczne
" poszukiwanie ekstremum
37
" progr. stochastyczne
" optymalizacja:
- zasady optymalizacji
- Z. O. B.
programma  gr. podawanie do publicznej wiadomości obwiesaczenie o porządku spraw,
przwidywanych do rozpatrywania przez zgromadz. Ludowe na rynku;
- porządek zamierzonych działań ludzkich,, wyznaczający zwłaszcza kolejność ich
podejmowania;
- umiejscowienie wspomnianych działań w przyszłości;
" treść przedmiotu nauczania
" spis pozycji składających się na daną imprezę
" ciąg dyrektyw mających na spowodować określone działanie automatu
 projekt planu
 plan
opt.: zastosowanie gospodarności (wydajności)
zastosowanie oszczędności
O. LANGE: nauka o programowaniu zajmuje się kwestią doboru słaściwych środków dla
realizacji odreślinego celu, kiedy środki są wymierne, a cel dopuszcza rozmaite
stopnie realizacji;
kolejność postępownia: - programowanie rzeczowe
- ?????
Program: ciąg instrukcji, których wykonanie przez komputer pozwala uzyskać dane
wyjściowe na podstawie danych wejściowych;
- diagnostyczny
- interpretacyjny (interpreter)
- kompilujący (kompilator, translator)
- nadzorczy (supervisor, dyrygent)
- testujący
- standardowy
- symulujący
- usługowy
Programownie: opracowywanie programów
Pełny cykl opracowywania programu:
1. Analiza problemowa, sprecyzowanie zadania; podział zadań na ewentualne części;
wybór algorytmów dla poszczególnych części.
2. Opracowywanie sieci działań programu:
a. sieć czynności
38
b. tablice decyzyjne (warunki dla punktów rozgałęzienia i pętli)
3. Wybór formatów danych wejściowych i wyjściowych, języka programowani.
4. Zapisywanie programu w języku programowania (kodowanie)
[sieć działań ciąg instrukcji języka programownia]
5. Uruchamianie programu (sprawdzanie poprawności, eliminowanie błędów)
6. Opracowanie dokumentacji: opis dla użytkownika
PROGRAMOWANIE MATEMATYCZNE
Dział matematyki zajmujący się opracowywaniem metod rozwiązywania zadań
polegających na poszukiwaniu ekstremum funkcji celu [1] na zadanym zbiorze
rozwiązań dopuszczalnych;
Zadanie P. M. polega na znalezieniu takiego wektora: x* " Rn, n > 1
ażeby: f(x*) = min f(x)
przy ograniczeniach: gi(x) d" 0
x e" 0
Rn  n-wymiarowa przestrzeń wektorów rzeczywistych
Zastosowanie: - zarządzanie
- projektowanie
" jeżeli gi(x) i f(x) są liniowe P. L.
" jeżeli gi(x) i f(x) są wypukłe P. Wypukłe P. Kwadtratowe
" jeżeli gi(x) lub f(x) są nieliniowe P. N.
" gdy żąda się aby zmienne decyzyjne (wsztstkie albo część z nich) przyjmowały tyklo
zadane dyskretne wartości P. Dyskretne
" jeżeli f(x*) lub f(x) lub g(x) są zmiennymi losowymi P. Stochastyczne
" jeżeli przynajmniej 2 funkcje celu zadanie wielokryter. optym.
Najlepiej rozwinięte metody P. M. to metody rozwiąz. zadań P. Wypukłym.
PROGRAMOWANIE LINIOWE
funkcja celu i ograniczenia - liniowe
Zadanie:
max z = cTx
Ax = b
x e" 0
gdzie:
39
 x  wektor rozwiązań
A  macierz ograniczeń
B  wektor prawych stron
C  wektor kosztów
T  operator transponowania wektora
Wektor x spełniający ograniczenia nazywamy rozwiązaniem dopuszczalnym.
Zadanie polega na znalezieniu takiego rozwiązania dopuszczalnego xO, które daje największą
wartość funkcji celu cTx.
" probl. opt. ekonomicznych
technicznych
o jako przybliżenia bardziej złożonych zadań
o jako elementy algorytmów rozwiązań zadań PN
- istnieją szczególne postacie macierzy ograniczeń
umożliwiea opracowanie bardziej efektywnych metod ich rozwiązywania,
np.: zagadnienie transportowe
- teoria dualności
- analiza optymalizacyjna wpływ zmian parametrów na rozwiązania optymalne
Klasyczny przykład zastosowania PL
w planowaniu produkcji wybór optymalnego
zestawu wytwarzanych wyrobów przy
ograniczonych zasobach;
Możemy produkować n typów wyrobów.
Niech xj (j = 1, 2, ..., n) oznacza planowaną liczbę jednostek wyrobu j.
Do dyspozycji jest m typów zasobów.
Każdego z nich można zużyć nie więcej niż bi (i = 1, 2, ..., m).
Wyprodukowanie jednostki wyrobu j pochłania aij jednostek zasobu i i przynosi cj zł zysku.
F. celu (łączny zysk):
n
z = x = max
"c j j
j=1
n
ograniczenia: x d" bj dla i = 1, 2, ..., m
"aij j
j=1
oraz: xj e" 0, j = 1, 2, ..., n
PROGRAMOWANIE NIELINIOWE
- znalezienie nieujemnego wektora x spełniającego warunki gi(x) d" 0, i = 1, 2, ..., m,
i minimalizującego wartości funkcji celu f
- f. celu lub co najmniej jedna z funkcji gi(x) nie jest funkcją liniową;
40
- zadanie:
min z = f(x)
gi(x) d" 0, i = 1, 2, ..., m
(wektor x spełniający ograniczenie wektor dopuszczalny;
rozwiązanie zadania wektorem optymalnym)
- działy PN:
programowanie kwadratowe
programowanie geometryczne
programowanie wypukłe
" gdy funkcja f ma wiele ekstremów lokalnych  wynikiem działania algorytmów jest
zwykle jedno z nich; istniejące metody nie gwarantują, że jest to ekstremum globalne;
" metody (znane najbardziej) rozwiązywania ogólnych zadań PN:
1. metody sprowadzenie zadania do problemu minimalizacji funkcji bez
ograniczeń;
2. metody modyfikacji kierunków  polegają na generowaniu ciągu punktów
zbieżnych do rozwiązania w wyniku tworzenia tzw. Dopuszczalnych
kierunków poprawy albo rzutowania kierunków gradientu na powierzchnie
styczne do ograniczeń;
Najczęściej uzupełnia się funkcję celu składnikiem mającym charakter kary za
przekroczenie ograniczeń, następnie wykorzystuje się jedną z metod
poszukiwania minimum bez ograniczeń: - metoda Gaussa-Seidela
- metoda największego spadku
W teorii PN centralne miejsce zajmuję:
- zagadnienia warunków optymalności rozwiązań
- teoria dualności badanie funkcji Lagrange a
[metody współczynników Lagrange a]
Mnożniki Lagrange a zmienne dualne
ceny pozorne
oceny umowne
oceny dualne
ceny obiektywnie uzasadnione
Ciekawa interpretacja ekstremiczna przy ocenie znaczenia ?????
PROGRAMOWANIE WYPUKA
E
programowanie matematyczne
programowanie minimum funkcji wypukłej (maksimum funkcji wklęsłej) na zbiorze
wypukłym [ poszukiwanie ekstremum]
Zadanie  postać:
41
min f(x)
gi(x) d" 0, i = 1, 2, ..., m
x e" 0
gdzie: f, gi, i = 1, 2, ..., m funkcje wypukłe,
x n-wymiarowy wektor rozwiązań
RYSUNEK str. 118
Istota (właściwość zadań PW): znalezienie minimum lokalnego funkcji f na zbiorze
dopuszczalnym oznacza jednocześnie wyznaczenie minimum globalnego na tym
zbiorze.
Gdy funkcja f oraz ograniczenia gi (i = 1, 2, ..., m) mają własność rozdzielności można je
wyznaczyć w postaci sumy n składników, z których każdy jest funkcją tylko jednej zmiennej
xj.
n
min f (x)= f (x ),
" j j
j=1
n
gi(x)= (x )d" 0 , i = 1, 2, ..., m
"gij j
j=1
xj e" 0, j = 1, 2, .., n
ę!
zadanie programowania
 rozdzielnego
PROGRAMOWANIE GEOMETRYCZNE
- dział programowania NIELINIOWEGO
- przedmiotem jest rozwiązywanie zadań o postaci:
ko
n
aok
j
min ż =
"cok"x j
k=1 j=1
ki
n
aik
j
d"1, i = 1, 2, ..., m
"cik"x j
k=1 j=1
xj e" 0, j = 1, 2, ..., n
gdzie:
ko, ki  liczby składników w funkcji celu i w i-tym ograniczeniu,
cok, cik, aokj, aikj  liczby rzeczywiste,
Zadanie polega na znalezieniu nieujemnego wektora x = (x1, x2, ..., xn) spełniającego
ograniczenia:
42
ki
n
aik
j
d"1, i = 1, 2, ..., m
"cik"x j
k=1 j=1
i minimalizującego funkcję ż.
Zast. P.G. projektowanie inżynierskie
" istnieją bardzo efektywne metody rozwiązywania tych zadań (gdy szczególna postać
funkcji celu i ograniczeń)
" inna klasa: problemy, w których współczynniki cok, cik dla wszystkich i, k są nieujemne
Główną uwagę koncentruje się tu raczej na badaniu względnych wielkości składników funkcji
celu niż samych zmiennych.
Zamiast znajdować bezpieczne wartości optymalne zmiennych w programowaniu
geometrycznym najpierw ustala się optymalny sposób rozdzielenia całkowitego kosztu
pomiędzy różne składniki funkcji celu.
[Pozwala stwierdzić w jaki sposób należy rozdzielić zasoby między odpowiednie składniki
realizujące cel danej konstrukcji]
Metody: - ujęcie różniczkowe
- wg nierówności geometrycznej
43
PROGRAMOWANIE
- wstęp -
PL
Zagadnienie komiwojażera pr. dyskretne, pr. sieciowe
Zagadnienie rozmieszczenia pr dyskretne
Zagadnienie transportowe pr. liniowe
" PROGRAMOWANIE (ogólnie)
" Pr. matematyczne
Pr. liniowe
Pr. dyskretne
Pr. sieciowe
Pr. nieliniowe
" Pr. kwadratowe
Pr. binarne
" Pr. geometryczne
" Pr. wypukłe
Pr. dynamiczne
Pr. stochastyczne
Poszukiwanie ekstremum (opt.)
Optymalizacja:
zas. opt.
Z. O. B.
" zadanie prymalne, zadanie dualne PL
" rozw. dopuszczalne; rozw. optymalne
" zastosowanie max efektu, zastosowanie min nakładów śr.
" metoda duplex PL
" (0-1) PL binarne  szczeg. przyp. PL w liczbach całkowitych
"  Problem : - loklizacji
- obwodowy
- obciążenia maszyn
44
" PL parametryczne [wyznaczenie ekstremum w zadaniach optymalizacyjnych z funkcjami
wyników i warunków ubocznych zależnymi od parametrów; zachowanie się rozwiązania
przy zamianie parametrów]
" PL w liczbach całkowitych:
o metoda Lande-Doiga
o metoda Gomory ego
PL zadanie transportowe
zadanie prod.-transport
- dualność
- tw.
Dualność pary standardowych zadań PL.
Tw. [Charakterystykę minimum funkcji nakładów stanowi maksimum liniowej funkcji
wyników i odwrotnie]
Zadanie prymalne PL:
c x max f(x) = c1x1 + c2x2 + ... + cnxn max
Ax d" b a11x1 + a12x2 + ... + a1xn d" b1
. .
. .
. .
x e" 0 xj e" 0 (j = 1, 2, ..., n)
zadanie dualne PL:
y b min f(y) = y1b1 + ... + ymbm min
y A e" C y1a11 + y2a21 + ... + ymam1 e" c1
. .
. .
. .
y1a1n + ... + ymamn e" cn
y e" 0 yi e" 0 (i = 1, 2, ..., m)
Rozw. dop.: x, y , rozw. opt.: xo, yo
Wektory: b oraz y m-wymiar.: b " Rm, y " Rm
x oraz c n: x " Rn, C " Rn
Interpr. prakseol. [Lange]
45
Zasada: maksimum efektu (maks. wydajn.)
minimum nakładu środków
W zadaniu prymalnym wyznaczenie maks. funkcji wyników przy danym nakładzie
wyznaczenie min. Funkcji nakładów przy danym wyniku
[Tw. o dualności]
1. Jeżeli zadania {Ax < b, x d" 0} i {y A e" c , y e" 0} mają rozw. dop., to istnieje również
rozwiązanie optymalne xo i yo oraz spełnione jest równanie:
c xo = yob
2. Jeżeli zadanie {Ax d" b, x e" 0} ma rozwiązanie dopuszczalne, to: max c x = +"
osiągane jest wtedy i tylko wtedy, gdy zadanie {y A e" c , y e" 0} nie ma rozwiązań
dopuszczalnych.
3. Jeżeli zadanie {y A e" c , ye" 0} ma rozwiązanie dopuszczalne, to: miny b = -"
osiągane jest wtedy i tylko wtedy, gdy zadanie {Ax d" b, x e" 0} nie ma rozwiązań
dopuszczalnych.
ZADANIA PIERWOTNE
I DUALNE
PROGRAMOWANIA LINIOWEGO
Metody programowania liniowego. Oznaczenia Gaussa:
X  wektor kolumnowy n zmiennych (x, ..., xn),
C  wektor wierszowy n parametrów funkcji celu (c1, c2, ..., cn),
B  wektor kolumnowy ograniczeń (b1, b2, ..., bn),
W  wektor kolumnowy m zmiennych (w1, w2, ..., wn),
O  wektor kolumnowy n-wyrazowy, którego wszystkie składowe są równe zeru,
A  macierz o m wierszach i n kolumnach i elementach aij,
ZADANIE PIERWOTNE
- polega na znalezieniu przy danych A i B takiego wektora X, który maksymalizuje
(minimalizuje) funkcję celu:
f = CX (1)
która spełnia wymagania: AX = B (2)
oraz warunki brzegowe: X e" 0 (3)
ZADANIE DUALNE modelu sformułowanego przez (1), (2), (3)
- polega na znalezieniu wektora W, który maksymalizuje (minimalizuje) funkcję: g(x) = BTW
spełniającą ograniczenia:
ATW e" CT
oraz warunki brzegowe:
W e" 0
46
 gdzie: BT  wektor wierszowy o m składowych (b1, b2, ..., bm),
AT  transponowana macierz A, czyli macierz o n wierszach i m kolumnach.
CT  wektor kolumnowy o n składowych (c1, c2, ..., cn),
Pods. twierdzenie o dualności pr. liniowego
Jeżeli istnieje skończone, optymalne rozwiązanie zadania pierwotnego, to istnieje
również skończone, optymalne rozwiązanie zadania dualnego i zachodzą równości:
min Cx = max BTW
max CX = min BTW
Twierdzenie to pozwala na rozwiązanie poś m rednie zadania trudniejszego,
korzystając z rozwiązania zadania łatwiejszego.
Interpretacja fizyczna zadań pierwotnego i dualnego.
Zadanie pierwotne (sformułowanie):
Ile jednostek xj (j = 1, 2, ..., n) każdego rodzaju produkcji należy
wyprodukować, aby otrzymać maksymalny zysk produkcji, jeśli znamy:
zysk cj na jednostkę produkcji j-tego rodzaju,
aij  ilość i-tego zasobu dla wytworzenia jednej jednostki produkcji j-tego
rodzaju,
bi  wielkość zasobu i-tego rodzaju (i = 1, 2, ..., m),
Zadanie dualne polega na określeniu ceny wi, jaką należy ustalić dla jednej jednostki
każdego z zasobów bi, aby przy zadanych zyskach cj, wielkości zasobów bi i
współczynnikach aij zminimalizować nakłady na produkcję.
Zadanie pierwotne:
Funkcja celu:
n dochód z jednostki
.................................. ..............................
liczba
produkcji j-tego �" są ?????
"
jednostek
i=1 rodzaju
d k ji j
.....................................
nakłady i-tego zasobu
n
.............................. ......................
liczba jednostek
na wyprod. jednej
zapas i-
�" d"
" produkcji j-tego
jednostki produkcji j-
i=1 tego
rodzaju
tego rodzaju
(i = 1, 2, ..., m); (j = 1, 2, ..., n)
(j = 1, 2, ..., n)
liczba jednostek
............................
e" 0
produkcji j-tego
rodzaju
47
Zadanie dualne:
Funkcja celu:
n
....................... ............................. ............................
zapas i- cena ogólna
�" =
"
i=1 tego jednostki cena
(i = 1, 2, ..., m);
Warunki ograniczające:
n
........................................ ........................... ......................
nakłady i-tego
cena ogólna
�" e"
"
zasobu na
jednostki i- cena
i=1
wyprod jednej
(j = 1, 2, ..., n)
.........................
cena
e" 0
jednostki
rys str 134
PROGRAM
TRANSPORTOWY
(minimalizacja kosztów transportu przy z góry zadanych ograniczeniach)
Z każdym łukiem (x, y) sieci związane są 3 nieujemne funkcje rzeczywiste: f, c, d
o argumencie (x, y).
Funkcja f(x, y)  przepływ po łuku (ilość jednostek ładunku przewożona przez węzeł
do y).
Funkcja c(x, y)  pojemność na łuku (max wielkość funkcji f(x, y) i max ilość
ładunku, jaka może być przewieziona z węzła x do y).
Funkcja d(x, y)  koszt na łuku (koszt transportu jednostk ładunku  towaru od węzła
x do węzła y).
Z każdym węzłem wejściowym  x związana jest funkcja rzeczywista  a o argumencie  x
taka, że całkowity przepływ ładunków z tego węzła musi być niewiększy od zapasu a(x).
Z każdym węzłem wyjściowym  x związana jest funkcja rzeczywista  b o argumencie  x
taka, że całkowity przepływ towarów do tego węzła musi być większy od zapotrzebowania
b(x).
Funkcje f(x, y), c(x, y), d(x, y), a(x), b(x) są większe lub równe zero i są całkowite.
48
PRZYKA
AD (problem transportowy)
Należy zminimalizować tonokilometry przewozu między dwoma dostawcami i trzema
odbiorcami:
odbiorcy maksymalna
dostawcy
1 2 3 produkcja, t
1 2 5 3
100
2 1 7 4
150
zapotrzebowanie, t 80 50 70
C  liczby oznaczające odległości między dostawcą, a odbiorcą, np.: C1,3 = 3
C2,2 = 7
m n
Model ma charakter otwarty, gdyż: a1 + a2 = 250 >
"ai "bj
i=1 j=1
b1 + b2 + b3 = 200
Warunki dotyczące dostawców (zgodnie z zapisem):
n
X11 + X12 + X13 d" 100 xi, d" ai
" j
j=1
X21 + X22 + X23 d" 150
Warunki dotyczące odbiorców (zgodnie z zapisem):
m
X11 + X21 = 80 = bj
"xij
i=1
X12 + X22 = 50
X13 + X23 = 70
Funkcja celu: F = 2 X11 + 5 X12 + 3 X13 + X21 + 7 X22 + 4 X23 (min)
Rozwiązanie (metoda Simpleks)
x11=0 x22=0
x12=50 x23=20
x13=50
x21=80 F=560
Z porównania liczb wynika, że odbiorca 1 powinien otrzymać materiał od odbiorcy 2,
odbiorca 2 od dostawcy 1, a odbiorca 3 od dostawców 1i 2.
W tym przypadku zdolności dostawcze będą wykorzystane a dostawcy 1 w 100%, a dostawcy
n
2 w 66,6%, zgodnie z zapisem wynikającym z warunku d" ai
"kij
j=1
49
Należy zaprojektować prostokątny przekrój bh belki drewnianej, zdolnej do przeniesienia
danego momentu zginającego Mobl=1666,7 kGcm (166,67 Nm). Naprężenie dopuszczalne k
kG
(wytrzymałość oblicz. R) dla materiału belki jest równe 100 (10 Mpa) .
cm2
" Belka spełni swoje zadanie, gdy przeniesie żądany moment zginający i gdy
naprężenia w przekroju belki nie przekroczą wartości dopuszczalnych.
" Zaprojektowany dz
wigar musi wykazywać wystarczające bezpieczeństwo
przed utratą stateczności przy zginaniu. (Dla uproszczenia zadania nie
b
formułujemy jawnie tego wymagania: stosunek przekroju powinien
h
przyjmować wypróbowane wartości).
Projektowanie zwykłe
a) przyjmuje się wartości liczbowe na szerokość i wysokość przekroju belki i
podstawia się te wymiary do wzoru na naprężenia w belce
M M
� = = d" k �! R (1)
W b �" h2
6
b) sprawdza się czy warunek (1) jest zachowany. Gdy naprężenie przekracza dop.
wartość k, zmienia się wymiary.
c) powtarza się czynność aż � d" k �! R
Projektant będzie się starał maksymalnie wykorzystać naprężenia, spodziewając
się, że dzięki temu najlepiej wykorzystać materiał.
Po znalezieniu b i h, spełniających warunek (1) zadanie jest rozwiązane.
Zaprojektowany przekrój belki zdolny do przeniesienia danego momentu
zginającego.
Projektowanie optymalne
(Aby dz
wigar był optymalny, nie wystarczy że przeniesie on moment zginający: można
zaprojektować belki o innych wymiarach, które spełnią swoje zadanie).
" Wybieramy kryterium oceny jakości konstrukcji (najczęściej: kryterium
ekonomiczno-kosztowe konstrukcji).
W tym przykładzie kryterium optymalnej jakości dz
wigara wyrażone jest przez
pole przekroju. Za optymalny uznany jest dz
wigar, który ma najmniejsze pole
przekroju spośród wszystkich dz
wigarów zdolnych do przeniesienia danego
momentu. Np.:
- dla b=4 cm, h=5 cm � = R = k =10MPa
pole 20 cm2
- dla b=2 cm, h=7,1 cm � = 9,9MPa pole 14,2 cm2
h
" Granice stosunków wymiarów przekroju dz
wigara
b
( warunki stateczności  przyjęte dowolnie):
h
e"1 (2)
b
h
oraz d" 4 (3)
b
50
" Kryterium minimalnego pola:
z = b �" h = min (4)
" Model matematyczny zadania: warunek (1)�(4)
" Liczba zmiennych: dwie (b oraz h)
" Sens fizyczny: b>0 , h>0 stąd rozwiązanie w układzie współrzędnych
prostokątnych ( I ćwiartka)
Warunki (1)�(4) przedstawiamy graficznie:
b b
10 10
b=h
8
8
Obszar spełniający
6
6 Obszar
war. (3)
spełniający war. (2)
4
4
b=h/4
2
2
h (cm)
h (cm)
4
2 6 8 10
2 4 6 8 10
Warunek (1) przekształcamy, aby wymiar b był funkcją wymiaru h:
M 6�" M 6�"166,67
= = k czyli =10
W b�" h2 b �" h2
graniczny przypadek
10
b
i ostatecznie b = wymagania (1)
h2
(przekrój o takich
10
wymiarach osiągnął
naprężenia
8
dopuszczalne
6
4
2
h (cm)
4
2 6 8 10
Obszar rozwiązań dopuszczalnych:
Współrzędne wszystkich punktów tego
b
obszaru spełnia wszystkie wymagania
(2)
10
zadania [warunki (1)�(3)]. Punkty te
tworzą jednolity, spójny obszar
8
dopuszczalny.
6
Wymiary b i h wybieramy z tego zbioru
4
(3)
rozwiązań dopuszczalnych przy pomocy
2
(1)
funkcji (4).
h (cm)
2 4 6 8 10
Interpretacja funkcji z (4): miejsce geometryczne wszystkich punktów o tej
samej wartości (wysokości) z.
Dwa wykresy
51
Podstawiamy w miejsce z kolejno wartości np. 1, 4, 2 itp.
b
b
(2)
10
8
6
4
(3)
2
z, = 20 z, = 20
(1)
z, = 1 z, = 4 z, = 1 z, = 4
h (cm)
h (cm)
2 4 10
6 8
2 4 6 8 10
Wartości z =1 i z =4 leżą poza obszarem dopuszczalnym. Warstwica z=2 leży w obszarze
dopuszczalnym ale nie jest najmniejszą z warstwic wchodzących w obszar dopuszczalny.
Dla z = 13,57 otrzymujemy punkt " współrzędnych h = 7,37 i b = 1,84 cm spełniający
wszystkie warunki zadania [(1)�(4)]. Współrzędne punktu (7,37; 1,84) odpowiadają
optymalnemu przekrojowi dz
wigara.
W projektowaniu zwykłym możemy osiągnąć tylko to, że konstrukcja spełni swoje zadanie.
W projektowaniu optymalnym osiągniemy ponadto to, że konstrukcja jest
najlepsza  optymalna  z punktu widzenia wybranego kryterium.
MACIERZOWA POSTAĆ MODELU SIECIOWEGO
Mij = 1 dla (xi , xj ) T (X)
Mij = 0 dla (xi , xj ) T (X)
3
7
4
5
6
2
1
2
5
6
8
4
1 2 3 4 5 6
1 0 1 0 0 0 0
2 0 0 1 1 0 0
3 0 0 0 0 1 0
4 0 0 0 0 1 0
5 0 0 0 0 0 1
6 0 0 0 0 0 0
52
 1 2 3 4 5 6
1 0 5
2 0 4 6
3 0 7
4 0 8
5 0 2
6 0
Programowanie sieciowe - programowanie dwuwartościowe
Zmienne bierne tworzą zbiór dwuwskaz
nikowy (macierz) o elementach binarnych
� ={xij}; xij = { 0
1
W przypadku liniowym wielkością optymalizowaną jest suma
n
J = �" xij
"cij
i, j=1
Ujęcie geometryczne:
" Rozważamy zbiór skończony punktów na płaszczyz
nie
'" = {A, A2 ,....., An} 2
4
1 5
3
6
" Elementy macierzy C = {cij} traktujemy jako odległości między
punktami i, j
" Długość odcinków łączących punkty Ai i Aj musi odpowiadać w
pewnej skali odległościom określonym wzorem C = {cij}
Tak interpretacja jest możliwa, gdy cij spełniają warunki:
cij = 0 ; cij > 0 ; cij = c ; cij + c e" cik
jk jk
Założenie: zadania nasze spełniają ww. warunki i mają interpretacje
geometryczną [ w przestrzeni o dużej liczbie wymiarów ]
Sieć: punkty połączone ze sobą za pomocą odcinków.
Składa się z fragmentów (podzbiorów punktów połączonych)
oraz punktów izolowanych
53
SIE
Ć
:
3FRAGMENTOWA
+ 2 PUNKTY IZOL.
Zadania optymalizacyjne ( na podstawie zbioru punktów oraz sieci)
1. o najkrótszym połączeniu wszystkich punktów
2. o najkrótszej trasie zamkniętej ( komiwojażer )
3. o najkrótszej drodze
4. o  racjonal. Zwiedzaniu
5. o przydziałach
6. o drodze krytycznej
7. o  lawinach o  rozchodzeniu się plotek
Postać analityczna zadań:
n
Funkcja celu J = �" xij
"cij
i, j=1
Warunki ograniczające dla zadań:
" zadania o najkrótszym połączeniu:
n n
xij e" 1 ; e" 1
""xij
j=1 i=1
interpretacja: każdy punkt ma połączenie co najmniej z jednym innym
punktem.
" Zadanie o najkrótszej trasie zamknięcia przechodzącej przez wszystkie punkty
zbioru:
n n
= 1 ; = 1
"xij "xij
j=1 i=1
interpretacja: każdy punkt ma powiązanie jednokierunkowe dokładnie z
jednym punktem.
" Zadanie o najkrótszej drodze z punktu Ai do punktu Aj wg zadanej sieci S:
liczba dróg wchodz. do p. pocz. Ai
= = 0
"xki "x jk
oraz liczba dróg wychodz. z p.koń. Aj
k"S k"S
wynosi a
liczba dróg wychodz. z p. pocz. Ai
oraz liczba dróg wchodz. do p.koń.
= = 1
"xki "x jk
Aj=1
k"S k"S
i
warunek ciągłości drogi:
dla wszystkich pozost. pkt. liczba dróg
wchodz. = liczbie dróg wychodz. i jest
= ; (l " S)
przy tym =1 "xkl "xlk
k"S k"S
(jeżeli pkt. leżą na drodze najkrótszej
oraz 0 (gdy na niej nie leży)
" Zadanie o przydziałach (2 rodzaje punktów I i II):
0 c macierz odległości
C`=
c 0
warunki ograniczające:
2n
Każdemu punktowi I rodzaju
xij = 1 (i = 1, 2,....., 2n)
przydzielono dokładnie jeden pkt
"
j=n+1
rodzaju II
Każdemu punktowi II rodzaju
przydzielono dokładnie jeden pkt
rodzaju I
54
Ograniczenia nie
nieprawdziwe dla zadania
o drodze krytycznej
n
= 1 (j = n+1, n+2,....., 2n)
"xij
i=1
(w zadaniach o  małżeństwach oba warunki odpowiadają wymaganej monogamii)
Trudności analityczne: - wynik o oznaczeniach dwuwskaz
nikowych
duża liczba zmiennych
- brak efektywnych rozwiązań (dla niektórych
zadań)
str. 147-177: zadania + rys
55