Rozwiązywanie problemów MOP (metody optymalizacji). Metodyczne podstawy opracowywania decyzji zarządczych Rozwiązanie nazywa się optymalnym

Programowanie liniowe to dział matematyki zajmujący się metodami znajdowania minimum lub maksimum funkcji liniowej skończonej liczby zmiennych, pod warunkiem, że zmienne spełniają skończoną liczbę ograniczeń w postaci równań liniowych lub nierówności liniowych.

Zatem zadanie ogólne programowanie liniowe(ZLP) można sformułować w następujący sposób.

Znajdź wartości zmiennych rzeczywistych, dla których funkcja celu

przyjmuje minimalną wartość na zbiorze punktów, których współrzędne spełniają system ograniczeń

Jak wiadomo, uporządkowany zbiór wartości N zmienne , , … jest reprezentowane przez punkt w przestrzeni n-wymiarowej. W dalszej części będziemy oznaczać ten punkt X=( , , … ).

W postaci macierzowej problem programowania liniowego można sformułować w następujący sposób:

, A– macierz rozmiarów,

Kropka X=( , , … ), spełniający wszystkie warunki, nazywa się ważny punkt . Nazywa się zbiór wszystkich dopuszczalnych punktów ważny obszar .

Optymalne rozwiązanie (optymalny plan) problem programowania liniowego nazywany jest rozwiązaniem X=( , , … ), należący do obszaru dopuszczalnego i dla którego funkcja liniowa Q przyjmuje wartość optymalną (maksymalną lub minimalną).

Twierdzenie. Zbiór wszystkich możliwych rozwiązań układu ograniczeń problemu programowania liniowego jest wypukły.

Zbiór punktów nazywa się wypukły , jeśli wraz z dowolnymi dwoma punktami zawiera ich dowolną wypukłą kombinację liniową.

Kropka X zwany wypukła kombinacja liniowa punktów, jeżeli spełnione są warunki

Zbiór wszystkich możliwych rozwiązań problemu programowania liniowego to wypukły obszar wielościenny, który będziemy odtąd nazywać wielościan rozwiązań .

Twierdzenie. Jeżeli ZLP ma rozwiązanie optymalne, to funkcja celu przyjmuje wartość maksymalną (minimalną) w jednym z wierzchołków wielościanu rozwiązania. Jeżeli funkcja celu przyjmuje wartość maksymalną (minimalną) w więcej niż jednym punkcie, to przyjmuje tę wartość w dowolnym punkcie będącym wypukłą liniową kombinacją tych punktów.

Wśród wielu rozwiązań systemu M równania liniowe opisujące wielościan rozwiązań, wyróżnia się tzw. rozwiązania podstawowe.

Podstawowe rozwiązanie systemu M równania liniowe z n zmiennymi to rozwiązanie, w którym wszystko n-m zmienne inne niż podstawowe wynoszą zero. W problemach programowania liniowego takie rozwiązania nazywane są dopuszczalne rozwiązania podstawowe (plany referencyjne).

Twierdzenie. Każdemu dopuszczalnemu rozwiązaniu podstawowemu problemu programowania liniowego odpowiada wierzchołek wielościanu rozwiązania i odwrotnie, każdemu wierzchołkowi wielościanu rozwiązania odpowiada dopuszczalne rozwiązanie podstawowe.

Z powyższych twierdzeń wynika ważny wniosek:

Jeśli problem programowania liniowego ma rozwiązanie optymalne, to pokrywa się ono z co najmniej jednym z możliwych rozwiązań podstawowych.

W związku z tym należy szukać optymalnej funkcji liniowej celu zadania programowania liniowego wśród skończonej liczby jego możliwych rozwiązań podstawowych.

Podstawą rozwiązywania problemów ekonomicznych są modele matematyczne.

Model matematyczny problem to zbiór zależności matematycznych opisujących istotę problemu.

• wybór zmiennych problemowych
• opracowanie systemu ograniczeń
• wybór funkcji celu

Zmienne zadania nazywane są wielkościami X1, X2, Xn, które całkowicie charakteryzują proces gospodarczy. Zwykle zapisuje się je jako wektor: X=(X 1, X 2,...,X n).

System ograniczeń Problemy to zbiór równań i nierówności opisujących ograniczone zasoby rozważanego problemu.

Funkcja celu zadania nazywane są funkcją zmiennych zadania, która charakteryzuje jakość zadania i którego ekstremum należy znaleźć.

W przypadek ogólny Problem programowania liniowego można zapisać w następujący sposób:

Zapis ten oznacza: znaleźć ekstremum funkcji celu (1) i odpowiadające mu zmienne X=(X 1, X 2,...,X n) pod warunkiem, że zmienne te spełniają system ograniczeń (2) i nie -warunki negatywne (3) .

Prawidłowe rozwiązanie(planem) problemu programowania liniowego jest dowolny n-wymiarowy wektor X=(X 1 , X 2 ,...,X n), który spełnia układ więzów i warunków nieujemności.

Zbiór wykonalnych rozwiązań (planów) postaci problemu obszar możliwych rozwiązań(ODR).

