Rozdział 1. Przedmiot i zadania badań operacyjnych.

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

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

§ 3. Modele matematyczne operacji.

Rozdział 2. Różnorodność zadań w badaniach operacyjnych i podejścia do ich rozwiązywania.

§ 4. Bezpośrednie i odwrotne problemy badań operacyjnych. Zadania deterministyczne.

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

§ 6. Wielokryterialne problemy badań operacyjnych. „Podejście systemowe”.

Rozdział 3. Programowanie liniowe.

§ 7. Zagadnienia programowania liniowego.

§ 8. Główny problem programowania liniowego.

§ 9. Istnienie rozwiązania 03LP i sposoby jego poszukiwania.

§ 10. Problem transportu programowania liniowego.

§ 11. Zagadnienia programowania całkowitoliczbowego. 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 postaci ogólnej. Zasada optymalności.

Rozdział 5 Losowe procesy Markowa.

§ 15. Pojęcie procesu Markowa.

§ 16. Przebieg zdarzeń.

§ 17. Równania Kołmogorowa dla prawdopodobieństw stanów. Prawdopodobieństwa końcowe stanów.

Rozdział 6

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

§ 19. Schemat śmierci i reprodukcji. Mała formuła.

§ 20. Najprostsze systemy kolejkowe i ich charakterystyka.

§ 21. Bardziej skomplikowane problemy teorii kolejek.

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

§ 22. Idea, cel i zakres metody.

§ 23. Partia i formy jej organizacji.

§ 24. Wyznaczanie charakterystyk stacjonarnego procesu losowego z jednej implementacji.

Rozdział 8

§ 25. Przedmiot i problemy 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 zdarzenie (system działań) połączone jedną ideą i mające na celu osiągnięcie jakiegoś celu (wszystkie zdarzenia omówione w paragrafach 1–8 poprzedniego akapitu są „operacjami”).

Operacja jest zawsze zdarzeniem kontrolowanym, to znaczy od nas zależy, w jaki sposób dobierzemy niektóre parametry charakteryzujące jej organizację. „Organizacja” jest tutaj rozumiana w szerokim tego słowa znaczeniu, w tym zespół środków technicznych wykorzystywanych w działaniu.

Dowolny określony wybór parametrów zależnych od nas nazywamy rozwiązaniem. Decyzje mogą być udane i nieudane, rozsądne i nierozsądne. Rozwiązania nazywane są optymalnymi, jeśli z tego czy innego powodu są preferowane w stosunku do innych. 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 – zidentyfikować obszar praktycznie równoważnych rozwiązań optymalnych (rozsądnych), w ramach których można dokonać ostatecznego wyboru.

Należy zauważyć, że samo podejmowanie decyzji wykracza poza zakres badania operacji i leży w kompetencjach osoby odpowiedzialnej, częściej – grupy osób, które otrzymały prawo do ostatecznego wyboru i które są odpowiedzialne za ten wybór. Dokonując wyboru, mogą wziąć pod uwagę, obok zaleceń wynikających z obliczeń matematycznych, szereg przesłanek (o charakterze ilościowym i jakościowym), które nie zostały uwzględnione w tym obliczeniu.

Nieodzowna obecność osoby (jako ostatecznego organu decyzyjnego) nie jest anulowana nawet w obecności w pełni zautomatyzowanego systemu sterowania, 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. Wraz z rozwojem automatów sterujących funkcje człowieka nie są anulowane, ale po prostu przenoszone z jednego, elementarnego poziomu na inny, wyższy. Ponadto szereg zautomatyzowanych systemów sterowania zapewnia aktywną interwencję człowieka podczas kontrolowanego procesu.

Te parametry, których całość tworzy rozwiązanie, nazywane są elementami rozwiązania. Jako elementy rozwiązania mogą pojawić się różne liczby, wektory, funkcje, znaki fizyczne itp. Na przykład, jeśli zostanie sporządzony plan transportu jednorodnych towarów z punktów wyjścia A 1, A 2, ..., A m do miejsc docelowych W 1,В 2 , ..., В n , wtedy elementami rozwiązania będą liczby x ij , pokazujący, ile ładunku zostanie wysłane z pierwszego punktu wyjścia ja V J-ty cel podróży w j. Zestaw liczb X 11 , X 12, …, X 1 n , …, X m 1 , X m 2 , …, xmn 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 zweryfikować, próbując samodzielnie wybrać i „nazwać po nazwie” elementy rozwiązania w przykładach 1–8 z poprzedniego akapitu. Dla uproszczenia cały zestaw elementów rozwiązania będziemy oznaczać jedną literą X i powiedz „decyzja X".

