Widok tabelaryczny PPP. Simplex - tabele.

PROSTA METODA ROZWIĄZANIA ZLP

3.1. ogólna charakterystyka oraz główne etapy metody simpleks

Założycielami metody simplex są radziecki matematyk L.V. Kantorowicza i amerykańskiego matematyka J. Dantziga.

Metodą simpleksową można rozwiązać dowolny problem lub odkryć jego nierozwiązywalność. Wiele specjalnych klas problemów można rozwiązać innymi metodami, które są bardziej skuteczne dla tych klas. Zaletą metody simpleksowej jest jednak jej wszechstronność. Prawie wszystkie komputery zostały opracowane standardowe programy dla rozwiązań Simpleks ZLP- metoda.

Opiszmy główny pomysł metoda simplex.

Uważamy, że ZLP jest zapisane w formie kanonicznej, a funkcję celu należy zminimalizować. Jak już wiemy, optymalnego planu należy szukać wśród planów wspierających ZLP. Metoda simpleks nie przechodzi przez wszystkie plany referencyjne (co często byłoby niemożliwe ze względu na ich ogromną liczbę), ale zaczynając od jakiegoś początkowego planie referencyjnym, sekwencyjnie przechodzi do innych planów referencyjnych ze spadkiem funkcja celu. Metoda simpleks przestaje działać, gdy zostanie znaleziony optymalny plan odniesienia lub zostanie stwierdzona nierozwiązywalność problemu.

Rozwiązując problem metodą simplex, można wyróżnić następujące etapy:

1) doprowadzenie PAP do Forma kanoniczna;

2) wprowadzenie systemu równania liniowe do postaci Jordana z nieujemnymi prawymi stronami z jednoczesnym sprawdzeniem nierozstrzygalności ZLP ze względu na niespójność układu więzów liniowych;

3) badanie planu odniesienia pod kątem optymalności;

4) badanie ZLP pod kątem nierozstrzygalności ze względu na nieograniczoność od dołu na nieparzystości funkcji celu;

5) przejście na nowy, „lepszy” plan referencyjny.

Aby zredukować i uporządkować rekordy przy rozwiązywaniu problemu metodą simpleksową, stosuje się tzw. tablice simpleksowe. Aby skorzystać z tabeli simpleksowej, ZLP należy przekonwertować do postaci tabelarycznej. Robi się to tak.

Niech ZLP będzie zapisane w formie kanonicznej (2.3-2.5). Dla przynosząc PAP W formie tabelarycznej układ (2.4) należy najpierw sprowadzić do postaci Jordana z nieujemnymi prawymi stronami. Załóżmy, że ta postać Jordana ma postać (2.6). Wyraźmy z (2.6) zmienne podstawowe w kategoriach wolnych:

Podstawiając do funkcji celu (2.3) zamiast zmiennych podstawowych ich wyrażenia poprzez zmienne wolne według wzorów (3.1), wykluczamy w ten sposób zmienne podstawowe z funkcji celu. Funkcja celu będzie miała postać:

W formie tabelarycznej funkcję celu zapisuje się w następujący sposób:

Gdzie .

Zwróćmy uwagę na następujące cechy tabelarycznej formy PPP:

a) układ równań liniowych sprowadza się do postaci Jordana z nieujemnymi prawymi stronami;

b) zmienne bazowe wyłącza się z funkcji celu i zapisuje się to w postaci (3.3).

Przejdźmy teraz do opisu tabeli simplex. Niech ZLP zostanie zapisane w formie tabelarycznej:

(3.4)

Następnie wypełniona tabela simplex wygląda następująco.

Tabela 3.1.

Podstawa	Zmienne	Wolni członkowie
			...	x k			...
			...				...
			...				...
. . .	. .	. .	...	. .	. .	. .	...	. .	. . .
			...				...
F			...				....

Plan podstawowy PPL: ..., nazywa się planem odniesienia odpowiadającym tej tabeli simplex. Jak widać ze wzoru (3.2), wartość funkcji celu dla tego planu odniesienia jest równa γ ​​0.

Spójrzmy na przykład. Zredukuj poniższy ZLP do postaci tabelarycznej i wypełnij tabelę simplex:

W pierwszej kolejności należy doprowadzić ZLP do formy kanonicznej. Aby to zrobić, funkcja f należy zastąpić - f:

Układ równań należy zapisać w postaci Jordana z nieujemnymi prawymi stronami. Ogólne przyjęcie Sposób, w jaki można to osiągnąć, zostanie omówiony później (sekcja 3.7). W naszym przykładzie taka forma Jordana już istnieje ze zmiennymi bazowymi i . Wykluczmy z funkcji celu zmienne podstawowe – f. W tym celu wyrażamy je za pomocą wyrażeń swobodnych i zastępujemy je funkcją celu.

