Definicje badań operacyjnych. Badania operacyjne. Konstruowanie wstępnego planu odniesienia

1. Przedmiot i cele badań operacyjnych w ekonomii. Podstawowe pojęcia teorii badań operacyjnych.

Przedmiotem badań operacyjnych są systemy zarządzania organizacją lub organizacje, które składają się z dużej liczby oddziałujących na siebie jednostek, które nie zawsze są ze sobą spójne i mogą być przeciwne.

Celem badań operacyjnych jest ilościowe uzasadnienie decyzji podejmowanych w zarządzaniu organizacjami.

Rozwiązanie, które okaże się najkorzystniejsze dla całej organizacji, nazywamy optymalnym, natomiast rozwiązanie, które jest najkorzystniejsze dla jednego lub większej liczby działów, będzie suboptymalne.

Badania operacyjne to nauka zajmująca się opracowywaniem i praktycznym zastosowaniem metod najbardziej optymalnego zarządzania systemami organizacyjnymi.

Operacja to dowolne wydarzenie (system działań) połączone jednym planem i mające na celu osiągnięcie jakiegoś celu.

Celem badań operacyjnych jest wstępne ilościowe uzasadnienie optymalnych rozwiązań.

Każdy konkretny dobór parametrów zależnych od nas nazywamy rozwiązaniem. Rozwiązania optymalne to takie, które są lepsze od innych ze względu na pewne cechy.

Parametry, których kombinacja tworzy rozwiązanie, nazywane są elementami rozwiązania.

Zbiór możliwych rozwiązań ma dane warunki, które są stałe i nie mogą zostać naruszone.

Wskaźnik efektywności jest miarą ilościową, która pozwala porównać różne rozwiązania pod względem efektywności.

2. Koncepcja planowania i zarządzania siecią. Sieciowy model procesu i jego elementy.

Metoda pracy z grafami sieciowymi – planowanie sieci – opiera się na teorii grafów. W tłumaczeniu z języka greckiego wykres (grafpho - piszę) przedstawia układ punktów, niektóre z nich są połączone liniami - łukami (lub krawędziami). Jest to topologiczny (matematyczny) model oddziałujących ze sobą systemów. Za pomocą wykresów można rozwiązać nie tylko problemy z planowaniem sieci, ale także inne problemy. Metodę planowania sieciowego stosuje się przy planowaniu zestawu wzajemnie powiązanych prac. Pozwala na wizualizację sekwencji organizacyjnej i technologicznej prac oraz ustalenie zależności pomiędzy nimi. Ponadto pozwala na koordynację operacji o różnym stopniu złożoności i identyfikację operacji, od których zależy czas trwania całej pracy (czyli zdarzenia organizacyjnego), a także skupienie się na terminowym wykonaniu każdej operacji.

Podstawą planowania i zarządzania siecią jest model sieci (NM), który modeluje zbiór wzajemnie powiązanych prac i zdarzeń, które odzwierciedlają proces osiągania określonego celu. Można to przedstawić w formie wykresu lub tabeli.

Podstawowe pojęcia modelu sieci:

Wydarzenie, praca, ścieżka.

Zdarzenia są wynikiem jednego lub większej liczby zadań. Nie mają przedłużenia w czasie.

Ścieżka to łańcuch zadań następujących po sobie, łączący wierzchołek początkowy i końcowy.

Czas trwania podróży wyznacza suma czasów trwania jej dzieł składowych.

3. Budowa i organizacja schematu sieci.

Model sieciowy służy jako model odzwierciedlający zależności technologiczne i organizacyjne procesu prac budowlano-instalacyjnych w systemach planowania i zarządzania siecią (NPS).

Model sieciowy to graficzna reprezentacja procesów, których realizacja prowadzi do osiągnięcia jednego lub większej liczby wyznaczonych celów, wskazująca na ustalone relacje pomiędzy tymi procesami. Schemat sieci jest modelem sieci z obliczonymi parametrami czasowymi.

Strukturę diagramu sieci, która określa wzajemną zależność działań i zdarzeń, nazywa się jej topologią.

Praca jest procesem produkcyjnym wymagającym czasu, pracy i zasobów materialnych, który po ukończeniu prowadzi do osiągnięcia określonych rezultatów.

Zależność (praca fikcyjna), która nie wymaga czasu, jest oznaczona przerywaną strzałką. Fikcyjna praca jest używana na diagramie sieciowym, aby pokazać relacje między zdarzeniami i działaniami.

Schemat sieci wykorzystuje czas, koszt i inne cechy pracy.

Praca ciągła - czas potrzebny na wykonanie tej pracy w dniach roboczych lub innych jednostkach czasu, które są takie same dla wszystkich prac w harmonogramie sieci. Czas pracy może być pewną (deterministyczną) lub zmienną losową określoną przez prawo jej rozkładu.

Kosztem pracy są bezpośrednie koszty niezbędne do jej wykonania, zależne od czasu trwania i warunków tej pracy.

Zasoby charakteryzuje zapotrzebowanie na jednostki fizyczne potrzebne do wykonania danego zadania.

Jakość, niezawodność i inne wskaźniki pracy służą jako dodatkowe cechy pracy.

Zdarzeniem jest fakt zakończenia jednej lub większej liczby prac, który jest konieczny i wystarczający do rozpoczęcia jednej lub większej liczby kolejnych prac. Każdemu zdarzeniu przypisany jest numer zwany kodem. Każde zadanie jest zdefiniowane przez dwa zdarzenia: kod zdarzenia początkowego, oznaczony jako i, oraz kod zdarzenia końcowego, oznaczony jako j.

Wydarzenia, które nie mają wcześniejszej pracy, nazywane są początkowymi; zdarzenia, które nie mają kolejnych, są skończone.

1 Kierunek budowy sieci może mieć różny charakter. Schemat sieci można zbudować od zdarzenia początkowego do końcowego i od zdarzenia końcowego do początkowego, a także od dowolnego zdarzenia do zdarzenia początkowego lub końcowego.

2 Podczas budowania sieci rozwiązano następujące problemy:

Jakie prace należy wykonać, aby rozpocząć tę pracę;

Jaką pracę zaleca się wykonywać równolegle z tą pracą;

3 Wstępny harmonogram sieci konstruowany jest bez uwzględnienia czasu trwania prac tworzących sieć.

4 Forma wykresu powinna być prosta i wizualnie łatwa do zauważenia.

5 Pomiędzy dwoma zdarzeniami może wystąpić tylko jedno zadanie. Podczas wznoszenia budynków i budowli prace mogą być wykonywane sekwencyjnie, równolegle lub jednocześnie, niektóre sekwencyjnie, inne równolegle, w wyniku czego pomiędzy poszczególnymi robotami powstają różne zależności.

Numerowanie (kodowanie) zdarzeń odbywa się po zakończeniu budowy sieci, począwszy od zdarzenia początkowego do zdarzenia końcowego.

4. Ścieżka krytyczna schematu sieci. Rezerwy czasu. Wczesne i późne daty wydarzeń oraz pracy w harmonogramie sieci.

Na schemacie sieci może istnieć wiele ścieżek pomiędzy zdarzeniami początkowymi i końcowymi. Ścieżkę o najdłuższym czasie trwania nazywamy krytyczną. Ścieżka krytyczna określa całkowity czas trwania działania. Wszystkie pozostałe ścieżki mają krótszy czas trwania, dlatego wykonywana na nich praca ma rezerwy czasu.

Ścieżkę krytyczną oznaczono na schemacie sieci grubymi lub podwójnymi liniami (strzałkami).

Przy sporządzaniu schematu sieci szczególne znaczenie mają dwie koncepcje:

Wcześniejsze rozpoczęcie prac to okres, przed którym nie można rozpocząć tych prac bez naruszenia przyjętego ciągu technologicznego. Wyznaczana jest najdłuższa droga od zdarzenia początkowego do początku tej pracy

Opóźnione zakończenie pracy to najpóźniejszy termin na wykonanie pracy, po upływie którego łączny czas pracy nie ulega przedłużeniu. Wyznacza się ją najkrótszą drogą od danego zdarzenia do zakończenia wszystkich prac.

Wcześniejsze zakończenie to termin, przed którym prace nie mogą zostać ukończone. Jest to równoznaczne z wczesnym rozpoczęciem plus czas trwania tej pracy

Późny start - okres, po którym nie można rozpocząć prac bez wydłużenia całkowitego czasu trwania budowy. Jest to równoznaczne z późnym zakończeniem minus czas trwania tej pracy.

Jeśli zdarzeniem jest koniec tylko jednego zadania (tzn. tylko jedna strzałka jest skierowana w jego stronę), to wcześniejszy koniec tego zadania zbiega się z wczesnym początkiem następnego.

Rezerwa ogólna (pełna) to maksymalny czas, o jaki można opóźnić wykonanie danej pracy bez zwiększania łącznego czasu trwania pracy. Jest to określane na podstawie różnicy pomiędzy późnym i wczesnym rozpoczęciem (lub późnym i wczesnym zakończeniem – co jest tym samym).

Rezerwa prywatna (bezpłatna) to maksymalny czas, o jaki można opóźnić wykonanie danego zadania bez zmiany wcześniejszego rozpoczęcia kolejnego. Rezerwa ta jest możliwa tylko wtedy, gdy zdarzenie obejmuje dwa lub więcej zadań (zależności), tj. dwie lub więcej strzałek (ciągłych lub przerywanych) jest skierowanych w jego stronę. Wtedy tylko jedno z tych zadań będzie miało wcześniejsze zakończenie, które zbiega się z wczesnym rozpoczęciem następnego zadania, ale dla pozostałych będą to różne wartości. Ta różnica dla każdego zadania będzie jego rezerwą prywatną.

5. Programowanie dynamiczne. Zasada optymalności i kontroli Bellmana.

Programowanie dynamiczne jest jedną z najpotężniejszych technik optymalizacyjnych. Specjaliści o różnych profilach zajmują się problematyką podejmowania racjonalnych decyzji, wyboru najlepszych opcji i optymalnego zarządzania. Wśród metod optymalizacyjnych szczególne miejsce zajmuje programowanie dynamiczne. Metoda ta jest niezwykle atrakcyjna ze względu na prostotę i przejrzystość jej podstawowej zasady – zasady optymalności. Zakres stosowania zasady optymalności jest niezwykle szeroki, a zakres problemów, do których można ją zastosować, nie został jeszcze w pełni zarysowany. Programowanie dynamiczne od samego początku było środkiem praktycznego rozwiązywania problemów optymalizacyjnych.

Oprócz zasady optymalności, głównej metody badań, dużą rolę w aparacie programowania dynamicznego odgrywa idea zanurzenia konkretnego problemu optymalizacyjnego w rodzinie podobnych problemów. Trzecią cechą odróżniającą ją od innych metod optymalizacyjnych jest kształt wyniku końcowego. Zastosowanie zasady optymalności i zasady zanurzenia w wieloetapowych, dyskretnych procesach prowadzi do powtarzających się równań funkcjonalnych dotyczących optymalnej wartości kryterium jakości. Powstałe równania umożliwiają spójne zapisanie optymalnych kontroli dla pierwotnego problemu. Korzyść polega na tym, że problem obliczania sterowania dla całego procesu zostaje podzielony na szereg prostszych problemów obliczania sterowania dla poszczególnych etapów procesu.

Główną wadą tej metody jest, jak mówi Bellman, „przekleństwo wymiarowości” – jej złożoność katastrofalnie rośnie wraz ze wzrostem rozmiaru problemu.

6. Problem podziału środków pomiędzy przedsiębiorstwami.

Można powiedzieć, że procedura konstruowania optymalnego sterowania metodą programowania dynamicznego dzieli się na dwa etapy: wstępny i końcowy. Na etapie wstępnym dla każdego kroku wyznaczane jest SOE w zależności od stanu systemu (osiągniętego w wyniku poprzednich kroków), a warunkowo optymalne wzmocnienie na wszystkich pozostałych etapach, począwszy od tego, również w zależności od stanu . Na ostatnim etapie określana jest (bezwarunkowa) optymalna kontrola dla każdego etapu. Optymalizacja wstępna (warunkowa) wykonywana jest krok po kroku w odwrotnej kolejności: od kroku ostatniego do pierwszego; optymalizacja ostateczna (bezwarunkowa) – również etapowa, ale w naturalnej kolejności: od pierwszego do ostatniego kroku. Z dwóch etapów optymalizacji, pierwszy jest nieporównywalnie ważniejszy i bardziej czasochłonny. Po ukończeniu pierwszego etapu przejście do drugiego nie nastręcza żadnych trudności: pozostaje jedynie „przeczytać” zalecenia przygotowane już na pierwszym etapie.

7. Sformułowanie problemu programowania liniowego.

Programowanie liniowe jest popularnym narzędziem rozwiązywania problemów ekonomicznych, które charakteryzują się obecnością jednego kryterium (np. maksymalizacja dochodu z produkcji poprzez optymalny wybór programu produkcyjnego, czy np. minimalizacja kosztów transportu itp.). Problemy gospodarcze charakteryzują się ograniczeniami zasobów (materialnych i/lub finansowych). Zapisane są one w formie układu nierówności, czasem w formie równości.

Z punktu widzenia prognozowania akceptowalnych przedziałów cenowych (lub wolumenów sprzedaży) w ramach uogólnionej metody nieparametrycznej zastosowanie programowania liniowego oznacza:

Kryterium stanowi cena MAX kolejnego produktu z grupy zainteresowania f.

Zmiennymi kontrolowanymi są ceny wszystkich produktów z grupy f.

Ograniczenia naszego problemu prognozowania przy użyciu uogólnionej metody nieparametrycznej są następujące:

a) system nierówności (ograniczenia racjonalności zachowań konsumentów) (patrz 4.2. Prognozowanie w ramach uogólnionej metody nieparametrycznej);

b) wymóg nieujemności zmiennych kontrolowanych (w naszym problemie prognostycznym będziemy wymagać, aby ceny produktów z grupy f nie spadły poniżej 80% wartości cen w ostatnim punkcie czasowym);

c) ograniczenie budżetowe w postaci równości - wymóg, aby wysokość kosztów zakupu produktów z grupy f była stała (uwzględniając np. 15% inflację).

8. Graficzna metoda rozwiązywania problemów programowania liniowego.

Metoda graficzna opiera się na geometrycznej interpretacji problemu programowania liniowego i jest stosowana głównie przy rozwiązywaniu problemów w przestrzeni dwuwymiarowej i tylko niektórych problemów w przestrzeni trójwymiarowej, ponieważ dość trudno jest skonstruować rozwiązanie wielościanu utworzonego jako w wyniku przecięcia półprzestrzeni. Generalnie niemożliwe jest graficzne przedstawienie problemu w przestrzeni o wymiarach większych niż trzy.

Niech problem programowania liniowego będzie określony w przestrzeni dwuwymiarowej, czyli więzy zawierają dwie zmienne.

Znajdź minimalną wartość funkcji

(2.1) Z = С1х1+С2х2

a11x1 + a22x2 b1

(2.2)a21x1 + a22x2 b2

aM1x1 + aM2x2 bM

(2.3) x1 0, x2 0

Załóżmy, że układ (2.2) pod warunkiem (2.3) jest niesprzeczny, a jego wielokąt rozwiązania jest ograniczony. Każda z nierówności (2.2) i (2.3), jak zauważono powyżej, definiuje półpłaszczyznę z liniami granicznymi: ai1x1 + ai2x2 + ai3x3 = bi,(i = 1, 2, ..., n), x1=0 , x2=0 . Funkcja liniowa (2.1) dla stałych wartości Z jest równaniem linii prostej: C1x1 + C2x2 = const. Skonstruujmy wielokąt rozwiązań układu więzów (2.2) i wykres funkcji liniowej (2.1) w Z = 0 (ryc. 2.1). Wówczas postawiony problem programowania liniowego można nadać następującą interpretację. Znajdź punkt rozwiązania wielokąta, w którym linia nośna C1x1 + C2x2 = const i funkcja Z osiąga minimum.

Wartości Z = C1x1 + C2x2 rosną w kierunku wektora N = (C1, C2), zatem przesuwamy prostą Z = 0 równolegle do siebie w kierunku wektora X. Z ryc. 2.1 wynika z tego, że prosta dwukrotnie staje się linią odniesienia w stosunku do wielokąta rozwiązania (w punktach A i C) i przyjmuje minimalną wartość w punkcie A. Współrzędne punktu A (x1, x2) wyznacza się rozwiązując układ równań prostych AB i AE.

Jeśli wielokąt rozwiązania jest nieograniczonym obszarem wielokątnym, możliwe są dwa przypadki.

Przypadek 1. Prosta C1x1 + C2x2 = const, poruszająca się w kierunku wektora N lub przeciwnie do niego, stale przecina wielokąt rozwiązania i nie jest dla niego podporą w żadnym punkcie. W tym przypadku funkcja liniowa nie jest ograniczona wielokątem rozwiązania zarówno powyżej, jak i poniżej (ryc. 2.2).

Przypadek 2. Linia prosta, poruszająca się, staje się jednak podporą względem wielokąta rozwiązań (ryc. 2.2, a - 2.2, c). Następnie, w zależności od rodzaju obszaru, funkcja liniowa może być ograniczona od góry i nieograniczona od dołu (ryc. 2.2, a), ograniczona od dołu i nieograniczona od góry (ryc. 2.2, b) lub ograniczona zarówno od dołu, jak i z góry (ryc. 2.2, c).

9. Metoda sympleksowa.

Metoda simplex jest główną metodą programowania liniowego. Rozwiązanie problemu rozpoczyna się od rozważenia jednego z wierzchołków wielościanu warunków. Jeśli badany wierzchołek nie odpowiada maksimum (minimum), wówczas przechodzą do sąsiedniego, zwiększając wartość funkcji celu przy rozwiązywaniu problemu dla maksimum i zmniejszając ją przy rozwiązywaniu problemu dla minimum. Zatem przechodzenie z jednego wierzchołka do drugiego poprawia wartość funkcji celu. Ponieważ liczba wierzchołków wielościanu jest ograniczona, w skończonej liczbie kroków gwarantuje się znalezienie optymalnej wartości lub ustalenie, że problem jest nierozwiązywalny.

Metoda ta jest uniwersalna, ma zastosowanie do dowolnego problemu programowania liniowego w postaci kanonicznej. Układ więzów jest tutaj układem równań liniowych, w którym liczba niewiadomych jest większa niż liczba równań. Jeżeli rząd systemu wynosi r, to możemy wybrać r niewiadomych, które wyrażamy w postaci pozostałych niewiadomych. Dla pewności zakładamy, że wybrane zostaną pierwsze kolejne niewiadome X1, X2, ..., Xr. Wtedy nasz układ równań można zapisać jako

Metoda sympleksowa opiera się na twierdzeniu zwanym podstawowym twierdzeniem metody sympleksowej. Wśród optymalnych planów problemu programowania liniowego w postaci kanonicznej koniecznie znajduje się rozwiązanie odniesienia do jego układu ograniczeń. Jeśli optymalny plan problemu jest unikalny, to pokrywa się z jakimś rozwiązaniem referencyjnym. Istnieje skończona liczba różnych rozwiązań wspierających system ograniczeń. Można zatem poszukiwać rozwiązania problemu w postaci kanonicznej, przeszukując rozwiązania referencyjne i wybierając spośród nich to, dla którego wartość F jest największa. Ale po pierwsze, wszystkie rozwiązania referencyjne są nieznane i należy je znaleźć, a po drugie, w rzeczywistych problemach jest ich wiele i bezpośrednie wyszukiwanie jest prawie niemożliwe. Metoda simpleksowa jest pewną procedurą ukierunkowanego wyliczania rozwiązań pomocniczych. Na podstawie znalezionego wcześniej pewnego rozwiązania referencyjnego przy użyciu określonego algorytmu metody simplex obliczamy nowe rozwiązanie referencyjne, w którym wartość funkcji celu F jest nie mniejsza niż na starym. Po szeregu kroków dochodzimy do rozwiązania referencyjnego, czyli planu optymalnego.

10. Stwierdzenie problemu transportowego. Metody wyznaczania planów referencyjnych.

Istnieje m punktów wyjścia („dostawcy”) i n punktów konsumpcji („konsumenci”) takiego samego produktu. Dla każdego elementu zdefiniowano:

ai - wielkość produkcji i-tego dostawcy, i = 1, …, m;

вj - popyt j-tego konsumenta, j= 1,…,n;

сij to koszt transportu jednej jednostki produktu z punktu Ai, i-tego dostawcy, do punktu Bj, j-tego konsumenta.

Dla przejrzystości wygodnie jest przedstawić dane w formie tabeli, zwanej tabelą kosztów transportu.

Konieczne jest znalezienie takiego planu transportu, który w pełni zaspokoiłby zapotrzebowanie wszystkich konsumentów, jednocześnie zapewniłby wystarczające dostawy dostawców, a całkowite koszty transportu byłyby minimalne.

Plan transportu odnosi się do wielkości przewozu, tj. ilość towarów, które należy przetransportować od i-tego dostawcy do j-tego konsumenta. Aby zbudować model matematyczny problemu należy wprowadzić m·n zmiennych xij, i= 1,..., n, j= 1,..., m, każda zmienna xij oznacza wielkość transportu z punktu Ai do punktu Bj. Zbiór zmiennych X = (xij) będzie planem, który należy znaleźć na podstawie sformułowania problemu.

Jest to warunek rozwiązania zamkniętych i otwartych problemów transportowych (CTZ).

Oczywiście, aby Problem 1 był możliwy do rozwiązania, konieczne jest, aby całkowity popyt nie przekraczał wielkości produkcji od dostawców:

Jeżeli ta nierówność jest ściśle spełniona, to problem nazywa się „otwartym” lub „niezrównoważonym”, natomiast jeżeli , to problem nazywa się „zamkniętym” problemem transportowym i będzie miał postać (2):

Stan równowagi.

Jest to warunek rozwiązania zamkniętych problemów transportowych (CTP).

11. Algorytm rozwiązywania problemu transportowego.

Zastosowanie algorytmu wymaga spełnienia szeregu warunków:

1. Musi być znany koszt transportu jednostki produktu z każdego miejsca produkcji do każdego miejsca przeznaczenia.

2. Musi być znany stan magazynowy produktów w każdym punkcie produkcji.

3. Muszą być znane wymagania dotyczące produktu w każdym miejscu spożycia.

4. Całkowita podaż musi równać się całkowitemu popytowi.

Algorytm rozwiązywania problemu transportowego składa się z czterech etapów:

Etap I: Przedstaw dane w formie standardowej tabeli i znajdź dowolną możliwą alokację zasobów. Dopuszczalna jest taka dystrybucja zasobów, która pozwala zaspokoić cały popyt w miejscach docelowych i usunąć cały zapas produktów z punktów produkcyjnych.

Etap 2. Sprawdzenie powstałej alokacji zasobów pod kątem optymalności

Etap 3. Jeśli wynikająca z tego alokacja zasobów nie jest optymalna, następuje redystrybucja zasobów, co zmniejsza koszty transportu.

Etap 4. Ponowne sprawdzenie optymalności powstałej alokacji zasobów.

Ten proces iteracyjny powtarza się aż do uzyskania optymalnego rozwiązania.

12. Modele zarządzania zapasami.

Pomimo tego, że każdy model zarządzania zapasami ma odpowiadać na dwa główne pytania (kiedy i ile), istnieje znaczna liczba modeli, których konstrukcja wykorzystuje różnorodne narzędzia matematyczne.

Sytuację tę tłumaczy się różnicą warunków początkowych. Główną podstawą klasyfikacji modeli zarządzania zapasami jest charakter zapotrzebowania na przechowywane produkty (przypomnijmy, że z punktu widzenia bardziej ogólnej gradacji rozważamy obecnie tylko przypadki z niezależnym popytem).

Zatem w zależności od charakteru popytu mogą istnieć modele zarządzania zapasami

deterministyczny;

probabilistyczny.

Z kolei popyt deterministyczny może mieć charakter statyczny, gdy intensywność zużycia nie zmienia się w czasie, lub dynamiczny, gdy niezawodny popyt może zmieniać się w czasie.

Popyt probabilistyczny może być stacjonarny, gdy funkcja gęstości prawdopodobieństwa popytu nie zmienia się w czasie, i niestacjonarny, gdy funkcja gęstości prawdopodobieństwa zmienia się w czasie. Powyższą klasyfikację ilustruje rysunek.

Najprostszym przypadkiem jest przypadek deterministycznego statycznego popytu na produkty. Jednak tego typu konsumpcja jest w praktyce dość rzadka. Najbardziej złożone modele to modele niestacjonarne.

Oprócz charakteru popytu na produkty, budując modele zarządzania zapasami, należy wziąć pod uwagę wiele innych czynników, na przykład:

terminy realizacji zamówień. Czas trwania okresu udzielania zamówień może być stały lub być zmienną losową;

proces uzupełniania zapasów. Może być natychmiastowy lub rozłożony w czasie;

istnienie ograniczeń w zakresie kapitału obrotowego, powierzchni magazynowej itp.

13. Systemy kolejkowe (QS) i wskaźniki ich efektywności.

Systemy kolejkowe (QS) to systemy specjalnego typu, które realizują wielokrotne wykonywanie podobnych zadań. Systemy takie odgrywają ważną rolę w wielu obszarach ekonomii, finansów, produkcji i życia codziennego. Jako przykłady QS w kwestiach finansowych i ekonomicznych; w tym zakresie możemy wymienić banki różnego typu (komercyjne, inwestycyjne, hipoteczne, innowacyjne, oszczędnościowe), organizacje ubezpieczeniowe, państwowe spółki akcyjne, spółki, firmy, stowarzyszenia, spółdzielnie, inspektoraty podatkowe, służby audytorskie, różne systemy komunikacji (m.in. centrale telefoniczne), kompleksy załadunkowo-rozładunkowe (porty, stacje towarowe), stacje benzynowe, różne przedsiębiorstwa i organizacje usługowe (sklepy, punkty informacyjne, fryzjerzy, kasy biletowe, kantory, warsztaty, szpitale). Za rodzaj QS można uznać również systemy takie jak sieci komputerowe, systemy gromadzenia, przechowywania i przetwarzania informacji, systemy transportowe, zautomatyzowane obszary produkcyjne, linie produkcyjne, różne systemy wojskowe, w szczególności systemy obrony powietrznej lub przeciwrakietowej

Każdy QS zawiera w swojej strukturze pewną liczbę urządzeń obsługujących, które nazywane są kanałami usług (urządzenia, linie). Rolę kanałów mogą pełnić różne urządzenia, osoby wykonujące określone czynności (kasjerzy, operatorzy, fryzjerzy, sprzedawcy), linie komunikacyjne, samochody, dźwigi, ekipy remontowe, tory kolejowe, stacje benzynowe itp.

Systemy kolejkowe mogą być jednokanałowe lub wielokanałowe.