Oprócz elementów rozwiązania, którymi w pewnym stopniu możemy dysponować, w każdym zadaniu badań operacyjnych podane są również warunki „dyscyplinujące”, które są ustalone od samego początku i nie można ich naruszyć (np. maszyny, wielkość planowanego zadania;

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

Oznaczmy ten zbiór ponownie jedną literą X, ale fakt, że rozwiązanie X należy do tego zbioru, zapiszemy to jako wzór: X X(czytaj: pierwiastek X w zestawie X).

Chodzi o to, że w mnogości możliwych rozwiązań X podkreślić te rozwiązania X(czasami – jedno, a częściej – cały wachlarz rozwiązań), które z takiego czy innego punktu widzenia są bardziej efektywne (skuteczniejsze, bardziej preferowane) niż inne. Aby porównać różne rozwiązania pod względem efektywności, trzeba mieć jakieś kryterium ilościowe, tzw. wskaźnik efektywności (często nazywany jest „funkcją celu”). Wskaźnik ten jest tak dobrany, aby odzwierciedlał ukierunkowanie operacji na cel. Za „najlepsze” rozwiązanie zostanie uznane to, które w maksymalnym stopniu przyczyni się do osiągnięcia celu. Aby wybrać miarę wydajności „powiedz po imieniu”. 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 odwróci wskaźnik efektywności W maksimum (lub minimum). Na przykład chciałbym zmaksymalizować dochód z operacji; jeśli koszty są wskaźnikiem efektywności, pożądana jest ich minimalizacja. Jeśli pożądane jest zmaksymalizowanie wskaźnika wydajności, zapiszemy to w formularzu W => max, a jeśli zminimalizowane - W => min.

Bardzo często operacji towarzyszy działanie czynników losowych („kaprysy” pogody, wahania podaży i popytu, awarie urządzeń technicznych itp.). W takich przypadkach zwykle nie sama wartość, którą chcielibyśmy zmaksymalizować (zminimalizować), ale jej wartość średnia (oczekiwanie matematyczne) jest traktowana jako wskaźnik efektywności.

W niektórych przypadkach zdarza się, że operacja, której towarzyszą czynniki losowe, zmierza do jakiegoś bardzo konkretnego celu. A, które można osiągnąć tylko całkowicie lub wcale (schemat „tak-nie”) i nie interesują nas żadne wyniki pośrednie. Następnie jako wskaźnik efektywności wybiera się prawdopodobieństwo osiągnięcia tego celu. R(A). Na przykład, jeśli jakiś obiekt jest ostrzelany z warunkiem niezbędnym do jego zniszczenia, to wskaźnikiem skuteczności będzie prawdopodobieństwo zniszczenia obiektu.

Zły wybór wskaźnika wydajności jest bardzo niebezpieczny. Operacje organizowane z punktu widzenia nietrafionego kryterium mogą prowadzić do nieuzasadnionych kosztów i strat (przypomnijmy np. osławioną „val” jako główne kryterium oceny działalności gospodarczej przedsiębiorstw).

Aby zilustrować zasady wyboru wskaźnika efektywności, wróćmy ponownie do przykładów 1 - 8 z § 1, wybierzmy dla każdego z nich naturalny wskaźnik efektywności i wskażmy, czy wymagana jest jego maksymalizacja, czy minimalizacja. Przyglądając się przykładom należy mieć na uwadze, że nie wszystkie mają możliwość wyboru wskaźnika efektywności jednoznacznie podyktowanego słownym opisem zadania, przez co mogą występować różnice między czytelnikiem a autorem w tej kwestii.

1. Plan zaopatrzenia przedsiębiorstw. Zadaniem operacji jest zapewnienie dostaw surowców przy minimalnych kosztach transportu. Wskaźnik wydajności R- całkowity koszt transportu surowców na jednostkę czasu, na przykład miesiąc ( R => min.).

2. Budowa odcinka autostrady. Konieczne jest zaplanowanie budowy w taki sposób, aby zakończyć ją jak najszybciej. Naturalnym wskaźnikiem efektywności byłby czas zakończenia budowy, gdyby nie był on powiązany z czynnikami losowymi (awarie sprzętu, opóźnienia w wykonaniu poszczególnych robót). Dlatego jako wskaźnik wydajności możesz wybrać średni oczekiwany czas T zakończenie budowy (T => min.).

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

4. Odśnieżanie dróg. Jest to najkorzystniejszy ekonomicznie plan ochrony przed śniegiem, dlatego jako wskaźnik wydajności można wybrać średnie koszty na jednostkę czasu (na przykład na rok) R na utrzymanie i eksploatację dróg, w tym koszty związane zarówno z budową urządzeń ochronnych, jak i odśnieżaniem i opóźnieniami w ruchu (R => min.).

5. Nalot na okręty podwodne. Ponieważ rajd ma bardzo konkretny cel A - zniszczenie łodzi, to jako wskaźnik efektywności należy wybrać prawdopodobieństwo R(A), że łódź zostanie zniszczona.

6. Selektywna kontrola produktów. Naturalną miarą wydajności sugerowaną przez opis problemu jest średni oczekiwany koszt. R do kontroli w jednostce czasu, pod warunkiem, że system kontroli zapewnia określony poziom jakości, np. średni procent odrzutów nie jest wyższy niż określony ( R=> min).

7. Badanie lekarskie. Jako wskaźnik efektywności możesz wybrać średni procent (udział) Q pacjentów i nosicieli infekcji, których zidentyfikowano (P=> sprawdzać).

8. Serwis biblioteczny. W sformułowaniu problemu celowo dopuszczono pewną niejasność:

nie jest jasne, co należy rozumieć przez „najlepszą obsługę klienta” lub „zaspokajanie jego potrzeb w możliwie największym stopniu”. Jeśli jakość usługi ocenia się na podstawie czasu, w jakim abonent, który zamówił książkę, czeka na jej otrzymanie, to średni czas można uznać za wskaźnik wydajności. T oczekiwań wobec książki czytelnika, który się o nią ubiegał ( T=> min). Możesz podejść do zagadnienia z nieco innej perspektywy, wybierając średnią liczbę jako wskaźnik efektywności. M książek wydanych w jednostce czasu (M => maks.).

Rozważane przykłady są specjalnie dobrane tak, aby były na tyle proste, że wybór wskaźnika efektywności jest stosunkowo łatwy i jest bezpośrednio podyktowany słownym sformułowaniem zadania, jego (prawie zawsze) jednoznacznym ukierunkowaniem na cel. Jednak w praktyce nie zawsze tak jest. Czytelnik może się o tym przekonać, próbując np. wybrać wskaźnik efektywności transportu miejskiego. Co należy uznać za taki wskaźnik? Średnia prędkość ruchu pasażerów w mieście? Lub średnia liczba przewożonych pasażerów? Albo średnią liczbę kilometrów, które będzie musiała przejść osoba, której transport nie jest w stanie dostarczyć we właściwe miejsce? Tu jest o czym myśleć!

Niestety w większości problemów o znaczeniu praktycznym wybór wskaźnika efektywności nie jest prosty i rozwiązywany jest niejednoznacznie. Dla każdego złożonego zadania typowa jest sytuacja, gdy skuteczności działania nie da się wyczerpująco scharakteryzować jedną liczbą – trzeba zaangażować innych do pomocy. Z takimi „wielokryterialnymi” problemami zapoznamy się w § 6.

Przykłady rozwiązywania problemów programowania dynamicznego

W tej sekcji rozważymy (a nawet rozwiążemy do końca) kilka prostych (niezwykle uproszczonych) przykładów problemów programowania dynamicznego

1. Wytyczenie najkorzystniejszej trasy mię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 czego drugi leży na północny wschód od pierwszego. Dla uproszczenia powiedzmy. że wytyczanie ścieżki składa się z szeregu stopni, a na każdym stopniu 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 segmentów. Konieczne jest ułożenie takiej ścieżki A V W, gdzie całkowity koszt jest minimalny.

Jak to zrobić? Możesz zrobić na dwa sposoby: albo przejść przez wszystkie możliwe opcje ścieżki i wybrać tę, na której koszty są minimalne (a przy dużej liczbie segmentów jest to bardzo, bardzo trudne!); lub podziel proces przejścia od A V W na poszczególne kroki (jeden krok - jeden segment) i optymalizować sterowanie krokami. Okazuje się, że druga metoda jest nieporównywalnie wygodniejsza! Tutaj, podobnie jak w innych badaniach operacyjnych, celowe, zorganizowane poszukiwanie rozwiązania ma przewagę nad naiwnym „ślepym” wyliczaniem.

Pokażmy, jak to się robi na konkretnym przykładzie. Podziel odległość od A zanim W w kierunku wschodnim, powiedzmy, na 7 części, aw kierunku północnym - na 5 części (w zasadzie fragmentacja może być dowolnie mała). Następnie dowolna ścieżka z A V W zawiera T\u003d 7 + 5 \u003d= 12 segmentów skierowanych na wschód lub północ (ryc. 13.2). Zapiszmy na każdym z odcinków liczbę wyrażającą (w dowolnych jednostkach) koszt ułożenia ścieżki na tym odcinku. Konieczne jest wybranie takiej ścieżki A V W, dla których suma liczb na odcinkach jest minimalna.

Skonstruowaną ścieżkę będziemy traktować jako system kontrolowany S, przemieszczania się pod wpływem kontroli ze stanu początkowego A do finału W. Stan tego układu przed rozpoczęciem każdego kroku będzie charakteryzowany przez dwie współrzędne: wschód (X) i północna (y), oba są liczbami całkowitymi (0 X 5 7, 0 Na 5). Dla każdego ze stanów układu (punkt węzłowy prostokątnej siatki na ryc. 13.2) musimy znaleźć warunkowe sterowanie optymalne: idziemy z tego punktu na północ (kontrola „c”) lub na wschód (kontrola "C"). Ta kontrola jest dobrana tak, aby koszt wszystkich pozostałych kroków (w tym tego) był minimalny. Koszt ten nadal będziemy nazywać „warunkowym zyskiem optymalnym” (chociaż w tym przypadku nie jest to „zysk”, a „strata”) dla danego stanu systemu. S przed rozpoczęciem następnego kroku.

Rozwiniemy procedurę optymalizacji warunkowej w przeciwnym kierunku - od końca do początku. W pierwszej kolejności przeprowadzamy optymalizację warunkową ostatniego, dwunastego kroku. Rozważ osobno prawy górny róg naszej prostokątnej siatki (ryc. 13.3). Gdzie możemy być po 11 kroku? Tylko

gdzie w jednym (ostatnim) kroku można się dostać W, czyli w jednym z punktów W 1 Lub O 2 . Jeśli jesteśmy w punkcie W 1 , nie mamy wyboru (wymuszona kontrola): musimy iść na wschód, a to będzie nas kosztować 10 jednostek. Wpiszmy tę liczbę 10 w okręgu w pobliżu punktu W 1 , a optymalna kontrola zostanie pokazana przez krótką strzałkę wychodzącą z W 1 i skierowany na wschód. Za punkt O 2 wymuszona jest również kontrola (północ), przepływ do końca wynosi 14, zapiszemy to kółkiem w punkcie O 2 . W ten sposób dokonywana jest warunkowa optymalizacja ostatniego kroku i warunkowe optymalne wzmocnienie dla każdego z punktów B 1 , B 2 znalezione i zapisane w odpowiednim kubku.

Teraz zoptymalizujmy przedostatni (11.) krok. Po przedostatnim (10.) kroku możemy wylądować w jednym z punktów do 1, do 2, do 3(Rys. 13.4). Znajdźmy dla każdego z nich warunkową optymalną kontrolę i warunkową optymalną wypłatę. Za punkt Od 1 przymusowe zarządzanie: idź na wschód;

do końca będzie nas to kosztować 21 jednostek (11 na tym etapie plus 10, wpisanych w kółko na W 1). Liczba 21 jest zapisana w kółku w kropce Od 1 . Za punkt od 2 zarządzanie nie jest już wymuszone: możemy iść zarówno na wschód, jak i na północ. W pierwszym przypadku wydamy 14 jednostek na tym etapie i od O 2 do końca - jeszcze 14, tylko 28 sztuk. Jeśli pójdziemy na północ, wydamy 13 + 10, w sumie 23 jednostki. Stąd warunkowa kontrola optymalna w punkcie od 2 - idź na północ (zaznacz to strzałką i wpisz liczbę 23 w kółku obok do 2), Za punkt od 3 kontrola jest ponownie wymuszona („c”), do końca będzie kosztować 22 jednostki (ustaw strzałkę na północ, wpisz liczbę 22 w kółku, gdy od 3).

Podobnie „cofając się” od przedostatniego kroku wstecz, dla każdego punktu o współrzędnych całkowitych znajdujemy kontrolę optymalną warunkową („c” lub „b”), którą oznaczamy strzałką, oraz warunkowy zysk optymalny (wydatek na koniec ścieżki), które piszemy w kółku. Oblicza się to w następujący sposób: natężenie przepływu w danym kroku jest dodawane do już zoptymalizowanego natężenia przepływu, zapisanego w kółku, do którego prowadzi strzałka. Tym samym na każdym kroku optymalizujemy tylko ten krok, a kolejne są już zoptymalizowane. Efekt końcowy procedury optymalizacyjnej przedstawiono na rys. 13,5.

Zatem optymalizacja warunkowa została już przeprowadzona: niezależnie od tego, gdzie jesteśmy, wiemy już, dokąd iść (strzałka) i ile będzie nas kosztowało dotarcie do celu (liczba w kółku). W kółko w kropkę A optymalna wypłata dla całej budowy ścieżki od A V W:

W* = 118.

Teraz pozostaje skonstruować bezwarunkową optymalną kontrolę - trajektorię prowadzącą od A I W w najtańszy sposób. Aby to zrobić, wystarczy „przestrzegać strzelców”, czyli czytać, co zalecają robić na każdym kroku. Taka optymalna trajektoria jest zaznaczona na rys. 13,5 okrążył dwukrotnie. Odpowiednia bezwarunkowa optymalna kontrola będzie:

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

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

Zauważmy, że w trakcie optymalizacji warunkowej możemy spotkać się z przypadkiem, gdy obie kontrole dla jakiegoś punktu na płaszczyźnie są optymalne, tj. prowadzą do tego samego kosztu środków od tego punktu do końca, np. w punkcie o współrzędnych (5; 1) obie kontrole „c” i „b” są optymalne i dają przepływ do końca równy 62. Wybieramy dowolnie dowolną z nich (w naszym przypadku wybraliśmy „c”; równie dobrze moglibyśmy wybrać "C"). Takie przypadki niejednoznacznego wyboru optymalnego sterowania są stale spotykane w programowaniu dynamicznym; w przyszłości nie będziemy ich specjalnie oznaczać, ale po prostu arbitralnie wybierzemy dowolną z równoważnych opcji. Oczywiście od tej arbitralności może zależeć optymalna kontrola całego procesu, ale nie optymalny zysk. Ogólnie rzecz biorąc, w problemach programowania dynamicznego (a także w problemach programowania liniowego) rozwiązanie nie zawsze jest unikalne.

A teraz wróćmy do początku i spróbujmy rozwiązać problem w sposób „naiwny”, wybierając na każdym kroku, zaczynając od pierwszego, najbardziej opłacalnego (dla tego kroku) kierunku (jeśli jest ich dwóch, wybieramy każdy). W ten sposób uzyskujemy kontrolę

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

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

W problemie rozwiązanym powyżej warunki zostały celowo uproszczone do granic możliwości. Oczywiście nikt nie będzie prowadził torów kolejowych „po schodkach”, poruszając się tylko ze względu na północ lub ze względu na wschód. Dokonaliśmy takiego uproszczenia, aby w każdym punkcie wybierać tylko z dwóch kontrolek: „od” lub „do”. Zamiast dwóch możliwych kierunków, można by wprowadzić kilka z nich i dodatkowo poczynić mniejsze kroki; nie ma to fundamentalnego znaczenia, ale oczywiście komplikuje i wydłuża obliczenia.

Należy zauważyć, że zadania podobne do tych omówionych powyżej są bardzo często spotykane w praktyce: na przykład przy wyborze najszybszej trasy między dwoma punktami lub najbardziej ekonomicznego (pod względem zużycia paliwa) przyrostu prędkości i wysokości przez statek powietrzny.

Zróbmy jedną przelotną uwagę. Uważny czytelnik zapewne zauważył, że w naszym problemie punkty A I W(początek i koniec) w zasadzie nie różnią się od siebie: możliwe byłoby zbudowanie warunkowych optymalnych kontroli nie od końca do początku, ale od początku do końca i bezwarunkowo - w przeciwnym kierunku. Rzeczywiście tak jest: w każdym problemie programowania dynamicznego „początek” i „koniec” można zamienić miejscami. Jest to całkowicie równoważne wcześniej opisanej metodzie pod względem obliczeń, ale jest nieco mniej wygodne, gdy ustnie wyjaśnia się ideę metody: łatwiej jest argumentować, odnosząc się do „już ustalonych” warunków na początku tego kroku niż do tych, które po tym kroku wciąż „idą”. Zasadniczo oba podejścia są całkowicie równoważne.

2. Problem alokacji zasobów. Metoda programowania dynamicznego umożliwia skuteczne rozwiązanie wielu problemów ekonomicznych (patrz np. ). Rozważ jeden z najprostszych takich problemów. Dysponujemy pewnym zapasem środków (zasobów). DO, które powinny być rozdzielone T przedsiębiorstwa P 1 , P 2 , ..., P m . Każde z przedsiębiorstw I przy inwestowaniu w nie X generuje dochód na podstawie X, tj. reprezentujący jakąś funkcję ( X). Wszystkie funkcje ( X) (I = 1, 2, ..., T) są dane (oczywiście te funkcje są niemalejące). Pytanie, jak rozdysponować środki DO. między przedsiębiorstwami, tak aby w sumie dawały maksymalny dochód?

Problem ten można łatwo rozwiązać metodą programowania dynamicznego.Choć w swoim sformułowaniu nie zawiera ona wzmianki o czasie, to jednak można w myślach rozłożyć operację dystrybucji środków w jakiejś kolejności, traktując inwestycję środków w przedsiębiorstwie P 1 jako pierwszy krok, aw P 2 itd.

System zarządzany S w tym przypadku fundusze lub zasoby, które są dystrybuowane. Stan systemu S przed każdym krokiem charakteryzuje się jedną liczbą S- rezerwa gotówkowa jeszcze nie zainwestowana. W tym problemie „kontrole krokowe” są środkami x 1, x 2, ..., x 3, przydzielone firmom. Należy znaleźć sterowanie optymalne, czyli taki zbiór liczb x 1, x 2, ..., xm, przy którym całkowity dochód jest maksymalny:

(13.1)

Rozwiążemy ten problem najpierw w postaci ogólnej, formułowej, a następnie - dla konkretnych danych liczbowych. Znajdź dla każdego I-ty krok to warunkowa optymalna wypłata (od tego kroku do końca), jeśli podeszliśmy do tego kroku z marginesem środków S. Oznacz warunkową optymalną wypłatę W i (S), a odpowiednią warunkowo optymalną kontrolą są fundusze, w które zainwestowano I przedsiębiorstwo, - x ja (S).

Zacznijmy optymalizację od ostatniej, T - krok. Przejdźmy do tego kroku z resztą funduszy S. Co powinniśmy zrobić? Oczywiście zainwestować całą kwotę S w całości na rzecz przedsiębiorstwa P M. Dlatego warunkowa kontrola optymalna włączona M-ty krok: dać ostatniemu przedsiębiorstwu wszystkie dostępne środki S, tj.

i warunkową optymalną wypłatę

W m (S) = (S).

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

Przejdźmy do przedostatniego (T- 1) krok. Zbliżmy się do niego z rezerwą funduszy S. Oznaczać Szer.m -1 (S) warunkowa optymalna wypłata na dwóch ostatnich krokach: ( M- 1)-m i M-m (który jest już zoptymalizowany). Jeśli przydzielimy ( M- 1) krok ( M- 1) przedsiębiorstwo oznacza X, wtedy będzie ostatni krok S-x. Nasza wypłata w dwóch ostatnich krokach będzie równa

,

i trzeba go znaleźć X, przy którym to wzmocnienie jest maksymalne:

Znak oznacza, że ​​wartość maksymalna jest przejmowana przez wszystkich X, co jest możliwe (zainwestować więcej niż S, nie możemy) z wyrażenia w nawiasach klamrowych. To maksimum to warunkowa optymalna wypłata dla ostatnich dwóch kroków, a następnie wartość X, przy którym osiągane jest to maksimum, jest włączona kontrola warunkowa optymalna (T- 1) krok.

i odpowiednią warunkową kontrolę optymalną x ja (S) - ta wartość X, w którym osiągane jest to maksimum.

Kontynuując w ten sposób dochodzimy wreszcie do 1. przedsiębiorstwa P 1 . Tutaj nie musimy zmieniać wartości S; wiemy na pewno, że zasób środków przed pierwszym krokiem jest równy DO:

Tak więc znaleziono maksymalny zysk (dochód) ze wszystkich przedsiębiorstw. Teraz pozostaje tylko „przeczytać zalecenia”. To znaczenie X, przy którym osiągane jest maksimum (13,4), a na 1. kroku następuje optymalna regulacja. Po zainwestowaniu tych środków w pierwsze przedsiębiorstwo będziemy mieli DO- .„Odczyt” rekomendacji dla tej wartości S, alokujemy optymalną ilość środków na drugie przedsięwzięcie:

,

i tak dalej aż do końca.

Rozwiążmy teraz przykład liczbowy. Początkowy zasób środków K = 10 (jednostek konwencjonalnych) i wymagane jest optymalne rozłożenie jej pomiędzy pięć przedsiębiorstw (t = 5). Dla uproszczenia założymy, że inwestowane są tylko całkowite kwoty środków. funkcje dochodu ( 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, począwszy od określonej kwoty inwestycji, dochody przestają rosnąć (w rzeczywistości odpowiada to temu, że każde przedsiębiorstwo jest w stanie „opanować” 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 dochodzimy do kolejnego kroku, mając rezerwę środków S, staramy się przeznaczyć taką czy inną kwotę środków na ten krok, zysk na tym kroku bierzemy zgodnie z tabelą 13.1, dodajemy go do już zoptymalizowanego zysku na wszystkich kolejnych krokach aż do końca (biorąc pod uwagę, że zostało nam już mniej środków, wystarczy o taką ilość środków, jakie przeznaczyliśmy) i znajdź inwestycję, przy której suma ta osiągnie swoje maksimum. Ta inwestycja jest warunkowo 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 S, z z jakim podchodzimy do tego kroku. Ponadto tabela jest podzielona na pięć par kolumn, odpowiadających numerowi kroku. Pierwsza kolumna każdej pary zawiera wartość

Tabela 13.2

S	i=5	i=4	i=3	i=2	i=1
x5(S)	W 5(S)	x4(S)	W4(S)	x 3(S)	W 3(S)	x2(S)	W2(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 kontrola optymalna, w drugiej - warunkowa optymalna wypłata. Tabela jest wypełniona od lewej do prawej, od góry do dołu. Decyzja na piątym – ostatnim – etapie jest wymuszona: wszystkie środki są przydzielone;

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

S0 = K = 10. Oprawione są optymalne kontrole na wszystkich etapach. W ten sposób doszliśmy do ostatecznego wniosku: musimy przydzielić dwie jednostki z dziesięciu do pierwszego przedsięwzięcia, pięć jednostek do drugiego, dwie do trzeciego, żadnej do czwartego, jedną jednostkę do piątego. Przy takim rozkładzie dochód będzie maksymalny i równy 5,6.

Aby wyjaśnić czytelnikowi, w jaki sposób wypełniona jest tabela 13.2, zademonstrujemy to na jednej próbce obliczeniowej. Załóżmy, że musimy np. zoptymalizować rozwiązanie x 3(7)- co zrobić w kroku trzecim, gdybyśmy podeszli do niego z rezerwą środków S= 7, a ile maksymalnie możemy wygrać na wszystkich pozostałych

Tabela 13.3

X	7 - X		W4(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, w tym trzeci? Załóżmy, że wszystkie kroki po trzecim (4 i 5) zostały już zoptymalizowane, czyli dwie pierwsze pary kolumn tabeli 13.2 zostały wypełnione. Znajdźmy X 3 pkt 7 i W 3(7). Aby to zrobić, skompilujemy płytkę pomocniczą (patrz tabela 13.3). Pierwsza kolumna zawiera listę wszystkich możliwych załączników. X na trzecim stopniu, nie przekraczając S = 7. W drugiej kolumnie - co pozostanie po takiej inwestycji z zasobu funduszy S = 7. W trzeciej kolumnie – zysk w trzecim kroku z inwestowania X w przedsiębiorstwie trzecim wypełnia kolumna (tabela 13.1). W czwartej kolumnie - optymalna wypłata na wszystkich pozostałych krokach (czwarty i piąty), pod warunkiem, że zbliżyliśmy się do czwartego kroku z pozostałymi środkami (wypełniona kolumna ja = 4 tabele 13.2). W piątej kolumnie - suma dwóch wypłat: krokowej i dalej optymalizowanej dla danej inwestycji X w trzecim kroku.

Spośród wszystkich wypłat z ostatniej kolumny wybierana jest maksymalna (w tabeli 13.3 jest równa W 3(7) = 3,6 i odpowiednia kontrola X(7) = 2).

Powstaje pytanie: co jeśli w tabeli pomocniczej typu 13.3 maksimum zostanie osiągnięte dla więcej niż jednego X, a przy dwóch lub więcej? Odpowiadamy: nie ma znaczenia, który wybrać; zysk nie zależy od tego. Ogólnie rzecz biorąc, w problemach programowania dynamicznego rozwiązanie nie powinno być w ogóle unikalne (już o tym wspominaliśmy).

3. Problem załadunku maszyny. Korzystając z metody programowania dynamicznego, można z powodzeniem rozwiązać szereg problemów optymalizacyjnych opisanych w rozdziale 3, w szczególności niektóre problemy programowania całkowitoliczbowego. Zauważmy, że integralność rozwiązań, która sprawia, że ​​problemy z programowaniem liniowym są tak trudne, w tym przypadku nie komplikuje, a wręcz przeciwnie, upraszcza procedurę (tak jak została ona dla nas uproszczona przez integralność 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); ich waga jest znana q 1 , q 2 , ..., q n i koszt od 1, z 2 , ..., z n . Nośność maszyny to Q. Pytanie, które z przedmiotów należy zabrać do samochodu, aby ich całkowity koszt (z całkowitą wagą Q) było maksimum?

Powinieneś poznać podstawowe pojęcia i definicje badań operacyjnych.

Operacja to każde kontrolowane działanie mające na celu osiągnięcie celu. Wynik operacji zależy od sposobu jej realizacji, organizacji, w przeciwnym razie - od wyboru określonych parametrów. Każdy określony wybór parametrów nazywa się rozwiązaniem. Rozwiązania optymalne to takie, które z jakiegoś powodu są lepsze od innych. Dlatego głównym zadaniem badań operacyjnych jest wstępne ilościowe uzasadnienie optymalnych rozwiązań.

Uwaga 1

Należy zwrócić uwagę na sformułowanie problemu: samo podejmowanie decyzji wykracza poza zakres badań operacyjnych i należy do kompetencji odpowiedzialnej osoby lub grupy osób, które mogą brać pod uwagę inne względy niż matematycznie uzasadnione.

Uwaga 2

Jeżeli w niektórych zadaniach badań operacyjnych optymalnym rozwiązaniem jest to, w którym wybrane kryterium efektywności przyjmuje wartość maksymalną lub minimalną, to w innych zadaniach nie jest to w ogóle konieczne. Tak więc w problemie za optymalną możemy uznać np. taką liczbę placówek i personelu w nich zatrudnionego, w której średni czas obsługi klienta nie przekroczy np. 5 minut, a średnia długość kolejki w dowolnym momencie będzie nie więcej niż 3 osoby (1, str. 10-11).

O efektywności działań produkcyjnych i handlowych w dużej mierze decyduje jakość decyzji podejmowanych na co dzień przez menedżerów różnych szczebli. W tym względzie ogromne znaczenie mają zadania doskonalenia procesów decyzyjnych, które pozwalają rozwiązywać badania operacyjne. Terminu „badania operacyjne” użyto po raz pierwszy w latach 1939-1940. na terenie wojskowym. W tym czasie sprzęt wojskowy i zarządzanie nim stały się zasadniczo bardziej skomplikowane w wyniku rewolucji naukowej i technologicznej. I dlatego do początku II wojny światowej zaistniała pilna potrzeba prowadzenia badań naukowych w zakresie efektywnego wykorzystania nowego sprzętu wojskowego, ilościowej oceny i optymalizacji decyzji podejmowanych przez dowództwo. W okresie powojennym sukcesy nowej dyscypliny naukowej były pożądane na obszarach pokojowych: w przemyśle, działalności przedsiębiorczej i handlowej, w instytucjach rządowych i edukacyjnych.

Badania operacyjne to metodologia stosowania matematycznych metod ilościowych do uzasadniania rozwiązań problemów we wszystkich obszarach celowej działalności człowieka. Metody i modele badań operacyjnych pozwalają uzyskać rozwiązania najlepiej spełniające cele organizacji.

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

Główny postulat badań operacyjnych jest następujący: rozwiązaniem optymalnym (sterowaniem) jest taki zbiór wartości zmiennych, który osiąga optymalną (maksymalną lub minimalną) wartość kryterium efektywności (funkcji celu) operacji i obserwuje określone ograniczenia.

Przedmiotem badań operacyjnych jest problem podejmowania optymalnych decyzji w systemie ze sterowaniem opartym na ocenie efektywności jego funkcjonowania. Charakterystycznymi pojęciami badań operacyjnych są: model, zmienne zmienne, ograniczenia, funkcja celu.

Przedmiotem badań operacyjnych w rzeczywistości są systemy zarządzania organizacją (organizacje), które składają się z dużej liczby oddziałów oddziałujących na siebie, a interesy działów nie zawsze są ze sobą zgodne i mogą być przeciwstawne.

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

Rozwiązanie, które jest najbardziej korzystne dla całej organizacji, nazywamy rozwiązaniem optymalnym, a rozwiązanie, które jest najbardziej korzystne dla jednego lub więcej działów, będzie rozwiązaniem suboptymalnym.

Jako przykład typowego zadania zarządzania organizacją, w którym ścierają się sprzeczne interesy działów, rozważ problem zarządzania zapasami przedsiębiorstwa.

Dział produkcji dąży do wyprodukowania jak największej ilości produktów przy jak najniższych kosztach. Interesuje go zatem jak najdłuższa i ciągła produkcja, czyli wytwarzanie wyrobów w dużych seriach, gdyż taka produkcja zmniejsza koszty rekonfiguracji sprzętu, a co za tym idzie całościowe koszty produkcji. Produkcja wyrobów w dużych ilościach wymaga jednak tworzenia dużych wolumenów zapasów materiałów, komponentów itp.

Dział handlowy jest również zainteresowany dużymi zapasami gotowych produktów, aby zaspokoić każde zapotrzebowanie klienta w dowolnym momencie. Zawierając każdą umowę, dział sprzedaży, dążąc do sprzedaży jak największej liczby produktów, musi zaoferować konsumentowi jak najszerszą gamę produktów. W rezultacie często dochodzi do konfliktu między działem produkcji a działem sprzedaży w zakresie asortymentu. Jednocześnie dział sprzedaży nalega na włączenie do planu wielu produktów wytwarzanych w małych ilościach, nawet jeśli nie przynoszą one dużych zysków, a dział produkcji domaga się wykluczenia takich produktów z asortymentu.

Dział finansowy, dążąc do zminimalizowania kwoty kapitału niezbędnego do funkcjonowania przedsiębiorstwa, stara się zmniejszyć ilość „powiązanego” kapitału obrotowego. Dlatego jest zainteresowany redukcją zapasów do minimum. Jak widać, wymagania dotyczące wielkości zapasów dla różnych działów organizacji są różne. Powstaje pytanie, która strategia inwentaryzacyjna będzie najbardziej korzystna dla całej organizacji. Jest to typowe zadanie zarządzania organizacją. Wiąże się to z problemem optymalizacji funkcjonowania systemu jako całości i wpływa na sprzeczne interesy jego działów.

Kluczowe cechy badań operacyjnych:

1. Systematyczne podejście do analizy postawionego problemu. Podejście systemowe, czyli analiza systemowa, jest główną zasadą metodologiczną badań operacyjnych, która brzmi następująco. Każde zadanie, bez względu na to, jak prywatne może się wydawać na pierwszy rzut oka, rozpatrywane jest z punktu widzenia jego wpływu na kryterium funkcjonowania całego systemu. Powyżej podejście systemowe zostało zilustrowane na przykładzie problemu zarządzania zapasami.

2. Typowe dla badań operacyjnych jest to, że przy rozwiązywaniu każdego problemu pojawia się coraz więcej nowych zadań. Dlatego też, jeśli na początku stawiane są wąskie, ograniczone cele, stosowanie metod operacyjnych nie jest skuteczne. Największy efekt można osiągnąć tylko przy ciągłych badaniach, zapewniających ciągłość w przechodzeniu od jednego zadania do drugiego.

3. Jedną z istotnych cech badań operacyjnych jest dążenie do znalezienia optymalnego rozwiązania problemu. Jednak takie rozwiązanie często okazuje się nieosiągalne ze względu na ograniczenia narzucane przez dostępne zasoby (pieniądze, czas komputerowy) czy poziom współczesnej nauki. Na przykład dla wielu problemów kombinatorycznych, w szczególności problemów szeregowania z liczbą maszyn n > 4, optymalne rozwiązanie przy współczesnym rozwoju matematyki można znaleźć jedynie poprzez proste wyliczenie opcji. Wtedy trzeba ograniczyć się do poszukiwania rozwiązania „wystarczająco dobrego” lub suboptymalnego. Dlatego jeden z jego twórców, T. Saaty, zdefiniował badania operacyjne jako „…sztukę udzielania złych odpowiedzi na te praktyczne pytania, na które inne metody dają jeszcze gorsze odpowiedzi”.

4. Cechą badań operacyjnych jest to, że są one prowadzone w sposób kompleksowy, w wielu obszarach. Tworzy się grupę operacyjną do przeprowadzenia takiego badania. W jego skład wchodzą specjaliści z różnych dziedzin wiedzy: inżynierowie, matematycy, ekonomiści, socjologowie, psycholodzy. Zadaniem tworzenia takich grup operacyjnych jest kompleksowe badanie całego zespołu czynników wpływających na rozwiązanie problemu oraz wykorzystanie idei i metod różnych nauk.

Każde badanie operacyjne przechodzi kolejno przez następujące główne etapy:

1) opis zadania planistycznego,

2) budowanie modelu matematycznego,

3) znalezienie rozwiązania,

4) sprawdzenie i poprawienie modelu,

5) wdrożenie znalezionego rozwiązania w praktyce.

