Podstawowe pojęcia badań operacyjnych. Badania operacyjne Rozwiązanie gry w strategiach mieszanych

W. Slinkin

Podręcznik dla studentów uczelni pedagogicznych

na kierunku Informatyka

Szadryńsk, 2003

Slinkina I.N.

Badania operacyjne. Pomoc nauczania. - Shadrinsk: wydawnictwo Shadrinsk State Pedagogical Institute, 2002. - 106 s.

Slinkina I.N. – kandydat nauk pedagogicznych

Podręcznik przedstawia teoretyczną część kursu „Badania operacyjne”. Przeznaczony jest dla studentów studiów stacjonarnych i niestacjonarnych wydziałów realizujących specjalność „Informatyka”.

© Shadrinsky Państwowy Instytut Pedagogiczny

© Slinkina I.N., 2002

Pytania do bloków w kursie „Badania operacyjne” 5

1.1. Przedmiot i cele badań operacyjnych 7

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

1.3. Matematyczne modele operacji 10

1.4. Zrozumienie programowania liniowego 12

1.5. Przykłady problemów ekonomicznych programowania liniowego. Problem najlepszego wykorzystania zasobów 13

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

1.7. Przykłady problemów ekonomicznych programowania liniowego. Problem z mieszanką 16

1.8. Przykłady problemów ekonomicznych programowania liniowego. Zadanie transportowe 17

1.9. Podstawowe typy pisania problemów programowania liniowego 19

1.10. Metody konwersji 21

1.11. Przejście do formy kanonicznej 22

1.12. Przejście do notacji symetrycznej 25

2.1. Geometryczna interpretacja problemu programowania liniowego 28

2.2. Graficzne rozwiązywanie problemów programowania liniowego 29

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

2.4. Ogólna idea metody simplex 35

2.5. Budowa wstępnego planu referencyjnego rozwiązywania problemów programowania liniowego metodą simplex 36

2.6. Znak optymalności planu podstawowego. stoły simplex 40

2.7. Przejście na nienajgorszy plan referencyjny. 44

2.8. Transformacje simplex 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 simplex. Zapętlanie 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 zadania transportowego 61

3.3. Budowa wstępnego planu podstawowego. Reguła narożnika północno-zachodniego 63

3.4. Budowa wstępnego planu podstawowego. Reguła minimalnego elementu 64

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

3.6. Potencjalna metoda 65

3.7. Rozwiązywanie problemów transportowych z ograniczeniami przepustowości 69

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

3.9. Istota dyskretnych metod optymalizacji 72

3.10. Problem programowania wypukłego 74

3.11. Metoda mnożników Lagrange'a 75

3.12. Metody gradientowe 77

4.1. Metody funkcji kary i bariery 78

4.2. Programowanie dynamiczne. Podstawowe koncepcje. Istota metod rozwiązań 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. Redukcja gry matrix do 92 zł

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

4.9. Strumienie zdarzeń 96

4.10. Schemat śmierci i reprodukcji 97

4.11. Mała Formuła 99

4.12. Najprostsze systemy kolejkowe 101

Pytania do bloków w kursie „Badania operacyjne”

Blok 1

1. Przedmiot i zadania badań operacyjnych.

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

3. Modele matematyczne operacji.

4. Pojęcie programowania liniowego.

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

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

7. Przykłady problemów ekonomicznych programowania liniowego. Problem z mieszanką.

8. Przykłady problemów ekonomicznych programowania liniowego. zadanie transportowe.

9. Podstawowe typy pisania problemów programowania liniowego.

10. Metody transformacji.

11. Przejście do formy kanonicznej.

12. Przejście do notacji symetrycznej.

Blok 2

1. Geometryczna interpretacja 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. Budowa wstępnego podstawowego planu rozwiązywania problemów programowania liniowego metodą simplex.

6. Znak optymalności planu podstawowego. Tabele simpleksowe.

7. Przejście na nienajgorszy plan referencyjny.

8. Transformacje simpleksowe.

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 simplex. Zapętlanie.

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

Blok 3

1. Asymetryczne problemy dualne.

2. Otwarte i zamknięte modele problemu transportowego.

3. Budowa wstępnego planu podstawowego. Reguła narożnika północno-zachodniego.

4. Budowa wstępnego planu podstawowego. Reguła minimalnego elementu.

5. Budowa wstępnego planu podstawowego. Metoda Vogla.

6. Metoda potencjałów.

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

8. Przykłady problemów programowania dyskretnego. Problem transportu kontenerowego. Zadanie przydziału.

9. Istota dyskretnych metod optymalizacji.

10. Problem programowania wypukłego.

11. Metoda mnożników Lagrange'a.

12. Metody gradientowe.

Blok 4

1. Metoda funkcji kary i bariery.

2. Programowanie dynamiczne. Podstawowe koncepcje. Istota metod rozwiązań.

3. Programowanie stochastyczne. Podstawowe koncepcje.

4. Gry macierzowe o sumie zerowej.

5. Strategie czyste i mieszane.

6. Własności strategii czystych i mieszanych.

7. Redukcja gry macierzowej do LLP

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

9. Strumienie zdarzeń.

10. Schemat śmierci i reprodukcji.

11. Mała formuła.

12. Najprostsze systemy kolejkowe.

Blok 1.

Przedmiot i cele badań operacyjnych

Obecny stan nauki i techniki, w szczególności rozwój komputerowych narzędzi do obliczeń i matematycznego uzasadniania teorii, umożliwił znaczne uproszczenie rozwiązywania wielu problemów stawianych różnym dziedzinom nauki. Wiele problemów sprowadza się do rozwiązania kwestii optymalizacji produkcji, optymalnego sterowania procesem.

Potrzeby praktyki powołały do ​​życia specjalne metody naukowe, które wygodnie zgrupowano pod nazwą „badania operacyjne”.

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

Niech zostaną podjęte jakieś działania, aby osiągnąć określony cel. Osoba (lub grupa osób) organizująca wydarzenie zawsze ma pewną swobodę wyboru: może być zorganizowana w taki czy inny sposób. Decyzja jest pewnym wyborem spośród wielu opcji dostępnych dla organizatora.

Potrzebę podejmowania decyzji i testowania zaproponowanej hipotezy decyzyjnej potwierdzają matematycznie poniższe przykłady:

Zadanie 1. O najlepszym wykorzystaniu zasobów.

