Znajdź maksimum funkcji metodą simplex. Metoda simpleksowa rozwiązywania problemów programowania liniowego
Jeżeli stwierdzenie problemu zawiera ograniczenia ze znakiem ≥, to można je sprowadzić do postaci ∑a ji b j, mnożąc obie strony nierówności przez -1. Wprowadźmy m dodatkowych zmiennych x n+j ≥0(j =1,m) i przekształćmy ograniczenia do postaci równości
(2)
Załóżmy, że wszystko jest początkowe zmienne zadania x 1 , x 2 ,..., x n – niepodstawowe. Wtedy zmienne dodatkowe będą podstawowe, a konkretne rozwiązanie układu więzów będzie miało postać
x 1 = x 2 = ... = x n = 0, x n+ jot = b jot, j =1,m. (3)
Ponieważ w tym przypadku wartość funkcji celu F 0 = 0, możemy przedstawić F(x) w następujący sposób:
F(x)=∑c ja x ja +F 0 =0 (4)
Początkowa tabela simpleksowa (tabela simpleksowa 1) jest tworzona na podstawie równań (2) i (4). Jeżeli dodatkowe zmienne x n+j zostaną poprzedzone znakiem „+”, jak w (2), to wszystkie współczynniki przed zmiennymi x i oraz członem wolnym b j zostaną wpisane do tablicy sympleksowej bez zmian. Przy maksymalizacji funkcji celu współczynniki wpisuje się w dolnym wierszu tabeli sympleksowej z przeciwnymi znakami. Terminy swobodne w tabeli simplex określają rozwiązanie problemu.
Algorytm rozwiązania problemu jest następujący:
1. krok. Wyświetlani są członkowie kolumny wolnych członków. Jeśli wszystkie są pozytywne, wówczas jest to dopuszczalne podstawowe rozwiązanie znalezione i należy przejść do kroku 5 algorytmu, odpowiadającego znalezieniu rozwiązania optymalnego. Jeżeli początkowa tabela simpleks zawiera ujemne terminy wolne, wówczas rozwiązanie jest nieprawidłowe i należy przejść do kroku 2.
2. krok. Aby znaleźć dopuszczalne rozwiązanie, przeprowadza się je i należy zdecydować, którą ze zmiennych niepodstawowych uwzględnić w bazie, a którą zmienną usunąć z bazy.
Tabela 1.
| podstawowe zmienne | Bezpłatni członkowie z ograniczeniami | Zmienne niepodstawowe | |||||
| x 1 | x 2 | ... | x l | ... | x rz|||
| xn+1 | b 1 | 11 | 12 | ... | 1l | ... | 1n |
| xn+2 | b 2 | 21 | 22 | ... | 2l | ... | 2n |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| x n+r | b2 | r1 | r2 | ... | rl | ... | Arn |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| x n+m | b m | m1 | m2 | ... | ml | ... | miesiąc |
| F(x)maks | F 0 | -c 1 | -c 2 | ... | -c 1 | ... | -c rz |
Aby to zrobić, wybierz dowolny z elementów ujemnych kolumny wyrazów wolnych (niech będzie to b 2 wiodący lub rozwiązujący. Jeśli w wierszu z ujemnym wyrazem wolnym nie ma elementów ujemnych, to system ograniczeń jest niespójny i problem nie ma rozwiązania.
Jednocześnie z BP wyklucza się zmienną, która jako pierwsza zmieni znak, gdy wybrany NP x l wzrośnie. Będzie to x n+r, którego indeks r jest określony na podstawie warunku
te. zmienna, która ma najmniejszy stosunek wolnego terminu do elementu wybranej kolumny wiodącej. Ten związek nazywa się relacja simplex. Należy brać pod uwagę tylko pozytywne relacje sympleksowe.
Wywoływana jest linia odpowiadająca zmiennej x n+r prowadzić lub pozwalać. Element tabeli simplex a rl, znajdujący się na przecięciu wiodącego wiersza i wiodącej kolumny, nazywany jest elementem wiodącym lub rozwiązującym. Znalezienie elementu wiodącego kończy pracę z każdą zwykłą tabelą simplex.
Trzeci krok. Obliczana jest nowa tablica simplex, której elementy są przeliczane z elementów tablicy simplex z poprzedniego kroku i oznaczane liczbą pierwszą, tj. b" j , a" ji , c" i , F" 0 . Elementy są przeliczane przy użyciu następujących wzorów:
Najpierw nowa tabela jednostronna wypełni wiersz i kolumnę, które prowadziły w poprzedniej tabeli jednostronnej. Wyrażenie (5) oznacza, że element a" rl w miejscu elementu wiodącego jest równy odwrotności elementu poprzedniej tablicy sympleksowej. Elementy wiersza a ri są dzielone przez element wiodący, a elementy kolumna a jl jest również dzielona przez element wiodący, ale z przeciwnym znakiem. Elementy b” r i c” l są obliczane według tej samej zasady.
Pozostałe formuły można łatwo zapisać za pomocą .
Prostokąt skonstruowany jest według starej tablicy sympleksowej w taki sposób, że jedną z jego przekątnych tworzą elementy przeliczone (a ji) i wiodące (a rl) (rys. 1). Druga przekątna jest określona jednoznacznie. Aby znaleźć nowy element a" ji, od elementu a ji odejmuje się iloczyn elementów przeciwległej przekątnej podzielony przez element wiodący (jest to oznaczone znakiem "-" obok komórki). Elementy b" j, (j≠r) oraz c” i oblicza się ponownie w ten sam sposób. (i≠l).
4. krok. Analizę nowej tablicy simpleksowej rozpoczynamy od pierwszego kroku algorytmu. Akcja trwa do momentu znalezienia wykonalnego rozwiązania podstawowego, tj. wszystkie elementy kolumny pływakowej muszą być dodatnie.
5. krok. Uważamy, że znaleziono dopuszczalne rozwiązanie podstawowe. Przyglądamy się współczynnikom linii funkcji celu F(x) . Znakiem optymalności tablicy sympleksowej jest nieujemność współczynników dla zmiennych niepodstawowych w rzędzie F.
Ryż. 1. Reguła prostokąta
Jeśli wśród współczynników rzędu F znajdują się współczynniki ujemne (z wyjątkiem terminu wolnego), należy przejść do innego podstawowego rozwiązania. Przy maksymalizacji funkcji celu podstawą jest jedna ze zmiennych niepodstawowych (np. x l), której kolumna odpowiada maksymalnej wartości bezwzględnej ujemnego współczynnika c l w dolnym wierszu tabeli simplex. Pozwala to wybrać zmienną, której wzrost prowadzi do poprawy funkcji celu. Kolumna odpowiadająca zmiennej x l nazywana jest kolumną wiodącą. Jednocześnie z bazy wyłącza się zmienną x n+r, której indeks r wyznacza minimalna relacja sympleksowa:
Wiersz odpowiadający x n+r nazywa się wiodącym, a element tablicy sympleksowej a rl, znajdujący się na przecięciu wiersza wiodącego i kolumny wiodącej, nazywa się elementem wiodącym.
6. krok. zgodnie z zasadami opisanymi w kroku 3. Procedura trwa do momentu znalezienia optymalne rozwiązanie lub dochodzi do wniosku, że nie istnieje.
Jeśli podczas optymalizacji rozwiązania wszystkie elementy w kolumnie wiodącej nie będą dodatnie, wówczas nie będzie można wybrać wiersza wiodącego. W tym przypadku funkcja w obszarze dopuszczalnych rozwiązań problemu nie jest ograniczona powyżej i F max ->&∞.
Jeżeli na kolejnym etapie poszukiwania ekstremum jedną z podstawowych zmiennych stanie się równy zeru, wówczas odpowiednie rozwiązanie podstawowe nazywa się zdegenerowanym. W tym przypadku następuje tzw. cykliczność, charakteryzująca się tym, że ta sama kombinacja BP zaczyna się powtarzać z określoną częstotliwością (zachowana jest wartość funkcji F) i nie ma możliwości przejścia do nowego wykonalnego rozwiązania podstawowego . Pętla jest jedną z głównych wad metody simpleks, ale jest stosunkowo rzadka. W praktyce w takich przypadkach zwykle odmawiają wprowadzenia do bazy zmiennej, której kolumna odpowiada maksymalnej wartości bezwzględnej ujemnego współczynnika w funkcji celu, i dają losowy wybór nowe rozwiązanie podstawowe.
Przykład 1. Rozwiąż problem
max(F(x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤7; x 1 + 4x 2 ≥8; x 2 ≤4; x 1,2 ≥0)
Stosując metodę sympleksową podać interpretację geometryczną procesu rozwiązania.
Graficzną interpretację rozwiązania problemu przedstawiono na rys. 2. Maksymalna wartość funkcji celu osiągana jest w wierzchołku ODZP o współrzędnych . Rozwiążmy problem za pomocą tabel simpleksowych. Pomnóżmy drugie ograniczenie przez (-1) i wprowadźmy dodatkowe zmienne, aby nierówności sprowadzić do postaci równości, a następnie
Przyjmujemy zmienne początkowe x 1 i x 2 jako niepodstawowe, a dodatkowe x 3, x 4 i x 5 traktujemy jako podstawowe i tworzymy tabelę simpleksową (tabela simpleksowa 2). Rozwiązanie odpowiadające tabeli simplex. 2, jest nieważne; element wiodący jest zarysowany i wybrany zgodnie z krokiem 2 poprzedniego algorytmu. Poniższa tabela simplex. Ryc. 3 określa dopuszczalne rozwiązanie podstawowe, odpowiada mu wierzchołek ODZP na ryc. 1. 2 Zarysowano i wybrano element wiodący zgodnie z 5. krokiem algorytmu rozwiązywania problemu. Tabela 4 odpowiada optymalnemu rozwiązaniu problemu, zatem: x 1 = x 5 = 0; x2 = 4; x 3 = 3; x 4 = 8; Fmaks. = 20.
Ryż. 2. Rozwiązanie graficzne zadania
Do produkcji trzech rodzajów koszul wykorzystuje się nici, guziki i materiał. Zapasy nici, guzików i tkanin, normy ich zużycia do szycia jednej koszuli podano w tabeli. Znajdować maksymalny zysk I optymalnego planu wydanie produktów zapewniających to (znajdź).
| koszula 1 | koszula 2 | koszula 3 | Rezerwy | wątki (m.) | 1 | 9 | 3 | 96 | guziki (szt.) | 20 | 10 | 30 | 640 | tekstylny ( | 1 | 2 | 2 | 44 | Zysk (r.) | 2 | 5 | 4 |
Rozwiązanie problemu
Budowa modelu
Przez i liczba koszul pierwszego, drugiego i trzeciego typu przeznaczonych do wydania.
Wtedy ograniczenia zasobów będą wyglądać następująco:
Dodatkowo zgodnie ze znaczeniem zadania
Funkcja celu wyrażająca uzyskany zysk:
Otrzymujemy następujący problem programowania liniowego:
Sprowadzenie problemu programowania liniowego do postaci kanonicznej
Zmniejszmy problem do Forma kanoniczna. Wprowadźmy dodatkowe zmienne. Wszystkie dodatkowe zmienne wprowadzamy do funkcji celu ze współczynnikiem równym zero. Dodajemy po lewej stronie ograniczeń dodatkowe zmienne, które nie mają preferowanej formy i otrzymujemy równości.
Rozwiązanie problemu metodą simplex
Wypełnianie tabeli simplex:
Ponieważ rozwiązujemy problem do maksimum, obecność liczb ujemnych w linii indeksu przy rozwiązywaniu problemu do maksimum wskazuje, że nie uzyskaliśmy rozwiązania optymalnego i konieczne jest przejście od tabeli 0. iteracji do Następny.
Przechodzimy do kolejnej iteracji w następujący sposób:
odpowiada kolumna wiodąca
Kluczowy wiersz jest określony przez minimalny stosunek wolnych terminów i członków kolumny wiodącej (relacje simpleksowe):
Na przecięciu kolumny klucza i wiersza klucza znajdujemy element umożliwiający, tj. 9.
Teraz przystępujemy do kompilacji pierwszej iteracji: Zamiast wektora jednostkowego wprowadzamy wektor .
W nowy stół w miejsce elementu włączającego piszemy 1, wszystkie pozostałe elementy kolumny klucza są zerami. Kluczowe elementy ciągu są podzielone na element Enable. Wszystkie pozostałe elementy tabeli obliczane są przy użyciu reguły prostokąta.
Kolumna klucza dla pierwszej iteracji odpowiada
Elementem rozstrzygającym jest liczba 4/3. Wyprowadzamy wektor z podstawy i zamiast tego wprowadzamy wektor. Otrzymujemy tabelę drugiej iteracji.
Kolumna klucza dla drugiej iteracji odpowiada
Znajdujemy kluczową linię, w tym celu definiujemy:
Elementem rozstrzygającym jest liczba 10/3. Wyprowadzamy wektor z podstawy i zamiast tego wprowadzamy wektor. Otrzymujemy tabelę trzeciej iteracji.
| № | BP | c B | O.O | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | Simpleks | 2 | 5 | 4 | 0 | 0 | 0 | relacja | 0 | x 4 | 0 | 96 | 1 | 9 | 3 | 1 | 0 | 0 | 32/3 | x 5 | 0 | 640 | 20 | 10 | 30 | 0 | 1 | 0 | 64 | x 6 | 0 | 44 | 1 | 2 | 2 | 0 | 0 | 1 | 22 | Fj - do j | 0 | -2 | -5 | -4 | 0 | 0 | 0 | 1 | x 2 | 5 | 32/3 | 1/9 | 1 | 1/3 | 1/9 | 0 | 0 | 32 | x 5 | 0 | 1600/3 | 170/9 | 0 | 80/3 | -10/9 | 1 | 0 | 20 | x 6 | 0 | 68/3 | 7/9 | 0 | 4/3 | -2/9 | 0 | 1 | 17 | Fj - do j | 160/3 | -13/9 | 0 | -7/3 | 5/9 | 0 | 0 | 2 | x 2 | 5 | 5 | -1/12 | 1 | 0 | 1/6 | 0 | -1/4 | -- | x 5 | 0 | 80 | 10/3 | 0 | 0 | 10/3 | 1 | -20 | 24 | x 3 | 4 | 17 | 7/12 | 0 | 1 | -1/6 | 0 | 3/4 | 204/7 | Fj - do j | 93 | -1/12 | 0 | 0 | 1/6 | 0 | 7/4 | 3 | x 2 | 5 | 7 | 0 | 1 | 0 | 1/4 | 1/40 | -3/4 | x 1 | 2 | 24 | 1 | 0 | 0 | 1 | 3/10 | -6 | x 3 | 4 | 3 | 0 | 0 | 1 | -3/4 | -7/40 | 17/4 | Fj - do j | 95 | 0 | 0 | 0 | 1/4 | 1/40 | 5/4 |
W wierszu indeksowym wszystkie terminy są nieujemne, zatem otrzymujemy następujące rozwiązanie problemu programowania liniowego (wypisujemy je z kolumny wolnych terminów):
Konieczne jest uszycie 24 koszul typu 1, 7 koszul typu 2 i 3 koszul typu 3. W takim przypadku uzyskany zysk będzie maksymalny i wyniesie 95 rubli.
Pomoc w rozwiązaniu problemów na ten temat możesz uzyskać, wysyłając wiadomość na VKontakte, Viber lub wypełniając formularz. Koszt rozwiązania Praca domowa zaczyna się od 7 BYN. za zadanie (200 rubli rosyjskich), ale nie mniej niż 10 rubli białoruskich. (300 RUB) za całe zamówienie. Szczegółowy projekt. Koszt pomocy przy egzaminie online (w tym przypadku wymagana jest 100% przedpłata) wynosi od 30 BYR. (1000 rubli rosyjskich) za rozwiązanie problemu.
| - | x 1 | + | x 2 | - | S 1 | = | 1 | ||||||||||
| x 1 | +3 | x 2 | + | S2 | = | 15 | |||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 4 |
| - | x 1 | + | x 2 | - | S 1 | + | R 1 | = | 1 | |||||||||||
| x 1 | +3 | x 2 | + | S2 | = | 15 | ||||||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 4 |
| x 1 = 0 x 2 = 0 S 1 = 0 S 2 = 15 S 3 = 4 R 1 = 1 |
=> W = 1 |
| x 1 | x 2 | S 1 | S2 | S 3 | R 1 | Św. członek | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | 1: 1 = 1 |
| 1 | 3 | 0 | 1 | 0 | 0 | 15 | 15: 3 = 5 |
| -2 | 1 | 0 | 0 | 1 | 0 | 4 | 4: 1 = 4 |
| 1 | -1 | 1 | 0 | 0 | 0 | W - 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | |
| 4 | 0 | 3 | 1 | 0 | -3 | 12 | |
| -1 | 0 | 1 | 0 | 1 | -1 | 3 | |
| 0 | 0 | 0 | 0 | 0 | 1 | W - 0 |
| - | x 1 | + | x 2 | - | S 1 | = | 1 | ||||||||||
| 4 | x 1 | + | 3 | S 1 | + | S2 | = | 12 | |||||||||
| - | x 1 | + | S 1 | + | S 3 | = | 3 |
| x 1 | x 2 | S 1 | S2 | S 3 | Św. członek | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 4 | 0 | 3 | 1 | 0 | 12 | 12: 4 = 3 |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F-1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F-1 | |
| 0 | 1 | -1/4 | 1/4 | 0 | 4 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| 0 | 0 | 7/4 | 1/4 | 1 | 6 | |
| 0 | 0 | -2 | -1 | 0 | F-13 |
| S 1 = 0 S 2 = 0 x 1 = 3 x 2 = 4 S 3 = 6 |
=> F - 13 = 0 => F = 13 |
Krok 0. Etap przygotowawczy.
Zmniejszamy problem LP do specjalna forma (15).
Krok 1. Kompilowanie stół simpleksowy, odpowiadający specjalnej formie:
|
|
|
|||||
|
|
|
|
|
|||
|
|
|
|
|
|
||
|
|
|
|
|
|
||
|
|
|
|
|
|
||
Należy pamiętać, że tabela ta odpowiada dopuszczalnemu rozwiązaniu podstawowemu 
problemy (15). Oznaczający funkcja celu w sprawie tej decyzji 
Krok 2. Kontrola optymalności
Jeżeli wśród elementów wiersza indeksowego znajdują się tabele simpleksowe 
nie ma wtedy ani jednego pozytywnego elementu 
, znaleziono optymalne rozwiązanie problemu LP: Algorytm kończy działanie.
Krok 3. Kontrola nierozstrzygalności
Jeśli wśród 
jest element pozytywny 
i w odpowiedniej kolumnie 
nie ma ani jednego pozytywnego elementu 
, to funkcja celu L jest nieograniczona od dołu na zbiorze dopuszczalnym. W tym przypadku nie ma optymalnego rozwiązania. Algorytm kończy działanie.
Krok 4. Wybór kolumny wiodącej Q
Wśród elementów 
wybierz maksymalny element dodatni 
. Deklarujemy, że ta kolumna jest kolumną wiodącą (zezwalającą).
Krok 5. Wybór linii prowadzącej P
Wśród pozytywnych elementów kolumny 
znajdź element 
, dla którego zachodzi równość
.
Strunowy P Deklarujemy, że jest to wiodące (pozwalające). Element 
Deklarujemy, że jest liderem (pozwalając).
Krok 6 Konwersja tabeli Simplex
Tworzymy nową tabelę simplex, w której:
a) zamiast zmiennej podstawowej 
zanotować 
, zamiast zmiennej niepodstawowej 
zanotować 
;
b) element wiodący zostaje zastąpiony wartością odwrotną 
;
c) wszystkie elementy kolumny wiodącej (z wyjątkiem 
) pomnożyć przez 
;
d) wszystkie elementy linii prowadzącej (z wyjątkiem 
) pomnożyć przez 
;
e) pozostałe elementy tablicy simplex są konwertowane według poniższego schematu „prostokątnego”.
Od elementu odejmuje się iloczyn trzech czynników:
pierwszy to odpowiedni element kolumny wiodącej;
drugi to odpowiedni element linii wiodącej;
trzecia jest odwrotnością elementu wiodącego 
.
Przekształcony element i odpowiadające mu trzy współczynniki są właśnie wierzchołkami „prostokąta”.
Krok 7 Przejście do kolejnej iteracji następuje poprzez powrót do kroku 2.
2.3. Algorytm metody simpleksowej dla problemu maksymalnego
Algorytm metody simplex dla problemu maksymalnego różni się od algorytmu dla problemu minimalnego jedynie znakami linii indeksowej współczynników w funkcji celu 
, a mianowicie:
W kroku 2:
:
W kroku 3
. Funkcja celu jest nieograniczona z góry na zbiorze dopuszczalnym.
W kroku 4:
.
2.4. Przykład rozwiązania problemu metodą simplex
Rozwiąż zadanie zapisane w postaci (15).
Stwórzmy tabelę simplex:
|
|
|
|
|
|
| |||
|
|
|
Ponieważ współczynniki linii funkcji celu są nieujemne, początkowe rozwiązanie bazowe nie jest optymalne. Wartość funkcji celu dla tej podstawy L=0.
Wybierz kolumnę wiodącą - jest to kolumna odpowiadająca zmiennej 
.
Wybierz linię wiodącą. W tym celu znajdujemy 
. Dlatego linia wiodąca odpowiada zmiennej 
.
Przekształcamy tabelę simplex, wprowadzając zmienną 
do bazy i wyprowadza zmienną 
od podstawy. Otrzymujemy tabelę:
|
|
|
|
|
|
|
| ||
|
|
|
Zakończona zostaje jedna iteracja metody. Przejdźmy do nowej iteracji. Wynikowa tabela nie jest optymalna. Podstawowe rozwiązanie odpowiadające tabeli ma postać . Wartość funkcji celu na tej podstawie L= -2.
Kolumną wiodącą jest tutaj kolumna odpowiadająca zmiennej 
. Linia wiodąca – linia odpowiadająca zmiennej 
. Po przeprowadzeniu przekształceń otrzymujemy tablicę sympleksową:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Kolejna iteracja zakończona. Przejdźmy do nowej iteracji.
Linia funkcji celu nie zawiera wartości dodatnich, co oznacza, że odpowiadające jej rozwiązanie podstawowe jest optymalne i algorytm się kończy.
Jedna z metod rozwiązania problemy optymalizacyjne (zwykle związane ze znalezieniem minimum lub maksimum) Programowanie liniowe zwany . Metoda Simplex obejmuje całą grupę algorytmów i metod rozwiązywania problemów programowania liniowego. Jedna z tych metod, polegająca na zapisaniu danych źródłowych i przeliczeniu ich w specjalnej tabeli, to tzw tabelaryczna metoda simplex .
Rozważmy algorytm metody simpleks tabelaryczny na przykładzie rozwiązania zadanie produkcyjne, co sprowadza się do znalezienia Plan produkcji zapewnienie maksymalnego zysku.
Dane wejściowe dla problemu metody simplex
Firma produkuje 4 rodzaje produktów, przetwarzając je na 3 maszynach.
Normy czasowe (min./szt.) obróbki produktów na maszynach określa macierz A:
Fundusz czasu pracy maszyny (min.) jest określony w macierzy B:
Zysk ze sprzedaży każdej jednostki produktu (RUB/sztukę) wyraża macierz C:
Cel zadania produkcyjnego
Opracuj plan produkcji, który zmaksymalizuje zysk przedsiębiorstwa.
Rozwiązanie problemu metodą jednostronną tabelaryczną
(1) Oznaczmy przez X1, X2, X3, X4 planowaną liczbę produktów każdego rodzaju. Następnie pożądany plan: ( X1, X2, X3, X4)
(2) Zapiszmy ograniczenia planu w postaci układu równań:
(3) Zatem docelowy zysk wynosi:
Oznacza to, że zysk z realizacji planu produkcyjnego powinien być maksymalny.
(4) Aby rozwiązać powstały problem skrajność warunkowa, zastępujemy system nierówności systemem równania liniowe wprowadzając do niego dodatkowe zmienne nieujemne ( X5, X6, X7).
(5) Przyjmijmy co następuje planie referencyjnym:
X1 = 0, X2 = 0, X3 = 0, X4 = 0, X5 = 252, X6 = 144, X7 = 80
(6) Wprowadźmy dane do stół simpleksowy:
W ostatniej linii wpisujemy współczynniki funkcji celu i samą jej wartość ze znakiem przeciwnym;
(7) Wybierz w Ostatni wiersz największy (modulo) liczba ujemna.
Obliczmy b = N / Elementy_wybranej_kolumny
Spośród obliczonych wartości b wybieramy najmniej.
Przecięcie wybranej kolumny i wiersza da nam element rozstrzygający. Zmieniamy bazę na zmienną odpowiadającą elementowi rozwiązującemu ( X5 do X1).
- Sam element rozstrzygający zmienia się na 1.
- Dla elementów linii rozdzielczości – a ij (*) = a ij / RE ( to znaczy dzielimy każdy element przez wartość elementu rozdzielającego i uzyskujemy nowe dane).
- W przypadku elementów kolumny rozdzielczości są one po prostu resetowane do zera.
- Pozostałe elementy tabeli przeliczamy korzystając z reguły prostokąta.
a ij (*) = a ij – (A * B / RE)
Jak widać, bierzemy aktualnie przeliczaną komórkę i komórkę z elementem rozstrzygającym. Tworzą przeciwległe narożniki prostokąta. Następnie mnożymy wartości z komórek pozostałych 2 rogów tego prostokąta. Ta praca ( A * B) podziel przez element rozwiązujący ( ODNOŚNIE). I odejmij od aktualnie przeliczanej komórki ( ij) co się stało. Otrzymujemy nową wartość - ij (*).
(9) Sprawdź ponownie ostatnią linię ( C) NA obecność liczb ujemnych. Jeśli ich tam nie ma, znaleziono optymalny plan, przejdź do ostatni etap rozwiązanie problemu. Jeśli tak, plan nie jest jeszcze optymalny i należy ponownie obliczyć tabelę jednostronną.
Ponieważ w ostatniej linii znowu mamy liczby ujemne, rozpoczynamy nową iterację obliczeń.
(10) Ponieważ w ostatniej linijce nie ma elementów negatywnych, oznacza to, że znaleźliśmy optymalny plan produkcji! Mianowicie: wyprodukujemy te produkty, które przesunęły się do kolumny „Podstawa” - X1 i X2. Znamy zysk z wyprodukowania każdej jednostki produkcji ( macierz C). Pozostaje pomnożyć znalezione wielkości produkcji produktów 1 i 2 przez zysk na 1 sztukę, otrzymamy wynik końcowy ( maksymalny! ) zysk dla danego planu produkcyjnego.
ODPOWIEDŹ:
X1 = 32 szt., X2 = 20 szt., X3 = 0 szt., X4 = 0 szt.
P = 48 * 32 + 33 * 20 = 2196 rub.
Galyautdinov R.R.
© Kopiowanie materiału jest dozwolone tylko w przypadku bezpośredniego hiperłącza do