Każdy QS jest przeznaczony do obsługi (spełniania) określonego przepływu aplikacji (wymagań) docierających do wejścia systemu, przeważnie nie regularnie, ale w losowych momentach. Obsługa wniosków w tym przypadku również nie trwa stałym, z góry znanym czasem, ale czasem losowym, który zależy od wielu przypadkowych, czasem nam nieznanych, przyczyn. Po obsłużeniu żądania kanał zostaje zwolniony i gotowy na przyjęcie kolejnego żądania. Losowy charakter przepływu żądań i czasu ich obsługi prowadzi do nierównomiernego obciążenia QS: innym razem na wejściu QS mogą kumulować się nieobsługiwane aplikacje, co prowadzi do przeciążenia QS, a czasami, gdy na wejściu QS są wolne kanały, nie będzie aplikacji, co prowadzi do niedociążenia QS, tj. do bezczynności swoich kanałów. Wnioski gromadzące się na wejściu do QS albo „dołączają” do kolejki, albo z uwagi na brak możliwości dalszego pozostawania w kolejce, pozostawiają QS bez obsługi.

Wskaźniki efektywności funkcjonowania pary „CMO – konsument”, gdzie przez konsumenta rozumie się cały zestaw aplikacji lub niektóre z ich źródeł (np. średni dochód osiągany przez CMO w jednostce czasu itp.). ). Ta grupa wskaźników okazuje się przydatna w przypadkach, gdy część przychodów uzyskanych z obsługi aplikacji i koszty obsługi mierzone są w tych samych jednostkach. Wskaźniki te mają zazwyczaj bardzo specyficzny charakter i są zdeterminowane specyfiką QS, obsługiwanych żądań i dyscypliny obsługi.

14. Równania dynamiki dla stanów probabilistycznych (równania Kołmogorowa). Prawdopodobieństwa graniczne stanów.

Formalnie różniczkując równanie Kołmogorowa – Chapmana ze względu na s przy s = 0, otrzymujemy bezpośrednie równanie Kołmogorowa:

Formalnie różniczkując równanie Kołmogorowa-Chapmana ze względu na t przy t = 0, otrzymujemy odwrotne równanie Kołmogorowa

Należy podkreślić, że dla przestrzeni nieskończenie wymiarowych operator nie jest już koniecznie ciągły i nie wszędzie można go zdefiniować, np. jako operator różniczkowy w przestrzeni rozkładów.

Jeżeli liczba stanów układu S jest skończona i wydaje się możliwe przejście od każdego stanu (w określonej liczbie kroków) do każdego innego stanu, to prawdopodobieństwa graniczne stanów istnieją i również nie zależą od stanu początkowego systemu.

Na ryc. pokazuje wykres stanów i przejść spełniających podany warunek: z dowolnego stanu system może prędzej czy później przejść do dowolnego innego stanu. Warunek nie będzie spełniony, gdy zmieni się kierunek strzałki 4-3 na wykresie na ryc., lecz w odwrotną stronę.

Załóżmy, że podany warunek jest spełniony, a zatem istnieją prawdopodobieństwa graniczne:

Prawdopodobieństwa graniczne będą oznaczane tymi samymi literami, co prawdopodobieństwa stanów, przy czym mają na myśli liczby, a nie zmienne (funkcje czasu).

Jest oczywiste, że graniczne prawdopodobieństwa stanów muszą sumować się do jedności: W rezultacie w systemie ustala się pewien ograniczający reżim stacjonarny: nawet jeśli system losowo zmienia swoje własne stany, prawdopodobieństwo każdego z tych stanów nie zależą od czasu i każdy z nich zachodzi z pewnym stałym prawdopodobieństwem, które jest średnim względnym czasem przebywania układu w tym stanie.

15. Proces śmierci i reprodukcji.

Nazwijmy proces Markowa śmierci i reprodukcji z czasem ciągłym takim procesem, który może przyjmować tylko nieujemne wartości całkowite; zmiany w tym procesie mogą nastąpić w dowolnym momencie czasu t, natomiast w dowolnym momencie mogą albo wzrosnąć o jeden, albo pozostać niezmienione.

Przepływy reprodukcyjne λi(t) będziemy nazywać przepływami Poissona prowadzącymi do wzrostu funkcji X(t). Odpowiednio μi(t) są strumieniami śmierci prowadzącymi do zmniejszenia funkcji X(t).

Ułóżmy równanie Kołmogorowa z wykresu:

Jeśli przepływ jest stanem skończonym:

Układ równań Kołmogorowa dla procesu śmierci i reprodukcji z ograniczoną liczbą stanów ma postać:

Proces czystej reprodukcji jest procesem śmierci i reprodukcji, w którym intensywności wszystkich potoków śmierci są równe zeru.

Proces czystej śmierci jest procesem śmierci i reprodukcji, w którym intensywność wszystkich strumieni reprodukcji jest równa zeru.

16. Systemy kolejkowe z awariami.

Najprostszym z problemów rozpatrywanych w ramach teorii kolejkowania jest model jednokanałowego QS z awariami lub stratami.

Należy zauważyć, że w tym przypadku liczba kanałów wynosi 1 (). Kanał ten odbiera strumień żądań Poissona, którego intensywność jest równa . Czas wpływa na intensywność:

Jeśli wniosek wpłynie na kanał, który nie jest aktualnie wolny, zostanie odrzucony i nie będzie już wyświetlany w systemie. Obsługa wniosków odbywa się w czasie losowym, którego rozkład realizowany jest zgodnie z prawem wykładniczym z parametrem:

17. Systemy kolejkowe z oczekiwaniem.

Żądanie otrzymane, gdy kanał jest zajęty, jest umieszczane w kolejce i oczekuje na obsługę.

System z ograniczoną długością kolejki. Załóżmy najpierw, że ilość miejsc w kolejce jest ograniczona m, czyli jeżeli wniosek wpłynie w momencie, gdy w kolejce jest już m wniosków, to pozostawi system bez obsługi. W przyszłości kierując m do nieskończoności uzyskamy charakterystykę jednokanałowego QS bez ograniczeń co do długości kolejki.

Będziemy numerować stany QS zgodnie z liczbą aplikacji w systemie (zarówno obsługiwanych, jak i oczekujących na obsługę):

— kanał jest bezpłatny;

— kanał jest zajęty, nie ma kolejki;

— kanał jest zajęty, w kolejce znajduje się jedno żądanie;

—kanał jest zajęty, w kolejce znajduje się k - 1 żądań;

— kanał jest zajęty, w kolejce czeka mnóstwo aplikacji.

18. Metody podejmowania decyzji w warunkach konfliktowych. Gry matrixowe. Czyste i mieszane gry strategiczne.

Gra macierzowa to gra dwóch graczy o skończonej sumie zerowej, w której wypłata gracza 1 jest określona w postaci macierzy (wiersz macierzy odpowiada numerowi zastosowanej strategii gracza 2, kolumna odpowiada do numeru zastosowanej strategii gracza 2; na przecięciu wiersza i kolumny macierzy znajduje się wypłata gracza 1, odpowiednia do zastosowanych strategii).

W przypadku gier macierzowych udowodniono, że każda z nich ma rozwiązanie i można je łatwo znaleźć, sprowadzając grę do problemu programowania liniowego.

Dwuosobową grę macierzową o sumie zerowej można traktować jako następującą abstrakcyjną grę dla dwóch graczy.

Pierwszy gracz ma m strategii i = 1,2,...,m, drugi gracz ma n strategii j = 1,2,...,n. Każdej parze strategii (i,j) przyporządkowana jest liczba aij, która wyraża zysk gracza 1 kosztem gracza 2, jeśli pierwszy gracz zaakceptuje jego i-tą strategię, a 2 - swoją j-tą strategię.

