2. Wprowadzenie naturalnych zmiennych podstawowych. Budowa stołu simpleksowego. Definicja planu zerowego.

Metoda Simplex. Algorytm metody simplex.

Metoda Simplex- algorytm rozwiązania problem optymalizacji Programowanie liniowe poprzez wyliczenie wierzchołków wielościanu wypukłego w przestrzeni wielowymiarowej. Metodę tę opracował amerykański matematyk George Danzig w 1947 roku.

Ideą metody simpleks jest przełożenie postawionego problemu opisowego na formę matematyczną. Matematyczne sformułowanie problemu zawiera równanie funkcji celu wskazujące pożądany wynik - określenie minimum lub maksimum funkcji celu; układy więzów liniowych określone przez równości lub nierówności. Otrzymane opis matematyczny prowadzą do postaci macierzowej. Następnie macierzowy opis problemu sprowadza się do postaci kanonicznej. Po systemie równania liniowe sprowadzone do postaci kanonicznej, zaczynamy rozwiązywać problem programowania liniowego. Algorytm rozwiązania tego problemu składa się z ciągu konstrukcji macierzy. Każdy krok rozwiązania przybliża Cię do uzyskania pożądanego rezultatu.

W schemacie obliczeniowym metody sympleksowej realizowany jest uporządkowany proces, w którym rozpoczynając od pewnego początkowego dopuszczalnego punktu narożnego (zwykle początku układu współrzędnych) dokonuje się kolejnych przejść od jednego dopuszczalnego skrajnego punktu do drugiego, aż do uzyskania punktu odpowiadającego rozwiązaniu optymalnemu znaleziony.

Algorytm metody simpleksowej

1. Wprowadzamy system ograniczeń Forma kanoniczna(kiedy system jest ograniczony). Co więcej, w systemie można zidentyfikować jedną podstawę.

2. Znajdź oryginał planie referencyjnym(nieujemne rozwiązania podstawowe układu równań KZLP). Każdy z planów odniesienia wyznaczany jest przez układ m liniowo niezależnych wektorów zawartych w danym układzie n wektorów A 1 , A 2 ,…, Jakiś. Górną granicę liczby planów referencyjnych zawartych w danym zadaniu wyznacza liczba kombinacji Z nm);

3. Budujemy stół simpleksowy (stół simpleksowy macierz służąca do wyliczania dopuszczalnych rozwiązań bazowych (niezdegenerowanego) problemu programowania liniowego podczas jego rozwiązywania metodą sympleksową. Tworzy się ją z macierzy współczynników układu równań programowania liniowego sprowadzonego do postaci kanonicznej, jej sekwencyjnej transformacji zgodnie z tzw. algorytm simpleksowy pozwala na ograniczoną liczbę kroków (iteracji) uzyskanie pożądanego rezultatu – planu zapewniającego ekstremalną wartość funkcji celu).

4. B stół simpleksowy sprawdzamy wektory pod kątem ujemności, tj. oceny Zj – Сj wpisana w linii musi wynosić ≤ 0 (minimum), Zj – Сj ≥ 0(do maksimum). Jeżeli oszacowania spełniają warunki optymalności, problem jest rozwiązany.

5. Jeżeli dla niektórych wektorów naruszone zostaną warunki optymalności, to należy wprowadzić do bazy wektor odpowiadający:

max[θ 0 j (Zj – Сj)] ; min[θ 0 j (Zj – Сj)] ; θ 0 j = min, Gdzie x ja> 0

Element wektorowy θj co odpowiada θ 0 j nazywany permisywnym; wiersz i kolumna, w których się znajduje, nazywane są prowadnicą, wektor w rzędzie prowadzącym opuszcza podstawę.

6. Znajdźmy współczynnik rozszerzalności dla wszystkich wektorów w nowej bazie. Zastosujmy metodę Giordano Gaussa

Sprawdźmy jaki jest optymalny plan referencyjny. Jeżeli estymacja spełnia warunki optymalności, problem zostaje rozwiązany, jeżeli nie, wykonywane są kroki 5-7.

2. Wprowadzenie naturalnych zmiennych podstawowych. Budowa stołu simpleksowego. Definicja planu zerowego.

Metoda simplex jest najskuteczniejsza w rozwiązywaniu złożone zadania i reprezentuje proces iteracyjny (krok po kroku), rozpoczynający się od zero(odniesienie) rozwiązanie (wierzchołek N-wymiarowy wielościan). Następny w wyszukiwaniu optymalna opcja Plan zakłada ruch wzdłuż punktów narożnych (wierzchołków wielościanu) aż wartość funkcji celu osiągnie wartość maksymalną (minimalną). Rozważmy algorytm metody simplex na przykładzie problemu planowania obrotu przy ograniczonych zasobach surowcowych.

Firma sprzedaje N grupy produktów, posiadające M ograniczone zasoby materialne i pieniężne B ja ≥0 (1 ≤ I≤m) . Koszty zasobów każdego są znane I- rodzaj produkcji i sprzedaży jednostki towaru każdej grupy, przedstawiony w formie matrycy ( A ij) oraz zysk uzyskany przez przedsiębiorstwo ze sprzedaży jednostki towaru J-grupa zawarta w funkcji celu Z(X). Metoda programowania liniowego nie różni się od układu (1) - (2):

Z(X) = с 1 Х 1 + с 2 Х 2 + с 3 Х 3 + … +с n Х n →max(min) (1)

a 11 X 1 + za 12 X 2 +…a 1n X n ≤ b 1,

za 21 X 1 + za 22 X 2 +…a 2n X n ≤ b 2 (2)

a m1 X 1 + a m2 X 2 +…a mn X n ≤ b m,

X 1 ≥0 X 2 ≥0 X 3 ≥0 …X n ≥0

Etapy rozwiązania problemu metodą simplex obejmują:

1) Opracowanie planu zerowego odniesienia. Wprowadzamy nowe zmienne nieujemne (podstawowe), dzięki którym układ nierówności (2) staje się układem równań:

za 11 X 1 + za 12 X 2 +…a 1n X n + X n+1 = b 1

za 21 X 1 + za 22 X 2 +…a 2n X n + X n+2 = b 2 (3)

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