Firma produkuje kilka rodzajów produktów. Do ich wytworzenia wykorzystywane są pewne zasoby (m.in. ludzie, energia itp.). Konieczne jest obliczenie, jak zaplanować pracę przedsiębiorstwa, aby koszt zasobów był minimalny, a zysk maksymalny.

Zadanie 2. O mieszankach.

Konieczne jest przygotowanie mieszanki o określonych właściwościach. Aby to zrobić, możesz użyć niektórych „produktów” (do obliczania diet - żywność, do mieszanek paszowych - karma dla zwierząt, do mieszanek technicznych - stopy, płyny do celów technicznych). zadaniem jest dobranie optymalnej ilości produktów (w stosunku do ceny) w celu uzyskania optymalnej ilości mieszanki.

Zadanie 3. zadanie transportowe.

Istnieje sieć przedsiębiorstw wytwarzających ten sam rodzaj produktów o tej samej jakości oraz sieć konsumentów tych produktów. Konsumenci i dostawcy są połączeni środkami komunikacji (drogi, linie kolejowe, linie lotnicze). Taryfy transportowe są ustalane. Konieczne jest obliczenie optymalnego planu transportu produktów, aby koszty transportu były minimalne, żądania wszystkich konsumentów zostały spełnione, a wszystkie towary zostały wywiezione od dostawców.

W każdym z powyższych przykładów mówimy o jakimś wydarzeniu realizującym określony cel. Podano pewne warunki, które charakteryzują sytuację (w szczególności środki, którymi można dysponować). W ramach tych uwarunkowań wymagane jest podjęcie takiej decyzji, aby planowana impreza była w jakimś sensie bardziej opłacalna.

Zgodnie z tymi ogólnymi cechami opracowywane są również ogólne metody rozwiązywania takich problemów, które razem składają się na schemat metodologiczny i aparat badań operacyjnych.

Obecnie szeroko stosowane są zautomatyzowane systemy sterowania (ACS) oparte na wykorzystaniu technologii komputerowej. Stworzenie zautomatyzowanego systemu sterowania jest niemożliwe bez uprzedniego zbadania sterowanego procesu metodami modelowania matematycznego. Wraz ze wzrostem skali 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 każde zdarzenie (system działań) połączone jednym planem i ukierunkowane na osiągnięcie jakiegoś celu.

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

Definicja: Decyzją nazywamy każdy określony wybór zależny od parametrów decyzyjnych.

Definicja: Optymalne rozwiązania to te, które są preferowane w stosunku do innych z tego czy innego powodu.

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

Czasami w wyniku badania możliwe jest wskazanie jednego, ściśle określonego rozwiązania, znacznie częściej możliwe jest wskazanie obszaru praktycznie równoważnych rozwiązań optymalnych, w ramach których można dokonać ostatecznego wyboru.

Samo podejmowanie decyzji wykracza poza zakres badań operacyjnych i należy do kompetencji osoby odpowiedzialnej, częściej grupy osób, którym dane jest prawo ostatecznego wyboru i które za ten wybór ponoszą odpowiedzialność.

Definicja: Parametry, których całość tworzy rozwiązanie, nazywane są elementami rozwiązania.

Jako elementy rozwiązania mogą pojawić się różne liczby, wektory, funkcje, znaki fizyczne itp. Dla uproszczenia cały zbiór elementów rozwiązania będzie oznaczony przez x.

Oprócz elementów rozwiązania w każdym zadaniu badań operacyjnych, istnieją również określone warunki, które są ustalone w stanie problemu i nie mogą być naruszone. W szczególności warunki te obejmują środki (materiałowe, techniczne, ludzkie), którymi można dysponować oraz inne ograniczenia nałożone na rozwiązanie. W całości tworzą one tzw. „zbiór możliwych rozwiązań”. Oznaczmy ten zbiór X, a fakt, że rozwiązanie x należy do tego zbioru, zapiszemy: хОХ.

Aby porównać różne rozwiązania pod względem efektywności, trzeba mieć jakieś kryterium ilościowe, tzw. wskaźnik efektywności (funkcja celu). Wskaźnik ten jest tak dobrany, aby odzwierciedlał ukierunkowanie operacji na cel. Za najlepsze rozwiązanie zostanie uznane to, które w maksymalnym stopniu przyczyni się do osiągnięcia celu. Aby wybrać wskaźnik wydajności Z, musisz najpierw określić, do czego powinno doprowadzić rozwiązanie problemu. Przy wyborze rozwiązania preferowane jest takie, które ustawia wskaźnik wydajności Z na maksimum lub minimum. Na przykład chciałbym zmaksymalizować dochód z operacji; jeśli koszty są wskaźnikiem efektywności, pożądana jest ich minimalizacja.

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

Zadanie wyboru wskaźnika wydajności jest rozwiązywane indywidualnie dla każdego problemu.

Zadanie 1. O najlepszym wykorzystaniu zasobów.

Zadaniem operacji jest wyprodukowanie maksymalnej ilości towaru. Wskaźnik efektywności Z to zysk ze sprzedaży towarów przy minimalnym koszcie zasobów (max Z).

Zadanie 2. O mieszankach.

Naturalnym wskaźnikiem efektywności, sugerowanym przez sformułowanie problemu, jest cena produktów potrzebnych do wykonania mieszanki, pod warunkiem zachowania określonych właściwości mieszanki (min Z).

Zadanie 3. zadanie transportowe.

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

1. Przedmiot i cele badania operacji w gospodarce. 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ć przeciwstawne.

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

Rozwiązanie, które okaże się najkorzystniejsze dla całej organizacji, nazywamy optymalnym, a rozwiązanie, które jest najbardziej korzystne dla jednego lub kilku 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 każde zdarzenie (system działań) połączone jednym planem i ukierunkowane na osiągnięcie jakiegoś celu.

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

Każdy określony wybór parametrów zależnych od nas nazywamy decyzją. Rozwiązania nazywane są optymalnymi, jeśli z tego czy innego powodu są preferowane w stosunku do innych.

Parametry, których całość tworzy rozwiązanie, nazywane są elementami rozwiązania.

Zbiór dopuszczalnych rozwiązań ma określone warunki, które są stałe i nie mogą być naruszone.