Każdy gracz wykonuje jeden ruch: gracz 1 wybiera swoją i-tą strategię (i=), 2 - swoją j-tą strategię (j=), po czym gracz 1 otrzymuje wypłatę aij kosztem gracza 2 (jeśli aij

Każda strategia gracza i=; j = jest często nazywana czystą strategią.

Definicja. Strategia mieszana gracza to pełny zbiór prawdopodobieństw wykorzystania jego strategii czystych.

Zatem jeśli gracz 1 ma m czystych strategii 1,2,...,m, to jego strategia mieszana x jest zbiorem liczb x = (x1,..., xm) spełniającym zależności

xi³ 0 (i= 1,m), =1.

Podobnie dla gracza 2, który ma n czystych strategii, strategia mieszana y jest zbiorem liczb

y = (y1, ..., yn), yj ³ 0, (j = 1,n), = 1.

Ponieważ za każdym razem, gdy gracz korzysta z jednej czystej strategii, wyklucza użycie innej, czyste strategie są zdarzeniami niezgodnymi. Co więcej, są to jedyne możliwe zdarzenia.

Strategia czysta jest szczególnym przypadkiem strategii mieszanej. Rzeczywiście, jeśli w strategii mieszanej zostanie zastosowana jakakolwiek i-ta czysta strategia z prawdopodobieństwem 1, wówczas wszystkie inne czyste strategie nie zostaną zastosowane. I ta i-ta strategia czysta jest szczególnym przypadkiem strategii mieszanej. Aby zachować tajemnicę, każdy gracz stosuje własne strategie, niezależnie od wyborów drugiego gracza.

19. Geometryczna metoda rozwiązywania gry macierzowej.

Rozwiązanie gier o rozmiarze 2xn lub nx2 pozwala na jednoznaczną interpretację geometryczną. Takie gry można rozwiązać graficznie.

Na płaszczyźnie XY wzdłuż osi odciętych wykreślamy pojedynczy odcinek A1A2 (rysunek 5.1). Przypiszmy każdemu punktowi odcinka strategię mieszaną U = (u1, u2). Co więcej, odległość od jakiegoś punktu pośredniego U do prawego końca tego odcinka to prawdopodobieństwo u1 wyboru strategii A1, odległość do lewego końca to prawdopodobieństwo u2 wyboru strategii A2. Punkt A1 odpowiada czystej strategii A1, punkt A2 odpowiada czystej strategii A2.

W punktach A1 i A2 przywrócimy prostopadłe i przeniesiemy na nie wygrane graczy. Na pierwszej prostopadłej (zbiegającej się z osią OY) pokazujemy wypłatę gracza A przy zastosowaniu strategii A1, na drugiej – przy zastosowaniu strategii A2. Jeśli gracz A zastosuje strategię A1, to jego wypłata przy strategii B1 gracza B będzie równa 2, a przy strategii B2 będzie równa 5. Liczby 2 i 5 na osi OY odpowiadają punktom B1 i B2. Podobnie na drugiej prostopadłej znajdujemy punkty B”1 i B”2 (zyskuje 6 i 4).

Łącząc punkty B1 i B"1, B2 i B"2 otrzymujemy dwie linie proste, których odległość od osi OX określa średnią wypłatę dla dowolnej kombinacji odpowiednich strategii.

Na przykład odległość dowolnego punktu na odcinku B1B"1 do osi OX określa średnią wypłatę gracza A dla dowolnej kombinacji strategii A1 i A2 (z prawdopodobieństwami u1 i u2) oraz strategii B1 gracza B.

Współrzędne punktów należących do linii łamanej B1MB"2 wyznaczają minimalną wypłatę gracza A w przypadku stosowania przez niego dowolnej strategii mieszanej. Ta minimalna wartość jest największa w punkcie M, zatem punkt ten odpowiada strategii optymalnej U* = ( ,), a jej rzędna jest równa kosztowi gry v .

Współrzędne punktu M znajdujemy jako współrzędne punktu przecięcia linii B1B"1 i B2B"2.

Aby to zrobić, musisz znać równania linii. Takie równania można utworzyć korzystając ze wzoru na równanie prostej przechodzącej przez dwa punkty:

Utwórzmy równania linii prostych dla naszego problemu.

Linia B1B"1: = lub y = 4x + 2.

Bezpośrednie B2B"2: = lub y = -x + 5.

Otrzymujemy układ: y = 4x + 2,

Rozwiążmy to: 4x + 2 = -x + 5,

x = 3/5, y = -3/5 + 5 = 22/5.

Zatem U = (2/5, 3/5), v = 22/5.

20. Gry dwumacierzowe.

Gra bimatrix to skończona gra dwóch graczy o sumie niezerowej, w której wypłaty każdego gracza są określone przez macierze oddzielnie dla odpowiedniego gracza (w każdej macierzy wiersz odpowiada strategii gracza 1, kolumna odpowiada strategii gracza 2, na przecięciu wiersza i kolumny w pierwszej macierzy znajduje się wypłata gracza 1, w drugiej macierzy - wypłata gracza 2.)

Opracowano także teorię optymalnego zachowania gracza dla gier dwumacierzowych, jednak rozwiązywanie takich gier jest trudniejsze niż w przypadku zwykłych gier macierzowych.

21. Gry statystyczne. Zasady i kryteria podejmowania decyzji w warunkach niepewności całkowitej i częściowej.

W badaniach operacyjnych powszechnie wyróżnia się trzy rodzaje niepewności:

niepewność celów;

niepewność naszej wiedzy o środowisku i czynnikach działających w tym zjawisku (niepewność natury);

niepewność działań aktywnego lub biernego partnera lub przeciwnika.

W powyższej klasyfikacji rodzaj niepewności rozpatrywany jest z punktu widzenia tego czy innego elementu modelu matematycznego. Na przykład niepewność celów znajduje odzwierciedlenie przy stawianiu zadania w wyborze poszczególnych kryteriów lub całego wektora korzystnego efektu.

Z drugiej strony pozostałe dwa rodzaje niepewności wpływają głównie na formułowanie funkcji celu równań ograniczeń i metodę decyzyjną. Oczywiście powyższe stwierdzenie ma charakter dość warunkowy, jak zresztą każda klasyfikacja. Przedstawiamy go jedynie w celu zwrócenia uwagi na kilka dodatkowych cech niepewności, o których należy pamiętać w procesie decyzyjnym.

Rzecz w tym, że oprócz omówionej powyżej klasyfikacji niepewności, należy wziąć pod uwagę ich rodzaj (lub „rodzaj”) z punktu widzenia ich związku z losowością.

Na tej podstawie można wyróżnić niepewność stochastyczną (probabilistyczną), gdy nieznane czynniki są statystycznie stabilne i dlatego reprezentują zwykłe obiekty teorii prawdopodobieństwa - zmienne losowe (lub funkcje losowe, zdarzenia itp.). W takim przypadku wszystkie niezbędne cechy statystyczne (prawa dystrybucji i ich parametry) muszą być znane lub określone podczas ustalania problemu.

Przykładem takich zadań może być w szczególności system konserwacji i naprawy wszelkiego rodzaju sprzętu, system organizacji trzebieży itp.

Skrajnym przypadkiem może być także niepewność typu niestochastycznego (według słów E.S. Ventzela – „zła niepewność”), w której nie istnieją żadne założenia dotyczące stabilności stochastycznej. Wreszcie można mówić o pośrednim typie niepewności, gdy decyzja podejmowana jest na podstawie pewnych hipotez dotyczących praw rozkładu zmiennych losowych. Jednocześnie decydent musi mieć na uwadze niebezpieczeństwo rozbieżności uzyskanych wyników z warunkami rzeczywistymi. Ryzyko niedopasowania jest sformalizowane za pomocą współczynników ryzyka.

Podejmowanie decyzji w warunkach ryzyka może opierać się na jednym z następujących kryteriów:

kryterium wartości oczekiwanej;

kombinacje wartości oczekiwanej i wariancji;

znany poziom graniczny;

najbardziej prawdopodobne wydarzenie w przyszłości.

Rozdział 1. Przedmiot i zadania badań operacyjnych.

§ 1. Co to są badania operacyjne i czemu służą.

§ 2. Podstawowe pojęcia i zasady badań eksploatacyjnych.

§ 3. Matematyczne modele działań.

Rozdział 2. Odmiany problemów badań operacyjnych i podejścia do ich rozwiązywania.

§ 4. Zagadnienia bezpośrednie i odwrotne badań operacyjnych. Zadania deterministyczne.

§ 5. Problem wyboru rozwiązania w warunkach niepewności.

§ 6. Problemy wielokryterialne w badaniach operacyjnych. „Podejście systemowe”.

Rozdział 3. Programowanie liniowe.

§ 7. Zagadnienia programowania liniowego.

§ 8. Główny problem programowania liniowego.

§ 9. Istnienie rozwiązania 03LP i metody jego znalezienia.

§ 10. Problem transportu programowania liniowego.

§ 11. Zagadnienia programowania liczb całkowitych. Pojęcie programowania nieliniowego.

Rozdział 4. Programowanie dynamiczne.

§ 12. Metoda programowania dynamicznego.

§ 13. Przykłady rozwiązywania problemów programowania dynamicznego.

§ 14. Problem programowania dynamicznego w formie ogólnej. Zasada optymalności.

Rozdział 5. Procesy losowe Markowa.

§ 15. Pojęcie procesu Markowa.

§ 16. Strumienie wydarzeń.

§ 17. Równania Kołmogorowa dla prawdopodobieństw stanu. Prawdopodobieństwa stanu końcowego.

Rozdział 6. Teoria kolejkowania.

§ 18. Zagadnienia teorii kolejek. Klasyfikacja systemów kolejkowych.

§ 19. Schemat śmierci i reprodukcji. Wzór Little’a.

§ 20. Najprostsze systemy kolejkowe i ich charakterystyka.

§ 21. Bardziej złożone problemy teorii kolejek.

Rozdział 7. Modelowanie statystyczne procesów losowych (metoda Monte Carlo).

§ 22. Idea, cel i zakres stosowania metody.

§ 23. Pojedyncza działka i formy jej organizacji.

§ 24. Wyznaczanie charakterystyk stacjonarnego procesu losowego na podstawie jednej realizacji.

Rozdział 8. Metody gier uzasadniające decyzję.

§ 25. Przedmiot i zadania teorii gier.

§ 26. Antagonistyczne gry macierzowe.

§ 27. Metody rozwiązywania gier skończonych.

§ 28. Zagadnienia teorii rozwiązań statystycznych.

PRZEDMIOT I CELE BADAŃ OPERACYJNYCH

Podstawowe pojęcia i zasady badań operacyjnych

W tej części zapoznamy się z terminologią, podstawowymi pojęciami i zasadami nauki o „badaniach operacyjnych”.

Operacja to dowolne wydarzenie (system działań) połączone jednym planem i mające na celu osiągnięcie jakiegoś celu (wszystkie zdarzenia omówione w paragrafach 1–8 poprzedniego akapitu to „operacje”).

Operacja jest zawsze zdarzeniem kontrolowanym, czyli od nas zależy, jak dobierzemy pewne parametry charakteryzujące jej organizację. „Organizacja” jest tu rozumiana w szerokim znaczeniu tego słowa, łącznie z zespołem środków technicznych wykorzystywanych w działaniu.

Każdy konkretny dobór parametrów zależnych od nas nazywamy rozwiązaniem. Decyzje mogą być skuteczne i nieudane, rozsądne i nierozsądne. Rozwiązania optymalne to takie, które są lepsze od innych ze względu na pewne cechy. Celem badań operacyjnych jest wstępne ilościowe uzasadnienie optymalnych rozwiązań.

Czasami (stosunkowo rzadko) w wyniku badania udaje się wskazać jedno rozwiązanie ściśle optymalne, znacznie częściej udaje się zidentyfikować obszar niemal równoważnych rozwiązań optymalnych (rozsądnych), w ramach którego można dokonać ostatecznego wyboru.

Należy pamiętać, że samo podejmowanie decyzji wykracza poza zakres badania operacji i wchodzi w zakres kompetencji osoby odpowiedzialnej, częściej – grupy osób, którym dane jest prawo ostatecznego wyboru i które są za ten wybór odpowiedzialne. Dokonując wyboru, mogą wziąć pod uwagę, oprócz zaleceń wynikających z obliczenia matematycznego, szereg czynników (ilościowych i jakościowych), które nie zostały uwzględnione w tym obliczeniu.

Niezbędna obecność osoby (jako ostatecznego decydenta) nie zostaje zniweczona nawet w obecności w pełni zautomatyzowanego systemu kontroli, który, jak się wydaje, podejmuje decyzję bez udziału człowieka. Nie wolno nam zapominać, że samo stworzenie algorytmu sterującego, wybór jednej z jego możliwych opcji, to także decyzja i to bardzo odpowiedzialna. W miarę rozwoju automatów kontrolnych funkcje człowieka nie są zniesione, lecz po prostu przeniesione z jednego, podstawowego poziomu na inny, wyższy. Ponadto szereg zautomatyzowanych systemów sterowania zapewnia aktywną interwencję człowieka podczas kontrolowanego procesu.

Parametry te, których kombinacja tworzy rozwiązanie, nazywane są elementami rozwiązania. Jako elementy rozwiązania mogą pojawić się różne liczby, wektory, funkcje, cechy fizyczne itp. Na przykład, jeśli sporządzony zostanie plan transportu jednorodnego towaru z punktów wyjścia A 1, A 2,…, A m do miejsc docelowych W 1,B 2, ..., B n, wtedy elementami rozwiązania będą liczby x ij , pokazujący, jaka ilość ładunku zostanie wysłana z 1. punktu wyjścia A ja V J miejsce docelowe w j. Zestaw liczb X 11 , X 12, …, X 1 n , …, X m 1, X m2,…, x min tworzy rozwiązanie.

W najprostszych problemach badań operacyjnych liczba elementów rozwiązania może być stosunkowo niewielka. Jednak w większości problemów o znaczeniu praktycznym liczba elementów rozwiązania jest bardzo duża, co czytelnik może sprawdzić, próbując samodzielnie zidentyfikować i „nazwać” elementy rozwiązania w przykładach 1–8 poprzedniego akapitu. Dla uproszczenia cały zbiór elementów rozwiązania będziemy oznaczać jedną literą X i powiedz „decyzja” X".

Oprócz elementów rozwiązania, które w pewnym stopniu możemy kontrolować, w każdym zadaniu badań operacyjnych podawane są także warunki „dyscyplinujące”, które są od początku ustalone i których nie można naruszać (np. nośność maszyny, wielkość planowanego zadania;

charakterystyka wagowa sprzętu itp.). Warunki te obejmują w szczególności środki (materialne, techniczne, ludzkie), którymi mamy prawo dysponować, oraz inne ograniczenia nałożone decyzją. Razem tworzą tak zwany „zbiór możliwych rozwiązań”.

Oznaczmy ten zbiór ponownie jedną literą X, i fakt, że decyzja X należy do tego zbioru, zapiszemy to jako wzór: X X(czytaj: element X zawarte w zestawie X).

Rzecz w tym, że w wielu możliwych rozwiązaniach X podkreśl te rozwiązania X(czasami jeden, ale częściej cały obszar rozwiązań), które z tego czy innego punktu widzenia są bardziej skuteczne (skuteczne, preferowane) niż inne. Aby porównać różne rozwiązania pod względem efektywności, trzeba dysponować jakimś kryterium ilościowym, tzw. wskaźnikiem efektywności (często nazywanym „funkcją celu”). Wskaźnik ten dobiera się tak, aby odzwierciedlał docelową orientację operacji. Za „najlepsze” rozwiązanie zostanie uznane to, które w największym stopniu przyczynia się do osiągnięcia celu. Aby wybrać „nazwa po nazwie” wskaźnik wydajności W, Przede wszystkim musisz zadać sobie pytanie: czego chcemy Do czego dążymy podejmując się operacji? Wybierając rozwiązanie, w naturalny sposób będziemy preferować takie, które odwraca wskaźnik efektywności W do maksimum (lub do minimum). Na przykład chciałbym zmaksymalizować dochód z operacji; jeżeli wyznacznikiem efektywności są koszty, wskazane jest ograniczenie ich do minimum. Jeżeli pożądana jest maksymalizacja wskaźnika efektywności, zapiszemy to w formularzu W => max, a jeśli zminimalizowany - W => min.

Bardzo często operacji towarzyszą czynniki losowe (katastrofy pogodowe, wahania podaży i popytu, awarie urządzeń technicznych itp.). W takich przypadkach za wskaźnik efektywności przyjmuje się zwykle nie samą wartość, którą chciałoby się maksymalizować (minimalizować), ale jej wartość średnią (oczekiwanie matematyczne).

W niektórych przypadkach zdarza się, że operacja, której towarzyszą czynniki losowe, ma jakiś bardzo konkretny cel A, które można osiągnąć jedynie w całości lub w ogóle (schemat „tak-nie”) i nie interesują nas żadne rezultaty pośrednie. Następnie jako wskaźnik efektywności wybiera się prawdopodobieństwo osiągnięcia tego celu R(A). Przykładowo, jeśli strzela się do jakiegoś obiektu pod warunkiem jego zniszczenia, to wskaźnikiem skuteczności będzie prawdopodobieństwo zniszczenia obiektu.

Wybór niewłaściwego wskaźnika wydajności jest bardzo niebezpieczny. Działalność zorganizowana według niefortunnie wybranego kryterium może prowadzić do nieuzasadnionych kosztów i strat (przypomnijmy chociażby osławiony „wał” jako główne kryterium oceny działalności gospodarczej przedsiębiorstw).

Aby zilustrować zasady wyboru wskaźnika efektywności, powróćmy jeszcze raz do przykładów 1 – 8 z § 1, dla każdego z nich wybierz naturalny wskaźnik efektywności i wskaż, czy należy go maksymalizować, czy minimalizować. Analizując przykłady, należy mieć na uwadze, że nie we wszystkich wybór wskaźnika wykonania jest jednoznacznie podyktowany słownym opisem zadania, zatem pomiędzy czytelnikiem a autorem mogą w tej kwestii występować różnice.

1. Plan dostaw przedsiębiorstwa. Celem operacji jest zapewnienie dostaw surowców przy jednoczesnej minimalizacji kosztów transportu. Wskaźnik wydajności R- całkowite koszty transportu surowców w jednostce czasu, na przykład na miesiąc ( R => min).

2. Budowa odcinka autostrady. Budowę należy zaplanować tak, aby zakończyć ją jak najszybciej. Naturalnym wyznacznikiem efektywności byłby czas zakończenia budowy, gdyby nie był on powiązany z czynnikami losowymi (awarie sprzętu, opóźnienia w realizacji poszczególnych robót). Dlatego też jako wskaźnik efektywności można wybrać średni oczekiwany czas T zakończenie budowy (T => min).

3. Sprzedaż towarów sezonowych. Jako wskaźnik efektywności można przyjąć średni oczekiwany zysk P ze sprzedaży towarów w sezonie (P => max).

4. Zabezpieczenie dróg przed śniegiem. Mówimy o najkorzystniejszym ekonomicznie planie ochrony przed śniegiem, dlatego jako wskaźnik efektywności możesz wybrać średnie koszty na jednostkę czasu (na przykład rocznie) R na utrzymanie i eksploatację dróg, w tym koszty związane zarówno z budową urządzeń ochronnych, jak i oczyszczaniem dróg oraz opóźnieniami w ruchu (R => min).

5. Nalot przeciw okrętom podwodnym. Ponieważ nalot ma bardzo konkretny cel A - zniszczenie łodzi, wówczas jako wskaźnik skuteczności należy wybrać prawdopodobieństwo R(A), że łódź zostanie zniszczona.

6. Kontrola próbek produktów. Naturalnym wskaźnikiem efektywności, jaki sugeruje sformułowanie problemu, jest średni oczekiwany koszt R za kontrolę w jednostce czasu, pod warunkiem, że system kontroli zapewnia określony poziom jakości, np. średni procent wad nie jest wyższy od zadanego ( R=> min).

7. Badanie lekarskie. Możesz wybrać średni procent (udział) jako wskaźnik efektywności Q zidentyfikowanych pacjentów i nosicieli infekcji (P => sprawdzać).

8. Usługi biblioteczne. W sformułowaniu problemu celowo dopuszczono pewną niejasność:

Nie jest jasne, co oznacza „najlepsza obsługa klienta” lub „maksymalne spełnianie jego żądań”. Jeśli jakość usługi ocenia się na podstawie czasu oczekiwania na jej otrzymanie abonent zamawiający książkę, wówczas za wskaźnik efektywności można przyjąć średni czas T oczekiwań wobec książki przez czytelnika, który złożył o nią wniosek ( T=> min). Można podejść do problemu z nieco innych stanowisk, wybierając średnią liczbę jako wskaźnik efektywności M książek wydanych w jednostce czasu (M => maks.).

Rozważane przykłady zostały specjalnie wybrane na tyle proste, że wybór wskaźnika wykonania był stosunkowo łatwy i był bezpośrednio podyktowany słownym sformułowaniem problemu i jego (prawie zawsze) jednoznacznym ukierunkowaniem na cel. Jednak w praktyce nie zawsze tak jest. Czytelnik może to zweryfikować, próbując na przykład wybrać wskaźnik efektywności transportu miejskiego. Co powinniśmy wziąć za taki wskaźnik? Średnia prędkość pasażerów podróżujących po mieście? Albo średnią liczbę przewożonych pasażerów? Albo średnią liczbę kilometrów, jaką będzie musiała przejść na piechotę osoba, której nie da się dowieźć we właściwe miejsce? Jest tu o czym myśleć!

Niestety w większości problemów o znaczeniu praktycznym wybór wskaźnika efektywności nie jest prosty i jest rozwiązywany niejednoznacznie. W przypadku każdego złożonego zadania typowa jest sytuacja, gdy skuteczności operacji nie można w sposób wyczerpujący scharakteryzować jedną liczbą – do pomocy trzeba sprowadzić inne. Z takimi „wielokryterialnymi” problemami zapoznamy się w § 6.

Przykłady rozwiązywania problemów programowania dynamicznego

W tej sekcji przyjrzymy się (a nawet rozwiążemy do końca) kilku prostym (skrajnie uproszczonym) przykładom problemów programowania dynamicznego

1. Wyznaczenie najkorzystniejszej trasy pomiędzy dwoma punktami. Przypomnijmy sobie problem 4 z poprzedniego akapitu i rozwiążmy go do końca w skrajnie (i celowo) uproszczonych warunkach. Musimy zbudować ścieżkę łączącą

dwa punkty A I W, z których drugi leży na północny wschód od pierwszego. Dla uproszczenia, powiedzmy. że wytyczanie ścieżki składa się z szeregu kroków, a na każdym kroku możemy poruszać się albo na wschód, albo na północ; w jakikolwiek sposób od A V W jest schodkową linią przerywaną, której odcinki są równoległe do jednej z osi współrzędnych (ryc. 13.1). Znane są koszty budowy każdego z tych odcinków. Wymagane jest ułożenie takiej ścieżki A V W, przy którym koszty całkowite są minimalne.

Jak to zrobić? Można to zrobić na jeden z dwóch sposobów: albo przejść przez wszystkie możliwe opcje ścieżki i wybrać tę przy minimalnych kosztach (a przy dużej liczbie segmentów jest to bardzo, bardzo trudne!); lub oddziel proces przejścia od A V W na osobne etapy (jeden krok - jeden segment) i krok po kroku optymalizuj sterowanie. Okazuje się, że druga metoda jest nieporównywalnie wygodniejsza! Tutaj, podobnie jak w innych badaniach operacyjnych, ukierunkowane, zorganizowane poszukiwanie rozwiązania ma przewagę nad naiwnym poszukiwaniem „w ciemno”.

Pokażemy, jak to się robi, na konkretnym przykładzie. Podziel odległość od A zanim W w kierunku wschodnim, powiedzmy, na 7 części, a w kierunku północnym - na 5 części (w zasadzie kruszenie może być tak małe, jak to pożądane). Następnie dowolna ścieżka z A V W zawiera T= 7 + 5 == 12 segmentów skierowanych na wschód lub północ (ryc. 13.2). Na każdym segmencie umieśćmy liczbę wyrażającą (w niektórych konwencjonalnych jednostkach) koszt ułożenia ścieżki wzdłuż tego odcinka. Musisz wybrać tę ścieżkę A V W, dla których suma liczb na segmentach jest minimalna.

Konstruowaną ścieżkę rozważymy jako system kontrolowany S, poruszanie się pod wpływem kontroli ze stanu początkowego A do końca W. Stan tego układu przed rozpoczęciem każdego etapu będzie scharakteryzowany dwiema współrzędnymi: wschodnią (X) i północna (y), obie są liczbami całkowitymi (0 X 5 7, 0 Na 5). Dla każdego ze stanów układu (punkt węzłowy siatki prostokątnej na rys. 13.2) musimy znaleźć warunkowe optymalne sterowanie: od tego punktu należy udać się na północ (kontrola „c”) lub na wschód (kontrola „c”) "C"). Sterowanie to jest tak dobrane, aby koszt wszystkich pozostałych do końca kroków (łącznie z tym) był minimalny. Koszt ten będziemy nadal nazywać „warunkowym optymalnym zyskiem” (choć w tym przypadku nie jest to „wygrana”, ale „strata”) dla danego stanu systemu S przed rozpoczęciem następnego kroku.

