Praca pochodzi z serwisu www.e-sciagi.pl <<<>>> Zacznij zarabiać http://partner.e-sciagi.pl             

1         Wstęp

1.1     Kilka słów o przedmiocie

Tematem zajęć będą Metody Optymalizacji a nie same Badania Operacyjne. Ponieważ większość z tych metod powstała na potrzeby Badań Operacyjnych, pozostaniemy przy tej drugiej nazwie.

Zajmować będziemy się metodami optymalizacji, służącymi do rozwiązywania problemów decyzyjnych. Program zajęć obejmuje zapoznanie się z metodami rozwiązywania następujących problemów

Problemy dynamiczne

Problemy statyczne

Problemy liniowe              Problemy nieliniowe

Programowanie liniowe

(metoda sympleks, sztuczna baza,

dualność)

Programowanie nieliniowe

Problemy

ciągłe

Problemy

dyskretne

Programowanie liniowe

całkowitoliczbowe

(algorytm Gomory'ego)

Wieloetapowe procesy decyzyjne

Jednowymiarowy proces alokacji

(programowanie dynamiczne)

1.2     Problemy i modele decyzyjne

Każdy system działania rodzi tzw. sytuacje decyzyjne. Sytuacją decyzyjną nazywać będziemy ogół czynników, które wyznaczają postępowanie decyzyjne podmiotu podejmującego decyzję, zwanego na ogół decydentem.

Następstwem prawie każdej sytuacji decyzyjnej jest pewien problem decyzyjny, którego rozwiązanie wyznacza racjonalną decyzję. Problem decyzyjny można zdefiniować następująco:

·      istnieje cel lub zbiór celi które należy osiągnąć

·      istnieją alternatywne sposoby dojścia do celu

·      optymalny sposób lub kombinacja sposobów nie jest oczywista.

Badania operacyjne (ang. operational research) należą do tych dziedzin wiedzy, które zajmują się metodami rozwiązywania problemów decyzyjnych, wynikających z potrzeb racjonalnej działalności człowieka.

Rozwiązanie problemu decyzyjnego za pomocą badań operacyjnych jest procedurą składającą się z następujących etapów:

·      rozpoznanie sytuacji decyzyjnej i wynikającego z niej problemu decyzyjnego

·      budowa modelu decyzyjnego

·      rozwiązanie problemu decyzyjnego (metodą badań operacyjnych lub programowania matematycznego)

·      ocena poprawności i realności uzyskanych rozwiązań oraz ewentualna weryfikacja modelu decyzyjnego

·      przedstawienie rozwiązań decydentowi i ostateczne przygotowanie decyzji.

Nie każdy problem decyzyjny może być rozwiązany za pomocą badań operacyjnych. Rozwiązać można jedynie problemy dobrze ustrukturalizowane, dające się przedstawić w postaci modelu matematycznego. Nie da się rozwiązać metodami badań operacyjnych problemów nieustrukturalizowanych i słabo ustrukturalizowanych.

Budowa modelu decyzyjnego jest jednym z trudniejszych etapów w procedurze podejmowania decyzji. W praktyce najwięcej problemów sprawia:

·      wyróżnienie istotnych cech sytuacji decyzyjnej i ujęcie ich w modelu

·      modelowanie - tę samą sytuację często można odwzorować za pomocą kilku modeli.

Od postaci sformułowanego modelu zależą szanse jego efektywnego rozwiązania - stąd przy formułowaniu modelu należy mieć rozeznanie co do metod, którymi można go rozwiązać.

Model decyzyjny jest konstrukcją formalną, odwzorowującą  istotne cechy rzeczywistej sytuacji decyzyjnej. Model taki może być sformułowany w różnej postaci. Matematyczna postać modelu decyzyjnego jest następująca:

                            z=f(x1,x2,...,xn)              (1.1)

gdzie:

·      zmienne x1,x2,...,xn (zapisywane też jako x) noszą nazwę zmiennych decyzyjnych i są przedmiotem sterowania przez podejmowanie decyzji; określają one alternatywne sposoby działania

·      z jest miarą oceny podjętej decyzji

·      f jest funkcją odwzorowującą zależność między zmiennymi decyzyjnymi a miarą oceny z; funkcja f  nazywana jest funkcją celu lub funkcją kryterium.

Na ogół zbiór alternatywnych sposobów działania nie jest dowolny i wtedy podejmowanie decyzji przebiega w warunkach pewnych ograniczeń. Uwzględnienie tych warunków w modelu decyzyjnym polega na określeniu zbioru dopuszczalnych decyzji (rozwiązań) dla konkretnej sytuacji decyzyjnej. Ogólnie warunki ograniczające można przedstawić następująco:

                            gi(x)<= 0    (i=1,2,...,m)              (1.2)

Zagadnienie wyboru decyzji za pomocą modelu decyzyjnego polega na określeniu wartości zmiennych decyzyjnych ze zbioru dopuszczalnych sposobów działania opisanych ograniczeniami tak, aby uzyskać najkorzystniejszą wartość miary podjętej decyzji - optimum funkcji celu.

Operację poszukiwania wartości zmiennych decyzyjnych x1,x2,...,xn które maksymalizują lub minimalizują funkcję celu będziemy zapisywać symbolicznie w sposób następujący:

                            (max) z=f(x1,x2,...,xn) lub              

                            (min) z=f(x1,x2,...,xn)              (1.3)

Tak więc ogólna, matematyczna postać modelu decyzyjnego jest następująca:

                            (max lub min)        z=f(x1,x2,...,xn)             

                            przy ograniczeniach:   gi(x)<= 0    (i=1,2,...,m)               (1.4)

Przykład: Zakład produkcyjny produkuje dwa typy wyrobów: krzesła i stoły. Każdy z tych produktów musi być złożony z części a następnie wykończony i zapakowany. Czas potrzebny na złożenie krzesła i stołu wynosi odpowiednio 3 i 4 jednostki czasu. Wykończenie i zapakowanie krzesła i stołu wynosi odpowiednio 6 i 2 jednostki czasu. Producent dysponuje 60 jednostkami czasu na składanie wyrobów i 32 jednostkami czasu na  wykończenie i zapakowanie. Każde krzesło przynosi zysk wielkości 20 jednostek a stół - 24 jednostki. Ile krzeseł i ile stołów powinien zakład wyprodukować dla maksymalizacji zysku?

Matematyczna postać problemu decyzyjnego wygląda następująco:

(max) zysk = 20*krzesła+24*stoły

3*krzesła+4*stoły <= 60                                          - ograniczenie czasu składania wyrobów

6*krzesła+2*stoły <= 32                                          - ograniczenie czasu wykończenia i pakowania

krzesła >= 0                                                                      - ograniczenie wielkości produkcji krzeseł

stoły >= 0                                                                      - ograniczenie wielkości produkcji stołów

Modele decyzyjne a co za tym idzie typ problematyki, można podzielić według różnych kryteriów:

·      Postać funkcji celu

§      programowanie liniowe - funkcja celu i ograniczenia są funkcjami liniowymi

§      programowanie nieliniowe - w przeciwnym razie

·      Postać zmiennych decyzyjnych

§      zmienne ciągłe

§      zmienne dyskretne

·      Liczba etapów procesu decyzyjnego

§      programowanie statyczne - jeden etap

§      programowanie dynamiczne - wiele etapów

·      Liczba kryteriów (funkcji celu)

§      model jednokryterialny

§      model wielokryterialny

1.3     Zadanie[1] programowania matematycznego

Ogólna postać zadania programowania matematycznego jest następująca:

              funkcja celu:              (max  lub  min) z = f(x)              (1.5)

              ograniczenia:              gi(x) <= 0 (i=1,2,...,m)              (1.6)

gdzie zÎR, a xÎRn  jest wektorem zmiennych decyzyjnych. Funkcja f nosi nazwę funkcji celu lub funkcji kryterium. Funkcje gi(x) nazywa się funkcjami ograniczeń (warunki ograniczające, ograniczenia).

Dowolne rozwiązanie xÎRn spełniające układ równań i nierówności (1.6) nosi nazwę rozwiązania dopuszczalnego. Zbiór wszystkich rozwiązań dopuszczalnych, będziemy oznaczać przez X. Jeżeli zbiór rozwiązań dopuszczalnych jest zbiorem pustym (X=Æ), to zadanie (1.6) nazywa się sprzecznym.

DEFINICJA: Rozwiązanie xoÎX nazywamy rozwiązaniem optymalnym zadania programowania matematycznego (1.5-6), jeżeli dla dowolnego xÎX spełniony jest warunek:

              (minimalizacja funkcji celu)              f(xo)£f(x)              (1.7a)

              (maksymalizacja funkcji celu)              f(xo)≥f(x)              (1.7b)

W przypadku gdy zadanie (1.5-6) nie jest sprzeczne i przy tym nie istnieje xo spełniające warunek (1.7a-b), to mówimy że zadanie nie ma skończonego rozwiązania optymalnego. Zadanie może mieć również więcej niż jedno rozwiązanie optymalne, jeżeli  warunek (1.7a-b) spełniony jest dla więcej niż jednego xoÎX.

TWIERDZENIE: Dla dowolnej funkcji z = f(x) spełnione są równości

                            (min) f(x)  =  - (max) [-f(x)]

                            (max) f(x)  =  - (min) [-f(x)]              (1.8)

2         Zadanie programowania liniowego

2.1     Wprowadzenie

Jeżeli w zadaniu (1.5-6) funkcja celu oraz warunki ograniczające są liniowe, to zadanie takie nazywamy zadaniem programowania liniowego. Postać ogólna zadania programowania liniowego jest zatem następująca:

              funkcja celu:              (min albo max) z=c...