Optymalne rozwiązanie(plan) zadania programowania liniowego to takie dopuszczalne rozwiązanie (plan) problemu, w którym funkcja celu osiąga ekstremum.

Przykład kompilacji modelu matematycznego

Problem wykorzystania zasobów (surowców)

Stan : schorzenie: Aby wyprodukować n rodzajów produktów, zużywa się m rodzajów zasobów. Utwórz model matematyczny.

Znany:

• b i (i = 1,2,3,...,m) — zasoby każdego i-tego rodzaju zasobu;
• a ij (i = 1,2,3,...,m; j=1,2,3,...,n) - koszt każdego i-tego rodzaju zasobu przy produkcji jednostki objętości j-tego rodzaju produktu;
• c j (j = 1,2,3,...,n) - zysk ze sprzedaży jednostki objętości j-tego rodzaju produktu.

Wymagane jest sporządzenie planu produkcji zapewniającego maksymalny zysk przy danych ograniczeniach zasobów (surowców).

Rozwiązanie:

Wprowadźmy wektor zmiennych X=(X 1, X 2,...,X n), gdzie x j (j = 1,2,...,n) jest wielkością produkcji j-tego typu produkt.

Koszty i-tego rodzaju zasobu na wytworzenie danej objętości x j produktów są równe a ij x j , zatem ograniczenie wykorzystania zasobów na wytworzenie wszystkich typów produktów ma postać:
Zysk ze sprzedaży produktu j-tego rodzaju jest równy c j x j, więc funkcja celu jest równa:

Odpowiedź- Model matematyczny ma postać:

Postać kanoniczna problemu programowania liniowego

W ogólnym przypadku problem programowania liniowego jest zapisywany w taki sposób, że ograniczenia są zarówno równaniami, jak i nierównościami, a zmienne mogą być albo nieujemne, albo dowolnie zmienne.

W przypadku, gdy wszystkie ograniczenia są równaniami i wszystkie zmienne spełniają warunek nieujemności, problem programowania liniowego nazywa się kanoniczny.

Można go przedstawić w notacji współrzędnych, wektorowych i macierzowych.

Problem kanonicznego programowania liniowego w zapisie współrzędnych ma postać:

Problem kanonicznego programowania liniowego w notacji macierzowej ma postać:

• A jest macierzą współczynników układu równań
• X — macierz-kolumna zmiennych zadania
• Ао — macierz-kolumna odpowiednich części systemu ograniczeń

Często stosuje się problemy programowania liniowego, zwane symetrycznymi, które w zapisie macierzowym mają postać:

Sprowadzenie ogólnego problemu programowania liniowego do postaci kanonicznej

W większości metod rozwiązywania problemów programowania liniowego przyjmuje się, że układ więzów składa się z równań i warunków naturalnych nieujemności zmiennych. Jednak przy kompilowaniu modeli problemów ekonomicznych ograniczenia kształtują się głównie w postaci układu nierówności, dlatego konieczna jest możliwość przejścia od układu nierówności do układu równań.

Weźmy nierówność liniową a 1 x 1 +a 2 x 2 +...+a n x n ≤b i dodajmy do jej lewej strony pewną wartość x n+1 tak, że nierówność zamienia się w równość a 1 x 1 +a 2 x 2 + ...+a n x n +x n+1 =b. Co więcej, ta wartość x n+1 jest nieujemna.

Spójrzmy na wszystko na przykładzie.

Sprowadź problem programowania liniowego do postaci kanonicznej:

Rozwiązanie:
Przejdźmy do problemu znalezienia maksimum funkcji celu.
W tym celu zmieniamy znaki współczynników funkcji celu.
Aby przekształcić drugą i trzecią nierówność układu więzów w równania, wprowadzamy nieujemne zmienne dodatkowe x 4 x 5 (w modelu matematycznym operacja ta jest oznaczona literą D).
Zmienną x 4 wprowadza się po lewej stronie drugiej nierówności ze znakiem „+”, ponieważ nierówność ma postać „≤”.
Zmienną x 5 wprowadza się po lewej stronie trzeciej nierówności ze znakiem „-”, ponieważ nierówność ma postać „≥”.
Zmienne x 4 x 5 wprowadza się do funkcji celu ze współczynnikiem. równy zeru.
Problem zapisujemy w formie kanonicznej.

Badania operacyjne to złożona dyscyplina matematyczna zajmująca się konstrukcją, analizą i zastosowaniem modeli matematycznych do podejmowania optymalnych decyzji podczas operacji.

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

Cel badań operacyjnych- ilościowe uzasadnienie decyzji podejmowanych w zarządzaniu organizacjami

Działanie- system kontrolowanych działań, połączonych jednym planem i mających na celu osiągnięcie określonego celu.

Nazywa się zbiór parametrów kontrolnych (zmiennych) podczas operacji decyzja. Rozwiązanie nazywa się do przyjęcia , jeśli spełnia zestaw określonych warunków. Rozwiązanie nazywa się optymalny

, jeśli jest to akceptowalne i według pewnych kryteriów lepsze od innych, a przynajmniej nie gorsze. Znak preferencji

zwane kryterium optymalności. Kryterium optymalności