Opis zadania planistycznego:

Zadania planowania i zarządzania siecią

rozważyć związek między terminami zakończenia dużego kompleksu operacji (robot) a momentami rozpoczęcia wszystkich operacji kompleksu. Zadania te polegają na znalezieniu minimalnego czasu trwania zestawu operacji, optymalnej proporcji kosztów i czasu ich realizacji.

Zadania kolejkowe poświęcone są badaniu i analizie systemów kolejkowych z kolejkami aplikacji lub wymagań i polegają na określeniu wskaźników wydajności systemów, ich optymalnych charakterystyk, na przykład na określeniu liczby kanałów obsługi, czasu obsługi itp.

Zadania zarządzania zapasami polegają na znalezieniu optymalnych wartości poziomów zapasów (punktów zamówień) i wielkości zamówień. Specyfika takich zadań polega na tym, że wraz ze wzrostem poziomu zapasów z jednej strony rosną koszty ich przechowywania, ale z drugiej strony maleją straty z tytułu ewentualnego niedoboru magazynowanego produktu.

Problemy z alokacją zasobów pojawiają się w przypadku pewnego zestawu operacji (prac), które muszą być wykonane przy ograniczonych dostępnych zasobach i wymagane jest znalezienie optymalnego podziału zasobów między operacjami lub składu operacji.

Zadania naprawy i wymiany sprzętu są istotne ze względu na zużycie sprzętu i konieczność jego wymiany w czasie. Zadania sprowadzają się do ustalenia optymalnego terminu, ilości napraw i przeglądów zapobiegawczych oraz momentów wymiany sprzętu na zmodernizowany.

Zadania szeregowania (szeregowania) polegają na określeniu optymalnej sekwencji operacji (na przykład obróbki części) na różnych typach urządzeń.

Zadania planowania i rozmieszczenia polegają na określeniu liczby i lokalizacji nowych obiektów, biorąc pod uwagę ich interakcje z istniejącymi obiektami i między sobą.

Problemy wyboru tras, czyli problemy sieciowe, spotykane są najczęściej przy badaniu różnych problemów w transporcie i systemie komunikacyjnym i polegają na wyznaczeniu najbardziej ekonomicznych tras (1, s. 15).

Pod operacja rozumiane jest jako każde wydarzenie, które łączy jedna idea i kierunek dla osiągnięcia określonego celu.

Operacja jest zawsze zdarzeniem zarządzanym, tj. do nas należy wybór parametrów charakteryzujących sposób jego organizacji.

Każdy określony dobór parametrów zależny od nas zostanie wywołany decyzja.

Optymalne rozwiązania to takie, które z jakiegoś powodu są lepsze od innych.

Głównym celem badań operacyjnych jest wstępne uzasadnienie ilościowe optymalnych rozwiązań. Celem badań operacyjnych nie jest pełna automatyzacja podejmowania decyzji. Decyzję zawsze podejmuje człowiek. Celem badań operacyjnych jest uzyskanie danych ilościowych i zaleceń, które ułatwią osobie podejmowanie decyzji.

Wraz z głównym zadaniem - uzasadnienie optymalnych rozwiązań - Zakres badań operacyjnych obejmuje inne zadania:

ocena porównawcza różnych wariantów organizacji operacji,

Ocena wpływu na działanie różnych parametrów,

Badanie „wąskich gardeł”, tj. elementów, których zakłócenie ma szczególnie silny wpływ na powodzenie operacji itp.

Te zadania pomocnicze mają szczególne znaczenie, gdy dana operacja nie jest rozpatrywana w izolacji, ale jako integralny element całości systemy operacje. „Systemowe” podejście do zadań badań operacyjnych wymaga uwzględnienia wzajemnej zależności i uwarunkowania całego szeregu działań, tj. podjąć ostateczną decyzję uwzględniając rolę i miejsce tej operacji w systemie.

Pod efektywność działanie rozumiane jest jako stopień jego przystosowania do wykonywania postawionego przed nim zadania.

Aby ocenić skuteczność operacji i porównać skuteczność różnie zorganizowanych operacji, trzeba mieć pewną liczbę kryterium oceny Lub wskaźnik wydajności.

Kolejność działań w badaniach operacyjnych.

1. Formułuje się cel badania i rozwija sformułowanie problemu.

2. Aby zastosować metody ilościowe w dowolnej dziedzinie, zawsze konieczne jest zbudowanie modelu matematycznego zjawiska. Na podstawie analizy właściwości oryginału budowany jest ten model.

3. Po zbudowaniu modelu uzyskuje się na nim wyniki

4. Interpretuje się je w odniesieniu do oryginału i przenosi do oryginału.

5. Za pomocą porównania porównuje się wyniki symulacji z wynikami uzyskanymi z bezpośredniego badania oryginału.

Jeżeli wyniki uzyskane za pomocą modelu są zbliżone do wyników uzyskanych w badaniu oryginału, to pod względem tych właściwości model można uznać za adekwatny do oryginału.

Podczas projektowania i eksploatacji zautomatyzowanych systemów sterowania często pojawiają się zadania związane z analizą zarówno ilościowych, jak i jakościowych wzorców ich funkcjonowania, określeniem ich optymalnej struktury itp.

Bezpośrednie eksperymenty na obiektach w celu rozwiązania tych problemów mają szereg istotnych wad:

1. Naruszony jest ustalony tryb działania obiektu.

2. W eksperymencie na pełną skalę nie można przeanalizować wszystkich alternatywnych opcji budowy systemu itp.

Wskazane jest rozwiązanie tych problemów na modelu wydzielonym z obiektu i zaimplementowanym na komputerze.

Podczas modelowania systemów informacyjnych szeroko stosowane są modele matematyczne.

Metoda modelowania matematycznego to metoda badania różnych obiektów poprzez zestawienie odpowiedniego opisu matematycznego i obliczenie na jego podstawie cech badanego obiektu.

Konieczne jest zbudowanie modelu matematycznego. Formalnie odzwierciedla funkcjonowanie oryginału i opisuje główne wzorce jego zachowania. W tym przypadku wszystkie drugorzędne, nieistotne czynniki są wyłączone z rozważań.

Przedmiotem modelowania matematycznego są systemy złożone. Złożony system to w pewien sposób zorganizowany i celowo funkcjonujący zespół dużej liczby powiązanych z informacjami i oddziałujących na siebie elementów pod wpływem czynników zewnętrznych.

Istnieją 4 główne etapy modelowania systemów na komputerze:

Budowa modelu koncepcyjnego systemu i jego sformalizowanie;

Algorytmizacja modelu systemu i opracowanie programu do modelowania;

Pozyskiwanie i interpretacja wstępnych wyników symulacji;

Sprawdzenie adekwatności modelu i systemu; dopasowanie modelu

Główne obliczenia wskaźników jakości funkcjonowania systemu na podstawie wyników modelowania, implementacja modelu.

Wykład 3. Podstawowe pojęcia metody ocen rzeczoznawczych. Tworzenie grup eksperckich. procedury głosowania. Metody szeregowania, porównania parami, ocena w skali względnej.

1. Podstawowe pojęcia IO

I O – dyscyplina naukowa, zajmująca się opracowywaniem i praktycznym zastosowaniem metod najefektywniejszego zarządzania różnymi systemami organizacyjnymi.

IO zawiera następujące sekcje:

1) program matematyczny. (uzasadnianie planów, programów działalności gospodarczej); zawiera sekcje: program liniowy, program nieliniowy, program dynamiczny

2) teoria kolejek oparta na teorii procesów losowych;

3) teoria gier, która umożliwia uzasadnianie decyzji podejmowanych w warunkach niekompletności informacji.

Przy rozwiązywaniu konkretnego problemu sterowania, zastosowanie metod IO polega na:

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

Badanie wzajemnych powiązań, które determinują późniejsze podejmowanie decyzji i ustalenie kryteriów wydajności, które pozwalają ocenić przewagę takiego lub innego sposobu działania.

Podstawowe pojęcia i definicje IO.

Operacja – każda kontrolowana czynność mająca na celu osiągnięcie celu. Wynik operacji zależy od sposobu jej realizacji, organizacji, w przeciwnym razie - od wyboru określonych parametrów. Operacja jest zawsze zdarzeniem kontrolowanym, to znaczy od nas zależy, w jaki sposób dobierzemy niektóre parametry charakteryzujące jej organizację. „Organizacja” jest tutaj rozumiana w szerokim tego słowa znaczeniu, w tym zespół środków technicznych wykorzystywanych w działaniu.

Dowolny wybór parametrów jest wywoływany decyzja . Decyzje mogą być udane i nieudane, rozsądne i nierozsądne. Optymalny rozważyć te rozwiązania, które z tego czy innego powodu są lepsze od innych. Głównym zadaniem badań operacyjnych jest wstępne uzasadnienie ilościowe optymalnych rozwiązań.

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

Wydajność działania – stopień jej przystosowania do realizacji zadania wyrażany jest ilościowo w postaci kryterium efektywności – funkcji celu. Wybór kryterium efektywności decyduje o wartości praktycznej opracowania. (Niewłaściwie dobrane kryterium może być szkodliwe, ponieważ działania zorganizowane w ramach takiego kryterium efektywności prowadzą czasem do nieuzasadnionych kosztów).

Zadania planowania i zarządzania siecią rozważyć związek między terminami zakończenia dużego kompleksu operacji (robot) a momentami rozpoczęcia wszystkich operacji kompleksu. Zadania te polegają na znalezieniu minimalnego czasu trwania kompleksu operacji, optymalnego stosunku kosztów i czasu ich realizacji.

Kolejkowanie zadań poświęcone badaniu i analizie systemów kolejkowych z kolejkami wniosków lub wymagań i polegają na określeniu wskaźników wydajności systemów, ich optymalnych charakterystyk, na przykład na określeniu liczby kanałów obsługi, czasu obsługi itp.

Zadania zarządzania zapasami polegają na znalezieniu optymalnych wartości stanu magazynowego (punktu ponownego zamówienia) oraz wielkości zamówienia. Specyfika takich zadań polega na tym, że wraz ze wzrostem poziomu zapasów z jednej strony rosną koszty ich magazynowania, z drugiej strony maleją straty z tytułu ewentualnego niedoboru magazynowanego produktu.

Zadania alokacji zasobów wynikają z określonego zestawu operacji (prac), które muszą być wykonane przy ograniczonych dostępnych zasobach i wymagane jest znalezienie optymalnego podziału zasobów między operacjami lub składu operacji.

Zadania związane z naprawą i wymianą sprzętu 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, ilości napraw i przeglądów zapobiegawczych oraz momentów wymiany sprzętu na zmodernizowany.

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

Planowanie i rozmieszczanie zadań nia polegają na określeniu optymalnej liczby i lokalizacji nowych obiektów, z uwzględnieniem ich interakcji z istniejącymi obiektami i między sobą.

zadania wyboru trasy, Lub sieć zadania najczęściej spotykane w badaniu różnych zadań w transporcie i systemie komunikacyjnym i polegają na wyznaczeniu najbardziej ekonomicznych tras.

2. Ogólne zadanie programu liniowego. Optymalne rozwiązanie

Model ekonomiczny i matematyczny

LP to dziedzina matematyki, która rozwija teorię i metody numeryczne rozwiązywania problemów znajdowania ekstremów (maksimum lub minimum) funkcji liniowej wielu zmiennych w obecności ograniczeń liniowych, tj. Równości lub nierówności łączących te zmienne.

Metody LP stosuje się do praktycznych problemów, w których: 1) konieczne jest wybranie najlepszego rozwiązania (planu optymalnego) ze zbioru możliwych; 2) rozwiązanie można wyrazić jako zbiór wartości niektórych zmiennych wielkości; a) ograniczenia nałożone na wykonalne rozwiązania przez specyficzne warunki problemu formułowane są w postaci równań lub nierówności liniowych; 4) cel wyrażony jest jako funkcja liniowa głównych zmiennych. Jako kryterium jakości rozwiązania służą wartości funkcji celu, pozwalające na porównanie różnych rozwiązań.

W celu praktycznego rozwiązania problemu ekonomicznego metodami matematycznymi należy przede wszystkim napisać go przy użyciu modelu ekonomiczno-matematycznego. Model ekonomiczno-matematyczny - opis matematyczny badanego procesu lub obiektu gospodarczego. Model ten wyraża wzorce procesu gospodarczego w abstrakcyjnej formie za pomocą zależności matematycznych.

Ogólny schemat budowy modelu: I

1) wybór określonej liczby zmiennych, których przypisanie - wartości liczbowe jednoznacznie określa jeden z możliwych stanów badanego zjawiska;

2) wyrażenie zależności tkwiących w badanym zjawisku w postaci zależności matematycznych (równania, nierówności). Relacje te tworzą system ograniczeń problemowych;

3) ilościowe wyrażenie wybranego kryterium optymalności w postaci funkcji celu; I

4) matematyczne sformułowanie problemu jako problemu znalezienia ekstremum funkcji celu, z zastrzeżeniem ograniczeń nałożonych na zmienne.

Ogólny problem programowania liniowego wygląda jak:

Mając dany układ m równań i nierówności liniowych z n zmiennymi

i funkcja liniowa

Należy znaleźć takie rozwiązanie układu X=(x1,x2,…,xj,…,xn), w którym funkcja liniowa F przyjmuje wartość optymalną (tj. maksymalną lub minimalną).

Układ (1) nazywany jest układem ograniczeń, a funkcja F nazywana jest funkcją liniową, postacią liniową, funkcją celu lub funkcją celu.

W skrócie, ogólny problem programowania liniowego można przedstawić jako:

z ograniczeniami:

Optymalne rozwiązanie (lub optymalny plan) Problem LP to rozwiązanie X=(x1,x2,…,xj,…,xn) układu ograniczeń (1), które spełnia warunek (3), przy którym funkcja liniowa (2) przyjmuje optymalne (maksimum lub minimalna wartość.

Przy założeniu, że wszystkie zmienne są nieujemne, układ ograniczeń (1) składa się tylko z nierówności - takie zadanie programowania liniowego nazywamy standardowym (symetrycznym); jeśli układ więzów składa się tylko z równań, to problem nazywamy kanonicznym.

Szczególnym przypadkiem problemu kanonicznego jest problem w postaci podstawowej, który różni się tym, że wszystkie współczynniki wektora ograniczeń B są nieujemne, aw każdym równaniu występuje zmienna o współczynniku 1, której nie ma w żadnym z pozostałych równań. Zmienna z tą właściwością nazywana jest zmienną bazową.

Problemy standardowe i kanoniczne są szczególnymi przypadkami problemu ogólnego. Każdy z nich jest używany w określonym obszarze. Co więcej, wszystkie trzy sformułowania są sobie równoważne: każdy problem programowania liniowego można sprowadzić do problemu kanonicznego, standardowego lub ogólnego za pomocą prostych przekształceń matematycznych.

4 . Elementy algebry liniowej

Układ m równań liniowych z n zmiennymi ma postać

lub w skrócie

Dowolnych m zmiennych układu m równań liniowych z n zmiennymi (m< n) называются основными (или базисными), если определитель матрицы коэффициентов при них отличен от нуля. Такой определитель часто называют базисным минором матрицы А. Тогда остальные m–n переменных называются неосновными (или свободными).

Aby rozwiązać układ (2.1) pod warunkiem m< n сформулируем утверждение.

Oświadczenie 2.1. Jeśli dla systemuMrównania liniowe zNzmienne (M < N) rząd macierzy współczynników dla zmiennych jest równy m, tj. istnieje co najmniej jedna grupa zmiennych podstawowych, to układ ten jest nieokreślony, a każdemu dowolnemu zestawowi wartości zmiennych niepodstawowych odpowiada jedno rozwiązanie układu.

Rozwiązanie X=(x1,x2,…,xn) układu (2.1) nazywamy dopuszczalnym, jeżeli zawiera tylko składowe nieujemne, tj. xj>=0 dla dowolnego j=1,n. W przeciwnym razie rozwiązanie nazywa się nieważne.

Wśród nieskończonego zbioru rozwiązań układu wyróżnia się tzw. rozwiązania podstawowe.

Podstawowe rozwiązanie układ m równań liniowych z n zmiennymi nazywamy rozwiązaniem, w którym wszystkie n–m zmiennych innych niż podstawowe są równe zeru.

W problemach programowania liniowego szczególne znaczenie mają dopuszczalne rozwiązania podstawowe, czyli tak zwane plany wsparcia. Rozwiązanie podstawowe, w którym co najmniej jedna ze zmiennych głównych jest równa zero, nazywamy zdegenerowanym.

Wypukłe zbiory punktów

Ogólna właściwość definiująca, która odróżnia wielokąt wypukły od niewypukłego, polega na tym, że jeśli weźmiesz dowolne dwa jego punkty i połączysz je z odcinkiem, to cały segment będzie należeć do tego wielokąta. Ta właściwość może być traktowana jako definicja wypukłego zbioru punktów.

Zbiór punktów nazywamy wypukłym jeśli wraz z dowolnymi dwoma punktami zawiera cały odcinek łączący te punkty.

Zbiory wypukłe mają ważne nieruchomość: punkt przecięcia (część wspólna) dowolnej liczby zbiorów wypukłych jest zbiorem wypukłym.

Wśród punktów zbioru wypukłego można wyróżnić punkty wewnętrzne, brzegowe i narożne.

Punkt zbioru nazywamy wewnętrznym, jeśli część jego otoczenia zawiera punkty tylko tego zbioru.

Punkt zbioru nazywamy granicą, jeśli któreś z jego sąsiedztw zawiera zarówno punkty należące do danego zbioru, jak i punkty do niego nienależące.

Szczególnie interesujące w problemach programowania liniowego są punkty narożne. Punkt zbioru nazywa się kątowy(lub ekstremalny), jeśli nie jest wewnętrzny dla żadnego segmentu, który w całości należy do danego zestawu.

na ryc. 2.4 pokazuje przykłady różnych punktów wielokąta: wewnętrznego (punkt M), granicznego (punkt N) i narożnego (punkty A, B, C, D, E). Punkt A jest kątowy, ponieważ dla dowolnego segmentu należącego w całości do wielokąta, na przykład segmentu AP, nie jest on wewnętrzny; punkt A jest wewnętrzny względem odcinka KL, ale odcinek ten nie należy w całości do wielokąta.

W przypadku zbioru wypukłego punkty narożne zawsze pokrywają się z wierzchołkami wielokąta (wielościanu), podczas gdy w przypadku zbioru niewypukłego nie jest to konieczne. Zbiór punktów nazywamy zamkniętym, jeśli zawiera wszystkie swoje punkty brzegowe. Zbiór punktów nazywa się ograniczony, jeśli istnieje kula (okrąg) o promieniu skończonej długości, wyśrodkowana w dowolnym punkcie zbioru, który całkowicie zawiera dany zbiór; w przeciwnym razie zbiór nazywany jest nieograniczonym.

Wypukły domknięty zbiór punktów na płaszczyźnie, który ma skończoną liczbę punktów narożnych, nazywany jest wypukłym wielokątem, jeśli jest ograniczony, a wypukłym regionem wielokątnym, jeśli jest nieograniczony.

Znaczenie geometryczne rozwiązań nierówności, równań i ich układów

Rozważmy rozwiązania nierówności.

Stwierdzenie 1. Zbiór rozwiązań nierówności z dwiema zmiennymi a11x1+a12x2<=b1 является одной из двух полуплоскостей, на которые вся плоскость делится прямой a11x1+a12x2=b1 , включая и эту прямую, а другая полуплоскость с той же прямой есть множество решений неравен­ства a11x1+a12x2>=b1.

Aby określić żądaną półpłaszczyznę (górną lub dolną), zaleca się ustawienie dowolnego punktu kontrolnego, który nie leży na jej granicy - konstruowanej linii. Jeśli nierówność jest spełniona w punkcie kontrolnym, to jest również spełniona we wszystkich punktach półpłaszczyzny zawierającej punkt kontrolny i nie jest spełniona we wszystkich punktach drugiej półpłaszczyzny. I odwrotnie, jeśli nierówność nie jest spełniona w punkcie kontrolnym, to nie jest spełniona we wszystkich punktach półpłaszczyzny zawierającej punkt kontrolny i jest spełniona we wszystkich punktach drugiej półpłaszczyzny. Jako punkt kontrolny wygodnie jest przyjąć początek współrzędnych O (0; 0), który nie leży na konstruowanej linii.

Rozważ zbiór rozwiązań systemów nierówności.

Twierdzenie 2. Zbiorem rozwiązań kompatybilnego układu m nierówności liniowych dwóch zmiennych jest wielokąt wypukły (lub wielokąt wypukły).

Każda z nierówności, zgodnie ze Stwierdzeniem 1, definiuje jedną z półpłaszczyzn, która jest wypukłym zbiorem punktów. Zbiorem rozwiązań wspólnego układu nierówności liniowych są punkty należące do półpłaszczyzn rozwiązań wszystkich nierówności, tj. należą do ich skrzyżowania. Zgodnie ze stwierdzeniem o przecięciu zbiorów wypukłych, zbiór ten jest wypukły i zawiera skończoną liczbę punktów narożnych, tj. jest wypukłym wielokątem (wypukłym obszarem wielokątnym).

Współrzędne punktów narożnych - wierzchołki wielokąta znajdują się jako współrzędne punktów przecięcia odpowiednich prostych.

Podczas konstruowania obszarów rozwiązań dla układów nierówności mogą wystąpić również inne przypadki: zbiór rozwiązań jest wypukłym regionem wielokątnym (ryc. 2.9, a); jeden punkt (ryc. 2.9, b); zbiór pusty, gdy system nierówności jest niespójny (ryc. 2.9, c).

5 . Geometryczna metoda rozwiązywania problemów LP

optymalne rozwiązanie problemu LP

Twierdzenie 1. Jeśli problem LP ma rozwiązanie optymalne, to funkcja liniowa przyjmuje maksymalną wartość w jednym z wierzchołków wielościanu rozwiązania. Jeśli funkcja liniowa przyjmuje wartość maksymalną w więcej niż jednym punkcie narożnym, to przyjmuje ją w dowolnym punkcie, który jest wypukłą liniową kombinacją tych punktów.

Twierdzenie wskazuje główny sposób rozwiązywania problemów LP. Rzeczywiście, zgodnie z tym twierdzeniem, zamiast badać nieskończony zbiór możliwych rozwiązań, aby znaleźć wśród nich pożądane rozwiązanie optymalne, konieczne jest zbadanie tylko skończonej liczby punktów narożnych wielościanu rozwiązania.

Poniższe twierdzenie jest poświęcone analitycznej metodzie znajdowania punktów narożnych.

Twierdzenie 2. Każdemu dopuszczalnemu rozwiązaniu podstawowemu problemu LP odpowiada punkt narożny wielościanu rozwiązania i odwrotnie, każdemu punktowi narożnemu wielościanu rozwiązania odpowiada dopuszczalne rozwiązanie podstawowe.

Z Twierdzeń 1 i 2 natychmiast wynika ważny wniosek: jeśli problem LP ma rozwiązanie optymalne, to pokrywa się z co najmniej jednym z jego dopuszczalnych rozwiązań podstawowych.

Więc, optimum funkcji liniowej problemu LP należy szukać wśród skończonej liczby jego dopuszczalnych rozwiązań podstawowych.

Tak więc zbiorem dopuszczalnych rozwiązań (wielościanu rozwiązań) problemu LP jest wielościan wypukły (lub obszar wielościanu wypukłego), a optymalne rozwiązanie problemu znajduje się co najmniej w jednym z punktów narożnych wielościanu rozwiązania.

Rozważ problem w standardowej postaci z dwiema zmiennymi (P = 2).

Niech geometryczną reprezentacją systemu ograniczeń będzie wielokąt ABCDE(Rys. 4.1). Należy znaleźć wśród punktów tego wielokąta taki punkt, w którym funkcja liniowa F=c1x1+c2x2 przyjmuje wartość maksymalną (lub minimalną).

Rozważ tzw linia poziomu funkcja liniowa F, tj. linia, wzdłuż której ta funkcja przyjmuje tę samą ustaloną wartość A, tj. F = A, lub c1x1+c2x2=a.

Na wielokącie rozwiązania znajdź punkt, przez który przechodzi linia poziomu funkcji F z największym (jeśli funkcja liniowa jest maksymalizowana) lub najmniejszym (jeśli jest minimalizowana) poziomem.

Równanie linii poziomu funkcji c1x1+c2x2=a jest równaniem prostej. Na różnych poziomach A linie poziomu są równoległe, ponieważ ich nachylenia są określone tylko przez stosunek współczynników c1 i c2, a zatem są równe. Więc linie poziomu funkcji F – są to swoiste „równoległości”, zwykle usytuowane pod kątem do osi współrzędnych.

Ważną właściwością linii poziomu funkcji liniowej jest to, że przy równoległym przesunięciu linii w jednym kierunku poziom tylko wzrasta, a przy przesunięciu w drugim kierunku tylko maleje. Wektor c=(c1,c2) ​​​​począwszy od początku układu współrzędnych wskazuje kierunek najszybszego wzrostu funkcji F. Linia poziomu funkcji liniowej jest prostopadła do wektora c=(c1,c2).

Kolejność graficznego rozwiązania problemu LP:

1. Skonstruuj wielokąt rozwiązania.

2. Skonstruuj wektor c = (c1, c2) i narysuj dla niego linię poziomu funkcji liniowej F, na przykład F=0.

3. Przesunięcie równoległe prostej F=0 w kierunku wektora c(-c) w celu znalezienia punktu Amax(Bmin), w którym F osiąga swoje maksimum (minimum).

1. Rozwiązując wspólnie równania prostych przecinających się w optymalnym punkcie, znajdź jego współrzędne.

2. Oblicz Fmax(Fmin).

Komentarz. Punkt minimalny to punkt „wejścia” do wielokąta decyzyjnego, a punkt maksymalny to punkt „wyjścia” z wielokąta.

6. Ogólna idea metody simplex. Interpretacja geometryczna

Metoda graficzna ma zastosowanie do bardzo wąskiej klasy problemów programowania liniowego: może skutecznie rozwiązywać problemy zawierające nie więcej niż dwie zmienne. Rozważono główne twierdzenia programowania liniowego, z których wynika, że ​​jeżeli problem programowania liniowego ma rozwiązanie optymalne, to odpowiada co najmniej jednemu wierzchołkowi wielościanu rozwiązania i pokrywa się co najmniej z jednym z dopuszczalnych rozwiązań podstawowych system ograniczeń. Wskazano sposób rozwiązania dowolnego problemu programowania liniowego: wyliczenie skończonej liczby możliwych rozwiązań podstawowych układu ograniczeń i wybranie spośród nich tego, na podstawie którego funkcja celu podejmuje optymalną decyzję. Geometrycznie odpowiada to wyliczeniu wszystkich punktów narożnych wielościanu rozwiązania. Takie wyliczenie ostatecznie doprowadzi do rozwiązania optymalnego (jeśli takie istnieje), ale jego praktyczna realizacja wiąże się z ogromnymi trudnościami, gdyż dla rzeczywistych problemów liczba wykonalnych rozwiązań podstawowych, choć skończona, może być niezwykle duża.

Liczbę dopuszczalnych rozwiązań podstawowych do wyliczenia można zmniejszyć, jeśli wyliczenie przeprowadza się nie w sposób losowy, ale uwzględniając zmiany funkcji liniowej, tj. dążenie do tego, aby każde kolejne rozwiązanie było „lepsze” (a przynajmniej „nie gorsze”) od poprzedniego pod względem wartości funkcji liniowej (zwiększanie jej przy znajdowaniu maksimum, zmniejszanie przy znajdowaniu minimum) . Takie wyliczenie pozwala zredukować liczbę kroków w poszukiwaniu optimum. Wyjaśnijmy to na przykładzie graficznym.

Niech obszar możliwych rozwiązań będzie reprezentowany przez wielokąt ABCDE. Załóżmy, że jest to jego punkt narożny A odpowiada pierwotnemu dopuszczalnemu rozwiązaniu podstawowemu. Losowe wyliczenie musiałoby wypróbować pięć wykonalnych podstawowych rozwiązań odpowiadających pięciu punktom narożnym wielokąta. Jednak rysunek pokazuje, że po szczycie A korzystne, aby przejść do następnego szczytu W, a następnie do optymalnego punktu Z. Zamiast pięciu, pokonano tylko trzy wierzchołki, konsekwentnie poprawiając funkcję liniową.

Idea sekwencyjnego doskonalenia rozwiązania stała się podstawą uniwersalnej metody rozwiązywania problemów programowania liniowego - metoda simplex lub metoda sukcesywnego doskonalenia planu.

Geometryczny sens metody simplex polega na sekwencyjnym przejściu z jednego wierzchołka wielościanu z więzami (zwanego początkowym) do sąsiedniego, w którym funkcja liniowa przyjmuje najlepszą (przynajmniej nie najgorszą) wartość w stosunku do cel problemu; aż do znalezienia rozwiązania optymalnego – wierzchołka, w którym osiągana jest optymalna wartość funkcji celu (jeżeli problem ma skończone optimum).

Metoda simplex została po raz pierwszy zaproponowana przez amerykańskiego naukowca J. Danziga w 1949 r., Ale już w 1939 r. Idee metody zostały opracowane przez rosyjskiego naukowca L.V. Kantorowicz.

Metoda simplex, która pozwala rozwiązać dowolny problem programowania liniowego, jest uniwersalna. Obecnie służy do obliczeń komputerowych, ale proste przykłady z wykorzystaniem metody simplex można również rozwiązywać ręcznie.

Aby wdrożyć metodę simplex - sukcesywnego ulepszania rozwiązania - konieczne jest opanowanie trzy główne elementy:

metoda określania dowolnego początkowego wykonalnego podstawowego rozwiązania problemu;

zasada przejścia do najlepszego (dokładniej nie najgorszego) rozwiązania;

kryterium sprawdzania optymalności znalezionego rozwiązania.

Aby skorzystać z metody simplex, problem programowania liniowego należy sprowadzić do postaci kanonicznej, tj. układ ograniczeń należy przedstawić w postaci równań.

Literatura wystarczająco szczegółowo opisuje: znajdowanie wstępnego planu odniesienia (początkowego możliwego rozwiązania podstawowego), również metodą sztucznej bazy, znajdowanie optymalnego planu odniesienia, rozwiązywanie problemów z wykorzystaniem tablic simplex.

7 . Algorytm metody simplex.

Rozważmy rozwiązanie LLP metodą simplex i przedstawmy je w odniesieniu do problemu maksymalizacji.

1. W zależności od stanu problemu tworzony jest jego model matematyczny.

2. Skonstruowany model jest konwertowany do postaci kanonicznej. W takim przypadku może się wyróżniać podstawa ze wstępnym planem referencyjnym.

3. Model kanoniczny problemu jest zapisany w postaci tablicy simplex, tak że wszystkie wyrazy swobodne są nieujemne. Jeśli wybrano początkowy plan referencyjny, przejdź do kroku 5.

Tablica simplex: układ równań restrykcyjnych i funkcja celu są wprowadzane w postaci wyrażeń rozwiązanych względem bazy początkowej. Linia, w której wprowadzane są współczynniki funkcji celu F, nazywana jest linią F lub linią funkcji celu.

4. Początkowy plan odniesienia znajduje się wykonując przekształcenia simpleksowe z dodatnimi elementami rozdzielczości odpowiadającymi minimalnym stosunkom simpleksowym i nie uwzględniając znaków elementów rzędu F. Jeżeli w trakcie przekształceń występuje wiersz 0, którego wszystkie elementy, z wyjątkiem wyrazu wolnego, są zerami, to układ restrykcyjnych równań problemu jest niespójny. Jeżeli istnieje rząd 0, w którym poza wyrazem wolnym nie ma innych elementów dodatnich, to układ równań restrykcyjnych nie ma rozwiązań nieujemnych.

Nazwiemy redukcję układu (2.55), (2.56) do nowej podstawy transformacja simplex . Jeśli przekształcenie simplex uznać za formalną operację algebraiczną, to można zauważyć, że w wyniku tej operacji następuje redystrybucja ról między dwiema zmiennymi wchodzącymi w skład pewnego układu funkcji liniowych: jedna zmienna przechodzi z zależnej w niezależną, a druga odwrotnie – z niezależnej na zależną. Ta operacja jest znana w algebrze jako Etap eliminacji Jordana.

5. Znaleziony początkowy plan podstawowy jest sprawdzany pod kątem optymalności:

a) jeśli w wierszu F nie ma elementów ujemnych (nie licząc terminu wolnego), to plan jest optymalny. Jeśli nie ma zer, to plan optymalny jest unikalny; jeśli jest co najmniej jedno zero, to istnieje nieskończona liczba planów optymalnych;

b) jeśli w wierszu F znajduje się co najmniej jeden element ujemny, który odpowiada kolumnie elementów niedodatnich, to;

c) jeśli w wierszu F jest co najmniej jeden element ujemny, aw jego kolumnie co najmniej jeden element dodatni, to możemy przełączyć się na nowy plan odniesienia, który jest bliższy optymalnemu. Aby to zrobić, określona kolumna musi być przypisana jako rozdzielcza, przez minimalny współczynnik simpleks, znajdź wiersz rozdzielczy i wykonaj transformację simpleksową. Uzyskany podstawowy plan jest ponownie sprawdzany pod kątem optymalności. Opisany proces jest powtarzany, aż do uzyskania optymalnego planu lub do momentu, gdy problem stanie się nierozwiązywalny.

