PRZEBIEG ĆWICZENIA I

I. Metoda programowania liniowego PL - metoda prymalna simpleks

Celem ćwiczenia jest zapoznanie się z podstawową metodą rozwiązywania liniowego zadania optymalizacji na przykładzie prymarnej metody simpleks.

Metoda prymalnego simpleksu pozwala na wyliczenie takiego wektora zmiennych decyzyjnych x, należącego do zbioru rozwiązań dopuszczalnych X, dla którego funkcja celu osiąga maksimum:

przy ograniczeniach:

dim x= nx1, dim c=nx1, dim A'=mxn, dim b = mx1

Wektor b nazywany jest wektorem wyrazów wolnych w ograniczeniach i powinien przyjmować wartości nieujemne.

II. Zadania testowe

1.
, jedno optymalne rozwiązanie.

Funkcja celu: max x₀ = 3x₁ + 5x₂

Ograniczenia:

--> Interpretacja graficzna:[Author:M]

--> Rozwiązanie zadania tablicową metodą simpleks:[Author:M]

				↑
		0	1	2
	0	0	-3	-5
	3	24	2	3
	4	12	2	1
←	5	3	-1	1
			↑
		0	1	5
	0	15	-8	5
←	3	15	5	-3
	4	9	3	-1
	2	3	-1	1
		0	3	5
	0	39,00	1,60	0,20
	1	3,00	0,20	-0,60
	4	0,00	-0,60	0,80
	2	6,00	0,20	0,40

Rozwiązanie: x₁ = 3, x₂ = 6 - w punkcie o tych współrzędnych znajduje się maksimum funkcji celu, przy w/w ograniczeniach.

2.
, nieskończenie wiele rozwiązań na zbiorze ograniczonym - np. odcinek dla n=2.

Funkcja celu: max x₀ = - 2x₁ + 3x₂

Ograniczenia:

Interpretacja graficzna:

Rozwiązanie zadania tablicową metodą simpleks:

				↑
		0	1	2
	0	0	2	-3
←	3	6	-2	3
	4	24	4	3
			↑
		0	1	3
	0	6	0	1
	2	2	-0,67	0,33
←	4	18	6	-1
		0	4	3
	0	6	0	1
	2	4	0,11	0,22
	1	3	0,17	-0,17

Rozwiązanie: Zbiór optymalnych rozwiązań leży na prostej f(x) = - 2x₁ + 3x₂, między punktami
x' = (0, 2) i x'' = (3, 4).

Wyprowadzenie ogólnego wzoru na punkty maksymalne zależnego od λ (λ = [0, 1]).

3.
, nieskończenie wiele rozwiązań na zbiorze nieograniczonym np. pół-prosta dla n=2.

Funkcja celu: max x₀ = - 2x₁ + x₂

Ograniczenia: - 2x₁ + x₂ <= 4 , x >= 0

Interpretacja graficzna:

Rozwiązanie zadania tablicową metodą simpleks:

				↑
		0	1	2
	0	0	2	-1
←	3	4	-2	1
		0	1	3
	0	4	0	1
	2	4	-2	1

Rozwiązanie: nieskończenie wiele rozwiązań na zbiorze nieograniczonym.

4.
zbiór pusty, zadanie PL nie ma rozwiązania.

Nie możne stworzyć takiego przykładu dla prymarnej metody simpleks.

5. Zadanie nieograniczone - funkcja celu może osiągnąć wartość nieskończenie dużą. Żadne ograniczenie nie wstrzymuje jej wzrostu.

Funkcja celu: max x₀ = x₁ + 2x₂

Ograniczenia: - x₁ + x₂ <= 2 , x >= 0

Interpretacja graficzna:

Rozwiązanie zadania tablicową metodą simpleks:

				↑
		0	1	2
	0	0	-1	-2
←	3	2	-1	1
		0	1	3
	0	4	-3	2
	2	2	-1	1

