Prawidłowa definicja pojęcia badań operacyjnych brzmi: Przedmiot i zadania badań operacyjnych

1. Podstawowe pojęcia AI

I O – sprzeciw naukowy, zajmujący się opracowywaniem i praktycznym zastosowaniem metod najbardziej efektywnego zarządzania różnymi systemami organizacyjnymi.

IO obejmuje następujące sekcje:

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

2) teoria kolejkowania, oparta na teorii procesów losowych;

3) teoria gier, która pozwala uzasadniać decyzje podejmowane w warunkach niepełnej informacji.

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

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

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

Podstawowe pojęcia i definicje IO.

Operacja – wszelkie kontrolowane działanie mające na celu osiągnięcie celu. Wynik operacji zależy od sposobu jej wykonania, organizacji, w przeciwnym razie - od wyboru określonych parametrów. Operacja jest zawsze zdarzeniem kontrolowanym, czyli od nas zależy, jak dobierzemy pewne parametry charakteryzujące jej organizację. „Organizacja” jest tu rozumiana w szerokim znaczeniu tego słowa, łącznie z zespołem środków technicznych wykorzystywanych w działaniu.

Nazywa się dowolny konkretny wybór parametrów decyzja . Decyzje mogą być skuteczne 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 ilościowe uzasadnienie optymalnych rozwiązań.

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

Efektywność działania – stopień jego przystosowania do zadania wyraża się ilościowo w postaci kryterium efektywności – funkcji celu. Wybór kryterium efektywności decyduje o wartości praktycznej badania. (Nieprawidłowo wybrane kryterium może być szkodliwe, gdyż działania organizowane pod kątem takiego kryterium efektywności prowadzą czasami do nieuzasadnionych kosztów.)

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

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

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

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

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

Planowanie (harmonogramowanie) zadań polegają na ustaleniu optymalnej kolejności operacji (na przykład obróbki części) na różnego rodzaju sprzęcie.

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

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

2. Ogólny problem programu liniowego. Optymalizacja rozwiązania

Model ekonomiczno-matematyczny

LP to dział matematyki rozwijający teorię i metody numeryczne rozwiązywania problemów znajdowania ekstremum (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 problemów praktycznych, w których: 1) konieczne jest wybranie najlepszego rozwiązania (planu optymalnego) spośród wielu możliwych; 2) rozwiązanie można wyrazić jako zbiór wartości niektórych zmiennych; a) ograniczenia nałożone na możliwe rozwiązania przez specyficzne warunki problemu są formułowane w postaci równań lub nierówności liniowych; 4) cel wyrażony jest w postaci funkcji liniowej głównych zmiennych. Wartości funkcji celu, umożliwiające porównanie różnych rozwiązań, służą jako kryterium jakości rozwiązania.

Aby praktycznie rozwiązać problem ekonomiczny metodami matematycznymi, należy go przede wszystkim zapisać za pomocą modelu ekonomiczno-matematycznego. Model ekonomiczno-matematyczny to matematyczny opis badanego procesu gospodarczego lub przedmiotu. Model ten wyraża prawa procesu gospodarczego w abstrakcyjnej formie za pomocą zależności matematycznych.

Ogólny schemat tworzenia modelu: I

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

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

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, pod warunkiem spełnienia ograniczeń nałożonych na zmienne.

Ogólny problem programowania liniowego ma postać:

Biorąc pod uwagę układ m równań liniowych i nierówności z n zmiennymi

i funkcja liniowa

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

System (1) nazywany jest systemem ograniczeń, a funkcja F nazywana jest funkcją liniową, formą 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) problemu LP jest rozwiązaniem X=(x1,x2,…,xj,…,xn), układem więzów (1), spełniającym warunek (3), przy którym funkcja liniowa (2) przyjmuje optymalność (maksymalna lub minimalna) wartość.

Pod warunkiem, że wszystkie zmienne są nieujemne, układ ograniczeń (1) składa się wyłącznie z nierówności - taki problem programowania liniowego nazywa się standardowym (symetrycznym); jeśli układ więzów składa się tylko z równań, wówczas problem nazywa się kanonicznym.

Szczególnym przypadkiem problemu kanonicznego jest problem w postaci podstawowej, charakteryzujący się tym, że wszystkie współczynniki wektora więzów B są nieujemne i w każdym równaniu występuje zmienna o współczynniku 1, która nie jest uwzględniona w żadnym innym równaniu. Zmienna posiadająca tę właściwość nazywana jest podstawową.

Problemy standardowe i kanoniczne są szczególnymi przypadkami problemu ogólnego. Każdy z nich jest stosowany w swoim konkretnym 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 krótkiej formie

Dowolne 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. Jeżeli istnieje co najmniej jedna grupa zmiennych podstawowych, to układ ten jest nieokreślony, a każdemu dowolnemu zbiorowi wartości zmiennych niepodstawowych odpowiada jedno rozwiązanie układu.

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

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

Podstawowe rozwiązanie układu m równań liniowych z n zmiennymi jest rozwiązanie, w którym wszystkie n–m mniejszych zmiennych jest równe zero.

W zagadnieniach programowania liniowego szczególne zainteresowanie cieszą się dopuszczalnymi rozwiązaniami podstawowymi, czyli, jak się je nazywa, planami odniesienia. Rozwiązanie podstawowe, w którym przynajmniej jedna ze zmiennych głównych jest równa zeru, nazywa się zdegenerowanym.

Wypukłe zbiory punktów

Wspólną cechą definiującą, która odróżnia wielokąt wypukły od niewypukłego, jest to, że jeśli weźmiesz dowolne dwa jego punkty i połączysz je segmentem, wówczas cały segment będzie należeć do tego wielokąta. Za pomocą tej właściwości można zdefiniować wypukły zbiór punktów.

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

Zbiory wypukłe mają ważne znaczenie nieruchomość: Przecięcie (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, graniczne i narożne.

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

Punkt zbioru nazywany jest punktem brzegowym, jeśli w którymkolwiek z jego otoczeń znajdują się 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 skrajny), jeśli nie jest wewnętrzny żadnego segmentu całkowicie należącego do danego zbioru.

Na ryc. 2.4 pokazuje przykłady różnych punktów wielokąta: wewnętrzny (punkt M), brzegowy (punkt N) i narożnik (punkty A, B, C, D, E). Punkt A jest punktem narożnym, ponieważ dla dowolnego odcinka należącego w całości do wielokąta, na przykład odcinka AP, nie jest on wewnętrzny; punkt A należy do 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), natomiast w przypadku zbioru niewypukłego nie jest to konieczne. Zbiór punktów nazywa się zamkniętym, jeżeli zawiera wszystkie swoje punkty graniczne. Zbiór punktów nazywa się ograniczony, jeśli istnieje kula (okrąg) o promieniu skończonej długości ze środkiem w dowolnym punkcie zbioru, który w całości zawiera dany zbiór; w przeciwnym razie mówi się, że zbiór jest nieograniczony.

Wypukły zamknięty zbiór punktów na płaszczyźnie mający skończoną liczbę punktów narożnych nazywany jest wielokątem wypukłym, jeśli jest ograniczony, i obszarem wielokąta wypukłego, 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 wyznaczyć pożądaną półpłaszczyznę (górną lub dolną), zaleca się wyznaczenie dowolnego punktu kontrolnego, który nie leży na jej granicy – ​​skonstruowanej linii prostej. Jeżeli nierówność zachodzi w punkcie kontrolnym, to obowiązuje we wszystkich punktach półpłaszczyzny zawierającej punkt kontrolny i nie obowiązuje we wszystkich punktach drugiej półpłaszczyzny. I odwrotnie, jeśli nierówność nie jest spełniona w punkcie kontrolnym, 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. Za punkt kontrolny wygodnie jest przyjąć początek współrzędnych O (0;0), które nie leżą na skonstruowanej linii.

Rozważmy zbiór rozwiązań układów nierówności.

Stwierdzenie 2. Zbiór rozwiązań wspólnego układu nierówności liniowych dwóch zmiennych jest wielokątem wypukłym (lub obszarem wielokąta wypukłego).

Każda z nierówności, zgodnie ze Stwierdzeniem 1, wyznacza jedną z półpłaszczyzn, która jest wypukłym zbiorem punktów. Zbiór rozwiązań wspólnego układu nierówności liniowych to punkty należące do półpłaszczyzn rozwiązań wszystkich nierówności, tj. należą do ich przecięcia. 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łków wielokąta - znajdują się jako współrzędne punktów przecięcia odpowiednich linii.

Podczas konstruowania obszarów rozwiązań dla systemów nierówności mogą wystąpić inne przypadki: zbiór rozwiązań jest wypukłym obszarem wielokątnym (ryc. 2.9, a); jeden punkt (ryc. 2.9, b); zbiór pusty, gdy układ 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żeli problem LP ma rozwiązanie optymalne, to funkcja liniowa przyjmuje maksymalną wartość w jednym z punktów narożnych 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 będącym wypukłą liniową kombinacją tych punktów.

Twierdzenie wskazuje podstawowy 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 badanie tylko skończonej liczby punktów narożnych wielościanu rozwiązania.

Następne twierdzenie poświęcone jest 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.

Ważny wniosek wynika bezpośrednio z twierdzeń 1 i 2: Jeżeli problem LP ma rozwiązanie optymalne, to pokrywa się ono z co najmniej jednym z dopuszczalnych rozwiązań podstawowych.

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

Zatem zbiór możliwych rozwiązań (wielościan rozwiązania) problemu LP jest wielościanem wypukłym (lub obszarem wielościanu wypukłego), a optymalne rozwiązanie problemu znajduje się przynajmniej w jednym z punktów narożnych wielościanu rozwiązania.

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

Niech obrazem geometrycznym układu więzów będzie wielokąt ABCDE(ryc. 4.1). Należy wśród punktów tego wielokąta znaleźć punkt, w którym funkcja liniowa F=c1x1+c2x2 przyjmuje wartość maksymalną (lub minimalną).

Weźmy pod uwagę tzw linia pozioma funkcja liniowa F, tj. linia, wzdłuż której ta funkcja przyjmuje tę samą stałą 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 najwyższym (jeśli funkcja liniowa jest maksymalizowana) lub najniższym (jeśli jest minimalizowana) poziomem.

Równanie linii poziomu funkcji c1x1+c2x2=a jest równaniem linii prostej. Na różnych poziomach A linie poziomu są równoległe, ponieważ ich współczynniki kątowe są określone jedynie przez relację między współczynnikami c1 i c2, a zatem są równe. Zatem 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 w jednym kierunku poziom tylko wzrasta, a przy przesunięciu w drugim kierunku jedynie maleje. Wychodzący z początku wektor c=(c1,c2) ​​wskazuje kierunek najszybszego wzrostu funkcji F. Linia poziomu funkcji liniowej jest prostopadła do wektora c=(c1,c2).