obejmuje funkcję celu, kierunek optymalizacji lub zbiór funkcji celu i odpowiadających im kierunków optymalizacji. Funkcja celu

jest ilościowym wskaźnikiem preferencji lub skuteczności rozwiązań. Kierunek optymalizacji

- jest to maksimum (minimum), jeśli najkorzystniejsza jest największa (najmniejsza) wartość funkcji celu.

Kryterium może być np. maksymalizacja zysków lub minimalizacja kosztów.

Model matematyczny problemu IO obejmuje:

1) opis zmiennych, które należy znaleźć;

2) opis kryteriów optymalności;– uzasadnić ilościowo i jakościowo podjętą decyzję. Ostateczną decyzję podejmuje odpowiedzialna osoba lub grupa osób zwana decydentem.

Nazywa się wektor spełniający układ więzów akceptowalne rozwiązanieLub plan ZLP. Zbiór wszystkich planów nazywa się ważny obszar Lubobszar możliwych rozwiązań. Nazywa się plan, który zapewnia maksimum (minimum) funkcji celuoptymalnego planu Luboptymalne rozwiązanie dla ZLP. Zatem,rozwiązać PIL – oznacza znalezienie optymalnego planu.

Bardzo łatwo jest przenieść ogólny ZLP do głównego, stosując następujące oczywiste zasady.

Minimalizacja funkcji celu F jest równoznaczne z maksymalizacją funkcji G = – F.

Ograniczenie nierówności jest równoważne równaniu pod warunkiem, że jest to dodatkowa zmienna.

Jeśli dla jakiejś zmiennej X J nie narzuca się warunku nieujemności, wówczas dokonuje się zmiany zmiennej.

Linia pozioma funkcje F, czyli linia, wzdłuż której ta funkcja przyjmuje tę samą stałą wartość Z, tj. F(X 1 , X 2)= C

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

W przypadku dwóch zmiennych zbiór rozwiązań nierówności liniowej (równania) jest półpłaszczyzną (prostą).

Przecięcie tych półpłaszczyzn (i linii prostych, jeśli układ więzów ma równania) reprezentuje możliwy obszar. Jeśli nie jest pusty, to jest zbiorem wypukłym i nazywa się go.

wielokąt rozwiązania W przypadku trzech zmiennych dopuszczalnym obszarem ZLP jest przecięcie półprzestrzeni i ewentualnie płaszczyzn i nazywa się to

wielościan rozwiązańNazywa się układ równań liniowych, układ z podstawą jeśli każde równanie zawiera niewiadomą o współczynniku równym 1, której nie ma w pozostałych równaniach układu. Te niewiadome nazywane są, podstawowy – odpoczynek.

bezpłatny Nazwiemy układ równań liniowych, kanonicznyjeśli jest to system z podstawą i tyle B I ≥ 0. Podstawowym rozwiązaniem w tym przypadku okazuje się plan, gdyż jego składowe są nieujemne. Zadzwońmy do niego podstawowy (Lub) plan wspierający

system kanoniczny. Nazwiemy układ równań liniowych Nazwiemy to OZLP

(KZLP), jeśli układ równań liniowych tego problemu jest kanoniczny, a funkcja celu jest wyrażona tylko w postaci niewiadomych wolnych. Jeżeli w tabeli sympleksu wśród współczynników dowolnej niewiadomej swobodnej znajduje się przynajmniej jeden element dodatni, wówczas możliwe jest przejście do nowego problemu kanonicznego, równoważnego pierwotnemu, w którym określona niewiadoma wolna okazuje się podstawowa (w w tym przypadku jedna z niewiadomych podstawowych staje się wolna).

Twierdzenie 2. (w sprawie poprawy poziomu bazowego) J i w kolumnie x J Jeśli istnieje przynajmniej jeden element dodatni, a relacja kluczowa jest >0, wówczas możliwe jest przejście do równoważnego problemu kanonicznego o nie gorszym projekcie podstawowym.

Twierdzenie 3. (warunek wystarczający optymalności). 0 Jeśli wszystkie elementy wiersza indeksowego tablicy simpleksowej problemu maksymalizacji są nieujemne, to podstawowy projekt tego problemu jest optymalny i przy

na zbiorze planów problemów istnieje maksimum funkcji celu.. Twierdzenie 4(przypadek nieograniczonej funkcji celu) J . J Jeśli wiersz indeksowy tabeli simplex problemu maksymalizacji zawiera element ujemny z

, oraz w nieznanej kolumnie x

wszystkie elementy są dodatnie, to na zbiorze planów problemów funkcja celu nie jest ograniczona z góry.

Metoda Simplex:

Zapisujemy ten KZLP do oryginalnej tabeli simplex.

Jeżeli wszystkie elementy wiersza indeksowego tablicy sympleksowej są nieujemne, to podstawowy plan problemu jest optymalny (Twierdzenie 3).

Jeżeli wiersz indeksowy zawiera element ujemny, nad którym w tabeli nie ma elementu dodatniego, to funkcja celu nie jest ograniczona od góry na zbiorze planów i problem nie ma rozwiązań (Twierdzenie 4).