Kolumna współczynników dla zmiennej zawartej w bazie nazywa się rozdzielczą. Zatem wybierając zmienną wprowadzoną do bazy (lub wybierając kolumnę rozstrzygającą) przez ujemny element wiersza F, zapewniamy, że funkcja F rośnie .

Nieco trudniejsze jest określenie zmiennej, która ma zostać wykluczona z podstawy. W tym celu tworzą stosunki wolnych członków do dodatnich elementów kolumny rozdzielczej (takie relacje nazywane są simpleksami) i znajdują wśród nich najmniejszą, która określa wiersz (rozdzielczy) zawierający zmienną wykluczoną. Wybór zmiennej do wykluczenia z bazy (lub wybór ciągu rozstrzygającego) zgodnie z minimalnym współczynnikiem simplex gwarantuje, jak już ustalono, dodatniość składowych bazowych w nowym układzie referencyjnym.

W kroku 3 algorytmu zakłada się, że wszystkie elementy kolumny wyrazów wolnych są nieujemne. Wymóg ten nie jest obowiązkowy, ale jeśli jest spełniony, to wszystkie kolejne przekształcenia simpleksowe są wykonywane tylko z dodatnimi elementami rozdzielczości, co jest wygodne w obliczeniach. Jeśli w kolumnie wolnych członków występują liczby ujemne, wówczas element rozstrzygający wybiera się w następujący sposób:

1) spójrz na linię odpowiadającą pewnemu ujemnemu elementowi swobodnemu, na przykład t-wierszowi, i wybierz w nim dowolny ujemny element, a odpowiadająca mu kolumna zostanie uznana za dopuszczającą (zakładamy, że ograniczenia problemu są zgodne );

2) uzupełnić stosunki elementów kolumny wolnych członków do odpowiednich elementów kolumny rozdzielczej, które mają te same znaki (stosunki simplex);

3) wybierz najmniejszą z relacji simplex. Określi ciąg uprawnień. Niech to będzie np. R-linia;

4) na przecięciu rozstrzygających kolumn i wierszy zostaje znaleziony element rozstrzygający. Jeśli element łańcucha y okazał się rozdzielczy, to po przekształceniu simpleksowym wolny element tego ciągu stanie się dodatni. W przeciwnym razie w następnym kroku wiersz t jest ponownie adresowany. Jeśli problem jest rozwiązywalny, to po określonej liczbie kroków w kolumnie wolnych terminów nie będzie żadnych negatywnych elementów.

8. Metoda macierzy odwrotnych

Rozważ LP w postaci:

A jest macierzą ograniczeń;

C=(c1,c2,…,cn)–wektor–wiersz;

X=(x1,x2,…,xn) – zmienne;

jest wektorem prawej strony.

Zakładamy, że wszystkie równania są liniowo niezależne, tj. ranga(a)=m. W tym przypadku podstawą jest podrzędny rzędu macierzy A. Oznacza to, że istnieje co najmniej jedna podmacierz B rzędu m taka, że ​​|B|<>0. Wszystkie niewiadome odpowiadające B nazywane są podstawowymi. Wszystkie inne są bezpłatne.

Niech B będzie pewną bazą. Wtedy permutując kolumny macierzy A zawsze można doprowadzić A do postaci A=(B|N),

gdzie N jest podmacierzą składającą się z kolumn macierzy A, które nie należą do bazy. W ten sam sposób można podzielić wektor x na – wektor zmiennych podstawowych i.

Każde rozwiązanie problemu (1) spełnia warunek A*x=b, w związku z czym układ przyjmuje następującą postać:

Ponieważ |B|<>0, to istnieje macierz odwrotna. Mnożąc przez odwrotność po lewej stronie, otrzymujemy:

- wspólna decyzja.

Rozwiązaniem podstawowym (ze względu na bazę B) jest szczególne rozwiązanie problemu (2) otrzymane pod warunkiem. Wtedy jest to jednoznacznie określone.

Podstawowym rozwiązaniem jest tzw wykonalny, Jeśli.

Podstawa odpowiadająca wdrożonemu rozwiązaniu podstawowemu. zwany wykonalna podstawa. Podstawowe rozwiązanie nazywa się zdegenerowanym, jeśli wektor ma zerowe składowe.

Rozwiązanie ogólne zawiera wszystkie istniejące rozwiązania. Wróćmy do funkcji celu. Wprowadzamy Cb-współczynniki przed podstawowymi zmiennymi, Cn-reszta.

W ten sposób otrzymujemy. Podstawiamy z rozwiązania ogólnego:

Oświadczenie. Kryterium optymalności dla rozwiązania podstawowego.

Powiedzmy. Wtedy rozwiązanie podstawowe jest optymalne. Jeżeli, to rozwiązanie podstawowe nie jest optymalne.

Dokumentacja: Zostawiać. Rozważ podstawowe rozwiązanie, .

Zatem jest wartością funkcji celu dla rozwiązania podstawowego.

Niech będzie inne rozwiązanie: (Xb,Xn).

Potem patrzymy

Zatem podstawowym rozwiązaniem jest min. Niech przeciwnie, nie trzymaj, tj. istnieje.

Wtedy istnieje rozwiązanie, dla którego wartość funkcji celu będzie mniejsza niż wartość funkcji celu dla rozwiązania podstawowego.

Niech odpowiada wolnej zmiennej Xi:Xj, przypisz wartość i wprowadź ją do bazy, a następnie wyprowadź inną zmienną i nazwij ją wolną.

Jak ustalić? Wszystkie wolne zmienne z wyjątkiem zmiennej nadal mają wartość 0.

Następnie w rozwiązaniu ogólnym, gdzie.

Wyciągamy: - warunek konieczny.

Podstawowe rozwiązanie nazywa się regularnym if. Wyprowadzamy zmienną z bazy. Przy nowym rozwiązaniu funkcja celu maleje, ponieważ

Algorytm:

1. Problem LP w postaci standardowej.

2. Pozostawiamy równania liniowo niezależne.

3. Znajdź macierz B taką, że |B|<>0 i podstawowe rozwiązanie.

obliczamy:

jeśli, to istnieje rozwiązanie optymalne - jest to rozwiązanie podstawowe;

jeśli, to znajdziemy komponent, podłącz go, w ten sposób znajdziemy inne rozwiązanie; – przy której jedna ze zmiennych podstawowych =0. Odrzucamy tę zmienną z bazy, wpisujemy xi. Otrzymaliśmy nową bazę B2 sprzężoną z bazą B1. Następnie ponownie obliczamy.

1. Jeśli istnieje rozwiązanie optymalne, to po skończonej liczbie kroków je otrzymamy.

Geometrycznie procedura jest interpretowana jako przejście od punktu narożnego do sprzężonego punktu narożnego wzdłuż granicy zbioru X, zbioru rozwiązań problemu. Ponieważ istnieje skończona liczba punktów narożnych, a ścisłe zmniejszenie funkcji F(x) zabrania dwukrotnego przejścia przez ten sam skrajny punkt, to jeśli istnieje rozwiązanie optymalne, to po skończonej liczbie kroków je otrzymamy.

9. Ekonomiczna interpretacja problemu, dualny problem wykorzystania zasobów

Zadanie. Do produkcji dwóch rodzajów produktów P1 i P2 stosuje się cztery rodzaje zasobów S1, S2, S3, S4. Przy danych zapasach zasobów liczba jednostek zasobów wydanych na wytworzenie jednostki produkcji. Zysk uzyskany z jednostki produkcji P1 i P2 jest znany. Konieczne jest sporządzenie planu produkcji produktów, w których zysk z jego sprzedaży będzie maksymalny.

ZadanieI(oryginalny):

F=c1x1+c2x2+…+CnXn->max z ograniczeniami:

oraz warunek nieujemności x1>=0, x2>=0,…,Xn>=0

Sporządzić taki plan produkcji X=(x1,x2,…,Xn), w którym zysk (przychód) ze sprzedaży produktów będzie maksymalny, pod warunkiem, że zużycie zasobów na każdy rodzaj produktu nie przekroczy dostępnych dyby

ZadanieII(podwójny)

Z=b1y1+b2y2+…+BmYm->min

z ograniczeniami:

oraz warunek nieujemności

y1>=0, y2>=0,…,yn>=0.

Znajdź taki zbiór cen (szacunków) zasobów Y=(y1,y2,…,yn), przy którym całkowity koszt zasobów będzie minimalny, pod warunkiem, że koszt zasobów w produkcji każdego rodzaju produktu będzie nie mniej niż zysk (przychód) ze sprzedaży tych produktów

W powyższym modelu bi(i=1,2,…,m) oznacza zasób zasobu Si; aij- liczba jednostek zasobów Si zużytych w produkcji jednostki produkcji Pj(j=1,2,…,n); cj- zysk (przychód) ze sprzedaży jednostki produkcji Pj (lub cena produkcji Pj) .

Załóżmy, że jakaś organizacja zdecydowała się na zakup zasobów przedsiębiorstwa S1,S2,…,Sm i konieczne jest ustalenie optymalnych cen tych zasobów y1,y2,…,ym. Jest oczywiste, że organizację zakupową interesuje fakt, że koszty wszystkich zasobów Z w ilościach b1,b2,…,bm przy cenach odpowiednio y1,y2,…,ym były minimalne, tj. Z=b1,y1+b2y2+…+bmym->min.

Z drugiej strony przedsiębiorstwo sprzedające zasoby jest zainteresowane tym, aby uzyskiwany przychód był nie mniejszy niż kwota, którą przedsiębiorstwo może uzyskać przetwarzając zasoby na gotowe produkty.

A11 jednostek zasobu S1, a21 jednostek zasobu S2,…., aj1 jednostek zasobu Si1 ,……, am1 jednostek zasobu Sm wydaje się na wytworzenie jednostki produktu P1 po cenie y1,y1,…,yi ,…,ym, odpowiednio. Zatem, aby spełnić wymagania sprzedawcy, koszt zasobów zużytych do wytworzenia jednostki produkcji P1 musi wynosić co najmniej jej cenę c1, tj. a11y1+a21y2+…+am1ym>=c1.

Podobnie można komponować ograniczenia w postaci nierówności dla każdego rodzaju produktu P1,P2,…Pn. W prawej części tabeli podano model ekonomiczno-matematyczny oraz sensowną interpretację tak otrzymanego problemu dualnego II.

Ceny surowców y1,y1,…,yi,…,ym otrzymały w literaturze ekonomicznej różne nazwy: rachunkowość, niejawna, cień . Znaczenie tych imion jest takie warunkowy , „fałszywe” ceny. W przeciwieństwie do cen „zewnętrznych” c1,c2,…,cn dla produktów, które są z reguły znane przed rozpoczęciem produkcji, ceny surowców y1,y2,…,ym Czy wewnętrzny , ponieważ nie są ustawiane z zewnątrz, ale są ustalane bezpośrednio w wyniku rozwiązania problemu, dlatego często nazywane są szacunki zasoby.

10. Wzajemnie dualne problemy LP i ich własności

Rozważmy formalnie dwa problemy I i II programowania liniowego przedstawione w tabeli, abstrahując od sensownej interpretacji parametrów zawartych w ich modelach ekonomicznych i matematycznych.

Oba zadania mają następujące znaczenie nieruchomości:

1. W jednym zadaniu szukają maksimum funkcji liniowej, w drugim minimum.

2. Współczynniki dla zmiennych w funkcji liniowej jednego problemu są wolnymi członkami układu ograniczeń w innym.

3. Każdy z problemów jest podany w postaci standardowej, aw problemie maksymalizacji wszystkie nierówności postaci "<=", а в задаче минимизации – все неравенства вида ">=".

4. Macierze współczynników dla zmiennych w układach ograniczeń obu problemów są transponowane do siebie.

5. Liczba nierówności w układzie ograniczeń jednego problemu jest taka sama, jak liczba zmiennych w innym problemie.

6. W obu problemach zachowane są warunki nieujemności zmiennych.

Komentarz. Jeśli warunek nieujemności zostanie nałożony na j-tą zmienną pierwotnego problemu, to j-tym ograniczeniem problemu dualnego będzie nierówność, ale jeśli j-ta zmienna może przyjmować zarówno wartości dodatnie, jak i ujemne, to j-tym ograniczeniem problemu dualnego będzie równanie; ograniczenia pierwotnego problemu i zmienne problemu dualnego są podobnie powiązane.

Dwa problemy I i II programowania liniowego o wskazanych własnościach nazywane są problemami symetrycznymi wzajemnie dualnymi. Poniżej dla uproszczenia będziemy je po prostu nazywać podwójne zadania.

Każdy problem LP może być powiązany z jego podwójnym problemem.

11. Algorytm kompilacji problemu dualnego:

1. Doprowadź wszystkie nierówności układu ograniczeń pierwotnego problemu do tego samego znaczenia: jeśli w pierwotnym problemie poszukuje się maksimum funkcji liniowej, wówczas wszystkie nierówności układu ograniczeń są zredukowane do postaci „<=", а если минимум – к виду ">=". Dla tych nierówności, w których ten wymóg nie jest spełniony, pomnóż przez -1.

2. Skompiluj rozszerzoną macierz układu A, która zawiera macierz współczynników dla zmiennych, kolumnę wolnych członków układu ograniczeń i wiersz współczynników dla zmiennych w funkcji liniowej.

3. Znajdź macierz transponowaną do macierzy A .

4. Sformułuj problem dualny na podstawie otrzymanej macierzy oraz warunki nieujemności zmiennych: tworzą funkcję celu problemu dualnego, przyjmując jako współczynniki zmiennych wolne elementy układu ograniczeń problemu pierwotnego; ułożyć układ więzów dla problemu dualnego, przyjmując elementy macierzy jako współczynniki zmiennych, a współczynniki zmiennych w funkcji celu pierwotnego problemu jako elementy swobodne i zapisać nierówności o przeciwnym znaczeniu; zapisz warunek nieujemności zmiennych problemu dualnego.

12. Pierwsze twierdzenie o dualności

Związek między optymalnymi rozwiązaniami problemów dualnych ustalany jest za pomocą twierdzeń o dualności.

Wystarczający znak optymalności.

Jeśli X*=(x1*,x2*,…,xn*) I Y*=(y1*,y2*,…,ym*) są dopuszczalnymi rozwiązaniami wzajemnie dualnych problemów, dla których zachodzi równość,

wtedy jest optymalnym rozwiązaniem pierwotnego problemu I i jest optymalnym rozwiązaniem dualnego problemu II.

Oprócz wystarczającego kryterium optymalności wzajemnie dualnych problemów istnieją inne ważne relacje między ich rozwiązaniami. Przede wszystkim nasuwają się pytania: czy zawsze istnieje równoczesne optymalne rozwiązanie dla każdej pary problemów dualnych; czy to możliwe, że jeden z podwójnych problemów ma rozwiązanie, a drugi nie. Na te pytania odpowiada następujące twierdzenie.

Pierwsze (główne) twierdzenie o dualności. Jeśli jeden z wzajemnie dualnych problemów ma optymalne rozwiązanie, to drugi też, a optymalne wartości ich funkcji liniowych to:

Fmaks = Żmin lub F(X*)=Z(Y*) .

Jeżeli funkcja liniowa jednego z problemów nie jest ograniczona, to warunki drugiego problemu są sprzeczne (problem nie ma rozwiązania).

Komentarz. Stwierdzenie przeciwne do drugiej części głównego twierdzenia o dualności nie jest prawdziwe w przypadku ogólnym, tj. z faktu, że warunki pierwotnego problemu są sprzeczne, nie wynika, że ​​funkcja liniowa problemu dualnego nie jest ograniczona.

Ekonomiczne znaczenie pierwszego twierdzenia o dualności.

Plan produkcji X*=(x1*,x2*,…,xn*) oraz zbiór cen (szacunków) zasobów Y*=(y1*,y2*,…,ym*) okazują się optymalne wtedy i tylko wtedy, gdy zysk (przychód) z produktu, znaleziony przy cenach „zewnętrznych” (znanych z góry) c1,c2,…,cn, jest równy kosztowi zasobów przy „wewnętrznych” (określonych tylko z rozwiązania problemu) ceny y1 ,y2,…,ym. Dla wszystkich innych planów X I Y obu zadań, zysk (przychód) z produktu jest zawsze mniejszy (lub równy) kosztowi zasobów.

Ekonomiczne znaczenie pierwszego twierdzenia o dwoistości można również interpretować następująco: przedsiębiorstwu nie zależy na tym, aby wytwarzać produkty zgodnie z optymalnym planem X*=(x1*,x2*,…,xn*) i uzyskać maksymalny zysk ( przychód) Fmax lub sprzedać zasoby po optymalnych cenach Y* =(y1*,y2*,…,ym*) i zwrócić ze sprzedaży równą jej minimalny koszt środków Zmin.

13. Drugie twierdzenie o dualności

Niech dane będą dwa wzajemnie dualne problemy. Jeżeli każdy z tych problemów jest rozwiązywany metodą simplex, to konieczne jest sprowadzenie ich do postaci kanonicznej, dla której konieczne jest wprowadzenie do systemu ograniczeń problemu I (w skrócie) T zmienne nieujemne, ale do układu ograniczeń problemu II () – N zmienne nieujemne, gdzie i(j) to numer nierówności, w której wprowadzona jest dodatkowa zmienna.

Układy ograniczeń dla każdego z wzajemnie dualnych problemów będą miały postać:

Ustalmy zgodność między początkowymi zmiennymi jednego z podwójnych problemów a dodatkowymi zmiennymi drugiego problemu (tabela).

Twierdzenie. Dodatnie (niezerowe) składowe optymalnego rozwiązania jednego z wzajemnie dualnych problemów odpowiadają zerowym składowym optymalnego rozwiązania drugiego problemu, tj. dla dowolnego i=1,2,…,m u j=1,2,…,n: jeśli X*j>0, to; Jeśli , wtedy i podobnie,

Jeśli następnie ; Jeśli następnie.

Z twierdzenia tego wynika ważny wniosek, że wprowadzona zgodność między zmiennymi wzajemnie dualnych problemów po osiągnięciu optimum (tj. na ostatnim etapie rozwiązywania każdego problemu metodą simplex) reprezentuje zgodność między główny(z reguły nie równe zeru) zmienne jednego z problemów dualnych i niezwiązane z rdzeniem(równe zeru) zmienne innego problemu, gdy tworzą dopuszczalne rozwiązania podstawowe.