a m1 X 1 + a m2 X 2 +…a mn X n + X n+m = b m,

Jeśli przyjmiemy zmienne wejściowe jako wektory kolumnowe, wówczas reprezentują one pojedynczy (podstawowy) wektory. Należy pamiętać, że podstawowe zmienne mają prosty charakter znaczenie fizyczne- Ten reszta konkretnego zasobu w magazynie dla danego planu produkcji, dlatego podstawa ta nazywana jest naturalny. Rozwiązujemy układ (3) ze względu na podstawowe zmienne:

X n+1 = b 1, -a 11 X 1 - a 12 X 2 -…a 1n X n

X n+2 = b 2 - za 21 X 1 - za 22 X 2 -…a 2n X n (4)

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

X n+m = b m, - a m1 X 1 + a m2 X 2 +…a mn X n

Zapisujemy funkcję celu w postaci

Z(X) = 0-(-с 1 Х 1 -с 2 Х 2 -с 3 Х 3 -…-с n Х n) (5)

Zakładając, że wymagane zmienne główne X 1 = X 2 = X 3 = ... = X n = 0, otrzymujemy zerowy plan odniesienia X = (0, 0, ...0, b 1, b 2, b 3 ... b m), przy czym Z(X) = 0 (wszystkie zasoby w magazynie, nic nie wyprodukowano). Wprowadzamy plan do tabeli simplex.

Plan	Podstawa	C i /C j	Oznaczający X ja	X 1	X2	X rz	Xn+1	Xn+2	X n+ 3	Qmin
	Xn+1		b 1	11	12	13				b 1/a 12
Xn+2		b 2	21	22	23				b 2 / a 22
Xn+3		b 3	31	32	33				b 3 / a 32
Z(X) = 0	-C 1	- C2	- C 3				Indeks. linia

2) Z ujemnych współczynników linii indeksu wybieramy największą wartość bezwzględną, która wyznacza kolumnę wiodącą i pokazuje, która zmienna w następnej iteracji (kroku) przejdzie z głównej (wolnej) do podstawowej (w rzeczywistości grupa produktów, której sprzedaż przynosi maksymalny dochód). Następnie dzielimy zapasy surowców b i przez odpowiednie współczynniki kosztowe, wyniki wprowadzamy do tabeli i wyznaczamy wartość minimalną Q min (wybierany jest zasób, którego rezerwa najsilniej ogranicza produkcję wybranej grupy produktów). Wartość ta wybiera linię wiodącą i zmienną Xi, która w kolejnym kroku (iteracji) opuści bazę i stanie się wolna.

3) Przejście na nowy plan następuje w wyniku przeliczenia tabeli simplex metodą Jordana-Gaussa. Najpierw zastępujemy X j w podstawie X i kolumny wiodącej. Podzielmy wszystkie elementy linii wiodącej przez element rozdzielczy (RE), w wyniku czego miejsce RE w linii wiodącej będzie wynosić 1. Ponieważ X i stało się podstawowe, pozostałe jego współczynniki powinny być równe 0 Nowe elementy tego planu odnajdujemy zgodnie z zasadą prostokąta

NE=SE – (A*B)/RE (6)

Powstały plan ocenia się za pomocą współczynników linii indeksowej: jeśli wszystkie są dodatnie, to plan jest optymalny, jeśli nie, to plan można poprawić, wykonując kolejną iterację (krok).

Przykład. Na zakup wyposażenia zakładu produkcyjnego przeznaczono 20 tysięcy rubli. Sprzęt można ustawić na powierzchni nieprzekraczającej 72 m2. Można zamówić sprzęt dwóch typów: typu A, wymagający powierzchni produkcyjnej 6 m2 i zapewniający 6 tys. sztuk. produktów na zmianę (cena 5000 rubli) i typ B, wymagający powierzchni 12 m2 i produkujący 3 tysiące sztuk (cena 2000 rubli). Jaki jest optymalny plan nabycia sprzętu, który należy zapewnić maksymalna wydajność działka?

Oznaczmy ilość zakupionego sprzętu typu A i B odpowiednio przez X 1 i X 2.

Produktywność witryny ( funkcja celu): Z(X) =6Х 1 +3Х 2.

Główne ograniczenia są ze sobą powiązane

z gotówką: 5Х 1 +2Х 2 ≤ 20,

z powierzchnią zakładu produkcyjnego: 6Х 1 +12Х 2 ≤ 72.

Wprowadzamy nowe zmienne podstawowe X 3 (reszta Pieniądze po zakupie sprzętu) i X 4 (powierzchnia pozostała po rozmieszczeniu sprzętu) i przepisz ograniczenia w postaci układu równań:

5X 1 +2X 2 +X 3 =20 (X 3 =20 – 5X 1 - 2X 2)

6X 1 +12X 2 +X 4 = 72 (X 4 =72 – 6X 1 – 12X 2)

W tym przypadku funkcja celu: Z(X) = 6Х 1 +3Х 2 +0Х 3 +0Х 4 .

Tworzymy plan odniesienia (0): X = (0, 0, 20, 72), tj. nic nie zostało jeszcze zakupione (nie wydano żadnych pieniędzy, miejsce jest puste). Tworzenie tabeli simplex

Plan	Podstawa	C i /C j	Oznaczający X ja	X 1	X2	X 3	X 4	Qmin
	X 3							20/5=4
X 4							72/6=12
Z(X) = 0	- 6	- 3			Linia indeksu
	→X 1				0,4	0,2		4/0,4=10
X 4				9,6	-1,2		48/9,6=5
Z(X) = 6*4=24		-0,6	1,2		Linia indeksu
	X 1					0,25	-1/24	-
→X 2					-1/8	5/48	-
Z(X) =6*2+3*5=27			9/8	1/16	Linia indeksu

Oczywiście kolumna wiodąca odpowiada X 1, ponieważ ma największy indeks 6. Minimalną wartość Q min = 4 (najpoważniejsze ograniczenie zasobów) znajdujemy poprzez zdefiniowanie wiersza wiodącego pokazującego, że X 3 pochodzi ze zmiennych bazowych , a zamiast tego wprowadzono X 1 . Przeliczamy elementy linii wiodącej, dzieląc je przez 5 i korzystając ze wzoru (6) wyznaczamy elementy linii drugiej i indeksowej. Funkcja celu dla planu 1 jest równa Z(X) = 6*4+3*0 = 24.