Procedurę optymalizacji warunkowej rozwiniemy w przeciwnym kierunku - od końca do początku. Na początek przeprowadzimy optymalizację warunkową ostatniego, 12-tego kroku. Rozważmy osobno prawy górny róg naszej prostokątnej siatki (ryc. 13.3). Gdzie możemy być po 11. kroku? Tylko

dokąd w jednym (ostatnim) kroku można dojść W, czyli w jednym z punktów W 1 Lub O 2. Jeśli jesteśmy w punkcie W 1 , nie mamy wyboru (kontrola przymusowa): musimy udać się na wschód, a będzie nas to kosztować 10 jednostek. Zapiszmy tę liczbę 10 w kółku obok kropki W 1 , i pokazujemy optymalną kontrolę za pomocą krótkiej strzałki wychodzącej z W 1 i skierowany na wschód. Za punkt O 2 sterowanie jest również wymuszone (północ), natężenie przepływu do końca wynosi 14, zapiszemy to w kółku w punkcie O 2. W ten sposób przeprowadzana jest optymalizacja warunkowa ostatniego kroku i warunkowe optymalne wzmocnienie dla każdego z punktów B1, B2 znalezione i zapisane w odpowiednim okręgu.

Teraz zoptymalizujmy przedostatni (11.) krok. Po przedostatnim (10.) kroku mogliśmy wylądować w jednym z punktów C1, C2, C3(ryc. 13.4). Znajdźmy dla każdego z nich warunkową optymalną kontrolę i warunkowe optymalne wzmocnienie. Za punkt C 1 kontrola wymuszona: idź na wschód;

do końca będzie nas to kosztować 21 jednostek (11 na tym etapie plus 10 wpisanych w kółko w godz W 1). W kółku w kropce piszemy liczbę 21 C 1. Za punkt C 2 kontrola nie jest już wymuszona: możemy udać się zarówno na wschód, jak i na północ. W pierwszym przypadku wydamy 14 jednostek na ten krok i od O 2 Pozostało jeszcze 14 sztuk, w sumie 28 jednostek. Jeśli pójdziemy na północ, wydamy 13 + 10, co daje w sumie 23 jednostki. Oznacza to, że warunkowa optymalna kontrola w danym punkcie C2 - idź na północ (zaznaczamy to strzałką i wpisujemy liczbę 23 w kółku obok C2), Za punkt C 3 kontrola jest ponownie wymuszona („z”), do końca będzie to kosztować 22 jednostki (umieść strzałkę na północ, wpisz liczbę 22 w kółko w C 3).

Podobnie „cofając się” od przedostatniego kroku wstecz, dla każdego punktu o współrzędnych całkowitych znajdujemy warunkową optymalną kontrolę („c” lub „c”), którą oznaczamy strzałką, oraz warunkowe optymalne wzmocnienie (zużycie do koniec ścieżki), który zapisujemy w kółku. Oblicza się go w następujący sposób: natężenie przepływu na tym etapie dodaje się do już zoptymalizowanego natężenia przepływu zapisanego w okręgu wskazanym strzałką. Tym samym na każdym etapie optymalizujemy tylko ten krok, a kolejne są już zoptymalizowane. Końcowy wynik procedury optymalizacyjnej pokazano na rys. 13,5.

Tym samym optymalizacja warunkowa została już zakończona: niezależnie od tego, w którym z punktów węzłowych się znajdujemy, wiemy już, dokąd się udać (strzałka) i ile będzie nas kosztować dotarcie do końca (liczba w okręgu). W okręgu w punkcie A optymalne wzmocnienie rejestruje się dla całej konstrukcji ścieżki A V W:

W* = 118.

Teraz pozostaje skonstruować bezwarunkową optymalną kontrolę - trajektorię prowadzącą z A I W w najtańszy sposób. Aby to zrobić, wystarczy „słuchać strzałek”, czyli czytać, co instruują Cię na każdym kroku. Ta optymalna trajektoria jest zaznaczona na ryc. 13,5 zakreślił dwukrotnie. Odpowiednia bezwarunkowa optymalna kontrola będzie wynosić:

x* =(s, s, s, s, w, w, s, w, w, w, w, w)

to znaczy, że musimy zrobić pierwsze cztery kroki na północ, kolejne dwa na wschód, potem znowu jeden na północ i pozostałe pięć na wschód. Problem jest rozwiązany.

Należy pamiętać, że podczas optymalizacji warunkowej możemy spotkać się z przypadkiem, w którym obydwie kontrole dla jakiegoś punktu na płaszczyźnie są optymalne, tzn. prowadzą do takiego samego wydatku środków od tego punktu do końca, np. w punkcie o współrzędnych (5; 1) obydwa regulatory „c” i „b” są optymalne i dają do końca natężenie przepływu równe 62. Dowolnie wybieramy dowolne z nich (w naszym przypadku wybraliśmy „c”; z takim samym sukcesem mogliśmy wybrać „c” ”). Takie przypadki niejednoznacznego wyboru optymalnego sterowania spotyka się stale w programowaniu dynamicznym; w przyszłości nie będziemy ich specjalnie zaznaczać, ale po prostu dowolnie wybierzemy dowolną z równoważnych opcji. Oczywiście od tej arbitralności może zależeć optymalne sterowanie całym procesem, ale nie optymalny zysk. Ogólnie rzecz biorąc, w przypadku problemów programowania dynamicznego (podobnie jak w przypadku problemów programowania liniowego) rozwiązanie nie zawsze jest jedyne.

Wróćmy teraz do początku i spróbujmy rozwiązać problem w „naiwny” sposób, wybierając na każdym kroku, zaczynając od pierwszego, najbardziej opłacalnego (dla tego kroku) kierunku (jeśli są dwa, wybierz dowolny ). W ten sposób uzyskamy kontrolę

x = (c, s, w, w, w, w, s, w, w, w, s, s).

Obliczmy koszty tej trajektorii. Będą równi W=10 +12 +8+10 +11 +13 +15+8 + +10+9+8+14=128, czyli z pewnością więcej niż W* = 118. W tym przypadku różnica nie jest bardzo duża, ale w innych może być znacząca.

W rozwiązanym powyżej problemie warunki zostały celowo maksymalnie uproszczone. Oczywiście nikt nie będzie prowadził torów kolejowych „po schodach”, poruszając się wyłącznie na północ lub dokładnie na wschód. Dokonaliśmy tego uproszczenia, aby w każdym punkcie wybierać tylko z dwóch kontrolek: „c” lub „c”. Zamiast dwóch możliwych kierunków można by wprowadzić kilka i w dodatku podjąć mniejsze kroki; Nie ma to zasadniczego znaczenia, ale oczywiście komplikuje i wydłuża obliczenia.

Należy pamiętać, że w praktyce bardzo często spotyka się problemy podobne do omówionych powyżej: np. przy wyborze najszybszej trasy pomiędzy dwoma punktami lub najbardziej ekonomicznego (pod względem zużycia paliwa) zwiększenia prędkości i wysokości przez statek powietrzny.

Poczynimy jedną przelotną uwagę. Uważny czytelnik zapewne zauważył, że w naszym problemie chodzi o punkty A I W(początek i koniec) w zasadzie nie różnią się od siebie: możliwe byłoby skonstruowanie warunkowych kontroli optymalnych nie od końca do początku, ale od początku do końca, a bezwarunkowych - w przeciwnym kierunku. Rzeczywiście to prawda: w każdym problemie programowania dynamicznego „początek” i „koniec” można zamienić miejscami. Jest to całkowicie równoważne z wcześniej opisaną metodą pod względem obliczeń, jednak jest nieco mniej wygodne przy słownym wyjaśnianiu idei metody: łatwiej jest argumentować, odwołując się na początku danego kroku do „już ustalonych” warunków niż te, które po tym kroku jeszcze „przyjdą”. W istocie oba podejścia są całkowicie równoważne.