Drugie twierdzenie o dualności. Składniki optymalnego rozwiązania problemu dualnego są równe wartościom bezwzględnym współczynników przy odpowiednich zmiennych funkcji liniowej pierwotnego problemu, wyrażonych jako mniejsze zmienne jego optymalnego rozwiązania.

Komentarz. Jeżeli w jednym ze wzajemnie dualnych problemów naruszona zostanie jednoznaczność rozwiązania optymalnego, to optymalne rozwiązanie problemu dualnego jest zdegenerowane. Wynika to z faktu, że w przypadku naruszenia jednoznaczności rozwiązania optymalnego problemu pierwotnego, w wyrażeniu funkcji liniowej jego rozwiązania optymalnego względem zmiennych niepodstawowych brakuje przynajmniej jednej ze zmiennych głównych.

14. Obiektywnie określone oceny i ich znaczenie

Składniki optymalnego rozwiązania problemu dualnego nazywane są optymalnymi (podwójnymi) oszacowaniami pierwotnego problemu. Nazwał ich akademik L.V. Kantorowicz obiektywnie uwarunkowane szacunki ( w literaturze nazywane są też dochodami ukrytymi) .

Dodatkowe zmienne pierwotnego problemu I, reprezentujące różnicę między zapasami bi zasobów S1,S2,S3,S4 i ich spożycie, ekspresowe resztki zasobów , oraz dodatkowe zmienne problemu dualnego II reprezentujące różnicę między kosztami zasobów na wytworzenie z nich jednostki produkcji a cenami cj produktów P1,P2 , wyrazić nadwyżka kosztów nad ceną.

Tak więc obiektywnie określone szacunki zasobów określają stopień rzadkości zasobów: zgodnie z optymalnym planem produkcji zasoby rzadkie (tj. W pełni wykorzystane) otrzymują oszacowania niezerowe, a nierzadkie - zerowe. Wartość y*i jest oszacowaniem i-tego zasobu. Im wyższa wartość oszacowania y*i, tym większa rzadkość zasobu. Dla zasobu nierzadkiego y*i=0.

Tak więc tylko opłacalne, nieopłacalne typy produktów mogą mieścić się w optymalnym planie produkcji (chociaż kryterium opłacalności jest tu specyficzne: cena produktu nie przekracza kosztów zasobów zużytych do jego wytworzenia, ale jest dokładnie równa do nich).

Trzecie twierdzenie o dualności . Składniki optymalnego rozwiązania problemu dualnego są równe wartościom pochodnych cząstkowych funkcji liniowej Fmaks(B1, B2,…, bm)zgodnie z odpowiednimi argumentami, tj.

Obiektywnie określone szacunki zasobów pokazują, o ile jednostek pieniężnych zmieni się maksymalny zysk (przychód) ze sprzedaży produktów, gdy stan odpowiedniego zasobu zmieni się o jedną jednostkę.

Podwójne szacunki mogą służyć jako narzędzie do analizy i podejmowania właściwych decyzji w ciągle zmieniającej się branży. Na przykład za pomocą obiektywnie określonych szacunków zasobów można porównać optymalne koszty warunkowe i wyniki produkcji.

Obiektywnie określone szacunki zasobów pozwalają ocenić efekt nie jakichkolwiek, a jedynie stosunkowo niewielkich zmian zasobów. Przy gwałtownych zmianach same oszacowania mogą się różnić, co spowoduje niemożność wykorzystania ich do analizy efektywności produkcji. Na podstawie stosunków obiektywnie wyznaczonych oszacowań można wyznaczyć wyliczone normy substytucji zasobów, przy których trwające wymiany w ramach stabilności oszacowań dualnych nie wpływają na efektywność planu optymalnego. Wniosek. Podwójne wyniki to:

1. Wskaźnik niedoboru zasobów i produktów.

2. Wskaźnik wpływu ograniczeń na wartość funkcji celu.

3. Wskaźnik efektywności produkcji niektórych rodzajów produktów z punktu widzenia kryterium optymalności.

4. Narzędzie do porównywania całkowitych kosztów warunkowych i wyników.

15. Zestawienie zadania transportowego według kryterium kosztów.

TK - problem najbardziej ekonomicznego planu transportu jednorodnego lub wymiennego produktu z punktu produkcji (stacji wyjściowych) do punktów konsumpcji (stacji docelowych) - to najważniejsze prywatne zadanie LP, które ma szerokie zastosowanie praktyczne nie tylko problemy z transportem.

TK wyróżnia się w LP pewnością cech ekonomicznych, cechami modelu matematycznego, obecnością określonych metod rozwiązania.

Najprostsze sformułowanie TOR pod względem kosztów jest następujące: w T punkty wyjścia A1,…,Am to odpowiednio a1,…,am jednostki jednorodnego ładunku (zasobów) do dostarczenia N konsumenci B1,…,Bn w ilościach b1,…,bn jednostek (potrzeb). Znane są koszty transportu Cij transportu jednostki ładunku z i-tego miejsca wyjazdu do j-tego miejsca zużycia.

Należy sporządzić plan transportu, czyli ustalić, ile jednostek ładunku należy wysłać z i-tego miejsca wyjazdu do j-tego miejsca konsumpcji, aby potrzeby zostały w pełni zaspokojone, a suma koszty transportu są minimalne.

Dla jasności warunki TK zostaną przedstawione w formie tabeli, która nazywa się dystrybucja .

Dostawca	Konsument			Zapas ładunków
Potrzebować

Tutaj ilość ładunku przewiezionego z i-tego punktu początkowego do j-tego miejsca docelowego jest równa xij, stan ładunku w i-tym punkcie wyjściowym jest określony wartością ai>=0, a popyt j-tego miejsca przeznaczenia w ładunku wynosi bj>=0 . Zakłada się, że wszystkie xij>=0.

Matryca nazywa się macierz taryf (koszty lub koszty transportu).

Plan zadań transportowych nazywa się macierzą, gdzie każda liczba xij oznacza liczbę jednostek ładunku, które muszą zostać dostarczone z i-tego punktu wyjścia do j-tego miejsca przeznaczenia. Macierz xij jest nazywana macierz ruchu.

Całkowite całkowite koszty związane z realizacją planu transportowego można przedstawić za pomocą funkcji celu

Zmienne xij muszą spełniać ograniczenia dotyczące zapasów, konsumentów i warunki nieujemności:

– ograniczenia dotyczące zapasów (2);

– ograniczenia dla konsumentów (2);

są warunkami nieujemności (3).

Zatem matematycznie problem transportu jest sformułowany w następujący sposób. Dany jest układ ograniczeń (2) pod warunkiem (3) i funkcja celu (1). Wśród zbioru rozwiązań układu (2) należy znaleźć takie rozwiązanie nieujemne, które minimalizuje funkcję (1).

Układ ograniczeń dla problemu (1) - (3) zawiera m + n równań z TN zmienne. Przyjmuje się, że całkowite rezerwy są równe całkowitym potrzebom, tj.

16. Znak rozwiązywalności problemu transportowego

Aby problem transportowy miał dopuszczalne plany, konieczna i wystarczająca jest równość

Istnieją dwa rodzaje zadań transportowych: Zamknięte , w którym całkowita wielkość ładunków dostawców jest równa całkowitemu zapotrzebowaniu konsumentów, oraz otwarty , w którym łączne moce produkcyjne dostawców przewyższają popyt konsumentów lub popyt konsumentów jest większy niż rzeczywiste łączne moce dostawców, tj.

Model otwarty można przekształcić w model zamknięty. Tak więc, jeśli, to fikcyjny (n + 1)-ty cel zostanie wprowadzony do matematycznego modelu problemu transportowego. W tym celu w macierzy zadań przewidziana jest dodatkowa kolumna, dla której zapotrzebowanie jest równe różnicy między całkowitą mocą dostawców a rzeczywistym zapotrzebowaniem konsumentów:

Wszystkie taryfy za dostawę towarów do tego punktu zostaną uznane za równe zeru. W ten sposób otwarty model problemu przekształca się w zamknięty. Dla nowego problemu funkcja celu jest zawsze taka sama, ponieważ koszt dodatkowego transportu wynosi zero. Innymi słowy, fikcyjny konsument nie narusza spójności systemu ograniczeń.

Jeżeli, to wprowadza się fikcyjny (m + 1)-ty punkt wyjścia, do którego przypisany jest zapas ładunku równy.

Ponownie przyjmuje się, że taryfy za dostawę towarów od tego fikcyjnego dostawcy są równe zeru. Do macierzy zostanie dodany jeden wiersz, nie wpłynie to na funkcję celu, a układ ograniczeń problemu stanie się zgodny, czyli możliwe stanie się znalezienie planu optymalnego.

Następujące twierdzenie ma ogromne znaczenie dla problemu transportu.

Twierdzenie. Ranga macierzy problemu transportowego jest o jeden mniejsza od liczby równań, tj. R ( A )= M + N -1.

Z twierdzenia wynika, że ​​każdy układ referencyjny musi mieć (m-1)(n-1) zmiennych wolnych równych zeru oraz m+n-1 zmiennych podstawowych.

Poszukamy planu transportu zadania transportowego bezpośrednio w tabeli dystrybucji. Zakładamy, że jeśli zmienna xij przyjmuje wartość, to zapiszemy tę wartość do odpowiedniej komórki (I,j), ale jeśli xij=0, to komórkę (I,j) pozostawimy wolną. Uwzględnienie twierdzenia o randze macierzy w tablicy dystrybucji plan generalny powinien zawierać m+n-1 zajęte komórki a reszta będzie za darmo.

Te wymagania dotyczące planu podstawowego nie są jedynymi. Plany bazowe muszą spełniać inny wymóg związany z cyklami.

Zestaw komórek macierzy ruchu, w którym dwie i tylko dwie sąsiednie komórki znajdują się w jednym wierszu lub w jednej kolumnie, a ostatnia komórka zestawu znajduje się w tym samym wierszu lub kolumnie co pierwsza, nazywa się zamkniętym cykl .

Graficznie cykl jest zamkniętą linią łamaną, której wierzchołki znajdują się w zajętych komórkach tabeli, a łącza znajdują się tylko w wierszach lub kolumnach. Co więcej, w każdym wierzchołku cyklu znajdują się dokładnie dwa ogniwa, z których jedno znajduje się w rzędzie, a drugie w kolumnie. Jeżeli polilinia tworząca cykl przecina się sama ze sobą, to punkty samoprzecięcia nie są wierzchołkami.

Z zestawem komórek cykli powiązane są następujące ważne właściwości planów zadań transportowych:

1) dopuszczalny plan zadania przewozowego jest odniesieniem wtedy i tylko wtedy, gdy z komórek zajmowanych przez ten plan nie da się utworzyć cyklu;

2) jeśli mamy plan podstawowy, to dla każdej wolnej komórki można utworzyć tylko jeden cykl zawierający tę komórkę i część komórek zajętych.

17. Budowanie początkowej linii bazowej

Reguła narożnika północno-zachodniego.

Aby sporządzić wstępny plan transportu, wygodnie jest zastosować regułę północno-zachodniego rogu, która jest następująca.

Wypełnimy, zaczynając od lewego górnego rogu, umownie zwanego „północno-zachodnim rogiem”, przesuwając się dalej wzdłuż linii w prawo lub w dół kolumny. W komórce (1; 1) wpisujemy mniejszą z liczb a1 i b1, czyli . Jeśli, to pierwsza kolumna jest „zamknięta”, tj. popyt pierwszego konsumenta jest całkowicie zaspokojony. Oznacza to, że dla wszystkich pozostałych komórek pierwszej kolumny ilość ładunku dla .

Jeśli, to pierwsza linia jest podobnie „zamknięta”, tj . Przystępujemy do wypełnienia sąsiedniej komórki (2; 1), do której wchodzimy.

Po wypełnieniu drugiej komórki (1; 2) lub (2; 1) przystępujemy do wypełnienia kolejnej trzeciej komórki w drugim rzędzie lub w drugiej kolumnie. Będziemy kontynuować ten proces, aż na pewnym etapie wyczerpią się zasoby i potrzeby. Ostatnia wypełniona komórka będzie w ostatniej n-tej kolumnie iw ostatnim m-tym wierszu.

Zasada „elementu minimalnego”.

Wstępny plan referencyjny, zbudowany według zasady „rogu północno-zachodniego”, zwykle okazuje się bardzo daleki od optymalnego, ponieważ przy jego ustalaniu nie uwzględnia się kosztów cij. Dlatego w dalszych obliczeniach do uzyskania optymalnego planu potrzebnych będzie wiele iteracji. Liczbę iteracji można zmniejszyć, jeśli plan początkowy jest zbudowany zgodnie z zasadą „minimalnego elementu”. Jego istota polega na tym, że na każdym kroku realizowane jest maksymalne możliwe „przemieszczenie” ładunku do komórki przy minimalnej taryfie cij. Wypełnianie tabeli zaczynamy od komórki, która odpowiada najmniejszemu elementowi cij macierzy taryf. Najmniejsza z liczb ai lub bj jest umieszczana w komórce z najniższą taryfą . Wtedy z rozpatrzenia wyłącza się wiersz odpowiadający dostawcy, którego zapasy zostały całkowicie wyczerpane, lub kolumnę odpowiadającą konsumentowi, którego zapotrzebowanie zostało w pełni zaspokojone. Może się okazać, że należy jednocześnie wykluczyć wiersz i kolumnę, jeśli zapas dostawcy zostanie całkowicie wyczerpany, a zapotrzebowanie konsumenta zostanie całkowicie zaspokojone. Następnie z pozostałych komórek tabeli ponownie wybierana jest komórka z najniższą taryfą i proces dystrybucji zapasów trwa do momentu rozdysponowania wszystkich zapasów i zaspokojenia popytu.

18. Metoda potencjałów

Ogólna zasada wyznaczania optymalnego planu zadania transportowego metodą potencjałów jest podobna do zasady rozwiązywania problemu LP metodą simplex, a mianowicie: najpierw znajduje się podstawowy plan zadania przewozowego, a następnie sukcesywnie ulepszane aż do uzyskania optymalnego planu.

Istota metody potencjalnej jest następująca. Po znalezieniu początkowego referencyjnego planu transportu każdemu dostawcy (w każdym wierszu) przypisywana jest pewna liczba zwana potencjałem dostawcy Ai, a każdemu konsumentowi (w każdej kolumnie) pewna liczba zwana potencjałem konsumenta.

Koszt tony ładunku w punkcie jest równy kosztowi tony ładunku przed transportem + koszt jego transportu: .

Aby rozwiązać problem transportu metodą potencjalną, konieczne jest:

1. Zbuduj podstawowy plan transportu zgodnie z jedną z przedstawionych zasad. Liczba wypełnionych komórek powinna wynosić m+n-1.

2. Oblicz potencjały i odpowiednio dostawców i odbiorców (dla zajętych komórek): . Liczba wypełnionych komórek to m+n-1, a liczba równań to m+n. Ponieważ liczba równań jest o jeden mniejsza od liczby niewiadomych, to jedna z niewiadomych jest wolna i może przyjąć dowolną wartość liczbową. Na przykład, . Pozostałe potencjały dla danego rozwiązania odniesienia są jednoznacznie określone.

3. Sprawdź optymalność, tj. dla wolnych komórek obliczyć wyniki. Jeśli, to transport jest celowy, a plan X jest optymalny - znak optymalności. Jeśli istnieje co najmniej jedna różnica, przejdź do nowego planu referencyjnego. W sensie ekonomicznym wartość charakteryzuje zmianę całkowitych kosztów transportu, jaka nastąpi w wyniku realizacji pojedynczej dostawy przez i-tego dostawcę do j-tego konsumenta. Jeśli, to pojedyncza dostawa doprowadzi do oszczędności w kosztach transportu, jeśli - do ich wzrostu. Dlatego jeśli wśród wolnych kierunków dostaw nie ma kierunków oszczędzających koszty transportu, to wynikowy plan jest optymalny.

4. Spośród liczb dodatnich wybiera się maksimum, zbudowane dla wolnej komórki, której odpowiada cyklowi przeliczania. Po zbudowaniu cyklu dla wybranej wolnej komórki należy przejść do nowego planu referencyjnego. Aby to zrobić, musisz przenieść obciążenia w komórkach skojarzonych z tą wolną komórką w cyklu ponownego obliczania.

a) Każdej z komórek połączonych cyklem z daną wolną komórką przypisany jest określony znak, a ta wolna komórka to „+”, a wszystkie pozostałe komórki (wierzchołki cyklu) to naprzemiennie znaki „–” i „+” . Komórki te będziemy nazywać minusem i plusem.

b) W ujemnych komórkach cyklu znajdujemy minimalną podaż, którą oznaczamy przez. Mniejsza z liczb xij w ujemnych komórkach jest przenoszona do tej wolnej komórki. Jednocześnie liczba ta jest dodawana do odpowiednich liczb w komórkach ze znakiem „+” i odejmowana od liczb w komórkach ujemnych. Komórka, która wcześniej była wolna, zostaje zajęta i wchodzi do planu referencyjnego; a komórka minus, w której znajdowało się minimum liczb xij, jest uważana za wolną i opuszcza plan odniesienia.

W ten sposób wyznaczono nową linię bazową. Przejście od jednej linii bazowej do drugiej opisane powyżej nazywane jest przesunięciem w cyklu ponownego obliczania. Podczas przesuwania w cyklu przeliczania liczba zajętych komórek pozostaje niezmieniona, a mianowicie pozostaje równa m+n-1. Co więcej, jeśli w komórkach ujemnych znajdują się dwie lub więcej identycznych liczb xij, to tylko jedna z tych komórek jest pusta, a pozostałe są zajęte z zerowymi zapasami.

5. Powstały plan referencyjny jest sprawdzany pod kątem optymalności, tj. powtórz wszystkie kroki z punktu 2.

19. Pojęcie programowania dynamicznego.

DP (planowanie) to matematyczna metoda znajdowania optymalnych rozwiązań wieloetapowych (wieloetapowych) problemów. Niektóre z tych problemów naturalnie rozkładają się na oddzielne kroki (etapy), ale są problemy, w których podział musi być wprowadzony sztucznie, aby można go było rozwiązać metodą DP.