Wskaźnik wydajności – miara ilościowa, która pozwala na porównanie różnych rozwiązań pod kątem 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. Przetłumaczony z greckiego graf (grafpho - piszę) przedstawia układ punktów, z których część jest połączona liniami - łukami (lub krawędziami). Jest to topologiczny (matematyczny) model oddziałujących na siebie systemów. Za pomocą wykresów można rozwiązywać nie tylko problemy związane z planowaniem sieci, ale także inne problemy. Metodę planowania sieciowego stosuje się przy planowaniu kompleksu połączonych ze sobą prac. Pozwala na wizualizację organizacyjnej i technologicznej sekwencji prac oraz ustalenie relacji między nimi. Ponadto pozwala koordynować operacje o różnym stopniu złożoności oraz identyfikować operacje, od których zależy czas trwania całej pracy (czyli wydarzenia organizacyjnego), a także skupiać się na terminowym wykonaniu każdej operacji.

Podstawą planowania i zarządzania siecią jest model sieciowy (SM), który modeluje zbiór powiązanych ze sobą działań i zdarzeń odzwierciedlających proces osiągania określonego celu. Można to przedstawić w formie wykresu lub tabeli.

Podstawowe pojęcia modelu sieciowego:

Wydarzenie, praca, sposób.

Zdarzenia są wynikiem wykonania jednej lub więcej czynności. Nie mają przedłużenia w czasie.

Ścieżka to ciąg następujących po sobie prac, łączących wierzchołki początkowe i końcowe.

Czas trwania ścieżki jest określony przez sumę czasów trwania jej prac składowych.

3. Budowa i uporządkowanie schematu sieci.

Model sieciowy jest stosowany jako model odzwierciedlający współzależności technologiczne i organizacyjne procesu robót budowlanych i instalacyjnych w systemach planowania i zarządzania siecią (SPU).

Model sieci to graficzna reprezentacja procesów, których realizacja prowadzi do osiągnięcia jednego lub większej liczby celów, ze wskazaniem ustalonych relacji między tymi procesami. Diagram sieci jest modelem sieci z obliczonymi parametrami czasowymi.

Struktura diagramu sieci, która określa wzajemną zależność pracy i zdarzeń, nazywana jest jego topologią.

Praca to proces produkcyjny wymagający czasu, pracy i zasobów materialnych, który po wykonaniu prowadzi do osiągnięcia określonych rezultatów.

Uzależnienie (praca fikcyjna), która nie wymaga czasu, jest oznaczone kropkowaną strzałką. Praca fikcyjna jest używana na diagramie sieciowym, aby pokazać relacje między zdarzeniami i działaniami.

W harmonogramie sieciowym używany jest czas, koszt i inne cechy pracy.

Czas pracy - czas wykonania tej pracy w dniach roboczych lub innych jednostkach czasu, taki sam dla wszystkich prac w sieci. Czas trwania pracy może być pewną (deterministyczną) lub zmienną losową określoną przez prawo jej rozkładu.

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

Zasoby charakteryzują się zapotrzebowaniem na jednostki fizyczne niezbędne do wykonania tej pracy.

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

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

Zdarzenia, które nie mają wcześniejszych działań, nazywane są zdarzeniami początkowymi; zdarzenia, które nie mają kolejnych – finałowych.

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

2 Podczas budowania sieci rozwiązywane są następujące pytania:

Jaką pracę (pracę) należy wykonać, aby rozpocząć tę pracę;

Jaka praca powinna być wykonywana równolegle z tą pracą;

3 Wstępny harmonogram sieci jest budowany bez uwzględnienia czasu trwania czynności składających się na sieć.

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

5 Pomiędzy dwoma wydarzeniami może być tylko jedno dzieło. Podczas wznoszenia budynków i budowli prace mogą być wykonywane sekwencyjnie, równolegle lub jednocześnie, niektóre w seriach, a niektóre równolegle, w wyniku czego powstają różne zależności pomiędzy poszczególnymi pracami.

Numeracja (kodowanie) zdarzeń następuje po zakończeniu budowy sieci, począwszy od zdarzenia początkowego do końcowego.

4. Ścieżka krytyczna diagramu sieciowego. Rezerwy czasu. Wczesne i późne daty wydarzeń i działań na diagramie sieciowym.

Na diagramie sieciowym może istnieć wiele ścieżek między zdarzeniami początkowymi i końcowymi. Ścieżka o najdłuższym czasie trwania nazywana jest ścieżką krytyczną. Ścieżka krytyczna określa całkowity czas trwania działań. Wszystkie inne ścieżki mają krótszy czas trwania, a zatem wykonywana na nich praca ma rezerwy czasowe.

Ścieżka krytyczna jest wskazana na schemacie sieci za pomocą pogrubionych lub podwójnych linii (strzałki).

Podczas sporządzania schematu sieci szczególne znaczenie mają dwie koncepcje:

Wczesne rozpoczęcie pracy - okres, przed którym nie można rozpocząć tej pracy bez naruszenia przyjętej sekwencji technologicznej. Decyduje o tym najdłuższa droga od zdarzenia inicjującego do rozpoczęcia tej pracy.

Późne zakończenie to najpóźniejsza data zakończenia zadania, która nie zwiększa całkowitego czasu trwania zadania. Wyznacza ją najkrótsza droga od danego zdarzenia do zakończenia wszystkich prac.

Wcześniejsze zakończenie to termin, przed którym praca nie może zostać zakończona. Jest to równowartość wcześniejszego rozpoczęcia plus czas trwania tej pracy.

Późny start - okres, po którym nie można rozpocząć tej pracy bez wydłużenia całkowitego czasu trwania budowy. Jest równy późnemu zakończeniu pracy pomniejszonemu o czas trwania danej pracy.

Jeśli wydarzeniem jest koniec tylko jednego zadania (to znaczy, że skierowana jest do niego tylko jedna strzałka), to wczesne zakończenie tego zadania zbiega się z wczesnym rozpoczęciem następnego.

Całkowita (pełna) rezerwa to maksymalny czas, o jaki można opóźnić wykonanie tej pracy bez zwiększania całkowitego czasu trwania pracy. Decyduje o tym różnica między późnym a wczesnym początkiem (lub późnym i wczesnym zakończeniem – co jest tym samym).