Jednak jeden ze współczynników wiersza indeksowego dla kolumny X 2 pozostaje ujemny -0,6, dlatego plan ten nie jest optymalny i konieczna jest kolejna iteracja (krok), aby go poprawić. Wybierz drugą kolumnę jako wiodącą i minimalna wartość Q min = 5 definiujemy linię wiodącą za pomocą zmiennej podstawowej X 4. Po wykonaniu tych samych przekształceń otrzymujemy drugi plan, który będzie optymalny, ponieważ wszystkie współczynniki indeksu są dodatnie.

Przeanalizujmy uzyskane wyniki. Dla optymalnego rozwiązania funkcja celu ma maksymalna wartość 27 tysięcy rubli, przy czym oba zasoby są pobierane z bazy, a zatem całkowicie wydawane.

Upewnijmy się, że: 5*2+2*5 = 20 tysięcy rubli, 6*2+12*5=72 mkw. Wymaganym rozwiązaniem jest X = (2; 5;0;0), ale nie zawsze tak się dzieje.

Wykład nr 10

Temat: Metoda Simplex w przypadku problemów ze sztuczną podstawą

Metoda rozwiązania simplex polega na wprowadzeniu dodatkowych (podstawowych) zmiennych, które umożliwiają utworzenie macierzy jednostkowej. Jeżeli ograniczenia problemu przedstawimy w postaci nierówności:

a i1 X 1 + a i2 X 2 +…a in X n ≥ b ja (1)

lub równania:

a i1 X 1 + a i2 X 2 +…a in X n = b ja (1*),

wówczas nie ma możliwości uzyskania planu referencyjnego w pożądanej formie. W tym przypadku, aby zachować równość (1*), wprowadzamy sztuczna podstawa Y i , a zmienne sztuczne nie są bezpośrednio związane z treścią zadania, ale umożliwiają zbudowanie planu referencyjnego (wyjściowego):

a i1 X 1 + a i2 X 2 +…a in X n +Y ja = b ja (2)

Funkcja celu przy maksymalnym rozwiązaniu problemu zostanie zapisana w postaci:

Z(X) =∑C jot X jot +(-M)∑Y ja (3),

przy rozwiązywaniu podobnego problemu przynajmniej:

Z(X)=∑C jot X jot +(M)∑Y ja (3*),

gdzie M jest bardzo duże Liczba dodatnia, rodzaj kary za użycie sztucznych zmiennych.

W przypadku nierówności (1) wprowadzamy początkowo dodatkowe zmienne X n + i ze znakiem minus. Ich macierz nie będzie jednolita, zatem do każdej nierówności układu (1) wprowadzamy sztuczne zmienne У i:

a i1 X 1 +a i2 X 2 +…a in X n –X n+i +Y i =b ja (4)

Funkcja celu w tym przypadku to Z(X)=∑C j X j +0∑X n + i +(-M)∑Y i (aby znaleźć maksimum). Aplikacja sztuczna podstawa nadaje metodzie simpleks większą elastyczność i pozwala na jej wykorzystanie w szerokim zakresie zadań.

Przykład . Określ maksymalne i minimalne wartości zysku z produkcji dwóch rodzajów produktów A i B, jeśli w tabeli podano koszty produkcji i rentowność ze sprzedaży jednostki produktu. Głównym warunkiem jest pełne zatrudnienie pracowników w przedsiębiorstwie.

Matematycznie ograniczenia wielkości produkcji zostaną zapisane w postaci układu mieszanego:

1X 1 + 1X 2 ≤ 6,

2X 1 + 1X 2 = 8.

Wprowadźmy zmienną podstawową X 3 dla pierwszej nierówności i zmienną sztuczną Y 1 dla drugiego równania:

1X 1 + 1X 2 + X 3 = 6,

2X 1 + 1X 2 + Y 1 = 8.

Wyraźmy X 3 i Y 1 z otrzymanego układu równań i aby wyznaczyć maksimum, wyobraźmy sobie funkcję celu:

Z(X)= 3X 1 + 2X 2 +0X 3 –MY 1 = 3X 1 + 2X 2 –M(8 -2X 1 –X 2)=

3X 1 + 2X 2 –8M +2MX 1 + MX 2 = (2M + 3)X 1 + (M + 2)X 2 -8M

Dla planu referencyjnego - X=(0,0,6,8). Zbudujmy tabelę simplex:

Plan	Podstawa	C i /C j	Oznaczający X ja	X 1	X2	X 3	T 1	Qmin
	X 3							6/1=6
T 1	-M						8/2=4
Z(X) = -8M	-2M-3	-M-2			Linia indeksu
	X 3				0,5		-0,5	2/0,5=4
→X 1				0,5		0,5	4/0,5=8
Z(X) = 3*4=12		- 0,5		M+1,5	Linia indeksu
	→X 2						-1	-
X 1					-1		-
Z(X) =3*2+2*4=14				M+1	Linia indeksu

Z reguły doskonalenie planu odniesienia rozpoczyna się od usunięcia z bazy sztucznej zmiennej Y 1. W drugiej iteracji otrzymano optymalny plan X = (2,4,0,0), przy maksymalnym dochodzie 14 tysiąc. pocierać. , a współczynniki wiersza indeksu są nieujemne. Łatwo sprawdzić, że w tym zadaniu, przy optymalnym planie, zasoby są w pełni wykorzystane (2*1+4*1=6; 2*2+1*4=8).

