Algorytm Simplex - Historia wersji

Admin o 05:51, 30 wrz 2022

2022-09-30T05:51:24Z

← poprzednia wersja		Wersja z 05:51, 30 wrz 2022
Linia 347:		Linia 347:
	[-1, 2, 1, 0, 100],		[-1, 2, 1, 0, 100],
	[1, -0.5, 0, 1, - 10],		[1, -0.5, 0, 1, - 10],
	[-3,-4,0,0,0]		[3,4,0,0,0]
	]		]

Admin o 04:09, 30 wrz 2022

2022-09-30T04:09:57Z

← poprzednia wersja		Wersja z 04:09, 30 wrz 2022
Linia 1402:		Linia 1402:
	\|		\|
	\|}		\|}
	To zmniejszenie (b[0], b[1]) należy interpretować jako wyliczenie wpływu x3 na x1 i x2 we wspomnianej wyżej ~~nieruchomości~~ (wiersz 1). Jak to policzylibyśmy bez tablicy? Przyjmując x1+2*x2+x3 = 9 (wiersz 1) i x3=2 (6/2 - wiersz 2). Jeśli w ostatecznym wyniku x1=0, to x2=(9-2)/2 =3.5. Czyli dokładnie tyle, ile wylicza algorytm.		To zmniejszenie (b[0], b[1]) należy interpretować jako wyliczenie wpływu x3 na x1 i x2 we wspomnianej wyżej nierówności (wiersz 1). Jak to policzylibyśmy bez tablicy? Przyjmując x1+2*x2+x3 = 9 (wiersz 1) i x3=2 (6/2 - wiersz 2). Jeśli w ostatecznym wyniku x1=0, to x2=(9-2)/2 =3.5. Czyli dokładnie tyle, ile wylicza algorytm.
	[[Plik:Simplex3.ods\|mały]]		[[Plik:Simplex3.ods\|mały]]

Admin: /* Analiza działania algorytmu */

2022-09-29T22:15:06Z

Analiza działania algorytmu

Podgląd zmian

Admin: /* Przykładowa implementacja */

2022-09-29T22:07:56Z

Przykładowa implementacja

Podgląd zmian

Admin: /* Algorytm Simplex */

2022-09-28T22:52:10Z

Algorytm Simplex

← poprzednia wersja		Wersja z 22:52, 28 wrz 2022
Linia 387:		Linia 387:

	0.00, 0.00, -3.67, -6.67, -300.00		0.00, 0.00, -3.67, -6.67, -300.00

			'''Uwaga! Wartości zmiennych w ostatniej kolumnie dotyczą zmiennych bazowych. Jeśli zmienna decyzyjna nie jest obecna w bazie - oznacza to, że w rozwiązaniu jej wartość wynosi zero (0).'''

171.22.162.141: /* Równania i nierówności liniowe */

2022-09-28T22:27:17Z

Równania i nierówności liniowe

← poprzednia wersja		Wersja z 22:27, 28 wrz 2022
Linia 34:		Linia 34:

	== Równania i nierówności liniowe ==		== Równania i nierówności liniowe ==
	~~W algorytmie Simplex rozwiązywane są układy równań i nierówności liniowych.~~ Zanim przejdziemy do algorytmu Simplex, musimy poznać przynajmniej podstawy ~~tego zagadnienia~~.		Zanim przejdziemy do algorytmu Simplex, musimy poznać przynajmniej podstawy rozwiązywania układów równań i nierówności liniowych.

	Rozważmy prosty układ równań:		Rozważmy prosty układ równań:

171.22.162.141: /* Problem programowania liniowego */

2022-09-28T22:25:23Z

Problem programowania liniowego