Rezerwa prywatna (bezpłatna) - jest to maksymalny czas, o jaki można opóźnić wykonanie tej pracy, bez zmiany wcześniejszego rozpoczęcia następnej. Ta rezerwa jest możliwa tylko wtedy, gdy zdarzenie obejmuje dwie lub więcej czynności (zależności), tj. dwie lub więcej strzałek (pełnych lub kropkowanych) wskazuje na to. Wtedy tylko jedno z tych zadań będzie miało wcześniejsze zakończenie, które zbiega się z wcześniejszym rozpoczęciem kolejnego zadania, podczas gdy dla pozostałych będą to inne wartości. Ta różnica dla każdego dzieła będzie jego prywatną rezerwą.

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

Programowanie dynamiczne jest jedną z najpotężniejszych technik optymalizacji. Zadaniami podejmowania racjonalnych decyzji, wybierania najlepszych opcji, optymalnej kontroli zajmują się specjaliści o różnych profilach. 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 zastosowania zasady optymalności jest niezwykle szeroki, zakres problemów, do których można ją zastosować, nie został jeszcze w pełni zarysowany. Programowanie dynamiczne od samego początku służy praktycznemu rozwiązywaniu problemów optymalizacyjnych.

Oprócz zasady optymalności, głównej metody badawczej, ważną rolę w aparacie programowania dynamicznego odgrywa idea zanurzenia określonego problemu optymalizacyjnego w rodzinie problemów podobnych. Trzecią jej cechą, która wyróżnia ją spośród innych metod optymalizacji, jest forma końcowego wyniku. Zastosowanie zasady optymalności i zasady zanurzenia w wieloetapowych, dyskretnych procesach prowadzi do powtarzających się równań funkcyjnych ze względu na optymalną wartość kryterium jakości. Otrzymane równania umożliwiają sekwencyjne wypisanie optymalnych sterowań dla pierwotnego problemu. Zaletą jest tutaj rozbicie zadania obliczania sterowania dla całego procesu na szereg prostszych zadań 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ść wzrasta katastrofalnie wraz ze wzrostem wymiarowości problemu.

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

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 wyznaczany jest SOC w zależności od stanu systemu (osiągniętego w wyniku poprzednich kroków), a warunkowo optymalne wzmocnienie na wszystkich pozostałych krokach, począwszy od tego, zależy również od państwo. W końcowym etapie określane jest (bezwarunkowe) optymalne sterowanie dla każdego kroku. Wstępna (warunkowa) optymalizacja jest wykonywana krok po kroku w odwrotnej kolejności: od ostatniego kroku do pierwszego; ostateczna (bezwarunkowa) optymalizacja – także etapami, ale w naturalnej kolejności: od pierwszego kroku do ostatniego. Z dwóch etapów optymalizacji pierwszy jest nieporównywalnie ważniejszy i bardziej czasochłonny. Po zakończeniu pierwszego etapu realizacja drugiego etapu nie nastręcza żadnych trudności: pozostaje tylko „przeczytać” rekomendacje przygotowane już w pierwszym etapie.

7. Postawienie 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 dobór programu produkcyjnego lub np. . Zadania gospodarcze charakteryzują się ograniczeniami zasobów (materialnych i/lub finansowych). Są one pisane jako system nierówności, czasem jako równości.

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