Jeśli w tabeli nad każdym ujemnym elementem wiersza indeksu znajduje się przynajmniej jeden element dodatni, to należy przejść do nowej tabeli simplex, dla której plan podstawowy nie jest gorszy od poprzedniego (Twierdzenie 2). W tym celu (patrz dowód twierdzenia 1) jeśli jest to system z podstawą i tyle B wybierz kluczową kolumnę w tabeli, u podstawy której znajduje się dowolny ujemny element wiersza indeksu;

wybierz relację kluczową (najmniejszą z relacji

Rozważając wynikową tabelę simplex, z pewnością pojawi się jeden z trzech przypadków opisanych w akapitach. 2, 3, 4. Jeżeli wystąpią sytuacje, o których mowa w ust. 2 lub 3, wówczas proces rozwiązania problemu się kończy, natomiast jeżeli wystąpi sytuacja z kroku 4, to proces jest kontynuowany.

Jeśli weźmiemy pod uwagę, że liczba różnych planów podstawowych jest skończona, możliwe są dwa przypadki:

po skończonej liczbie kroków problem zostanie rozwiązany (pojawi się sytuacja 2 lub 3);

zaczynając od pewnego kroku pojawia się zapętlenie(okresowe powtarzanie tabel simpleksowych i planów podstawowych).

Zadania te nazywają się symetryczne problemy podwójne.

Zwróćmy uwagę na następujące cechy łączące te zadania:

Jednym z problemów jest problem maksymalizacji, a drugim problemem minimalizacji.

W problemie maksymalizacji wszystkie nierówności są ≤, a w problemie minimalizacji wszystkie nierówności są ≥.

Liczba niewiadomych jednego problemu jest równa liczbie nierówności drugiego.

Macierze współczynników niewiadomych w nierównościach obu problemów podlegają wzajemnej transpozycji.

Swobodne wyrazy nierówności jednego z problemów są równe współczynnikom odpowiednich niewiadomych w wyrażeniu funkcji celu drugiego problemu.

Algorytm konstrukcji problemu dualnego.

1. Sprowadź wszystkie nierówności układu ograniczeń pierwotnego problemu do jednego znaczenia - do postaci kanonicznej.

2. Utwórz rozszerzoną macierz układu A, która zawiera kolumnę b i oraz współczynniki funkcji celu F.

3. Znajdź transponowaną macierz A T.

4. Zapisz podwójny problem. Twierdzenie 5.

F(X) ≤ G(Wartość funkcji celu problemu maksymalizacji dla żadnego z jego planów nie przekracza wartości funkcji celu jego problemu podwójnej minimalizacji dla żadnego z jego planów, tj. zachodzi następująca nierówność:),

y zwany.

podstawowa nierówność dualna (Twierdzenie 6.warunek wystarczający optymalności

). (Jeżeli dla niektórych planów problemów dualnych wartości funkcji celu są równe, to plany te są optymalne.Twierdzenie 7. podstawowe twierdzenie o dualności).

Jeśli ZLP ma skończone maksimum, to jego dualność również ma skończone maksimum i (wartości optymalnefunkcje celu pokrywają się. Jeśli funkcja obiektywna jednego z problemów dualnych nie jest ograniczona, wówczas warunki drugiego problemu są sprzeczne.

Twierdzenie 8.

Składniki optymalnego rozwiązania dualnego ZLP są równe odpowiednim elementom wiersza indeksowego optymalnej tablicy simpleksowej problemu bezpośredniego, odpowiadającym zmiennym dodatkowym.

Twierdzenie 11.(kryterium optymalności planu problemu transportowego). Aby plan transportu) był optymalny konieczne i wystarczające jest istnienie liczb () i () spełniających następujące warunki:

a) dla wszystkich podstawowych komórek planu (>0);

b) dla wszystkich wolnych komórek (=0).

Potencjalna metoda

Krok 1. Sprawdź, czy to zadanie transportowe jest zamknięte. Jeśli tak, przejdź do drugiego kroku. Jeśli nie, sprowadź problem do zamkniętego problemu, przedstawiając fikcyjnego dostawcę lub fikcyjnego konsumenta.

Krok 2. Znajdź wstępne rozwiązanie referencyjne (wstępny plan referencyjny) zamkniętego problemu transportowego.

Krok 3. Sprawdź wynikowe rozwiązanie wsparcia pod kątem optymalności:

obliczyć dla niego potencjał dostawcy ty I i konsumenci w J

dla wszystkich wolnych komórek ( B, J) obliczyć szacunki;

jeśli wszystkie szacunki nie są dodatnie (), wówczas rozwiązanie problemu jest zakończone: oryginalny plan odniesienia jest optymalny. Jeżeli wśród ocen znajdzie się choć jedna pozytywna, wówczas przechodzimy do kroku czwartego.

Krok 4. Wybierz komórkę ( B * ,J * ) z największą pozytywną oceną i dla niej zbudować zamknięty cykl redystrybucji ładunków. Cykl zaczyna się i kończy w wybranej komórce. B * , J * Otrzymujemy nowe rozwiązanie podporowe, w którym komórka (

) będzie zajęty. Wróćmy do trzeciego kroku.