Tabelaryczny widok ZLP przedstawia się następująco:

Wypełnijmy tabelę simplex (aby skrócić wpisy, pierwsza kolumna ma nagłówek „B”, ostatnia kolumna to „Q”).

Tabela 3.2.

B					Q
			-5
	-7		-2
-F	-4				-20

Plan odniesienia odpowiadający tej tabeli simplex ma postać:

Wartość funkcji - f w tym planie odniesienia wynosi - 20.

Niech będzie kompletna tabela simplex. Sformułujmy warunek optymalności dla planu odniesienia.

Jeśli dolny wiersz tabeli jednostronnej zawiera wszystkie liczby z wyjątkiem, być może, tej znajdującej się najbardziej na prawo, niepozytywne, wówczas plan odniesienia odpowiadający tej tabeli jest optymalny.

Dla uproszczenia zasadność tego stwierdzenia uzasadnimy przykładem. Niech wypełniona tabela simplex będzie wyglądać następująco:

Tabela 3.3.

B						Q
				-1
					-1
F			-5	-3	-1

Wartość funkcji celu dla planu odniesienia odpowiadającego tabeli simplex wynosi 6. Zapiszmy funkcję celu w postaci tabelarycznej: , Gdzie . Ponieważ dla każdego dopuszczalnego rozwiązania Zmienne ZLP przyjmuje tylko wartości nieujemne, następnie od Ostatni wpis z funkcji celu widać, że jej wartość w dowolnym punkcie nieparzystej nieparzystości jest nie mniejsza niż 6. Zatem minimalna wartość funkcja celu na ODR wynosi 6 i osiąga się ją za pomocą planu odniesienia odpowiadającego tabeli simplex, .

3.4. Warunek nierozstrzygalności ZLP ze względu na nieograniczoną od dołu nieparzystość funkcji celu.

Jeśli tabela simpleksowa jest wypełniona dla ZLP, wówczas ODD problemu nie jest puste, więc plan odniesienia odpowiadający tabeli simpleksowej należy do ODD. Jednak ZLP może być nierozwiązywalny ze względu na nieograniczoną od dołu nieparzystą funkcję celu.

Warunek nierozstrzygalności formułuje się w następujący sposób.

Jeśli tabela simplex zawiera co najmniej jedną kolumnę inną niż ta znajdująca się najbardziej na prawo, która ma Liczba dodatnia, a wszystkie pozostałe wiersze kolumny zawierają liczby niedodatnie, wówczas LLP jest nierozwiązywalne ze względu na nieograniczoną od dołu nieparzystość funkcji celu.

Aby to uzasadnić, ponownie posłużymy się przykładem.

Tabela 3.4.

B						Q
					-2
			-3		-1
F				-1

Kolumna w dolnym wierszu zawiera liczbę dodatnią, a pozostałe wiersze zawierają liczby niedodatnie. Udowodnimy nierozstrzygalność ZLP.

Wypiszmy formę Jordana odpowiadającą tabeli simplex i przenieśmy terminy zawierające , do prawa strona. Dostajemy

Niech a będzie dowolną liczbą dodatnią. Oczywiście ZLP ma następujące możliwe rozwiązanie: Obliczmy wartość funkcji celu dla tego rozwiązania wykonalnego. Z tabeli 3.4 mamy:

. Przy określonym dopuszczalnym rozwiązaniu f = 4 - 2a. Z tego widzimy, że wartość funkcji celu może stać się tak mała, jak jest to pożądane w wystarczającym stopniu bardzo ważne A. Innymi słowy, funkcja celu nie jest ograniczona od dołu na ODE. Dlatego ZLP jest nierozstrzygalny.

3.5. Przejście na nowy plan referencyjny.

Załóżmy, że warunki optymalności i nierozstrzygalności nie są spełnione. Następnie metoda simplex przechodzi na nowy plan odniesienia. Przejście to następuje poprzez usunięcie z bazy jednej ze zmiennych podstawowych i wprowadzenie do bazy jednej ze zmiennych wolnych. W takim przypadku muszą zostać spełnione dwa następujące warunki:

1) nowa podstawa musi być nadal dopuszczalna, tj. prawe strony odpowiedniej formy Jordana nadal muszą być nieujemne;

2) przy nowym planie odniesienia wartość funkcji celu nie powinna przekraczać wartości z poprzedniego planu odniesienia.