Kryterium jest cena MAX następnego produktu z interesującej nas grupy 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% 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 (biorąc pod uwagę 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 w rozwiązywaniu problemów przestrzeni dwuwymiarowej i tylko niektórych problemów przestrzeni trójwymiarowej, ponieważ dość trudno jest skonstruować rozwiązanie polytope, które ma postać wynikiem przecięcia półprzestrzeni. Zadanie przestrzeni o wymiarach większych niż trzy nie może być w ogóle przedstawione graficznie.

Niech problem programowania liniowego będzie dany w przestrzeni dwuwymiarowej, tj. ograniczenia 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ązań jest ograniczony. Każda z nierówności (2.2) i (2.3), jak zaznaczono 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 ustalonych wartości Z jest równaniem prostej: C1x1 + C2x2 = const. Skonstruujmy wielokąt rozwiązań układu więzów (2.2) i wykres funkcji liniowej (2.1) dla Z = 0 (rys. 2.1). Wtedy danemu problemowi programowania liniowego można nadać następującą interpretację. Znajdź punkt wielokąta rozwiązania, w którym prosta C1x1 + C2x2 = const jest linią wsparcia i funkcja Z osiąga minimum.

Wartości Z = C1x1 + C2x2 rosną w kierunku wektora N = (C1, C2), więc przesuwamy prostą Z = 0 równolegle do siebie w kierunku wektora X. Z ryc. 2.1 wynika z tego, że prosta dwukrotnie staje się odniesieniem względem wielokąta rozwiązań (w punktach A i C), a minimalna wartość jest 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 decyzyjny 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 do niego odniesieniem w żadnym punkcie. W tym przypadku funkcja liniowa jest nieograniczona na wielokącie rozwiązania zarówno powyżej, jak i poniżej (ryc. 2.2).

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

9. Metoda simpleksowa.

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 do maksimum i zmniejszając przy rozwiązywaniu problemu do minimum. Zatem przejście 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, dająca się zastosować do dowolnego problemu programowania liniowego w postaci kanonicznej. Układem ograniczeń jest tutaj układ równań liniowych, w którym liczba niewiadomych jest większa niż liczba równań. Jeśli rangą systemu jest r, to możemy wybrać r niewiadomych, które wyrazimy za pomocą pozostałych niewiadomych. Dla pewności zakładamy, że wybrane są pierwsze kolejne niewiadome X1, X2, ..., Xr. Wtedy nasz układ równań można zapisać jako

Metoda simplex opiera się na twierdzeniu zwanym fundamentalnym twierdzeniem metody simplex. Wśród optymalnych planów dla problemu programowania liniowego w postaci kanonicznej koniecznie musi istnieć referencyjne rozwiązanie jego systemu ograniczeń. Jeżeli optymalny plan problemu jest unikalny, to pokrywa się z jakimś rozwiązaniem referencyjnym. Istnieje skończenie wiele różnych rozwiązań wspierających system z ograniczeniami. Zatem rozwiązania problemu w postaci kanonicznej można by szukać wyliczając rozwiązania wzorcowe i wybierając spośród nich to, dla którego wartość F jest największa. Ale, po pierwsze, wszystkie rozwiązania wzorcowe są nieznane i trzeba je znaleźć, a po drugie, w rzeczywistych problemach tych rozwiązań jest bardzo dużo i bezpośrednie wyliczenie jest prawie niemożliwe. Metoda simpleks jest pewną procedurą ukierunkowanego wyliczania rozwiązań wzorcowych. Na podstawie jakiegoś wcześniej znalezionego rozwiązania odniesienia za pomocą pewnego algorytmu metody simplex obliczamy nowe rozwiązanie odniesienia, w którym wartość funkcji celu F jest nie mniejsza niż w starym. Po serii kroków dochodzimy do rozwiązania wzorcowego, jakim jest plan optymalny.

10. Sformułowanie problemu transportowego. Metody ustalania planów bazowych.

Istnieje m punktów wyjścia („dostawców”) i n punktów konsumpcji („konsumentów”) pewnego identycznego produktu. Dla każdej pozycji są zdefiniowane:

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

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

cij - koszt transportu jednej jednostki produkcji z punktu Ai - i-tego dostawcy do punktu Bj - j-tego konsumenta.

Dla jasności wygodnie jest przedstawić dane w formie tabeli, która nazywa się tabelą kosztów transportu.

Konieczne jest znalezienie planu transportu, który w pełni zaspokoiłby popyt wszystkich konsumentów, przy wystarczającej liczbie dostawców i całkowitych kosztach transportu.

Pod pojęciem planu transportowego rozumie się natężenie ruchu, tj. ilość towarów, które mają być przetransportowane od i-tego dostawcy do j-tego konsumenta. Aby zbudować model matematyczny problemu należy wprowadzić m n zmiennych хij, i= 1,…, n, j= 1, …, m, każda zmienna хij oznacza natężenie ruchu od 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 zadań transportowych zamkniętych i otwartych (ZTZ).

Oczywiście dla rozwiązania problemu 1 konieczne jest, aby całkowity popyt nie przekraczał wielkości produkcji od dostawców:

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

Stan równowagi.

Jest to warunek rozwiązania zadań transportu zamkniętego (ZTZ).

11. Algorytm rozwiązywania problemu transportowego.

Zastosowanie algorytmu wymaga spełnienia szeregu warunków wstępnych:

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

2. Zapas produktów w każdym punkcie produkcji musi być znany.

3. Zapotrzebowanie na żywność w każdym punkcie spożycia musi być znane.

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

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

Etap I. Przedstawienie danych w postaci standardowej tabeli i poszukiwanie dowolnej akceptowalnej alokacji zasobów. Akceptowalna dystrybucja zasobów to taka, która zaspokaja cały popyt w miejscach docelowych i usuwa całą podaż produktów z punktów produkcji.

Etap 2. Sprawdzenie uzyskanej alokacji zasobów pod kątem optymalności

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

Etap 4. Ponowne sprawdzenie optymalności uzyskanej alokacji zasobów.

Ten iteracyjny proces jest powtarzany aż do uzyskania optymalnego rozwiązania.

12. Modele zarządzania zapasami.

Pomimo faktu, że każdy model zarządzania zapasami ma na celu udzielenie odpowiedzi na dwa podstawowe pytania (kiedy i ile), istnieje znaczna liczba modeli, które wykorzystują różnorodne narzędzia matematyczne do budowy.

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

Tak więc, w zależności od charakteru popytu, modele zarządzania zapasami mogą być

deterministyczny;

probabilistyczny.

Z kolei popyt deterministyczny może być statyczny, gdy intensywność konsumpcji nie zmienia się w czasie, lub dynamiczny, gdy niezawodny popyt może zmieniać się w czasie.

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

Najprościej jest w przypadku deterministycznego statycznego popytu na produkty. Jednak ten rodzaj konsumpcji jest w praktyce dość rzadki. Najbardziej złożonymi modelami są modele typu niestacjonarnego.

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

warunki realizacji zleceń. Czas trwania okresu zbiorów może być stały lub być zmienną losową;

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

obecność ograniczeń dotyczących 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ą powtarzalne wykonywanie zadań tego samego typu. Takie systemy odgrywają ważną rolę w wielu obszarach gospodarki, finansów, produkcji i życia codziennego. Jako przykłady CMO w obszarze finansowym i gospodarczym; W sferze banki różnego typu (komercyjne, inwestycyjne, hipoteczne, innowacyjne, oszczędnościowe), organizacje ubezpieczeniowe, państwowe spółki akcyjne, spółki, firmy, stowarzyszenia, spółdzielnie, inspekcje podatkowe, usługi audytorskie, różne systemy łączności (w tym centrale telefoniczne ), kompleksy załadunkowo-rozładunkowe (porty, stacje towarowe), stacje benzynowe, różne przedsiębiorstwa i organizacje sektora usługowego (sklepy, punkty informacyjne, fryzjerzy, kasy biletowe, kantory, warsztaty naprawcze, szpitale). Za rodzaj QS można również uznać systemy takie jak sieci komputerowe, systemy gromadzenia, przechowywania i przetwarzania informacji, systemy transportowe, zautomatyzowane zakłady 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ń serwisowych, które nazywane są kanałami serwisowymi (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, koleje, stacje benzynowe itp.

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

Każdy QS jest zaprojektowany do obsługi (wykonania) określonego strumienia aplikacji (wymagań), które docierają na wejście systemu w większości nie regularnie, ale w przypadkowych momentach. Zgłoszenia serwisowe w tym przypadku również nie trwają przez stały, znany nam czas, lecz przez czas losowy, który zależy od wielu przypadkowych, czasem nam nieznanych przyczyn. Po obsłużeniu żądania kanał zostaje zwolniony i jest gotowy do przyjęcia następnego żądania. Losowy charakter przepływu zgłoszeń i czas ich obsługi prowadzi do nierównomiernego obciążenia QS: innym razem na wejściu QS mogą gromadzić się nieobsługiwane zgłoszenia, co prowadzi do przeciążenia QS, a czasami przy wolnych kanałach nie będzie żądania na wejściu QS, co prowadzi do niedociążenia QS, tj. opróżnić swoje kanały. Zgłoszenia, które gromadzą się na wejściu do QS, albo „dostają się” do kolejki, albo z uwagi na brak możliwości dalszego przebywania w kolejce pozostawiają QS bez obsługi.

Wskaźniki wydajności dla funkcjonowania pary „QS – konsument”, gdzie przez konsumenta rozumie się cały zestaw aplikacji lub część ich źródła (np. średni dochód, jaki przynosi QS w jednostce czasu itp.). Ta grupa wskaźników jest przydatna w przypadkach, gdy część przychodów uzyskiwanych ze zgłoszeń serwisowych i kosztów obsługi mierzona jest w tych samych jednostkach. Wskaźniki te mają zwykle bardzo specyficzny charakter i są determinowane przez specyfikę QS, obsłużonych próśb oraz 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 względem s przy s = 0, otrzymujemy bezpośrednie równanie Kołmogorowa:

Formalnie różniczkując równanie Kołmogorowa-Chapmana względem t w t = 0, otrzymujemy odwrotne równanie Kołmogorowa

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

W przypadku, gdy liczba stanów systemu S jest skończona i możliwe jest przejście z każdego stanu (na taką lub inną liczbę kroków) do każdego innego stanu, wówczas istnieją graniczne prawdopodobieństwa stanów, które również nie zależą od początkowy stan systemu.

na ryc. przedstawia wykres stanów i przejść spełniających warunek: z dowolnego stanu system może prędzej czy później przejść do dowolnego innego stanu. Warunek nie będzie spełniony, gdy kierunek strzałek 4-3 na wykresie na rys. zostanie odwrócony.

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

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

Oczywiste jest, że graniczne prawdopodobieństwa stanów powinny sumować się do jedności: W związku z tym w systemie ustala się pewien graniczny tryb stacjonarny w: niech układ i losowo zmienia swoje własne stany, ale prawdopodobieństwo każdego z tych stanów nie zależy na czas, a każdy z nich jest realizowany z pewnym stałym prawdopodobieństwem, czyli średnim względnym czasem, jaki system spędza w tym stanie.

15. Proces śmierci i reprodukcji.

Przez proces śmierci i reprodukcji Markowa w czasie ciągłym rozumiemy sp, który może przyjmować tylko nieujemne wartości całkowite; zmiany w tym procesie mogą wystąpić w dowolnym momencie t, podczas gdy w dowolnym momencie może on albo wzrosnąć o jeden, albo pozostać niezmieniony.

Przepływy mnożenia λi(t) są przepływami Poissona prowadzącymi do wzrostu funkcji X(t). Odpowiednio, μi(t) to przepływy śmierci prowadzące do zmniejszenia funkcji X(t).

Ułóżmy równania Kołmogorowa zgodnie z wykresem:

Jeśli wątek o skończonej liczbie stanów:

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

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

Proces czystej śmierci jest takim procesem śmierci i reprodukcji, w którym intensywność wszystkich przepływów reprodukcyjnych jest równa zeru.

16. Systemy kolejkowe z awariami.

Najprostszym z problemów rozważanych w ramach teorii kolejek jest model jednokanałowego QS z awariami lub stratami.

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

Jeśli wniosek trafi do kanału, który w danej chwili nie jest bezpłatny, zostaje odrzucony i nie pojawia się już w systemie. Aplikacje obsługiwane są w czasie losowym, którego rozkład realizowany jest zgodnie z prawem wykładniczym z parametrem:

17. Systemy kolejkowe z czekaniem.

Żądanie, które przychodzi w czasie, 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 liczba miejsc w kolejce jest ograniczona liczbą m, tzn. jeśli klient przychodzi w momencie, gdy w kolejce jest już m klientów, pozostawia system nieobsługiwany. W przyszłości, jeśli m dąży do nieskończoności, otrzymamy charakterystykę jednokanałowego QS bez ograniczeń co do długości kolejki.

Stany QS ponumerujemy według ilości zgłoszeń w systemie (zarówno obsłużonych jak i oczekujących na obsługę):

— kanał jest bezpłatny;

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

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

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

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

18. Metody podejmowania decyzji w warunkach konfliktu. Matrycowe gry. Czyste i mieszane gry strategiczne.

Gra macierzowa to końcowa gra dwóch graczy o sumie zerowej, w której wypłata gracza 1 podana jest 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, adekwatna 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.

Gra macierzowa dla dwóch graczy o sumie zerowej może być postrzegana jako następująca abstrakcyjna gra dla dwóch graczy.

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

Każdy z graczy 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 nazywany czystą strategią.

Definicja. Strategia mieszana gracza to pełny zestaw prawdopodobieństw zastosowania jego czystych strategii.

Zatem jeśli gracz 1 ma m strategii czystych 1,2,...,m, to jego strategia mieszana x jest zbiorem liczb x = (x1,...,xm) spełniających 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 używa jednej czystej strategii, wyklucza użycie innej, czyste strategie są zdarzeniami niekompatybilnymi. Ponadto są to jedyne możliwe zdarzenia.

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

19. Geometryczna metoda rozwiązywania gry macierzowej.

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

Na płaszczyźnie XY, wzdłuż odciętej, odkładamy pojedynczy odcinek A1A2 (ryc. 5.1). Każdy punkt odcinka jest powiązany z jakąś mieszaną strategią U = (u1, u2). Ponadto 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 przywracamy piony i odkładamy na nich wypłaty graczy. Na pierwszej prostopadłej (pokrywającej się z osią OY) pokazujemy wypłatę gracza A przy zastosowaniu strategii A1, na drugiej – przy zastosowaniu strategii A2. Jeżeli gracz A stosuje strategię A1, to jego wypłata przy strategii B1 gracza B wynosi 2, a przy strategii B2 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 (wypłaty 6 i 4).

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

Na przykład odległość od dowolnego punktu odcinka 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.

Rzędne punktów należących do linii łamanej B1MB"2 określają minimalną wypłatę gracza A, gdy stosuje on dowolne strategie mieszane. Ta minimalna wartość jest największa w punkcie M, zatem punkt ten odpowiada strategii optymalnej U* = (,), a jej rzędna jest równa cenie gry v .

Znajdziemy współrzędne punktu M jako współrzędne punktu przecięcia prostych B1B"1 i B2B"2.

Aby to zrobić, musisz znać równania linii. Możesz ułożyć takie równania, korzystając ze wzoru na równanie prostej przechodzącej przez dwa punkty:

Ułóżmy równania prostych dla naszego problemu.

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

Bezpośredni 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.

Więc U = (2/5, 3/5), v = 22/5.

20. Gry dwumacierzowe.

Gra dwumacierzowa 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.)

Dla gier dwumacierzowych opracowano również teorię optymalnego zachowania graczy, jednak rozwiązanie takich gier jest trudniejsze niż konwencjonalnych gier macierzowych.

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

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

niepewność celów;

niepewność naszej wiedzy o środowisku i czynnikach wpływających na to zjawisko (niepewność natury);

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

W powyższej klasyfikacji rodzaj niepewności rozpatrywany jest z punktu widzenia jednego lub drugiego elementu modelu matematycznego. I tak na przykład niepewność celów znajduje odzwierciedlenie w sformułowaniu problemu wyboru albo poszczególnych kryteriów, albo całego wektora użytecznego efektu.

Z drugiej strony pozostałe dwa rodzaje niepewności wpływają głównie na formułowanie funkcji celu równań z ograniczeniami i metody decyzyjnej. Oczywiście powyższe stwierdzenie jest raczej warunkowe, jak zresztą każda klasyfikacja. Przedstawiamy go tylko po to, aby podkreślić jeszcze kilka cech niepewności, o których należy pamiętać w procesie podejmowania decyzji.

Faktem jest, że oprócz powyższej 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, a zatem są zwykłymi obiektami teorii prawdopodobieństwa – zmiennymi losowymi (lub funkcjami losowymi, zdarzeniami itp.). W takim przypadku wszystkie niezbędne charakterystyki statystyczne (prawa dystrybucji i ich parametry) muszą być znane lub określone podczas stawiania 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.

Innym skrajnym przypadkiem może być niepewność niestochastyczna (według E.S. Wentzela – „zła niepewność”), w której nie ma żadnych założeń o stabilności stochastycznej. Wreszcie możemy mówić o pośrednim typie niepewności, gdy decyzja jest podejmowana na podstawie pewnych hipotez dotyczących praw rozkładu zmiennych losowych. Jednocześnie decydent musi mieć na uwadze niebezpieczeństwo rozbieżności między jego wynikami a rzeczywistymi warunkami. To ryzyko niedopasowania jest sformalizowane za pomocą współczynników ryzyka.

Podejmowanie decyzji dotyczących 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 limitu;

najbardziej prawdopodobne wydarzenie w przyszłości.

Operacja każde wydarzenie (system działań), połączone jednym planem i ukierunkowane na osiągnięcie określonego celu, nazywa się. Operacja jest zawsze kontrolowane wydarzenie, tj. można zrezygnować z metody doboru niektórych parametrów charakteryzujących jej organizację. Te opcje są nazywane zmienne kontrolne.

Nazywa się każdy określony wybór takich zmiennych decyzja. Decyzje mogą być udane i nieudane, rozsądne i nierozsądne. Optymalny wymienić takie rozwiązania, które według pewnych kryteriów są lepsze od innych.

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

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

Aby porównać skuteczność różnych rozwiązań, trzeba mieć kryterium ilościowe tzw wskaźnik wydajności(lub funkcja celu). Wskaźnik ten wybiera się, aby odzwierciedlić ukierunkowanie operacji na cel.

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 matematyczne oczekiwanie).

