- 1,03 MB

Podajmy matematyczne sformułowanie zasady optymalności. Dla uproszczenia założymy, że dane są początkowe stany x 0 i końcowe x T układu. Oznaczmy przez z 1 (x 0 , u 1) wartość funkcji celu w pierwszym etapie przy stanie początkowym układu x 0 i przy sterowaniu u 1 , przez z 2 (x 1 , u 2) odpowiednią wartość funkcji celu dopiero na drugim etapie, ..., do
z i (х i -1,u i) – wł i-ty etap, ..., poprzez z N (x N -1 , u N) -on N-ty etap. To oczywiste

Musimy znaleźć optymalną kontrolę u*= (; ;...;), taką, która zapewni ekstremum funkcja celu(1) z zastrzeżeniem ograniczeń.

Aby rozwiązać ten problem, zanurzamy go w rodzinie podobnych. Wprowadźmy pewną notację. Niech będą odpowiednio obszarami

definicje podobnych problemów na ostatnim etapie, dwóch ostatnich itp.;
- domena oryginalny problem. Oznaczmy odpowiednio przez F 1 (x N -1), F 2 (x N -2), ..., F k (x N -k), ..., F N (x 0), odpowiednio, warunkowo optymalne wartości funkcji celu na ostatnim etapie, dwa ostatnie itd., na k ostatnich itd., na wszystkich N etapach.

Zacznijmy ostatni etap. Niech x N-1 będą możliwymi stanami układu na początku N-tego etapu. Znaleźliśmy:

F 1 (x N -1) = z N (x N -1, u N). (2)

Dla dwóch ostatnich etapów otrzymujemy

F 2 (x N -2) = (Z N -1 (x N -2, u N -1) + F 1 (x N -1)). (3)

Podobnie:

F 3 (x N -3) = (Z N -2 (x N -3, u N -2) + F 2 (x N -2)). (4)

………………………………………………….

F k (x N -k) = (z N-k +1 (x N -k, u N-k +1) + F k- 1 (x N-k +1)). (5)

…………………………………………………..

F N (x 0) = (z 1 (x 0, u 1) + F N -1 (x 1)). (6)

Wyrażenie (6) jest matematyczną reprezentacją zasady optymalności. Wyrażenie (5) – ogólny kształt rejestrowanie warunkowo optymalnej wartości funkcji celu dla k pozostałych etapów. Wyrażenia (2) – (6) nazywane są funkcjonalnymi równaniami Bellmana. Wyraźnie widać ich rekurencyjny (rekurencyjny) charakter, tzn. aby znaleźć optymalną kontrolę w N krokach, trzeba znać warunkowo optymalną kontrolę w poprzednich N – 1 etapach itp. Dlatego często równania funkcyjne nazywane są rekurencyjnymi (rekurencyjnymi) Relacje Bellmana.

1. Cechy zadań Programowanie dynamiczne

Na podstawie powyższego możemy wyróżnić następujące cechy problemów programowania dynamicznego.

• Rozważamy układ, którego stan na każdym etapie jest określony przez wektor x t. Dalsze zmiany w jej stanie zależą tylko od ten stan x t i nie zależy od tego, w jaki sposób system doszedł do tego stanu. Takie procesy nazywane są procesami bez następstw.
• Na każdym etapie wybierane jest jedno rozwiązanie u t, pod wpływem którego system wychodzi Poprzedni stan x t -1 do nowego x t . Ten nowy stan jest funkcją stanu na początku przedziału x t -1 oraz decyzji u t podjętej na początku przedziału, czyli x t = x t (x t -1,u t).
• Działanie na każdym etapie wiąże się z określonym zyskiem (przychodem, zyskiem) lub stratą (kosztami), które zależą od stanu na początku kroku (etapu) i podjętej decyzji.
• Ograniczenia można nałożyć na wektory stanu i sterowania, których kombinacja tworzy obszar możliwych rozwiązań.
• Należy znaleźć taką dopuszczalną kontrolę u t dla każdego stopnia t, aby otrzymać ekstremalną wartość funkcji celu dla wszystkich T kroków.

Dowolna prawidłowa sekwencja działań dla każdego kroku, która przenosi system ze stanu początkowego do stanu końcowego, nazywana jest strategią sterowania. Strategię sterowania, która skutkuje ekstremalną wartością funkcji celu, nazywamy optymalną.

Interpretacja geometryczna problemu programowania dynamicznego jest następująca. Niech n będzie wymiarem przestrzeni stanów. W każdym momencie współrzędne układu mają bardzo określoną wartość. Wraz ze zmianą czasu t wartości współrzędnych wektora stanu mogą się zmieniać. Przejście układu z jednego stanu do drugiego nazwijmy trajektorią jego ruchu w przestrzeni stanów. Takie przejście odbywa się poprzez wpływ na współrzędne stanu. Przestrzeń, w której stany układu służą jako współrzędne, nazywa się przestrzenią fazową. Problem programowania dynamicznego można zinterpretować szczególnie wyraźnie, jeśli przestrzeń stanów jest dwuwymiarowa. Obszar możliwych stanów w tym przypadku zostanie przedstawiony pewną figurą, stany początkowy i końcowy układu - punktami x 0 (ryc. 1). Sterowanie to wpływ, który przenosi system ze stanu początkowego do stanu końcowego. W przypadku wielu problemów ekonomicznych nie jest znany stan początkowy lub końcowy, ale znany jest obszar X 0 lub X T, do którego należą te punkty.

Obrazek 1

Następnie dopuszczalne punkty kontrolne przenoszą punkty z obszaru X 0 do X T . Problem programowania dynamicznego można geometrycznie sformułować następująco: znaleźć trajektorię fazową rozpoczynającą się w obszarze X 0 i kończącą się w obszarze X T, dla której funkcja celu osiąga wartość ekstremalną. Jeśli znany jest stan początkowy i końcowy problemu programowania dynamicznego, wówczas mówimy o problemie o ustalonych końcach. Jeśli znane są obszary początkowe i końcowe, mówimy o problemie z wolnymi końcami.

1. PROBLEM DYSTRYBUCJI ZASOBÓW

2.1 Ogólne określenie problemu

Rozważmy zastosowanie metody programowania dynamicznego na przykładzie podziału środków pomiędzy sześć obiektów rekonstrukcyjnych przedsiębiorstwa wodociągowego:

1. Centralna stacja pompowo-filtracyjna;

2. Wschodnia przepompownia i filtracja;

3. Przepompownia wody;

4. Centralna stacja napowietrzania;

5. Stacja napowietrzania wschodniego;

6. Stacja napowietrzania wiejskiego.

Łączna kwota środków przeznaczonych na rozwój to nie więcej niż 195 tysięcy hrywien. Na podstawie obliczeń techniczno-ekonomicznych ustalono, że w wyniku przebudowy, w zależności od wielkości wydanych środków, obiekty będą charakteryzowały się wydajnością przedstawioną w tabeli 1.1. Konieczne jest określenie optymalnego podziału środków pomiędzy obiektami rekonstrukcyjnymi, który zapewni maksymalny wzrost produktywności tych obiektów. Zatem w zadaniu tym zastosowano kryterium optymalizacyjne – całkowitą produktywność przedsiębiorstw obiektów rekonstrukcyjnych.

Tabela 1.1 Dane wejściowe dotyczące produktywności obiektów rekonstrukcyjnych

Numer seryjny obiektu

Wolumen środków przeznaczonych na rozwój obiektów (tys. UAH)

Produktywność obiektów w wyniku zagospodarowania (tys. m3)

1. Schemat blokowy programu

Rysunek 1. Program główny

QtObj – liczba obiektów

QtRes – liczba zasobów

effMatrix - macierz wydajności obiektu,

distVector – wektor przydzielonych zasobów

Krok 1: Optymalizacja warunkowa

Krok 2. Optymalizacja bezwarunkowa

I = QtObj-1.0 z wyniku wektorowego

Rysunek 2. Wprowadzanie danych

distVector – wektor odległości, effMatrix = macierz wydajności

jeśli zostaną wprowadzone wszystkie elementy macierzy

jeśli wektor wydajności nie jest

negatywny

Rysunek 3. Optymalizacja warunkowa,

tworzymy macierz wyjściową (maksimum funkcji celu)

outMatrix – maksymalna macierz docelowa

QtObj – liczba obiektów

QtRes – liczba zasobów

Matryca – macierz wydajności

distVect – wektor odległości (wektor zasobu)

nie tak Jeśli pierwsze przedsiębiorstwo

Znalezienie maksimum

tak maxItem = temp; outMatrix[i][j] = maxItem

1. Struktura algorytmu programu

1. Wprowadzanie danych – klasa DataDlg.

Zmienni członkowie klasy.

//wektor do przechowywania ilości zasobów

std::wektor distVector;

//macierz wydajności obiektu

int** effMatrix;

//funkcja konwertująca ciąg znaków na liczbę

int StringToInt(CString);

//funkcja sprawdzająca poprawność wprowadzonych danych

BOOLWypełnijMacierz();

//funkcja czyszczenia zasobów po zamknięciu okna

wirtualny BOOL DestroyWindow();

//funkcja inicjowania dialogu

wirtualny BOOL OnInitDialog();

1. Obliczanie wyników - główna klasa programu CourseWorkDlg

Zmienni członkowie klasy

wartość całkowita; //wartość wydajności

intMaxIndex;// maksymalny indeks w wektorze zasobów

int Obiekt;//przedsiębiorstwo

int Recource;//dedykowany zasób

Pozycja ** outMatrix; //maksymalna macierz docelowa

std::wektor resWektor; //wektor wyników

void BuildOutMatrix(int**,std::vector );//funkcja generowania macierzy celów (optymalizacja warunkowa)

afx_msg void OnBnClickedButton1(); // moduł obsługi kliknięcia przycisku „Oblicz”, który rozpoczyna proces obliczeń.

virtual BOOL DestroyWindow();//czyszczenie zasobów programu

1. Wyprowadzanie raportu klasy wyników

Celem tej klasy jest wyświetlenie wektora wynikowego w formie tabelarycznej.

2.4 Wyniki programu

Wstępne wprowadzanie danych

1. Wprowadzanie danych o produktywności obiektów rekonstrukcyjnych

1. Jeżeli nie wszystkie pola są wypełnione

1. Jeżeli wprowadzono nieprawidłowy znak

Poprawne wprowadzanie danych

Pokaż rezultat

1. Wprowadzanie danych

Wynik programu

Wstępne wprowadzanie danych

Wprowadzanie produktywności obiektu

Aplikacja.

Lista programów

int DataDlg::StringToInt(CString str)

const wchar_t* s = T2CW(str);

int val = _wtoi(s);

// czy wszystkie pola są wypełnione?

BOOL DataDlg::FillMatrix()

flaga bool = prawda;

for (int i = 0; tj< Cells.GetSize(); i ++){

for (int j = 0 ; j< Cells.GetAt(i)->Edytuje.GetSize(); j++)(

CEdit * temp = Cells.GetAt(i)->Edits.GetAt(j) ;

if (temp->m_hWnd != NULL)(

temp->GetWindowText(str);

if (str.IsEmpty())(

MessageBox(L"Musisz wypełnić wszystkie pola", L"Błąd", MB_ICONERROR | MB_OK);

Opis pracy

Celem pracy jest zaimplementowanie na komputerze rozwiązania problemu optymalnej alokacji środków na rozwój produkcji.
Cele zajęć:
Rozważać aspekty teoretyczne rozwiązywanie problemów programowania dynamicznego; powtarzalny charakter zadań tego typu; Zasady optymalności Bellmana.
Opracowanie algorytmu. Schematy blokowe. Struktura algorytmu.
Implementacja komputerowa opracowanego algorytmu w wybranym języku programowania.

Treść

WSTĘP………………………………………………………2
Programowanie dynamiczne
Podstawowe pojęcia…………………4
Zasady programowania dynamicznego. Równania funkcyjne Bellmana………………….5
Cechy problemów programowania dynamicznego…………….10
Problem alokacji zasobów………………………12
Ogólne przedstawienie problemu……………………….13
Schemat blokowy programu
Struktura algorytmu programu
Wynik programu
Wniosek
Bibliografia

Wyślij swoją dobrą pracę do bazy wiedzy jest prosta. Skorzystaj z poniższego formularza

Dobra robota do serwisu">

Studenci, doktoranci, młodzi naukowcy, którzy wykorzystują bazę wiedzy w swoich studiach i pracy, będą Państwu bardzo wdzięczni.

Wysłany dnia http://www.allbest.ru/

Problem alokacji zasobów metodą programowania dynamicznego

Aby zwiększyć moce produkcyjne trzech przedsiębiorstw A, B i C, przydzielana jest określona liczba jednostek dodatkowej energii elektrycznej w ilości x 0 = 8 jednostek. Energię elektryczną można wypuścić w postaci 1, 2, 3, 4, 5, 6, 7 i 8 jednostek. Inwestując x i jednostek energii elektrycznej w rozwój i-tego przedsiębiorstwa, możesz uzyskać dochód z i jednostek w tym przedsiębiorstwie. Istnieć różne warianty x i k) przydział dodatkowej energii elektrycznej. Przynoszą dochód do i (k), k=1,n. Możliwe opcje rozwój przedsiębiorstw przedstawiono w tabeli 1. Całkowity dochód dla wszystkich przedsiębiorstw powinien być maksymalny, tj. y=? y i (k)>max

Tabela 1. Możliwości rozwoju przedsiębiorstwa

Opcja k	Przedsiębiorstwo A	Przedsiębiorstwo B	Przedsiębiorstwo C

Matematyczny inscenizacja zadania:

ty=? Na I (k)> maks

?X I (k)?x 0

Rozwiązanie:

Rozważanie sposobu rozwiązania problemu zacznijmy od ostatniego (3 kroki) etapu (tabela 2), w którym przydzielane są inwestycje przedsiębiorstwu C. Jako rozwiązanie równania poszukiwane jest warunkowe optymalne sterowanie na trzecim etapie

sol do (S 2)=max k f do , x C (k)?S 2 , k=1,2,3,4

Tabela 2. Rozwiązania warunkowo optymalne (krok 3)

Państwo		Kontrola

Istnieją cztery możliwości inwestowania środków - kontrola czteroetapowa x C (1) = 0 jednostek, x C (2) = 1 jednostka, x C (3) = 2 jednostki, x C (4) = 3 jednostki. oraz dziewięć teoretycznie możliwych stanów układu S 2 poprzedzających przydział środków przedsiębiorstwu C – wolumeny inwestycji nieprzydzielonych do III etapu: 0,1,2,3,4,5,6,7,8.

Załóżmy, że układ znajdował się w stanie S 2 = 2. Wtedy dla regulacji skokowej x C (2) = 1 dochód C (2) będzie równy 3 jednostkom. (Tabela 3), a sterowanie krokowe x C (3) = 2 będzie optymalne dla tego stanu, dając warunkowo maksymalne wzmocnienie g c (S 2) = 5. Jeżeli system był w stanie S 2 =3, to dozwolone są wszystkie regulacje krokowe: x C (1) = 0 jednostek, x C (2) = 1 jednostka, x C (3) = 2 jednostki, x C (4) = 3 jednostki. , a optymalna kontrola będzie wynosić x C (4) = 3, co zapewnia warunkowo maksymalne wzmocnienie g c (S 2) = 6.

Tabela 3. Dystrybucja inwestycji w programowaniu dynamicznym

W podobny sposób wypełniane są wszystkie możliwe stany poprzedzające etap 3. Optymalne wartości wskaźników zaznaczono w tabelach pogrubioną czcionką.

Następnie w ten sam sposób rozpatrywany jest drugi etap (tabela 4), który polega na przydzieleniu inwestycji przedsiębiorstwu A. W drugim etapie całkowity zysk jest sumą wygranych otrzymanych w trzecim i drugim etapie i jest podawany według stosunku:

g A (S 1)=max k f A +g c], x A (k)?S 1, k=1,2,3,4

Zatem dla stanu S 1 =3 przy sterowaniu krokowym x A (2) = 1 otrzymujemy:

sol ZA (S 1)=max k fa ZA + sol do ]

Max k 4+g c =4+5=9, gdzie znajdujemy z tabeli 1, a g c z tabeli 3. Wszystkie stany wypełniamy w podobny sposób.

Tabela 4. Rozwiązania warunkowo optymalne (krok 2)

Państwo	fa + g do	Kontrola

Powstają tu sytuacje, w których rozwiązanie optymalne nie będzie rozwiązaniem jedynym, zatem w stanie S 1 = 3 sterowanie krokowe x A (2) = 1 i x A (3) = 2 będzie warunkowo optymalne, dając to samo zysk g A (S 1) = 9

Tabela 5. Rozwiązania bezwarunkowo optymalne (krok 1)

Na pierwszym etapie (tabela 5) – przyporządkowaniu inwestycji przedsiębiorstwu B – występuje tylko jeden stan poprzedni systemu, odpowiadający stanowi początkowemu S 0 =8. Bezwarunkowo optymalne wzmocnienie jest określone przez wyrażenie:

y * = g B (S 0)= max k (f A +g A) x in (k)?S 0 =x 0, k=1,2,3,4,5

Bezwarunkowo optymalne kontrole zapewniające maksymalny dochód mogą być różne.

Schemat odnalezienia wszystkich optymalne opcje rozkład inwestycji pomiędzy przedsiębiorstwami (tabela 6) przedstawia rysunek 1.

Tabela 6. Optymalny rozkład inwestycji.

Rysunek 1. Schemat optymalnego podziału inwestycji pomiędzy przedsiębiorstwa

Wniosek: po rozważeniu problemu alokacji zasobów metodą programowania dynamicznego zidentyfikowano dwie możliwości optymalnej alokacji zasobów.

Opublikowano na Allbest.ru

...

Podobne dokumenty

ogólna charakterystyka oraz wskaźniki wyników ekonomicznych trzech badanych przedsiębiorstw. Rozwiązanie problemu planowania produkcji i podziału inwestycji z wykorzystaniem programowania liniowego i dynamicznego. Analiza porównawcza wyników.

praca na kursie, dodano 25.04.2015


Procesy wieloetapowe w zadania dynamiczne. Zasada optymalności i relacje powtarzalności. Metoda programowania dynamicznego. Problemy optymalnej alokacji środków na rozwój produkcji i planowanie programu produkcyjnego.

praca na kursie, dodano 30.12.2010


Metoda programowania dynamicznego i jej główne etapy. Optymalna strategia wymiany sprzętu. Minimalizacja kosztów budowy i funkcjonowania przedsiębiorstw. Optymalny podział zasobów w STROYKROVLYA LLC i inwestycje w PKT Khimvolokno.

praca na kursie, dodano 01.08.2015


Matematyczny model planowania produkcji. Opracowanie optymalnego planu działalności produkcyjnej przedsiębiorstwa metodą Programowanie liniowe. Odkrycie Najlepszym sposobem dystrybucja zasobów pieniężnych w okresie planowania.

praca magisterska, dodana 08.07.2013


Obliczanie kosztów transportu metodą minimalne koszty. Znajdowanie warunkowej optymalnej równości w procesie programowania dynamicznego. Liniowy równanie algebraiczne Kołmogorow dla średniego czasu bezproblemowa praca system redundantny.

praca na kursie, dodano 14.01.2011


Metoda graficzna rozwiązywanie problemu optymalizacji procesów produkcyjnych. Zastosowanie algorytmu simplex do rozwiązania ekonomicznie zoptymalizowanego problemu zarządzania produkcją. Metoda programowania dynamicznego do wyboru optymalnego profilu ścieżki.

test, dodano 15.10.2010


Optymalny plan podział środków pomiędzy przedsiębiorstwami. Opracowanie planu dla każdego przedsiębiorstwa, w którym będzie zwrot z inwestycji najwyższa wartość. Stosowanie metod programowania liniowego i dynamicznego.

praca na kursie, dodano 16.12.2013


Charakterystyczne cechy problemów programowania liniowego. Ogólne sformułowanie problemu planowania produkcji. Budowa modelu matematycznego podziału zasobów przedsiębiorstwa. Analiza wrażliwości rozwiązania optymalnego. Sporządzanie raportu zrównoważonego rozwoju.

prezentacja, dodano 12.02.2014


Znalezienie optymalnego portfela papierów wartościowych. Przegląd metod rozwiązania problemu. Budowa modelu matematycznego. Problem z programowaniem stożka. Zależność wektora podziału kapitału początkowego od jednego z parametrów początkowych.

praca magisterska, dodana 02.11.2017


Dynamiczny model programowania. Zasada optymalności i równanie Bellmana. Opis procesu modelowania i konstruowania schematu obliczeniowego programowania dynamicznego. Problem minimalizacji kosztów budowy i funkcjonowania przedsiębiorstw.

Plan lekcji

Dyscyplina akademicka METODY I MODELE MATEMATYCZNE W EKONOMII

Temat lekcji Rozwiązanie różnych problemy praktyczne DP przy użyciu metod matematycznych.

Cele Lekcji

Rozwijanie umiejętności rozwiązywania problemów programowania dynamicznego.

Rozwój jakości umysłu, uwagi i umiejętności pracy akademickiej uczniów.

Zaszczepianie w uczniach dyscypliny i determinacji.

Sprzęt do lekcji Notatki z wykładów, wiceprezes Agaltsov „Metody matematyczne w programowaniu”.

Podczas zajęć:

Czas organizacji:

sprawdzanie nieobecności, uzupełnianie dziennika.

Aktualizacja wiedzy referencyjnej: odpowiedzi na pytania zabezpieczające

Jakie zadania nazywane są wieloetapowymi?

Jakiego aparatu matematycznego używa się do rozwiązywania problemów wieloetapowych?

Jaka jest optymalna kontrola u*?

Jaki jest algorytm metody kolejne przybliżenia w dwóch kręgach?

Podaj przykłady problemów optymalnej alokacji zasobów.

Nauka nowego materiału:

Klasyczne problemy programowania dynamicznego

• Problem z najdłuższym wspólnym podciągiem: Mając dwa ciągi, musisz znaleźć najdłuższy wspólny podciąg.

• Problem znalezienia najdłuższego podciągu rosnącego: mając dany ciąg, należy znaleźć najdłuższy podciąg rosnący.

• Problem odległości redakcyjnej (odległość Levenshteina): mając dwa ciągi znaków, należy znaleźć minimalną liczbę wymazań, zamian i dodań znaków, które przekształcają jeden ciąg w drugi.

• Problem obliczania liczb Fibonacciego

• Problem kolejności mnożenia macierzy: mając dane macierze, ..., przy ich mnożeniu należy minimalizować liczbę operacji skalarnych.

• Problem z wyborem trajektorii

• Problem sekwencyjnego podejmowania decyzji

• Problem wykorzystania pracy

• Problem z zarządzaniem zapasami

• Problem plecakowy: z nieograniczonego zbioru obiektów o właściwościach „koszt” i „waga” należy wybrać określoną liczbę obiektów w taki sposób, aby przy ograniczonej wadze całkowitej uzyskać maksymalny koszt całkowity.

• Algorytm Floyda-Warshalla: znajdź najkrótsze odległości pomiędzy wszystkimi wierzchołkami ważonego grafu skierowanego.

• Algorytm Bellmana-Forda: znajdź najkrótszą ścieżkę w grafie ważonym pomiędzy dwoma danymi wierzchołkami.

• Maksymalny niezależny zbiór wierzchołków w drzewie: mając drzewo, znajdź maksymalny zbiór wierzchołków taki, aby żadne dwa z nich nie były połączone krawędzią.

Przykład: Optymalna alokacja zasobów

Kapitał 40 milionów rubli. inwestor musi zainwestować w cztery projekty inwestycyjne, aby uzyskać maksymalny dochód. Rentowność projektów podano w tabeli (inwestycje są wielokrotnościami 8 milionów rubli)

ty

Zysk z wdrożenia

f4(u)

f3(u)

f2(u)

f1(u)

55

39

120

115

10 0

120

135

134

14 0

145

158

147

Rozwiązanie:

Jest to problem programowania dynamicznego. Rozwiązanie składa się z dwóch etapów. W pierwszym etapie (od końca do początku) szukamy warunkowego rozwiązania optymalnego, w drugim (od początku do końca) szukamy optymalnego rozwiązania problemu.

Scena 1.

Rozdzielamy kapitał pomiędzy cztery projekty i obliczamy uzyskany zysk L (I ), I = 8,16,24,32,40.

1 krok: Gotówka inwestują w czwarty projekt.

L(8)= 55

L(16)=58

L(24)=90

L(32)=100

L(40)=140

Krok 2: Fundusze są inwestowane w czwarty i trzeci projekt.

ty

Zysk z wdrożenia

1 krok

f3(u)

55

39

10 0

120

14 0

145

Krok 3: Fundusze są inwestowane w projekt czwarty, trzeci (krok 2) i drugi.

ty

Zysk z wdrożenia

Krok 2

fa 2(u)

94

108

120

135

135

175

158

175

134

214

147

Etap 2:

W czwartym kroku wybieramy maksimum uzyskanych wartości zysku L (40) = 214.

I powrót do Odwrotna kolejność Z tabeli do tabeli (od 4 kroków do 1) wybieramy takie wartości dochodu, przy których uzyskuje się wartość 214.

Maksymalny dochód 214 milionów rubli. z zainwestowanych środków można otrzymać przy następującym podziale środków:

1 projekt – 0 milionów rubli.

2 projekt – 24 miliony rubli.

Trzeci projekt – 8 milionów rubli.

4 projekt – 8 milionów rubli.

Konsolidacja nowego materiału:

5. Podsumowanie lekcji: wnioski, oceny, Praca domowa:

(2) ust. 5.1

Ср12: tworzenie i przyswajanie treści materiału teoretycznego

Podpis nauczyciela

Dostępny określona ilość zasoby s 0, które należy rozdzielić pomiędzy n podmiotów gospodarczych na bieżącą działalność w badanym okresie (miesiąc, kwartał, półrocze, rok itp.), aby uzyskać sumę maksymalny zysk. Wielkość inwestycji zasobów x i (;) w działalność każdego podmiotu gospodarczego jest wielokrotnością pewnej wartości h. Wiadomo, że każdy podmiot gospodarczy, w zależności od wielkości wykorzystanych środków x i w badanym okresie, generuje zysk w wysokości f i (x i) (nie jest uzależniony od inwestowania zasobów w inne podmioty gospodarcze).

Wyobraźmy sobie proces podziału zasobów pomiędzy podmiotami gospodarczymi jako n-etapowy proces zarządzania (liczba kroków pokrywa się z numer warunkowy podmiot gospodarczy). Niech s k() będzie parametrem stanu, tj. ilość środków dostępnych po k-tym kroku do podziału pomiędzy pozostałe (n - k) podmioty gospodarcze. Wówczas równania stanu można zapisać w postaci:

Wprowadźmy pod uwagę funkcję - warunkowo optymalny zysk całkowity uzyskany od k-tego, (k+1) - tego, ..., n-tego podmiotu gospodarczego, jeżeli zasoby w wysokości s k-1 () były optymalnie rozłożone pomiędzy nimi. Wiele możliwych decyzje zarządcze względem wielkości rozproszonych zasobów na k-tym kroku można przedstawić następująco: .

Następnie powtarzające się równania R.E. Bellman (odwrócony diagram) będzie wyglądał następująco:

Przykład. Istnieje pewna ilość zasobów s 0 =100, która musi zostać rozdzielona pomiędzy n=4 podmiotów gospodarczych na bieżącą działalność w badanym okresie (miesiącu), aby uzyskać łączny maksymalny zysk. Wielkość zaangażowania zasobów x i (;) w działalność każdego podmiotu gospodarczego jest wielokrotnością wartości h = 20 i jest określona wektorem Q. Wiadomo, że każdy podmiot gospodarczy w zależności od wielkości wykorzystanych środków x i za badany okres przynosi zysk w wysokości f i (x i) () (nie jest zależny od inwestycji zasobów w inne podmioty gospodarcze):

Należy określić, ile zasobów należy przeznaczyć na każde przedsiębiorstwo, aby łączny zysk był jak największy.

Rozwiązanie. Utwórzmy powtarzające się równania Bellmana (schemat odwrotny):

Wyznaczmy maksima warunkowe zgodnie z (13), a wyniki obliczeń przedstawiono w tabeli 1.

Tabela 1. Obliczanie optimów warunkowych

		22+20=42
		22+33=55		17+42=59
		22+46=68		17+55=72		14+59=73
		67+20=87

Według wyników optymalizacja warunkowa Ustalmy optymalną alokację zasobów:

Zatem optymalna alokacja zasobów to:

co zapewni największy zysk w ilości 87 jednostek konwencjonalnych. legowisko. jednostki

Odpowiedź: optymalna alokacja zasobów: która zapewnia największy zysk spośród 87 jednostek konwencjonalnych. legowisko. jednostki

Wniosek

Programowanie dynamiczne to dziedzina programowanie matematyczne, w tym zestaw technik i środków do znalezienia optymalnego rozwiązania, a także optymalizacji każdego kroku w systemie i opracowania strategii zarządzania, to znaczy proces zarządzania można przedstawić jako proces wieloetapowy. Programowanie dynamiczne, wykorzystujące planowanie krok po kroku, pozwala nie tylko uprościć rozwiązanie problemu, ale także rozwiązać te problemy, dla których nie można zastosować metod Analiza matematyczna. Uproszczenie rozwiązania osiąga się poprzez znaczne zmniejszenie liczby badanych opcji, ponieważ zamiast jednorazowo rozwiązywać złożony problem wielowymiarowy, metoda planowania krok po kroku obejmuje wiele rozwiązań dotyczących proste zadania. Planując proces krok po kroku, wychodzimy od interesów całego procesu jako całości, tj. Podejmując decyzję na danym etapie, zawsze należy mieć na uwadze ostateczny cel. Programowanie dynamiczne ma jednak również swoje wady. W przeciwieństwie do programowania liniowego, w którym metoda simplex jest uniwersalna, nie ma takiej metody w programowaniu dynamicznym. Każde zadanie ma swoje własne trudności i w każdym przypadku konieczne jest znalezienie najbardziej odpowiedniej metody rozwiązania. Wadą programowania dynamicznego jest także złożoność rozwiązywania problemów wielowymiarowych. Problem programowania dynamicznego musi spełniać dwa warunki. Pierwszy warunek nazywany jest zwykle warunkiem braku następstw, a drugi warunkiem addytywności funkcji celu problemu. W praktyce występują problemy planistyczne, w których znaczącą rolę odgrywają czynniki losowe, wpływające zarówno na stan systemu, jak i na zysk. Istnieje różnica między deterministycznymi i stochastycznymi problemami programowania dynamicznego. W problemie deterministycznym optymalne sterowanie jest unikalne i jest określone z góry jako trudny program działania. W problemie stochastycznym optymalne sterowanie jest losowe i wybierane jest w trakcie samego procesu, w zależności od losowej sytuacji. W schemacie deterministycznym, przechodząc proces etapami od końca do początku, jest to również na każdym etapie cała linia warunkowe optymalne kontrole, ale ze wszystkich tych kontroli ostatecznie wdrożono tylko jedną. Nie ma to miejsca w schemacie stochastycznym. Każda z warunkowych optymalnych kontroli może faktycznie zostać wdrożona w przypadku poprzedniego ruchu proces losowy doprowadzi system do odpowiedniego stanu. Zasada optymalności jest podstawą krok po kroku rozwiązywania problemów programowania dynamicznego. Typowymi przedstawicielami problemów ekonomicznych programowania dynamicznego są tzw. problemy produkcji i magazynowania, problemy podziału inwestycji kapitałowych, problemy kalendarza planowanie produkcji i inni. Problemy programowania dynamicznego wykorzystuje się przy planowaniu działalności przedsiębiorstwa, uwzględniając zmiany zapotrzebowania na produkty w czasie. W optymalnym podziale zasobów pomiędzy przedsiębiorstwami pod względem kierunku lub czasu. Opis cech programowania dynamicznego i rodzajów problemów, które można w jego ramach sformułować, musi z konieczności być bardzo ogólny i nieco niejasny, ponieważ istnieje ogromna różnorodność różne zadania, wpasowując się w schemat programowania dynamicznego. Tylko nauka duża liczba przykłady zapewniają jasne zrozumienie struktury programowania dynamicznego.

1. Podstawowe pojęcia

1.1. Dynamiczny model programowania

1.2. Zasada optymalności. Równanie Bellmana

2. Optymalna alokacja zasobów

2.1 Opis problemu

2.2 Dwuwymiarowy model alokacji zasobów

2.3 Dyskretny model dynamiczny optymalna alokacja zasobów

2.4 Uwzględnienie następstw w problematyce optymalnej alokacji zasobów

Wniosek

Lista wykorzystanych źródeł

Załącznik 1. Lista programów rozwiązujących problem optymalnej alokacji zasobów przy zadanych parametrach. Wyniki programu

Wstęp

W całej historii ludzie uciekali się do skomplikowanych rytuałów, gdy musieli podjąć decyzję. Odprawiali uroczyste ceremonie, składali ofiary ze zwierząt, przepowiadali przyszłość za pomocą gwiazd i obserwowali lot ptaków. Opierali się na ludowych przesądach i starali się kierować prymitywnymi zasadami, które ułatwiały im trudne zadanie podejmowania decyzji. Obecnie do podejmowania decyzji wykorzystuje się nowy i, najwyraźniej, bardziej naukowy „rytuał”, oparty na wykorzystaniu komputera elektronicznego. Bez nowoczesnych środki techniczne Umysł ludzki prawdopodobnie nie jest w stanie uwzględnić wielu różnorodnych czynników, jakie napotykają przy prowadzeniu biznesu, projektowaniu rakiety czy regulowaniu ruchu drogowego. Obecnie istnieje ich wiele metody matematyczne optymalizacje są już dość rozwinięte, co pozwala efektywnie wykorzystać możliwości rozwiązań cyfrowych i hybrydowych komputery. Jedną z tych metod jest programowanie matematyczne, które obejmuje obie metody szczególny przypadek Programowanie dynamiczne.

Większość praktycznych problemów ma kilka (a niektóre być może nawet nieskończona liczba) rozwiązania. Celem optymalizacji jest znalezienie najlepszym rozwiązaniem spośród wielu potencjalnie możliwych zgodnie z pewnym kryterium wydajności lub jakości. Problem, który pozwala tylko na jedno rozwiązanie, nie wymaga optymalizacji. Optymalizację można osiągnąć za pomocą wielu strategii, począwszy od bardzo złożonych procedur analitycznych i numerycznych matematycznych po inteligentne wykorzystanie prostej arytmetyki.

Programowanie dynamiczne jest metodą optymalizacyjną dostosowaną do operacji, w której proces decyzyjny można rozbić na odrębne etapy (kroki). Takie operacje nazywane są wieloetapowy.

Jako gałąź programowania matematycznego, programowanie dynamiczne (DP) zaczęło się rozwijać w latach 50. XX wieku. dzięki pracy R. Bellmana i jego współpracowników. Po raz pierwszy za pomocą tej metody rozwiązano problemy optymalnego zarządzania zapasami, następnie klasa problemów znacznie się rozszerzyła. Jak metoda praktyczna optymalizacji metoda programowania dynamicznego stała się możliwa dopiero przy zastosowaniu nowoczesnej technologii komputerowej.

Metoda programowania dynamicznego opiera się na zasadzie optymalności sformułowanej przez Bellmana. Zasada ta oraz idea włączenia konkretnego problemu optymalizacyjnego do rodziny podobnych problemów wieloetapowych prowadzą do relacji rekurencyjnych – równań funkcjonalnych – względem optymalna wartość funkcja docelowa. Ich rozwiązanie pozwala nam konsekwentnie uzyskać optymalną kontrolę nad pierwotnym problemem optymalizacyjnym.

1. Podstawowe pojęcia

1.1 Dynamiczny model programowania

Dajmy ogólny opis dynamiczne modele programowania.

Rozważany kontrolowany system, który pod wpływem kontroli przechodzi od stanu początkowego

do stanu końcowego. Załóżmy, że proces zarządzania systemem można podzielić na P kroki. Niech , ,…, będą stanami układu po pierwszym, drugim,..., P-ty krok. Pokazano to schematycznie na rys. 1.

Obrazek 1

Państwo

systemy po kth krok ( k = 1,2 …,N) charakteryzuje się parametrami , ,…, które nazywane są współrzędne fazy. Stan można przedstawić za pomocą punktu w przestrzeni s-wymiarowej zwanego przestrzeń fazowa. Konsekwentną transformację systemu (krok po kroku) osiąga się za pomocą określonych działań , ,…, , które stanowią zarządzanie systemem , gdzie jest włączona kontrola k-krok, przeniesienie systemu ze stanu do stanu (ryc. 1). Zarządzanie włączone k Piątym krokiem jest wybranie wartości poszczególnych zmiennych sterujących.

Zakładamy odtąd, że stan układu jest końcowy kth krok zależy tylko od poprzedniego stanu systemu

i zarządzanie dalej ten krok(ryc. 1). Ta właściwość nazywa się żadnych następstw. Oznaczmy tę zależność jako , (1.1)

Nazywa się równością (1.1). równania stanów. Funkcje

zakładamy, że dane.

Zmienna kontrola U , uzyskamy różne „efektywności” procesu, które będziemy oceniać ilościowo za pomocą funkcji celu Z , w zależności od stanu początkowego systemu

i z wybranej kontrolki U : . (1.2)

Wskaźnik wydajności kth etap procesu kontroli, który zależy od stanu

na początku tego kroku, a sterowanie wybrane na tym etapie będzie oznaczone rozważanym problemem optymalizacja krok po kroku funkcja celu (1.2) musi być addytywna, tj. . (1.3)

Jeżeli właściwość addytywności funkcji celu Z nie jest spełniona, to czasami można to osiągnąć poprzez pewne przekształcenia funkcji. Na przykład, jeśli Z jest funkcją multiplikatywną podaną jako

, to możemy rozważyć funkcję, która jest addytywna.

Zazwyczaj warunki procesu są kontrolowane na każdym etapie

obowiązują pewne ograniczenia. Kontrole spełniające te ograniczenia nazywane są dopuszczalnymi .

Problem optymalizacji krok po kroku można sformułować w następujący sposób: określić zbiór możliwych kontroli