Kolumna tabeli simplex zawierająca zmienną wpisaną do bazy nazywa się kolumna ogólna. Linia zawierająca zmienną wyprowadzoną z podstawy nazywa się linia ogólna. Nazywa się element na przecięciu wiersza ogólnego i kolumny ogólnej elementem ogólnym.

Zasada wyboru elementu ogólnego.

Dowolna kolumna tabeli simplex inna niż skrajna na prawo, która ma liczbę dodatnią w dolnym wierszu, jest wybierana jako kolumna ogólna. Następnie uwzględniane są tylko te wiersze tabeli simplex, inne niż najniższy, które mają liczby dodatnie na przecięciu z kolumną ogólną. Dla każdego z tych wierszy obliczany jest stosunek terminu wolnego do elementu w kolumnie ogólnej. Jako ogólny wybiera się wiersz, dla którego ten stosunek jest minimalny. Element na przecięciu wiersza ogólnego i kolumny ogólnej będzie elementem ogólnym.

Zilustrujmy tę regułę przykładem.

Tabela 3.5.

B						Q
				2	-1
				-2
F

Możesz wybrać kolumnę lub kolumnę jako kolumnę ogólną. Wybierzmy (najczęściej wybierana jest kolumna z największą liczbą dodatnią na dole). Teraz zacznijmy wybierać linię ogólną. Aby to zrobić, rozważ dwie linie - i . Wykonujemy proporcje 4:2 i 8:3. Stosunek 4:2 ma mniejszą wartość, dlatego pierwszą linię wybieramy jako ogólną. Dlatego elementem ogólnym jest 2 - stoi na przecięciu kolumny i wiersza.

Po wybraniu elementu ogólnego należy przejść do nowego planu odniesienia, w którym zmienna staje się podstawowa, a zmienna x 1 staje się wolna. Współczynnik dla w nowej formie Jordana musi być równy 1. Dlatego pierwszy wiersz tabeli 3.5 dzielimy przez 2. Następnie wynikowy pierwszy wiersz mnożymy przez (-3) i dodajemy do drugiego wiersza , wykluczyć z drugiego równania. Podobnie, stosując procedurę Jordana, wykluczamy ją z trzeciego równania i z funkcji celu (ta ostatnia wymaga tabelarycznej postaci ZLP).

W rezultacie otrzymujemy następującą tabelę.

Tabela 3.6

B						Q
F						-2

Należy pamiętać, że w kolumnie Q pierwsze trzy wiersze zawierają liczby nieujemne, tj. nowa podstawa nadal obowiązuje. Nie jest to przypadkowy fakt: tak będzie zawsze, jeśli będzie ściśle przestrzegana zasada wyboru linii ogólnej. Ponadto wartość funkcji celu w nowym planie odniesienia wynosi -2, w starym 12. „Ulepszenie” planu odniesienia gwarantuje zasadę wyboru kolumny ogólnej. Choć nie udowadniamy tych faktów ściśle, należy mieć na uwadze, że one zawsze mają miejsce.

Patrząc na tabelę H.6 widzimy, że nie jest spełniony ani warunek optymalności planu odniesienia, ani warunek nierozwiązywalności ZLP. Oznacza to, że musimy ponownie wybrać element ogólny i przejść do nowej tabeli simplex. Czytelnik może to zrobić samodzielnie.

3.6. Algorytm tabelaryczny simplex.

Niech będzie kompletna tabela simplex. Podsumowując powyższe, otrzymujemy następujący algorytm rozwiązywania ZLP metodą simpleksową.

1. Jeżeli w dolnym wierszu tabeli simplex wszystkie liczby, z wyjątkiem być może tej skrajnej na prawo, są dodatnie, to plan odniesienia odpowiadający tabeli simplex jest optymalny i algorytm zatrzymuje się. W przeciwnym razie przejdź do punktu 2.

2. Jeżeli tabela simplex zawiera inną kolumnę niż ta znajdująca się najbardziej na prawo, która w dolnym wierszu ma liczbę dodatnią, a we wszystkich pozostałych wierszach liczby niedodatnie, to LLP jest nierozwiązywalne ze względu na nieograniczoną od dołu nieparzystość funkcji celu i algorytm się zatrzymuje. W przeciwnym razie przejdź do punktu 3.

3. Wybierz dowolną kolumnę inną niż ta skrajna na prawo, która ma w dolnym wierszu liczbę dodatnią - nazwijmy to ogólną. Następnie rozważamy wiersze tabeli simplex, inne niż dolny, które w kolumnie ogólnej mają liczby dodatnie. Dla każdego z tych wierszy obliczamy stosunek terminu wolnego do elementu w kolumnie ogólnej. Wiersz, dla którego ta relacja jest minimalna, jest wierszem ogólnym. Element na przecięciu kolumny ogólnej i wiersza ogólnego będzie elementem ogólnym. Przejdź do punktu 4.

