Najprostsze to tak zwane liniowe modele deterministyczne. Podawane są w postaci liniowej zmiennych kontrolnych ( X):

W = za 0 + A 1 X 1 + … + k x k

pod liniowymi ograniczeniami formy

B 1 j x 1 + B 2 j x 2 + … + b kj x k ³ bj , j = 1,…, Q 1 ;

C 1 j x 1 + C 2 j x 2 + … + c kj x k = cj , j = 1,…, Q 2 ;

D 1 j x 1 + D 2 j x 2 + … + d kj x k £ dj , j = 1,…, Q 3 .

Całkowita liczba ograniczeń m = q 1 + Q 2 + Q 3 może przekroczyć liczbę zmiennych (M> k). Ponadto warunek dodatniości zmiennych ( x ja ³ 0).

Powierzchnia odpowiedzi dla modelu liniowego to hiperpłaszczyzna. Rozważmy na przykład liniowy model z dwiema zmiennymi o następującej postaci:

W=–2X 1 –3X 2 (2.2)

z następującymi ograniczeniami

(2.3)

2X 1 + 3X 2 £18;

X 1 – 4X 2 £ 4;

–2X 1 + X 2 £ 2;

X 1 ³ 0; X 2 ³ 0.

Obowiązujący zakres (zakres definicji) OABCD dla modelu (2.2) tworzą więzy (2.3) (rys. 2.2). Powierzchnia odpowiedzi jest płaskim wielokątem OA"B"C"D"(ryc. 2.2, B).

Dla pewnej relacji z ograniczeniami zbiór możliwych rozwiązań może być nieobecny (pusty). Przykład takiego zestawu pokazano na rys. 2.3. Bezpośredni AC I słońce ogranicz zakres dopuszczalnych wartości z góry. Trzecie ograniczenie odcina poniżej od linii prostej obszar wartości dopuszczalnych AB. Zatem nie ma ogólnego obszaru, który spełniałby wszystkie trzy ograniczenia.

Modele liniowe są dość proste, dlatego z jednej strony implikują znaczne uproszczenie problemu, z drugiej zaś pozwalają na opracowanie prostych i efektywnych metod rozwiązania.

W badaniach DLA modele liniowe stosowane są rzadko i prawie wyłącznie w przybliżonym opisie problemów.

Modele liniowe mogą być wykorzystywane do stopniowej aproksymacji modeli nieliniowych (linearyzacja problemu). Ta technika jest szczególnie skuteczna podczas badania małych obszarów badanej przestrzeni. Podstawą jest reprezentacja poszczególnych sekcji nieliniowej powierzchni odpowiedzi za pomocą modelu liniowego duża grupa metody optymalizacyjne, tzw. metody z taktyką liniową.

Badanie modeli liniowych nie jest trudne. W szczególności wpływ każdej ze zmiennych na charakterystykę modelu formy

W = za 0 + A 1 X 1 + A 2 X 2 + …+ k x k

jest określony przez jego współczynniki:

, I = 1,…, k.

Znalezienie optimum modelu liniowego W opt opracował wydajną metodę simplex.

Najprostsze modele kosztów, rozumiane jako zbiór ponoszonych kosztów, sprowadzane są niekiedy do modeli liniowych.

Przykładem takiego modelu jest klasyk model kosztów transportu (problem transportu)(Rysunek 2.4).

Dostępny k punkty produkcyjne
(I = 1,…, k) I M punkty konsumpcyjne
(J = 1,…, M) jakiegoś produktu. Ilość produktu wyprodukowanego w każdym k punkty produkcji, ja; ilość produktu potrzebna w każdym M punkty konsumpcyjne, bj.

Zakłada się równość całkowitej produkcji i konsumpcji:

Ilość transportowanego produktu I-ty punkt produkcji w J-ty punkt zużycia, równy xij; koszt transportu jednostki tego produktu - z ij.

Całkowity koszt transportu Z Podano S model liniowy:

z następującymi ograniczeniami

Modele liniowe obejmują również modele w postaci liniowych równań różniczkowych (pochodne zwyczajne lub cząstkowe).

Liniowe równanie różniczkowe zwyczajne N zamówienie ma postać

Warunki początkowe są zapisane jako

Liniowe równanie różniczkowe cząstkowe ma postać

Model, podany w postaci równania różniczkowego cząstkowego, zawiera warunki początkowe i brzegowe (warunki na granicy dziedziny definicji funkcji F( T)).

2.3. Badanie najprostszego modelu matematycznego
działanie silnika turbiny gazowej

Silnik turbiny gazowej (GTE) jest główną jednostką napędową nowoczesnych samolotów.

Schemat GTE ma postać pokazaną na ryc. 2.5.

Tutaj 1 – dyfuzor wlotowy; 2 - sprężarka; 3 - komora spalania; 4 – turbina;
5 - dysza wylotowa.

Cykl pracy GTE obejmuje następujące etapy:

1) Nadjeżdża z prędkością V przepływ powietrza przez dyfuzor wchodzi do sprężarki.

2) Sprężarka, obracająca się na tym samym wale co turbina, spręża powietrze, które dostaje się do komory spalania.

3) Paliwo (nafta) jest stale wtryskiwane do komory spalania, która jest mieszana ze sprężonym powietrzem.

4) Gaz powstający podczas spalania dostaje się do turbiny, która rozpędza ją do prędkości W.

5) Przy tej prędkości gaz jest wyrzucany przez dyszę do atmosfery.

W związku z faktem, że W > V generowana jest siła pociągowa R, co pozwala samolotowi latać w atmosferze.

Zmiana siły pociągowej odbywa się poprzez zmianę szybkości wtrysku paliwa do komory spalania poprzez przesunięcie gałki sterowania silnikiem (THROT). Ruch przepustnicy do określonego kąta d przepustnicy jest wykonywany ręcznie przez pilota lub za pomocą siłownika zgodnie z sygnałami z ACS w locie. Wzrost wartości ciągu d powoduje wzrost siły R, a spadek to spadek tej siły.

GTE jest złożony układ techniczny, w którym zachodzi znaczna liczba procesów fizycznych i chemicznych. Silnik wyposażony jest we wszelkiego rodzaju urządzenia automatyki, układy obracania i chłodzenia łopatek turbiny itp. Oczywiście dość kłopotliwy będzie również matematyczny opis funkcjonowania silnika turbogazowego, w tym układy równań różniczkowych w pochodnych cząstkowych, równania różniczkowe zwyczajne, funkcje przestępne, algorytmy układ cyfrowy kontrola silnika. Modele takie wykorzystywane są w procesie projektowania silników turbinowych.

Aby rozwiązać problemy sterowania lotem, więcej niż prosty model GTE, czyli zależność siły ciągu R od kąta d odchylenia przepustnicy. Proces zmiany siły ciągu opisuje równanie różniczkowe zwyczajne postaci:

, (2.11)

gdzie t > 0 jest stałą czasową silnika, która zależy m.in cechy konstrukcyjne również od temperatury otoczenia, jego wilgotności i innych czynników zewnętrznych; k[kg/deg] – współczynnik proporcjonalności.

Warunek początkowy dla równania (2.11) jest zapisany jako

R(0) = R 0 . (2.12)

Zatem równanie (2.11) wraz z warunkiem początkowym (2.12) jest najprostszy model matematyczny silnika turbogazowego, zapisany w postaci równania różniczkowego zwyczajnego 1-te zamówienie.

Aby określić współczynnik proporcjonalności k posłużono się krzywymi kalibracyjnymi zależności ciągu od kąta obrotu przepustnic, zbudowanymi na podstawie danych eksperymentalnych. Tangens nachylenia wykresu jest równy żądanemu współczynnikowi.

Całkowanie równania (2.11) z warunkiem początkowym (2.12) pozwala dowiedzieć się, jak zmienia się siła ciągu w czasie (rys. 2.6).

Gdy przepustnica jest odchylona, ​​ciąg R wzrasta, a następnie stabilizuje się na pewnym poziomie granicznym, tj. GTE jest obiektem inercyjnym.

Granica ciągu z (2.11) otrzymujemy, gdy tempo jego zmian jest równe zeru:

. (2.13)

Czas narastania zależy od wartości stałej czasowej silnika t. Proces uważa się za stabilny, gdy t = t usta, gdy ciąg wchodzi w tzw. pięcioprocentowy korytarz wartości granicznej siły ciągu (ryc. 2.6). Im większy t, tym bardziej bezwładność silnika, a co za tym idzie, tym więcej T usta

na ryc. Na rys. 2.7 przedstawiono zachowanie się siły ciągu w zależności od kąta wychylenia przepustnicy przy t = 0,5.

Siła ciągu podczas startu, gdy przepustnica jest wychylona o 10°, osiąga stan ustalony w trzeciej sekundzie i osiąga wartość 3390 kg. Dziesięć sekund po starcie, gdy przepustnica jest wychylona o 20°, siła ciągu wynosi 6780 kg, a kolejne dziesięć sekund później, gdy przepustnica jest wychylona o 30°, siła ciągu wynosi 10170 kg. Graniczna wartość siły pociągowej wynosi
14270 kg.

Podobne informacje.

3.1. Zadanie ogólne Programowanie liniowe

Programowanie liniowe- jest to najbardziej rozwinięta sekcja programowania matematycznego, za pomocą której przeprowadza się analizę i rozwiązywanie problemów ekstremalnych z liniowymi powiązaniami i ograniczeniami.

Programowanie liniowe obejmuje szereg heurystycznych (przybliżonych) metod rozwiązania, które pozwalają, w danych warunkach, ze wszystkich opcje rozwiązania problemów produkcyjnych, aby wybrać najlepsze, optymalne. Metody te obejmują następujące metody - graficzną, simpleksową, potencjalną (zmodyfikowaną metodę dystrybucji - MOD), Khichkova, Kreko, aproksymacyjną metodę Vogla i inne.

Niektóre z tych metod łączy wspólna nazwa - metoda dystrybucji lub transportu.

Miejscem narodzin programowania liniowego jest Rosja. Pierwsze prace nad programowaniem liniowym przyszłego akademika L.V. Kantorowicza zostały opublikowane w 1939 roku. W 1975 roku otrzymał Nagrodę Nobla w dziedzinie ekonomii za opracowanie metod programowania liniowego. Ponieważ większość prac akademika L.V. Kantorowicza poświęca się rozwiązywaniu problemów transportowych, można uznać, że wspomniana Nagroda Nobla to także zasługa rosyjskiej nauki o transporcie.

W transporcie drogowym metody programowania liniowego są stosowane od lat 60. XX wieku do rozwiązywania wielu najważniejszych problemów produkcyjnych, a mianowicie: skracania odległości przewozu ładunków; opracowanie optymalnego schematu transportu; wybór najkrótszych tras ruchu; zadania transportu różnych, ale wymiennych ładunków; planowanie dnia zmianowego; planowanie transportu ładunków małoseryjnych; dystrybucja autobusów wzdłuż tras i inne.

Cechy modelu programowania liniowego są następujące:

Wyrażono funkcję celu i ograniczenia zależności liniowe(równości lub nierówności);

Liczba zależności jest zawsze mniejsza niż liczba niewiadomych (warunek niepewności);

Nieujemność wymaganych zmiennych. Ogólna forma zapisu modelu programowania liniowego w skróconej formie jest następująca:

Znajdować X ij ≥ 0 (j = 1, 2…n) przy następujących rodzajach ograniczeń:

Te ograniczenia minimalizują (lub maksymalizują) funkcję celu

Standardową formą pisania modelu programowania liniowego jest zapisywany układ równań liniowych kanoniczny postaci, tj. w postaci równości liniowych, w liczbach nieujemnych:

za 11 x 1 + za 12 x 2 + ... + za 1 n x n \u003d b 1;

za 21 x 1 + za 22 x 2 + ... + za 2 n x n \u003d b 2 ; (3.1)

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

za m x 1 + za m 2 x 2 + ...+ za mn x n = b m ..

Jeżeli model jest zapisany w postaci nierówności w liczbach nieujemnych, czyli ma postać

za 11 x 1 + za 12 x 2 + ... + za 1 n x n ≤ b 1;

za 21 x 1 + za 22 x 2 + ... + za 2 n x n ≤ b 2 ; (3.2)

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

za m x 1 + za m 2 x 2 + …+ za mn x n ≤ b m ,..

następnie ten wpis jest zredukowany do kanoniczny postaci (3.1) wprowadzając dodatkowe zmienne x n +1> 0 (I=1,2…M) na lewą stronę nierówności (lub zmniejszenie liczby zmiennych, jeśli znak nierówności jest skierowany w przeciwnym kierunku). Podstawą są dodatkowe zmienne.

Standardową formą rozwiązywania problemu programowania liniowego jest znalezienie rozwiązań układu równań liniowych w liczbach nieujemnych, które minimalizują funkcję celu. Funkcja celu ma wtedy postać

L = do 1 x 1 + do 2 x 2 ... do n x n → min, (3,3)

Gdzie s 1 , s 2 … s n są współczynnikami funkcji celu Ł ze zmiennymi X J .

Dodatkowe zmienne wchodzą do funkcji celu z zerowymi współczynnikami.

W przypadku maksymalizacji funkcji celu Ł należy odwrócić znaki zmiennych funkcji celu i ponownie dojdziemy do problemu minimalizacji, tj. jedno zadanie zostaje zredukowane do innego zastępstwa Ł NA - Ł lub maks Ł=min(- Ł).

Podstawowym rozwiązaniem układu równań liniowych (3.1) jest rozwiązanie, w którym zmiennym niepodstawowym podane są wartości zerowe.

Rozwiązanie podstawowe nazywamy dopuszczalnym, w którym zmienne zawarte w podstawie są nieujemne.

Dopuszczalne rozwiązanie, które maksymalizuje (lub minimalizuje) funkcję celu (3.3) nazywamy optymalnym.

Każdemu problemowi programowania liniowego odpowiada inny problem, zwany problemem dualnego programowania liniowego. Pierwotny problem w odniesieniu do dualnego nazywa się problemem bezpośrednim. Problemy pierwotne i dualne tworzą parę, zwaną parą podwójną w programowaniu liniowym. Para pierwotna i podwójna tworzą parę asymetryczną, gdy problem pierwotny jest zapisany w postaci kanonicznej, a parę symetryczną, gdy warunki problemów są zapisane jako nierówności.

Zasady tworzenia modelu matematycznego problemu dualnego oparte są na zasadach rachunku macierzowego.

Pojęcie dualności jest szeroko stosowane w analizie problemów programowania liniowego. Właściwość dwoistości jest szczegółowo rozważana w każdym konkretnym przypadku.

3.2. Metoda grafowo-analityczna

Metoda grafowo-analityczna jest jedną z najprostszych metod programowania liniowego. Wyraźnie ujawnia istotę programowania liniowego, jego geometryczną interpretację. Jej wadą jest to, że pozwala rozwiązywać problemy z 2 lub 3 niewiadomymi, czyli ma zastosowanie do wąskiego zakresu problemów. Metoda opiera się na zasadach geometrii analitycznej.

Rozwiązywanie problemu z dwiema zmiennymi x 1 I x2, która zgodnie ze znaczeniem problemu nie powinna być ujemna, przeprowadzana jest w układzie współrzędnych kartezjańskich. równania x 1=0 i x2= 0 to osie układu współrzędnych pierwszej ćwiartki

Rozważmy metodę rozwiązania na konkretnym przykładzie.

Przykład 3.1. W magazynie znajduje się 300 ton wyrobów z pianobetonu i 200 ton wyrobów stalowych. Przedsiębiorstwo motoryzacyjne musi dostarczyć te produkty do budowanego obiektu. Firma samochodowa posiada ciężarówki KAMAZ - 5320 i

ZIŁ-4314. Na jedną podróż KamAZ-5320 może dostarczyć 6 ton pianobetonu i 2 tony stali, a zysk z podróży wyniesie 4 tysiące rubli. ZIL-4314 dostarcza 2 tony pianobetonu i 4 tony stali podczas jednej podróży, zysk z podróży to 6 tysięcy rubli. Konieczne jest zorganizowanie transportu w taki sposób, aby zapewnić przedsiębiorstwu samochodowemu jak największy zysk.

Skonstruujmy matematyczny model problemu. Oznacz przez x 1 żądaną liczbę podróży KamAZ-5320 i przez X 2 wymagana liczba jeźdźców ZiŁ-4314.

Całkowity transport w tonach produktów z pianobetonu wynosi 6 x 1+ 2x2 i ze stali 2 x 1+ 4x2. Limit wysyłki, oparty na liczbie dostępnych przedmiotów, wynosi 6 x 1+ 2x 2 ≤ 300t dla pianobetonu i 2 x 1+ 4x 2 ≤ 200t dla stali.

Całkowity zysk w tysiącach rubli. wyrażone jako 4 X 1 + 6X 2 , który należy zmaksymalizować i który jest kryterium optymalności w rozpatrywanym problemie. Model matematyczny problemu wygląda zatem następująco. Konieczna jest maksymalizacja funkcji celu

Ł = 4x 1+ 6x 2 → maks. w warunkach: 6 x 1+ 2x 2 ≤ 300; 2x 1+ 4x 2 ≤ 200; x 1 ≥ 0;x 2 ≥ 0.

Rozważ równanie 6 x 1+ 2x 2 = 300. Aby skonstruować prostą opisaną tym równaniem, znajdujemy dwa punkty leżące na tej prostej. Na x 1= 0 z równania prostej znajdujemy 2 x 2 = 300, skąd x 2 \u003d 150. Dlatego punkt A o współrzędnych (0,150) leży na żądanej linii. Na x2= 0 mamy 6 x 1\u003d 300, skąd x 1 \u003d 50, a punkt D o współrzędnych (50,0) również znajduje się na żądanej linii. Narysuj linię przechodzącą przez te dwa punkty OGŁOSZENIE(Rys. 3.1).

Nierówność liniowa 6 x 1+ 2x 2 ≤ 300 to półpłaszczyzna znajdująca się po jednej stronie konstruowanej linii 6 x 1+ 2x 2 = 300. Aby dowiedzieć się, po której stronie tej prostej znajdują się punkty pożądanej półpłaszczyzny, podstawiamy do nierówności 6 x 1+ 2x 2 ≤ 300 współrzędnych jakiegoś punktu nie leżącego na linii granicznej. Na przykład początek to 0-(0,0). Spełnia nierówność 6∙0 + 2∙0 = 0< 300. Это значит, что начало координат лежит в области допустимых значений, которая находится слева от прямой OGŁOSZENIE i na ryc. 3.1 jest zacieniony.

Równanie 2 x 1+ 4x2= 200 zostanie zbudowanych z dwóch punktów. Na x 1 = 0 4x 2 = 200 skąd x 2 = 50. Następnie wskaż mi ma współrzędne (0,50) i należy do wymaganej linii. Na x2= 0, 2x 2 = 200 kropek Z leży na podanej linii o współrzędnych (100,0). Podstawiając pod nierówność współrzędne punktu Z(0,0), otrzymujemy 2∙0 + 4∙0 = 0< 200. Значит, начало координат находится в области допустимых значений от прямой 2x 1+ 4x2= 200.

System ograniczeń zadań wymaga, aby plany ( x 1; x2) spełniają wszystkie cztery nierówności, tj. dopuszczalne układy to punkty ( x 1; x2) musi być jednocześnie we wszystkich czterech półpłaszczyznach. Wymóg ten spełniają tylko punkty znajdujące się wewnątrz i na granicy wielokąta. OKD, czyli wielokąt dopuszczalnych rozwiązań.

Punktami są wierzchołki wielokąta możliwych rozwiązań O, E, K, D Segmenty linii OE, EK, KD, OD- jego żebra. Dowolny punkt wielokąta OKD jest planem zadania, spełniającym wszystkie jego warunki. Wierzchołki wielokąta są utworzone przez przecięcie dwóch prostych i odpowiadają podstawowym planom problemu, wśród których znajduje się najlepszy (optymalny) plan. Zatem planów odniesienia będzie tyle, ile jest wierzchołków wielokąta rozwiązań dopuszczalnych.

Dla funkcji celu można również uzyskać wizualną reprezentację geometryczną Ł = 4x 1+ 6x2. Na przykład ustalamy jakąś wartość funkcji celu Ł= 120. równanie 4 x 1+ 6x 2 = 120 definiuje linię przechodzącą przez punkt W ze współrzędnymi (x 1 \u003d 0; x 2 \u003d 20) i punktem Ł ze współrzędnymi (( X 1 = 30; X 2 = 0). Odcinek BL leży wewnątrz wielokąta OKD. Dlatego dla wszystkich planów (punktów) tego odcinka wartość funkcji celu jest taka sama i równa 120. Podając inne wartości funkcji celu otrzymujemy linie równoległe, które nazywane są linie poziome funkcja celu.

Przesuwanie linii Ł równolegle do siebie w jednym kierunku, otrzymujemy wzrost funkcji celu, aw przeciwnym kierunku - jej spadek. W tym przykładzie ruch po linii prostej BL w prawo określa wzrost funkcji celu, którą maksymalizujemy. Robimy to do linii BL będzie miał co najmniej jeden punkt wspólny z wielokątem dopuszczalnych rozwiązań OKD. z ryc. 3.1 wynika, że ​​ostatnim punktem przecięcia prostej poziomu funkcji celu będzie punkt DO. Oznacza to, że punkt DO ustala optymalny plan zadań.

Nazywa się kierunek wzrostu prostopadły do ​​linii poziomu kierunek największego wzrostu funkcji celu i wyznacza jej maksymalne wzmocnienie. Kierunek ten można ustawić bez rysowania linii poziomu. W tym celu jest to konieczne na osiach x 1 I x2 odłóż odcinki równe współczynnikom funkcji celu i korzystając z nich, jak ze współrzędnych, skonstruuj wektor o największym wzroście funkcji celu. W matematyce to się nazywa gradient i oznaczony znakiem grad. Gradient dla funkcji Ł = 4x1 + 6x2 wektor woli N| 4; 6 | . Dla wygody jego konstrukcji zwiększamy współrzędne np. o 10 razy, tj. n | 40; 60 | . Skonstruujmy gradient funkcji celu Ł, dla którego łączymy punkt o współrzędnych (40; 60) z początkiem układu współrzędnych. Linie poziomu funkcji celu są rysowane prostopadle do kierunku gradientu.

Tak więc, w taki czy inny sposób, ustalono, że punkt DO ustala optymalny plan zadania, którego wartości zmiennych odpowiadają współrzędnym danego punktu. Aby ustalić współrzędne, należy rozwiązać układ równań prostych tworzących ten wierzchołek:

6x 1+ 2x2= 300;

2x 1+ 4x2= 200.

Wyrównujemy współczynniki przy x 1, mnożąc drugie równanie przez 3 i odejmujemy pierwsze od drugiego równania. Weźmy 10 x2= 300,x 2 = 30. Podstawiając wartość x 2 \u003d 30 do dowolnego z równań, na przykład do pierwszego, określamy wartość X 1:

6x 1+ 2X · 30 = 300,

skąd 6 x 1 = 300 - 60 = 240 zatem, x 1 = 40.

Tak więc, aby uzyskać jak największy zysk dla firmy samochodowej, konieczne jest odbycie 40 podróży do KamAZ-5320 i 30 podróży do ZIL-4314. Maksymalny zysk w tym przypadku będzie

Ł = 4x 1+ 6x2\u003d 4 40 + 6 30 \u003d 340 tysięcy rubli.

Na podstawie rozważanego przykładu i geometrycznej interpretacji problemu optymalizacyjnego z dwiema zmiennymi możemy wyciągnąć następujące wnioski:

1) w przestrzeni dwuwymiarowej obszarem możliwych rozwiązań jest wielokąt;

2) każdy bok wielokąta odpowiada wartości jednej zmiennej równej zeru;

3) każdy wierzchołek wielokąta dopuszczalnych rozwiązań odpowiada wartościom dwóch zmiennych równych zeru;

4) każdej wartości funkcji celu odpowiada prosta;

5) optymalnemu rozwiązaniu problemu odpowiada wierzchołek wielokąta, w którym funkcja celu przyjmuje wartość optymalną, natomiast zmiennymi optymalnymi są współrzędne tego wierzchołka.

W ogólnym przypadku problemy optymalizacyjne mają podobną interpretację geometryczną. Zbiorem planów zadań będzie wielościan, którego wierzchołki odpowiadają planom odniesienia. Podczas rozwiązywania problemu przejście z jednego wierzchołka wielościanu do drugiego o dużej wartości funkcji celu odbywa się aż do uzyskania jego optymalnej wartości. Należy zauważyć, że skuteczność metod optymalizacyjnych polega właśnie na tym, że wyliczanie wierzchołków (iteracja) odbywa się tylko w kierunku największego wzrostu funkcji celu. Dlatego nie bierze się pod uwagę wszystkich wierzchołków, których jest ogromna liczba, ale tylko te, które są bliższe skrajności.

Określając klasę problemów optymalizacyjnych i wybierając metodę ich rozwiązania, należy wiedzieć, czy zbiór dopuszczalnych rozwiązań jest wypukłym czy niewypukłym, liniową czy nieliniową funkcją celu.

Z definicji zestaw nazywa się wypukły jeśli dla dowolnych dwóch punktów cały odcinek łączący te punkty należy do tego zbioru. Przykładami zestawów wypukłych są na przykład odcinek (ryc. 3.2, a), płaszczyzna w kształcie koła, sześcianu, równoległościanu, a także wielokąty, które są całkowicie umieszczone po jednej stronie każdego z jego boków itp.

na ryc. 3.2b pokazuje zbiory niewypukłe. W zbiorach niewypukłych można wskazać co najmniej dwa punkty odcinka AB, które nie należą do rozpatrywanego zbioru.

3.3. Metoda simpleksowa

Metoda simpleksowa jest powszechną metodą rozwiązywania problemów programowania liniowego. Metoda ma swoją nazwę od słowa „simplex”, oznaczającego najprostszy wypukły wielokąt, którego liczba wierzchołków jest zawsze o jeden większa niż wymiar przestrzeni. Metoda simplex została opracowana w USA przez matematyka J. Dantziga pod koniec lat 40. XX wieku.

Metoda simplex obejmuje otrzymanie nieujemnego rozwiązania podstawowego układu kanonicznych równań liniowych typu (3.1), następnie minimalizację (maksymalizację) funkcji celu (3.3) i w ten sposób znalezienie optymalnych wartości wymagane zmienne x 1, x 2… x n.

Idea metody simplex polega na tym, że w trakcie obliczeń kolejno przechodzi się od pierwszego podstawowego rozwiązania do drugiego, trzeciego itd. przez tzw simpleks transformacje. Przekształcenia wykonywane są w formie tablic simplex, co znacznie upraszcza i przyspiesza obliczenia.

Aby otrzymać nieujemne podstawowe rozwiązania układu równań liniowych, należy przeprowadzić proces eliminacji niewiadomych w taki sposób, aby wyrazy swobodne równań pozostały nieujemne na wszystkich etapach procesu. W tym przypadku należy kierować się następującą zasadą: za nową zmienną podstawową przyjmuje się każdą zmienną wolną, dla której występuje co najmniej jeden dodatni współczynnik; z bazy wyprowadza się zmienną, która odpowiada najmniejszemu stosunkowi wyrazów wolnych równań do odpowiednich dodatnich współczynników równań ze zmienną wprowadzoną do bazy. Takie przekształcenia to tzw konwertery simpleksowe.

Jest to bardzo ważne, ponieważ aby znaleźć konkretne rozwiązanie nieujemne, które odpowiada największej możliwej wartości jednej zmiennej wolnej przy zerowych wartościach innych zmiennych wolnych, zamiast określać zakres określonej zmiennej i zastępować jej największą możliwą wartość do wspólna decyzja wystarczy przyjąć tę zmienną jako podstawową i poddać układ przekształceniu simplex, przechodząc do nowej bazy, co znacznie upraszcza obliczenia.

Obliczenia są wygodnie wykonywane przy użyciu tabel simplex. Przejście z jednej tabeli do drugiej odpowiada jednej iteracji, czyli przejściu z jednej bazy do drugiej, przy czym wartość funkcji celu maleje. Przez określoną liczbę iteracji przechodzą one do bazy, dla której uzyskuje się optymalną (minimalną lub maksymalną) wartość funkcji celu. Rozważmy metodę simplex w postaci ogólnej.

Ogólnym zadaniem programowania liniowego jest minimalizacja (maksymalizacja) funkcji celu, której zmienne są połączone układem równań liniowych, z zastrzeżeniem warunku nieujemności.

Niech konieczne będzie zminimalizowanie postaci liniowej

Ł = do 1 x 1 + do 2 x 2 + ... do n x n.

W następujących warunkach (dla przejrzystości w równaniach zachowane są współczynniki zerowe i jednostkowe):

1x 1+ 0x 2 + ... 0x m + za 1m+ 1x m+1 ... + za 1n x n \u003d b 1;

0x 1+ 1x 2+… 0x m + za 2m+ 1x m+1 ... + za 2n x n \u003d b 2;

……………………………………………

0x 1+ 0x 2 + ... 1x m + a mm + 1x m +1 ... + a mn x n \u003d b m.

Ten układ równań ma już gotową podstawę, ponieważ każde równanie z ograniczeniami zawiera niewiadomą o współczynniku równym jeden, którego nie ma w innych równaniach, tj. Ze współczynników zmiennych X 1 , X 2 …, x m możesz utworzyć macierz tożsamości.

Rozwiążmy równania dla podstawowych zmiennych:

x 1 \u003d b 1 - (za 1m + 1 x m + 1 ... + za 1n x n);

x 2 \u003d b 2 - (za 2m + 1 x m + 1 ... + za 2n x n);

………………………………

x m \u003d b m - (a mm + 1x m + 1 ... + a mn x n),

a funkcję celu wyrazimy za pomocą zmiennych wolnych, podstawiając w miejsce zmiennych podstawowych ich wyrażenia wyrażone za pomocą zmiennych wolnych:

L=c 1 b 1 +c 2 b 2 +c m b m –(c 1 a 1m +c 2 a 2m+1 +…+c m a mn+1)x m+1 -…-(c 1 a 1n +c 2 a 2n +…+c m a mn)x n …+c n x n..

Zmienne x 1, x 2 ..., x m, za pomocą których znajduje się pierwszy podstawowy plan, są podstawowe, a reszta x m +1 , x m +2 ,…x n – bezpłatny. Zawsze powinno być tyle zmiennych podstawowych, ile jest równań w układzie. Na podstawie warunku nieujemności najmniejsza wartość wolnych zmiennych jest równa zeru. Otrzymane podstawowe rozwiązanie układu równań jest jego początkowym możliwym rozwiązaniem, tj. x 1 \u003d b 1, x 2 \u003d b 2, ... x m \u003d b m, x m +1 \u003d 0,…, x n = 0.

Rozwiązanie to odpowiada wartości funkcji celu

Ł = do 1 b 1 + do 2 b 2 + ... do m b m.

Początkowe rozwiązanie jest sprawdzane pod kątem optymalności. Jeśli nie jest optymalna, to wprowadzając do bazy zmienne wolne, uzyskuje się następujące możliwe rozwiązania z mniejszą wartością funkcji celu. W tym celu określa się zmienną wolną, którą należy wprowadzić do bazy, a także zmienną, którą należy usunąć z bazy. Następnie przechodzą z poprzedniego systemu do następnego równoważnego systemu. Odbywa się to za pomocą tablic simplex. Rozwiązanie problemu trwa do uzyskania optymalnej wartości funkcji celu.

Tabele simplex są kompilowane w następujący sposób (patrz Tabela 3.1). Umieść wszystkie zmienne na górze tabeli X 1 , X 2 …, x rz i współczynniki cj, z którym odpowiednie zmienne są zawarte w funkcji celu. Pierwsza kolumna c ja składa się ze współczynnika funkcji celu dla zmiennych zawartych w podstawie. Następnie następuje kolumna podstawowych zmiennych i wyrazów wolnych równań. Elementami pozostałych kolumn tabeli są współczynniki zmiennych, z którymi te ostatnie wchodzą do układu równań. Zatem każdy wiersz tabeli odpowiada równaniu układu, rozwiązanemu względem zmiennej podstawowej. W tabeli przedstawiono również wariant planu odpowiadający funkcji celu dla danej podstawy.

Dolny rząd tabeli nazywa się indeks. Każdy z jego elementów (oszacowanie) ∆ J określić

∆jot = z jot – do jot ,

Gdzie cj są współczynnikami odpowiednich zmiennych w funkcji celu; zj – suma iloczynów współczynników funkcji celu ze zmiennymi podstawowymi i odpowiadającymi im zmiennymi - elementami J-ta kolumna tabeli.

Tabela 3.1

Tablica simplex z początkową poprawnością

1.

2. wskazówki użytkowania maty. modele w gospodarce.

Modele matematyczne pozwalają na wyznaczenie optymalnych wartości nieznanych parametrów systemy gospodarcze co jest istotne w procesie podejmowania decyzji. Programowanie matematyczne zapewnia po prostu aparat, który pozwala zoptymalizować proces selekcji najlepsze opcje plany w procesie zarządzania w systemach gospodarczych.

Stosowane w statystyce matematycznej, metody optymalizacyjne, metody ekonomiczne. cybernetyka, problemy eksperymentalne.

Podczas badania złożonych procesów i zjawisk w gospodarce często stosuje się modelowanie - dobrze zdefiniowane konkretne przedstawienie rozważanych cech badanego obiektu. Jej istota polega na tym, że badane zjawisko jest odtwarzane w warunkach eksperymentalnych z wykorzystaniem modelu w innej skali czasowej i przestrzennej. Model to specjalnie stworzony obiekt, za pomocą którego odtwarza się pewne cechy badanego systemu w celu jego zbadania. Modelowanie matematyczne jest najdoskonalszą i zarazem najskuteczniejszą metodą pozyskiwania informacji o badanym obiekcie. Jest to potężne narzędzie do analizy w ekonomii. Wyniki badań z wykorzystaniem modeli będą miały znaczenie praktyczne, gdy skonstruowany model będzie wystarczająco adekwatny do rozpatrywanego zjawiska, tj. wystarczająco dobrze, aby odzwierciedlić rzeczywistą sytuację.

2. programowanie matematyczne jako nauka, jego struktura. Problemy z optymalizacją. Trudności w stosowaniu klasycznych metod optymalizacyjnych w rozwiązywaniu problemów ekonomicznych.

Programowanie matematyczne jest gałęzią matematyki stosowanej, która się rozwija podstawy teoretyczne i metody rozwiązywania ekstremalnych problemów.

Programowanie matematyczne obejmuje kilka sekcji, z których główne to:

1. Programowanie liniowe. W tej części znajdują się problemy, w których nieznane zmienne są zawarte w związkach matematycznych pierwszego stopnia.

2. Programowanie nieliniowe. Ta sekcja zawiera problemy, w których funkcja celu i (lub) ograniczenia mogą być nieliniowe.

3. Programowanie dynamiczne. Ta sekcja zawiera zadania, w których proces rozwiązania można podzielić na osobne etapy.

4. Programowanie całkowite. Ta sekcja zawiera zadania, w których nieznane zmienne mogą przyjmować tylko wartości całkowite.

5. Programowanie stochastyczne. Ta sekcja zawiera zadania, które zawierają zmienne losowe w funkcji celu lub ograniczeniach.

6. Programowanie parametryczne. Ta sekcja zawiera problemy, w których współczynniki nieznanych zmiennych w funkcji celu lub ograniczeniach zależą od niektórych parametrów.

Aby rozwiązać problemy programowania matematycznego, trudno jest zastosować klasyczne metody znajdowania ekstremum, ponieważ w problemach programowania matematycznego funkcja celu osiąga swoją wartość ekstremalną na granicy obszaru dopuszczalnych wartości nieznanych zmiennych, a pochodne nie istnieją w punktach granicznych. Pełne wyliczenie punktów dopuszczalnych jest niemożliwe ze względu na ich znaczącą liczbę.

3. Pojęcie modelu matematycznego, rodzaje mat. modele

Model matematyczny jest abstrakcją rzeczywistego zjawiska lub procesu zapisaną w matematycznych symbolach i wyrażeniach. Modele matematyczne procesy gospodarcze a zjawiska nazywane są modelami ekonomicznymi i matematycznymi

Modele dzielą się na:

1. liniowy, w którym wszystkie zależności są opisane relacjami liniowymi,

2. nieliniowy, w których występują relacje nieliniowe;

3. stochastyczny, które uwzględniają losowy charakter badanych procesów,

4. deterministyczny, które uwzględniają średnie wartości wszystkich parametrów.

5. dynamiczny modele, w których badane systemy rozpatrywane są w fazie rozwoju na przestrzeni kilku okresów,

6. statyczny gdzie czynnik czasu nie jest brany pod uwagę.

7. optymalizacja modele, w których wybór dokonywany jest w zależności od ekstremalizacja jakieś kryterium,

8. brak optymalizacji, w którym nie ma kryterium optymalności.

9. makromodele(dla całego gospodarstwa domowego)

10. mikromodele(poszczególne ogniwa lub procesy gospodarki).

Rodzaje modeli matematycznych: liniowy, nieliniowy, kwadratowy, całkowity, dyskretny, parametryczny, liniowy ułamkowy, dynamiczny, stochastyczny

4. Ogólne zestawienie problemów programowania matematycznego.

Rozważmy ogólne sformułowanie problemu programowania matematycznego.

Ogólnym problemem programowania matematycznego jest wyznaczenie optymalnej wartości funkcji celu, a wartości zmiennych muszą należeć do pewnego przedziału wartości dopuszczalnych. Matematycznie definicja rozwiązania optymalnego wyraża się znalezieniem ekstremum (max lub min) funkcji wielu zmiennych

Z = f(x1, x2, …, xn)

w zadanym przedziale zmian tych zmiennych

gi (x1, x2,…, xn) Ribi (i = 1, 2,…, m),

gdzie Ri jest jednym ze znaków ≥, =, ≤.

5. Problem optymalizacji planu produkcji. Ekonomiczne sformułowanie i konstrukcja matematycznego modelu problemów.

Otoczenie ekonomiczne:

Firma produkuje N rodzaje używanych produktów M rodzaje surowców. Do wytworzenia jednostki produkcji wykorzystuje się ściśle określoną ilość surowców tego czy innego rodzaju. Surowce każdego rodzaju w przedsiębiorstwie są ograniczone. Przedsiębiorstwo uzyskuje określony zysk ze sprzedaży jednostki produkcji. Konieczne jest znalezienie takiego planu produkcji, w którym przedsiębiorstwo uzyska maksymalny łączny zysk.

Ustawienie matematyczne:

Niech j będzie indeksem typu produktu j = 1, n

i - indeks typu zasobu i = 1, m

oraz ij to koszty surowców I-ty typ do produkcji jednostki produkcji J-ty typ;

Ai jest zadaną granicą dostępnej wielkości zasobów i-tego typu;

Pj - zysk uzyskany ze sprzedaży jednostki produkcji j-tego rodzaju;

xj to wielkość produkcji j-tego typu.

z \u003d P1x 1 + P2x 2 + ... + Pnx n → maks

a11x 1 + a12x 2 +…+ a1nx n ≤ A1

a21x 1 + a22x 2 +…+ a2nx n ≤ A2

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

a m1x1 + a m2x2 +…+ a m n x n ≤ Am

xj ≥ 0, j = 1, n

6. Zadanie diety. Ekonomiczne sformułowanie i konstrukcja modelu matematycznego problemu.

Otoczenie ekonomiczne

Niektóre gospodarstwa dokarmiają zwierzęta. Stosowany do tuczu N rodzaje paszy. Zawartość składników odżywczych (wapnia, fosforu itp.) jest znana na jednostkę paszy każdego gatunku. Dla prawidłowego żywienia zwierząt konieczne jest spożywanie składników pokarmowych w ilościach nie mniejszych niż podane. Koszt jednostkowy każdej paszy jest znany. Konieczne jest ustalenie diety żywienia zwierząt, w której całkowity koszt tuczu będzie minimalny.

Ustawienie matematyczne:

j to indeks rodzaju paszy, j = 1, n

i – indeks rodzaju składników pokarmowych, i = 1, m

Ai to wymagane dzienne spożycie i-tego rodzaju składnika odżywczego;

Сj to koszt jednostki paszy typu j.

Wprowadźmy nieznane zmienne:

хj - dzienna objętość karmienia zwierząt j-ty widok rufa.

W zakresie wprowadzonej notacji dane zadanie zostanie napisane dalej

a11x1 + a12x2 +…+ a1nxn ≥ A1

a21x1 + a22x2 +…+ a2nxn ≥ A2

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

am1x1 + am2x2 +…+ i mnxn ≥am

xj ≥ 0, j = 1, n

7. Zadanie transportowe . Ekonomiczne sformułowanie i konstrukcja modelu matematycznego problemu.

Otoczenie ekonomiczne :

Dostępny M dostawcy produktów jednorodnych i N konsumentów tego produktu. Znane koszty jednostkowe dostawy jednostki produkcji od każdego dostawcy do każdego konsumenta. Zapasy dostawców są ograniczone. Znane są również potrzeby dotyczące produktów każdego konsumenta.

Konieczne jest ustalenie takiego planu transportu produktów od dostawców do konsumentów, w którym całkowity koszt transportu będzie minimalny.

Ustawienie matematyczne :

Wprowadźmy notację ustawić parametry:

j – wskaźnik konsumenta, j = 1, n

i – indeks dostawcy, i = 1, m

Ai to ilość produktów dostępnych u i-tego dostawcy;

Bj - wielkość popytu na produkty j-tego konsumenta;

Cij to jednostkowy koszt transportu jednostki produktu od i-tego dostawcy do j-tego konsumenta.

Wprowadźmy nieznane zmienne:

хij to wielkość transportu produktów od i-tego dostawcy do j-tego konsumenta.

z = С11x11 + С12x12 +…+С1nx1n + С21x21 +…+ Сm(n -1)xm (n-1) + Сmnxmn → min

Ograniczenia zadań.

I. Od każdego dostawcy możesz odebrać produkty w ilości nie większej niż dostępna:

x11 + x12 +…+ x1n ≤ A1

x21 + x22 +…+ x2n ≤ A2 (2)

…………………….

xm1 + xm2 +…+ xmn ≤ Am

II. Potrzeba każdego konsumenta na produkty musi być zaspokojona

x11 + x21 +…+ xm1 ≥B1

x12 + x22 +…+ xm2 ≥B2

……………………. (3)

x1n + x2n +…+ xmn ≥Bn

III. Warunek nieujemny: xij ≥0, i = 1, m ; j = 1, n

Często wygodnie jest napisać instrukcję matematyczną w złożonej formie:

, ja = 1, m , j = 1, n

8. Problem wyboru zadań lub zadań. Ekonomiczne sformułowanie i konstrukcja modelu matematycznego problemu.

Otoczenie ekonomiczne :

Dostępny N rodzaje pracy i N wykonawcy. Każdy z wykonawców może wykonać dowolną, ale tylko jedną pracę. Koszt wykonania każdej pracy przez każdego wykonawcę jest ustalony. Konieczne jest przydzielanie wykonawców do pracy w taki sposób, aby całkowity koszt wykonania pracy był minimalny.

Ustawienie matematyczne .

Wprowadźmy oznaczenie dla podanych parametrów.

i – indeks prac, i = 1, m

j to indeks wykonawców, j = 1, n

Cij to koszt wykonania i-tego zlecenia przez j-tego wykonawcę.

Wprowadźmy nieznane zmienne. W tym problemie nieznane zmienne mogą przyjmować tylko dwie wartości, 0 lub 1. Takie zmienne nazywane są zmiennymi pustymi.

1 - jeżeli j-ty wykonawca jest przypisany do i-tej pracy;

0 - inaczej.

W odniesieniu do wprowadzonej notacji problem ten można zapisać w następujący sposób:

z = С11x11 + С12x12 +…+С1nx1n + С21x21 …+ С(n-1)(n-1)x(n-1)(n-1) + Сnnxnn → min

I grupa ograniczeń.

Do każdego utworu należy przypisać tylko jednego wykonawcę:

x11 + x12 +…+ x1n = 1

x21 + x22 +…+ x2n = 1

……………………..

xn1 + xn2 +…+ xnn = 1

II. grupa restrykcyjna.

Każdy wykonawca może wykonać tylko jedno zadanie:

x11 + x21 +…+ xn1 = 1

x12 + x22 +…+ xn2 = 1

……………………..

x1n + x2n +…+ xnn = 1

x ja = ( 0,1) ja = 1, n ; j = 1, n

9. Problem cięcia materiałów. Ekonomiczne sformułowanie i konstrukcja modelu matematycznego problemu.

Otoczenie ekonomiczne .

Surowiec tej samej wielkości jest dostarczany do cięcia. Wymagane jest pocięcie go na półfabrykaty o danym rozmiarze w określonej ilości, tak aby całkowity odpad był minimalny.

Ustawienie matematyczne .

Wprowadźmy notację:

i jest indeksem spacji,

Ai - wymagana liczba półfabrykatów i-tego typu;

j - indeks opcji skrawania,

Cj to wielkość odpadu przy cięciu jednostki materiału wyjściowego zgodnie z wariantem j;

a ij to liczba półfabrykatów i-tego typu podczas wycinania jednostki materiału wyjściowego zgodnie z opcją j.

Wprowadźmy notację nieznanych zmiennych.

xj to ilość surowca pociętego zgodnie z opcją j.

W odniesieniu do wprowadzonej notacji problem ten można zapisać w następujący sposób:

z \u003d С1x1 + С2x2 + ... + Сnxn → min

a11x1 + a12x2 +…+ a1nxn = A1

a21x1 + a22x2 +…+ a2nxn = A2

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

am1x1 + am2x2 +…+ amnxn =Popr

xj ≥ 0, j = 1, n

Wykorzystanie modeli matematycznych pozwala zaoszczędzić do 20% surowców.

Model matematyczny cięcia budowany jest w dwóch etapach.

W pierwszym etapie konstruowane są warianty skrawania, w wyniku których obliczane są wartości liczby wariantów n, liczby wykrojów każdego rodzaju uzyskiwanych przy różnych wariantach skrawania (aij), a także wartości odpadów (Cj).

Konstrukcję opcji cięcia jednostki materiału źródłowego przeprowadza się w postaci poniższej tabeli:

numer opcji

Puste i1

i2 puste

pusty im

Wykroje są ułożone w nierosnącej kolejności ich rozmiarów. Konstrukcja wariantów odbywa się metodą pełnego wyliczenia.

10. Ogólna postać modelu problemu LP i jego cechy

Ogólna forma LLP to:

z \u003d С1x1 + ... + Сnxn maks (min)

a11 X1 + a12 X2 + … + a1n Xn R1 a1

a21 X1 + a22 X2 + … + a2n Xn R2 a2

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

am1 X1 + am2 X2 +…+ amnxn Rm am

xj ≥ 0, j = 1, k, k ≤ n

W ogólnej postaci każdy symbol R1 , R2 ,…, Rm oznacza jeden ze znaków: ≥, = lub ≤ .

Ogólna postać modelu problemu LP ma następujące cechy.

1. Układ więzów przedstawiony jest w postaci równań (warunki sztywne) i nierówności (warunki niesztywne).

2. Warunki nieujemności nie są nakładane na wszystkie zmienne

3. Funkcja celu dąży albo do maksimum, albo do minimum.

11. Standardowa postać modelu problemu LP i jego cechy

Standardowy formularz jest następujący.

Znajdź maksimum lub minimum funkcji celu z:

z = С1x1 + … + Сnxn → max (min) (1)

Z zastrzeżeniem następujących ograniczeń:

a11 X1 + a12 X2 + … + a1n Xn ≤ a1

a21 X1 + a22 X2 + ... + a2n Xn ≤ a2

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

am1 X1 + am2 X2 +… + amn Xn ≥ popr

xj ≥ 0, j = 1, k, k ≤ n

Cechy standardowej postaci modelu problemu LP są następujące:

1. system ograniczeń przedstawiony jest w postaci nierówności (warunki niesztywne)

2. warunki nieujemności są nałożone na wszystkie zmienne

3. funkcja celu dąży do maksimum lub do minimum

12. Postać kanoniczna modelu problemu LP i jego cechy

Forma kanoniczna to:

Znajdź minimum funkcji celu z:

z = С1x1 + … + Сnxn → min

Z zastrzeżeniem następujących ograniczeń:

a11 X1 + a12 X2 + ... + a1n Xn = a1

a21 X1 + a22 X2 + ... + a2nxn = a2

…………………………

am1x1 + am2 X2 +… + amn Xn = am

Xj ≥0, j = 1, n

Cechy formy kanonicznej są następujące:

1. System ograniczeń przedstawiono w postaci równań (warunki rygorystyczne).

2. Warunki braku ujemności mają zastosowanie do wszystkich zmiennych

3. Funkcja celu ma tendencję

W niektórych źródłach funkcja celu problemu LP, przedstawiona w postaci kanonicznej, dąży do maksimum. Odbywa się to dla wygody rozwiązania problemu zgodnie z algorytmem opracowanym dla funkcji maksymalnego celu.

13. Możliwy, dopuszczalny, optymalny plan zadania podstawowego, ODZ zadania LP

Definicja 1. Nazywa się wartości nieznanych zmiennych, które spełniają wszystkie ograniczenia problemu programowania liniowego dopuszczalny wartości zmiennych lub plany .

Definicja 2. Zbiór wszystkich planów dla problemu programowania liniowego nazywa się dziedziną dopuszczalnych wartości zmiennych ( ODZ ).

Definicja 3. Nazywa się plan problemu programowania liniowego, w którym funkcja celu przyjmuje wartość minimalną (lub maksymalną) na ODZ optymalny .

14. Typy zapisów zadań LP: rozszerzone, składane, macierzowe, wektorowe.

Modele problemów LP można pisać w różnych formach.

1. Rozwinięty widok rekordu modelu

Z = c1 X1 + c2 X2 + … + cn Xn → min

a11 X1 + a12 X2 + … + a1n Xn = a1,

a21 X1 + a22 X2 + … + a2n Xn = a2,

……………………………………………

a m1 X1 + am2 X2 + … + amn Xn = am,

Xj ≥ 0, j = 1, n.

2. Zwinięty widok:

,

Xj ≥ 0, j = 1, n.

3. Model problemu LP w postaci macierzowej:

X ≥ 0

Gdzie

a11 a12 … a1n X1 a1

A= a21 a22 … a2n , X= X2 , A0 = a2

… … … … … …

1 rano 2 … rano X3 rano

4. Model problemu LP w postaci wektorowej:

Gdzie

X1 a11 a12 a1n a1

X2 , a21 , a22 , a2n , a2

… … … … …

Хn rano 1 rano 2 rano 2 rano

15. Przejście od standardowej i ogólnej postaci problemów LP do kanonicznej. Twierdzenie o połączeniu

Aby przejść od formy ogólnej lub standardowej do formy kanonicznej, stosuje się następujące techniki.

1. Zmienna konwersja. Jeżeli jakaś zmienna Xk jest niedodatnia (Xk ≤ 0), to wprowadzana jest nowa zmienna Xk ", tak że Xk " = –Xk . Oczywiście Xk " ≥ 0. Następnie w każdym ograniczeniu i funkcji celu zmienna Xk jest zastępowana przez [ – Xk "].

Jeżeli jakaś zmienna Xt może przyjmować dowolne wartości, to jest zastępowana różnicą dwóch nieujemnych zmiennych Xt' i Xt'', czyli zakłada się, że xt = Xt' – Xt'', gdzie Xt' 0 ≥ i Xt'' ≥ 0.

2. Transformacja ograniczeń. Jeżeli któryś z więzów w modelu ma postać nierówności, to jest on przekształcany w równość przez dodanie (jeśli nierówność jest typu ≤) lub odjęcie (jeśli nierówność jest typu ≥) z jego lewej strony. Zmienne te nazywane są zmiennymi bilansowymi. Zmienne bilansowe są zawarte w funkcji celu z zerowymi współczynnikami. Zmienna balance przyjmuje wartość indeksu sekwencyjnie po już istniejących. Jeśli np. system ograniczeń ma 5 zmiennych, to pierwszą zmienną bilansową będzie X6, a drugą X7 itd.

16. Przejście od postaci kanonicznej modelu ZLP do standardu

Aby przejść z formy kanonicznej do formy standardowej, każdy z nich

równania do zastąpienia układem nierówności:

Innym sposobem jest doprowadzenie układu równań do specjalnej postaci i dalsze wyeliminowanie niektórych zmiennych.

Korzystając z metody Jordana-Gaussa, wybieramy podstawową zmienną w każdym równaniu. Selekcji takiej dokonuje się za pomocą ekwiwalentnych (elementarnych) przekształceń Gaussa. Obejmują one:

a) mnożenie dowolnego równania przez stałą różną od zera;

b) dodanie do dowolnego równania dowolnego innego równania pomnożonego przez dowolną stałą.

Wygodnie jest zapisać początkowy układ równań liniowych przed transformacją w postaci macierzy lub tabeli:

Problem zapisujemy w postaci standardowej.

17. Pojęcie hiperpłaszczyzny półpłaszczyzny, hiperpłaszczyzny podporowej.

18. Geometryczny. interpretacja układu ograniczeń i funkcji celu w problemach LP

19. Zbiór wypukły: punkty skrajne (narożne) zbioru. Wypukły wielościan

Definicja Zbiór M nazywamy wypukłym, jeśli wraz z dowolnymi dwoma punktami należącymi do dany zestaw, zawiera również łączący je segment.

zestaw wypukły

Definicja Punkt x zbioru M nazywamy punktem narożnym lub skrajnym, jeśli nie znajduje się on wewnątrz żadnego segmentu, który w całości należy do danego zbioru.

Twierdzenie 1. Dowolny punkt odcinka można przedstawić jako wypukłą kombinację jego punktów narożnych.

x \u003d λ 1 ZA + λ 2 B

λ 1 , λ 2 ≥ 0 wypukła kombinacja punktów narożnych A i B

λ1 + λ2 = 1

Twierdzenie 2. Każdy punkt wypukłego zbioru domkniętego można przedstawić jako wypukłą kombinację jego punktów narożnych.

20. Algorytm graficznej metody rozwiązywania problemów LP

1. Sprawdzane jest, czy oryginalny LPP jest w formie standardowej, jeśli nie, to zadanie należy przekonwertować do formy standardowej.

2. Sprawdzana jest liczba nieznanych zmiennych. Jeśli ta liczba jest większa niż trzy, problemu nie można rozwiązać metodą graficzną (są inne skuteczne metody rozwiązywanie takich problemów).

3. Rejon dopuszczalnych wartości zmiennych dla ZLP jest w trakcie budowy.

4. Trwa budowanie wektora prowadzącego C .

5. Początkowa izocelka jest rysowana przez ODZ (prostopadle do wektora kierunkowego).

6. Wykonywany jest mentalny ruch początkowej izoceli w kierunku wektora C, jeżeli wyznaczona zostanie maksymalna wartość funkcji celu, lub odwrotnie, jeżeli wyznaczona zostanie jej minimalna wartość, aż izocel stanie się odniesieniem do ODZ. Punkty przecięcia izocel odniesienia i ODZ będą punktami optymalnymi problemu.

7. W celu wyznaczenia współrzędnych punktu optymalnego konieczne jest rozwiązanie układu odpowiednich równań liniowych.

8. Aby znaleźć optymalną wartość funkcji celu, należy wstawić do funkcji celu optymalne wartości zmiennych i obliczyć jej wartość.

20. algorytm graficzny. Metoda rozwiązywania problemów LP

Algorytm metody graficznej.

1. Poprzez sukcesywne budowanie każdego z warunków układu ograniczeń problemu przeprowadzana jest konstrukcja ODZ.

2. Wektor kierujący C jest zbudowany ze współczynników dla zmiennych funkcji celu.

3. Początkowy izocel jest rysowany prostopadle do wektora kierunkowego przechodzącego przez początek układu współrzędnych.

4. Początkowy izocel jest mentalnie przesuwany w kierunku rosnących wartości wektora C, jeżeli wyznaczona jest maksymalna wartość funkcji celu, lub w przeciwnym kierunku, jeżeli wyznaczona jest jej minimalna wartość, aż izocel stanie się odniesienie do ODZ. Punkty przecięcia izocel odniesienia i ODZ będą punktami optymalnymi problemu.

5. Aby określić współrzędne punktu optymalnego, konieczne jest rozwiązanie układu odpowiednich równań liniowych tych warunków, na przecięciu których znajduje się punkt optymalny.

6. Aby znaleźć optymalną wartość funkcji celu, należy podstawić współrzędne punktu optymalnego do funkcji celu i obliczyć jej wartość.

23. twierdzenia o zakresie dopuszczalnych wartości problemu LP i o funkcji celu

Twierdzenie ODZ. Dziedziną dopuszczalnych rozwiązań problemu LP jest zbiór wypukły (zamknięty i ograniczony w przestrzeni n-wymiarowej)

Twierdzenie 2. O funkcji celu problemu programowania liniowego.

Funkcja celu LLP przyjmuje swoją optymalną wartość w jednym z punktów narożnych obszaru dopuszczalnych wartości zmiennych. Jeśli funkcja celu przyjmuje swoją optymalną wartość w kilku punktach narożnych, to przyjmuje taką samą wartość w dowolnym punkcie, który jest wypukłą kombinacją tych punktów narożnych.

24. Twierdzenie o punkcie narożnym. Wystarczające i warunek konieczny

25. Wnioski z twierdzenia o własnościach rozwiązań problemów LP i wnioski. Pojęcie linii bazowej.

Konsekwencje z twierdzeń.

Definicja. Plan = (х1,х2,…,хn), którego dodatnie współrzędne odpowiadają wektorom liniowo niezależnym, nazywamy plan podstawowy PLP .

Konsekwencja 1. Plan referencyjny ma nie więcej niż m współrzędnych dodatnich.

Jeśli ma dokładnie m współrzędnych dodatnich, to taki projekt podpory nazywany jest niezdegenerowanym, w przeciwnym razie zdegenerowanym.

Konsekwencja 2. Każdy punkt narożny ODZ to plan podstawowy.

27. Algorytm metody simplex.

Podczas rozwiązywania problemów LP metodą simplex konieczne jest wykonanie następującej sekwencji działań.

1. Sprawdza się, czy problem LP ma postać kanoniczną. Jeśli nie, to konieczne jest przekształcenie pierwotnego modelu do postaci kanonicznej.

2. Dla tego planu odniesienia wybiera się początkowy plan odniesienia i wartość funkcji celu.

3. Konstruowana jest początkowa tablica simplex.

4. Sprawdzane są wartości oszacowań optymalności w linii indeksu. Jeśli nie ma pozytywnych oszacowań, wówczas wypisywane jest rozwiązanie optymalne i algorytm kończy swoją pracę. W przeciwnym razie punkt 5 jest spełniony.

5. W bazie wprowadza się wektor, który odpowiada największemu oszacowaniu dodatniemu. Ta kolumna jest nazywana kolumną włączania.

6. Z bazy wyprowadzamy wektor, który odpowiada stosunkowi simpleksowemu obliczonemu ze wzoru 0< Ө ≤ . Podana linia zwany łańcuchem włączającym.

7. Powstaje nowa tablica simplex. Odpowiednio zmieniane są kolumny B i C B. Pozostała część tabeli jest wypełniana z poprzedniej za pomocą transformacji Gaussa, przy czym wiersz indeksu jest uznawany za m+1 wierszy i również jest przekształcany za pomocą transformacji Gaussa. Przechodzimy do wdrożenia paragrafu 4 tego algorytmu.

Po zbudowaniu każdej tabeli można sprawdzić poprawność obliczeń korzystając ze wzorów do obliczania szacunków podanych w poprzednim akapicie.

28. Wybór podstawy i budowa wstępnego planu referencyjnego rozwiązywania problemów metodą simplex.

29. Tablice simplex, ich wypełnianie. Wzory do obliczania współczynników wiersza indeksu.

30 . Twierdzenie o optymalności dla planu problemu programowania liniowego jest konsekwencją twierdzenia o estymacji optymalności dla rozwiązywania problemów metodą simplex.

Twierdzenie 1: Jeżeli dla pewnego wektora Ā j w układzie

X 1 + za 1 m +1 X m +1 + za 1 m +2 X m +2 + ... + za 1 n X n \u003d za 1

X 2 + za 2 m +1 X m +1 + za 2 m +2 X m +2 + ... + za 2 n X n \u003d za 2

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

X m + a mn +1 X m +1 + a mn +2 X m +2 + ... + a mn X n = a m

Zależność Z j – c j > 0 jest spełniona, to plan X B0 nie jest optymalny i można przejść do planu X B1 tak, że Z (X B1) ≤ Z (X B0).

Tutaj Z j = (С, Ā j) jest iloczynem skalarnym wektorów.

C jest wektorem składającym się ze współczynników przy zmiennych podstawowych funkcji celu Z

Ā j jest wektorem składającym się ze współczynników rozszerzenia odpowiedniego wektora wyrażonych w wektorach bazowych.

c j jest współczynnikiem funkcji celu Z ze zmienną X j

Konsekwencja z twierdzenia: Jeżeli dla wszystkich wektorów Ā 1 , Ā 2 , …, Ā n pewnego planu odniesienia Ő relacja Z j – c j< 0, то опорный план Х является оптимальным. Величины (Z j – c j) – называются оценками оптимальности соответствующих векторов.

Zatem twierdzenie i wniosek pozwalają stwierdzić, czy kolejny plan wsparcia jest optymalny, a jeśli nie, to należy przejść do innego planu wsparcia, w którym wartość funkcji celu będzie mniejsza.

Komentarz. Twierdzenie i wniosek zakładają, że problem ma postać kanoniczną z minimalną funkcją celu. Jednak metoda simplex może być również stosowana do rozwiązywania problemów z funkcją maksymalnego celu. W takim przypadku przy analizie wartości oszacowań stosuje się ich przeciwne znaczenie, to znaczy plan będzie optymalny, jeśli wszystkie oszacowania optymalności będą nieujemne (dodatnie lub ujemne).

31. Wybór wektora wchodzącego do bazy i wyprowadzającego z bazy. Relacja simplex.

Aby przełączyć się na nowy plan referencyjny, potrzebny jest jeden z wektorów swobodnych wprowadź do bazy i wyprowadź niektóre wektory bazowe. Aby wprowadzić do bazy, wybieramy wektor, który ma co najmniej jedną współrzędną dodatnią. Niech wektor A m+1 będzie takim wektorem.

rozkład -

Odp. wektor, kot. będzie planem odniesienia, jeśli jego współrzędne są nieujemne, a liczba współrzędnych dodatnich będzie równa m.

Współrzędne wektora X1 muszą być nieujemne, tj. .

Jeśli , to ta współrzędna będzie nieujemna.

Niech minimum w relacji (5) otrzymamy przy i = 1, to jeśli weźmiemy

następnie pierwsza współrzędna wektora 1 X stanie się zerem.

Relacja (6) jest nazywana relacja simplex. W ten sposób przeszliśmy od pierwotnej linii bazowej 0 X(wektory bazowe A1, A2, ... Am) do planu odniesienia 1 X(wektory podstawowe A2, A3,…, Am, Am+1).

32. dopuszczający element tabeli, jego wybór. Pełna reguła eliminacji Jordana dla ponownego obliczania tablicy simplex.

33. Reguła czworoboku dla przeliczania tablicy simplex

34. Znak wyjątkowości planu optymalnego, zbioru planów optymalnych i braku planu optymalnego przy rozwiązywaniu problemu LP metodą simplex.

Podczas rozwiązywania problemów metodą simplex możliwe są następujące rodzaje optymalnych rozwiązań:

1. Wyjątkowość . Jeżeli oszacowania wszystkich wektorów swobodnych są ściśle ujemne, to otrzymany układ podpór jest optymalny i unikalny. (patrz przykład w poprzednim akapicie).

2. Optimum alternatywne (zbiór rozwiązań optymalnych).

Jeżeli wśród niedodatnich oszacowań wektorów swobodnych znajdzie się co najmniej jedno oszacowanie zerowe, to otrzymany układ podpór będzie optymalny, ale nie jedyny. W takim przypadku można przejść do innych planów wsparcia (wprowadza się do bazy wektory odpowiadające oszacowaniom zerowym) i następnie zapisać ogólne rozwiązanie optymalne jako wypukłą kombinację otrzymanych optymalnych planów wsparcia.

3. LLP nie ma rozwiązania optymalnego, ponieważ funkcja celu nie jest ograniczona od dołu . Jeśli tabela simplex ma pozytywny wynik i wszystkie elementy dana kolumna są wtedy ujemne i zerowe dany wektor można zaliczyć do podstawy. Jednak żadnego z wektorów bazowych nie można wywnioskować z bazy. Wynika z tego, że przy przejściu na plan niewspierający możliwy jest dalszy spadek funkcji celu.

4. LLP nie ma rozwiązania optymalnego, ponieważ system ograniczeń jest niespójny. Ponieważ przy rozwiązywaniu LLP zwykła metoda simplex powinna być początkowym planem odniesienia, układ równań liniowych z pewnością nie jest niespójny. Dlatego taki przypadek nie może wystąpić przy rozwiązywaniu zwykłą metodą simplex.

5. Jeżeli ODZ składa się z jednego punktu, to rozwiązanie takiego problemu jest trywialne i można je uzyskać bez użycia metody simplex.

35. Kiedy stosuje się metodę sztucznej podstawy?

sztuczny.

36. Konstrukcja M-problemu w metodzie sztucznej bazy

Jeśli jednak problem programowania liniowego ma postać kanoniczną, nie wszystkie równania zawierają zmienne podstawowe, tj. Nie ma oryginalnej linii bazowej. W takim przypadku w tych równaniach, w których nie ma zmiennych podstawowych, konieczne jest dodanie jakiejś nieujemnej zmiennej o współczynniku +1. Taka zmienna nazywa się sztuczny.

Do funkcji celu należy dodać sztuczną zmienną o bardzo dużej liczbie dodatniej (ponieważ funkcją celu jest znalezienie minimum). Ta liczba jest oznaczona List łaciński M. Można ją uznać za równą +∞. W związku z tym czasami metoda sztucznej bazy nazywana jest metodą M. Takie przekształcenie pierwotnego problemu nazywa się konstrukcją problemu rozszerzonego. Jeśli rozwiązujesz problem z funkcją celu, aby znaleźć sztuczną zmienną, musisz dodać do funkcji celu bardzo dużą liczbę dodatnią (ponieważ funkcja celu polega na znalezieniu minimum). Liczba ta jest oznaczona łacińską literą M. Można ją uznać za równą +∞. W związku z tym czasami metoda sztucznej bazy nazywana jest metodą M. Takie przekształcenie pierwotnego problemu nazywa się konstrukcją problemu rozszerzonego. Jeśli problem jest rozwiązywany za pomocą funkcji celu, aby znaleźć maksimum, to zmienne sztuczne wchodzą do funkcji celu ze współczynnikiem -M.

Zatem w rozszerzonym problemie mamy linię bazową (chociaż niektóre zmienne bazowe są sztuczne).

Tworzona jest początkowa tablica simplex.

37. budowanie linii indeksu metodą sztucznej bazy

Tworzona jest początkowa tablica simplex, w której wiersz indeksu jest podzielony na dwa wiersze, ponieważ oszacowania składają się z dwóch wyrazów. Górny wiersz zawiera wyraz oszacowania bez M, dolny wiersz pokazuje współczynniki przy M. Znak oszacowania jest określony przez znak współczynnika przy M, niezależnie od wartości i znaku wyrazu bez M, gdyż M jest bardzo dużą liczbą dodatnią.

Zatem, aby określić wektor, który jest wprowadzany do bazy, należy przeanalizować dolną linię indeksu. Jeśli sztuczny wektor jest wyprowadzany z bazy, to odpowiednią kolumnę w kolejnych tablicach simplex można pominąć, jeśli nie ma potrzeby uzyskiwania rozwiązania problemu dualnego (patrz następny temat).

Po usunięciu wszystkich sztucznych wektorów z bazy dolny wiersz będzie zawierał wszystkie elementy zerowe, z wyjątkiem oszacowań odpowiadających sztucznym wektorom. Będą równe -1. Linię taką można usunąć z rozważań i dalsze rozwiązanie można przeprowadzić zwykłą metodą simplex, jeśli nie ma potrzeby uzyskiwania rozwiązania problemu dualnego (patrz następny temat).

38. Kryterium optymalności w metodzie sztucznej bazy. Znakiem rozpoznawczym jest budowa wstępnego podstawowego planu zadania pierwotnego.

39. Algorytm metody dual simplex

Algorytm metody dual simplex:

1. wypełnić pierwszą tablicę simplex w zwykły sposób, niezależnie od znaków wolnych członków. Uważa się, że taki problem powinien mieć wyjściową podstawę jednostkową.

2. Wybierz linię prowadzącą przez największy bezwzględny ujemny element kolumny wolnych prętów A0

3. Kolumna prowadząca jest wybierana zgodnie z najmniejszą bezwzględną wartością stosunku elementów linii indeksu do ujemnych elementów linii prowadzącej.

4. Przelicz tablicę simplex zgodnie z regułą pełnych eliminacji Jordana

5. sprawdzić otrzymany plan pod kątem dopuszczalności. Oznaką uzyskania akceptowalnego planu odniesienia jest brak elementów ujemnych w kolumnie A0. Jeśli w kolumnie A0 znajdują się elementy ujemne, przejdź do drugiego akapitu. Jeśli ich nie ma, przystępują do rozwiązania problemu w zwykły sposób.

6. Znakiem uzyskania rozwiązania optymalnego metodą dual simplex jest kryterium optymalności dla zwykłej metody simplex.

41. Modele transportu otwartego i zamkniętego. Przejście z otwartego modelu transportu do zamkniętego.

Rodzaje zadań transportowych.

Dostępny M dostawcy jednorodnych produktów o znanych zapasach produktów i N konsumentów tych produktów przy danych wielkościach potrzeb. Znane są również jednostkowe koszty transportu.

Jeśli suma wielkości zapasów produktów jest równa wielkości potrzeb wszystkich konsumentów, wówczas taki problem nazywa się zamknięte zadanie transportowe

(tj. jeśli ∑ Ai = ∑ Bj), w przeciwnym razie nazywamy problem transportu otwarty. Aby rozwiązać problem transportu, konieczne jest jego zamknięcie.

Otwarte zadanie transportowe można przekształcić w zamknięte w następujący sposób.

Niech ∑Ai > ∑Bj. W tym przypadku konieczne jest wprowadzenie fikcyjnego konsumenta n + 1 o wolumenie potrzeb ∑Ai – ∑Bj Przyjmuje się, że jednostkowe koszty transportu od dostawców do fikcyjnego konsumenta wynoszą 0, ponieważ w rzeczywistości taki transport nie będzie przeprowadzone, a część produktów pozostanie u dostawców.

Jeżeli ∑Bj > ∑Ai . W takim przypadku konieczne jest wprowadzenie fikcyjnego dostawcy m + 1 o wielkości zapasów ∑Bj – ∑Ai . Zakłada się, że jednostkowe koszty transportu od fikcyjnego dostawcy do konsumentów są równe 0, ponieważ w rzeczywistości taki transport nie zostanie zrealizowany, a konsumenci nie otrzymają części produktów.

42. Metody konstruowania rozkładu początkowego w problemie transportowym: metoda północno-zachodniego narożnika i metoda najmniejszego elementu macierzy.

Północno-zachodnia technika konstruowania planu referencyjnego. Zgodnie z tą techniką tworzenie wartości ruchu rozpoczyna się od s.-z. narożnik stołu, tj. z komórki x11. Zgodnie z tą metodą dystrybuowane są przede wszystkim towary pierwszego dostawcy. Co więcej, pierwszy dostawca najpierw w jak największym stopniu zadowala pierwszego konsumenta. Następnie, jeśli dostawca nadal ma towar,

Metoda najmniejszego elementu w macierzy.

Istota metody polega na tym, że w ogniwie umieszczana jest zawsze maksymalna możliwa podaż, która odpowiada najniższej taryfie matrycy.

Najpierw wykonujemy oznaczenia (na przykład znakiem ▼) w tych komórkach linii, w których obserwuje się najniższą cenę za linię. Następnie chodzimy po stole po kolumnach i robimy te same notatki w komórkach, w których najniższa cena jest według kolumn.

Dalszy rozkład odbywa się najpierw w miarę możliwości na komórki z dwoma znakami, następnie - z jednym, a następnie problem jest ponownie równoważony do (m + n - 1) wypełnień. Nadzienia organizujemy przy podawaniu stołu od lewej do prawej i od góry do dołu.

43. Właściwości zadań transportowych

Problem transportu ma pewne właściwości, które można odzwierciedlić w następujących twierdzeniach.

Twierdzenie 1. Zamknięty problem transportowy zawsze ma rozwiązanie.

Twierdzenie 2. Jeżeli wielkość zapasów produktów i wielkość potrzeb są liczbami całkowitymi, to rozwiązanie problemu transportu również będzie liczbą całkowitą.

Twierdzenie 3. układ ograniczeń zamkniętego problemu transportowego jest zawsze liniowo zależny.

Z twierdzenia tego wynika, że ​​rozkład zamkniętego problemu transportowego ma zawsze m + n – 1 zmiennych podstawowych i (m – 1) (n – 1) zmiennych czasu wolnego.

44. Rozkład zdegenerowany w problemach transportowych, pozbycie się degeneracji. Przekreślona kombinacja.

Rozkład nazywamy zdegenerowanym, jeśli liczba komórek jest mniejsza niż m + n - 1.

45. Twierdzenia o optymalności dla problemu transportu.

Twierdzenie. Jeśli dla jakiegoś podziału zadania transportowego ty

warunki są spełnione:

A). ui+vj = cij dla zajętych komórek

B) ui+vj ≤ сij, dla wolnych komórek,

wtedy ten rozkład jest optymalny.

Wartości ui nazywane są potencjałami wierszowymi, a wartości vj potencjałami kolumnowymi.

46. ​​Potencjały i metody ich obliczania.

Aby znaleźć potencjały wierszy i kolumn, stosuje się następujące rozumowanie, oparte na warunku a) twierdzenia o optymalności.

Liczba równań opartych na tym warunku to m + n – 1, a liczba niewiadomych ui i vj to m + n. To. liczba zmiennych jest większa niż liczba równań, a wszystkie równania są liniowo niezależne. Rozwiązanie takiego układu równań liniowych jest nieoznaczone, więc jednemu z potencjałów należy przypisać dowolną wartość. W praktyce ui = 0. Otrzymuje się układ m + n – 1 równań z m + n – 1 nieznanymi zmiennymi. Układ ten można rozwiązać dowolną metodą. W praktyce do obliczenia potencjałów brane są pod uwagę zajęte komórki, dla których znany jest jeden z ich potencjałów i na podstawie warunku a) twierdzenia obliczane są wartości pozostałych nieznanych potencjałów.

47. Obliczanie oszacowań optymalności rozkładu zadań transportowych i kryterium optymalności.

Na podstawie zależności b) twierdzenia możemy napisać następujący wzór na obliczanie oszacowań: δ ij= ui + vj – сij. Aby nie mylić szacunków z natężeniem ruchu, są one (szacunki) otoczone kółkami.

Szacunki optymalności w wolnych komórkach TK są kryterium optymalności, które sprawdza rozkład pod kątem optymalności. Jeśli szacunki wszystkich wolnych komórek są mniejsze lub równe zeru, to ten rozkład jest optymalny.

48. redystrybucja zaopatrzenia w problemie transportowym

Jeśli dystrybucja nie jest optymalna, konieczna jest redystrybucja dostaw.

W celu redystrybucji budowany jest cykl ponownego obliczania. Komórka z najwyższym pozytywnym wynikiem jest wybierana jako komórka. Ta komórka jest oznaczona znakiem „+”, co oznacza, że ​​\u200b\u200bnależy zapisać w niej określoną ilość dostawy. Ale wtedy równowaga w tej kolumnie zostanie zakłócona, dlatego jedną z zajętych komórek tej kolumny należy oznaczyć znakiem „-”, to znaczy wielkość podaży należy zmniejszyć o tę samą kwotę. Ale wtedy saldo dla tej linii ulegnie zmianie, dlatego jakaś zajęta komórka tej linii musi być oznaczona znakiem „+”. Proces ten trwa do momentu umieszczenia znaku „-” w wierszu, w którym znajdowała się pierwotna komórka.

Dla każdej wolnej komórki istnieje cykl ponownego obliczania, a ponadto jedyny.

49. Łańcuchy redystrybucyjne, ich rodzaje.

Niech rozważany plan transportu nie będzie optymalny, tj. istnieją pozytywne szacunki względne. Następnie pobierana jest niekorzystna komórka (jedna z niekorzystnych) i budowany jest dla niej cykl przeliczeń, zgodnie z którym następuje redystrybucja planowanego transportu. Cykl jest zbudowany w postaci łamanej linii zamkniętej, której odcinki biegną albo wzdłuż kolumny, albo wzdłuż linii. W jednym z rogów linii przerywanej znajduje się niekorzystna komórka zgłaszająca produkt, aw pozostałych rogach komórki są wypełnione, tj. konstruując cykl zaczynamy od komórki kandydującej i wracamy do niej linią przerywaną, ale zwroty możemy wykonywać tylko w wypełnionych komórkach (odpowiadających podstawowym zmiennym). Niech niekorzystna komórka zgłosi roszczenie do produktu Q. Aby zapobiec nierównowadze w tabeli, konieczne jest

dodawać i odejmować Q do dostępnego ruchu. Ponieważ istnieje parzysta liczba rogów, Q zostanie dodane w połowie komórek i odjęte w drugiej połowie. Cykl rozpoczyna się zgodnie z ruchem wskazówek zegara lub przeciwnie do ruchu wskazówek zegara od komórki kandydującej, umieszczając tam dobre Q, następnie Q jest odejmowane od sąsiedniej komórki, następnie dodawane i tak dalej. Wartość samego Q jest tak dobrana, że ​​jedna z komórek jest opróżniana, ale żadna z dostaw nie stałaby się ujemna.

Aby to zrobić, należy wybrać Q równe najmniejszej redukowalnej z komórek, w których Q jest odejmowane. Na poniższym rys. 7.1 i 7.2 pokażemy przykłady cykli i zasadę obliczeń.

W takim przypadku opróżniane są dwie komórki. Ale konieczne jest, aby tylko jedna komórka stała się wzajemnie pusta. Robią to: jedna z pustych komórek jest pusta w nowej tabeli, a zero jest umieszczane w drugiej pustej komórce. Ta komórka jest uważana za podstawową (wypełnioną) w nowej tabeli.

50. Wybór wielkości redystrybucji.

Określenie objętości przewożonych produktów. Przy określaniu ilości produktów przechodzących przez cykl liczenia musimy wziąć pod uwagę następujące dwa czynniki:

a) po przekształceniu w komórkach tabeli nie należy uzyskiwać liczb ujemnych;

b) jedna z zajętych komórek musi zostać zwolniona.

Aby te warunki były spełnione, należy dobrać wielkość transportowanych produktów w następujący sposób: θ=min (хij) -, gdzie (хij) to wielkość transportu z komórek cyklu przeliczeniowego oznaczonych symbolem „ -" podpisać.

θ = min(20;30)=20

θ jest dodawane do wartości komórek oznaczonych znakiem „+”. Od wartości komórek oznaczonych znakiem „-” odejmuje się θ. Wartość zasilania pozostałych komórek jest nadpisywana bez zmian. W rezultacie otrzymujemy następującą tabelę.

53. Algorytm metody potencjałów.

Algorytm:

1. Sprawdź, czy równanie jest spełnione dla zadania jeśli nie, do zadania zostaje wprowadzony fikcyjny dostawca lub konsument

2. Warunek zadania jest zapisywany w postaci tabeli transportowej

3. Tworzona jest początkowa linia bazowa

4. Określa się potencjały dostaw i odbiorców

5. Obliczane są wyniki wolnych komórek. Jeśli wszystkie nie są negatywne, plan jest optymalny i musisz napisać odpowiedź. Macierz transportu X i określ wysokość kosztów transportu. Jeżeli plan nie jest optymalny, tzn. wśród szacunków są ujemne, to wybieramy obiecującą komórkę o największej wartości ujemnej. oszacować i przejść pod względem wielkości do następnego.

6. Załaduj perspektywiczną komórkę. Przygotuj nowy plan bazowy w postaci tabeli transportowej. Przejdź do punktu 4.

54. Rozliczanie kosztów produkcji i transportu produktów. Zadanie transportowe z zakazami dostaw.

Rozwiązując niektóre problemy, należy wziąć pod uwagę koszty nie tylko transportu towarów, ale także produkcji transportowanych produktów. Aby to zrobić, w macierzy transp. zadania

Gdzie Cij' to obniżony koszt wytworzenia jednej jednostki produkcji.

Cij” – koszt transportu jednej jednostki produkcji.

Zadania z zakazem zaopatrzenia.

W niektórych sytuacjach transport produktów na żadnej trasie nie jest możliwy.

Aby to zrobić, w macierzy zadania transportowego, przez które transport jest zabroniony, wprowadza się taryfę wygórowaną M. Ponadto zadanie jest rozwiązywane w zwykły sposób, jednak ta komórka zawsze będzie odpowiadać ujemnemu wynikowi komórki.

55. uwzględnienie ograniczeń w przepustowości tras, uwzględnienie obligatoryjności niektórych dostaw w problematyce transportowej.

uwzględnienie ograniczeń w przepustowości tras.

W niektórych zadaniach transportowych, na niektórych trasach, mniejsze wydajność niż jest to konieczne do zaspokojenia zapotrzebowania punktu poboru.

z uwzględnieniem obligatoryjności niektórych dostaw w problematyce transportowej.

W niektórych przypadkach zadanie wymaga realizacji np. na trasie Ak Bs dostawy w jednostkach objętości A. W tym przypadku podaż obowiązkowa jest odejmowana od wielkości produkcji punktu A i wielkości S Bs i problem zostaje rozwiązany w odniesieniu do podaży opcjonalnej. Po uzyskaniu rozwiązania optymalnego podaż jest koniecznie dodawana do objętości stojącej w komórce Ak Bs.

56. Możliwe wnioski z ekonomicznego. interpretacja optymalnego rozkładu dla otwartych problemów transportowych.

Po otrzymaniu optymalnego rozkładu należy powrócić do pierwotnego problemu i dokonać odpowiedniej ekonomii. wnioski. Są to:

1. W przypadku wprowadzenia punktu poboru oznacza to, że w analizowanym systemie występują nadmierne wielkości produkcji i istnieje możliwość, bez uszczerbku dla rozpatrywanego systemu, zmniejszenia zdolności tych punktów produkcji o wielkość wiążących które są powiązane z fikcyjnym miejscem konsumpcji.

2. Wprowadzenie fikcyjnego miejsca produkcji oznacza, że ​​moce rzeczywistych miejsc produkcji są niewystarczające i należy je zwiększyć. Zwiększa się wydajność tych punktów produkcyjnych, które znajdują się najbliżej punktów zużycia powiązanych z fikcyjnym punktem produkcji. Moce wytwórcy powiększone są o wartość wiążącą. Aby to zrobić, rozważ kolumnę punktu zużycia, która jest powiązana z fikcyjnym punktem produkcji, i znajdź w niej najniższą taryfę. Najbardziej efektywne jest zwiększenie mocy punktu produkcyjnego odpowiadającego tej taryfie o kwotę wiązania.

57. Pojęcie dwoistości. Ekonomiczne sformułowanie problemów dualnych na przykładzie problemu optymalizacji planu produkcji.

Problem dualny to problem pomocniczy programowania liniowego sformułowany przy użyciu pewnych reguł bezpośrednio z warunków problemu pierwotnego lub bezpośredniego.

Niech będzie zadanie optymalizacji planu produkcji. To wygląda tak:

Zadanie początkowe:

za 11 x 1 + za 12 x 2 +…+ za 1p x p ≤v 1 | 1

za 21 x 1 + za 22 x 2 +…+ za 2p x p ≤v 2 | o 2

……………….. |.. (1)

A T 1 x 1 + za T 2 x 2 + ... + za T n x n ≤ v 1 | Na T

xj ≥0,j = 1,n(2)

z = do 1 x 1 +c 2 x 2 +…+c n x n ->maks(3)

X \u003d (x 1, x 2, ..., x n)

a ij - ilość surowców i-tego typu wydana na wytworzenie j-tego rodzaju produktu

Podwójny problem

Niech przedsiębiorstwo z jakiegokolwiek powodu nie będzie w stanie wytwarzać produktów. W celu obniżenia kosztów przestojów firma może sprzedać posiadane surowce. Po jakiej cenie należy sprzedawać surowce?

i - cena i-tego rodzaju surowca dostępnego w przedsiębiorstwie.

za 11 y 1 + za 21 y 2 + ... + za T 1 rok T≥s 1

za 12 x 1 + za 22 y 2 + ... + za T 2 x n ≥s 2

……………….. (1’)

A 1 szt y 1 +a 2p y 2 +…+ za tp Na T≥s P

i ≥0, j = 1,m(2’)

F = b 1 y 1 + b 2 y 2 +…+b m y m ->min(3’)

58. Zgodność elementów strukturalnych problemu bezpośredniego i dualnego

Każdy problem programowania liniowego może być powiązany

podwójne zadanie według następujących zasad:

1. We wszystkich ograniczeniach pierwotnego problemu muszą obowiązywać wolne terminy

być po prawej stronie, a wyrazy z niewiadomymi po lewej.

2. Więzy-nierówności pierwotnego problemu muszą mieć znaki,

skierowany w jednym kierunku.

3. Jeżeli funkcja celu w zadaniu pierwotnym jest zminimalizowana, to ograniczenia nierównościowe należy zapisać znakiem „≤”, wówczas w zadaniu dualnym funkcja celu zostanie zminimalizowana, a znaki ograniczeń nierównościowych będą miały postać „≥”.

4. Każde ograniczenie pierwotnego problemu odpowiada zmiennej w

podwójne zadanie. Jeśli zmienna odpowiada nierówności, jest nieujemna, jeśli odpowiada równości, to zmienna jest bez ograniczeń co do znaku („dowolna”).

5. Współczynniki zmiennych w ograniczeniach problemu dualnego uzyskuje się przez transpozycję macierzy złożonej z

współczynniki dla zmiennych pierwotnego problemu.

6. Wolne terminy pierwotnego problemu to współczynniki w

zmienne w funkcji celu problemu dualnego i wolne

wyrazy w problemie dualnym to współczynniki zmiennych w

funkcji pierwotnego problemu.Zauważamy również, że relacja dualności jest wzajemna, tj. zadanie dualne w stosunku do dualnego pokrywa się z pierwotnym.Para dualna zadań dzieli się na symetryczne i asymetryczne. W parze symetrycznej ograniczenia problemu pierwotnego i dualnego nie są ścisłymi nierównościami, a zatem zmienne obu problemów mogą przyjmować tylko wartości nieujemne.

59. Konstruowanie problemów dualnych do problemów pierwotnych zapisanych w standardowej, kanonicznej i ogólnej postaci modelu (konstrukcja problemów dualnych symetrycznych i asymetrycznych)

Formularz standardowy (oryginał)

Σ za ij x j ≤ b ja , i=1,n(1)

xj ≥0, j=1,n(2)

z = Σ do j x j ->maks(3)

Podwójny standard

Σ a ij y ja ≤ c j , j=1,n(1)

yi ≥0, j=1,m(2)

F = Σ b i y i ->min(3)

Oryginalny problem w postaci kanonicznej:

Σ za ij x j = b ja , i=1,m(1)

xj ≥0, j=1,n(2)

z = Σ do j x j ->min(3)

Podwójny kanoniczny

Σ a ij y ja ≤ c j , j=1,n(1)

y i - dowolne (2)

F = Σ b i y i ->max(3)

Podajmy ekonomiczną interpretację pary problemów dualnych. Rozważ problem racjonalnego wykorzystania zasobów. Niech przedsiębiorstwo posiada zasoby b1,b2,…bm, które można wykorzystać do wytworzenia n-rodzajów produktów. Podajmy również koszt jednostkowy produktu typu j cj (j=1,n) oraz wskaźnik zużycia i-tego zasobu (i=1,m) na produkcję j-te jednostki produkty - aij Należy określić wielkość produkcji każdego rodzaju xj (j=1,n), maksymalizując całkowity koszt

f= c1x1+…+cnxn (1)

Jednocześnie zużycie zasobów nie powinno przekraczać ich dostępności:

a11x1+…+a1nxn<=b1 }

…………………….. } (2)

am1x1+…+amnxn<=bm }

Wszystkie znane w sensie ekonomicznym są nieujemne:

Xj>=0 (j=1,n). (3)

Zauważ, że ten problem tworzy symetryczny problem dualny.

Asymetryczne problemy dualne.

Doprowadźmy ZLP do maksimum w postaci kanonicznej:

Maks. Z=(n;j=1)Σcj*xj

(n;j=1)Σaij*xj=bi (i=1,m)

Xj>=0 (j=1,n).

60. Główne i drugie twierdzenie o dualności (podaj twierdzenia i wyjaśnij)

Pierwsze twierdzenie o dualności.

Twierdzenie: jeśli jeden z problemów dualnych ma plan optymalny, to drugi jest rozwiązywalny, tj. ma opcjonalny plan. W tym przypadku ekstremalne wartości funkcji celu pokrywają się (j=od 1 do n) Σcjxj*= (i=od 1 do m)Σbiyi* jeśli w oryginale. jeśli funkcja celu jest nieograniczona na zbiorze planów, to w problemie dualnym układ ograniczeń jest niespójny.

Drugie twierdzenie o dualności i jego ekonomiczna interpretacja.

Aby dopuszczalne rozwiązania pary problemów dualnych były optymalne, konieczne i wystarczające jest spełnienie warunku: xj*(∑aij yi*-cj)=0, j od 1 do n, yi*( ∑aij xj*-bi)=0, I od 1 do m. Są to warunki uzupełniającego luzu. Wynika z nich, że jeśli jakieś ograniczenie problemu dualnego zostanie przekształcone przez plan optymalny w ścisłą równość, to odpowiedni składnik opt. plan problemu dualnego powinien być równy zero.Jeśli jakiś składowy opt. plan jest równy zeru, to odpowiednie ograniczenie problemu dualnego jest konwertowane przez opt.plan na ścisłą równość xj*>0, stąd (i= od 1 do m)Σaij yi*=cj opt.plan, to jeśli koszty>ceny, wielkość produkcji=0 Σaij yi* >cj stąd xj*=0

yi*>0 zatem (j=od 1 do n) Σaij xj*=bi (wyścigi zasobów = zasoby zasobów).

(j=1 do n) Σaij xj*

Znaczenie twierdzenia jest następujące:

Jeżeli oszacowanie kosztów zużycia zasobów do produkcji jednostki prod-ii \u003d cena, to ten typ prod-ii jest uwzględniony w planie optymalnym;

Jeśli koszty przekraczają cenę, to prod-yu nie powinno być produkowane;

Jeżeli zużycie zasobów = zapasy, to kosztorys tego zasobu jest dodatni. Taki zasób nazywany jest rzadkim. Najbardziej deficytowy.res-s ma najwyższy wynik;

Jeśli zasób nie jest w pełni wykorzystany, to jego kosztorys = 0.

61. Konstrukcja optymalnego planu wsparcia dla problemu dualnego z tablicy simplex problemu pierwotnego

Informacje z kolumn odwrotnej macierzy przekształceń liniowych, które doprowadziły do ​​optymalnego wyniku. Kolumny macierzy D-1 dostarczają bardzo przydatnych informacji.

Kolumna A3: „ukryta” cena zasobu S2 wynosi y01=0, kolumna pozostaje

single i z pierwszego wiersza można wyczytać, że x3=9, tj. przy wdrażaniu znalezionego optymalnego planu pierwszy zasób będzie w nadmiarze, a ten nadmiar (niepełne wykorzystanie) wyniesie zaledwie 9 jednostek konwencjonalnych.

Kolumna A4: cena „ukryta” zasobu S2 jest równa y02=1, zasób zostanie w pełni wykorzystany, a jego ewentualny wzrost doprowadzi do wzrostu funkcji celu (tj. dochodu). I ponieważ y02=1, to wzrost zasobu S2 o 1 j.m. da dodatek w postaci dochodu o .Z = y02 · .w2 = = 1,1 = 1 (tys. UAH) (tutaj.w2 to przyrost zasobu S2, a .Z to odpowiedni przyrost dochodu). Przy takim przyroście zasobu S2 maksymalny dochód wyniesie już Zmax=58 tys. hrywien. + 1 tys. hrywien = 59 tys. hrywien. na ryc. 6.2 ilustruje tę sytuację, której komentarz zostanie podany poniżej. Z kolumny A4 wynika również, że wraz ze wzrostem zasobu S2 o 1 j.m. dla nowego punktu optymalnego produkcja towaru T1 zmniejszy się o ½ tony (na przecięciu wiersza zmiennej podstawowej x1 i kolumny A4 wynosi „-1/2”), a produkcja towaru T2 wzrośnie o 3 /2 tony (ponieważ w wierszu ze zmienną podstawową x2 w kolumnie A4 mamy „3/2”. To, co zostało powiedziane o kolumnie A4, zostanie poniżej skomentowane za pomocą konstrukcji graficznych (rys. 6.2). Kolumna A5: „cień "cena zasobu S3 jest równa y03=2. Oznacza to, że wzrost zasobu S3 o 1 j.m. przyniesie dodatek w Z do.Z = y03 .v3 = 2,1 =2(tys. hrywien) i wyniesie Zmax=58 tys. hrywien. + 2 tysiące hrywien = 60 tysięcy hrywien. Jednocześnie, jak wynika z kolumny A5 tabeli. 3 produkcja T1 wzrośnie o ½ tony, a T2 spadnie o ½ tony. Zapas surowców S1 (patrz wiersz 1) wzrośnie o 3/2 j.m.

62. Idea metody programowania dynamicznego i jej geometryczna interpretacja. Zasada optymalności Bellmana.

Optymalne rozwiązanie problemu metodą programowania dynamicznego znajduje się na podstawie równania funkcjonalnego

Aby go zdefiniować, potrzebujesz:

1. zapisz równanie funkcjonalne dla ostatniego stanu procesu (odpowiada l \u003d n-1)

fn-1(Sl-1)=optymalny(Rn(Sn-1,Un)+f0(Sn))

2. znaleźć Rn(Sn-1,Un) z dyskretnego zbioru jego wartości dla pewnych ustalonych Sn-1 i Un z odpowiednich obszarów dopuszczalnych (skoro f0(Sn)=0, to f1(Sn-1)= optymalny(Rn( Sn-1,Un)

W efekcie po pierwszym kroku znane jest rozwiązanie Un i odpowiadająca mu wartość funkcji f1(Sn-1)

3. Zmniejsz wartość l o jeden i zapisz odpowiednie równanie funkcyjne. Dla l=n-k (k= 2,n) wygląda to tak

fk(Sn-k)=optymalny(Rn-k+1(Sn-k,Un-k+1)+fk-1(Sn-k+1)) (2)

4. znajdź warunkowo optymalne rozwiązanie na podstawie wyrażenia (2)

5. sprawdzić, ile wynosi wartość l. Jeżeli l=0, to obliczenie rozwiązań warunkowo optymalnych jest zakończone i znalezione zostaje rozwiązanie optymalne problemu dla pierwszego stanu procesu. Jeśli l nie jest równe 0, przejdź do kroku 3.

6. Oblicz optymalne rozwiązanie problemu dla każdego kolejnego kroku procesu, przechodząc od końca obliczeń do początku.

Dynamika metody programów pozwala na zastąpienie jednego problemu z wieloma zmiennymi szeregiem kolejno rozwiązywanych problemów z mniejszą liczbą zmiennych. Decyzja jest podejmowana krok po kroku. Główną zasadą, na której opiera się optymalizacja procesu wieloetapowego, a także cechami metody obliczeniowej, jest zasada optymalności Bellmana.

Zachowanie optymalne ma tę właściwość, że niezależnie od stanu początkowego i decyzji początkowej, kolejne decyzje muszą być optymalne w stosunku do stanu wynikającego z decyzji początkowej.

Matematycznie jest to zapisane jako wyrażenie postaci:

fn-1(Sl)=optymalny(Rl+1(Sl,Ul+1)+fn-(l+1)(Sl+1)) (1)

(l=0,n-1)Optimum w wyrażeniu oznacza maksimum lub minimum w zależności od stanu problemu.

63. Wymagania dla problemów rozwiązywanych metodą DP

Programowanie dynamiczne to matematyczna metoda znajdowania optymalnych rozwiązań wieloetapowych problemów. Proces wieloetapowy to proces, który rozwija się w czasie i dzieli się na kilka kroków lub etapów.

Jedną z cech metody programowania dynamicznego jest to, że decyzje podejmowane w odniesieniu do procesów wieloetapowych nie są rozpatrywane jako pojedynczy akt, ale jako cały zespół powiązanych ze sobą decyzji. Ta sekwencja powiązanych ze sobą decyzji nazywana jest strategią.Celem planowania optymalnego jest wybór strategii, która zapewni najlepszy wynik pod względem wcześniej wybranego kryterium. Taką strategię nazywamy optymalną.

Inną ważną cechą metody jest niezależność optymalnej decyzji podjętej w kolejnym kroku od prehistorii, tj. w jaki sposób optymalizowany proces osiągnął swój obecny stan. Optymalne rozwiązanie jest wybierane tylko z uwzględnieniem czynników charakteryzujących proces w danym momencie.

Metoda programów dynamicznych charakteryzuje się również tym, że wybór optymalnego rozwiązania na każdym kroku powinien być dokonywany z uwzględnieniem jego konsekwencji w przyszłości. Oznacza to, że optymalizując proces na każdym kroku, w żadnym wypadku nie należy zapominać o wszystkich kolejnych krokach.

64. Ekonomiczne sformułowanie i konstrukcja modelu matematycznego problemu rozwiązywanego metodą DP (na przykładzie problemu dystrybucji inwestycji kapitałowych). Relacja rekurencyjna Bellmana.

Wyjaśnijmy wstępnie, że metodę programowania dynamicznego stosuje się przede wszystkim do tych problemów, w których optymalizowany proces (lub sytuacja) jest rozmieszczony w przestrzeni lub czasie, lub obu.

Niech sam proces (sytuacja) będzie na tyle skomplikowany, że nie ma możliwości jego optymalizacji znanymi metodami. Następnie, zgodnie z metodą programowania dynamicznego, ZŁOŻONY proces (operacja, sytuacja) jest dzielony (partycjonowany) na pewną liczbę etapów (kroków). Ten podział jest w wielu przypadkach naturalny, ale w ogólnym przypadku jest wprowadzany sztucznie. . Na przykład, rozważając jakąkolwiek partię szachów, każdy ruch każdego z graczy po prostu służy

rozbicie całej partii na osobne kroki (etapy). A w operacji wojskowej polegającej na ściganiu jednego pocisku przeciw drugiemu, cały ciągły proces musi być sztucznie podzielony na etapy, na przykład co sekundę obserwacji. Metoda programowania dynamicznego pozwala na zastąpienie optymalizacji całego złożonego procesu optymalizacją warunkową dla każdego z etapów

(kroki), po których następuje synteza optymalnej kontroli całego procesu. Jednocześnie metoda przewiduje, że optymalizacja warunkowa na osobnym kroku (etapie) jest dokonywana w interesie przede wszystkim całej operacji.

Wszystkie obliczenia umożliwiające znalezienie optymalnej wartości efektu osiągniętego w n krokach, fn(S0), przeprowadza się według wzoru (1), który nazywa się podstawowym funkcjonalnym równaniem Bellmana lub relacją rekurencji. Przy obliczaniu kolejnej wartości funkcji fn-1 wykorzystuje się otrzymaną w poprzednim kroku wartość funkcji fn-(l+1) oraz bezpośrednią wartość efektu Rl+1(Sl,Ul+1), uzyskany w wyniku wyboru rozwiązania Ul+1 dla danego stanu układów Sl. Proces obliczania wartości funkcji fn-1(l=0,n-1)

Przeprowadza się go w naturalnym stanie początkowym f0(Sn)=0, co oznacza, że ​​poza stanem końcowym układu efekt jest równy zeru.

65. Problem dystrybucji inwestycji kapitałowych (przykład).

Aby rozwiązać problem optymalnej dystrybucji inwestycji kapitałowych, użyjemy funkcjonalnego równania Bellmana. Najpierw za pomocą najprostszej sytuacji zilustrujemy wyprowadzenie równania funkcyjnego Bellmana, a następnie na przykładzie udowodnimy, jak wykorzystać to równanie do rozwiązania interesującego nas problemu.

Zacznijmy od optymalnego rozłożenia alokowanych inwestycji kapitałowych w wysokości K pomiędzy dwa przedsiębiorstwa. Działy planowania przedsiębiorstw na podstawie swoich obliczeń utworzyły funkcje dochodu q(x) dla przedsiębiorstwa P1 oraz h(x) dla przedsiębiorstwa P2. Funkcje te oznaczają, że jeśli pierwsze lub drugie przedsiębiorstwo otrzymuje inwestycję w wysokości x, to pierwsze przedsiębiorstwo

otrzymamy dochód q(x), a drugi h(x), a wartość x może przyjmować ciągłe lub znane wartości dyskretne od 0 do K.

Niech zatem firmie P1 przydzielone zostaną inwestycje kapitałowe w kwocie x, to firmie P2 zostanie przydzielona kwota K - x. W tym przypadku dochód q(x) uzyskamy z pierwszego przedsiębiorstwa, a h(K - x) z drugiego. Jeżeli inwestycje K zostały rozdysponowane na jeden okres planowania, to całkowity dochód z dwóch przedsiębiorstw wyniesie R(K, x) = q(x) + h(K - x). Oczywiście x i odpowiednio K - x muszą być tak dobrane, aby R(K, x) przybrało swoją maksymalną wartość, którą oznaczamy przez F(K):

Ten wpis jest jak szkielet dla bardziej kompletnych wpisów.

funkcjonalne równanie Bellmana. KOMPLIKUJ nasze zadanie, rozkładając inwestycje kapitałowe na dwa okresy planowania (dwa etapy) . Załóżmy, że wstępnie postanowimy przydzielić kwotę x pierwszemu przedsiębiorstwu P1, a x drugiemu przedsiębiorstwu P1. Ogólnie rzecz biorąc, dochód byłby równy R(K, x) = q(x) +

h(K-x). Jeśli weźmiemy pod uwagę, że inwestycje są rozłożone na 2 okresy (2 etapy), to w pierwszym przedsiębiorstwie saldo inwestycji wyniesie x, gdzie , a w drugim - .(K - x), gdzie Odpowiednio dochód dla drugi okres będzie wynosił q( .x) - według pierwszego obiektu i h[.(K - x)] - według drugiego. Dynamiczna optymalizacja programowania zaczyna się z reguły od etapu końcowego. Dlatego zaczynamy od drugiego etapu, oznaczając F1 maksymalny możliwy dochód z dwóch przedsiębiorstw w drugim

scena. Dostawać

Następnie do rozważanego ostatniego (w naszym przypadku drugiego) etapu dodajemy niejako poprzedni (w naszym przypadku pierwszy) etap i razem znajdujemy maksymalny dochód z obu etapów:

Podobnie dla n etapów otrzymujemy

gdzie Fn-1 jest funkcją celu, która daje najlepszy wynik dla ostatnich (n - 1) etapów. Otrzymane funkcjonalne równanie Bellmana jest powtarzalne, tj. kojarzy wartość Fn z wartością Fn-1.

Mówiąc bardziej ogólnie, równanie Bellmana ma postać

gdzie , Fn-1 - maksymalny dochód dla (n - 1) ostatnich etapów, Fn -

maksymalny dochód dla wszystkich n etapów.

66. Koncepcja rozwiązywania problemów programowania nieliniowego

Niech problem programowania nieliniowego zostanie postawiony w następującej ogólnej postaci: znajdź takie wartości zmiennych x1, x2, ..., xn, które spełniają warunki:

i doprowadzić wymagane ekstremum (maksimum lub minimum) funkcji celu

f = f(x1, x2,…, xn), (13.2)

gdzie f(х1, …, хn) i qi(х1, …, хn) (m , 1 i =) są rzeczywiste nieliniowe,

funkcje regularne n zmiennych rzeczywistych.

Zgodnie z ich ogólnymi właściwościami, problemy programowania nieliniowego mogą

znacznie różnią się od liniowych. Na przykład dziedzina wykonalnych rozwiązań może już nie być wypukła, a ekstremum funkcji celu można zaobserwować w dowolnym punkcie dziedziny wykonalnej. Metody rozwiązywania problemów nieliniowych również znacznie się różnią. Rozważmy tylko niektóre podejścia do rozwiązania tych problemów.

Przede wszystkim podejście graficzne sprawdza się również przy rozwiązywaniu najprostszych problemów programowania nieliniowego. Jeśli więc argumentami problemu są zmienne x1 i x2, to najpierw na płaszczyźnie tych zmiennych budowany jest obszar możliwych rozwiązań, a następnie wyznaczany jest optymalny punkt w obszarze za pomocą poziomów funkcji celu f(x1,x2).

W programowaniu nieliniowym do rozwiązywania wielu problemów stosuje się podejście gradientowe. Istnieje szereg metod gradientowych, których istotą jest znalezienie optymalnego wyniku za pomocą gradientu funkcji celu – wektora wskazującego kierunek maksymalnego wzrostu celu dla rozpatrywanego punktu. W ogólnym przypadku procedura wyszukiwania odbywa się w trybie iteracyjnym od punktu początkowo wybranego do punktów o najlepszym wskaźniku. Niech np. - dziedzina dopuszczalnych rozwiązań

rozważanego problemu, a iteracyjny proces obliczeń rozpoczyna się od punktu

Ponadto najpierw następuje przejście wzdłuż gradientu funkcji celu, a następnie powrót do obszaru. wzdłuż gradientu do zaburzonej granicy regionu O2 O3. 13.3 pokazano tak, że Ai o indeksach nieparzystych należy do obszaru, a punkty Ai o indeksach parzystych nie.W miarę zbliżania się do optymalnego punktu Q kierunki gradientów roboczych zbiegają się. Dlatego idealnym kryterium zatrzymania procesu będzie współliniowość gradientu docelowego i gradientu granicznego przerwanej.

67. Pojęcie programowania parametrycznego i całkowitoliczbowego .

Rachunek i model matematyczny ZCLP.

W problemach z niepodzielnymi obiektami na zmienne nakładane są warunki całkowitoliczbowe. Czasami te warunki odnoszą się do wszystkich zmiennych, czasami do niektórych zmiennych.Rozważ problem całkowicie całkowity

f=(n,j=1)∑CjXi maks

(n,j=1)∑AijXj=bi, i=1,m

xi-liczba całkowita,j=1,n

Teraz, w przeciwieństwie do ogólnego problemu programowania liniowego, plan optymalny niekoniecznie musi znajdować się w wierzchołku wielościanu planu.Istnieją następujące metody rozwiązywania problemów całkowitoliczbowych:

1. Metody przycinania

2.Kombinatoryczny

3.Przybliżone metody..

Programowanie parametryczne jest działem programowania matematycznego zajmującym się badaniem problemów optymalizacyjnych, w których warunki dopuszczalności i funkcja celu zależą od pewnych parametrów deterministycznych.

Definicja. Programowanie liniowe (LP) - nauka o metodach badawczych i znajdowaniu ekstremalnych (maksymalnych i minimalnych) wartości funkcji liniowej, na której niewiadome nakładane są ograniczenia liniowe.

Ta funkcja liniowa nazywa się cel, i nazywane są ograniczenia, które są matematycznie zapisane jako równania lub nierówności system ograniczeń.

Definicja. Nazywa się matematyczne wyrażenie funkcji celu i jej ograniczeń matematyczny model problemu ekonomicznego.

Ogólnie rzecz biorąc, model matematyczny problemu programowania liniowego (LP) jest zapisany jako

z ograniczeniami:

Gdzie x j- nieznany; aj, b ja, cj podane są stałe.

Wszystkie lub niektóre równania układu ograniczeń można zapisać jako nierówności.

Model matematyczny w krótszej notacji ma postać

z ograniczeniami:

Definicja. Wykonalnym rozwiązaniem (planem) problemu programowania liniowego jest wektor = ( X 1 , X 2 ,..., xp), spełnienie systemu ograniczeń.

Zbiór rozwiązań dopuszczalnych tworzy obszar rozwiązań dopuszczalnych (ODD).

Definicja. Dopuszczalne rozwiązanie, w którym funkcja celu osiąga swoją wartość ekstremalną, nazywamy optymalnym rozwiązaniem problemu programowania liniowego i oznaczamy opt.

Podstawowe dopuszczalne rozwiązanie (X 1 , X 2 ,..., X R , 0, …, 0) jest rozwiązaniem odniesienia, gdzie R- stopień systemu ograniczeń.

Model matematyczny problemu LP może być kanoniczny i niekanoniczny.

7. Rozwiązywanie zadań programowania liniowego metodą graficzną. Wykresy funkcji ograniczeń. Linie poziomu.

Graficzna metoda rozwiązywania problemów programowania liniowego

Najprostszą i najbardziej wizualną metodą programowania liniowego jest metoda graficzna. Służy do rozwiązywania problemów LP z dwiema zmiennymi podanymi w postaci niekanonicznej i wieloma zmiennymi w postaci kanonicznej, pod warunkiem, że zawierają one nie więcej niż dwie zmienne wolne.

Z geometrycznego punktu widzenia w zadaniu programowania liniowego szuka się takiego punktu narożnego lub zbioru punktów z dopuszczalnego zbioru rozwiązań, na którym osiągana jest najwyższa (dolna) linia poziomu, położona dalej (bliżej) niż inne w kierunku najszybszego wzrostu.

Aby znaleźć ekstremalną wartość funkcji celu w graficznym rozwiązaniu problemów LP, stosuje się wektor Ł() na powierzchni X 1 OH 2 , które oznaczamy . Ten wektor pokazuje kierunek najszybszej zmiany funkcji celu. Innymi słowy, wektor jest normalną linii poziomu Ł()

Gdzie mi 1 i mi 2 - wektory jednostkowe wzdłuż osi WÓŁ 1 i WÓŁ odpowiednio 2; zatem = (∂L/∂х 1 , ∂L/∂х 2 ). Współrzędne wektora są współczynnikami funkcji celu L(). Konstrukcja linii poziomu zostanie szczegółowo rozważona przy rozwiązywaniu problemów praktycznych.

Algorytm rozwiązywania problemów

1. Znajdujemy obszar możliwych rozwiązań dla układu ograniczeń problemu.

2. Budowanie wektora .

3. Narysuj poziomą linię Ł 0 , który jest prostopadły .

4. Przesuwamy linię poziomu w kierunku wektora zadań do maksimum iw przeciwnym kierunku , do zadań minimalnych.

Linię poziomu przesuwa się tak długo, aż będzie miała tylko jeden wspólny punkt z obszarem możliwych rozwiązań. Ten punkt, który określa jednoznaczność rozwiązania problemu LP, będzie punktem ekstremalnym.

Jeśli okaże się, że linia poziomu jest równoległa do jednego z boków ODT, to w tym przypadku ekstremum zostanie osiągnięte we wszystkich punktach odpowiedniego boku, a problem LP będzie miał nieskończoną liczbę rozwiązań. Podobno taki problem LP ma alternatywa optymalna a jego rozwiązanie daje wzór:

gdzie 0 ≤ T≤ 1, 1 i 2 - optymalnych rozwiązań w punktach narożnych ODS.

Problem LP może być nierozwiązywalny, gdy ograniczenia, które go definiują, okazują się sprzeczne.

5. Znajdujemy w nim współrzędne punktu ekstremalnego i wartość funkcji celu.

Przykład 3 Wybór najlepszej opcji wydania produktu

Firma produkuje 2 rodzaje lodów: śmietankowe i czekoladowe. Do produkcji lodów stosuje się dwa produkty wyjściowe: mleko i nadzienia, których koszt na 1 kg lodów i dziennych zapasów podano w tabeli.

Badania rynku wykazały, że dzienne zapotrzebowanie na lody maślane przewyższa zapotrzebowanie na lody czekoladowe, ale nie więcej niż o 100 kg.

Ponadto stwierdzono, że zapotrzebowanie na lody czekoladowe nie przekracza 350 kg dziennie. Cena detaliczna 1 kg kremowych lodów wynosi 16 rubli, czekolada - 14 rubli.

Ile każdego rodzaju lodów powinna wyprodukować firma, aby zmaksymalizować przychody ze sprzedaży?

Rozwiązanie. Oznaczać: X 1 - dzienna wielkość produkcji lodów śmietankowych, kg; X 2 - dzienna produkcja lodów czekoladowych, kg.

Zróbmy matematyczny model problemu.

Znane są ceny lodów: odpowiednio 16 rubli i 14 rubli, więc funkcja celu będzie wyglądać następująco:

Ustaw limity na mleko do lodów. Jego zużycie na lody śmietankowe wynosi 0,8 kg, na lody czekoladowe - 0,5 kg. Zapas mleka 400kg. Zatem pierwsza nierówność będzie wyglądać następująco:

0,8x 1 + 0,5x 2 ≤400 - pierwsza nierówność jest ograniczeniem. Pozostałe nierówności są skonstruowane w podobny sposób.

Rezultatem jest system nierówności. jaki jest obszar rozwiązania każdej nierówności. Można to zrobić, podstawiając współrzędne punktu O(0:0) do każdej z nierówności. W rezultacie otrzymujemy:

Postać OABDEF- dziedzina dopuszczalnych rozwiązań. Budujemy wektor (16; 14). linia poziomu Ł 0 jest określone równaniem 16x 1 +14x 2 =Const. Wybieramy dowolną liczbę, np. liczbę 0, a następnie 16x 1 +14x 2 = 0. Na rysunku dla prostej L 0 wybrano pewną liczbę dodatnią, różną od zera. Wszystkie linie poziomu są do siebie równoległe. Wektor normalny linii poziomu.

Przesuń linię poziomu w kierunku wektora. punkt wyjścia Ł Chodzi o 0 z obszaru dopuszczalnych rozwiązań D, jego współrzędne określa się jako przecięcie prostych podanych równaniami:

Rozwiązując układ, otrzymujemy współrzędne punktu D(312,5; 300), w którym znajdzie się rozwiązanie optymalne, tj.

Tym samym firma musi dziennie wyprodukować 312,5 kg lodów maślanych i 300 kg lodów czekoladowych, a przychód ze sprzedaży wyniesie 9200 rubli.

8. Sprowadzenie dowolnego problemu programowania liniowego do problemu głównego. Przekształcanie ograniczeń wynikających z nierówności na odpowiadające im równania.

9. Metoda simpleksowa. Charakterystyka i algorytm metody, jej stosowalność.

Aby rozwiązać problem metodą simplex, jest to konieczne:

1. Wskaż metodę znalezienia optymalnego rozwiązania wzorcowego

2. Określ sposób przejścia z jednego rozwiązania wzorcowego do drugiego, na którym wartość funkcji celu będzie bliższa optymalnej, tj. wskazać sposób ulepszenia rozwiązania wzorcowego

3. Ustaw kryteria, które pozwolą ci w odpowiednim czasie zatrzymać wyliczanie rozwiązań referencyjnych dla rozwiązania optymalnego lub wyciągnąć wniosek o braku optymalnego rozwiązania.

Algorytm metody simplex rozwiązywania problemów programowania liniowego

1. Sprowadź problem do postaci kanonicznej

2. Znajdź początkowe rozwiązanie podporowe z „podstawą jednostkową” (jeśli nie ma rozwiązania podporowego, to problem nie ma rozwiązania, ze względu na niezgodność systemu ograniczeń)

3. Oblicz oszacowania rozwinięć wektorowych względem bazy rozwiązania wzorcowego i uzupełnij tabelę metody simpleks

4. Jeżeli kryterium jednoznaczności rozwiązania optymalnego jest spełnione, to rozwiązanie problemu się kończy

5. Jeżeli spełniony jest warunek istnienia zbioru rozwiązań optymalnych, to przez proste wyliczenie znajdują się wszystkie rozwiązania optymalne

10. Zadanie transportowe. Definicja, rodzaje, metody znajdowania początkowego rozwiązania problemu transportowego.

Problem transportu jest jednym z najczęstszych problemów programowania liniowego. Jej celem jest wypracowanie najbardziej racjonalnych sposobów i środków transportu towarów, eliminujących zbyt dalekobieżne, nadjeżdżające, powtarzające się przewozy.

1. Znalezienie początkowego rozwiązania odniesienia;

2. Sprawdzenie optymalności tego rozwiązania;

3. Przejście od jednego podstawowego rozwiązania do drugiego.

Wykład 2

W Forma kanoniczna

dopuszczalne rozwiązanie PLP(akceptowalny plan).

optymalne rozwiązanie LLP.

Konieczność

Przykład.

Wpiszmy problem Forma kanoniczna

Sytuacje szczególne rozwiązania graficznego ZLP

Z wyjątkiem sytuacji, gdy zadanie jest jedyne optymalne rozwiązanie dla i , może być specjalne sytuacje:

1. zadanie ma nieskończoną liczbę rozwiązań optymalnych – na odcinku osiągnięto ekstremum funkcji ( alternatywa optymalna)- Rysunek 2;

2. zadanie nie do rozwiązania z uwagi na nieograniczoność ODR, lub - Rysunek 3;

3. ODR- pojedyńczy punkt Ach, więc;

4. zadanie nie do rozwiązania jeśli ODR ma pusty obszar.

A

Rycina 2 Rycina 3

Jeżeli linia poziomu jest równoległa do boku obszaru możliwych rozwiązań, to ekstremum zostaje osiągnięte we wszystkich punktach boku. Problem ma nieskończoną liczbę optymalnych rozwiązań - alternatywa optymalna . Optymalne rozwiązanie można znaleźć według wzoru

gdzie jest parametr. Dla dowolnej wartości od 0 do 1 można uzyskać wszystkie punkty odcinka, dla których funkcja przyjmuje tę samą wartość. Stąd nazwa - alternatywna optymalna.

Przykład. Rozwiąż graficznie problem programowania liniowego ( alternatywa optymalna):

Pytania do samokontroli

1. Zapisz problem programowania liniowego w postaci ogólnej.

2. Zapisz problem programowania liniowego w postaci kanonicznej i standardowej.

3. Jakich przekształceń można użyć, aby przejść od ogólnej lub standardowej postaci problemu programowania liniowego do postaci kanonicznej?

4. Podaj definicję możliwych i optymalnych rozwiązań problemu programowania liniowego.

5. Które z rozwiązań jest „najlepsze” dla problemu minimalizacji funkcji if ?

6. Które z rozwiązań jest „najlepsze” dla problemu maksymalizacji funkcji if ?

7. Zapisz postać standardową modelu matematycznego problemu programowania liniowego z dwiema zmiennymi.

8. Jak skonstruować półpłaszczyznę daną nierównością liniową z dwiema zmiennymi ?

9. Jak nazywa się rozwiązanie układu nierówności liniowych z dwiema zmiennymi? Skonstruować na płaszczyźnie dziedzinę dopuszczalnych rozwiązań takiego układu nierówności liniowych, który:

1) ma unikalne rozwiązanie;

2) ma nieskończony zbiór rozwiązań;

3) nie ma rozwiązania.

10. Napisz dla funkcji liniowej gradient wektorowy, nazwij rodzaj linii poziomu. W jaki sposób linie gradientu i poziomu są rozmieszczone względem siebie?

11. Sformułuj algorytm graficznej metody rozwiązywania standardowego LLP z dwiema zmiennymi.

12. Jak znaleźć współrzędne i wartości rozwiązania, ?

13. Skonstruować obszar możliwych rozwiązań, linie gradientu i poziomu, dla problemów programowania liniowego, w których:

1) osiągana jest w jednym punkcie, oraz - na odcinku ODR;

2) jest osiągany w jednym punkcie ODS, oraz .

14. Podaj ilustrację geometryczną LLP, jeśli:

1) ma unikalne optymalne rozwiązania dla i ;

2) posiada zbiór optymalnych rozwiązań dla .

Wykład 2

Graficzna metoda znajdowania optymalnego rozwiązania

1. Postacie liniowych modeli matematycznych i ich transformacja

2. Graficzna metoda rozwiązywania problemu programowania liniowego

3. SYTUACJE SZCZEGÓLNE ROZWIĄZANIA GRAFICZNEGO LLP

4. Graficzne rozwiązanie problemów ekonomicznych programowania liniowego

Formy liniowych modeli matematycznych i ich transformacja

Model matematyczny problemu programowania liniowego (LPP) można zapisać w jednej z trzech postaci.

W ogólna postać modelu matematycznego wymagane jest znalezienie maksimum lub minimum funkcji celu; system ograniczeń zawiera nierówności i równania; nie wszystkie zmienne mogą być nieujemne.

W Forma kanoniczna model matematyczny musi znaleźć maksimum funkcji celu; system ograniczeń składa się tylko z równań; wszystkie zmienne są nieujemne.

W standardowej postaci modelu matematycznego wymagane jest znalezienie maksimum lub minimum funkcji; wszystkie ograniczenia są nierównościami; wszystkie zmienne są nieujemne.

Nazywa się rozwiązanie układu ograniczeń, które spełnia warunki nieujemności zmiennych dopuszczalne rozwiązanie PLP(akceptowalny plan).

Zbiór dopuszczalnych rozwiązań nazywa się obszar możliwych rozwiązań LLP.

Nazywa się możliwe rozwiązanie, w którym funkcja celu osiąga wartość ekstremalną optymalne rozwiązanie LLP.

Trzy formy LLP są równoważne w tym sensie, że każdą z nich można sprowadzić do innej postaci za pomocą przekształceń matematycznych.

Konieczność przejście od jednej formy modelu matematycznego do drugiej związane z metodami rozwiązywania problemów: na przykład metoda simplex, szeroko stosowana w programowaniu liniowym, jest stosowana do problemu zapisanego w postaci kanonicznej, a metoda graficzna do standardowej postaci modelu matematycznego.

Przejście do notacji kanonicznej ZLP.

Przykład.

Wpiszmy problem Forma kanoniczna, wprowadzając dodatkową zmienną (bilansującą) ze znakiem „+” po lewej stronie pierwszej nierówności układu ograniczeń oraz dodatkową zmienną ze znakiem „minus” po lewej stronie drugiej nierówności.

Ekonomiczne znaczenie różnych dodatkowych zmiennych może nie być takie samo: zależy to od ekonomicznego znaczenia ograniczeń, w których te zmienne są uwzględnione.

Tak więc w problemie zużycia surowców pokazują pozostałą część surowców, aw problemie wyboru optymalnych technologii pokazują niewykorzystany czas przedsiębiorstwa stosującego określoną technologię; w problemie cięcia - uwalnianie półfabrykatów o określonej długości przekraczającej plan itp.