Zwykle metody DP optymalizują działanie niektórych sterowanych systemów, których efekt jest szacowany przyłączeniowy, Lub mnożny, funkcja celu. Przyłączeniowy jest funkcją kilku zmiennych f(x1,x2,…,xn), której wartość jest obliczana jako suma niektórych funkcji fj zależnych tylko od jednej zmiennej xj: . Wyrazy addytywnej funkcji celu odpowiadają skutkom decyzji podjętych na poszczególnych etapach kontrolowanego procesu.

Zasada optymalności R. Bellmana.

Sens podejścia zastosowanego w programowaniu dynamicznym polega na zastąpieniu rozwiązania pierwotnego problemu wielowymiarowego ciągiem problemów o niższym wymiarze. Podstawowe wymagania do zadań:

1. przedmiotem badań powinien być system kontrolowany (obiekt) z podanym poprawnym stany i dopuszczalne działy;

2. Zadanie musi umożliwiać interpretację jako proces wieloetapowy, z którego każdy etap polega na przyjęciu rozwiązania O wybór jednej z dopuszczalnych kontroli prowadzących do zmiana stanu systemy;

3. zadanie nie powinno zależeć od liczby kroków i być określone dla każdego z nich;

4. stan systemu na każdym kroku musi być opisany tym samym (kompozycyjnie) zestawem parametrów;

5. kolejny stan, w jakim znajduje się system po wybraniu rozwiązania na k-ty krok, zależy tylko od podanego rozwiązania i stanu początkowego do początku k- krok. Ta właściwość jest najważniejsza z punktu widzenia ideologii programowania dynamicznego i nazywa się brak konsekwencji .

Rozważ problematykę zastosowania modelu programowania dynamicznego w uogólnionej formie. Niech będzie zadanie zarządzania jakimś abstrakcyjnym obiektem, który może znajdować się w różnych stanach. Bieżący stan obiektu będzie identyfikowany za pomocą pewnego zestawu parametrów, które będą oznaczane dalej przez S i nazywane wektor stanu. Zakłada się, że dany jest zbiór S wszystkich możliwych stanów. Zestaw jest również zdefiniowany dla obiektu dopuszczalne kontrole(działania kontrolne) X, który bez utraty ogólności można uznać za zbiór liczbowy. Czynności kontrolne mogą być przeprowadzane w dyskretnych punktach w czasie i kontroli rozwiązanie polega na wybraniu jednej z kontrolek. plan zadania lub strategia zarządzania wywoływany jest wektor x=(x1,x2,…,xn-1), którego składowymi są kontrole wybrane na każdym etapie procesu. W związku z oczekiwanym brak efektu między każdymi dwoma kolejnymi stanami obiektu Sk i Sk+1 istnieje znana zależność funkcjonalna, która obejmuje również wybraną kontrolę: . A więc ustalenie stanu początkowego obiektu i wybranie planu X jednoznacznie określić trajektoria zachowania obiekt.

Sprawność zarządzania na każdym kroku k zależy od aktualnego stanu Sk, wybranej kontroli xk i jest kwantyfikowana za pomocą funkcji fk(xk,Sk), które są sumami addytywna funkcja celu , charakteryzujące ogólną efektywność zarządzania obiektem. ( Notatka , że definicja funkcji fk(xk,Sk) obejmuje zakres dopuszczalnych wartości xk , i ten obszar z reguły zależy od aktualnego stanu Sk). Optymalna kontrola , dla danego stanu początkowego S1 sprowadza się do wyboru takiego planu optymalnego x* , w którym maksymalna ilość wartości fk na odpowiedniej trajektorii.

Główną zasadą programowania dynamicznego jest to, że w każdym kroku należy dążyć nie do izolowanej optymalizacji funkcji fk(xk,Sk), ale wybrać optymalne sterowanie x*k przy założeniu, że wszystkie kolejne kroki są optymalne. Formalnie zasada ta jest realizowana poprzez znajdowanie na każdym kroku k warunkowe sterowanie optymalne , zapewniając najwyższą sprawność całkowitą począwszy od tego kroku, przy założeniu, że aktualnym stanem jest S.

Oznaczmy przez Zk(s) maksymalną wartość sumy funkcji fk przez wszystkie kroki od k zanim P(uzyskiwanych pod optymalną kontrolą na danym odcinku procesu), pod warunkiem, że obiekt na początku etapu k jest w stanie S. Wtedy funkcje Zk(s) muszą spełniać zależność rekurencyjną:

Ten stosunek nazywa się podstawowa relacja rekurencyjna (podstawowe równanie funkcyjne) Programowanie dynamiczne. Realizuje podstawową zasadę programowania dynamicznego, znaną również jako Zasada optymalności Bellmana :

Optymalna strategia sterowania musi spełniać następujący warunek: niezależnie od stanu początkowego sk w k-tym kroku i sterowanie wybrane w tym kroku xk, kolejne kontrole (decyzje zarządcze) powinny być w stosunku do nich optymalne cocmo janyu ,wynikające z decyzji podjętej w kroku k .

Główna relacja pozwala znaleźć funkcje Zk(s) tylko V w połączeniu z stan początkowy co w naszym przypadku jest równość.

Sformułowana powyżej zasada optymalności ma zastosowanie tylko do obiektów sterowania, dla których wybór sterowania optymalnego nie zależy od prehistorii sterowanego procesu, tj. od tego, w jaki sposób system doszedł do stanu obecnego. Ta okoliczność umożliwia dekompozycję problemu i umożliwia jego praktyczne rozwiązanie.

Dla każdego konkretnego zadania równanie funkcjonalne ma swoją specyficzną postać, ale z pewnością musi zachować powtarzalny charakter tkwiący w wyrażeniu (*) i ucieleśniający główną ideę zasady optymalności.

20. Pojęcie modeli gier.

Model matematyczny sytuacji konfliktowej nazywa się gra , strony zaangażowane w konflikt gracze i wyniku konfliktu zwycięski.

Dla każdej sformalizowanej gry przedstawiamy zasady , te. system warunków, który określa: 1) opcje działań graczy; 2) ilość informacji, jakie każdy gracz posiada na temat zachowania partnerów; 3) wypłatę, do której prowadzi każdy zestaw działań. Zazwyczaj zysk (lub stratę) można określić ilościowo; na przykład możesz ocenić stratę na zero, wygraną na jeden, a remis na 1/2. Kwantyfikacja wyników gry nazywa się Zapłata .

Gra nazywa się łaźnia parowa , jeśli zaangażowanych jest dwóch graczy, oraz wiele , jeśli liczba graczy jest większa niż dwóch. Rozważymy tylko gry sparowane. Gra w nich dwóch graczy A I W, których interesy są przeciwne, a przez grę rozumiemy szereg działań ze strony A I W.

Gra nazywa się gra o sumie zerowej Lub antagonistyczny niebo , jeśli zysk jednego z graczy jest równy stracie drugiego, tj. suma wypłat obu stron wynosi zero. Aby wykonać zadanie gry, wystarczy wskazać wartość jednego z nich . Jeśli wyznaczymy A- wygrać jednego z graczy, B – wypłata drugiego, a następnie gra o sumie zerowej b= –A, więc wystarczy wziąć pod uwagę np A.

Wybór i wykonanie jednej z czynności przewidzianych regulaminem nazywa się przenosić gracz. Ruchy mogą być osobisty I losowy . ruch osobisty – jest to świadomy wybór przez gracza jednej z możliwych akcji (np. ruch w grze w szachy). Zestaw możliwych opcji dla każdego osobistego ruchu jest regulowany przez reguły gry i zależy od sumy poprzednich ruchów po obu stronach.

Losowy ruch – jest to losowo wybrana akcja (np. wybranie karty z przetasowanej talii). Aby gra była zdefiniowana matematycznie, reguły gry muszą określać dla każdego losowego ruchu rozkład prawdopodobieństwa możliwe rezultaty.

Niektóre gry mogą składać się tylko z losowych ruchów (tzw. czyste gry losowe) lub tylko z ruchów osobistych (szachy, warcaby). Większość gier karcianych należy do gier typu mieszanego, to znaczy zawiera zarówno ruchy losowe, jak i osobiste. W dalszej części rozważymy tylko osobiste ruchy graczy.

Gry są klasyfikowane nie tylko ze względu na charakter ruchów (osobiste, losowe), ale także ze względu na charakter i ilość informacji dostępnych dla każdego gracza na temat działań innego gracza. Szczególną klasą gier są tzw. „gry z pełną informacją”. Gra z pełną informacją Nazywa się grę, w której każdy gracz przy każdym osobistym ruchu zna wyniki wszystkich poprzednich ruchów, zarówno osobistych, jak i losowych. Przykładami gier z pełnymi informacjami są szachy, warcaby i dobrze znana gra w kółko i krzyżyk. Większość gier o znaczeniu praktycznym nie należy do gier z pełną informacją, ponieważ niewiadoma o działaniach przeciwnika jest zwykle istotnym elementem sytuacji konfliktowych.

Jednym z podstawowych pojęć teorii gier jest pojęcie strategie .

strategia Gracz nazywany jest zbiorem zasad, które określają wybór jego akcji dla każdego osobistego ruchu, w zależności od sytuacji. Zwykle w trakcie gry, przy każdym osobistym ruchu, gracz dokonuje wyboru w zależności od konkretnej sytuacji. Jednak w zasadzie możliwe jest, że wszystkie decyzje są podejmowane przez gracza z wyprzedzeniem (w odpowiedzi na daną sytuację). Oznacza to, że gracz wybrał określoną strategię, którą można podać w formie listy zasad lub programu. (Więc możesz grać w grę za pomocą komputera). Gra nazywa się ostateczny , jeśli każdy gracz ma skończoną liczbę strategii i nieskończony .– W przeciwnym razie.

W celu decydować gra , lub znaleźć decyzja gry , konieczne jest, aby każdy gracz wybrał strategię, która spełnia warunek optymalność , te. jeden z graczy musi otrzymać maksymalna wygrana, gdy drugi trzyma się swojej strategii, W tym samym czasie drugi gracz musi mieć minimalna strata , jeśli pierwszy zastosuje się do swojej strategii. Strategie takie nazywamy optymalny . Optymalne strategie muszą również spełniać warunek zrównoważony rozwój , te. rezygnacja ze strategii w tej grze powinna być nieopłacalna dla któregokolwiek z graczy.

Jeśli gra jest powtarzana wystarczająco dużo razy, gracze mogą nie być zainteresowani wygrywaniem i przegrywaniem w każdej grze, A średnia wygrana (przegrana) we wszystkich partiach.

Celem teorii gier jest określenie optymalnej strategii dla każdego gracza.

21. Macierz płatności. Dolna i górna cena gry

Koniec gry, w której gracz A To ma T strategii i gracza B - str strategii nazywa się grą m×n.

Rozważmy grę m×n dwóch graczy A I W(„my” i „przeciwnik”).

Niech gracz A ma T strategie osobiste, które oznaczamy przez A1,A2,…,Am. Niech gracz W dostępny N strategie osobiste oznaczamy B1,B2,…,Bn.

Niech każda ze stron wybierze określoną strategię; dla nas będzie to Ai, dla przeciwnika Bj. W wyniku wyboru przez graczy dowolnej pary strategii Ai i Bj () wynik gry jest jednoznacznie określony, tj. wygraj gracza aij A(dodatnia lub ujemna) i strata (-aij) gracza W.

Załóżmy, że wartości aij są znane dla dowolnej pary strategii (Ai,Bj) . Macierz P=aij , którego elementami są wypłaty odpowiadające strategiom Ai i Bj, zwany macierz płatności Lub matryca gry. Wiersze tej macierzy odpowiadają strategiom gracza A, a kolumny to strategie gracza B. Strategie te nazywane są czystymi.

Macierz gry m×n ma postać:

Rozważmy grę m×n z macierzą i określmy najlepszą spośród strategii A1,A2,…,Am . Wybór strategii Ai gracz A należy oczekiwać od gracza W odpowie na to jedną ze strategii Bj, dla której wypłata dla gracza A minimalny (gracz W stara się „wyrządzić krzywdę” graczowi A).

Oznacz przez najmniejszą wypłatę gracza A gdy wybiera strategię Ai dla wszystkich możliwych strategii gracza W(najmniejsza liczba w I-ty wiersz macierzy wypłat), tj.

Spośród wszystkich liczb () wybierz największą: .

Zadzwońmy niższa cena gry, Lub maksymalna wygrana (maksymalna). Jest to gwarantowana wypłata gracza A dla dowolnej strategii gracza B. Stąd,

Strategia odpowiadająca maksiminowi nazywa się strategia maximina . Gracz W zainteresowany zmniejszeniem wypłaty gracza A, wybierając strategię Bj, bierze pod uwagę maksymalną możliwą wypłatę dla A. Oznaczać

Spośród wszystkich liczb wybierz najmniejszą

i zadzwoń najwyższa cena gry Lub minimalna wypłata(minimaks). Ego gwarantowało utratę gracza B. Dlatego,

Nazywa się strategia minimax strategia minimaksu.

Zasada, która dyktuje graczom wybór najbardziej „ostrożnych” strategii minimax i maximin to tzw zasada minimaksu . Zasada ta wynika z rozsądnego założenia, że ​​każdy gracz dąży do osiągnięcia przeciwnego celu przeciwnika.

Twierdzenie. Niższa cena gry nigdy nie przekracza górnej ceny gry. .

Jeżeli górna i dolna cena gry są takie same, to łączna wartość górnej i dolnej ceny gry nazywa się cena netto gry, Lub cena gry. Strategie minimax odpowiadające cenie gry to optymalne strategie , i ich całość optymalne rozwiązanie Lub decyzja gry. W tym przypadku gracz A otrzymuje maksimum gwarantowane (niezależnie od zachowania gracza) W) wygrać w i gracz W osiągnie gwarantowane minimum (niezależnie od zachowania gracza A) przegrywający w. Mówi się, że rozwiązanie gry ma zrównoważony rozwój , te. jeśli jeden z graczy trzyma się swojej optymalnej strategii, to odejście od jego optymalnej strategii nie może być korzystne dla drugiego.

Jeśli któryś z graczy (np A) trzyma się swojej optymalnej strategii, a drugi gracz (W) w jakikolwiek sposób odbiega od swojej optymalnej strategii dla gracza, który dokonał odchylenia, nigdy nie może to być korzystne; takie zboczenie gracza W może w najlepszym przypadku pozostawić zysk bez zmian. aw najgorszym przypadku zwiększyć.

Wręcz przeciwnie, jeśli W przestrzega swojej optymalnej strategii, oraz A odbiega od własnego, to w żaden sposób nie może to być korzystne A.

Para czystych strategii daje optymalne rozwiązanie gry wtedy i tylko wtedy, gdy odpowiedni element jest zarówno największy w swojej kolumnie, jak i najmniejszy w swoim rzędzie. Taka sytuacja, jeśli występuje, to tzw punkt mocy. W geometrii nazywa się punkt na powierzchni, który ma właściwość jednoczesnego minimum wzdłuż jednej współrzędnej i maksimum wzdłuż drugiej moc kropka, przez analogię termin ten jest używany w teorii gier.

Gra dla której , zwany gra power point. Elementem, który ma tę właściwość, jest punkt potęgi macierzy.

Tak więc dla każdej gry z punktem mocy istnieje rozwiązanie, które określa parę optymalnych strategii dla obu stron, które różnią się następującymi właściwościami.

1) Jeśli obie strony trzymają się swoich optymalnych strategii, średnia wypłata jest równa kosztowi netto gry w, która jest jednocześnie jego dolną i górną ceną.

2) Jeśli jedna ze stron trzyma się swojej optymalnej strategii, podczas gdy druga odchodzi od własnej, wówczas strona odstępująca może na tym tylko stracić iw żadnym wypadku nie może zwiększyć swojego zysku.

W teorii gier udowodniono, że w szczególności każda gra z pełną informacją ma punkt mocy, a co za tym idzie, każda taka gra ma rozwiązanie, czyli istnieje para optymalnych strategii dla jednej i drugiej strony, dająca średnia wypłata równa cenie gry. Jeśli gra z pełną informacją składa się tylko z osobistych ruchów, to kiedy każda ze stron stosuje swoją własną optymalną strategię, musi zawsze zakończyć się całkiem określonym wynikiem, a mianowicie wypłatą dokładnie równą cenie gry.

22. Rozwiązanie gry w strategiach mieszanych.

Wśród skończonych gier o praktycznym znaczeniu gry z punktem siły są stosunkowo rzadkie; bardziej typowy jest przypadek, gdy dolna i górna cena gry są różne. Analizując macierze takich gier, dochodzimy do wniosku, że jeśli każdy gracz ma do wyboru jedną strategię, to na podstawie rozsądnie działającego przeciwnika wybór ten powinien być determinowany zasadą minimaksu. Trzymając się naszej strategii maximin, za każde zachowanie przeciwnika z pewnością gwarantujemy sobie wypłatę równą niższej cenie gry α. strategie mieszane

strategia mieszana Sa gracz A nazywamy zastosowaniem czystych strategii A1,A1,…,Ai,…,Am z prawdopodobieństwami p1,p2,…pi,…pm, a suma prawdopodobieństw jest równa 1: . Mieszane strategie gracza A są zapisane jako macierz

lub jako napis Sa=(p1,p2,…,pi,…,pm).

Podobnie strategie mieszane gracza B są oznaczone przez:

Lub Sb=(q1,q2,…,qi,…,qn),

gdzie suma prawdopodobieństw wystąpienia strategii jest równa 1: .

Oczywiście każda czysta strategia jest szczególnym przypadkiem strategii mieszanej, w której wszystkie strategie, z wyjątkiem jednej, są stosowane z zerową częstotliwością (prawdopodobieństwami), a ta jest stosowana z częstotliwością (prawdopodobieństwo) równą 1.

Okazuje się, że stosując nie tylko czyste, ale i mieszane strategie, można uzyskać rozwiązanie dla każdej skończonej gry, tj. do ceny gry, a przy jednostronnym odchyleniu od optymalnej strategii, wypłata może zmienić się tylko w kierunku niekorzystnym dla dewianta. Tak więc, w oparciu o zasadę minimax, jest to określone optymalne rozwiązanie (Lub rozwiązanie) gry: jest to para strategii optymalnych w ogólnym przypadku mieszany, mający następującą właściwość: jeśli jeden z graczy trzyma się swojej optymalnej strategii, to drugiemu nie może być opłacalne odejście od jego strategii. Wypłata odpowiadająca rozwiązaniu optymalnemu nazywana jest kosztem zabawy v . Cena gry spełnia nierówność:

Gdzie α i β to dolna i górna cena gry.

To stwierdzenie jest treścią tzw podstawowe twierdzenie teorii gier. Twierdzenie to zostało po raz pierwszy udowodnione przez Johna von Neumanna w 1928 r. Znane dowody twierdzenia są stosunkowo złożone; dlatego przedstawiamy tylko jego sformułowanie.

Każda skończona gra ma co najmniej jedno optymalne rozwiązanie, być może wśród strategii mieszanych.

Z głównego twierdzenia wynika, że ​​każda skończona gra ma swoją cenę.

Niech i – parę strategii optymalnych. Jeśli czysta strategia jest zawarta w optymalnej strategii mieszanej z niezerowym prawdopodobieństwem, to jest wywoływana aktywny (przydatny) .

sprawiedliwy twierdzenie o aktywnej strategii: jeśli jeden z graczy trzyma się swojej optymalnej strategii mieszanej, to wypłata pozostaje niezmieniona i równa kosztowi gry v, jeśli drugi gracz nie wykracza poza swoje aktywne strategie.

Gracz może używać dowolnej ze swoich aktywnych strategii w czystej postaci, a także może je mieszać w dowolnych proporcjach.

Twierdzenie to ma ogromne znaczenie praktyczne - podaje konkretne modele znajdowania optymalnych strategii przy braku punktu siodłowego.

Rozważać Gra w rozmiarze 2x2, co jest najprostszym przypadkiem skończonej gry. Jeżeli taka gra ma punkt siodłowy, to optymalnym rozwiązaniem jest para czystych strategii odpowiadających temu punktowi.

Gra bez punktu siodłowego, zgodnie z podstawowym twierdzeniem teorii gier optymalne rozwiązanie istnieje i jest określane przez parę strategii mieszanych I.

Aby je znaleźć, używamy twierdzenia o strategiach aktywnych. Jeśli gracz A trzyma się swojej optymalnej strategii , wtedy jego średnia wypłata będzie równa cenie gry w, bez względu na to, jakiej aktywnej strategii używa gracz W. W grze 2 na 2 czysta strategia dowolnego przeciwnika jest aktywna, jeśli nie ma punktu ssdl. Zwycięstwo gracza A(strata gracza W)- zmienną losową, której matematyczną wartością oczekiwaną (wartością średnią) jest cena gry. Dlatego średnia wypłata gracza A(strategia optymalna) będzie równa w zarówno dla pierwszej, jak i drugiej strategii przeciwnika.

Niech gra będzie dana przez macierz wypłat.

Średnia wypłata gracza A, jeśli zastosuje optymalną strategię mieszaną i gracza W - czysta strategia B1 (odpowiada to pierwszej kolumnie macierzy wypłat R), równa cenie gry w: .

Gracz otrzymuje taką samą średnią wypłatę A, jeśli drugi gracz stosuje strategię B2, tj. . Biorąc to pod uwagę, otrzymujemy układ równań do określenia optymalnej strategii i ceny gier w:

Rozwiązując ten układ, uzyskujemy optymalną strategię

oraz cenę gry.

Zastosowanie twierdzenia o aktywnej strategii do znajdowania – optymalna strategia gracza W, otrzymujemy to dla każdej czystej strategii gracza A (A1 Lub A2) Średnia strata gracza W równa cenie gry w, tj.

Wtedy optymalną strategię określają wzory: .

Zadanie rozwiązania gry, jeśli jej macierz nie zawiera punktu siodłowego, jest tym trudniejsze, im większa jest wartość M I N. Dlatego w teorii gier macierzowych rozważa się metody, za pomocą których rozwiązanie niektórych gier sprowadza się do rozwiązania innych, prostszych, w szczególności poprzez zmniejszenie wymiaru macierzy. Możliwe jest zmniejszenie wymiaru macierzy przez wykluczenie duplikować i oczywiście niekorzystny strategie.

Duplikować nazywane są strategiami, które odpowiadają tym samym wartościom elementów w macierzy wypłat, tj. macierz zawiera te same wiersze (kolumny).

Jeżeli wszystkie elementy i-tego rzędu macierzy są mniejsze niż odpowiadające im elementy k-tego rzędu, to i-ta strategia dla gracza A nieopłacalne (wygrywanie mniej).

Jeśli wszystkie elementy r-tej kolumny macierzy są większe niż odpowiadające im elementy j-tej kolumny, to dla gracza W R-ta strategia jest nieopłacalna (strata jest większa).

Procedura eliminacji powielających się i oczywiście nieopłacalnych strategii powinna zawsze poprzedzać rozwiązanie gry.

23. Geometryczna interpretacja gry 2×2

Decyzja o grze 2×2 pozwala na przejrzystą interpretację geometryczną.

Niech gra będzie dana macierzą wypłat P=(aij), i, j=1,2.

Na odciętej (ryc.) Odłóż na bok jednostka odcinek A1A2; punkt A1 ( X=0) przedstawia strategię A1, punkt A2 ( X=1) przedstawia strategię A2, a wszystkie punkty pośrednie tego odcinka to strategie mieszane Sa pierwszego gracza, a odległość od Sa do prawego końca odcinka to prawdopodobieństwo p1 strategii A1 , odległość do lewego końca jest prawdopodobieństwem p2 strategii A2 .

Narysujmy dwie prostopadłe do osi x przechodzące przez punkty A1 i A2: oś I-I i oś II-II. Na osi I-I odłożymy zyski w ramach strategii A1; na osi II-II – wypłaty w ramach strategii A2.

Jeśli gracz A stosuje strategię A1, to jego wypłata w ramach strategii B1 gracza B wynosi a11, aw przypadku strategii B2 wynosi a12. Liczby a11 i a12 na osi I odpowiadają punktom B1 i B2.

Jeśli gracz A stosuje strategię A2, to jego wypłata w strategii B1 gracza B wynosi a21, aw strategii B2 jest równa a22. Liczby a21 i a22 odpowiadają punktom B1 i B2 na osi II.

Łączymy punkty B1 (I) i B1 (II); B2 (I) i B2 (II). Masz dwie linie proste. Linia prosta B1B1– jeśli gracz A stosuje strategię mieszaną (dowolną kombinację strategii A1 i A2 z prawdopodobieństwem p1 i p2), a gracz B stosuje strategię B1. Zwycięski gracz A odpowiada jakiemuś punktowi na tej prostej. Średnia wypłata odpowiadająca strategii mieszanej jest określona wzorem a11p1+a21p2 i jest reprezentowana przez punkt M1 na linii B1B1.

Podobnie konstruujemy segment B2B2 odpowiadający zastosowaniu strategii B2 przez drugiego gracza. W tym przypadku średnie wzmocnienie jest określone wzorem a12p1+a22p2 i jest reprezentowane przez punkt M2 na linii prostej B2B2.

Musimy znaleźć strategię optymalną S*a, czyli taką, dla której minimalna wypłata (dla dowolnego zachowania W) obróciłby się do maksimum. Aby to zrobić, zbudujemy dolna granica zysku ze strategiami B1B2 , tj. linia przerywana B1NB2 zaznaczona na ryc. pogrubiona linia. Ten dolna granica będzie wyrażać minimalną wypłatę gracza A dla którejkolwiek ze swoich strategii mieszanych; kropkaN , w którym ta minimalna wypłata osiąga maksimum i określa rozwiązanie (optymalną strategię) oraz cenę gry. Współrzędna punktu N czy jest cena za grę w. Współrzędne punktu N znajdujemy jako współrzędne punktów przecięcia linii B1B1 i B2B2. W naszym przypadku rozwiązanie gry zostało określone przez punkt przecięcia strategii. Jednak nie zawsze tak będzie.

Geometrycznie możliwe jest określenie optymalnej strategii jako gracz A, jak i odtwarzacz W; w obu przypadkach stosowana jest zasada minimaksu, ale w drugim przypadku konstruowana jest nie dolna, ale górna granica wypłaty, a nie maksimum, ale minimum.

Jeśli macierz wypłat zawiera liczby ujemne, to w celu graficznego rozwiązania problemu lepiej jest przejść na nową macierz z elementami nieujemnymi; w tym celu wystarczy dodać odpowiednią liczbę dodatnią do elementów oryginalnej macierzy. Decyzja gry się nie zmieni, ale cena gry wzrośnie o tę liczbę. Metodę graficzną można wykorzystać do rozwiązania gry 2×n, m×2.

24. Sprowadzenie gry macierzowej do problemu programowania liniowego

Gra m × n generalnie nie ma wizualnej interpretacji geometrycznej. Jego rozwiązanie jest dość pracochłonne dla dużych T I N, nie ma jednak fundamentalnych trudności, ponieważ można go sprowadzić do rozwiązania problemu programowania liniowego. pokażmy to.

Niech gra m×n będzie dana przez macierz wypłat . Gracz A posiada strategie A1,A2,..Ai,..Am , gracz W - strategie B 1,B 2,..B I,.. B N. Konieczne jest określenie optymalnych strategii i miejsca to prawdopodobieństwa zastosowania odpowiednich czystych strategii Ai,Bj,

Optymalna strategia spełnia następujące wymaganie. Zapewnia graczowi Aśrednia wypłata nie mniejsza niż cena gry w, dla dowolnej strategii gracza W i wypłata równa cenie gry w, z optymalną strategią gracza W. Bez utraty ogólności ustawiamy w> 0; można to osiągnąć poprzez wykonanie wszystkich elementów . Jeśli gracz A stosuje strategię mieszaną przeciwko dowolnemu graczowi Bj o czystej strategii W, wtedy dostaje średnia wypłata , Lub matematyczne oczekiwanie wygranej (czyli pierwiastki J-Go kolumny macierzy wypłat są mnożone termin po terminie przez odpowiadające im prawdopodobieństwa strategii A1,A2,..Ai,..Am i wyniki są dodawane).

Dla optymalnej strategii wszystkie średnie wypłaty są nie mniejsze niż cena gry w, więc otrzymujemy układ nierówności:

Każdą z nierówności można podzielić przez liczbę. Wprowadźmy nowe zmienne: . Następnie system przybiera formę

Cel gracza A - zmaksymalizować gwarantowaną wypłatę, tj. cena gry w.

Dzieląc przez równość, otrzymujemy, że zmienne spełniają warunek: . Maksymalizacja ceny gry w jest równoważne minimalizacji ilości , więc problem można sformułować następująco: zdefiniuj wartości zmiennych , mamaaby spełnić ograniczenia liniowe(*) I natomiast funkcja liniowa (2*) zwrócił się do minimum.

Jest to problem programowania liniowego. Rozwiązując problem (1*)–(2*), otrzymujemy rozwiązanie optymalne i optymalną strategię .

Aby ustalić optymalną strategię, należy wziąć pod uwagę, że gracz W dąży do zminimalizowania gwarantowanej wypłaty, tj. znajdź maks. Zmienne spełniają nierówności

które wynikają z faktu, że średnia strata gracza W nie przekracza wartości gry, bez względu na to, jakiej czystej strategii używa gracz A.

Jeżeli oznaczymy (4*) , to otrzymamy układ nierówności:

Zmienne spełniają warunek.

Gra została zredukowana do następnego zadania.

Określ wartości zmiennych , które spełniają układ nierówności (5*)I zmaksymalizować funkcję liniową

Rozwiązanie problemu programowania liniowego (5*), (6*) określa optymalną strategię. W tym samym czasie cena gry. (7*)

Mając skompilowane macierze rozszerzone dla problemów (1*), (2*) i (5*), (6*), upewniamy się, że jedna macierz została otrzymana z drugiej przez transpozycję:

Zatem problemy programowania liniowego (1*), (2*) i (5*), (6*) są wzajemnie dualne. Oczywiście, ustalając optymalne strategie w konkretnych problemach, należy wybrać jeden z problemów wzajemnie dualnych, którego rozwiązanie jest mniej pracochłonne, a rozwiązanie drugiego problemu znaleźć za pomocą twierdzeń o dualności.

Rozwiązując dowolną skończoną grę o rozmiarze m×n, zaleca się przestrzeganie następującego schematu:

1. Wyklucz z macierzy wypłat strategie oczywiście nierentowne w porównaniu z innymi strategiami. Takie strategie dla gracza A

badania operacyjne) - stosunkowo nowy obszar, którego krótka historia sięga początków II wojny światowej. Dokładnie ta mata. Nauka zawiera dobrze zdefiniowany zestaw ogólnych zasad, aby zapewnić naukowcom plan realizacji działań badawczych. Obejmuje następujące etapy. 1. Sformułowanie problemu. 2. Budowa maty. model reprezentujący badany system. 3. Uzyskanie rozwiązania z tego modelu. 4. Sprawdzenie modelu i otrzymanego z niego rozwiązania. 5. Ustanowienie kontroli nad decyzją. 6. Prakt. wdrożenie rozwiązania: wdrożenie. Sformułowanie problemu Poważną uwagę należy zwrócić na zdefiniowanie ogólnego charakteru problemu i, co ważniejsze, celów badań. Cele te powinny być sformułowane w kategoriach behawioralnych, aby zminimalizować lub wyeliminować niejednoznaczność i niepewność. Należy również dać czas na prawidłowe ustalenie priorytetów realistycznie osiągalnych celów. Zbyt długa lista celów może powodować potencjalne trudności w ich realizacji, zwłaszcza jeśli cele te nie są wyraźnie połączone w logiczną sekwencję. Budowa modelu matematycznego Druga faza badań z t. sp. I o. sugeruje opis modelu. Celem modelu jest reprezentowanie świata rzeczywistego. w I. o. takie modele są symboliczne, wyrażone w mat. warunki. Klasyczne równanie E \u003d mc2 jest typowym przykładem maty. modele. Tradycyjną formą takich modeli są równania algebraiczne, nie tylko val. bardziej ekonomiczne niż sformułowania werbalne, ale pociągają za sobą dogłębność i precyzję definicji niezbędną do jasnego wyrażenia i zrozumienia poszczególnych elementów i ich relacji. Najważniejszym zadaniem w budowaniu takiego modelu jest jasne i precyzyjne opracowanie oraz zdefiniowanie funkcji celu. Ta funkcja wyraża związek między zmiennymi niezależnymi i zależnymi. Wyprowadzanie rozwiązania z zadanego modelu Trzecią fazą jest znalezienie rozwiązania. Z reguły pożądane jest znalezienie rozwiązania optymalnego lub lepszego, ale należy wziąć pod uwagę, że takie rozwiązanie będzie miało wartość jedynie w kontekście rozpatrywanego modelu. Ponieważ model jest jedynie reprezentacją rzeczywistego problemu, istnieje wiele sytuacji, w których optymalne rozwiązanie może nie wiązać się z najlepszym wyborem. Jednak w przypadku połączenia rozwiązania optymalnego z mniej optymalnymi lub bardziej realistycznymi rozwiązaniami alternatywnymi, z możliwością ich późniejszego przetestowania w odniesieniu do rzeczywistego problemu, zastosowanie rozwiązania optymalnego niesie za sobą określone korzyści. Jedna z takich korzyści dotyczy definicji na końcu badania. względna odległość między rozwiązaniem idealnym a akceptowaną alternatywą. Produktem ubocznym tej metodologii jest wykorzystanie I.o. jest założenie, że mniej optymalne rozwiązania mogą być postrzegane jako odskocznie na drodze do osiągnięcia celu. Ta metoda kolejnych przybliżeń może prowadzić badacza operacyjnego do bardziej owocnych wyników. Jest wiele mat. procedury uzyskiwania rozwiązań w I.o. Procedury te opierają się na zastosowaniach teorii prawdopodobieństwa. Walidacja modelu i rozwiązania na jego podstawie Walidacja modelu i rozwiązania polega na wykonaniu dwóch kroków. Pierwszy polega na dokładnej analizie wszystkich elementów modelu, m.in. ponowne sprawdzenie jego czynników algebraicznych pod kątem obecności uproszczonych błędów kosmetycznych, które mogą wpływać na ważność. Dr. jeszcze ważniejszym krokiem jest ponowne zdefiniowanie relacji modelu do założeń, które pierwotnie posłużyły do ​​opracowania tego modelu. Bardziej systematyczny plan przeglądu obejmuje również użycie ist. dane, które można łatwo wprowadzić do modelu, aby uzyskać rozwiązanie prototypowe. Dane te muszą być dokładnie przejrzane, aby zapewnić ważność kontroli dla badacza operacyjnego. Należy zauważyć, że gdy tylko model ten zostanie praktycznie opracowany na podstawie poprzednich źródeł. danych i potrzeb, w przyszłości może zachowywać się zupełnie inaczej. Dr. Częstym błędem jest wprowadzanie do modelu czynników, które nie zostały w nim przedstawione. Baza danych. Ustanowienie kontroli Piąty etap, ustanowienie kontroli nad decyzją, pojawia się w trakcie wielokrotnego stosowania modelu. Kontrola nad modelem zostaje ustanowiona, gdy badacz operacyjny dopuszcza rozbieżności w wartościach ist. danych i uznaje, że te rozbieżności mogą wpływać na relacje między elementami modelu i wynikającymi z nich rozwiązaniami. Dr. ważnym krokiem mogłoby być opracowanie restrykcji na wybranych bazach. parametry modelu w celu ustalenia zakresu dopuszczalnych wartości na podstawie rzeczywistych danych. Implementacja modelu Ostatnim krokiem jest wprowadzenie do modelu rzeczywistych danych. Prakt. wdrożenie modelu wiąże się z oczywistym krokiem wprowadzenia rzeczywistych danych i uzyskania rozwiązania rzeczywistego problemu. Ponadto ważna jest również ocena bliskości rozwiązania rzeczywistego do ist. uzyskanych wcześniej rozwiązań, a także konsekwencje tej decyzji dla poprawy sposobu użytkowania modelu. Te kroki zapewniają ważne połączenie między matą. natura I. o. i ćwiczyć. winiki wyszukiwania. Ostatecznie te decyzje i ich implikacje zarządcze są wykorzystywane przez doświadczonego specjalistę AI. udoskonalić model do ewentualnego wykorzystania w przyszłości. Zobacz także Metodologia badań (naukowych) R. S. Endrulis