4. Tworzymy nową tabelę simplex, w której:

1) zmienną w linii ogólnej wyprowadza się z podstawy; do podstawy wprowadzana jest zmienna z kolumny ogólnej;

2) linia ogólna jest podzielona na element ogólny;

3) stosując procedurę Jordana, wykonuje się wszystkie liczby kolumny ogólnej, z wyjątkiem 1, która znajduje się w wierszu ogólnym równy zeru. Przejdź do punktu 1.

Przykład I. Rozwiązać metodą sympleksową

Problem jest zapisany w formie kanonicznej, należy go sprowadzić do formy tabelarycznej. Układ równań zapisano w postaci Jordana z nieujemnymi prawymi stronami (zmienne podstawowe i ). Konieczne jest sprowadzenie funkcji celu do postaci tabelarycznej. W tym celu wyrażamy zmienne podstawowe w kategoriach wolnych

x 3 =10 - 2x 1 - x 2

x 4 = 8 - x 1 - 2x 2

i podstaw go do funkcji celu

Aby uzyskać postać tabelaryczną, zapisujemy funkcję w następujący sposób:

Teraz mamy tabelaryczny widok ZLP:

Wypełnijmy pierwszą tabelę simplex

Tabela 3.7

B					Q
F

W tabeli 3.7 nie są spełnione warunki optymalności i nierozstrzygalności. Jako ogólną wybierzmy kolumnę , która w dolnym wierszu ma liczbę dodatnią. Następnie porównując stosunki 10:3 i 8:1, wybieramy pierwszą linię jako ogólną. W tabeli ogólnym elementem jest 2.

Działając zgodnie z punktem 4 algorytmu simpleks tabelaryczny, przejdźmy do tabeli 3.8.

Tabela 3.8

B					Q
F			-5		-22

Warunki optymalności i nierozstrzygalności nie są spełnione. Wybierz element ogólny w tabeli 3.8 i przejdź do następnej tabeli

Tabela 3.9

B					Q
F					-24

Tabela 3.9 spełnia warunek optymalności.

Odpowiedź: optymalny plan

Minimalna wartość funkcji celu f min = - 24.

Przykład 2. Rozwiąż metodą simplex:

Przede wszystkim należy doprowadzić ZLP do formy kanonicznej

Teraz doprowadzamy ZLP do formy tabelarycznej. Widzimy, że układ równań jest zapisany w postaci Jordana z nieujemnymi prawymi stronami (i zmiennymi podstawowymi z). Jednakże funkcja celu zawiera zmienną bazową. Mamy:

Zatem zestawienie tabelaryczne ZLP wygląda następująco:

Wypełnij tabelę simplex (tabela 3.10).

Tabela 3.10

B				z	Q
	-1
z		-2
G					-1

Po wybraniu elementu ogólnego przejdź do tabeli 3.11

Simpleksowa metoda rozwiązywania problemów Programowanie liniowe

Metoda simpleksowa to Metoda analityczna Rozwiązania ZLP implementujące algorytm metoda graficzna analitycznie, bez rysowania rysunku.

Rzecz w tym, że metoda simplex polega na wyszukiwaniu ukierunkowanym dopuszczalne rozwiązania, w którym wartość funkcji celu w każdym kroku jest lepsza niż w poprzednim. Proces powtarza się aż do uzyskania rozwiązania optymalnego pod względem wartości funkcji celu.

Metodę simpleks można zastosować do rozwiązywania PLP z dowolną liczbą niewiadomych.

Realizacja techniczna Metoda simpleksowa związana jest z rozwiązywaniem układów równań liniowych, dla których stosowana jest metoda Gaussa oraz opracowano zasady przeliczania tablic sympleksowych.

Metoda Simplex z podstawa naturalna ma zastosowanie, jeśli ZLP jest podany w notacji kanonicznej, a macierz w QLP zawiera podmacierz jednostkową rozmiaru jestem. Dla pewności załóżmy, że to pierwsze M Macierze wektorowe układu równań tworzą macierz tożsamości. Następnie początkowy plan jest wybierany w następujący sposób:

Optymalizację planu odniesienia sprawdza się za pomocą znaku optymalności, przejście do innego planu odbywa się za pomocą transformacji Jordana-Gaussa za pomocą matematycznego znaku optymalności. Powstały plan referencyjny jest ponownie sprawdzany pod kątem optymalności itp.