2. Problem alokacji zasobów. Metoda programowania dynamicznego pozwala skutecznie rozwiązać wiele problemów ekonomicznych (patrz na przykład). Rozważmy jeden z najprostszych takich problemów. Dysponujemy pewną rezerwą środków (zasobów) DO, które należy rozdzielić T przedsiębiorstwa P 1, P 2, ..., P m. Każde z przedsiębiorstw P I inwestując w niego trochę pieniędzy X generuje dochód w zależności od X, tj. reprezentujący jakiś rodzaj funkcji ( X). Wszystkie funkcje ( X) (I = 1, 2, ..., T) są dane (oczywiście funkcje te są niemalejące). Pytanie brzmi: jak rozdzielać środki? DO. pomiędzy przedsiębiorstwami tak, aby łącznie dawały maksymalny dochód?

Problem ten można łatwo rozwiązać metodą programowania dynamicznego, choć w swoim sformułowaniu nie ma wzmianki o czasie, to jednak można w myślach rozłożyć operację podziału środków w jakiejś kolejności, uznając za pierwszy krok inwestycję środków w przedsiębiorstwo P 1, drugie - do P 2 itd.

System zarządzany S w tym przypadku rozdzielone fundusze lub zasoby. Stan systemu S przed każdym krokiem jest oznaczony jedną liczbą S- rezerwa gotówkowa środków jeszcze niezainwestowanych. W tym problemie środkiem są „sterowania krokowe”. x 1, x 2, ..., x 3, przydzielane przedsiębiorstwom. Należy znaleźć optymalną kontrolę, czyli taki zbiór liczb x 1, x 2, ..., x m, przy którym całkowity dochód jest maksymalny:

(13.1)

Rozwiążmy to zadanie najpierw w sposób ogólny, formalny, a następnie dla konkretnych danych liczbowych. Znajdziemy coś dla każdego I V kroku jest warunkowym optymalnym zyskiem (od tego kroku do końca), gdybyśmy podeszli do tego kroku z rezerwą środków S. Oznaczmy warunkowe optymalne wzmocnienie W i (S), a odpowiednią warunkową optymalną kontrolą są inwestowane środki I--te przedsiębiorstwo, - xi(S).

Optymalizację zacznijmy od ostatniej, T - krok. Podejdźmy do tego kroku z pozostałymi środkami S. Co powinniśmy zrobić? Oczywiście zainwestuj całą kwotę S całkowicie w przedsiębiorstwie P M. Dlatego warunkowa optymalna kontrola włączona M-krok: przekaż wszystkie dostępne środki ostatniemu przedsiębiorstwu S, tj.

i warunkowe optymalne wzmocnienie

W m (S) = (S).

Biorąc pod uwagę cały zakres wartości S(umieszczając je wystarczająco blisko), dla każdej wartości my S będziemy wiedzieć xm(S) I Wm(S). Ostatni krok jest zoptymalizowany.

Przejdźmy do przedostatniego, (T- 1) krok. Podejdźmy do niego z rezerwą środków S. Oznaczmy W m -1 (S) warunkowa optymalna wypłata w dwóch ostatnich krokach: ( M- 1) i M-m (który jest już zoptymalizowany). Jeśli wybierzemy przez ( M- 1) krok ( M- 1) fundusze przedsiębiorstwa X, wtedy pozostanie ostatni krok S - x. Nasza wypłata na dwóch ostatnich etapach będzie równa

,

i musisz znaleźć coś takiego X, przy którym wzmocnienie to jest największe:

Znak oznacza, że ​​na całość zostaje przejęta wartość maksymalna X, możliwe (zainwestuj więcej niż S, nie możemy), z wyrażenia w nawiasach klamrowych. To maksimum jest warunkową optymalną wypłatą dla ostatnich dwóch kroków, w przeciwnym razie jest to wartość X, przy którym osiągane jest to maksimum, następuje warunkowa optymalna kontrola (T- 1) krok.

i odpowiadająca warunkowa kontrola optymalna x i (S) - następnie wartość X, w którym osiągane jest to maksimum.

Idąc dalej w ten sposób, dotrzemy w końcu do 1. przedsiębiorstwa P 1. Tutaj nie będziemy musieli zmieniać wartości S; wiemy na pewno, że rezerwa środków przed pierwszym krokiem jest równa DO:

Znaleziono więc maksymalny zysk (dochód) ze wszystkich przedsiębiorstw. Teraz pozostaje już tylko „przeczytać zalecenia”. To znaczenie X, przy którym osiągane jest maksimum (13,4), a optymalna kontrola jest już na pierwszym etapie. Po tym jak zainwestujemy te środki w pierwsze przedsiębiorstwo, zostaną nam one DO- .„Czytanie” rekomendacji dla tej wartości S, Na drugie przedsięwzięcie przeznaczamy optymalną kwotę środków:

,

itd. do końca.

Rozwiążmy teraz przykład numeryczny. Początkowy stan środków K. = 10 (jednostki konwencjonalne) i wymagane jest jego optymalne rozdysponowanie pomiędzy pięć przedsiębiorstw (t = 5). Dla uproszczenia założymy, że inwestowane są tylko całe kwoty środków. Funkcje dochodowe ( X) podano w tabeli 13.1.

Tabela 13.1

X
	0,5 1,0 1,4 2,0 2,5 2,8 3,0 3,0	0,1 0,5 1,2 1,8 2,5 2,9 3,5 3,5	0,6 1,1 1,2 1,4 1,6 1,7 1,8 1,8	0,3 0,6 1,3 1,4 1,5 1,5 1,5 1,5	1,0 1,2 1,3 1,3 1,3 1,3 1,3 1,3

W każdej kolumnie, zaczynając od określonej kwoty inwestycji, dochód przestaje rosnąć (w rzeczywistości odpowiada to temu, że każde przedsiębiorstwo jest w stanie „przyjąć” tylko ograniczoną ilość środków).

Przeprowadźmy optymalizację warunkową w sposób opisany powyżej, zaczynając od ostatniego, piątego kroku. Za każdym razem zbliżamy się do kolejnego kroku, mając rezerwę środków S, staramy się przeznaczyć tę czy inną kwotę środków na ten krok, wygrane na tym etapie przyjąć zgodnie z tabelą 13.1, dodać je do już zoptymalizowanych wygranych na wszystkich kolejnych krokach aż do końca (biorąc pod uwagę, że zostało nam już mniej środków, po prostu dla tej kwoty środków, którą podkreśliliśmy) i znajdź inwestycję, przy której kwota ta osiąga maksimum. Ta inwestycja jest warunkową optymalną kontrolą na tym etapie, a samo maksimum jest warunkowym optymalnym zyskiem.

Tabela 13.2 przedstawia wyniki optymalizacji warunkowej dla wszystkich kroków. Tabela ma następującą strukturę: pierwsza kolumna podaje wartości zasobów funduszy SS do którego podchodzimy na tym etapie. Tabela jest dalej podzielona na pięć par kolumn, odpowiadających numerowi kroku. Pierwsza kolumna każdej pary zawiera wartość

Tabela 13.2

S	ja=5	ja=4	ja=3	ja=2	ja=1
x 5(S)	W 5(S)	x 4(S)	W 4(S)	x 3(S)	W 3(S)	x 2(S)	W 2(S)	x 1(S)	W 1(S)
		1,0 1,2 1,3 1,3 1,3 1,3 1,3 1,3 1,3 1,3		1,0 1,3 1,6 2,3 2,5 2,6 2,7 2,8 2,8 2,8		1,0 1,6 2,1 2,4 2,9 3,4 3,6 3,7 3,9 4,1		1,0 1,6 2,1 2,4 2,9 3,5 4,1 4,6 5,1 5,6		5,6

warunkowa optymalna kontrola, w drugiej - warunkowe optymalne wzmocnienie. Tabela jest wypełniana od lewej do prawej, od góry do dołu. Decyzja na piątym – ostatnim – etapie jest wymuszona: wszystkie środki są rozdysponowane;

Na wszystkich pozostałych etapach rozwiązanie musi zostać zoptymalizowane. W wyniku sekwencyjnej optymalizacji kroków 5, 4, 3, 2 i 1 otrzymamy pełną listę wszystkich zaleceń dotyczących optymalnej kontroli i bezwarunkowego optymalnego wzmocnienia W* dla całej operacji - w tym przypadku wynosi 5,6. W dwóch ostatnich kolumnach tabeli 13.2 wypełniony jest tylko jeden wiersz, ponieważ znamy dokładnie stan systemu przed rozpoczęciem pierwszego kroku:

S 0 = K. = 10. Optymalne elementy sterujące na wszystkich etapach są wyróżnione ramką. W ten sposób otrzymaliśmy ostateczny wniosek: musimy przydzielić dwie jednostki z dziesięciu dla pierwszego przedsiębiorstwa, pięć jednostek dla drugiego, dwie dla trzeciego, żadnej dla czwartego i jedną jednostkę dla piątego. Przy takim podziale dochód będzie maksymalny i równy 5,6.

Aby wyjaśnić czytelnikowi, w jaki sposób wypełniana jest Tabela 13.2, zademonstrujemy to za pomocą jednego przykładowego obliczenia. Załóżmy, że musimy zoptymalizować rozwiązanie x 3(7)- co zrobić w trzecim kroku, jeśli podchodzimy do niego z rezerwą środków S= 7 i ile maksymalnie możemy wygrać na wszystkich pozostałych

Tabela 13.3

X	7 - X		W 4(7 - X)	+W 4 (7 - X)
		1,8 1,7 1,6 1,4 1,2 1,1 0,6	1,0 1,3 1,6 2,3 2,5 2,6 2,7	1,8 2,7 2,9 3,0 3,5 3,2 2,7

kroki, łącznie z trzecim? Załóżmy, że wszystkie kroki po trzecim (4 i 5) zostały już zoptymalizowane, czyli dwie pierwsze pary kolumn tabeli 13.2 są wypełnione. Znajdziemy X 3 (7) i W 3(7). W tym celu utworzymy tabelę pomocniczą (patrz tabela 13.3). Pierwsza kolumna zawiera listę wszystkich możliwych załączników X na trzecim etapie, nie przekraczając S = 7. W drugiej kolumnie – co zostanie po takiej inwestycji z rezerwy środków S = 7. W trzeciej kolumnie - wygrane w trzecim kroku z inwestowania środków X w trzecim przedsiębiorstwie wypełnia się zgodnie z kolumną (tabela 13.1). W czwartej kolumnie - optymalne wygrane na wszystkich pozostałych etapach (czwarty i piąty) pod warunkiem, że z pozostałymi środkami zbliżyliśmy się do czwartego kroku (wypełnione kolumna ja = 4 tabele 13.2). W piątej kolumnie – suma dwóch wygranych: krokowej i dalej zoptymalizowanej pod daną inwestycję X w trzeci krok.

Ze wszystkich wygranych w ostatniej kolumnie wybierane jest maksimum (w tabeli 13.3 jest ono równe W 3(7) = 3,6 i odpowiednia kontrola X(7) = 2).

Powstaje pytanie: co się stanie, jeśli w tabeli pomocniczej takiej jak 13,3 maksimum zostanie osiągnięte przy więcej niż jeden X i z dwoma lub więcej? Odpowiadamy: nie ma absolutnie znaczenia, który wybrać; wygrana nie zależy od tego. Generalnie w problemach programowania dynamicznego rozwiązanie nie musi być unikalne (już o tym wspominaliśmy).

3. Problem załadunku maszyny. Stosując metodę programowania dynamicznego można z powodzeniem rozwiązać szereg problemów optymalizacyjnych opisanych w rozdziale 3, w szczególności niektóre problemy programowania liczb całkowitych. Należy zauważyć, że całkowity charakter rozwiązań, który tak bardzo utrudnia problemy programowania liniowego, w tym przypadku nie komplikuje, a wręcz przeciwnie, upraszcza procedurę (tak jak uprościła to dla nas całkowita liczba zanurzeń w poprzednim zadaniu).

Jako przykład rozważmy problem ładowania maszyny (wspominaliśmy już o tym w poprzednim rozdziale): istnieje pewien zbiór obiektów P 1, P 2,..., P n (każdy w jednym egzemplarzu); znane są ich wagi q 1 , q 2 , ..., q rz i koszt od 1, z 2, ..., z n. Nośność maszyny wynosi Q. Pytanie brzmi, które przedmioty należy zabrać do samochodu, aby ich całkowity koszt (wraz z wagą całkowitą Q) było maksimum?

Problem badań operacyjnych

Wprowadzenie……………………………………………………………………………...3

1. Podstawowe pojęcia i definicje badań operacyjnych…..……..5

2. Ogólne sformułowanie problemu badań operacyjnych………..…………6

Zakończenie………………………………………………………………….....13

Literatura………………………………………………………………………………......14

Wstęp

Badania operacyjne - dyscyplina naukowa zajmująca się opracowywaniem i praktycznym zastosowaniem metod najbardziej efektywnego zarządzania różnymi systemami organizacyjnymi.

Zarządzanie dowolnym systemem jest realizowane jako proces podlegający pewnym prawom. Ich wiedza pozwala określić warunki niezbędne i wystarczające do realizacji tego procesu. W tym celu należy określić ilościowo i zmierzyć wszystkie parametry charakteryzujące proces i warunki zewnętrzne. Dlatego celem badań operacyjnych jest ilościowe uzasadnienie podjętych decyzji na temat organizacji zarządzania.

Przy rozwiązywaniu konkretnego problemu zarządczego zastosowanie metod badań operacyjnych polega na:

Budowa modeli ekonomicznych i matematycznych problemów decyzyjnych w sytuacjach złożonych lub w warunkach niepewności;

Badanie zależności, które następnie determinują podejmowanie decyzji i ustalanie kryteriów wydajności, które pozwalają ocenić przewagę określonego sposobu działania.