Procedura graficznego rozwiązywania problemu LP:

1. Zbuduj wielokąt rozwiązań.

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

3. Ruchem równoległym prostej F=0 w kierunku wektora c(-c) znajdź punkt Amax(Bmin), w którym F osiąga maksimum (minimum).

1. Rozwiązując łącznie 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 rozwiązania, 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: pozwala skutecznie rozwiązywać problemy zawierające nie więcej niż dwie zmienne. Rozpatrzono podstawowe twierdzenia programowania liniowego, z których wynika, że ​​jeżeli zadanie programowania liniowego ma rozwiązanie optymalne, to odpowiada ono co najmniej jednemu punktowi narożnemu wielościanu rozwiązania i pokrywa się z co najmniej jednym z dopuszczalnych rozwiązań podstawowych wielościanu system ograniczeń. Wskazano sposób rozwiązania dowolnego problemu programowania liniowego: wyliczyć skończoną liczbę możliwych rozwiązań podstawowych układu ograniczeń i wybrać spośród nich to, dla którego funkcja celu stanowi rozwiązanie optymalne. Geometrycznie odpowiada to wyliczeniu wszystkich punktów narożnych wielościanu rozwiązania. Takie wyczerpujące poszukiwania ostatecznie doprowadzą do rozwiązania optymalnego (o ile takie istnieje), jednak jego praktyczna realizacja wiąże się z ogromnymi trudnościami, gdyż w przypadku problemów rzeczywistych liczba wykonalnych rozwiązań podstawowych, choć skończona, może być niezwykle duża.

Liczbę dopuszczalnych rozwiązań podstawowych, które należy przeszukiwać, można zmniejszyć, jeśli wyszukiwanie nie będzie prowadzone losowo, ale z uwzględnieniem zmian funkcji liniowej, tj. zapewnienie, że każde kolejne rozwiązanie jest „lepsze” (a przynajmniej „nie gorsze”) od poprzedniego, zgodnie z wartościami funkcji liniowej (zwiększając je przy znalezieniu maksimum, zmniejszając przy znalezieniu minimum) . To wyszukiwanie pozwala zmniejszyć liczbę kroków w poszukiwaniu optymalnego. 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 oryginalnemu wykonalnemu rozwiązaniu bazowemu. Wyszukiwanie losowe wymagałoby przetestowania pięciu możliwych rozwiązań bazowych odpowiadających pięciu punktom narożnym wielokąta. Jednak z rysunku jasno wynika, że ​​po górze A korzystne jest przejście do sąsiedniego wierzchołka W, a następnie do optymalnego punktu Z. Zamiast pięciu przeszliśmy tylko przez trzy wierzchołki, konsekwentnie poprawiając funkcję liniową.

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

Znaczenie geometryczne metody sympleksowej polega na sekwencyjnym przejściu od jednego wierzchołka wielościanu więzów (zwanego początkowym) do sąsiedniego, w którym funkcja liniowa przyjmuje najlepszą (przynajmniej nie najgorszą) wartość w stosunku do cel problemu; do momentu znalezienia rozwiązania optymalnego – wierzchołka, w którym zostaje osiągnięta optymalna wartość funkcji celu (jeżeli problem ma maksimum końcowe).

Metodę simpleksową po raz pierwszy zaproponował amerykański naukowiec J. Danzig w 1949 r., ale już w 1939 r. koncepcje tej metody opracował rosyjski naukowiec L.V. Kantorowicz.

Metoda simpleksowa, która umożliwia rozwiązanie dowolnego problemu programowania liniowego, jest uniwersalna. Obecnie wykorzystuje się go do obliczeń komputerowych, ale proste przykłady metodą sympleksową można rozwiązać ręcznie.

Aby wdrożyć metodę simplex - sekwencyjne doskonalenie 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 gorszego) rozwiązania;

kryterium sprawdzenia optymalności znalezionego rozwiązania.

Aby zastosować metodę simplex, problem programowania liniowego należy sprowadzić do postaci kanonicznej, tj. układ więzów należy przedstawić w postaci równań.

W literaturze dość szczegółowo opisano: znalezienie wstępnego planu wsparcia (początkowego dopuszczalnego rozwiązania podstawowego), także przy użyciu metody sztucznej bazy, znalezienie optymalnego planu wsparcia, rozwiązywanie problemów przy użyciu tablic simpleksowych.

7 . Algorytm metody simplex.

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

1. Na podstawie warunków zadania tworzony jest jego model matematyczny.

2. Gotowy model jest konwertowany do postaci kanonicznej. W takim przypadku można zidentyfikować podstawę ze wstępnym planem referencyjnym.

3. Model kanoniczny problemu zapisano w formie tabeli simplex, tak aby wszystkie wolne terminy były nieujemne. Jeśli wybrany został początkowy plan referencyjny, przejdź do kroku 5.

Tabela Simplex: układ równań ograniczeń i funkcja celu są wprowadzane w postaci wyrażeń rozwiązanych w stosunku do podstawy początkowej. Linię, w której zapisywane są współczynniki funkcji celu F, nazywa się linią F lub linią funkcji celu.

4. Początkowy plan odniesienia znajduje się poprzez wykonanie transformacji sympleksowych z elementami o dodatniej rozdzielczości odpowiadającymi minimalnym relacjom sympleksowym i bez uwzględnienia znaków elementów rzędu F. Jeżeli w trakcie przekształceń napotkany zostanie rząd zerowy, którego wszystkie elementy, z wyjątkiem członu wolnego, są zerami, to układ równań ograniczeń dla problemu jest niespójny. Jeżeli natrafiamy na wiersz 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ę systemu (2.55), (2.56) do nowej podstawy transformacja simpleksowa . Jeśli traktować transformację sympleksową jako formalną operację algebraiczną, to można zauważyć, że w wyniku tej operacji następuje redystrybucja ról pomiędzy dwiema zmiennymi wchodzącymi w skład pewnego układu funkcji liniowych: jedna zmienna przechodzi od zależnej do niezależnej, a druga wręcz przeciwnie, z niezależnego na zależny. Operacja ta znana jest w algebrze jako Krok eliminacji Jordana.

5. Znaleziony wstępny plan wsparcia jest sprawdzany pod kątem optymalności:

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

b) jeżeli w rzędzie F znajduje się przynajmniej jeden element ujemny, który odpowiada kolumnie elementów innych niż dodatnie, to;

c) jeżeli w wierszu F znajduje się przynajmniej jeden element ujemny, a w jego kolumnie przynajmniej jeden element dodatni, to można przejść do nowego planu odniesienia, bliższego optymalnemu. Aby to zrobić, należy wyznaczyć określoną kolumnę jako kolumnę rozdzielczą, stosując minimalny współczynnik sympleksowy, znaleźć wiersz rozwiązujący i wykonać transformację sympleksową. Powstały plan odniesienia jest ponownie sprawdzany pod kątem optymalności. Opisany proces powtarza się aż do uzyskania optymalnego planu lub ustalenia nierozwiązywalności problemu.

Kolumna współczynników zmiennej zawartej w podstawie nazywa się rozdzielczością. Zatem wybierając zmienną wprowadzoną do bazy (lub wybierając kolumnę rozdzielczą) w oparciu o element ujemny rzędu F, zapewniamy, że funkcja F wzrasta .

Nieco trudniej jest określić zmienną, którą należy wykluczyć z podstawy. W tym celu układają stosunki wyrazów wolnych do elementów dodatnich kolumny rozwiązującej (takie relacje nazywane są sympleksami) i znajdują spośród nich najmniejszy, który wyznacza wiersz (rozwiązujący) zawierający wykluczoną zmienną. Wybór zmiennej wyłączonej z bazy (lub wybór prostej rozdzielczej) zgodnie z minimalną relacją sympleksową gwarantuje, jak już ustalono, dodatniość składowych bazy w nowym planie odniesienia.

W punkcie 3 algorytmu zakłada się, że wszystkie elementy kolumny wolnych terminów są nieujemne. Wymóg ten nie jest konieczny, ale jeśli zostanie spełniony, wówczas wszystkie kolejne przekształcenia sympleksowe będą wykonywane wyłącznie z elementami o dodatniej rozdzielczości, co jest wygodne w obliczeniach. Jeśli w kolumnie wolnych terminów znajdują się liczby ujemne, wówczas element rozstrzygający wybierany jest w następujący sposób:

1) przejrzyj wiersz odpowiadający pewnemu ujemnemu terminowi swobodnemu, na przykład wierszowi t, i wybierz w nim jakiś element ujemny, a odpowiadającą kolumnę uznaj za rozwiązującą (zakładamy, że ograniczenia problemu są spójne);

2) tworzą relacje elementów kolumny wyrazów wolnych z odpowiednimi elementami kolumny rozdzielczej, które mają te same znaki (relacje simpleksowe);

3) wybrać najmniejszą z relacji sympleksowych. To określi ciąg włączający. Niech będzie np. R-linia;

4) na przecięciu rozdzielającej kolumny i wiersza znajduje się element rozstrzygający. Jeśli element rzędu y okaże się rozdzielczy, to po transformacji sympleksowej wyraz wolny tego rzędu stanie się dodatni. W przeciwnym razie w następnym kroku ponownie uzyskany zostanie dostęp do wiersza t. Jeśli problem da się rozwiązać, to po określonej liczbie kroków w kolumnie wolnych terminów nie pozostaną żadne elementy negatywne.

8. Metoda macierzowa odwrotna

Rozważmy LP w postaci:

A – macierz ograniczeń;

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

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 drobnostka 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 pozostałe są bezpłatne.

Niech B będzie jakąś bazą. Następnie przestawiając kolumny macierzy A zawsze możemy zredukować A do postaci A=(B|N),

gdzie N jest podmacierzą składającą się z kolumn macierzy A, które nie należą do podstawy. 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 postać:

Ponieważ |B|<>0, to mamy macierz odwrotną. Mnożąc od lewej strony przez odwrotność, otrzymujemy:

- wspólna decyzja.

Rozwiązanie podstawowe (w stosunku do bazy B) to szczególne rozwiązanie problemu (2) otrzymane pod warunkiem. Wtedy jest to ustalane jednoznacznie.

Rozwiązanie podstawowe nazywa się wykonalny, Jeśli.

Podstawa odpowiadająca wdrożonemu rozwiązaniu podstawowemu. Zwany możliwa do wdrożenia podstawa. Rozwiązanie podstawowe nazywa się zdegenerowanym, jeżeli wektor ma składowe zerowe.

Rozwiązanie ogólne zawiera wszystkie istniejące rozwiązania. Wróćmy do funkcji celu. Przed zmiennymi podstawowymi wprowadzamy Cb – współczynniki, Cn – resztę.

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

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

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

Dokument: Zostawiać. Rozważmy rozwiązanie podstawowe, .

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

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