Wyznaczając minimalną rentowność, inaczej formułujemy funkcję celu (+MY 1 wpisujemy jako wyraz:

Z(X)= 3X 1 + 2X 2 +0X 3 +MY 1 = 3X 1 + 2X 2 +M(8 -2X 1 –X 2)=

3X 1 + 2X 2 +8M - 2MX 1 - MX 2 = (3 - 2M)X 1 + (2 - M)X 2 +8M

Plan odniesienia jest taki sam, ale współczynniki wierszy indeksu w tabeli simplex są różne. Kolumnę wiodącą tak jak poprzednio wybiera się według największego dodatniego współczynnika w wartości bezwzględnej dla X 1, wiersz wiodący wyznacza minimalna wartość Q min = 4. W pierwszej iteracji sztuczna zmienna Y 1 jest wyprowadzana z podstawa.

Plan	Podstawa	C i /C j	Oznaczający X ja	X 1	X2	X 3	T 1	Qmin
	X 3							6/1=6
T 1	M						8/2=4
Z(X) = 8M	2M-3	M-2			Linia indeksu
	X 3				0,5		-0,5	2/0,5=4
→X 1				0,5		0,5	4/0,5=8
Z(X) = 3*4=12		- 0,5		-M+1,5	Linia indeksu

Wynikowe ujemne wartości współczynników w linii indeksu X i wskazują na optymalność pierwszego planu, podczas gdy dochód minimalny wynosi 12 tysięcy rubli.

Zapewnia ją jedynie produkcja produktu A (produkt B nie jest wytwarzany), surowce nie są w pełni wykorzystane (reszta X 3 = 2t), natomiast spełniony jest główny warunek – pracownicy są w pełni zatrudnieni w produkcji.

Wykład nr 11

Temat: Zamknięty problem transportu

1. Matematyczne sformułowanie liczby domkniętej problemu transportu. Wyznaczanie wymaganej liczby niewiadomych.

2. Etapy ustalania planu rozwiązania problemu transportowego.

Wykład 3. Tabele Simplex. Algorytm metody simplex.

§ 3 METODA PROSTA

3.1. Ogólna idea metody simplex. Interpretacja geometryczna

Metoda graficzna ma zastosowanie do bardzo wąskiej klasy problemów programowania liniowego: pozwala skutecznie rozwiązywać problemy zawierające nie więcej niż dwie zmienne. Rozważono podstawowe twierdzenia programowania liniowego, z których wynika, że ​​jeśli programowanie liniowe ma problem optymalne rozwiązanie, to odpowiada co najmniej jednemu punktowi narożnemu wielościanu rozwiązania i pokrywa się, zgodnie z co najmniej, z jednym z dopuszczalnych rozwiązań podstawowych systemu ograniczeń. Wskazano sposób rozwiązania dowolnego problemu programowania liniowego: wyliczyć ostateczny numer dopuszczalne rozwiązania podstawowe układu więzów i wybrać spośród nich to, dla którego funkcja celu stanowi rozwiązanie optymalne. Geometrycznie odpowiada to wyliczeniu wszystkich punktów narożnych wielościanu rozwiązania. Takie wyczerpujące poszukiwania ostatecznie doprowadzą do rozwiązania optymalnego (o ile takie istnieje), jednak jego praktyczna realizacja wiąże się z ogromnymi trudnościami, gdyż w przypadku problemów rzeczywistych liczba wykonalnych rozwiązań podstawowych, choć skończona, może być niezwykle duża.

Liczbę dopuszczalnych rozwiązań podstawowych, które należy przeszukiwać, można zmniejszyć, jeśli wyszukiwanie nie będzie prowadzone losowo, ale z uwzględnieniem zmian funkcji liniowej, tj. upewnienie się, że każde kolejne rozwiązanie jest „lepsze” (lub przynajmniej „nie gorsze”) od poprzedniego, zgodnie z wartościami funkcji liniowej (zwiększając je przy znalezieniu maksimum, zmniejszając przy znalezieniu minimum
). To wyszukiwanie pozwala zmniejszyć liczbę kroków w poszukiwaniu optymalnego. Wyjaśnijmy to na przykładzie graficznym.

Niech teren dopuszczalne rozwiązania reprezentowany przez wielokąt ABCDE. Załóżmy, że jest to jego punkt narożny A odpowiada oryginalnemu wykonalnemu rozwiązaniu bazowemu. Wyszukiwanie losowe wymagałoby przetestowania pięciu możliwych rozwiązań bazowych odpowiadających pięciu punktom narożnym wielokąta. Jednak z rysunku jasno wynika, że ​​po górze A korzystne jest przejście do sąsiedniego wierzchołka W, a następnie do optymalnego punktu Z. Zamiast pięciu przeszliśmy tylko przez trzy wierzchołki, konsekwentnie poprawiając funkcję liniową.

Podstawą była idea konsekwentnego udoskonalania rozwiązania metoda uniwersalna rozwiązywanie problemów programowania liniowego – metoda simpleksowa lub metoda sekwencyjnego doskonalenia planu.

Znaczenie geometryczne metody sympleksowej polega na sekwencyjnym przejściu od jednego wierzchołka wielościanu więzów (zwanego początkowym) do sąsiedniego, w którym funkcja liniowa przyjmuje najlepszą (przynajmniej nie najgorszą) wartość w stosunku do cel problemu; do momentu znalezienia rozwiązania optymalnego – wierzchołka, w którym zostaje osiągnięta optymalna wartość funkcji celu (jeżeli problem ma maksimum końcowe).

Metodę simpleksową po raz pierwszy zaproponował amerykański naukowiec J. Danzig w 1949 r., ale już w 1939 r. koncepcje tej metody opracował rosyjski naukowiec L.V. Kantorowicz.

Metoda simpleksowa, która umożliwia rozwiązanie dowolnego problemu programowania liniowego, jest uniwersalna. Obecnie wykorzystuje się go do obliczeń komputerowych, ale proste przykłady metodą sympleksową można rozwiązać ręcznie.

Aby wdrożyć metodę simplex - sekwencyjne doskonalenie rozwiązania - konieczne jest opanowanie trzy główne elementy:

metoda określania dowolnego początkowego wykonalnego podstawowego rozwiązania problemu;

zasada przejścia do najlepszego (dokładniej, nie gorszego) rozwiązania;

kryterium sprawdzenia optymalności znalezionego rozwiązania.

Aby zastosować metodę simplex, problem programowania liniowego należy sprowadzić do postaci kanonicznej, tj. układ więzów należy przedstawić w postaci równań.

W literaturze dość szczegółowo opisano: znalezienie wstępnego planu wsparcia (początkowego dopuszczalnego rozwiązania podstawowego), także przy użyciu metody sztucznej bazy, znalezienie optymalnego planu wsparcia, rozwiązywanie problemów przy użyciu tablic simpleksowych.

3.2. Algorytm metody simplex.

Rozważmy rozwiązanie ZLP metodą sympleksową i przedstawmy je w odniesieniu do problemu maksymalizacji.

1. Na podstawie warunków zadania tworzony jest jego model matematyczny.

2. Gotowy model przekształca się do postaci kanonicznej. W takim przypadku można zidentyfikować podstawę ze wstępnym planem referencyjnym.

3. Model kanoniczny problemu zapisano w formie tablicy sympleksowej, tak aby wszystkie wyrazy wolne były nieujemne. Jeśli wybrany został początkowy plan referencyjny, przejdź do kroku 5.

Tabela Simplex: układ równań ograniczeń i funkcja celu są wprowadzane w postaci wyrażeń rozwiązanych w stosunku do podstawy początkowej. Linia zawierająca współczynniki funkcji celu
, zwany
– ciąg znaków lub ciąg funkcji docelowej.

4. Znajdź początkowy plan odniesienia, wykonując przekształcenia sympleksowe z elementami o dodatniej rozdzielczości odpowiadające minimalnym relacjom sympleksowym i bez uwzględnienia znaków elementów
-linie. Jeżeli w trakcie przekształceń napotkany zostanie rząd zerowy, którego wszystkie elementy, z wyjątkiem członu wolnego, są zerami, to układ równań ograniczeń dla problemu jest niespójny. Jeżeli natrafiamy na wiersz 0, w którym poza wyrazem wolnym nie ma innych elementów dodatnich, to układ równań restrykcyjnych nie ma rozwiązań nieujemnych.

Nazwiemy redukcję systemu (2.55), (2.56) do nowej podstawy transformacja simpleksowa . Jeżeli transformację sympleksową potraktować jako formalną operację algebraiczną, to można zauważyć, że w wyniku tej operacji następuje redystrybucja ról pomiędzy dwiema zmiennymi wchodzącymi w skład pewnego układu funkcje liniowe: jedna zmienna przechodzi ze stanu zależnego do niezależnego, a druga, odwrotnie, z niezależnego do zależnego. Operacja ta znana jest w algebrze jako Krok eliminacji Jordana.

5. Znaleziony wstępny plan wsparcia jest sprawdzany pod kątem optymalności:

a) jeśli w
– w rzędzie nie ma elementów negatywnych (nie licząc terminu wolnego), wówczas plan jest optymalny. Jeśli nie ma zer, istnieje tylko jeden optymalny plan; jeśli jest co najmniej jedno zero, to istnieje nieskończona liczba optymalnych planów;