Czasami operacja, której towarzyszą czynniki losowe, dąży do takiego celu. A, które można osiągnąć całkowicie lub nie osiągnąć wcale (np. „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, to dochodzimy do dobrze znanego problemu „czarnej skrzynki” w cybernetyce.)

Zły wybór wskaźnika wydajności jest bardzo niebezpieczny. Operacje zorganizowane według nietrafionego 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 określenie zadania badań operacyjnych

Zadania badań operacyjnych dzielą się na dwie kategorie: a) bezpośrednie i b) odwrotne.

Bezpośrednie zadania 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, budowany jest model matematyczny, który pozwala wyrazić wskaźnik efektywności poprzez dane warunki i rozwiązanie, a mianowicie:

Gdzie
podane czynniki (dane wstępne),

zmienne kontrolne (roztwór),

Z– wskaźnik wykonania (funkcja celu),

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

Zależność ta w różnych modelach wyrażana jest w różny sposób. Związek pomiędzy I zwykle wyrażane jako limity

Jeśli typ zależności F znany, a następnie wskaźnik Z znajduje się przez bezpośrednie podstawienie I do tej funkcjonalności.

Problemy odwrotne odpowiedzieć na pytanie: jak, w danych warunkach wybierz rozwiązanie
tak, że wskaźnik wydajności Z ustawione na maksimum (minimum). Taki problem nazywa się problemem optymalizacji rozwiązania.

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

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

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

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

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