Po skończonej liczbie kroków zostanie uzyskane optymalne rozwiązanie, czyli optymalny plan transportu produktów od dostawców do konsumentów. Punkt nazywa się punktem maksimum lokalne

, jeśli istnieje otoczenie tego punktu takie, że

Warunki konieczne optymalności X * Aby funkcja jednej zmiennej miała w punkcie

ekstremum lokalne konieczne jest, aby pochodna funkcji w tym punkcie była równa zeru,

Aby funkcja miała w pewnym punkcie ekstremum lokalne, konieczne jest, aby w tym punkcie zniknęły wszystkie jej pochodne cząstkowe X * Jeśli w punkcie X * pierwsza pochodna funkcji jest równa zeru, a druga pochodna > 0, to funkcja w punkcie<0 то функция в точке X * ma minimum lokalne, jeśli 2 produkty,

ma maksimum lokalne. Twierdzenie 4. X * Jeżeli funkcja jednej zmiennej ma punkt N - instrumenty pochodne do (

1) rzędy równe zero, a pochodna n rzędu nie jest równa 0, wówczas N Jeśli X * nawet, to kropka

jest punktem minimalnym, jeśli,fn(x)>0<0.

maksymalny punkt, jeśli fn(x) N Jeśli X * dziwne, więc wskaż

– punkt przegięcia. macierz postaci kwadratowej .

Nazywa się postać kwadratową (5). dodatnio określony, jeśli dla Q(X) >0 i zdefiniowane negatywnie, jeśli dla.Q(X)<0

Macierz symetryczna A zwany dodatnio określony, jeśli zbudowana z niej forma kwadratowa (5) jest dodatnio określona.

Nazywa się macierzą symetryczną zdefiniowane negatywnie, jeśli zbudowana z niej forma kwadratowa (6) jest ujemnie określona.

Kryterium Sylwestra: macierz jest dodatnio określona, ​​jeśli wszystkie jej drobne kątowe są większe od zera.

Macierz jest ujemnie określona, ​​jeśli znaki małoletnich narożnych występują naprzemiennie.

Aby macierz była dodatnio określona, ​​wszystkie jej wartości własne muszą być większe od zera.

Wartości własne– pierwiastki wielomianu.

Warunek wystarczający optymalności podaje następujące twierdzenie.

Twierdzenie 5. Jeżeli w punkcie stacjonarnym macierz Hessego jest dodatnio określona, ​​wówczas ten punkt jest lokalnym punktem minimalnym, jeśli macierz Hessego jest ujemnie określona, ​​wówczas ten punkt jest lokalnym punktem maksymalnym.

Konflikt jest sprzecznością spowodowaną przeciwstawnymi interesami stron.

Sytuacja konfliktowa- sytuacja, w której strony, których interesy są całkowicie lub częściowo przeciwne.

Gra - jest to faktyczny lub formalny konflikt, w którym uczestniczy co najmniej dwóch uczestników, z których każdy dąży do osiągnięcia własnych celów

Zasady gry wymień dopuszczalne działania każdego gracza mające na celu osiągnięcie określonego celu.

Poprzez płatność nazywa się ilościową oceną wyników gry.

Gra podwójna– gra, w której biorą udział tylko dwie strony (dwóch graczy).

Gra o sumie zerowej Lub antagonistyczny - gra podwójna, w której kwota płatności wynosi zero, to znaczy, jeśli strata jednego gracza jest równa zyskowi drugiego.

Nazywa się wybór i wdrożenie jednego z działań przewidzianych w zasadach ruch gracza. Ruchy mogą być osobiste i losowe.

Osobisty ruch to świadomy wybór przez gracza jednego z możliwych działań (na przykład ruchu w grze w szachy).

Losowy ruch to losowo wybrana akcja (na przykład wybranie karty z przetasowanej talii).

Strategia gracz - jest to jednoznaczny wybór gracza w każdej z możliwych sytuacji, w których gracz ten musi wykonać osobisty ruch.

Optymalna strategia- jest to strategia gracza, która przy wielokrotnym powtarzaniu gry zapewnia mu maksymalną możliwą średnią wygraną lub minimalną możliwą średnią stratę.

Matryca płatności– wynikową macierz A, czyli inaczej matryca gry S.

Skończona gra wymiarowa(m  n) to gra zdefiniowana przez macierz A o wymiarze (m  n).

Maksymin Lub niższa cena gry nazwijmy tę liczbę alpa = max(i)(min aij)(j)

i odpowiednia strategia (string) maksymin.

Minimaks Lub najwyższa cena gry nazwijmy liczbę Beta = min(j)(max aij)i

i odpowiadająca jej strategia (kolumna) minimaks.

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

Gra z punktem siodłowym nazwał grę, dla której. Alp = beta

Kosztem gry nazywa się wielkością v if.v = alp = beta

Strategia mieszana gracz jest wektorem, którego każdy składnik pokazuje względną częstotliwość stosowania przez gracza odpowiedniej czystej strategii.

Twierdzenie 2 .

Główne twierdzenie teorii gier macierzowych.

Każda gra macierzowa o sumie zerowej ma rozwiązanie w strategiach mieszanych.3