Przykładowymi zadaniami badań operacyjnych odzwierciedlającymi ich specyfikę są następujące zadania.

Zadanie 1. W celu zapewnienia wysokiej jakości wytwarzanych wyrobów w zakładzie zorganizowany jest system kontroli wyrywkowej. Należy wybrać takie formy jej organizacji – np. przypisać wielkości partii kontrolnych, wskazać kolejność czynności kontrolnych, ustalić zasady odrzutów – aby zapewnić wymaganą jakość przy minimalnych kosztach.

Zadanie 2. W celu sprzedaży określonej partii towarów sezonowych tworzona jest sieć tymczasowych punktów sprzedaży detalicznej. Należy dobrać parametry sieci – liczbę punktów, ich lokalizację, liczbę pracowników – tak, aby zapewnić maksymalną efektywność ekonomiczną sprzedaży.

Zadanie 3. Należy w określonym terminie przeprowadzić masowe badania lekarskie pewnej grupy ludności w celu wykrycia określonych chorób. Do badania przydzielono materiały, sprzęt i personel. Należy opracować taki plan badań – ustalić liczbę placówek medycznych, ich lokalizację, rodzaj i liczbę badań, aby móc zidentyfikować jak największy odsetek chorych.

Należy także zwrócić uwagę na problemy dotyczące wykorzystania zasobów, mieszanek, wykorzystania wydajności, materiałów do cięcia, problemu transportu itp., w przypadku których konieczne jest znalezienie rozwiązania, gdy niektóre kryterium wydajności(na przykład zysk, przychód, koszty zasobów itp.) przyjmuje wartość maksymalną lub minimalną.

Podane zadania dotyczą różnych obszarów praktyki, jednak mają wspólne cechy: w każdym przypadku mówimy o niektórych kontrolowane zdarzenie (działanie), dążenie do pewnego cel. W zadaniu 1 - jest to organizacja kontroli pobierania próbek w celu zapewnienia jakości produktów; w zadaniu 2 - organizowanie tymczasowych punktów sprzedaży detalicznej na potrzeby wyprzedaży sezonowych; w zadaniu 3 - masowe badanie lekarskie w celu ustalenia odsetka przypadków.

Każde zadanie zawiera pewne elementy warunki zorganizowania tego wydarzenia, w ramach którego należy się odbyć rozwiązanie - tak, aby wydarzenie przyniosło jakąś korzyść. Warunkiem przeprowadzenia operacji w każdym zadaniu są dostępne nam środki, czas, sprzęt, technologia, a rozwiązaniem w zadaniu 1 jest wybór formy kontroli – wielkość partii kontrolnych, zasady odrzutów; w zadaniu 2 – przy wyborze liczby punktów rozmieszczenia i liczby personelu; w zadaniu 3 – w wyborze liczby stanowisk lekarskich, rodzaju i liczby badań.

1. Podstawowe pojęcia i definicje badań operacyjnych

Operacja- każde kontrolowane wydarzenie mające na celu osiągnięcie celu. Wynik operacji zależy od sposobu jej wykonania, organizacji, w przeciwnym razie - od wyboru określonych parametrów.

Nazywa się dowolny konkretny wybór parametrów decyzja.

Optymalny rozważyć te rozwiązania, które z tego czy innego powodu są lepsze od innych. Dlatego główne zadanie badania operacyjne mają charakter wstępny ilościowy uzasadnienie optymalnych rozwiązań.

Uwaga 1. Należy zwrócić uwagę na sformułowanie problemu: podejmować decyzje wykracza poza zakres badań operacyjnych i leży w gestii odpowiedzialnej osoby lub grupy osób, która może uwzględnić inne względy niż te, które są matematycznie uzasadnione.

Uwaga 2. Jeśli w niektórych problemach badań operacyjnych rozwiązaniem optymalnym jest takie, w którym przyjmuje się jakieś kryterium efektywności

wartość maksymalna lub minimalna, to w innych zadaniach nie jest to wcale konieczne. Zatem w zadaniu 2 można przyjąć taką optymalną liczbę punktów sprzedaży detalicznej i personelu w nich znajdującego się, aby średni czas obsługi klienta nie przekraczał np. 5 minut, a długość kolejki średnio w dowolnym momencie nie przekraczała niż 3 osoby.

Aby zastosować ilościowe metody badawcze, konieczne jest budowanie model matematyczny operacji. Podczas konstruowania modelu operacja jest z reguły uproszczona, schematyczna, a schemat operacji jest opisywany za pomocą jednego lub drugiego aparatu matematycznego.

Model operacje - jest to dość dokładny opis operacji za pomocą aparatu matematycznego (różnego rodzaju funkcje, równania, układy równań i nierówności itp.). Stworzenie modelu operacji wymaga zrozumienia istoty opisywanego zjawiska oraz znajomości aparatu matematycznego.

Wydajność działania - stopień jego przystosowania do zadania wyraża się ilościowo w postaci kryterium efektywności – funkcji celu. Przykładowo w problemie wykorzystania zasobów kryterium efektywności jest zysk ze sprzedaży wytworzonych produktów, który należy maksymalizować, w problemie transportowym – całkowite koszty transportu towarów od dostawców do konsumentów, które należy minimalizować . Wybór kryterium efektywności decyduje o wartości praktycznej badania. (Nieprawidłowo wybrane kryterium może być szkodliwe, gdyż działania organizowane pod kątem takiego kryterium efektywności prowadzą czasami do nieuzasadnionych kosztów.)

2. Ogólne sformułowanie problemu badań operacyjnych

Ważne jest zrozumienie metodologii konstruowania modeli problemów badań operacyjnych. Wszystkie czynniki zawarte w opisie operacji można podzielić na dwie grupy:

czynniki stałe(warunki pracy), na które nie mamy wpływu. Oznaczmy je przez α1, α2, ... ;

czynniki zależne(elementy rozwiązania) X 1, x2, ...; które w pewnych granicach możemy wybrać według własnego uznania.

Na przykład w problemie wykorzystania zasobów czynnikami stałymi powinny być rezerwy zasobów każdego rodzaju, macierz produkcji, której elementy określają zużycie surowców każdego rodzaju na jednostkę produkcji każdego typu. Elementy rozwiązania – plan produkcji dla każdego rodzaju produktu.

Kryterium wydajności wyrażone przez pewną funkcję zwaną cel, zależy od czynników obu grup, a więc funkcji celu Z można zapisać w postaci

Z= F (x1, x2, ..., α1, α2, ...)

Wszystkie modele badań operacyjnych można sklasyfikować w zależności od charakteru i właściwości operacji, charakteru rozwiązywanych problemów oraz cech stosowanych metod matematycznych.

Należy zauważyć przede wszystkim duży klasa modeli optymalizacyjnych. Takie problemy pojawiają się przy próbach optymalizacji planowania i zarządzania złożonymi systemami, przede wszystkim systemami gospodarczymi. Problem optymalizacji można sformułować w ogólnej postaci: znajdź zmienne x1, x2, ..., x N , spełniający układ nierówności (równania)

G I (x1, x2, x3,..., X N )<= B I , ja = 1, 2,..., N (0.1)

I obrócenie funkcji celu do maksimum (lub minimum), tj.

Z= F (x1, x2, ..., X N ) - M aha (m W ) (0.2)

(Warunki nieujemności zmiennych, jeśli takie istnieją, są zawarte w ograniczeniach (0.1))

Rozważmy inny problem typowy dla badań operacyjnych - klasyczny problem konsumpcji, ogromne znaczenie w analizie ekonomicznej.

Niech będzie P rodzaje towarów i usług, których ilości (w jednostkach naturalnych) x1, x2, ..., X N po odpowiednich cenach P 1, P 2, ..., P N dla jednostki. Całkowity koszt tych towarów i usług wynosi ∑ P I X I .

Poziom konsumpcji Z można wyrazić za pomocą jakiejś funkcji Z= F (x1, x2, ..., X N ) ,zwany funkcja użyteczności. Konieczne jest znalezienie takiego zestawu towarów i usług x1, x2, ..., X N dany wysokość dochodu I, Do zapewnić maksymalny poziom zużycia, te.

Z= F (x1, x2, ..., X N ) - M Oh (0.3)

jeśli się uwzględni

∑ P I X I <= I (0.4)

X I >= 0 ( I = 1, 2,..., N ) (0.5)

Rozwiązania tego problemu zależne od cen P 1, P 2, ..., P N i wysokość dochodu I, są nazywane funkcje popytu.

Jest oczywiste, że rozpatrywany problem zużycia (0,3)-(0,5), jak i wiele innych, jest szczególnym przypadkiem ogólnego problemu (0,1)-(0,2) sformułowanego powyżej w celu wyznaczenia ekstremum funkcji P zmiennych pod pewnymi ograniczeniami, tj. zadanie dla warunkowy ekstremum.

W przypadkach, gdy funkcje F I G I, w zadaniu (0.1)-(0.2) są co najmniej dwukrotnie różniczkowalne, możemy skorzystać klasyczny metody optymalizacyjne. Jednakże zastosowanie tych metod w badaniach operacyjnych jest bardzo ograniczone, gdyż zadanie wyznaczenia ekstremum warunkowego funkcji i zmiennych jest bardzo trudne technicznie: metoda pozwala na wyznaczenie ekstremum lokalnego, a ze względu na wielowymiarowość funkcja, wyznaczenie jej wartości maksymalnej (lub minimalnej) (ekstremum globalnego) może okazać się bardzo pracochłonne - zwłaszcza, że ​​ekstremum to jest możliwe na granicy obszaru rozwiązania. Klasyczne metody w ogóle nie działają, jeśli zbiór prawidłowych wartości argumentów jest dyskretny lub funkcja Z podano w tabeli. W takich przypadkach do rozwiązania problemu stosuje się metody (0,1)-(0,2). programowanie matematyczne.

Jeżeli kryterium efektywności Z= F (x1, x2, ..., X N ) (0,2) reprezentuje funkcję liniową i funkcje G I (x1, x2, x3,..., X N ) w układzie więzów (0,1) są również liniowe, wtedy taki problem jest problemem Programowanie liniowe. Jeśli na podstawie treści jego rozwiązania muszą być liczbami całkowitymi, to jest to problem Całkowite programowanie liniowe. Jeśli kryterium efektywności i (lub) układ ograniczeń są określone przez funkcje nieliniowe, to mamy problem programowanie nieliniowe. W szczególności, jeśli wskazane funkcje mają właściwości wypukłości, to powstały problem jest problemem programowanie wypukłe.

Jeśli w zadaniu programowania matematycznego występuje zmienna czasowa i kryterium efektywności (0,2) wyraża się nie wprost jako funkcję zmiennych, ale pośrednio – poprzez równania opisujące przebieg operacji w czasie, to taki problem jest problemem Programowanie dynamiczne.

Jeżeli kryterium efektywności (0,2) i system ograniczeń (0,1) są określone przez funkcje postaci Z*( X 1^α 1 )*( X 2^α 2 )...( X N ^α N ) , to mamy problem programowanie geometryczne. Jeśli funkcje F i/lub G I w wyrażeniach (0.2) i (0.1) zależą od parametrów, wówczas otrzymujemy problem programowanie parametryczne, jeśli te funkcje mają charakter losowy, zadanie programowanie stochastyczne. Jeśli znalezienie dokładnego optymalnego algorytmu nie jest możliwe ze względu na zbyt dużą liczbę opcji rozwiązania, należy zastosować metody heurystyczny programowanie, co pozwala znacznie zmniejszyć liczbę opcji, na które patrzysz i znaleźć, jeśli nie optymalne, to w miarę dobre rozwiązanie, satysfakcjonujące z praktycznego punktu widzenia.

Spośród wymienionych metod programowania matematycznego najpowszechniejszym i najbardziej rozwiniętym jest programowanie liniowe. Obejmuje szeroki zakres zadań z zakresu badań operacyjnych.

Zadania związane z planowaniem i zarządzaniem siecią rozważyć związek pomiędzy datami zakończenia dużego kompleksu operacji (prac) a czasem rozpoczęcia wszystkich operacji kompleksu. Zadania te polegają na znalezieniu minimalnego czasu trwania zestawu operacji, optymalnego stosunku wartości kosztów i terminu ich realizacji.

Problemy z kolejką poświęcone są badaniu i analizie systemów usług z kolejkami wniosków lub wymagań i polegają na określeniu wskaźników wydajności systemów, ich optymalnych cech, na przykład określenia liczby kanałów obsługi, czasu obsługi itp.

Zadania związane z zarządzaniem zapasami polegają na znalezieniu optymalnych wartości poziomu zapasów (punktu zamówienia) i wielkości zamówienia. Specyfiką takich zadań jest to, że wraz ze wzrostem poziomu zapasów z jednej strony rosną koszty ich przechowywania, ale z drugiej strony zmniejszają się straty wynikające z ewentualnego niedoboru magazynowanego produktu.

Problemy z alokacją zasobów powstają podczas pewnego zestawu operacji (prac), które należy wykonać przy ograniczonych dostępnych zasobach i konieczne jest znalezienie optymalnego podziału zasobów pomiędzy operacjami lub składu operacji.

Zadania związane z naprawą i wymianą sprzętu są istotne ze względu na zużycie sprzętu i konieczność jego wymiany w miarę upływu czasu. Zadania sprowadzają się do ustalenia optymalnego terminu, liczby napraw zapobiegawczych i przeglądów, a także momentu wymiany sprzętu na zmodernizowany.

Planowanie (harmonogramowanie) zadań polegają na określeniu optymalnej sekwencji operacji (na przykład obróbki części) na różnych typach sprzętu.

Zadania planowania i rozmieszczania polegają na ustaleniu optymalnej liczby i lokalizacji nowych obiektów, z uwzględnieniem ich interakcji z obiektami istniejącymi oraz między sobą.