Wspólne cechy badań operacyjnych

W każdym zadaniu mówimy o jakimś wydarzeniu realizującym określony cel.

Postawiono pewne warunki, które charakteryzują sytuację (w tym środki, którymi możemy dysponować).

W ramach tych uwarunkowań wymagane jest podjęcie takiej decyzji, aby planowane wydarzenie było w jakimś sensie najbardziej opłacalne.

Cechy badań operacyjnych

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

Największy efekt można osiągnąć tylko dzięki ciągłym badaniom, które zapewniają ciągłość w przechodzeniu od jednego zadania do drugiego, powstającego w trakcie rozwiązywania poprzedniego.

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

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

Podstawowe pojęcia badań operacyjnych

DZIAŁANIE - każde kontrolowane (to znaczy zależne od wyboru parametrów) wydarzenie, połączone jednym planem i mające na celu osiągnięcie jakiegoś celu.

ROZWIĄZANIE - dowolny konkretny dobór parametrów zależny od nas.

OPTYMALNE ROZWIĄZANIA – decyzje z takiego czy innego powodu są lepsze od innych.

CELEM BADANIA EKSPLOATACYJNEGO jest wstępne uzasadnienie ilościowe optymalnych rozwiązań.

ELEMENTY ROZWIĄZANIA - parametry, których całość tworzy rozwiązanie.

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

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

Pojęcie modelu matematycznego operacji

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

Bezpośrednie i odwrotne problemy badań operacyjnych

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

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

PROBLEMY ODWRÓCONE odpowiadają na pytanie, jak wybrać rozwiązanie x, aby wskaźnik efektywności W osiągnął maksimum (minimum).

Te zadania są trudniejsze. Można je rozwiązać przez proste wyliczenie rozwiązań bezpośrednich problemów.

Gdy jednak liczba rozwiązań jest duża, stosuje się metody wyliczania ukierunkowanego, w których optymalne rozwiązanie znajduje się wykonując kolejne „próby” lub przybliżenia, z których każde przybliża nas do pożądanego optymalnego.

Rozdział 1. Przedmiot i zadania badań operacyjnych.

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

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

§ 3. Modele matematyczne operacji.

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

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

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

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