Potem spójrzmy

Podstawowym rozwiązaniem jest więc jak najbardziej min. Przeciwnie, niech się nie spełni, tj. istnieje.

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

Niech odpowiada zmiennej wolnej Xi:Xj, przypisujemy wartość i wpisujemy ją do bazy, a następnie wyprowadzamy kolejną zmienną i nazywamy ją wolną.

Jak ustalić? Wszystkie zmienne wolne z wyjątkiem zmiennych są nadal równe 0.

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

Wyjmijmy: – warunek konieczny.

Rozwiązanie podstawowe nazywa się regularnym jeśli. Zmienną wyprowadzamy z podstawy. Przy nowym rozwiązaniu funkcja celu maleje, ponieważ

Algorytm:

1. Problem LP w postaci standardowej.

2. Pozostawiamy liniowo niezależne równania.

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

Obliczamy:

jeżeli, to istnieje rozwiązanie optymalne – jest to rozwiązanie podstawowe;

jeśli, to znajdziemy komponent, dodajemy go i w ten sposób znajdujemy inne rozwiązanie; – w którym jedna ze zmiennych podstawowych =0. Usuwamy tę zmienną z bazy i wprowadzamy xi. Otrzymaliśmy nową bazę B2, sprzężoną z bazą B1. Następnie obliczamy ponownie.

1. Jeżeli 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ż liczba punktów narożnych jest skończona, a ścisłe zmniejszenie funkcji F(x) uniemożliwia dwukrotne przejście 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 dualnego w stosunku do problemu wykorzystania zasobów

Zadanie. Do wytworzenia dwóch rodzajów produktów P1 i P2 wykorzystuje się cztery rodzaje surowców S1, S2, S3, S4. Podano rezerwy zasobów, czyli liczbę jednostek zasobów wydanych na wytworzenie jednostki produkcyjnej. Znany jest zysk uzyskany z jednostki produkcji P1 i P2. Konieczne jest sporządzenie planu produkcji, w którym zysk ze 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ądź 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 dla każdego rodzaju produktu nie przekroczy dostępnych rezerw

ZadanieII(podwójny)

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

z ograniczeniami:

i warunek nieujemności

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

Znajdź taki zbiór cen (oszacowań) zasobów Y=(y1,y2,…,yn), przy którym całkowite koszty zasobów będą minimalne, pod warunkiem, że koszty zasobów w produkcji każdego rodzaju produktu będą wynosić nie mniej niż zysk (przychód) ze sprzedaży tych produktów

W powyższym modelu bi(i=1,2,…,m) oznacza rezerwę zasobu Si; aij – liczba jednostek zasobu Si zużytych do wytworzenia jednostki produktu Pj(j=1,2,…,n); cj- zysk (przychód) ze sprzedaży jednostki produkcyjnej Pj (lub ceny produktu Pj) .

Załóżmy, że jakaś organizacja zdecydowała się na zakup zasobów S1, S2,..., Sm przedsiębiorstwa i konieczne jest ustalenie optymalnych cen tych zasobów y1, y2,..., ym. Oczywiście organizacja zakupowa jest zainteresowana wydatkami na wszystkie zasoby 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 uzyskany przychód był nie mniejszy niż kwota, którą przedsiębiorstwo może uzyskać w wyniku przetworzenia zasobów na gotowe produkty.

Aby wyprodukować jednostkę produktu P1, zużywa się a11 jednostek zasobu S1, a21 jednostek zasobu S2,...., aj1 jednostek zasobu Si1,......, am1 jednostek zasobu Sm po cenie y1 odpowiednio ,y1,...,yi,...,ym. Zatem, aby zaspokoić wymagania sprzedawcy, koszty zasobów zużytych do wytworzenia jednostki produktu P1 muszą być nie niższe niż jej cena c1, tj. a11y1+a21y2+…+am1ym>=c1.

Podobnie możesz tworzyć ograniczenia w postaci nierówności dla każdego typu produktu P1, P2,…Pn. Po prawej stronie tabeli podano model ekonomiczno-matematyczny i znaczącą interpretację otrzymanego w ten sposób problemu dualnego II.

Ceny surowców y1,y1,…,yi,…,ym otrzymały w literaturze ekonomicznej różne nazwy: księgowość, ukryta, cień . Znaczenie tych imion jest takie, że tak jest warunkowy , „fałszywe” ceny. W odróżnieniu od cen „zewnętrznych” c1,c2,…,cn dla produktów znanych z reguły przed rozpoczęciem produkcji, ceny surowców y1,y2,…,ym Czy wewnętrzny , ponieważ nie są one dane z zewnątrz, ale są ustalane bezpośrednio w wyniku rozwiązania problemu, dlatego częściej nazywane są szacunki zasoby.

10. Zagadnienia wzajemnie dualne 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.

Obydwa zadania mają następujące elementy nieruchomości:

1. W jednym zadaniu poszukuje się maksimum funkcji liniowej, w drugim minimum.

2. Współczynniki zmiennych w funkcji liniowej jednego problemu są swobodnymi członkami systemu ograniczeń w innym.

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

4. Macierze współczynników zmiennych w układach ograniczeń obu problemów podlegają wzajemnej transpozycji.

5. Liczba nierówności w układzie ograniczeń jednego problemu pokrywa się z liczbą zmiennych w innym problemie.

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

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

Dwa problemy programowania liniowego I i II, które mają wskazane właściwości, nazywane są symetrycznymi problemami dualnymi. W dalszej części dla uproszczenia będziemy je po prostu nazywać podwójne zadania.

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

11. Algorytm komponowania problemu dualnego:

1. Zredukuj wszystkie nierówności układu ograniczeń pierwotnego problemu do jednego znaczenia: jeśli w pierwotnym problemie szukają maksimum funkcji liniowej, to sprowadź wszystkie nierówności układu ograniczeń do postaci „<=", а если минимум – к виду ">=". W przypadku nierówności, w których ten wymóg nie jest spełniony, pomnóż przez –1.

2. Zbuduj rozszerzoną macierz układu A, która zawiera macierz współczynników dla zmiennych, kolumnę wolnych wyrazów układu ograniczeń oraz rząd współczynników dla zmiennych w funkcji liniowej.

3. Znajdź macierz transponowaną do macierzy A .

4. Na podstawie otrzymanej macierzy sformułuj problem podwójny oraz warunki nieujemności zmiennych: tworzą funkcję celu problemu dualnego, przyjmując jako współczynniki zmiennych wolne elementy systemu ograniczeń pierwotnego problemu; ułóż system ograniczeń dla problemu dualnego, przyjmując elementy macierzy jako współczynniki dla zmiennych i współczynniki dla zmiennych w funkcji celu pierwotnego problemu jako wyrazy wolne i zapisz nierówności o przeciwnym znaczeniu; zapisz warunek nieujemności zmiennych zadania dualnego.

12. Pierwsze twierdzenie o dualności

Związek pomiędzy optymalnymi rozwiązaniami problemów dualnych ustala się za pomocą twierdzeń o dualności.

Wystarczający znak optymalności.

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

wówczas jest optymalne rozwiązanie pierwotnego problemu I i podwójnego problemu II.

Oprócz wystarczającego znaku optymalności wzajemnie dualnych problemów istnieją inne ważne zależności między ich rozwiązaniami. Przede wszystkim pojawiają się pytania: czy dla każdej pary problemów dualnych zawsze istnieją jednocześnie optymalne rozwiązania; Czy jest możliwe, że jeden z podwójnych problemów ma rozwiązanie, a drugi nie? Odpowiedź na te pytania daje następujące twierdzenie.

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

Fmaks = Zmin lub F(X*)=Z(Y*) .

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

Komentarz. Twierdzenie odwrotne 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 jest nieograniczona.

Znaczenie ekonomiczne pierwszego twierdzenia o dualności.

Plan produkcji X*=(x1*,x2*,…,xn*) i zestaw cen (szacunków) zasobów Y*=(y1*,y2*,…,ym*) okazują się optymalne wtedy i tylko wtedy, gdy zysk (przychód) z produktów, stwierdzony po „zewnętrznych” (z góry znanych) cenach c1, c2,…, cn, jest równy kosztom zasobów po „wewnętrznych” (określanych tylko od rozwiązania problemu) ceny y1 ,y2,…,ym. Dla wszystkich innych planów X I Y W obu problemach zysk (przychód) z produktów jest zawsze mniejszy niż (lub równy) kosztom zasobów.

Znaczenie ekonomiczne pierwszego twierdzenia o dualności można interpretować następująco: przedsiębiorstwu jest obojętne, czy wytwarzać produkty według optymalnego planu X*=(x1*,x2*,…,xn*) i uzyskiwać maksymalny zysk (przychód) Fmax lub sprzedaj zasoby po optymalnych cenach Y* =(y1*,y2*,…,ym*) i zwracamy ze sprzedaży minimalny koszt zasobów Zmin.

13. Drugie twierdzenie o dualności

Niech zostaną podane dwa wzajemnie podwójne problemy. Jeżeli każdy z tych problemów zostanie rozwiązany metodą sympleksową, wówczas należy doprowadzić je do postaci kanonicznej, dla której należy wprowadzić do systemu ograniczeń Zadania I (w skrócie) T zmiennych nieujemnych i do układu ograniczeń Zadania II () – N zmienne nieujemne, gdzie i(j) jest numerem nierówności, do której wprowadzana jest zmienna dodatkowa.

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

Ustalmy zgodność pomiędzy zmiennymi początkowymi jednego z problemów dualnych i zmiennymi dodatkowymi 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 , następnie i podobnie,

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

Z twierdzenia tego wynika ważny wniosek, że wprowadzona zgodność pomiędzy zmiennymi wzajemnie dualnych problemów w momencie osiągnięcia optymalnego (tj. na ostatnim etapie rozwiązywania każdego problemu metodą simplex) reprezentuje zgodność pomiędzy główny(z reguły nierówne zero) zmienne jednego z problemów podwójnych i nie-rdzeniowe(równe zero) zmienne innego problemu, gdy tworzą możliwe rozwiązania podstawowe.

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

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

14. Obiektywnie określone oceny i ich znaczenie

Składniki optymalnego rozwiązania problemu dualnego nazywane są optymalnymi (podwójnymi) estymatorami problemu pierwotnego. Wezwał ich akademik L.V. Kantorowicz obiektywnie określone” szacunki ( w literaturze nazywane są także ukrytym dochodem) .

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

Zatem obiektywnie określone oceny zasobów określają stopień niedoboru zasobów: zgodnie z optymalnym planem produkcji zasoby rzadkie (tj. w pełni wykorzystane) otrzymują ocenę niezerową, a zasoby nierzadkie otrzymują ocenę zerową. Wartość y*i jest oceną i-tego zasobu. Im wyższa wartość oszacowania y*i, tym większa rzadkość zasobu. Dla zasobu, który nie jest rzadki y*i=0.