T

Jeśli jeden z graczy zastosuje optymalną strategię mieszaną, to jego wypłata jest równa kosztowi gry „ niezależnie od częstotliwości, z jaką drugi gracz wykorzystuje swoje strategie (w tym strategie czyste).

zabawa z naturą – gra, w której nie mamy informacji o zachowaniu partneraRyzyko R ja

Ryzyko R = jeśli jest to system z podstawą i tyle J - gracza przy wyborze strategii A i w warunkach H j nazywa się różnicą B ,

A jeśli jest to system z podstawą i tyle J Gdzie J- maksymalny element w

- kolumna.

Wykres jest zbiorem niepustego zbioru tzw

zbiór wierzchołków grafu i zbiór par wierzchołków, które są tzw

krawędzie wykresu.

Jeśli rozważane pary wierzchołków są uporządkowane, to graf

nazywa się zorientowanym (digrafem), w przeciwnym razie –

niezorientowany.

W

Nazywa się trasę (ścieżkę) w grafie łączącą wierzchołki A i B

ciąg krawędzi, z których pierwsza pochodzi z wierzchołka A, zaczynając

następna pokrywa się z końcem poprzedniej, a ostatnia krawędź jest uwzględniona

górne V.

Graf nazywamy spójnym, jeśli dla dowolnych dwóch jego wierzchołków istnieje ścieżka

łącząc je. W przeciwnym razie wykres nazywa się rozłączonym.

Graf nazywamy skończonym, jeśli liczba jego wierzchołków jest skończona.

Jeśli wierzchołek jest początkiem lub końcem krawędzi, to wierzchołek i krawędź

nazywane są incydentem. Stopień (rząd) wierzchołka to liczba krawędzi z nim sąsiadujących.

Ścieżka Eulera (łańcuch Eulera) w grafie to ścieżka przechodząca przez wszystko

krawędzi wykresu i to zresztą tylko raz.

Cykl Eulera to ścieżka Eulera, która jest cyklem.

Wykres Eulera to wykres zawierający cykl Eulera.

Cykl Eulera istnieje wtedy i tylko wtedy, gdy graf jest spójny i znajduje się w nim

nie ma wierzchołków stopnia nieparzystego.

Twierdzenie. Ścieżka Eulera w grafie istnieje wtedy i tylko wtedy, gdy graf

połączone, a liczba wierzchołków stopnia nieparzystego wynosi zero lub dwa.

Drzewo to spójny graf bez cykli, który ma wierzchołek początkowy

(pierwiastek) i skrajne wierzchołki (stopień 1); ścieżki od wierzchołka źródłowego do wierzchołków zewnętrznych nazywane są gałęziami.

Sieć (lub diagram sieciowy) jest zorientowaną skończonością

spójny graf, który ma wierzchołek początkowy (źródło) i wierzchołek końcowy (ujście).

Waga ścieżki w grafie jest sumą wag jej krawędzi.

Najkrótsza ścieżka z jednego wierzchołka do drugiego będzie nazywana ścieżką

minimalna waga.

Ciężar tej ścieżki będzie nazywany odległością pomiędzy

szczyty.

Praca jest procesem czasochłonnym, wymagającym zasobów,

lub logiczna zależność między dwoma lub większą liczbą zadań

Zdarzenie jest wynikiem wykonania jednego lub większej liczby zadań

Ścieżka to ciąg kolejnych dzieł łączących się

wierzchołki początkowe i końcowe.

Czas trwania podróży określa się na podstawie sumy czasów trwania podróży

jego dzieła założycielskie.

Zasady sporządzania schematów sieciowych.

1. Na schemacie sieci nie powinno być żadnych zdarzeń zakleszczenia (z wyjątkiem

końcowe), czyli takie, po których nie następuje żadna praca.

2. Nie powinno być żadnych zdarzeń (poza początkowym), które nie są poprzedzone chociaż

tylko jedna praca.

3. Na schemacie sieci nie powinno być cykli.

4. Każde dwa zdarzenia łączy nie więcej niż jedno zadanie.

5. Schemat sieci powinien być uporządkowany.

Dowolna ścieżka, której początek pokrywa się ze zdarzeniem początkowym i którego koniec pokrywa się z

zakończenie nazywa się pełną ścieżką. Pełna ścieżka z maksimum

czas trwania pracy nazywany jest ścieżką krytyczną

Hierarchia to pewien rodzaj systemu oparty na założeniu, że elementy systemu można grupować w niepowiązane zbiory

Opis metody analizy hierarchicznej

Konstrukcja macierzy porównań parami

Znajdź lambda max i rozwiąż układ względem wektora wag

Synteza lokalnych priorytetów

Sprawdzanie spójności macierzy porównań parami

Synteza priorytetów globalnych

Ocena spójności całej hierarchii

Metoda simpleksowa jest metodą rozwiązywania problemów programowania liniowego. Istota metody polega na znalezieniu wstępnego planu wykonalnego, a następnie jego ulepszaniu, aż do osiągnięcia maksymalnej (lub minimalnej) wartości funkcji celu w danym zbiorze wielościennym wypukłym lub stwierdzenia nierozwiązywalności problemu.