← poprzednia wersja		Wersja z 22:25, 28 wrz 2022
Linia 30:		Linia 30:

	'''Jest to typowe zagadnienie programowania liniowego.'''		'''Jest to typowe zagadnienie programowania liniowego.'''

	~~Najpopularniejszym algorytmem rozwiązywania problemów programowania liniowego, jest wymyślony w latach czterdziestych XX wieku przez George'a Dantziga algorytm Simplex.~~

	Stosując algorytm Simplex znaleźć rozwiązanie dla powyższego problemu: x1=50 a x2=25, natomiast zarobek wynosi 975zł. W dalszej części tekstu znajdziesz wyjaśnienie jak to zrobić.		Stosując algorytm Simplex znaleźć rozwiązanie dla powyższego problemu: x1=50 a x2=25, natomiast zarobek wynosi 975zł. W dalszej części tekstu znajdziesz wyjaśnienie jak to zrobić.

Admin: /* Postać standardowa problemu */

2022-09-27T00:53:29Z

Postać standardowa problemu

← poprzednia wersja		Wersja z 00:53, 27 wrz 2022
Linia 158:		Linia 158:
	Każde zagadnienie programowania liniowego daje się sprowadzić do postaci standardowej<ref>Justyna Kosakowska i Piotr Malicki, „Badania operacyjne - programowanie liniowe” https://www.snopes.com/fact-check/the-unsolvable-math-problem/</ref>: znaleźć minimum (lub maksimum) funkcji celu z, które równocześnie spełnia zadane ograniczenia (A*x=b).		Każde zagadnienie programowania liniowego daje się sprowadzić do postaci standardowej<ref>Justyna Kosakowska i Piotr Malicki, „Badania operacyjne - programowanie liniowe” https://www.snopes.com/fact-check/the-unsolvable-math-problem/</ref>: znaleźć minimum (lub maksimum) funkcji celu z, które równocześnie spełnia zadane ograniczenia (A*x=b).

	1. Gdy poszukujemy maksimum a nie minimum funkcji z:		1. Gdy poszukujemy maksimum a nie minimum funkcji z: wektor c zastępujemy wektorem −c oraz otrzymaną minimalną wartość funkcji mnożymy przez −1.

	wektor c zastępujemy wektorem −c oraz otrzymaną minimalną wartość funkcji mnożymy przez −1.

	2. Nierówność ai1 * x1 + ai2 * x2 + . . . + ain * xn <= bi		2. Nierówność ai1 * x1 + ai2 * x2 + . . . + ain * xn <= bi
Linia 174:		Linia 172:
	3. Gdy zmienne x nie spełniają ograniczenia (xi>0), korzystamy z faktu, że każda liczba rzeczywista może być przedstawiona jako różnica liczb nieujemnych. Wprowadzamy nowe zmienne xi’ i xi’’ i zamieniamy wystąpienia xi na różnicę xi’-xi’’.		3. Gdy zmienne x nie spełniają ograniczenia (xi>0), korzystamy z faktu, że każda liczba rzeczywista może być przedstawiona jako różnica liczb nieujemnych. Wprowadzamy nowe zmienne xi’ i xi’’ i zamieniamy wystąpienia xi na różnicę xi’-xi’’.

	4. Gdy zmienna xi musi być większa od pewnej wartości di:		4. Gdy zmienna xi musi być większa od pewnej wartości di: xi ≥ di, wprowadzamy zmienną xi’, taką, że xi′ = xi − di

	xi ≥ di

	- wprowadzamy zmienną xi’, taką, że xi′ = xi − di

	Podobnie w przypadku mniejszości (w miejsce większości): xi′ = di − xi		Podobnie w przypadku mniejszości (w miejsce większości): xi′ = di − xi
Linia 186:		Linia 180:
	6. Gdy mamy warunek równości – zamieniamy go na dwa warunki nierówności nieostrej (dotyczy to także =0).		6. Gdy mamy warunek równości – zamieniamy go na dwa warunki nierówności nieostrej (dotyczy to także =0).
	Przedstawmy zagadnienie z wcześniej rozważanego przykładu w postaci wektorowej:		Przedstawmy zagadnienie z wcześniej rozważanego przykładu w postaci wektorowej:
			----Przedstawmy zagadnienie z wcześniej rozważanego przykładu w postaci wektorowej:
	Przedstawmy zagadnienie z wcześniej rozważanego przykładu w postaci wektorowej:

	(1) x1>=2x2 – 100 == -x1+2x2 <= 100 == -1x1 + 2x2 <= 100		(1) x1>=2x2 – 100 == -x1+2x2 <= 100 == -1x1 + 2x2 <= 100
Linia 234:		Linia 227:

	== '''Podstawy''' ==		== '''Podstawy''' ==
	Aby zrozumieć algorytm Simplex, rozwiązujący zagadnienia programowania liniowego – musimy wprowadzić kilka prostych definicji i spostrzeżeń (lematów). ~~'''~~Wiele z opisów i implementacji algorytmu simplex – jest trudnych do zrozumienia, gdyż brakuje takich prostych objaśnień. Albo też – wręcz przeciwnie – objaśnienia są obszerne i z wykorzystaniem bardziej ogólnych definicji matematycznych (formalnie wprowadzone zbiory wypukłe i ekstrema).~~'''~~		Aby zrozumieć algorytm Simplex, rozwiązujący zagadnienia programowania liniowego – musimy wprowadzić kilka prostych definicji i spostrzeżeń (lematów). Wiele z opisów i implementacji algorytmu simplex – jest trudnych do zrozumienia, gdyż brakuje takich prostych objaśnień. Albo też – wręcz przeciwnie – objaśnienia są obszerne i z wykorzystaniem bardziej ogólnych definicji matematycznych (formalnie wprowadzone zbiory wypukłe i ekstrema).

	(1). Podzbiór zdefiniowany przez ograniczenia nazywamy dopuszczalnym. Każdy element tego zbioru nazywa się rozwiązaniem dopuszczalnym.		(1). Podzbiór zdefiniowany przez ograniczenia nazywamy dopuszczalnym. Każdy element tego zbioru nazywa się rozwiązaniem dopuszczalnym.
Linia 264:		Linia 257:

	x1, x2, x3, x4 >= 0		x1, x2, x3, x4 >= 0




Linia 317:		Linia 312:
	Zauważmy, że dzięki wykorzystaniu zmiennych swobodnych, punkt zerowy w pierwotnym układzie współrzędnych (x1,x2) stał się rozwiązaniem dopuszczalnym.		Zauważmy, że dzięki wykorzystaniu zmiennych swobodnych, punkt zerowy w pierwotnym układzie współrzędnych (x1,x2) stał się rozwiązaniem dopuszczalnym.

	Jeśli początek układu współrzędnych jest rozwiązaniem dopuszczalnym, to jest także rozwiązaniem optymalnym wtedy i tylko wtedy, gdy wszystkie ~~elementy~~ [c] są ~~ujemne~~ (przy założeniu, że funkcja celu ma być maksymalizowana). Uzasadnienie jest proste: jeśli ~~jakiś~~ element [c] (c[i]) jest większy od zera, ~~to możemy zwiększyć wartość funkcji celu, zwiększając odpowiednią zmienną~~ x[i].		Jeśli początek układu współrzędnych jest rozwiązaniem dopuszczalnym, to jest także rozwiązaniem optymalnym wtedy i tylko wtedy, gdy wszystkie współczynniki funkcji celu [c] są mniejsze lub równe zeru (przy założeniu, że funkcja celu ma być maksymalizowana). Uzasadnienie jest proste: skoro wszystkie wartości zmiennych decyzyjnych X są większe lub równe zeru, to jeśli i-ty element [c] (c[i]) jest większy od zera, zwiększenie współrzędnej i (x[i]>0) powoduje zwiększenie funkcji celu.

	Ponieważ algorytm z wykorzystaniem rozwiązania bazowego jest równoważny z algorytmem „geometrycznym” – ta reguła nadal obowiązuje. W przekształceniach dążymy do tego, by wszystkie elementy c były ~~nieujemne~~.		Ponieważ algorytm z wykorzystaniem rozwiązania bazowego jest równoważny z algorytmem „geometrycznym” – ta reguła nadal obowiązuje. W przekształceniach dążymy do tego, by wszystkie elementy c były mniejsze lub równe zeru (przy szukaniu maksimum).

	Do przekształceń wykorzystujemy metodę eliminacji Jordana-Gaussa. W tym celu tworzy się tablicę Simplex – dodając do '''A''' kolumnę '''b''' oraz wiersz '''c''' (uzupełniony zerem do rozmiaru n+1).		Do przekształceń wykorzystujemy metodę eliminacji Jordana-Gaussa. W tym celu tworzy się tablicę Simplex – dodając do '''A''' kolumnę '''b''' oraz wiersz '''c''' (uzupełniony zerem do rozmiaru n+1).
Linia 345:		Linia 340:
	Ten sposób przekształcenia gwarantuje, że wcześniej wybrane do bazy kolumny nie zostaną zmienione – chyba, że zawierają 1 w wybranym aktualnie wierszu.		Ten sposób przekształcenia gwarantuje, że wcześniej wybrane do bazy kolumny nie zostaną zmienione – chyba, że zawierają 1 w wybranym aktualnie wierszu.

	Przekształcamy w ten sposób tablicę simplex tak długo, aż wszystkie elementy c[i] będą ~~nie większe od zera~~, albo nie uda się znaleźć ~~wierzchołka~~ dającego wzrost funkcji celu (wtedy przyjmujemy, że zadanie nie ma rozwiązania).		Przekształcamy w ten sposób tablicę simplex tak długo, aż wszystkie elementy c[i] będą mniejsze lub równe zeru, albo nie uda się znaleźć przekształcenia dającego wzrost funkcji celu (wtedy przyjmujemy, że zadanie nie ma rozwiązania).

	Na naszym przykładzie (ostatni wiersz zawiera funkcję celu):		Na naszym przykładzie (ostatni wiersz zawiera funkcję celu):
Linia 386:		Linia 381:

	Wynik naszych działań:		Wynik naszych działań:

	~~----------------------~~

	Ostatnia kolumna zawiera wynik – wartości zmiennych x oraz funkcji celu:		Ostatnia kolumna zawiera wynik – wartości zmiennych x oraz funkcji celu:

Admin: /* Równania i nierówności liniowe */

2022-09-27T00:43:15Z

Równania i nierówności liniowe

← poprzednia wersja		Wersja z 00:43, 27 wrz 2022
Linia 88:		Linia 88:

	A = [ [-1,2], [1,-0.5], ]		A = [ [-1,2], [1,-0.5], ]

	b = [100, -10]		b = [100, -10]

	c = [3,4]		c = [3,4]

	def z(c,x): # Iloczyn skalarny		def z(c,x): # Iloczyn skalarny

	return sum([c1*x1 for c1,x1 in zip(c,x)])		return sum([c1*x1 for c1,x1 in zip(c,x)])

Admin o 18:25, 25 wrz 2022

2022-09-25T18:25:43Z

← poprzednia wersja		Wersja z 18:25, 25 wrz 2022
Linia 91:		Linia 91:
	b = [100, -10]		b = [100, -10]

	c = [-3,-4]		c = [3,4]

	def z(c,x): # Iloczyn skalarny		def z(c,x): # Iloczyn skalarny
Linia 336:		Linia 336:
	</blockquote>		</blockquote>

	W naszym przykładzie pierwsze rozwiązanie bazowe byłoby optymalne, gdyby lista '''c''' zawierała tylko ujemne elementy. Tak oczywiście nie jest (mamy [3,4]). Wybieramy kolumnę i o ~~największej~~ wartości dodatniej (max('''c[i]''') i wprowadzamy ją do bazy – eliminując współczynniki w tej kolumnie (sprowadzone do zera) – poza jednym – przy nowej zmiennej bazowej.		W naszym przykładzie pierwsze rozwiązanie bazowe byłoby optymalne, gdyby lista '''c''' zawierała tylko ujemne elementy. Tak oczywiście nie jest (mamy [3,4]). Wybieramy kolumnę i o wartości dodatniej (max('''c[i]''') i wprowadzamy ją do bazy – eliminując współczynniki w tej kolumnie (sprowadzone do zera) – poza jednym – przy nowej zmiennej bazowej.

	W wyniku przekształcenia jedna ze zmiennych bazowych x[j] zostanie usunięta z bazy (współczynnik c[j] zostanie wyzerowany, a inna x[i] znajdzie się w bazie (współczynnik a[i] otrzyma wartość 1).		W wyniku przekształcenia jedna ze zmiennych bazowych x[j] zostanie usunięta z bazy (współczynnik c[j] zostanie wyzerowany, a inna x[i] znajdzie się w bazie (współczynnik a[i] otrzyma wartość 1). (Na temat wyboru wiersza i kolumn będzie jeszcze mowa poniżej).

	Taką transformację możemy wykonać w następujący sposób:		Taką transformację możemy wykonać w następujący sposób:
Linia 346:		Linia 346:
	2) odejmujemy ten wiersz od pozostałych po pomnożeniu przez wartość komórki wybranej kolumny zmienianego wiersza (dla wiersza '''u''' będzie to A[u][i]).		2) odejmujemy ten wiersz od pozostałych po pomnożeniu przez wartość komórki wybranej kolumny zmienianego wiersza (dla wiersza '''u''' będzie to A[u][i]).

	Ten sposób przekształcenia gwarantuje, że wcześniej wybrane do bazy kolumny nie zostaną ~~zaburzone~~ – chyba, że zawierają 1 w wybranym aktualnie wierszu.		Ten sposób przekształcenia gwarantuje, że wcześniej wybrane do bazy kolumny nie zostaną zmienione – chyba, że zawierają 1 w wybranym aktualnie wierszu.

	Przekształcamy w ten sposób tablicę simplex tak długo, aż wszystkie elementy c[i] będą nie większe od zera, albo nie uda się znaleźć wierzchołka dającego wzrost funkcji celu (wtedy przyjmujemy, że zadanie nie ma rozwiązania).		Przekształcamy w ten sposób tablicę simplex tak długo, aż wszystkie elementy c[i] będą nie większe od zera, albo nie uda się znaleźć wierzchołka dającego wzrost funkcji celu (wtedy przyjmujemy, że zadanie nie ma rozwiązania).
Linia 401:		Linia 401:


	Trzeba jeszcze ustalić sposób wyboru wiersza i kolumny do wprowadzenia do bazy. Zgodnie z tak zwaną „regułą Blanda” (~~<nowiki>~~https://www.mimuw.edu.pl/~oskar/lecture_13.pdf~~</nowiki>~~), można przyjąć, przy wyborze kolumny wybieramy pierwszą z lewej o dodatnim współczynniku c, a następnie wiersz, dla którego najmniejszy jest iloraz wyrazu wolnego (b[i]) przez element z wybranej kolumny (dla kolumny k będzie to najmniejsza spośród b[i]/a[k][i] (oczywiście pod warunkiem, że mianownik jest dodatni).		Trzeba jeszcze ustalić sposób wyboru wiersza i kolumny do wprowadzenia do bazy. Zgodnie z tak zwaną „regułą Blanda” ( https://www.mimuw.edu.pl/~oskar/lecture_13.pdf ), można przyjąć, przy wyborze kolumny wybieramy pierwszą z lewej o dodatnim współczynniku c, a następnie wiersz, dla którego najmniejszy jest iloraz wyrazu wolnego (b[i]) przez element z wybranej kolumny (dla kolumny k będzie to najmniejsza spośród b[i]/a[k][i] (oczywiście pod warunkiem, że mianownik jest dodatni).

	Rozważmy inny przykład:		Rozważmy inny przykład:
Linia 514:		Linia 514:
	[[Plik:Simplex2.ods\|mały\|Tablica simplex w arkuszu kalkulacyjnym]]		[[Plik:Simplex2.ods\|mały\|Tablica simplex w arkuszu kalkulacyjnym]]

	== ~~Implementacja~~ ==		== Przykładowa implementacja ==
	Istnieje wiele opisów algorytmu i jego implementacji. Na przykład zwięzła implementacja w Pythonie: https://github.com/j2kun/ opisana w tekście: https://jeremykun.com/2014/12/01/linear-programming-and-the-simplex-algorithm/.		Istnieje wiele opisów algorytmu i jego implementacji. Na przykład zwięzła implementacja w Pythonie: https://github.com/j2kun/ opisana w tekście: https://jeremykun.com/2014/12/01/linear-programming-and-the-simplex-algorithm/.