Matematyczne kryterium optymalności składa się z dwóch następujących twierdzeń:

1. Jeśli dla wszystkich wektorów ZA 1 , ZA 2 , … , An warunek jest spełniony gdzie , wówczas powstały plan odniesienia jest optymalny. W sumie do ustalenia Z j brać udział M terminami, to znaczy nie wszystkie współczynniki funkcji celu w niej uczestniczą c j, ale tylko z liczbami odpowiadającymi numerom bieżących wektorów bazowych A ja, których liczba jest równa M .

2. Jeżeli dla jakiegoś wektora nie zawartego w bazie warunek jest spełniony , to należy poszukać nowego planu referencyjnego, dla którego wartość CF jest większa niż dla obecnego. W takim przypadku możliwe są dwa przypadki:

a) jeśli wszystkie składniki wektora K, które należy wpisać do podstawy, są dodatnie, wówczas LLP nie ma rozwiązania (nie ma ostatecznego maksimum);

b) jeśli wektor ma co najmniej jedną składową dodatnią K, do wpisania do podstawy, wówczas można uzyskać nowy plan referencyjny.

Na podstawie kryterium optymalności do bazy wprowadza się wektor K, co dało minimalną ujemną wartość różnicy simpleks:

Aby warunek nieujemności wartości planu odniesienia był spełniony, wektor wyprowadza się z bazy A r, co daje minimalny współczynnik ocen pozytywnych

Linia A r, w którym znajdował się stary wektor bazowy, nazywany jest prowadnicą, kolumną K i element rk- przewodniki.

Elementy linii prowadzącej w nowej tabeli simplex oblicza się za pomocą wzorów:

i wszelkie inne elementy I linia - według wzorów:

Wartości nowego planu referencyjnego oblicza się za pomocą podobnych wzorów:

,

Proces trwa albo do momentu uzyskania optymalnego planu, albo do momentu, gdy TF będzie nieograniczone. Jeśli wśród różnic Δ jot, j=1, 2, …, n planu optymalnego jedynie różnice odpowiadające wektorom bazowym wynoszą zero, co świadczy o jednoznaczności planu optymalnego. Jeżeli oszacowanie zerowe odpowiada wektorowi nieuwzględnionemu w podstawie, to w ogólnym przypadku oznacza to, że plan optymalny nie jest jednoznaczny.

Przykład. Rozwiąż ZLP korzystając ze wzoru:

znajdować ,

pod ograniczeniami

ZLP ten sprowadza się do postaci kanonicznej poprzez wprowadzenie dodatkowych zmiennych x 3 I x 4:

KZLP ma wymaganą liczbę (dwie) kolumn zerowych w x 3 I x 4, to znaczy ma oczywisty początkowy plan odniesienia (0,0,300,150).

Rozwiązanie przeprowadza się metodą sympleksową o bazie naturalnej z obliczeniami sformatowanymi w tabelach sympleksowych:

Numer tabeli Simplex	Podstawa	z j	z j					Q
B	1	2	3	4
	←3
4
Δ	-		-2	-3			-
I	→2			1/3		1/3
←4			2/3		-1/3
Δ	-		-1				-
II	2					1/2	-1/2	-
→1					-1/2	3/2	-
Δ	-				1/2	3/2	-

Przyjrzyjmy się bardziej szczegółowo wypełnianiu tabel simpleksowych i odpowiednio uzyskiwaniu rozwiązania KZLP.

W Górna linia stół ogólny dodane współczynniki do jot, jot=1, 2, 3, 4 ze zmiennymi w CF. Pierwsze dwa wiersze tabeli zero simplex zawierają wektory kolumnowe B, Za 1, Za 2, Za 3, Za 4, odpowiedni forma wektorowa Rekordy KZLP. Ponieważ bazą początkową jest para wektorów A 3, A 4, są one zawarte w kolumnie o nazwie „Baza” tabeli zerowej jednostronnej. W której, 3 jest zawarty w pierwszym wierszu, który wyznacza jednostka będąca pierwszym elementem tego wektora, oraz wektor 4- do drugiej linii, dla tego wektora jednostka znajduje się w drugiej linii. W kolumnie „ c ja” wprowadza się współczynniki funkcji celu odpowiadające wektorom bazowym A 3, A 4, to jest ok. 3, ok. 4. Obydwa są równe zeru. Następnie obliczane są wartości różnic Δ dla wektorów B, Za 1, Za 2, Za 3, Za 4 i wpisuje się je w trzecim wierszu tabeli zerowej. Dla wektora 1:

dla wektora:

Podobnie, .

Dla wektora B obliczenie różnicy jest nieco uproszczone, ponieważ nie ma odpowiedniego współczynnika do jot, jot=1, 2, 3, 4 w CF:

Nie dla wszystkich wektorów ZA 1, ZA 2, ZA 3, ZA 4 powstałe różnice są nieujemne, zatem wybrany przez nas plan odniesienia nie jest optymalny. Musimy poszukać nowego planu odniesienia i w tym celu musimy zastąpić jeden z wektorów zawartych w bazie A 3, A 4.

Aby wyznaczyć wektor, który musimy wprowadzić, szukamy wektora, dla którego wartość różnicy jest minimalna. To jest wektor 2, odpowiada minimalnej wartości różnicy: -3. Czyli indeks k ze wzoru (8.4) jest równe 2. Aby określić wektor, który będziemy musieli wyprowadzić z podstawy, obliczamy wartości Q dla każdej linii według wzoru (8.5) i wpisz je w ostatniej kolumnie. W w tym przypadku w każdej linii potrzebujemy wartości elementu wektora B podzielić przez wielkość elementu wektora 2. W pierwszym wierszu otrzymujemy 300/3=100, w drugim: 150/1=150. Stosunek w pierwszym rzędzie był mniejszy; odpowiadał mu wektor bazowy 3 dlatego indeks R we wzorze (8.5) jest równe 1, rk=3 (zaznaczone w tabeli ramką), a wektor wyprowadzimy z bazy 3(oznaczone strzałką w tabeli).

Ponieważ wśród elementów wektora 2, które należy wpisać do podstawy, są pozytywne, wówczas można uzyskać nowy plan referencyjny i rozwiązanie należy kontynuować.

Następnie wypełniana jest druga tabela simplex. Aby przeliczyć elementy wektorów B, Za 1, Za 2, Za 3, Za 4 stosuje się wzory (8.6)-(8.8). Nieco inaczej różnią się one przy definiowaniu elementów linii prowadzącej (w naszym przypadku pierwszej) i przy definiowaniu elementów pozostałych linii. Zapiszmy obliczenia kilku elementów:

Pozostałe elementy pierwszej tabeli sympleksu obliczane są w taki sam sposób, jak zrobiliśmy to w przypadku tabeli zerowej. Ponieważ nie wszystkie różnice w pierwszej tabeli simplex są nieujemne, konieczne staje się kontynuowanie obliczeń.

Jak widzimy, w wyniku obliczeń w drugiej tabeli sympleksowej z wektorami bazowymi Za 2, Za 1 wszystkie różnice okazały się nieujemne, co oznacza osiągnięcie planu optymalnego (75; 75; 0; 0). Różnica sympleksowa dla wektora W równa pożądanej maksymalnej wartości CF - 375.

Twierdzenie (o skończoności algorytmu simplex).Jeśli istnieje optymalne Decyzja PPP, to istnieje podstawowe rozwiązanie optymalne. To drugie można zawsze uzyskać metodą simpleksową i można zacząć od dowolnej bazy początkowej.

Aby zastosować metodę simpleksową z bazą naturalną, KZLP musi zawierać podmacierz jednostkową o rozmiarze mxm – w tym przypadku początkowy plan wsparcia (nieujemne rozwiązanie podstawowe układu ograniczeń KZLP) jest oczywisty.
Konkretnie zakładamy, że pierwszych m wektorów macierzy układu równań stanowi macierz jednostkowa. Wtedy początkowy plan odniesienia jest oczywisty - (b 1, b 2,..., b m,0,...,0).
Optymalizację planu odniesienia sprawdza się za pomocą kryterium optymalności; przejście na inny plan odniesienia odbywa się za pomocą transformacji Jordana-Gaussa z wykorzystaniem matematycznego kryterium optymalności. Powstały plan odniesienia jest ponownie sprawdzany pod kątem optymalności i tak dalej. Proces kończy się w skończonej liczbie kroków i przy ostatni krok albo ujawnia się nierozwiązywalność problemu (nie ma ostatecznego maksimum), albo uzyskuje się optymalny plan odniesienia i odpowiadającą mu optymalną wartość współczynnika CF.
Matematyczne kryterium optymalności składa się z dwóch następujących twierdzeń:
1. Jeżeli dla wszystkich wektorów A 1, A 2,…, A n warunek jest spełniony
Gdzie ,
wówczas powstały plan odniesienia jest optymalny.
2. Jeżeli dla jakiegoś wektora nie zawartego w bazie warunek jest spełniony , wówczas można otrzymać nowy plan referencyjny, dla którego wartość CF będzie większa od pierwotnej i mogą być dwa przypadki:
- jeśli wszystkie składowe wektora, które należy wprowadzić do bazy, są dodatnie, to LLP nie ma rozwiązania (nie ma optymalnego końcowego);
- jeżeli do bazy należy wprowadzić przynajmniej jedną dodatnią składową wektora, wówczas można otrzymać nowy plan odniesienia.
Na podstawie kryterium optymalności do bazy wprowadza się wektor A k, który daje minimalną ujemną wartość różnicy sympleksu:
Aby warunek nieujemności wartości planu odniesienia był spełniony, z bazy wyprowadza się wektor A r, który daje minimalny pozytywny współczynnik oceny

Wiersz A r nazywany jest prowadnicą, kolumna A k i element a r k nazywane są prowadnicami.
Elementy linii prowadzącej w nowej tabeli simplex oblicza się za pomocą wzorów:
A i-te elementy linie - według wzorów:
Wartości nowego planu referencyjnego wylicza się korzystając ze wzorów:
dla i = r;
Proces decyzyjny trwa albo do momentu uzyskania optymalnego planu, albo do momentu ustalenia FT jako nieograniczonego. Jeżeli wśród różnic sympleksowych (oszacowań) planu optymalnego tylko oszacowania odpowiadające wektorom bazowym wynoszą zero, oznacza to jednoznaczność planu optymalnego. Jeżeli oszacowanie zerowe odpowiada wektorowi, który nie jest uwzględniony, to w ogólnym przypadku oznacza to, że optymalny plan nie jest unikalny.
Notatka. Aby zastosować podaną procedurę minimalizacji funkcja liniowa f (x 1 ,x 2 ,…, x n) należy poszukać maksimum - f (x 1 ,x 2 ,…, x n), a następnie przyjąć otrzymane maksimum z przeciwnym znakiem. Optymalne rozwiązanie jest takie samo.
Przykład. Uzyskaj rozwiązanie w oparciu o model:
Sprowadźmy ten problem (model) programowania liniowego do postaci kanonicznej wprowadzając dodatkowe zmienne x 3 i x4:
KZLP posiada wymaganą liczbę pojedynczych kolumn, tj. ma oczywisty początkowy plan odniesienia (0,0,300,150). Rozwiązanie przeprowadza się metodą sympleksową na bazie naturalnej, a obliczenia przedstawiono w tabelach sympleksowych:

J. Optymalne wartości zmienne są równe: x1*=75, x2* =75 (zmienne główne), x3* =0, x4* =0 (zmienne dodatkowe). Maksymalna wartość funkcja celu wynosi 375.
Zatem w omawianym powyżej problemie optymalne wykorzystanie ograniczone zasoby, optymalne programu produkcyjnego obejmuje wydanie 75 jednostek. produktów pierwszego typu i 75 sztuk. produkty drugiego typu. Program ten wiąże się z maksymalnym przychodem ze sprzedaży gotowych produktów – 375 USD.

Numer			W	2	3	0	0
simpleks-	Podstawa		plan					Q
stoły
	A3	0	300	1	3	1	0	100
0	A4	0	150	1	1	0	1	150
		k(x)	0	-2	-3	0	0
	A2	3	100	1/3	1	1/3	0	300
I	A4	0	50	2/3

Metoda Simplex. Algorytm. Znak optymalności planu odniesienia.

Z interpretacji geometrycznej ZLP jasno wynika, że ​​maksimum lub minimum funkcji osiąga się w punkcie narożnym układu więzów wypukłego wielościanu – ODP. Dlatego metoda simplex opiera się na idei uwzględniania i testowania optymalności tylko punktów narożnych - wierzchołków wielościanu, a nie całego nieskończonego zbioru jego punktów.

Ryż. Geometryczna interpretacja idei metody simplex

w przypadku dwóch (rysunek a) i trzech (rysunek b) zmiennych.

Simpleks jest wielokątem wypukłym w przestrzeni n-wymiarowej z n+1 wierzchołkami, które nie leżą w tej samej hiperpłaszczyźnie (hiperpłaszczyzna dzieli przestrzeń na 2 półprzestrzenie).

Metoda Simplex jest procedurą obliczeniową opartą na zasadzie sekwencyjnego doskonalenia rozwiązania. W tym przypadku przechodzimy z jednego punktu bazowego do drugiego. Wartość funkcji celu zawsze się poprawia.

Podstawowe rozwiązanie– to jedno z akceptowalnych rozwiązań występujących w ODR.

Nazywa się zmienne, dla których rozwiązuje się układ równań liniowych podstawowy. Następnie wywoływane są wszystkie pozostałe zmienne bezpłatny.

Udowodniono, że jeśli istnieje rozwiązanie optymalne, to można je znaleźć w skończonej liczbie kroków, z wyjątkiem przypadków zapętlenia.

Algorytm metody Simplex:

1. Zbuduj model matematyczny zadania.

1. Przekształć powstały model matematyczny na Forma kanoniczna, gdzie: prawa strona warunków jest nieujemna; warunki są równościami (jeśli to konieczne, wprowadź sztuczne zmienne).
2. Zbuduj tabelę simplex i znajdź początkowy plan odniesienia umożliwiający rozwiązanie problemu. Wiele zmiennych podstawowy, są traktowane jako początkowe rozwiązanie podstawowe. Wartości tych zmiennych są równe wolnym terminom. Wszystkie pozostałe zmienne mają wartość zerową.
3. Sprawdzanie optymalności rozwiązania podstawowego odbywa się za pomocą specjalnych szacunków współczynników funkcji celu (patrz Ostatni wiersz tabele). Jeśli problem zostanie rozwiązany przy wartości maksymalnej, wszystkie oceny muszą być nieujemne; jeśli przy wartości minimalnej, wszystkie oceny muszą być niedodatnie.
4. Przejście na nowe rozwiązanie podstawowe. Oczywiście optymalny plan powinien uwzględniać zmienną, która w największym stopniu zwiększy funkcję celu. Przy rozwiązywaniu maksymalnych problemów plan optymalny obejmuje produkty, których produkcja jest najbardziej opłacalna. Wyznacza się to maksymalnie dodatnią wartością estymaty współczynników funkcji celu. Kolumna tabeli zawierająca to oszacowanie nazywana jest kolumną główną. Jeżeli chociaż jeden element kolumny jest dodatni, to zostaje znaleziony wiersz ogólny (w przeciwnym razie zadanie nie ma nr optymalne rozwiązanie). Jeśli w tej kolumnie są zera, musisz wziąć inną kolumnę. Aby znaleźć wiersz ogólny, wszystkich wolnych członków (zasobów) dzieli się na odpowiednie elementy kolumny ogólnej (wskaźnik zużycia zasobów na jednostkę produktu). Z uzyskanych wyników wybierany jest najmniejszy, a odpowiedni wiersz nazywa się wierszem ogólnym. Odpowiada zasobowi, do którego ogranicza produkcję ten krok. Element tabeli simplex znajdujący się na przecięciu ogólnego wiersza i kolumny nazywany jest elementem ogólnym. Wszystkie elementy ciągu ogólnego, w tym element wolny, są podzielone na element ogólny. W rezultacie element ogólny staje się równy 1. Następnie konieczne jest, aby wszystkie pozostałe elementy kolumny ogólnej stały się równe 0. Kolumna ogólna musi stać się jednością. Wszystkie linie oprócz ogólnej są konwertowane w następujący sposób: odebrane elementy Nowa linia pomnóż przez odpowiednie elementy kolumny ogólnej i odejmij wynikowy iloczyn od elementów starego wiersza. Wartość nowych zmiennych podstawowych zostanie uzyskana w odpowiednich komórkach kolumny wolnych terminów (reguła prostokątów).
5. Powstały roztwór zasadowy sprawdza się pod kątem optymalności (krok nr 4). Jeżeli jest ono optymalne, wówczas obliczenia zostają zatrzymane, w przeciwnym razie zostaje znalezione nowe rozwiązanie podstawowe (krok nr 5).

Znak optymalności planu odniesienia

Jeśli rozwiążemy problem dla max, wówczas wszystkie szacunki muszą być nieujemne.

Jeśli rozwiążemy problem przez min, wówczas wszystkie szacunki muszą być niekorzystne.

Jeśli plan referencyjny nie jest optymalny, należy przejść na lepszy plan referencyjny. W tym celu wybieramy najgorsze oszacowanie. Będzie odpowiadać kolumnie rozdzielczości. Następnie musisz znaleźć linię włączającą.

Θ (kolumna relacji simpleksowych) nie jest rysowana dla linii z ujemnymi i wartości zerowe. Ze wszystkich θ wybieramy najmniejsze; zawsze tak się dzieje, niezależnie od tego, czy pierwotny problem dotyczy wartości minimalnej czy maksymalnej.

Linia rozdzielcza zawsze pokazuje, który element należy usunąć z podstawy, a kolumna rozdzielcza zawsze pokazuje, który element należy wprowadzić do podstawy.