Rozważ następujący problem programowania liniowego w postaci kanonicznej:

Metoda sztucznej bazy

Jak pokazano powyżej, dla problemu zapisanego w postaci kanonicznej, jeśli należy do wektorów kolumnowych macierzy A Jest M jednostkowe i liniowo niezależne, można bezpośrednio określić plan referencyjny. Jednak w przypadku wielu problemów programowania liniowego zapisywanych w postaci kanonicznej i posiadających plany odniesienia, wśród wektorów kolumnowych macierzy A nie zawsze dostępne M jednostkowe i liniowo niezależne. Rozważ następujący problem:

Załóżmy, że musimy znaleźć maksimum funkcji

pod warunkami

gdzie są pierwsi N elementy są zerowe. Zmienne nazywane są sztucznymi. Kolumny wektorów

(28)

tworzą tak zwaną sztuczną podstawę M-wymiarowa przestrzeń wektorowa.

Ponieważ rozszerzony problem ma plan odniesienia, jego rozwiązanie można znaleźć metodą sympleksową.

Twierdzenie 4. Jeśli w planie optymalnym rozszerzony problem (24)−(26) wartości zmiennych sztucznych , To jest optymalnym planem problemu (21)−(23).

Zatem jeśli w znalezionym optymalnym planie dla rozszerzonego problemu wartości zmiennych sztucznych są równe zeru, to otrzymuje się optymalny plan dla pierwotnego problemu. Zastanówmy się bardziej szczegółowo nad znalezieniem rozwiązania rozszerzonego problemu.

Wartość funkcji celu dla planu odniesienia (27):

Zauważamy to F(X) i składają się z dwóch niezależnych części, z których jedna jest zależna M, a drugi - nie.

Po obliczeniu F(X) i ich wartości, a także początkowe dane rozszerzonego zadania są wprowadzane do tabeli simplex, jak pokazano powyżej. Jedyna różnica polega na tym, że ta tabela zawiera o jeden wiersz więcej niż zwykła tabela jednostronna. W tym samym czasie ( M Linia +1) zawiera współczynniki, które nie zawierają M i w ( M+2) linia – współczynniki dla M.

Podczas przechodzenia z jednego planu odniesienia do drugiego wektor odpowiadający największej liczbie ujemnej w wartości bezwzględnej ( M+2) linie. Sztuczny wektor wyłączony z bazy nie ma sensu ponownie wprowadzać do bazy. Przy przejściu na inny plan odniesienia może się zdarzyć, że żaden ze sztucznych wektorów nie zostanie wykluczony z bazy. Ponowne obliczenie tabeli simpleksowej przy przejściu z jednego planu odniesienia do drugiego odbywa się zgodnie ze zwykłymi zasadami metody simpleksowej (patrz wyżej).

Proces iteracyjny realizowany jest wg M Linia +2 o długości elementów M+2 linie odpowiadające zmiennym nie stanie się nieujemna. Co więcej, jeśli z podstawy wykluczy się zmienne sztuczne, wówczas znaleziony plan rozszerzonego problemu odpowiada pewnemu planowi odniesienia problemu pierwotnego.

M+2 rzędy, kolumny X 0 jest ujemne, wówczas pierwotny problem nie ma rozwiązania.

Jeśli nie, wszystkie zmienne sztuczne są wyłączone z podstawy i elementu M+2 rzędy, kolumny X 0 jest równe zero, to plan odniesienia pierwotnego problemu jest zdegenerowany i baza zawiera co najmniej jeden z wektorów sztucznej bazy.

Jeśli pierwotny problem zawiera kilka wektorów jednostkowych, to należy je uwzględnić w sztucznej bazie.

Jeśli podczas iteracji M Linia +2 nie zawiera już elementów ujemnych, następnie proces iteracji jest kontynuowany M Linia +1, aż do znalezienia optymalnego planu rozszerzonego problemu lub ujawnienia się nierozwiązywalności problemu.

Zatem proces znajdowania rozwiązania problemu programowania liniowego (21)−(23) metodą sztucznej bazy obejmuje następujące główne etapy:

• Skomponuj rozszerzony problem (24)−(26).
• Znajdź plan odniesienia rozszerzonego problemu.
• Stosując metodę sympleksową, z podstawy wyklucza się sztuczne wektory. W rezultacie odnajduje się plan odniesienia pierwotnego problemu lub rejestruje się jego nierozwiązywalność.
• Korzystając ze znalezionego planu odniesienia ZLP (21)−(23), albo znajdują optymalny plan pierwotnego problemu, albo ustalają jego nierozwiązywalność.

Aby rozwiązać problemy z programowaniem liniowym online, użyj kalkulatora

Składniki modelu matematycznego

Podstawą rozwiązywania problemów ekonomicznych są modele matematyczne.

Model matematyczny problem to zbiór zależności matematycznych opisujących istotę problemu.

• wybór zmiennych problemowych
• opracowanie systemu ograniczeń
• wybór funkcji celu

Zmienne zadania nazywane są wielkościami X1, X2, Xn, które całkowicie charakteryzują proces gospodarczy. Zwykle zapisuje się je jako wektor: X=(X1, X2,...,Xn).