Zatem w optymalnym planie produkcji można uwzględnić tylko dochodowe, nierentowne rodzaje produktów (jednak kryterium rentowności jest tutaj wyjątkowe: cena produktu nie przekracza kosztów zasobów zużytych do jego wytworzenia, ale jest dokładnie im równe).

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ę.

Ocena dualna może służyć jako narzędzie analizy i podejmowania właściwych decyzji w warunkach stale zmieniającej się produkcji. Przykładowo za pomocą obiektywnie określonych szacunków zasobów możliwe jest porównanie optymalnych kosztów warunkowych i wyników produkcji.

Obiektywnie określone szacunki zasobów pozwalają ocenić wpływ nie jakichkolwiek, a jedynie stosunkowo niewielkich zmian w zasobach. W przypadku nagłych zmian same szacunki mogą ulec zmianie, co uniemożliwi ich wykorzystanie do analizy efektywności produkcji. Na podstawie wskaźników obiektywnie określonych ocen można wyznaczyć wyliczone normy zastępowalności zasobów, przy czym zastąpienia dokonywane w granicach stabilności ocen dualnych nie wpływają na efektywność planu optymalnego. Wniosek. Podwójne szacunki 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. Stwierdzenie problemu transportowego w oparciu o kryterium kosztu.

TK – problem najbardziej ekonomicznego planu transportu jednorodnego lub wymiennego produktu z punktu produkcji (stacje początkowe) do punktów konsumpcji (stacje docelowe) – jest najważniejszym problemem szczegółowym LP, który ma szerokie zastosowania praktyczne nie tylko z powodu problemów transportowych.

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

Najprostsze sformułowanie specyfikacji technicznych według kryterium kosztu jest następujące: w T w punktach wyjścia A1,…,Am znajdują się odpowiednio a1,…,am jednostki jednorodnego ładunku (zasobów), które należy dostarczyć N konsumenci B1,…,Bn w ilościach b1,…,bn jednostek (potrzeb). Znane są koszty transportu Cij przewiezienia jednostki ładunku z i-tego punktu wyjścia do j-tego punktu konsumpcji.

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

Dla przejrzystości warunki specyfikacji technicznej prezentujemy w formie tabeli tzw dystrybucja .

Dostawca	Konsument			Zapas ładunku
Potrzebować

Tutaj ilość ładunku przewieziona z i-tego punktu wyjścia do j-tego miejsca przeznaczenia jest równa xij, stan ładunku w i-tym punkcie wyjścia jest określony przez wartość ai>=0, a zapotrzebowanie na ładunek w j-tym miejscu docelowym wynosi bj>=0 . Zakłada się, że wszystkie xij>=0.

Macierz nazywa się matryca taryfowa (koszty lub koszty transportu).

Plan zadań transportowych nazywa się macierzą, gdzie każda liczba xij oznacza liczbę jednostek ładunku, które należy dostarczyć z i-tego punktu wyjścia do j-tego miejsca przeznaczenia. Macierz xij nazywa się macierz transportu.

Całkowite koszty całkowite związane z realizacją planu transportu 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 rezerw (2);

– ograniczenia dla konsumentów (2);

– warunki nieujemne (3).

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

Układ więzów 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 możliwości rozwiązania problemu transportowego

Aby problem transportowy miał dopuszczalne plany, konieczne i wystarczające jest spełnienie równości

Istnieją dwa rodzaje problemów 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ą zapotrzebowanie konsumentów lub zapotrzebowanie konsumentów jest większe niż rzeczywiste łączne moce produkcyjne dostawców, tj.

Model otwarty można przekształcić w model zamknięty. Jeśli więc, to do matematycznego modelu problemu transportowego wprowadza się fikcyjny (n+1)-ty cel podróży. W tym celu w macierzy zadań przewidziana jest dodatkowa kolumna, dla której popyt jest równy różnicy pomiędzy łącznymi mocami dostawców a rzeczywistym zapotrzebowaniem odbiorców:

Wszystkie stawki za dostawę ładunku do tego momentu zostaną uznane za równe zeru. Przekształca to otwarty model problemu w model zamknięty. Dla nowego problemu funkcja celu jest zawsze taka sama, ponieważ ceny za dodatkowy transport są równe zeru. Inaczej mówiąc, fikcyjny konsument nie narusza zgodności systemu ograniczeń.

Jeżeli zatem zostanie wprowadzony fikcyjny (m+1)-ty punkt wyjścia, do którego przypisana jest rezerwa ładunku równa.

Taryfy za dostawę towarów od tego fikcyjnego dostawcy są ponownie ustalane na zero. Do macierzy zostanie dodany jeden wiersz, nie będzie to miało wpływu na funkcję celu, a układ ograniczeń problemu stanie się spójny, czyli możliwe stanie się znalezienie planu optymalnego.

Dla problemu transportu ważne jest następujące twierdzenie.

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

Z twierdzenia wynika, że ​​każdy układ referencyjny musi posiadać (m-1)(n-1) zmienne wolne równe zeru oraz zmienne bazowe m+n-1.

Planu transportu zadania transportowego będziemy szukać bezpośrednio w tabeli dystrybucyjnej. Załóżmy, że jeśli zmienna xij przyjmie wartość, to wpiszemy tę wartość do odpowiedniej komórki (I,j), natomiast jeśli xij=0, to komórkę (I,j) pozostawimy wolną. Uwzględnienie twierdzenia o rzędzie macierzy w tablicy rozkładu plan referencyjny musi zawierać m+n-1 zajęte komórki, a reszta będzie bezpłatna.

Podane wymagania dotyczące planu referencyjnego nie są jedynymi. Plany referencyjne muszą spełniać kolejny wymóg związany z cyklami.

Zbiór komórek macierzy transportu, w którym dwie i tylko dwie sąsiednie komórki znajdują się w jednym rzędzie lub w jednej kolumnie, a ostatnia komórka zbioru leży w tym samym wierszu lub kolumnie co pierwsza, nazywa się zamkniętym cykl .

Graficznie cykl jest zamkniętą linią przerywaną, 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 jest w rzędzie, a drugie w kolumnie. Jeżeli linia łamana 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 problemów transportowych:

1) dopuszczalny plan problemu transportowego jest planem odniesienia wtedy i tylko wtedy, gdy z komórek zajmowanych przez ten plan nie można utworzyć żadnego cyklu;

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

17. Konstrukcja wstępnego planu odniesienia

Zasada „narożnika północno-zachodniego”.

Aby sporządzić wstępny plan transportu, wygodnie jest zastosować zasadę „narożnika północno-zachodniego”, która jest następująca.

Wypełnianie będziemy rozpoczynać od lewego górnego rogu, umownie zwanego „rogem północno-zachodnim”, przesuwając się dalej wzdłuż linii w prawo lub w dół kolumny. Wstawmy do komórki (1; 1) mniejszą z liczb a1 i b1, czyli . Jeżeli wówczas 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 .

Jeśli, to pierwsza linia jest podobnie „zamknięta”, tj. dla . Przystępujemy do wypełniania 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łniania kolejnej trzeciej komórki wzdłuż drugiej linii lub w drugiej kolumnie. Będziemy kontynuować ten proces, aż w pewnym momencie wyczerpią się zasoby i potrzeby. Ostatnia wypełniona komórka będzie znajdować się w ostatniej n-tej kolumnie i w ostatnim m-tym wierszu.

Zasada „minimalnego elementu”.

Wstępny plan referencyjny, zbudowany według zasady „narożnika północno-zachodniego”, zwykle okazuje się bardzo odległy od optymalnego, gdyż przy jego ustalaniu nie uwzględnia się wartości kosztowych cij. Dlatego dalsze obliczenia będą wymagały wielu iteracji, aby osiągnąć optymalny plan. Liczbę iteracji można zmniejszyć, jeśli początkowy plan zostanie zbudowany zgodnie z zasadą „minimum elementu”. Jego istota polega na tym, że na każdym etapie odbywa się maksymalne możliwe „przemieszczenie” ładunku do klatki przy minimalnej taryfie cij. Wypełnianie tabeli zaczynamy od komórki odpowiadającej najmniejszemu elementowi cij macierzy taryfowej. W komórce z najniższą taryfą umieszczana jest niższa z cyfr ai lub bj . Wówczas wiersz odpowiadający dostawcy, którego zapasy zostały całkowicie wyczerpane, lub kolumna odpowiadająca klientowi, którego zapotrzebowanie zostało całkowicie zaspokojone, nie jest brany pod uwagę. Może zaistnieć konieczność jednoczesnego wyeliminowania wiersza i kolumny, jeśli zapasy dostawcy zostaną całkowicie wyczerpane, a zapotrzebowanie odbiorcy zostanie w pełni zaspokojone. Następnie z pozostałych komórek tabeli wybierana jest ponownie 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 problemu transportowego metodą potencjałów jest podobna do zasady rozwiązywania problemu LP metodą simplex, a mianowicie: najpierw znajduje się plan referencyjny problemu transportowego, a następnie sukcesywnie go udoskonalane aż do uzyskania planu optymalnego.

Istota metody potencjalnej jest następująca. Po znalezieniu wstępnego referencyjnego planu transportu każdemu dostawcy (w każdym wierszu) przypisuje się pewną liczbę zwaną potencjałem dostawcy Ai, a każdemu konsumentowi (w każdej kolumnie) przypisuje się pewną liczbę zwaną potencjałem konsumenta.

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

Aby rozwiązać problem transportowy metodą potencjalną, należy:

1. Skonstruuj podstawowy plan transportu zgodnie z jedną z podanych zasad. Liczba wypełnionych komórek musi wynosić m+n-1.

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

3. Sprawdź optymalność, tj. w przypadku wolnych komórek oblicz szacunki. Jeśli to transport jest celowy, a plan X jest optymalny - znak optymalności. Jeśli jest choć jedna różnica, przejdź do nowego planu referencyjnego. W sensie ekonomicznym wartość charakteryzuje zmianę całkowitych kosztów transportu, jaka nastąpi w wyniku jednorazowej dostawy przez i-tego dostawcę do j-tego konsumenta. Jeśli to pojedyncza dostawa doprowadzi do oszczędności w kosztach transportu, a jeśli - do ich wzrostu. W związku z tym, jeśli wśród kierunków bezpłatnych dostaw nie ma kierunków oszczędzających koszty transportu, wówczas powstały plan jest optymalny.

4. Spośród liczb dodatnich wybiera się maksimum i konstruuje cykl przeliczeń dla wolnej komórki, której odpowiada. Po zbudowaniu cyklu dla wybranej wolnej komórki należy przejść do nowego planu odniesienia. W tym celu konieczne jest przesunięcie obciążeń w ogniwach podłączonych do danego wolnego ogniwa poprzez cykl przeliczeń.