b) jeśli c
– w wierszu znajduje się co najmniej jeden element ujemny, co odpowiada kolumnie elementów niedodatnich
;

c) jeśli w
– w wierszu znajduje się przynajmniej jeden element ujemny, a w jego kolumnie przynajmniej jeden element dodatni, wówczas można przejść do nowego planie referencyjnym, bliższe optymalnemu. Aby to zrobić, należy wyznaczyć określoną kolumnę jako kolumnę rozdzielczą, stosując minimalny współczynnik sympleksowy, znaleźć wiersz rozwiązujący i wykonać transformację sympleksową. Powstały plan odniesienia jest ponownie sprawdzany pod kątem optymalności. Opisany proces powtarza się aż do uzyskania optymalnego planu lub ustalenia nierozwiązywalności problemu.

Kolumna współczynników zmiennej zawartej w podstawie nazywa się rozdzielczością. Zatem wybranie zmiennej wprowadzonej do bazy (lub wybranie kolumny rozdzielczej) przez element ujemny
-strings, zapewniamy funkcję rosnącą
.

Nieco trudniej jest określić zmienną, którą należy wykluczyć z podstawy. W tym celu układają stosunki wyrazów wolnych do elementów dodatnich kolumny rozwiązującej (takie relacje nazywane są sympleksami) i znajdują spośród nich najmniejszy, który wyznacza wiersz (rozwiązujący) zawierający wykluczoną zmienną. Wybór zmiennej wyłączonej z bazy (lub wybór prostej rozdzielczej) zgodnie z minimalną relacją sympleksową gwarantuje, jak już ustalono, dodatniość składowych bazy w nowym planie odniesienia.

W punkcie 3 algorytmu zakłada się, że wszystkie elementy kolumny wolnych terminów są nieujemne. Wymóg ten nie jest konieczny, ale jeśli zostanie spełniony, wówczas wszystkie kolejne przekształcenia sympleksowe będą wykonywane wyłącznie z elementami o dodatniej rozdzielczości, co jest wygodne w obliczeniach. Jeśli w kolumnie wolnych terminów znajdują się liczby ujemne, wówczas element rozstrzygający wybierany jest w następujący sposób:

1) spójrz na linię odpowiadającą na przykład pewnemu ujemnemu terminowi swobodnemu – wiersz i zaznacz w nim dowolny element ujemny, a odpowiadającą mu kolumnę uznamy za rozwiązującą (zakładamy, że ograniczenia problemu są spójne);

2) tworzą relacje elementów kolumny wyrazów wolnych z odpowiednimi elementami kolumny rozdzielczej, które mają te same znaki (relacje simpleksowe);

3) wybrać najmniejszą z relacji sympleksowych. To określi ciąg włączający. Niech będzie np. R-linia;

4) na przecięciu rozdzielającej kolumny i wiersza znajduje się element rozstrzygający. Jeśli element jest permisywny –stringi, to po transformacji sympleksowej wolny wyraz tego ciągu stanie się dodatni. W przeciwnym razie w następnym kroku ponownie przejdziemy do -linia. Jeśli problem da się rozwiązać, to po określonej liczbie kroków w kolumnie wolnych terminów nie pozostaną żadne elementy negatywne.

