Metoda simpleksowa z przykładami sztucznych zmiennych. Rozwiązywanie problemów programowania liniowego metodą sztucznej bazy

Rozwiązanie problemu Programowanie liniowe Metoda simpleks zaczyna się od znalezienia planu odniesienia.

Rozważmy trzeci przypadek konstrukcji wstępnego planu odniesienia (pierwszy i drugi opisano w paragrafie 2.1).

Niech system ograniczeń będzie miał postać

Przejdźmy dalej Forma kanoniczna poprzez wprowadzenie dodatkowych zmiennych
, które odejmujemy od lewej strony nierówności układu. Weźmy system

.

Teraz system ograniczeń nie ma preferowanej formy, ponieważ istnieją dodatkowe zmienne X N + I wejdź w lewą stronę (z B I 0) ze współczynnikami równymi –1. W tym wypadku tzw sztuczna podstawa idąc do M-zadanie.

Po lewej stronie ograniczeń równości dodawane są sztuczne zmienne, które nie mają preferowanej formy w I. Zmienne w funkcji celu w I wprowadzony ze współczynnikiem M w przypadku rozwiązania problemu co najmniej i przy współczynniku – M– dla problemu maksymalnego, gdzie M- duży Liczba dodatnia. Powstały problem nazywa się M-zadanie, odpowiadający oryginałowi. Zawsze ma preferowany wygląd.

Niech pierwotny problem programowania liniowego będzie miał postać

;
;

Jednakże żadne z ograniczeń nie ma preferowanej zmiennej. M-zadanie zostanie napisane w następujący sposób:

;

W tym przypadku funkcja znaku „–” (10) odnosi się do maksymalnego problemu. Problem (10)–(12) ma preferowaną postać. Jej inicjał planie referencyjnym wygląda jak

.

Jeżeli któreś z równań (8) mają preferowaną postać, to nie należy do nich wprowadzać sztucznych zmiennych.

Twierdzenie 5. Jeśli optymalnie X Hurt 

M-problemy (10)–(12) wszystkie zmienne sztuczne
potem plan
jest optymalnym planem pierwotnego problemu (7)–(9).

Twierdzenie 6 (oznaką niezgodności systemu ograniczeń ) . Jeśli optymalnie M-problem, co najmniej jedna ze zmiennych sztucznych jest różna od zera, to układ więzów pierwotnego problemu jest niespójny.

Gdy M-linia indeksu zadań stół simpleksowy Dzielimy to na dwie części. Pierwsza linia zawiera wolne terminy wyrażeń
I
, a w drugim – współczynniki zawierające M. Znak optymalności jest sprawdzany najpierw względem drugiej linii. Określa także zmienną, którą należy uwzględnić w podstawie. Ponieważ z podstawy wyklucza się zmienne sztuczne, można pominąć odpowiadające im kolumny elementów. Wyjaśnia to fakt, że sztuczne zmienne nie są zwracane do podstawy, w związku z czym odpowiednie kolumny nie będą już potrzebne. Po wyeliminowaniu z bazy wszystkich sztucznych zmiennych, proces poszukiwania optymalnego planu jest kontynuowany w oparciu o pierwszą linię funkcja celu.

Przykład 4. Rozwiąż problem programowania liniowego, korzystając ze sztucznej podstawy

Pierwsze ograniczenie ma preferowaną zmienną X 3, ale drugiego nie. Dlatego wprowadzamy do niego sztuczną zmienną w 1. Dochodzimy do M- zadanie

Dodajmy warunek M- problemy w tabeli simplex. 5. Jak wygląda wstępny plan referencyjny X 0 = (X 1 ;X 2 ;X 3 ;X 4 ;w 1) = (0; 0; 2; 0; 12),z(X 0) = 0 – 12M.

Tabela 5

	Z B
z J – C J

Dokonajmy niezbędnych wyjaśnień.

Wygodnie jest podzielić linię indeksu na dwie części. W pierwszym z nich wolne terminy wyrażeń  0 = C B A 0 i J =C B A J –C J, a w drugim – współczynniki zawierające M. Na przykład do stołu. 5:

Najpierw sprawdzamy znak optymalności za pomocą drugiej linii linii indeksu. Ponieważ są w nim negatywne oceny, plan X 0 nie jest optymalne.

Przejdźmy do nowego stołu. 6.

Kolumnę rozdzielającą można znaleźć przez max(|–3 M|; |–4M|} = 4M, linia rozdzielczości jest określona przez
. Dlatego 1 jest elementem umożliwiającym.

Tabela 6

	Z B
z J – C J

W linii indeksu nie ma ocen negatywnych. Zatem zgodnie z kryterium optymalności plan odniesienia (0; 2; 0; 0; 4) jest optymalny. Ale ponieważ w optymalnym planie sztuczna zmienna w 1 nie jest równe 0, to zgodnie z Twierdzeniem 6 układ więzów pierwotnego problemu jest niespójny. Problem nie ma rozwiązania.

Odpowiedź: nie ma decyzji.

Przykład 5. Rozwiąż problem, używając sztucznej podstawy

Zorganizujmy nagranie oryginalnego zadania. Pomnóżmy drugą nierówność przez –1:

Sprowadźmy problem do postaci kanonicznej. Dostajemy

Pierwsze i czwarte ograniczenie mają preferowane zmienne, ale drugie i trzecie nie. Dlatego wprowadzamy do nich zmienne sztuczne w 1 i w 2. Dochodzimy do M- zadanie

Dodajmy warunek M- problemy w tabeli simplex. 7. Jak wygląda początkowy plan referencyjny X 0 = (0; 0; 10; 0; 0; 4; 3; 9),z(X 0) = 0 + 12M.

Tabela 7

	Z B
z J – C J

Rozwiązujemy problem do minimum. Najpierw sprawdzamy znak optymalności za pomocą drugiej linii linii indeksu. Ponieważ jest w nim pozytywna ocena, plan X 0 nie jest optymalne. Przejdźmy do nowego stołu. 8.

Tabela 8

		Z B

Do tej pory rozpatrywaliśmy kompleksowo problem, którego rozwiązanie przeprowadzono w oparciu o najprostszy algorytm metody simpleks, gdyż wszystkie ograniczenia miały postać mniejszą lub równą. W tym przypadku dodatkowo zmienne zadania tworzą bazę jednostkową. Może się jednak okazać, że system ograniczeń przedstawiony jest w formie kanonicznej, ale nie jest zredukowany do podstawy jednostkowej.

Przy rozwiązywaniu takich problemów wprowadzono metoda sztucznej bazy. Jest to szczególnie wygodne, gdy liczba zmiennych znacznie przekracza liczbę równań.

Algorytm rozwiązania problemu metoda simplex Spójrzmy na przykład ze sztuczną podstawą.

Przykład 1

Znajdź maksimum Z=4X1+2X2+X3

3Х1+2Х2+Х3=15

Хj30, j=1,...,3

Przejdźmy do formy kanonicznej:

X1+X2+X3-X4=8

2Х1+Х2+Х3+Х5=8

3Х1+2Х2+Х3=15

Хj30, j=1,...,5

Zmax=4X1+2X2+X3+0×X4+0×X5

Ten system ograniczenia nie mają podstawy jednostkowej, ponieważ dodatkowa zmienna X4 ma współczynnik minus jeden, a trzecie ograniczenie zostało reprezentowane przez równanie i nie ma zmiennej bazowej. Aby istniała podstawa jednostkowa, wprowadzamy odpowiednie ograniczenia sztuczne zmienne y1 i y2 z dodatnimi współczynnikami (+1).

Należy zaznaczyć, że zmienne sztuczne wprowadza się jedynie w celu matematycznego sformalizowania problemu. Dlatego schemat obliczeń musi być taki, aby w ostatecznym rozwiązaniu wśród zmiennych podstawowych nie mogły zostać uwzględnione zmienne sztuczne. W tym celu dla zmiennych sztucznych w funkcji celu wprowadza się współczynnik M, oznaczający bardzo duża liczba. W praktyce (szczególnie przy rozwiązywaniu problemu na komputerze) zamiast M przyjmują określoną dużą liczbę, na przykład 10000. Ponadto, rozwiązując problem maksymalnie, współczynnik ten wprowadza się do funkcji celu z minusem znak, a przy rozwiązywaniu do minimum, ze znakiem plus. Teraz rozwiążemy problem T (M), którego funkcja celu zawiera funkcję celu zadania Z i sztuczne zmienne o współczynniku ±M, tj.

T=Z-M S yi, przy wyznaczaniu maksimum funkcji celu i

T=Z+M S y, przy wyznaczaniu minimum funkcji celu

W naszym przypadku:

X1+X2+X3-X4+y1=8

2Х1+Х2+Х3+Х5=8

3Х1+2Х2+Х3+y2=15

Хj30, j=1,...,5

Тmax= 4X1+2X2+X3+0×X4+0×X5 - M(y1+y2)

Problem ten rozwiązano w tabelach simpleksowych, ale dla wygody funkcja celu została podzielona na 2 linie:

W pierwszym wierszu zapisujemy szacunki, które nie zawierają współczynnika M;

W drugim wierszu znajdują się oszacowania dla każdej zmiennej wolnej, zawierające współczynnik M.

Elementy (wyniki) tych dwóch linii oblicza się za pomocą wzoru (2). Jedyna różnica:

Przy obliczaniu estymatorów wiersza Z należy uwzględnić współczynniki Cj zawarte w funkcji Z;

Przy obliczaniu szacunków linii M współczynnik ten nie jest brany pod uwagę, a M jest brane jako wspólny czynnik.

Aby zadanie T i zadanie Z było równe, konieczne jest, aby yi było równe zero. Dlatego też, dopóki y i nie jest równe zero, kolumna rozdzielcza jest wybierana na podstawie oszacowań w drugim wierszu przy użyciu algorytmu metody simpleks.

Dopiero gdy y i stanie się równe zeru, dalsze obliczenia zostaną przeprowadzone przy użyciu pierwszej linii indeksu, tj. -regularne zadanie Z.

Co więcej, gdy sztuczna zmienna zostanie wyprowadzona z bazy, wyrzucimy ją z tablicy simpleksowej, a następna tabela sympleksowa nie będzie miała poprzedniej kolumny rozdzielczej.

Istnieje związek pomiędzy optymalnymi rozwiązaniami problemu M i problemu Z, ustalony w następujący sposób twierdzenie:

1. Jeśli w optymalne rozwiązanie W problemie M wszystkie zmienne sztuczne (y i) są równe zeru, wówczas to rozwiązanie będzie optymalnym rozwiązaniem problemu Z.

2. Jeżeli w optymalnym rozwiązaniu problemu M przynajmniej jedna ze zmiennych sztucznych jest różna od zera, to problem Z nie ma rozwiązania ze względu na niezgodność układu więzów.

3. Jeśli M-problem okaże się nierozwiązalny (T®+¥ lub -¥), to pierwotny problem również jest nierozwiązalny albo z powodu niezgodności układu więzów, albo dlatego, że funkcja Z jest nieograniczona.

Stwórzmy pierwszą tabelę simplex. Przy rozwiązywaniu metodą M kolumnę rozdzielającą w wierszu M można wybrać nie według największego ujemnego oszacowania wartości bezwzględnej (przy rozwiązywaniu dla maksimum), a nie według największego dodatniego oszacowania (przy rozwiązywaniu dla minimum ), ale według tego, który wyświetla Y szybciej od podstawy. W w tym przykładzie kolumną rozdzielającą będzie kolumna zmiennej wolnej X2 z wynikiem (-3).

Tabela 3.1.

Pierwsza tabela simplex

Wypełnienie linii Z odbywa się według wzoru (2):

a00 = 0 × 8– 0 = 0

a01 =0 × 2– 4 = -4

a02 =0 × 1– 2 = -2

a03 =0 × 1– 1 = -1

a02 =0 × 0– 0 = 0

Wypełnianie linii M:

а¢00 = -М × 8 + (–М) × 15 = -23М

а¢01 = -М × 1 + (–М) × 3= -4М

а¢02 = -М × 1 + (–М) × 2= -3М

а¢03 = -М × 1+ (–М) × 1 = -2М

а¢04 = -М ×(-1)+ (–М) × 0 = 1М

Wyciągamy M jako wspólny czynnik.

Ostatnia kolumna w wierszu rozdzielczości zawiera 0, zatem kolumna wolnej zmiennej X4 jest przekazywana bez zmian.

Tabela 3.2.

Druga tabela simplex

W drugiej tabeli otrzymujemy rozwiązanie zdegenerowane, ponieważ otrzymujemy dwie identyczne minimalne relacje sympleksowe. Dlatego znajdujemy związek elementów kolumny obok rozdzielającej z elementami kolumny rozdzielającej, biorąc pod uwagę znak.

Tabela 3.3.

Trzecia tabela simplex

Teraz rozwiązujemy zwykłą metodą simplex.

Tabela 3.4.

Czwarta tabela simplex

Św.P	Cj
B.P.	Ci	ai0	X5	X4
X3				-1
X1
X2			-2	-1
Z

W linii oceny wszystkie elementy mają wartości nieujemne, dlatego uzyskuje się rozwiązanie optymalne:

Zmax=15 Xopt(0,7,1,0,0)

Przykład2

Problem został rozwiązany do minimum (Z®min) funkcji celu. W ostatniej iteracji otrzymaliśmy następującą tabelę:

Tabela 3.5.

Najnowsza tabela simplex

Św.P	Cj
B.P.	Ci	ai0	X1	X3	X4
U1	M	-1/2	-1/2	-1/2	-1
X5		1/2	1/2	1/2
X2		15/2	3/2	1/2
Z			-1
	M	-1/2	-1/2	-1/2	-1

W problemie T uzyskano rozwiązanie optymalne, ponieważ w rzędzie M nie ma już pozytywnych oszacowań, tj. wybór kolumny rozdzielczej jest niemożliwy, a podstawą jest U1. W tym przypadku pierwotny problem nie ma rozwiązania z powodu niezgodność systemu ograniczeń.

Warunkiem koniecznym zastosowania metody simpleks jest obecność planu referencyjnego, czyli akceptowalnego podstawowe rozwiązanie system kanoniczny równania. Aby to zrobić, muszą zostać spełnione następujące warunki:

• system musi mieć strukturę kanoniczną (krokową);
• istnieją jedynie ograniczenia równości;
• prawa strona więzów jest dodatnia;
• zmienne zadania są dodatnie.

Bez tych warunków nie ma możliwości uzyskania planu referencyjnego. Jednak w rzeczywistych problemach wymienione warunki nie zawsze są spełnione.

Istnieje specjalna metoda zwana sztuczną bazą, która pozwala uzyskać początkowy plan odniesienia w dowolnym zadaniu programowania liniowego.

Niech problem programowania liniowego zostanie zredukowany do postaci standardowej:

Niech wszyscy /? > 0, ale niektóre lub wszystkie zmienne bazowe są ujemne, X; 0. Dlatego nie ma planu odniesienia.

Uzupełnijmy równania więzów sztucznymi zmiennymi (zakładamy, że all x j j - 1, P).

Przedstawmy T zmienne (według liczby równań): x lM te, które są w środku nowy system będzie podstawowa i ujemna X-

W rezultacie otrzymujemy następujący problem równoważny.

Oto zmienne x n+i nie mam z tym nic wspólnego oryginalny problem Programowanie liniowe. Służą one jedynie do uzyskania planu odniesienia i nazywane są zmiennymi sztucznymi. I nowy

funkcja docelowa /(.t) jest tworzona dla kompletności problemu.

W optymalnym projekcie odniesienia sztuczne zmienne powinny wynosić zero. W przeciwnym razie warunki pierwotnego problemu zostaną naruszone.

W pierwotnym planie odniesienia zmienne sztuczne są podstawowe, to znaczy nie są równe zeru, a w planie optymalnym zmienne sztuczne muszą być równe zeru. Oznacza to, że sztuczne zmienne powinny optymalnie stać się wolne. To tłumaczenie jest główną ideą metody: tłumaczeniem sztucznych zmiennych ze zmiennych podstawowych na wolne. Przyjrzyjmy się mechanizmowi takiego tłumaczenia na przykładzie.

Przepiszmy ZLP w standardowej formie. W tym celu wprowadzamy dodatkowe zmienne x ) , x A, x 5 , x 6 i zapisz problem w formie kanonicznej.

Zmienne swobodne x, X 2 = 0, w takim przypadku zmienne podstawowe przyjmą wartości x 3 = -5, x 4 = -5, x 5 = 7, x 6 = 9. Ponieważ niektóre z podstawowych zmiennych są ujemne, dlatego nie ma planu odniesienia. Aby otrzymać początkowy plan odniesienia, w pierwszych dwóch równaniach ograniczeń wprowadzamy zmienne x 7, x 8 i formułujemy zadanie pomocnicze:

Zatem podstawą początkową jest

Stół Simplex ze sztuczną podstawą

	X4

Zapiszmy sekwencje planów referencyjnych.

Dla pierwszych trzech kroków przyrostowych A do są obliczane wyłącznie na podstawie sztucznych zmiennych, które są zawarte w sztucznej funkcji celu /(x) = x 7 + x 8 ze współczynnikiem c, = 1.

W trzecim etapie wyklucza się zmienne sztuczne, ponieważ wszystkie A do są pozytywne.

Zatem metoda simpleksowa z wprowadzeniem sztucznych zmiennych obejmuje dwa etapy.

Formacja i decyzja zadanie pomocnicze LP z wprowadzeniem sztucznych zmiennych. Sztuczne zmienne w początkowym projekcie odniesienia są podstawowe. Sztuczna funkcja celu obejmuje tylko sztuczne zmienne. Po otrzymaniu sąsiadujących planów referencyjnych przenosimy sztuczne zmienne z podstawowych na wolne. W rezultacie uzyskano optymalny plan odniesienia dla problemu pomocniczego /(x) = 0.

Optymalny plan odniesienia pomocniczego problemu LP jest początkowym planem odniesienia głównego problemu LP. Problem został rozwiązany dla pierwotnej funkcji celu /(x) przy użyciu zwykłej metody simplex.

Notatki

• 1. Wprowadzenie sztucznych zmiennych wymagane jest w dwóch przypadkach:
  • pewna liczba podstawowych zmiennych x jest ujemna w postaci kanonicznej;
  • jeśli trudno jest sprowadzić do postaci kanonicznej, po prostu dodaj sztuczną zmienną do dowolnego równania ograniczającego.
• 2. Występujące w praktyce automatyczna kontrola Problemy programowania liniowego zawierają od 500 do 1500 ograniczeń i ponad 1000 zmiennych. Oczywiste jest, że problemy tego wymiaru można rozwiązać jedynie za pomocą komputera i specjalnego oprogramowanie. Złożoność algorytmu polega na tym, że:
  • PPP wymaga spojrzenia kanonicznego;
  • PPP w przypadku problemów tej wielkości wymaga użycia dużych komputerów (i Równoległe obliczenia), ponieważ metoda simplex przechowuje całą tabelę.
• 3. Efektywność obliczeniową metody sympleksowej można ocenić za pomocą następujących wskaźników:
  • liczba kroków (sąsiadujące plany wsparcia);
  • koszty czasu pracy maszyny.

Istnieją takie teoretyczne szacunki dla standardowe zadanie programowanie liniowe za pomocą T ograniczenia i zmienne:

• średnia liczba kroków * 2 T i leży w zakresie )