a) Każdej z komórek połączonych cyklem z daną wolną komórką przypisany jest pewien znak, a ta wolna komórka to „+”, a wszystkim pozostałym komórkom (wierzchołki cyklu) przypisane są na przemian znaki „–” i „ +”. Nazwiemy te komórki minusem i plusem.

b) W ujemnych komórkach cyklu znajdujemy minimalną podaż, którą oznaczamy. Do tej wolnej komórki przenoszona jest mniejsza z liczb xij znajdujących się w komórkach ujemnych. Jednocześnie liczbę tę dodaje się do odpowiednich liczb w komórkach ze znakiem „+” i odejmuje od liczb w komórkach minus. Komórka, która była wcześniej wolna, zostaje zajęta i wchodzi na płaszczyznę wsparcia; a komórka minus, która zawierała minimum liczb xij, jest uważana za wolną i opuszcza plan wsparcia.

Tym samym ustalono nowy plan odniesienia. Opisane powyżej przejście z jednego planu odniesienia do drugiego nazywa się przesunięciem w cyklu przeliczeniowym. Po przesunięciu w cyklu przeliczeń 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, wówczas tylko jedna z tych komórek jest zwalniana, a pozostałe pozostają zajęte z zerowym zapasem.

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

19. Pojęcie programowania dynamicznego.

DP (planowanie) to matematyczna metoda znajdowania optymalnych rozwiązań problemów wieloetapowych (wieloetapowych). Niektóre z tych problemów w naturalny sposób dzielą się na osobne etapy (etapy), ale zdarzają się problemy, w których trzeba sztucznie wprowadzić podział, aby można je było rozwiązać metodą DP.

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

Zasada optymalności R. Bellmana.

Znaczenie podejścia realizowanego 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ć kontrolowany system (obiekt) z podanym ważnym stwierdza i akceptowalne działy;

2. zadanie musi umożliwiać interpretację jako proces wieloetapowy, którego każdy etap polega na akceptacji 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 na każdym z nich;

4. stan systemu na każdym etapie musi być opisany tym samym (w składzie) zestawem parametrów;

5. kolejny stan, w jakim znajduje się system po wybraniu rozwiązania km kroku, zależy tylko od podjętej decyzji i stanu początkowego k- krok. Właściwość ta jest fundamentalna z punktu widzenia ideologii programowania dynamicznego i nazywa się żadnych konsekwencji .

Rozważmy zagadnienia stosowania modelu programowania dynamicznego w formie uogólnionej. Niech zadaniem będzie sterowanie jakimś abstrakcyjnym obiektem, który może znajdować się w różnych stanach. Aktualny stan obiektu będzie identyfikowany za pomocą pewnego zestawu parametrów, które będą dalej oznaczane przez S i nazywane wektor stanu. Zakłada się, że dany jest zbiór S wszystkich możliwych stanów. Dla obiektu zdefiniowany jest także zbiór dopuszczalne kontrole(działania kontrolne) X, który bez utraty ogólności można uznać za zbiór liczbowy. Działania kontrolne mogą być przeprowadzane w dyskretnych momentach czasu i zarządzania rozwiązanie polega na wyborze jednego z elementów sterujących. Plan zadania lub strategia zarządzania nazywa się wektorem x=(x1,x2,…,xn-1), którego składowymi są elementy sterujące wybierane na każdym etapie procesu. W świetle oczekiwanych żadnych następstw pomiędzy każdymi dwoma kolejnymi stanami obiektu Sk i Sk+1 istnieje znana zależność funkcjonalna, która obejmuje także wybrane sterowanie: . Zatem ustalenie stanu początkowego obiektu i wybranie planu X jasno określić trajektoria zachowania obiekt.

Kontroluj efektywność 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ą terminami addytywna funkcja celu , charakteryzujących ogólną efektywność zarządzania obiektem. ( Notatka , że definicja funkcji fk(xk,Sk) zawiera zakres wartości dopuszczalnych xk , a obszar ten z reguły zależy od aktualnego stanu Sk). Optymalna kontrola , dla danego stanu początkowego S1 sprowadza się do wyboru takiego optymalnego planu x* , przy którym jest to osiągane maksymalna ilość wartości fk na odpowiedniej trajektorii.

Podstawową zasadą programowania dynamicznego jest to, że w każdym kroku nie należy dążyć do izolowanej optymalizacji funkcji fk(xk,Sk), lecz wybrać optymalne sterowanie x*k przy założeniu, że wszystkie kolejne kroki są optymalne. Formalnie zasada ta jest realizowana poprzez stwierdzenie na każdym kroku k warunkowe optymalne kontrole , zapewniając największą całkowitą wydajność począwszy od tego kroku, zakładając, że bieżący stan to S.

Niech Zk(s) oznaczają maksymalną wartość sumy funkcji fk na wszystkich etapach od k zanim P(otrzymywany przy optymalnej kontroli na danym odcinku procesu), pod warunkiem, że obiekt znajduje się na początku etapu k jest w stanie S. Wtedy funkcje Zk(s) muszą spełniać relację powtarzalności:

Ten stosunek nazywa się podstawowa relacja powtarzalności (podstawowe równanie funkcyjne) Programowanie dynamiczne. Implementuje 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, późniejsze zarządzanie (decyzje menedżerskie) musi być optymalne w stosunku do cocmo Iania ,wynikające z decyzji podjętej w kroku k .

Główna relacja pozwala nam 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 jedynie do sterowania obiektami, dla których wybór optymalnego sterowania nie jest zależny od tła sterowanego procesu, czyli od tego, w jaki sposób system doszedł do swojego aktualnego stanu. To właśnie ta okoliczność pozwala nam rozłożyć problem i umożliwić jego praktyczne rozwiązanie.

Dla każdego konkretnego zadania równanie funkcjonalne ma swoją specyficzną formę, ale z pewnością musi zachować powtarzalny charakter nieodłącznie związany z wyrażeniem (*) i ucieleśniającym podstawową ideę zasady optymalności.

20. Pojęcie modeli gier.

Model matematyczny sytuacji konfliktowej nazywa się gra , strony zaangażowane w konflikt – gracze, a rezultatem konfliktu jest wygrać.

Dla każdej sformalizowanej gry, zasady , te. system warunków określający: 1) opcje działań graczy; 2) ilość informacji, jakie każdy gracz posiada na temat zachowań swoich partnerów; 3) zysk, do którego prowadzi każdy zestaw działań. Zazwyczaj wygraną (lub przegraną) można określić ilościowo; na przykład możesz wycenić przegraną jako zero, wygraną jako jeden, a remis jako 1/2. Kwantyfikacja wyników gry nazywa się Zapłata .

Gra nazywa się łaźnia parowa , jeśli bierze w nim udział dwóch graczy, oraz wiele , jeśli liczba graczy jest większa niż dwóch. Będziemy brać pod uwagę tylko gry deblowe. W grę wchodzi 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 wygranych obu stron wynosi zero. Aby ukończyć zadanie gry, wystarczy wskazać wartość jednego z nich . Jeśli wyznaczymy A– wygrana jednego z graczy, B – wygraną drugiego, a następnie do gry o sumie zerowej b = –A, dlatego wystarczy rozważyć np A.

Nazywa się wybór i wdrożenie jednego z działań przewidzianych w zasadach postęp gracz. Ruchy mogą być osobisty I losowy . Osobisty ruch – jest to świadomy wybór przez gracza jednego z możliwych działań (na przykład ruchu w grze w szachy). Zestaw możliwych opcji każdego ruchu osobistego jest regulowany przez reguły gry i zależy od całości poprzednich ruchów obu stron.

Losowy ruch – jest to akcja wybrana losowo (na przykład wybranie karty z przetasowanej talii). Aby gra mogła zostać zdefiniowana matematycznie, reguły gry muszą określać każdy losowy ruch rozkład prawdopodobieństwa możliwe rezultaty.

Niektóre gry mogą składać się wyłącznie z ruchów losowych (tzw. czysty hazard) lub wyłącznie 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 przyszłości będziemy brać pod uwagę wyłącznie 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ń drugiego gracza. Szczególną klasą gier są tzw. „gry z pełną informacją”. Gra z pełną informacją to gra, 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 zawierających pełne informacje są szachy, warcaby i dobrze znana gra w kółko i krzyżyk. Większość gier o znaczeniu praktycznym nie należy do klasy gier z pełną informacją, gdyż niepewność co do działań przeciwnika jest zwykle istotnym elementem sytuacji konfliktowych.

Jednym z głównych pojęć teorii gier jest koncepcja strategie .

Strategia Gracz to zbiór zasad, które określają wybór jego akcji przy każdym osobistym ruchu, w zależności od aktualnej sytuacji. Zwykle podczas 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 gracz będzie podejmował z wyprzedzeniem (w reakcji na daną sytuację). Oznacza to, że gracz wybrał konkretną strategię, którą można określić w postaci listy zasad lub programu. (W ten sposób możesz grać w grę za pomocą komputera.) Gra nazywa się ostateczny , jeśli każdy gracz ma skończoną liczbę strategii, oraz nieskończony .– W przeciwnym razie.

W celu decydować gra , lub znajdź rozwiązanie gry , dla każdego gracza powinniśmy wybrać strategię spełniającą warunek optymalność , te. jeden z graczy musi otrzymać maksymalna wygrana, gdy drugi gracz trzyma się swojej strategii, w tym samym czasie drugi gracz musi to zrobić minimalna strata , jeśli pierwszy będzie trzymał się swojej strategii. Takie strategie nazywane są optymalny . Strategie optymalne również muszą spełniać ten warunek zrównoważony rozwój , te. Porzucenie strategii w tej grze musi być niekorzystne dla któregokolwiek z graczy.

Jeśli gra powtarza się kilka razy, gracze mogą nie być zainteresowani wygrywaniem i przegrywaniem w każdej konkretnej grze, ale A średnia wygrana (przegrana) we wszystkich partiach.

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

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

Najlepsza gra, w której gracz A To ma T strategii i gracza V – str strategii nazywa się grą m×n.

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

Pozwól graczowi A ma T strategie osobiste, które oznaczamy jako A1, A2,…, Am. Pozwól graczowi W dostępny N strategie osobiste, oznaczmy je B1,B2,…,Bn.

Niech każda ze stron wybierze konkretną strategię; dla nas będzie to Ai, dla wroga Bj. W wyniku wyboru przez graczy dowolnej pary strategii Ai i Bj (), wynik gry jest jednoznacznie określony, tj. wygrane gracza aij A(dodatni lub negatywny) 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 matryca płatności Lub matryca gry. Wiersze tej macierzy odpowiadają strategiom gracza A, a kolumny – 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 gracza AI A należy oczekiwać, że gracz W odpowie na nie jedną ze strategii Bj, dla której gracz wygrywa A minimalny (gracz W ma na celu „zaszkodzenie” graczowi A).