System ograniczeń Problemy to zbiór równań i nierówności opisujących ograniczone zasoby rozważanego problemu.

Funkcja celu zadania nazywane są funkcją zmiennych zadania, która charakteryzuje jakość zadania i którego ekstremum należy znaleźć.

Ogólnie problem programowania liniowego można zapisać w następujący sposób:

Zapis ten oznacza: znaleźć ekstremum funkcji celu (1) i odpowiadające mu zmienne X=(X1, X2,...,Xn) pod warunkiem, że zmienne te spełniają system ograniczeń (2) i nieujemność warunki (3).

Prawidłowe rozwiązanie(planem) problemu programowania liniowego jest dowolny n-wymiarowy wektor X=(X1, X2,...,Xn), który spełnia układ więzów i warunków nieujemności.

Zbiór wykonalnych rozwiązań (planów) postaci problemu obszar możliwych rozwiązań(ODR).

Optymalne rozwiązanie(plan) zadania programowania liniowego to takie dopuszczalne rozwiązanie (plan) problemu, w którym funkcja celu osiąga ekstremum.

Stan : schorzenie: Aby wyprodukować n rodzajów produktów, zużywa się m rodzajów zasobów. Utwórz model matematyczny.

Znany:

• bi (i = 1,2,3,...,m) - zasoby każdego i-tego rodzaju zasobu;
• aij (i = 1,2,3,...,m; j=1,2,3,...,n) - koszt każdego i-tego rodzaju zasobu za wytworzenie jednostki objętości j-ty rodzaj produktu;
• cj (j = 1,2,3,...,n) - zysk ze sprzedaży jednostki objętości j-tego rodzaju produktu.

Wymagane jest sporządzenie planu produkcji zapewniającego maksymalny zysk przy danych ograniczeniach zasobów (surowców).

Rozwiązanie:

Wprowadźmy wektor zmiennych X=(X1, X2,...,Xn), gdzie xj (j = 1,2,...,n) jest wielkością produkcji produktu j-tego typu.

Koszty i-tego rodzaju zasobu na wytworzenie danej objętości xj produktów są równe aijxj, zatem ograniczenie wykorzystania zasobów na wytworzenie wszystkich typów produktów ma postać:
Zysk ze sprzedaży produktu j-tego rodzaju jest równy cjxj, więc funkcja celu jest równa:

Odpowiedź- Model matematyczny wygląda następująco:

Postać kanoniczna problemu programowania liniowego

W ogólnym przypadku problem programowania liniowego jest zapisywany w taki sposób, że ograniczenia są zarówno równaniami, jak i nierównościami, a zmienne mogą być albo nieujemne, albo dowolnie zmienne.

W przypadku, gdy wszystkie ograniczenia są równaniami i wszystkie zmienne spełniają warunek nieujemności, problem programowania liniowego nazywa się kanoniczny.

Można go przedstawić w notacji współrzędnych, wektorowych i macierzowych.

Problem kanonicznego programowania liniowego w zapisie współrzędnych ma postać:

Problem kanonicznego programowania liniowego w notacji macierzowej ma postać:

• A - macierz współczynników układu równań
• X - macierz-kolumna zmiennych zadania
• Ао - macierz-kolumna odpowiednich części systemu ograniczeń

Często stosuje się problemy programowania liniowego, zwane symetrycznymi, które w zapisie macierzowym mają postać:

Sprowadzenie ogólnego problemu programowania liniowego do postaci kanonicznej

W większości metod rozwiązywania problemów programowania liniowego przyjmuje się, że układ więzów składa się z równań i warunków naturalnych nieujemności zmiennych. Jednak przy kompilowaniu modeli problemów ekonomicznych ograniczenia kształtują się głównie w postaci układu nierówności, dlatego konieczna jest możliwość przejścia od układu nierówności do układu równań.

Weźmy nierówność liniową a1x1+a2x2+...+anxn≤b i dodajmy do jej lewej strony pewną wartość xn+1 tak, że nierówność zamienia się w równość a1x1+a2x2+...+anxn+xn+1=b . Co więcej, ta wartość xn+1 jest nieujemna.

Spójrzmy na wszystko na przykładzie.

Sprowadź problem programowania liniowego do postaci kanonicznej:

Rozwiązanie:
Przejdźmy do problemu znalezienia maksimum funkcji celu.
W tym celu zmieniamy znaki współczynników funkcji celu.
Aby przekształcić drugą i trzecią nierówność układu więzów w równania, wprowadzamy nieujemne zmienne dodatkowe x4 x5 (w modelu matematycznym operacja ta jest oznaczona literą D).
Zmienną x4 wprowadza się po lewej stronie drugiej nierówności ze znakiem „+”, ponieważ nierówność ma postać „≤”.
Zmienną x5 wprowadza się po lewej stronie trzeciej nierówności ze znakiem „-”, ponieważ nierówność ma postać „≥”.
Zmienne x4 x5 wprowadza się do funkcji celu ze współczynnikiem. równy zeru.
Problem zapisujemy w formie kanonicznej: