Graficzna metoda rozwiązywania problemów programowania liniowego

W tej lekcji zapoznamy się z graficzną metodą rozwiązywania zadania programowania liniowego to znaczy takie problemy, w których wymagane jest znalezienie takich rozwiązań układu równań liniowych i (lub) nierówności (system ograniczeń), w których funkcja celu - funkcja liniowa - przyjmuje wartość optymalną.

Ze względu na to, że wizualizację rozwiązania graficznego uzyskuje się tylko na płaszczyźnie, możemy zapoznać się z graficzną reprezentacją problemu tylko w przestrzeni dwuwymiarowej. Ta reprezentacja jest odpowiednia dla systemu ograniczeń nierówności z dwiema zmiennymi lub dla układów równań, w których liczba zmiennych o 2 przekracza liczbę równań, to znaczy liczba wolnych zmiennych jest równa dwa.

Dlatego metoda graficzna ma tak wąski zakres zastosowania, że ​​nie można mówić o niej jako specjalnej metodzie rozwiązywania problemów programowania liniowego.

Jednak w celu opracowania wizualnych reprezentacji rozwiązań problemów programowania liniowego, metoda graficzna jest szczególnie interesująca. Ponadto pozwala na geometryczne potwierdzenie ważności twierdzenie programowania liniowego .

Wśród linii prostych wspomnianej rodziny równoległych linii prostych są mn (zielony) i MN (czerwony), które nazywamy odniesieniem. Linie pomocnicze są zwykle nazywane liniami, które mają co najmniej jeden wspólny punkt z wielokątem ABCDE , a wielokąt ABCDE leży całkowicie po jednej stronie tej linii. Jak widać na rysunku, linia prosta mn jest odniesieniem, ponieważ dotyka wielokąta w punkcie A, a cały wielokąt leży na prawo (lub wyżej) tej linii prostej. Linia MN jest również odniesieniem, ponieważ ma wspólny punkt C z wielokątem, a wielokąt leży całkowicie na lewo od tej linii.

Głównie twierdzenie programowania liniowego Wiadomo, że forma liniowa osiąga wartości maksymalne i minimalne w skrajnych punktach wielościanu roztworów. Oznacza to, że linie odniesienia mn i MN charakteryzują skrajne wartości formy liniowej (funkcja celu), to znaczy w punktach A i C forma liniowa osiąga wartości optymalne. W punkcie A , który jest bliżej początku, funkcja celu osiąga swoją minimalną wartość, aw punkcie C , który jest dalej od początku, osiąga swoją maksymalną wartość.

1. Zbuduj wielobok rozwiązań systemu nierówności.

4. Idąc dalej, dojdziemy do pewnej pozycji odniesienia, gdy linia prosta będzie miała jeden wspólny punkt. z rozwiązaniami wielokątów. W tym momencie funkcja celu osiąga maksimum.

5. Jeśli początkowo skonstruowana linia o równych wartościach przecina wielokąt rozwiązania, wówczas funkcja celu osiąga minimalną wartość w wierzchołku wielokąta położonego bliżej początku współrzędnych, a maksymalną wartość w wierzchołku bardziej oddaloną od początku.

Przykład 1. Za pomocą metody graficznej rozwiąż problem programowania liniowego, w którym chcesz znaleźć maksimum funkcji. z ograniczeniami

Skonstruuj wielokąt rozwiązań. Aby to zrobić, narysuj linie graniczne. Od pierwszej nierówności piszemy równanie . Jest to równanie pierwszej linii granicznej. Znajdź punkty przecięcia tej linii z osiami współrzędnych. Z z równania, które otrzymujemy na dostanie . Oznacza to, że pierwsza prosta linia odcina segmenty od osi współrzędnych. i .

Podobnie konstruujemy pozostałe linie graniczne. Druga linia prosta od osi współrzędnych odcina segmenty równe 6. Trzecia linia prosta biegnie równolegle do osi odcięcie na osi segment jest równy 2. Czwarta linia prosta ma równanie . Zbiega się z osią .

Z poniższego rysunku widać, że zestaw punktów czworobocznego ABDE spełnia wszystkie cztery nierówności systemu.

W związku z tym czworoboczny ABDE jest wielokątem rozwiązań systemu (zacienionych do wewnątrz).

Narysuj linię równych wartości funkcji celu. Biorąc pod uwagę równość F = 1, stwierdzamy, że ta linia odcina odpowiednio segmenty 1 i 1/3 na osi i na osi . Narysujmy linię prostą przez te punkty (na rysunku jest czarna).

Przesuwanie tej linii równolegle do siebie w kierunku gradientu - wektor (burgund), dostajemy linie pomocnicze. Pierwsza prosta (zielona) ma wspólny punkt z wielokątem A. Tutaj funkcja celu osiąga swoje minimum. Idąc dalej, dochodzimy do punktu B. Oto maksimum. Współrzędne punktu B : (2, 4). Zastępując w funkcji celu współrzędne punktu B , tj. , , uzyskujemy maksymalną wartość funkcji celu: .

Strona ma Kalkulator online do rozwiązywania problemów programowania liniowego metodą simpleks .

Przykład 3. Rozwiąż problem programowania liniowego, w którym chcesz znaleźć maksimum funkcji za pomocą metody graficznej. z ograniczeniami

gdzie .

Właściwa decyzja i odpowiedź .

Przykład 4. Korzystając z metody graficznej, rozwiąż problem programowania liniowego, w którym chcesz znaleźć minimum funkcji. z ograniczeniami

gdzie .

Właściwa decyzja i odpowiedź .

Jak dotąd ustalenia opierają się na fakcie, że zestaw rozwiązań problemu programowania liniowego jest skonfigurowany tak, aby optymalne rozwiązanie było oczywiście i unikalne. Teraz rozważ przykłady, gdy ten warunek jest naruszony. W tych przykładach wielobok rozwiązania jest skonstruowany w sposób pokazany w poprzednich przykładach, skupmy się na cechach, które wyróżniają te wyjątkowe przykłady.

Przykład 5. Rozwiąż problem programowania liniowego, w którym chcesz znaleźć maksimum funkcji za pomocą metody graficznej z ograniczeniami

Decyzja. Rysunek pokazuje: nieograniczony, wieloaspektowy region rozwiązań dla tego systemu więzów, początkową linię poziomu (czarny), wektor (bordowy) wskazujący kierunek ruchu początkowej linii poziomu, aby znaleźć maksimum funkcji celu.

Łatwo zauważyć, że funkcja F może wzrastać w nieskończoność w danym systemie ograniczeń, dlatego możemy warunkowo napisać to .

Strona ma Kalkulator online do rozwiązywania problemów programowania liniowego metodą simpleks .

Przykład 6. Rozwiąż problem programowania liniowego, w którym chcesz znaleźć maksimum funkcji za pomocą metody graficznej z ograniczeniami

Decyzja. Obszar pokazany na poniższym rysunku nie zawiera żadnych punktów wspólnych, które spełniałyby wszystkie nierówności systemu więzów. Oznacza to, że system ograniczeń jest sprzeczny i nie może zawierać jednego rozwiązania, w tym rozwiązania optymalnego.

Strona ma Kalkulator online do rozwiązywania problemów programowania liniowego metodą simpleks .

Strona ma Kalkulator online do rozwiązywania problemów programowania liniowego metodą simpleks .

Przykład 8. Korzystając z metody graficznej, rozwiąż problem programowania liniowego, w którym chcesz znaleźć maksimum funkcji. z ograniczeniami

Decyzja. Poniższy rysunek przedstawia obszar rozwiązania systemu ograniczeń i linii poziomu (czarny). Jeśli przesuniesz linię poziomą równolegle do oryginału w kierunku wektora wtedy opuści domenę rozwiązania nie w jednym punkcie, jak to było w poprzednich przykładach, ale połączy się z bezpośrednim CD , który jest linią graniczną domeny rozwiązania.

Wszystkie punkty segmentu CD dają taką samą wartość funkcji celu, która służy jako jego optymalna wartość: . W konsekwencji nie ma jednej, ale nieskończonej liczby optymalnych rozwiązań, które pokrywają się z punktami segmentowego CD , w szczególności z dwoma punktami narożnymi C i D. Ten przykład pokazuje, że w niektórych przypadkach naruszana jest wyjątkowość optymalnego rozwiązania.

Strona ma Kalkulator online do rozwiązywania problemów programowania liniowego metodą simpleks .

Na koniec należy zauważyć, że można również skonstruować wielościan rozwiązań w inny sposób, który różni się od tego, który rozważaliśmy. Mianowicie: nie możesz szukać punktu przecięcia linii prostych z osiami współrzędnych, ale szukaj punktu przecięcia linii prostych. W tym celu układy dwóch równań są rozwiązywane kolejno, tak że punkty przecięcia wszystkich linii są rozwiązaniami. Uzyskane punkty będą wierzchołkami wielościanu roztworów. Ta metoda jest czasami wygodna w przypadkach, gdy punkty przecięcia linii z osiami współrzędnych są liczbami ułamkowymi i, niepoprawnie odkładając punkt przecięcia, można uzyskać błąd w poszukiwaniu punktów przecięcia samych linii.

Początek tematu „Programowanie liniowe”

Udostępnij znajomym