Jeśli pewną rzeczywistą sytuację produkcyjną sprowadzić do postaci PLP, wówczas dodatkowe zmienne, które trzeba wprowadzić do modelu w procesie konwersji go do postaci kanonicznej, zawsze mają określone znaczenie ekonomiczne.

Metoda simpleks polega na znalezieniu i przetestowaniu wierzchołka (kąta) będącego rozwiązaniem problemu LP. Na każdym etapie metoda wybiera wierzchołek i odpowiadające mu zmienne, które zapewniają ruch do minimum (maksimum) z najwyższa prędkość. Wybrana zmienna zastępuje inną, najbardziej restrykcyjną. Metoda simplex pozwala również określić, czy rozwiązanie istnieje. Algorytm realizujący metodę simplex można zapisać jako:

Krok 1. Wyznacza się pewien wierzchołek w ODR, odpowiadający podstawowym dopuszczalnym rozwiązaniom (zmiennym) znalezionym poprzez ekstrakcję z macierzy T- kolumny liniowo niezależne i przyrównujące do zera wszystkie pozostałe zmienne odpowiadające innym kolumnom macierzy.

Krok 2. Wybrane spośród wszystkich pozostałych p - t krawędzie odpowiadające zmiennym niepodstawowym, krawędź (zmienna), która poruszając się po niej prowadzi do najszybszego spadku funkcji celu.

Krok 3. To tak, jakby wykonywany był ruch od początkowego wierzchołka wzdłuż wybranej krawędzi do innego wierzchołka, co daje nowe rozwiązanie, które ma niższą wartość CF. Nowy wierzchołek jest tworzony poprzez zastąpienie zmiennej bazowej (krawędź) nową zmienną bazową (krawędź).

Kolumny i elementy wektorów są zwykle uporządkowane i zapisane w formie tabeli simpleksowej, której tworzenie zostanie pokazane poniżej.

Metoda simpleks rozwiązuje problem LP w standardowej formie.

Minimalizuj (maksymalizuj) funkcję w warunkach x > 0; Topór = b.

Macierz A jest rzeczywista i ma wymiar T x” i ranga T.

Sformułowany problem LP można również zapisać w postaci

Na podstawie zapisu problemu LP w postaci (8Л) można powiedzieć, że macierz rozszerzona

wymiary (t + 1) (n + 2) odpowiada rozwiązaniom[x/] t.

Przedstawmy macierz A jako zbiór kolumn