Rozwiązanie: zadanie nieograniczone. Żadne ograniczenie nie zatrzymuje wzrostu funkcji celu.

--> III. Wnioski[Author:M]

1.
, jedno optymalne rozwiązanie

W tym przypadku, wzrostu funkcji jest powstrzymywany ograniczenia, którymi są 3 proste. Maksymalna wartość funkcji celu znajduję się w punkcie o współrzędnych (3, 6). Optymalne rozwiązanie otrzymujemy w 2 iteracji.

2.
, nieskończenie wiele rozwiązań na zbiorze ograniczonym - np. odcinek dla n=2.

Funkcja celu ma nieskończenie wiele rozwiązań, na zbiorze ograniczonym, gdy jest równoległa do jednego z ograniczeń. Drugie ograniczenie ogranicza zbiór. W maksimum funkcja celu „pokrywa” się z ograniczeniem, dając w konsekwencji nieskończenie wiele rozwiązań. Maksymalny punkt możemy obliczyć ze wzoru:

gdzie λ
[0, 1]. Podczas wyliczania optymalnego punktu metodą tablicową, w jednym ze współczynników funkcji celu występuje `0'. Możemy również wyznaczyć zmienną wychodzącą z bazy. Oznacza to, że punkt ten jest optymalny, ale nie jedyny. Istnieje więcej punktów optymalnych, dlatego tworzymy nową tablicę, aby sprawdzić ile jest optymalnych rozwiązań. Wynika z niej, że funkcja celu osiąga wartości optymalne na prostej między wierzchołkami `III' i `IV”.

3.
, nieskończenie wiele rozwiązań na zbiorze nieograniczonym np. pół-prosta dla n=2.

W tym przypadku jest tylko jedno ograniczenie. Funkcja celu ma nieskończenie wiele rozwiązań, na zbiorze nieograniczonym, gdy jest równoległa do tego ograniczenia, wartości optymalne osiągnie, gdy „pokryje się” z funkcją ograniczającą. W tablicy simpleksowej w jednym ze współczynników funkcji celu występuje `0', jednak nie żadna zmienna nie spełnia kryteriów wyjścia z bazy. Oznacza to, że zbiór jest nieograniczony. Możemy wyznaczyć równania parametryczne półprostej, na której znajdują się optymalne rozwiązania:

4.
zbiór pusty, zadanie PL nie ma rozwiązania.

Nie możne stworzyć takiego przykładu dla ograniczeń mniejszościowych, przy założeniu, że optymalnego rozwiązania szukamy w 1-szej ćwiartce.

5. Zadanie nieograniczone - funkcja celu może osiągnąć wartość nieskończenie dużą. Żadne ograniczenie nie wstrzymuje jej wzrostu.

Zadanie nieograniczone, występuje wtedy, gdy żadna funkcja nie ogranicza wzrostu funkcji celu. W tym przypadku funkcja celu dąży do nieskończoności, co widać na rys. 4. W tablicy simpleksowej pojawia się brak możliwości wyjścia z bazy, przy najmniejszej (ujemnej) wartości współczynnika funkcji celu.

Laboratorium Wydział Elektroniki	Technika optymalizacji
Autorzy: Dawid Tomasz (140517) Garbicz Marcin (140547) Kier: EiT Spec.: ESA	Wrocław, dnia 16.10.2006 Prowadzący: Dr inż. Ewa Szlachcic
Ćwiczenie I Zadanie programowania liniowego dla ograniczeń mniejszościowych	Metoda prymalna simpleks

2

Komentarz dotyczy wszystkich rysunków !!!

1. Zamalować obszar wspólny

2. Zaznaczyć wierzchołki simpleksu

3. Narysować kroki przechodzenia z wierzchołka na wierzchołek

Jedno przekształcenie tablic wyliczyć analitycznie

Brak zadania praktycznego, które jest bardzo mile widziane u pani Ewy . Radzę wymyślić ;P.

---