Problemy z wyborem trasy Lub sieć problemów najczęściej spotykanych w badaniu różnych problemów systemów transportowych i komunikacyjnych i polega na określeniu najbardziej ekonomicznych tras.

Wśród modeli badań operacyjnych, badane są modele podejmowania optymalnych decyzji w sytuacjach konfliktowych teoria gry. Sytuacje konfliktowe, w których zderzają się interesy dwóch (lub więcej) stron, realizujących różne cele, obejmują szereg sytuacji z zakresu ekonomii, prawa, spraw wojskowych itp. W problematyce teorii gier konieczne jest opracowanie rekomendacji dla rozsądne zachowania uczestników konfliktu, w celu ustalenia ich optymalnych strategii.

W praktyce w większości przypadków powodzenie operacji ocenia się nie na podstawie jednego, ale kilku kryteriów jednocześnie, z których jedno należy maksymalizować, a pozostałe minimalizować. Aparat matematyczny może być również przydatny w przypadkach wielokryterialne problemy badawcze operacji, przynajmniej pomóc w odrzuceniu oczywiście nieudanych rozwiązań.

Aby wybrać funkcję celu spośród różnych kryteriów, w tym także sprzecznych ze sobą (na przykład zysków i kosztów), konieczne jest ustalenie priorytet kryteria. Oznaczmy F 1 (x), f 2 (X), ..., F N (X)(Tutaj X - argument warunkowy). Ułóżmy je w kolejności malejącej według priorytetu. W zależności od pewnych warunków istnieją zasadniczo dwie opcje:

Kryterium wybiera się jako funkcję celu F 1 (X), mający najwyższy priorytet;

Rozważana jest kombinacja

F ( X ) = ω 1 * F 1 ( X ) + ω 2 * F 2 ( X ) + …+ ω N * F N ( X ) , (0.6)

Gdzie ω 1 , ω 2 , … ω N- niektóre współczynniki (wagi).

Ogrom F (X) Jako funkcję celu wybiera się , która w pewnym stopniu uwzględnia wszystkie kryteria.

W warunkach pewności ω I- liczby, F I (X)- Funkcje. W warunkach niepewności F I (X) może okazać się losowe i zamiast tego F I (X) za funkcję celu należy uznać matematyczne oczekiwanie sumy (0,6).

Próba sprowadzenia problemu wielokryterialnego do problemu z jednym kryterium efektywności (funkcją celu) w większości przypadków nie daje zadowalających rezultatów. Inne podejście polega na odrzuceniu („wyselekcjonowaniu”) ze zbioru rozwiązań dopuszczalnych, rozwiązań oczywiście nieudanych, gorszych od innych pod względem wszystkie kryteria. W wyniku tego zabiegu powstaje tzw skuteczny(Lub " Pareto”) rozwiązań, których zestaw jest zwykle znacznie mniejszy od pierwotnego. I ostateczny wybór rozwiązania „kompromisowego” (nie według wszystkich kryteriów optymalnego, które z reguły nie istnieje, ale do przyjęcia według tych kryteriów) pozostaje przy osobie – decydencie.

Wniosek

Rosyjscy naukowcy L.V. wnieśli ogromny wkład w stworzenie nowoczesnego aparatu matematycznego i rozwój wielu dziedzin badań operacyjnych. Kantorowicz, N.P. Buslenko, E.S. Ventzel, N.N. Worobiow, N.N. Moiseev, D.B. Judina i wielu innych. Na szczególną uwagę zasługuje rola akademika L.V. Kantorowicz, który w 1939 r., rozpoczynając planowanie funkcjonowania zakładów wytwórni sklejki, rozwiązał kilka problemów: o najlepszym załadunku sprzętu, o cięciu materiałów przy minimalnych stratach, o podziale ładunku na kilka rodzajów transportu itp. L.V. Kantorowicz sformułował nową klasę problemów ekstremalnych warunkowo i zaproponował uniwersalną metodę ich rozwiązywania, kładąc podwaliny pod nowy kierunek w matematyce stosowanej - programowanie liniowe.

Znaczący wkład w powstanie i rozwój badań operacyjnych wnieśli zagraniczni naukowcy R. Akof, R. Bellman, G. Danzig, G. Kuhn, J. Neumann, T. Saaty, R. Churchman, A. Kofman i inni.

Metody badań operacyjnych, jak wszystkie metody matematyczne, zawsze w pewnym stopniu upraszczają i zgrubiają problem, czasami odzwierciedlając procesy nieliniowe za pomocą modeli liniowych, układy stochastyczne za pomocą deterministycznych, procesy dynamiczne za pomocą modeli statycznych itp. Życie jest bogatsze niż jakikolwiek schemat. Nie należy zatem przeceniać znaczenia metod ilościowych w badaniach operacyjnych ani go minimalizować poprzez przytaczanie przykładów nieudanych rozwiązań. Warto w tym miejscu przytoczyć humorystycznie paradoksalną definicję badań operacyjnych, zaproponowaną przez jednego z ich twórców, T. Saaty’ego, jako „sztukę udzielania złych odpowiedzi na te praktyczne pytania, na które innymi metodami można odpowiedzieć jeszcze gorzej”.

Literatura

1. Kremer N. Sh., Putko B. A., Trishin I. M., Fridman M. N. Badania operacji w ekonomii: Podręcznik dla uniwersytetów - M.: UNITI, 2002.

2. Ventzel E.S. Badania operacyjne. Cele, zasady, metodologia - M.: Nauka, 1980.

3. Gorelik V.A., Ushakov I.A. Badania operacyjne. - M.: Inżynieria mechaniczna, 1986.

Operacja Nazywa się każde wydarzenie (system działań) połączone jednym planem i mające na celu osiągnięcie określonego celu. Zawsze jest operacja kontrolowane wydarzenie, tj. Można zdecydować, w jaki sposób wybrać pewne parametry charakteryzujące jego organizację. Parametry te nazywane są zmienne kontrolne.

Dowolny konkretny wybór takich zmiennych nazywa się decyzja. Decyzje mogą być skuteczne i nieudane, rozsądne i nierozsądne. Optymalny wymienić takie rozwiązania, które według jednych kryteriów są lepsze od innych.

Celem badań operacyjnych jest wstępne ilościowe uzasadnienie rozwiązań optymalnych, których może być więcej niż jedno. Ostateczny wybór decyzji wykracza poza zakres badań operacyjnych i dokonywany jest za pomocą tzw. teorii decyzji.

Każde zadanie badań operacyjnych ma wstępne warunki „dyscyplinujące”, tj. takie dane początkowe, które są ustalone od samego początku i nie można ich naruszyć. Razem tworzą tzw. zbiór możliwych rozwiązań.

Aby porównać różne rozwiązania pod względem efektywności, potrzebne jest kryterium ilościowe tzw wskaźnik wydajności(lub funkcja celu). Wskaźnik ten wybiera się tak, aby odzwierciedlał docelowy kierunek operacji.

Często operacji towarzyszy działanie czynników losowych. Wówczas za wskaźnik efektywności przyjmuje się nie samą wartość, którą chcielibyśmy zoptymalizować, ale jej wartość średnią (lub oczekiwanie matematyczne).

Czasem taki cel realizuje operacja, której towarzyszą czynniki losowe A, które można albo osiągnąć w całości, albo w ogóle nie osiągnąć (jak „tak-nie”). Następnie jako wskaźnik efektywności wybiera się prawdopodobieństwo osiągnięcia tego celu P(A). (Jeśli P(A) = 0 lub 1, wówczas dochodzimy do problemu „czarnej skrzynki” znanego w cybernetyce.)

Wybór niewłaściwego wskaźnika wydajności jest bardzo niebezpieczny. Działania zorganizowane według nieudanie wybranego kryterium mogą prowadzić do nieuzasadnionych kosztów i strat. (Na przykład „wał” jako główne kryterium oceny działalności gospodarczej przedsiębiorstwa.)

1.3. Ogólne sformułowanie problemu badań operacyjnych

Problemy badań operacyjnych można podzielić na dwie kategorie: a) do przodu i b) do tyłu.

Zadania bezpośrednie odpowiedzieć na pytanie: jaki będzie wskaźnik efektywności? Z, jeśli w danych warunkach y  Y zostanie podjęta jakaś decyzja X  X. Aby rozwiązać taki problem, konstruuje się model matematyczny pozwalający wyrazić wskaźnik efektywności poprzez dane warunki i rozwiązanie, a mianowicie:

Gdzie
określone czynniki (dane wstępne),

zmienne sterujące (decyzja),

Z– wskaźnik efektywności (funkcja celu),

F– zależność funkcjonalna pomiędzy zmiennymi.

Zależność ta jest różnie wyrażana w różnych modelach. Zależność pomiędzy I zwykle wyrażane w kategoriach ograniczeń

Jeśli rodzaj uzależnienia F jest znany, to wskaźnik Z znajduje się przez bezpośrednie podstawienie I w tę funkcjonalność.

Problemy odwrotne odpowiedzieć na pytanie: jak w tych warunkach wybierz rozwiązanie
tak aby wskaźnik wydajności Z ustawiony na maksimum (minimum). Problem ten nazywany jest problemem optymalizacji rozwiązania.

Niech problem bezpośredni zostanie rozwiązany, tj. określono model działania i typ zależności F słynny. Następnie problem odwrotny (tj. Problem optymalizacji) można sformułować w następujący sposób.

Trzeba znaleźć taka decyzja
przy którym wskaźnik efektywności Z = optować:

Ta formuła brzmi następująco: Z istnieje wartość optymalna
przejął wszystkie rozwiązania zawarte w zbiorze możliwych rozwiązań X.

Metoda znajdowania ekstremum wskaźnika efektywności Z i związane z nim optymalne rozwiązanie należy zawsze wybierać w oparciu o cechy funkcji F oraz rodzaj ograniczeń nałożonych na rozwiązanie. (Na przykład klasyczny problem programowania liniowego.)

Badania operacyjne– nauka zajmująca się rozwojem i praktycznym zastosowaniem matematycznych, ilościowych metod uzasadniania decyzji we wszystkich obszarach celowej działalności człowieka (efektywne zarządzanie organizacją).

Ogólne cechy badań operacyjnych

Każde zadanie dotyczy jakiegoś zdarzenia, które ma określony cel.

Określone są pewne warunki charakteryzujące sytuację (w tym środki, którymi możemy dysponować).

W tych warunkach należy podjąć taką decyzję, aby planowana impreza była w pewnym sensie jak najbardziej opłacalna.

Cechy badań operacyjnych

Systemowe podejście do analizy postawionego problemu oznacza, że ​​dany problem należy rozpatrywać z punktu widzenia jego wpływu na kryterium funkcjonowania całego systemu.

Największy efekt można osiągnąć jedynie przy ciągłych badaniach, zapewniających ciągłość w przejściu od jednego problemu do drugiego, powstającego w trakcie rozwiązywania poprzedniego.

Chociaż celem badań operacyjnych jest znalezienie optymalnego rozwiązania, to ze względu na złożoność obliczeń problemów kombinatorycznych ograniczają się one do znalezienia „wystarczająco dobrego” rozwiązania.

Badania operacyjne prowadzone są kompleksowo, w wielu obszarach. W celu przeprowadzenia badania tworzone są grupy operacyjne:

Podstawowe pojęcia dotyczące badań operacyjnych

DZIAŁANIE to dowolne kontrolowane (tj. zależne od doboru parametrów) zdarzenie, połączone jednym planem i mające na celu osiągnięcie jakiegoś celu.

DECYZJA – dowolny, konkretny wybór parametrów, które zależą od nas.

OPTYMALNE ROZWIĄZANIA – decyzje oparte na pewnych cechach, które są preferowane od innych.

CELEM BADAŃ OPERACYJNYCH jest wstępne ilościowe uzasadnienie optymalnych rozwiązań.

ELEMENTY ROZWIĄZANIA – parametry, których kombinacja tworzy rozwiązanie.

WSKAŹNIK EFEKTYWNOŚCI (FUNKCJA DOCELOWA) to kryterium ilościowe, które pozwala porównać różne rozwiązania pod względem efektywności i odzwierciedla docelową orientację działania (W=>max lub W=>min).

Najlepsze rozwiązanie to takie, które w maksymalnym stopniu przyczynia się do osiągnięcia celu.

Pojęcie modelu matematycznego operacji

Schematyczny, uproszczony opis operacji za pomocą tego lub innego aparatu matematycznego, odzwierciedlający najważniejsze cechy operacji, wszystkie istotne czynniki, od których głównie zależy powodzenie operacji.

Problemy badawcze operacji bezpośrednich i odwrotnych

PROBLEMY BEZPOŚREDNIE odpowiadają na pytanie, co się stanie, jeśli w danych warunkach podejmiemy jakąś decyzję x X, tj. jaki będzie wskaźnik efektywności W (lub liczba wskaźników)?

Aby rozwiązać ten problem, zbudowana jest mata. model, który pozwala wyrazić jeden lub więcej wskaźników wydajności poprzez określone warunki i elementy rozwiązania.

PROBLEMY ODWROTNE odpowiadają na pytanie, jak wybrać rozwiązanie x, aby wskaźnik efektywności W stał się maksymalny (minimalny).

Te zadania są trudniejsze. Można je rozwiązać, po prostu przeszukując rozwiązania bezpośrednich problemów.

Kiedy jednak liczba możliwości rozwiązania jest duża, stosuje się metody poszukiwania ukierunkowanego, w których rozwiązanie optymalne znajduje się poprzez wykonywanie kolejnych „prób” lub przybliżeń, z których każda przybliża nas do pożądanego optymalnego.