Oznaczmy przez najmniejsze wygrane gracza A gdy wybiera strategię Ai dla wszystkich możliwych strategii gracza W(najmniejsza liczba w I wiersz macierzy płatności), tj.

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

Zadzwońmy najniższa cena gry, Lub maksymalne wygrane (maxmin). Jest to gwarantowana wygrana gracza A przy dowolnej strategii gracza B. Stąd,

Strategia odpowiadająca maximinowi nazywa się strategia maksymalizacji . Gracz W zainteresowany zmniejszeniem wygranych gracza A, wybierając strategię Bj bierze pod uwagę maksymalną możliwą wypłatę A. Oznaczmy

Spośród wszystkich liczb wybierz najmniejszą

i zadzwońmy najwyższa cena gry Lub wygrana minimaxu(minimaks). Ego gwarantowało stratę gracza B. Dlatego,

Strategia odpowiadająca minimaxowi nazywa się strategia minimaxu.

Zasada, która nakazuje graczom wybierać najbardziej „ostrożne” strategie minimax i maximin, nazywa się zasada minimaxu . Zasada ta wynika z rozsądnego założenia, że ​​każdy gracz dąży do osiągnięcia celu przeciwnego do celu przeciwnika.

Twierdzenie. Niższa cena gry nie zawsze przekracza górną cenę gry .

Jeżeli górna i dolna cena gry są takie same, wówczas nazywa się sumę wartości górnej i dolnej ceny gry czysta cena gry, Lub kosztem gry. Strategie Minimax odpowiadające cenie gry to optymalne strategie , i ich całość - optymalne rozwiązanie Lub rozwiązanie gry. W tym przypadku gracz A otrzymuje maksimum gwarantowane (niezależne od zachowania gracza) W) wygrana w i odtwarzacz W osiąga gwarantowane minimum (niezależnie od zachowania gracza A) przegrywający w. Mówią, że rozwiązanie gry ma stabilność , te. Jeśli jeden z graczy będzie trzymał się swojej optymalnej strategii, odejście od optymalnej strategii nie będzie opłacalne dla drugiego.

Jeśli jeden z graczy (np A) trzyma się swojej optymalnej strategii, a drugi gracz (W) w jakikolwiek sposób odejdzie od swojej optymalnej strategii dla gracza, który dokonał odstępstwa, nigdy nie będzie to opłacalne; takie odchylenie gracza W może co najwyżej pozostawić wygraną bez zmian. a w najgorszym przypadku zwiększ go.

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

Para czystych strategii i 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 istnieje, nazywa się punkt mocy. W geometrii punkt na powierzchni, który ma tę właściwość, że ma jednocześnie minimum w jednej współrzędnej i maksimum w drugiej, nazywa się moc punkt, przez analogię termin ten jest używany w teorii gier.

Gra dla której , zwany bawienie się punktem zasilania. Elementem posiadającym tę właściwość jest punkt siły macierzy.

Zatem dla każdej gry z punktem mocy istnieje rozwiązanie wyznaczające parę optymalnych strategii dla obu stron, różniących 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, co jest jednocześnie jego dolną i górną ceną.

2) Jeśli jedna ze stron będzie trzymać się swojej optymalnej strategii, a druga odejdzie od własnej, wówczas strona odstępująca może tylko stracić i w żadnym wypadku nie może zwiększyć swoich wygranych.

W teorii gier udowodniono, że w szczególności każda gra z pełną informacją ma punkt mocy, a zatem każda taka gra ma rozwiązanie, czyli istnieje para optymalnych strategii obu stron, dających średnią wypłatę równa cenie gry. Jeśli gra z pełnymi informacjami składa się wyłącznie z ruchów osobistych, to gdy każda ze stron zastosuje swoją optymalną strategię, powinna zawsze zakończyć się dobrze określonym wynikiem, a mianowicie wygraną dokładnie równą kosztowi gry.

22. Rozwiązanie gry w strategiach mieszanych.

Wśród skończonych gier o znaczeniu praktycznym gry z punktem siły są stosunkowo rzadkie; bardziej typowym przypadkiem jest sytuacja, 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 licząc na rozsądnie działającego przeciwnika, o wyborze tym powinna decydować zasada minimax. Stosując się do naszej strategii maximin, przy każdym zachowaniu przeciwnika w oczywisty sposób gwarantujemy sobie wygraną równą niższej cenie gry α.Takie strategie kombinowane, polegające na zastosowaniu kilku czystych strategii, naprzemiennie według prawa losowego z pewien stosunek częstotliwości, nazywane są w teorii gier strategie mieszane

Strategia mieszana Sa gracz A to zastosowanie czystych strategii A1,A1,…,Ai,…,Am z prawdopodobieństwami p1,p2,…pi,…pm, a suma prawdopodobieństw jest równa 1: . Strategie mieszane gracza A są zapisane w postaci macierzy

lub jako ciąg Sa=(p1,p2,…,pi,…,pm).

Podobnie, mieszane strategie gracza B są oznaczone przez:

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

gdzie suma prawdopodobieństw pojawienia się strategii jest równa 1: .

Oczywiście każda strategia czysta jest szczególnym przypadkiem strategii mieszanej, w której wszystkie strategie oprócz jednej stosowane są z zerowymi częstotliwościami (prawdopodobieństwami), a ta z częstotliwością (prawdopodobieństwem) równym 1.

Okazuje się, że stosując nie tylko strategie czyste, ale także strategie mieszane, możliwe jest dla każdej skończonej gry uzyskanie rozwiązania, czyli pary takich (w ogólnym przypadku mieszanych) strategii, że gdy obaj gracze z nich skorzystają, wypłata będzie równa cenie gry i kiedy Każde jednostronne odchylenie od optymalnej strategii może zmienić wypłatę jedynie w kierunku niekorzystnym dla dewianta. Tak więc, w oparciu o zasadę minimax, określa się to optymalne rozwiązanie (Lub rozwiązanie) gry: to para optymalnych strategii w ogólnym przypadku mieszany, mający następującą właściwość: jeśli jeden z graczy trzyma się swojej optymalnej strategii, wówczas odejście od własnej strategii nie może być opłacalne dla drugiego. Nazywa się wypłatą odpowiadającą rozwiązaniu optymalnemu kosztem gry v . Cena gry spełnia nierówność:

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

Złożone oświadczenie stanowi treść tzw podstawowe twierdzenie teorii gier. Twierdzenie to zostało po raz pierwszy udowodnione przez Johna von Neumanna w 1928 roku. Znane dowody twierdzenia są stosunkowo złożone; Dlatego podamy jedynie jego sformułowanie.

Każda skończona gra ma co najmniej jedno optymalne rozwiązanie, prawdopodobnie spośród strategii mieszanych.

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

Niech będzie – parę optymalnych strategii. Jeżeli czysta strategia jest zawarta w optymalnej strategii mieszanej z niezerowym prawdopodobieństwem, wówczas nazywa się ją aktywny (przydatny) .

Sprawiedliwy twierdzenie o strategiach aktywnych: jeśli jeden z graczy będzie trzymał się swojej optymalnej strategii mieszanej, to wypłata pozostanie niezmieniona i równa kosztowi gry v, jeśli drugi gracz nie przekroczy granic swoich aktywnych strategii.

Gracz może wykorzystać dowolną ze swoich aktywnych strategii w czystej postaci, a także może je mieszać w dowolnych proporcjach.

Twierdzenie to ma ogromne znaczenie praktyczne – dostarcza konkretnych modeli znajdowania optymalnych strategii w przypadku braku punktu siodłowego.

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

Gra, w której nie ma punktu siodłowego, zgodnie z podstawowym twierdzeniem teorii gier optymalne rozwiązanie istnieje i jest określone przez parę strategii mieszanych I.

Aby je znaleźć, korzystamy z twierdzenia o strategiach aktywnych. Jeśli gracz A trzyma się swojej optymalnej strategii , wówczas jego średnia wygrana będzie równa cenie gry w, niezależnie od aktywnej strategii, z której korzysta gracz W. W grze 2x2 strategia dowolnego przeciwnika jest aktywna, jeśli nie ma środkowego punktu. Wygrane gracza A(strata gracza W)– zmienna losowa, której matematycznym oczekiwaniem (wartością średnią) jest cena gry. Zatem wypłata przeciętnego gracza A(strategia optymalna) będzie równa w zarówno dla strategii pierwszego, jak i drugiego wroga.

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

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

Gracz otrzymuje tę samą średnią wygraną A, jeśli drugi gracz zastosuje strategię B2, tj. . Uwzględniając to, otrzymujemy układ równań pozwalający określić optymalną strategię i ceny gier w:

Rozwiązując ten układ otrzymujemy optymalną strategię

i cena gry.

Zastosowanie twierdzenia o strategiach aktywnych w poszukiwaniach – optymalna strategia gracza W, stwierdzamy, że dotyczy to każdej strategii czysto gracza A (A1 Lub A2) średnia strata gracza W równa cenie gry w, tj.

Następnie optymalną strategię wyznaczają wzory: .

Problem rozwiązania gry, jeśli jej macierz nie zawiera punktu siodłowego, jest tym trudniejszy, im większe są wartości 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. Wymiar macierzy można zmniejszyć poprzez wykluczenie powielanie i oczywiście nierentowny strategie.

Duplikować nazywane są strategiami, które odpowiadają tym samym wartościom elementów w macierzy płatności, tj. macierz zawiera identyczne wiersze (kolumny).

Jeżeli wszystkie elementy i-tego rzędu macierzy są mniejsze od odpowiednich elementów k-tego rzędu, to i-ta strategia dla gracza A nieopłacalne (mniejszy zysk).

Jeżeli wszystkie elementy r-tej kolumny macierzy są większe od odpowiednich elementów j-tej kolumny, to dla gracza W R-ta strategia jest nieopłacalna (strata jest większa).

Procedura eliminacji duplikatów i oczywiście nieopłacalnych strategii powinna zawsze poprzedzać rozwiązanie gry.

23. Interpretacja geometryczna gry 2x2

Rozwiązanie gry 2x2 pozwala na jasną interpretację geometryczną.

Niech grę określi macierz płatności P=(aij), i, j=1,2.

Na osi odciętej (ryc.) narysujemy 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 – prawdopodobieństwo p2 strategii A2 .

Narysujmy dwie prostopadłe do osi odciętych poprzez punkty A1 i A2: oś I-I i oś II-II. Na osi I-I nakreślimy wygrane dla strategii A1; na osi II-II – wypłaty dla strategii A2.

Jeśli gracz A zastosuje strategię A1, to jego wypłata w przypadku strategii B1 gracza B wynosi a11, a w przypadku strategii B2 jest równa a12. Liczby a11 i a12 na osi I odpowiadają punktom B1 i B2.