Ponieważ macierz A ma rangę T, wtedy będzie T na przykład liniowo niezależne kolumny macierzy A (a V1 ,...,a V/i Rozważmy wektor x° > 0 taki, że wszystko p - t elementami są 0 i Ax° = b. Niech będą to elementy z liczbami..., ja n_m. Załóżmy także, że położenie aw liniowo niezależnych kolumn macierzy A odpowiada położeniu niezerowych elementów w wektorach 0. Z geometrycznego punktu widzenia, zgodnie z Oświadczeniem 3 w § 7.6, oznacza to, że x° jest wierzchołkiem (kątem) ODR i dodatkowo spełnia dane warunki. To rozwiązanie nazywa się dopuszczalne rozwiązanie podstawowe. Kąty dopuszczalnego zbioru to dopuszczalne rozwiązania podstawowe.

Przypomnijmy, że zbiór podstawowych rozwiązań zawiera wszystkie informacje niezbędne do optymalnego rozwiązania problemu LP. W przypadku dwuwymiarowym rozpatrywanym w § 7.6 rozwiązaniami podstawowymi są wszystkie 6 punktów, a dopuszczalnymi rozwiązaniami podstawowymi są punkty L, V, Si 0.

Zatem dowolny wektor x podobny do x° można zapisać jako

Gdzie x w- wektor, którego elementy odpowiadają liniowo niezależnym kolumnom macierzy A; xF - wektor z zerowymi elementami.

Zdefiniujmy podobnie wektory

Zmienne będące elementami wektora x w, są nazywane podstawowe zmienne, oraz zmienne będące elementami wektora x F są nazywane bezpłatny (niepodstawowe) zmienne.

Ponieważ x°F=0, wówczas wartość funkcji celu dla wektora początkowego x° będzie równa

gdzie /° jest wartością / w punkcie x°.

Nazywa się rozwiązanie (8.1) postaci [x°/°]t dla x > 0 oczywiste (wyraźne) rozwiązanie. Zatem, jeśli ustawimy zmienne niepodstawowe na zero, otrzymamy oczywiste rozwiązanie.

Dla wygody zmieńmy układ T liniowo niezależne kolumny macierzy A w lewo i zapisz macierz w postaci

Tutaj odpowiada macierz B T liniowo niezależne kolumny ma wymiar tekst i ranga T, oraz macierz F

Jest th (p - t) matryca. Ponieważ macierz B składa się z liniowo niezależnych kolumn, ma ona odwrotność B -1 i detB φ 0. Zauważ, że do utworzenia macierzy B możesz wybrać dowolną T liniowo niezależne kolumny macierzy A.

Przedstawmy problem (8.1) uwzględniając wprowadzone oznaczenie

Reprezentacja ta odpowiada macierzy rozszerzonej.Załóżmy to

skąd wynika

Jeśli wektor x V będzie rozwiązaniem układu Bx d = b, to będzie rozwiązaniem podstawowym. Jeśli nierówność jest spełniona V= B -1 b > O, zatem x w będzie akceptowalnym rozwiązaniem.

Zatem obecne rozwiązanie spełnia następujące równanie:

Rozważmy macierz (8.4). Podstawowe zmienne zostaną przedstawione w postaci jawnej, jeżeli zamienimy macierz B na macierz jednostkową I. Mnożąc pierwszy wiersz macierzy (8.4) po lewej stronie przez B~ 1 otrzymujemy

gdzie B_1 b > O, tj. T Górne elementy w prawej kolumnie są nieujemne i reprezentują bieżącą wartość zmiennych.

Po lewej stronie Górna linia Wynikiem jest macierz jednostkowa: B -1 B = I. Ta prezentacja bardzo wygodne, ponieważ przy mnożeniu przez wektor x w każda zmienna będzie w osobnej linii.

Zatem, podstawowe rozwiązanie, które uznamy za dopuszczalne i odpowiadające podstawie B, wynosi x m = [x in 0], gdzie x w == B_1 b. Rozwiązanie podstawowe wynika z założenia, że x F = 0. Jednakże, jeśli xF* 0, wówczas x^ można obliczyć jako x 5 = = B~"b - B^"Fx/r. Podstawiając to wyrażenie do funkcji celu (funkcji kosztu), otrzymujemy

Ponieważ konieczne jest określenie zależności kosztu od zmiennych niepodstawowych, z których jedna jest następnie zaliczana do zmiennych podstawowych, dolna granica pod macierzą I powinna wynosić zero. Aby to zrobić, w (8.7) mnożymy pierwszy wiersz (macierzy) przez od do i dodaj go do drugiego

gdzie jest wartością funkcji celu dla początkowego stulecia

torus x 0 z (8.3).

Nazywa się macierz (8.8). stół simpleksowy. Doprowadzenie jej do ten gatunek jest początkowym etapem algorytmu simplex. Podczas wykonywania algorytmu następuje przejście z jednej tabeli do drugiej, aż prawy dolny element tabeli osiągnie maksimum lub minimum.

Korzystając z tabeli simplex, łatwo jest znaleźć prawidłowe rozwiązanie. Zmienne X F odpowiadają zerowej podmacierzy, zmiennym x w- macierz jednostkowa:

Załóżmy, że problem LP został sprowadzony do postaci standardowej, obliczona została tablica sympleksowa i wybrane zostało początkowe rozwiązanie podstawowe odpowiadające wierzchołkowi wielościanu rozwiązania.

Następnie - rozwiązanie problemu (8.1). Więc

jak b > Och, to jest podstawowe dopuszczalne rozwiązanie.

Przedstawmy macierz (8.9) w wygodniejszej formie, zachowując podstawowy zapis:

Rozważmy osobno problemy maksymalizacji i minimalizacji.

Rozważmy uniwersalną metodę rozwiązania problemu kanonicznego programowania liniowego

Z N zmienne i M ograniczenia równości, znane jako metoda simplex.

Zbiór planów problemu kanonicznego to zbiór wielościenny wypukły ze skończoną liczbą punktów narożnych. A jeśli ten problem ma optymalne rozwiązanie, to osiąga się je przynajmniej w jednym punkcie narożnym.

Dowolny punkt narożny jest powiązany z podstawowym planem problemu, w którym zmienne są równe zeru, a pozostałe zmienne odpowiadają liniowo niezależnym kolumnom macierzy warunków. Te liniowo niezależne kolumny tworzą nieosobliwą macierz bazową.

Iterowanie po wszystkich punktach narożnych jest kosztowne obliczeniowo i dlatego nieefektywne. W 1947 r. J. Danzig zaproponował uporządkowaną procedurę wyliczania punktów narożnych, w której wystarczy zbadać tylko niewielką ich część, aby znaleźć optymalne rozwiązanie. Ta procedura nazywa się metoda simplex.

J. Danzig zaproponował zastąpienie w macierzy bazowej tylko jednego wektora przy przechodzeniu z jednego skrajnego punktu do drugiego. Oznacza to, że podczas takiego przejścia musimy wykluczyć jedną ze zmiennych podstawowych - uczynić ją niepodstawową ( równy zeru), a w jej miejsce wprowadzić nową zmienną spośród niepodstawowych (zero) - uczynić ją podstawową (dodatnią).

Okazuje się, że geometrycznie taka zamiana prowadzi do przejścia z jednego punktu narożnego do sąsiedniego (sąsiadującego) powiązanego z poprzedni punkt wspólna krawędź.

Ze wszystkich sąsiadujących punktów wybierany jest ten, w którym funkcja celu rośnie najbardziej. Ponieważ liczba punktów narożnych jest skończona, przez skończoną liczbę przejść wierzchołek najwyższa wartość funkcji celu, czyli nieograniczoność funkcji celu zostanie ustalona na nieograniczonym zbiorze planów.

Ogólny schemat metody simpleks składa się z następujących głównych kroków.

· krok 0. Określenie podstawy początkowej i odpowiadającego jej początkowego punktu narożnego (linii bazowej).

· krok 1. Sprawdzanie aktualnej linii bazowej pod kątem optymalności . Jeżeli kryterium optymalności jest spełnione, To plan jest optymalny i rozwiązanie jest kompletne. W przeciwnym razie przejdź do kroku 2.

· krok 2. Znalezienie zmiennej wprowadzonej do zmiennych podstawowych. (Z warunku zwiększenia funkcji celu).

· krok 3. Znalezienie zmiennej wyłączonej ze zmiennych podstawowych (z warunku zachowania ograniczeń problemu).

· krok 4 . Znalezienie współrzędnych nowej linii bazowej (sąsiedniego punktu narożnego). Przejdź do kroku 1.

Powtarzane kroki 1-4 tworzą jedną iterację metody simpleks.

Z tego diagramu wynika, że ​​po pierwsze, aby rozpocząć metodę simplex, musisz mieć jakiś punkt narożny - początkowy plan podstawowy, a po drugie, musisz być w stanie zbadać bieżący punkt narożny pod kątem optymalności bez obliczania wszystkich sąsiednich wierzchołki. Problemy te można łatwo rozwiązać, jeśli kanoniczny problem LP ma jakąś specjalną postać.

Definicja. Powiemy, że kanoniczny problem LP ma „preferowaną postać”, jeśli

1. prawe strony równań, .

2. macierz stanu zawiera podmacierz jednostkową rozmiaru

Innymi słowy, w każdym równaniu istnieje zmienna ze współczynnikiem równy jeden, brakuje w innych równaniach. Pierwszy warunek nie jest uciążliwy, gdyż w przypadku ujemnej prawej strony jakiegoś równania wystarczy pomnożyć go przez (-1). W przypadku problemu typu preferencyjnego znalezienie początkowej linii bazowej jest bardzo proste.

Przykład 2.1.

Matryca Warunków A oraz wektor prawych stron więzów B wygląda jak

A wektor docelowy c = (1, -3, 0, 4, 2).

Jedna macierz podstawowa jest od razu oczywista: z wektorami jednostkowymi warunków.

Dlatego wybierając jako zmienne podstawowe X 1 , X 3 ,X 5 , i ułożenie układu równań X 2 = x 4 = 0 (zmienne inne niż podstawowe) , znajdziemy go natychmiast X 1 = 10,X 3 = 20,X 5 = 8, a więc początkowa linia bazowa X 0 = (10, 0, 20, 0, 8). Widzimy, że wartości zmiennych podstawowych są równe prawym stronom więzów. Z tego jasno wynika, że ​​prawe strony muszą być dodatnie B I .

W przyszłości połączymy podstawowe zmienne w wektor X B.

Zatem w problem kanoniczny preferowanej formy, za początkową macierz bazową przyjmuje się podmacierz tożsamości A B = mi, a odpowiadające im zmienne bazowe są równe prawym stronom ograniczeń:

X B = B.

Dla podstawowego planu tego typu można sformułować kryterium optymalności, które jest wystarczająco proste do przetestowania. Przedstawmy ilości

? J = < с B , A J > - ok J , j = 1,...,n,(2.1)

Gdzie Z B- wektor współczynników funkcji celu dla zmiennych podstawowych X B , A J -J- t kolumna macierzy warunków, C J -J- współczynnik funkcji celu. Różnice ? J nazywane są różnicami simpleksowymi lub szacunkami sympleksowymi.

Kryterium optymalności dla planu podstawowego. Jeśli chodzi o podstawowy plan z jednostką macierz bazowa wszystkie szacunki simpleksowe są nieujemne, wówczas ten plan jest optymalny.

Zastosujmy to kryterium do sprawdzenia optymalności planu podstawowego X 0 = (10, 0, 20, 0, 8) z przykładu 2.1.

Ponieważ pod tym względem wektor podstawowych zmiennych X B =(X 1 , X 3 ,X 5 ), To Z B = (C 1 , C 3 ,C 5 ) = (1, 0, 2).

Stąd,

? 1 = < с B , A 1 > - ok 1 = 1 1 + 0 0 + 2 0 - 1= 0,

2 = < сБ, A2 >- c2 = 1 3 + 0 1 + 2 2 - (-3) = 10,

? 3 = < с B , A 3 > - ok 3 = 1 0 + 0 1 + 2 0 - 0= 0,

? 4 = < с B , A 4 > - ok 4 = 1 (-1) + 0 5 + 2 1 - 4= -3,

? 5 = < с B , A 5 > - ok 5 = 1 0 + 0 0 + 2 1 - 2= 0.

Od oceny ? 4 < 0, то базисный план X 0 nie optymalne. Należy pamiętać, że estymaty simpleksowe odpowiadające zmiennym podstawowym są zawsze równe zeru, dlatego wystarczy sprawdzić tylko estymatory niepodstawowe.

Idea metody simplex

Metoda Simplex

W poprzedniej części wykazano, że jeśli problem programowania liniowego ma rozwiązanie optymalne, to jednym z rozwiązań optymalnych jest dopuszczalne rozwiązanie podstawowe jego układu więzów, które odpowiada pewnemu punktowi narożnemu wielościanu rozwiązań dopuszczalnych system. Pokazano, jak znaleźć to optymalne rozwiązanie, wykorzystując skończone poszukiwanie rozwiązań podstawowych układu ograniczeń problemu. Jednakże wraz ze wzrostem wymiaru n układu ograniczeń problemu ilość obliczeń służących rozwiązaniu problemu metodą wyczerpującego wyliczania rozwiązań podstawowych rośnie wykładniczo i staje się nieprzydatna w praktyce. Można zorganizować wyliczenie tylko dopuszczalnych rozwiązań podstawowych i znacznie zmniejszyć liczbę wyliczonych rozwiązań, jeśli każde kolejne dopuszczalne rozwiązanie podstawowe zostanie tak wybrane, aby odpowiadająca mu wartość funkcji celu poprawiła się lub przynajmniej nie uległa pogorszeniu. Takie podejście pozwala zmniejszyć liczbę kroków w poszukiwaniu optymalnego rozwiązania podstawowego. Wyjaśnijmy tę ideę graficznie.

Niech wielokąt ABCDEFGH reprezentuje zbiór dopuszczalnych rozwiązań PLP z dwiema zmiennymi i wektorem – gradient funkcji celu.

Musimy znaleźć punkt tego wielokąta, w którym funkcja celu przyjmuje najmniejszą wartość. Niech zostanie wyznaczone początkowe dopuszczalne rozwiązanie podstawowe problemu odpowiadające punktowi narożnemu B. Po całkowitym przeszukaniu wszystkich dopuszczalnych rozwiązań podstawowych konieczne będzie zbadanie ośmiu takich rozwiązań odpowiadających ośmiu punktom narożnym wielokąta. Jednak z rysunku jasno wynika, że ​​biorąc pod uwagę kierunek gradientu, bardziej opłaca się udać do sąsiedniego wierzchołka C, niż do sąsiedniego wierzchołka D, co odpowiada optymalnemu rozwiązaniu podstawowemu problemu. Zatem zamiast ośmiu rozwiązań trzeba będzie wziąć pod uwagę tylko trzy wykonalne rozwiązania podstawowe.

Idea sekwencyjnego doskonalenia rozwiązania stanowi podstawę uniwersalnej metody rozwiązywania problemów programowania liniowego – metoda simplex.

Znaczenie geometryczne Metoda sympleksowa polega na wykonaniu sekwencyjnego przejścia od jednego wierzchołka wielościanu możliwych rozwiązań problemu do sąsiedniego, w którym funkcja celu przyjmuje wartość nie gorszą niż w poprzednim wierzchołku. To przejście trwa do momentu znalezienia optymalnego rozwiązania lub odkrycia, że ​​problem go nie ma.

Metodę simpleksową i jej nazwę po raz pierwszy zaproponował amerykański matematyk John Danzig w 1947 r., chociaż idee tej metody opublikował rosyjski matematyk L.V. Kantorowicz już w 1939 r. w artykule „ Metody matematyczne organizacja i planowanie produkcji.”

Metoda simplex składa się z trzech głównych elementów.