Rozdział 3. Programowanie liniowe.

§ 7. Zagadnienia programowania liniowego.

§ 8. Główny problem programowania liniowego.

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

§ 10. Problem transportu programowania liniowego.

§ 11. Zagadnienia programowania całkowitoliczbowego. Pojęcie programowania nieliniowego.

Rozdział 4. Programowanie dynamiczne.

§ 12. Metoda programowania dynamicznego.

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

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

Rozdział 5 Losowe procesy Markowa.

§ 15. Pojęcie procesu Markowa.

§ 16. Przebieg zdarzeń.

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

Rozdział 6

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

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

§ 20. Najprostsze systemy kolejkowe i ich charakterystyka.

§ 21. Bardziej skomplikowane problemy teorii kolejek.

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

§ 22. Idea, cel i zakres metody.

§ 23. Partia i formy jej organizacji.

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

Rozdział 8

§ 25. Przedmiot i problemy teorii gier.

§ 26. Antagonistyczne gry macierzowe.

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

§ 28. Zagadnienia teorii rozwiązań statystycznych.

PRZEDMIOT I CELE BADAŃ OPERACYJNYCH

Podstawowe pojęcia i zasady badań operacyjnych

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

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

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

Każdy określony wybór parametrów zależnych od nas nazywamy decyzją. Decyzje mogą być udane i nieudane, rozsądne i nierozsądne. Rozwiązania nazywane są optymalnymi, jeśli z tego czy innego powodu są preferowane w stosunku do innych. Celem badań operacyjnych jest wstępne ilościowe uzasadnienie optymalnych rozwiązań.

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

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

Nieodzowna obecność osoby (jako ostatecznego organu decyzyjnego) nie jest anulowana nawet w obecności w pełni zautomatyzowanego systemu sterowania, który, jak się wydaje, podejmuje decyzję bez udziału człowieka. Nie wolno nam zapominać, że samo stworzenie algorytmu sterującego, wybór jednej z jego możliwych opcji, to także decyzja, i to bardzo odpowiedzialna. Wraz z rozwojem automatów sterujących funkcje człowieka nie są anulowane, ale po prostu przenoszone z jednego, elementarnego poziomu na inny, wyższy. Ponadto szereg zautomatyzowanych systemów sterowania zapewnia aktywną interwencję człowieka podczas kontrolowanego procesu.

Te parametry, których całość tworzy rozwiązanie, nazywane są elementami rozwiązania. Jako elementy rozwiązania mogą pojawić się różne liczby, wektory, funkcje, znaki fizyczne itp. Na przykład, jeśli zostanie sporządzony plan transportu jednorodnych towarów z punktów wyjścia A 1, A 2, ..., A m do miejsc docelowych W 1,В 2 , ..., В n , wtedy elementami rozwiązania będą liczby x ij , pokazujący, ile ładunku zostanie wysłane z pierwszego punktu wyjścia ja V J-ty cel podróży w j. Zestaw liczb X 11 , X 12, …, X 1 n , …, X m 1 , X m 2 , …, xmn tworzy rozwiązanie.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Przykłady rozwiązywania problemów programowania dynamicznego

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

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

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

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

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

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

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

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

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

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

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

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

W* = 118.

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

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

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

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

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

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

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

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

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

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

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

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

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

(13.1)

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

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

i warunkową optymalną wypłatę

W m (S) = (S).

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

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

,

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

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

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

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

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

,

i tak dalej aż do końca.

Rozwiążmy teraz przykład liczbowy. Początkowy zasób środków K = 10 (jednostek konwencjonalnych) i wymagane jest optymalne rozłożenie jej pomiędzy pięć przedsiębiorstw (t = 5). Dla uproszczenia założymy, że inwestowane są tylko całkowite kwoty środków. funkcje dochodu ( X) podano w tabeli 13.1.

Tabela 13.1

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

W każdej kolumnie, począwszy od określonej kwoty inwestycji, dochody przestają rosnąć (w rzeczywistości odpowiada to temu, że każde przedsiębiorstwo jest w stanie „opanować” tylko ograniczoną ilość środków).

Przeprowadźmy optymalizację warunkową w sposób opisany powyżej, zaczynając od ostatniego, piątego kroku. Za każdym razem dochodzimy do kolejnego kroku, mając rezerwę środków S, staramy się przeznaczyć taką czy inną kwotę środków na ten krok, zysk na tym kroku bierzemy zgodnie z tabelą 13.1, dodajemy go do już zoptymalizowanego zysku na wszystkich kolejnych krokach aż do końca (biorąc pod uwagę, że zostało nam już mniej środków, wystarczy o taką ilość środków, jakie przeznaczyliśmy) i znajdź inwestycję, przy której suma ta osiągnie swoje maksimum. Ta inwestycja jest warunkowo optymalną kontrolą na tym etapie, a samo maksimum jest warunkowym optymalnym zyskiem.

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

Tabela 13.2

S	i=5	i=4	i=3	i=2	i=1
x5(S)	W 5(S)	x4(S)	W4(S)	x 3(S)	W 3(S)	x2(S)	W2(S)	x 1(S)	W 1(S)
		1,0 1,2 1,3 1,3 1,3 1,3 1,3 1,3 1,3 1,3		1,0 1,3 1,6 2,3 2,5 2,6 2,7 2,8 2,8 2,8		1,0 1,6 2,1 2,4 2,9 3,4 3,6 3,7 3,9 4,1		1,0 1,6 2,1 2,4 2,9 3,5 4,1 4,6 5,1 5,6		5,6

warunkowa kontrola optymalna, w drugiej - warunkowa optymalna wypłata. Tabela jest wypełniona od lewej do prawej, od góry do dołu. Decyzja na piątym – ostatnim – etapie jest wymuszona: wszystkie środki są przydzielone;

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

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

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

Tabela 13.3

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

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

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

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

3. Problem załadunku maszyny. Korzystając z metody programowania dynamicznego, można z powodzeniem rozwiązać szereg problemów optymalizacyjnych opisanych w rozdziale 3, w szczególności niektóre problemy programowania całkowitoliczbowego. Zauważmy, że integralność rozwiązań, która sprawia, że ​​problemy z programowaniem liniowym są tak trudne, w tym przypadku nie komplikuje, a wręcz przeciwnie, upraszcza procedurę (tak jak została ona dla nas uproszczona przez integralność zanurzeń w poprzednim zadaniu).

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