Jeśli gracz A zastosuje strategię A2, to jego wypłata w przypadku strategii B1 gracza B wynosi a21, a w przypadku 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). Mamy dwie proste linie. Direct 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. Gracz wygrywa A odpowiada pewnemu punktowi leżącemu na tej prostej. Średnia wypłata odpowiadająca strategii mieszanej jest określona wzorem a11p1+a21p2 i jest reprezentowana przez punkt M1 na prostej B1B1.

Podobnie konstruujemy segment B2B2 odpowiadający wykorzystaniu strategii B2 przez drugiego gracza. W tym przypadku średnia wygrana jest określona wzorem a12p1+a22p2 i jest reprezentowana przez punkt M2 na bezpośrednim B2B2.

Musimy znaleźć optymalną strategię S*a, czyli taką, dla której minimalna wypłata (dla dowolnego zachowania W) obróci się do maksimum. W tym celu będziemy budować dolny limit wygranych dla strategii B1B2 , tj. linia przerywana B1NB2 zaznaczona na ryc. odważna linia. Ten dolna granica będzie wyrażać minimalne wygrane gracza A z dowolną ze swoich strategii mieszanych; kropkaN , w którym ten minimalny zysk osiąga maksimum i wyznacza rozwiązanie (optymalną strategię) oraz cenę gry. Punkt rzędny N 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 o rozwiązaniu gry zadecydował punkt przecięcia strategii. Jednak nie zawsze tak będzie.

Geometrycznie można określić optymalną strategię jako gracz A, podobnie jak gracz W; w obu przypadkach stosowana jest zasada minimax, przy czym w drugim przypadku konstruowana jest nie dolna, ale górna granica wygranych, a nie maksymalna, ale wyznaczana na niej minimalna.

Jeśli macierz płatności zawiera liczby ujemne, to aby rozwiązać problem graficznie, lepiej przejść do nowej macierzy z elementami nieujemnymi; Aby to zrobić, wystarczy dodać odpowiednią liczbę dodatnią do elementów oryginalnej macierzy. Rozwiązanie gry nie ulegnie zmianie, ale cena gry wzrośnie o tę liczbę. Do rozwiązania gry 2×n, m×2 można zastosować metodę graficzną.

24. Sprowadzenie gry macierzowej do problemu programowania liniowego

W ogólnym przypadku gra m×n nie ma jasnej interpretacji geometrycznej. Jego rozwiązanie jest dość pracochłonne dla dużych T I N, nie nastręcza to jednak zasadniczych trudności, gdyż można je sprowadzić do rozwiązania problemu programowania liniowego. Pokażmy to.

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

Optymalna strategia spełnia następujący wymóg. Zapewnia graczowi Aśrednie wygrane, nie mniejsze niż cena gry w, dla dowolnej strategii gracza W i wygrane równe cenie gry w, z optymalną strategią gracza W. Bez utraty ogólności zakładamy w> 0; można to osiągnąć poprzez wykonanie wszystkich elementów . Jeśli gracz A stosuje strategię mieszaną przeciwko jakiejkolwiek czystej strategii gracza Bj W, wtedy dostaje średnie wygrane , Lub matematyczne oczekiwanie na wygraną (tj. elementy J-Go kolumny macierzy płatności są mnożone termin po terminie przez odpowiednie prawdopodobieństwa strategii A1, A2,..Ai,..Am i wyniki są dodawane).

W przypadku optymalnej strategii wszystkie średnie wypłaty nie są niższe niż cena gry w, zatem otrzymujemy układ nierówności:

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

Cel gracza A - maksymalizuj swoje gwarantowane wygrane, tj. cena gry w.

Dzieląc przez równość okazuje się, że zmienne spełniają warunek: . Maksymalizacja ceny gry w jest równoznaczne z minimalizacją ilości , Dlatego problem można sformułować następująco: określić wartości zmiennych , mamatak, aby spełniały one ograniczenia liniowe(*) I natomiast funkcja liniowa (2*) zastosowane do minimum.

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

Aby określić optymalną strategię, należy wziąć pod uwagę, że gracz W dąży do minimalizacji gwarantowanego zysku, tj. znajdź maks. Zmienne spełniają nierówności

co wynika z faktu, że średnia strata zawodnika W nie przekracza ceny gry, niezależnie od tego, jaką czystą strategię zastosuje gracz A.

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

Zmienne spełniają warunek.

Gra sprowadziła się do następnego problemu.

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

Rozwiązanie problemu programowania liniowego (5*), (6*) wyznacza optymalną strategię. Jednocześnie cena gry. (7*)

Po skompilowaniu rozszerzonych macierzy dla problemów (1*), (2*) i (5*), (6*) upewniamy się, że jedna macierz została uzyskana z drugiej poprzez transpozycję:

Zatem problemy programowania liniowego (1*), (2*) i (5*), (6*) są wzajemnie podwójne. Oczywiście przy wyznaczaniu optymalnych strategii 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źć wykorzystując twierdzenia o dualności.

Rozwiązując dowolną skończoną grę o wymiarach m×n, zaleca się stosować następujący schemat:

1. Wyklucz z matrycy płatności strategie, które w sposób oczywisty są nieopłacalne w porównaniu z innymi strategiami. Takie strategie dla gracza A

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Podstawowe pojęcia modelu sieci:

Wydarzenie, praca, ścieżka.

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

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

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

3. Budowa i organizacja schematu sieci.

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

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

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

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

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

Schemat sieci wykorzystuje czas, koszt i inne cechy pracy.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

7. Sformułowanie problemu programowania liniowego.

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

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

Kryterium stanowi cena MAX kolejnego produktu z grupy zainteresowania f.

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

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

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

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

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

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

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

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

Znajdź minimalną wartość funkcji

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

a11x1 + a22x2 b1

(2.2)a21x1 + a22x2 b2

aM1x1 + aM2x2 bM

(2.3) x1 0, x2 0

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

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

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

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

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

9. Metoda sympleksowa.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Stan równowagi.

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

11. Algorytm rozwiązywania problemu transportowego.

Zastosowanie algorytmu wymaga spełnienia szeregu warunków:

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

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

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

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

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

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

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

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

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

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

12. Modele zarządzania zapasami.

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

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

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

deterministyczny;

probabilistyczny.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15. Proces śmierci i reprodukcji.

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

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

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

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

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

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

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

16. Systemy kolejkowe z awariami.

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

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

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

17. Systemy kolejkowe z oczekiwaniem.

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

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

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

— kanał jest bezpłatny;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19. Geometryczna metoda rozwiązywania gry macierzowej.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

20. Gry dwumacierzowe.

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

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

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

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

niepewność celów;

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

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

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

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

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

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

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

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

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

kryterium wartości oczekiwanej;

kombinacje wartości oczekiwanej i wariancji;

znany poziom graniczny;

najbardziej prawdopodobne wydarzenie w przyszłości.

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

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

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

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

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

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

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

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

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

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

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

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

zmienne sterujące (decyzja),

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

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

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

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

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

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

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

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

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

Problem badań operacyjnych

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

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

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

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

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

Wstęp

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

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

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

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

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

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

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

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

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

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

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

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

1. Podstawowe pojęcia i definicje badań operacyjnych

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

jeśli się uwzględni

∑ P I X I <= I (0.4)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Rozważana jest kombinacja

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

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

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

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

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

Wniosek

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

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

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

Literatura

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

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

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

W. Slinkin

Podręcznik dla studentów uczelni pedagogicznych

na kierunku informatyka

Szadrinsk, 2003

Slinkina I.N.

Badania operacyjne. Podręcznik edukacyjno-metodologiczny. – Shadrinsk: wydawnictwo Państwowego Instytutu Pedagogicznego w Shadrinsk, 2002. - 106 s.

Slinkina I.N. – Kandydat nauk pedagogicznych

Podręcznik przedstawia część teoretyczną kursu Badań Operacyjnych. Jest przeznaczony dla studentów studiów stacjonarnych i niestacjonarnych kierunków realizujących specjalność „Informatyka”.

© Shadrinsk Państwowy Instytut Pedagogiczny

© Slinkina I.N., 2002

Pytania do jednostek w ramach kursu „Badania Operacyjne” 5

1.1. Przedmiot i zadania badań operacyjnych 7

1.2. Podstawowe pojęcia i zasady badań operacyjnych 8

1.3. Matematyczne modele działań 10

1.4. Pojęcie programowania liniowego 12

1,5. Przykłady problemów ekonomicznego programowania liniowego. Problem najlepszego wykorzystania zasobów 13

1.6. Przykłady problemów ekonomicznego programowania liniowego. Problem wyboru optymalnych technologii 15

1.7. Przykłady problemów ekonomicznego programowania liniowego. Problem z mieszaniną 16

1.8. Przykłady problemów ekonomicznego programowania liniowego. Problem transportu 17

1.9. Podstawowe rodzaje rejestracji problemów programowania liniowego 19

1.10. 21 metod konwersji

1.11. Przejście do formy kanonicznej 22

1.12. Przejście do symetrycznej formy zapisu 25

2.1. Interpretacja geometryczna zadania programowania liniowego 28

2.2. Rozwiązywanie problemów programowania liniowego metodą graficzną 29

2.3. Własności rozwiązań problemów programowania liniowego 34

2.4. Ogólna idea metody simplex 35

2.5. Konstrukcja wstępnego planu odniesienia przy rozwiązywaniu problemów programowania liniowego metodą simpleksową 36

2.6. Znak optymalności planu odniesienia. Tabele Simplex 40

2.7. Przejście na najgorszy plan referencyjny. 44

2.8. Transformacje sympleksowe 46

2.9. Optimum alternatywne (znak nieskończoności zbioru planów odniesienia) 51

2.10. Znak nieograniczoności funkcji celu 52

2.11. Pojęcie degeneracji. Monotoniczność i skończoność metody sympleksowej. Zapętlenie 53

2.12. Pojęcie dualności dla problemów symetrycznego programowania liniowego 54

3.1. Asymetryczne problemy dualne 57

3.2. Otwarte i zamknięte modele problemu transportu 61

3.3. Budowa wstępnego planu odniesienia. Zasada 63 narożnika północno-zachodniego

3.4. Budowa wstępnego planu odniesienia. Zasada minimalnego elementu 64

3.5. Budowa wstępnego planu odniesienia. Metoda Vogla 64

3.6. Potencjalna metoda 65

3.7. Rozwiązywanie problemów transportowych przy ograniczeniach przepustowości 69

3.8. Przykłady problemów programowania dyskretnego. Problem transportu kontenerowego. Problem z przydziałem 71

3.9. Istota dyskretnych metod optymalizacji 72

3.10. Problem programowania wypukłego 74

3.11. Metoda mnożnika Lagrange’a 75

3.12. Metody gradientowe 77

4.1. Metody funkcji karnych i barierowych 78

4.2. Programowanie dynamiczne. Podstawowe koncepcje. Istota metod rozwiązywania 79

4.3. Programowanie stochastyczne. Podstawowe pojęcia 81

4.4. Gry macierzowe o sumie zerowej 83

4,5. Strategie czyste i mieszane oraz ich właściwości 85

4.6. Właściwości strategii czystych i mieszanych 88

4.7. Obniżenie gry matrixowej do 92 zł

4.8. Problemy teorii kolejek. Klasyfikacja systemów kolejkowych 94

4.9. Transmisje wydarzeń 96

4.10. Schemat śmierci i reprodukcji 97

4.11. Formuła 99 Little’a

4.12. Najprostsze systemy kolejkowe 101

Pytania do bloków kursu „Badania Operacyjne”

Blok 1

1. Przedmiot i cele badań operacyjnych.

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

3. Matematyczne modele działań.

4. Pojęcie programowania liniowego.

5. Przykłady problemów ekonomicznego programowania liniowego. Zadanie

6. Przykłady problemów ekonomicznego programowania liniowego. Problem wyboru optymalnych technologii.

7. Przykłady problemów ekonomicznego programowania liniowego. Problem z mieszankami.

8. Przykłady problemów ekonomicznego programowania liniowego. Problem z transportem.

9. Podstawowe typy pisania problemów programowania liniowego.

10. Metody konwersji.

11. Przejście do formy kanonicznej.

12. Przejście do symetrycznej formy zapisu.

Blok 2

1. Interpretacja geometryczna problemu programowania liniowego.

2. Rozwiązywanie problemów programowania liniowego metodą graficzną.

3. Własności rozwiązań problemu programowania liniowego.

4. Ogólna idea metody simplex.

5. Konstrukcja wstępnego planu odniesienia przy rozwiązywaniu problemów programowania liniowego metodą simplex.

6. Znak optymalności planu odniesienia. Tabele Simplex.

7. Przejście na nie najgorszy plan referencyjny.

8. Transformacje sympleksowe.

9. Optimum alternatywne (znak nieskończoności zbioru planów odniesienia).

10. Znak nieograniczoności funkcji celu.

11. Pojęcie degeneracji. Monotoniczność i skończoność metody sympleksowej. Zapętlenie.

12. Pojęcie dualności w zagadnieniach symetrycznego programowania liniowego.

Blok 3

1. Asymetryczne problemy dualne.

2. Otwarte i zamknięte modele problemu transportu.

3. Konstrukcja wstępnego planu odniesienia. Zasada „narożnika północno-zachodniego”.

4. Konstrukcja wstępnego planu odniesienia. Reguła minimalnego elementu.

5. Konstrukcja wstępnego planu odniesienia. Metoda Vogla.

6. Metoda potencjałów.

7. Rozwiązywanie problemów transportowych przy ograniczeniach przepustowości.

8. Przykłady problemów programowania dyskretnego. Problem transportu kontenerowego. Problem z przydziałem.

9. Istota dyskretnych metod optymalizacji.

10. Problem programowania wypukłego.

11. Metoda mnożnika Lagrange'a.

12. Metody gradientowe.

Blok 4

1. Metoda funkcji kary i bariery.

2. Programowanie dynamiczne. Podstawowe koncepcje. Istota metod rozwiązywania.

3. Programowanie stochastyczne. Podstawowe koncepcje.

4. Gry macierzowe o sumie zerowej.

5. Strategie czyste i mieszane.

6. Właściwości strategii czystych i mieszanych.

7. Redukcja gry matrix do PLP

8. Problemy teorii kolejek. Klasyfikacja systemów kolejkowych.

9. Strumienie wydarzeń.

10. Schemat śmierci i reprodukcji.

11. Wzór Little'a.

12. Najprostsze systemy kolejkowe.

Blok 1.

Przedmiot i zadania badań operacyjnych

Obecny stan nauki i techniki, w szczególności rozwój komputerowych narzędzi obliczeniowych i matematyczne uzasadnienie teorii, pozwolił w znacznym stopniu uprościć rozwiązywanie wielu problemów stawianych różnym dziedzinom nauki. Wiele problemów sprowadza się do rozwiązania kwestii optymalizacji produkcji i optymalnego sterowania procesem.

Potrzeby praktyki dały początek specjalnym metodom naukowym, które wygodnie łączy się pod nazwą „badania operacyjne”.

Definicja: Przez badania operacyjne rozumiemy zastosowanie matematycznych, ilościowych metod do uzasadniania decyzji we wszystkich obszarach celowej działalności człowieka.

Niech zostaną podjęte pewne działania, aby osiągnąć określony cel. Osoba (lub grupa osób) organizująca wydarzenie ma zawsze pewną swobodę wyboru: można je zorganizować w taki czy inny sposób. Decyzja to wybór spośród szeregu możliwości, jakimi dysponuje organizator.

Konieczność podejmowania decyzji i testowania hipotezy proponowanego rozwiązania potwierdzają matematycznie następujące przykłady:

Zadanie 1. O najlepszym wykorzystaniu zasobów.

Firma produkuje kilka rodzajów produktów. Do ich wytworzenia wykorzystywane są pewne zasoby (w tym ludzie, energia itp.). Należy obliczyć, jak zaplanować pracę przedsiębiorstwa, aby koszty zasobów były minimalne, a zyski maksymalizowane.

Zadanie 2. O mieszankach.

Konieczne jest przygotowanie mieszaniny o określonych właściwościach. Aby to zrobić, możesz użyć niektórych „produktów” (do obliczania diet - produkty spożywcze, do mieszanek paszowych - produkty spożywcze dla zwierząt, do mieszanek technicznych - stopy, płyny do celów technicznych). zadaniem jest dobranie optymalnej ilości produktów (ze względu na cenę) tak, aby otrzymać optymalną ilość mieszanki.

Zadanie 3. Problem z transportem.

Istnieje sieć przedsiębiorstw wytwarzających podobne produkty tej samej jakości oraz sieć konsumentów tych produktów. Konsumentów i dostawców łączą szlaki komunikacyjne (drogi, linie kolejowe, linie lotnicze). Ustalono stawki za transport. Konieczne jest obliczenie optymalnego planu transportu produktów, aby koszty transportu były minimalne, potrzeby wszystkich konsumentów zostały zaspokojone, a wszystkie towary zostały usunięte od dostawców.

W każdym z podanych przykładów mówimy o jakimś wydarzeniu realizującym konkretny cel. Określono pewne warunki charakteryzujące sytuację (w szczególności środki, którymi można się pozbyć). W tych warunkach konieczne jest podjęcie takiej decyzji, aby planowana impreza była w pewnym sensie bardziej opłacalna.

Zgodnie z tymi ogólnymi cechami opracowywane są ogólne metody rozwiązywania podobnych problemów, które razem stanowią schemat metodologiczny i aparat badań operacyjnych.

Obecnie powszechne stają się zautomatyzowane systemy sterowania (ACS) oparte na wykorzystaniu technologii komputerowej. Stworzenie zautomatyzowanego systemu sterowania nie jest możliwe bez wstępnego zbadania kontrolowanego procesu z wykorzystaniem metod modelowania matematycznego. Wraz z rosnącą skalą i złożonością zdarzeń coraz większego znaczenia nabierają matematyczne metody uzasadniania decyzji.

Podstawowe pojęcia i zasady badań operacyjnych

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

Operacja jest zawsze zdarzeniem kontrolowanym, tj. Od obliczeń zależy, jak dobrać parametry charakteryzujące jego organizację. „Organizacja” jest tu rozumiana w szerokim znaczeniu tego słowa, łącznie z zespołem środków technicznych wykorzystywanych w działaniu.

Definicja: Decyzją nazywamy każdy konkretny wybór w oparciu o decydujące parametry.

Definicja: Optymalne rozwiązania to takie, które z tego czy innego powodu są lepsze od innych.

Cel badań operacyjnych– wstępne uzasadnienie ilościowe optymalnych rozwiązań.

Czasem w wyniku badania udaje się wskazać jedno, ściśle określone rozwiązanie, znacznie częściej udaje się zidentyfikować obszar niemal równoważnych rozwiązań optymalnych, w ramach którego można dokonać ostatecznego wyboru.

Samo podejmowanie decyzji wykracza poza zakres badań operacyjnych i wchodzi w zakres kompetencji osoby odpowiedzialnej, częściej – grupy osób, którym nadano prawo dokonania ostatecznego wyboru i na których ciąży odpowiedzialność za ten wybór.

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

Elementy rozwiązania mogą obejmować różne liczby, wektory, funkcje, cechy fizyczne itp. Dla uproszczenia cały zbiór elementów rozwiązania będziemy oznaczać przez x.

Oprócz elementów rozwiązania dowolnego problemu badań operacyjnych podane są także warunki, które są ustalone w stanie problemu i nie mogą zostać naruszone. W szczególności do warunków tych zaliczają się środki (materialne, techniczne, ludzkie), którymi można się pozbyć, oraz inne ograniczenia nałożone na decyzję. Razem tworzą tak zwany „zbiór możliwych rozwiązań”. Oznaczmy ten zbiór X i zapiszemy, że rozwiązanie x należy do tego zbioru: xОХ.

Aby porównać różne rozwiązania pod względem efektywności, trzeba dysponować jakimś kryterium ilościowym, tzw. wskaźnikiem efektywności (funkcją celu). Wskaźnik ten dobiera się tak, aby odzwierciedlał docelową orientację operacji. Za najlepsze rozwiązanie zostanie uznane takie, które w największym stopniu przyczynia się do osiągnięcia celu. Aby wybrać wskaźnik wydajności Z, należy najpierw określić, do czego powinno prowadzić rozwiązanie problemu. Przy wyborze rozwiązania preferowane jest to, które zwiększa wskaźnik efektywności Z do maksimum lub minimum. Na przykład chciałbym zmaksymalizować dochód z operacji; jeżeli wyznacznikiem efektywności są koszty, wskazane jest ograniczenie ich do minimum.

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

Zadanie wyboru wskaźnika wydajności rozwiązuje się indywidualnie dla każdego problemu.

Zadanie 1. O najlepszym wykorzystaniu zasobów.

Celem operacji jest wyprodukowanie maksymalnej liczby towarów. Wskaźnik efektywności Z – zysk ze sprzedaży towarów przy minimalnych kosztach zasobów (max Z).

Zadanie 2. O mieszankach.

Naturalnym wskaźnikiem efektywności, jaki sugeruje sformułowanie problemu, jest cena produktów niezbędnych do powstania mieszaniny, z zastrzeżeniem konieczności zachowania określonych właściwości mieszaniny (min Z).

Zadanie 3. Problem z transportem.

Celem operacji jest zapewnienie dostaw towarów do konsumentów przy minimalnych kosztach transportu. Wskaźnik efektywności Z to całkowity koszt transportu towaru w jednostce czasu (min Z).