PRZEBIEG ĆWICZENIA II

I. Metoda programowania liniowego PL - metoda dualna simpleks

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

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

przy ograniczeniach:

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

Macierz A' jest to macierz tworzona przez współczynniki przy zmiennych decyzyjnych w kolejnych m ograniczeniach większościowych. 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: min x₀ = x₁ + x₂

Ograniczenia:

--> Interpretacja graficzna:[Author:M]

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

				↑
			-x1	-x2
		0	1	1
	u1	-4	-2	-1
←	u2	-6	-2	-3
	u3	-4	-1	-4
			↑
			-x1	-u2
		-2,00	0,33	0,33
←	u1	-2,00	-1,33	-0,33
	x2	2,00	0,67	-0,33
	u3	4,00	1,67	-1,33
			-u1	-u2
		-2,50	0,25	0,25
	x1	1,50	-0,75	0,25
	x2	1,00	0,50	-0,50
	u3	1,50	1,25	-1,75

Rozwiązanie: x₁ = 1,5, x₂ = 1 - w punkcie o tych współrzędnych znajduje się minimum funkcji celu, przy w/w ograniczeniach. Optymalna wartość funkcji celu wynosi x₀ = 2,5.

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

Funkcja celu: min x₀ = x₁ + x₂

Ograniczenia:

Interpretacja graficzna:

Rozwiązanie zadania tablicową metodą simpleks:

				↑
			-x1	-x2
		0	1	1
←	u1	-4	-1	-2
	u2	-3	-1	-1
			↑
			-x1	-u1
		-2	0,5	0,5
	x2	2	0,5	-0,5
←	u2	-1	-0,5	-0,5
				↑
			-u2	-u1
		-3	1	0
	x2	1	1	-1
←	x1	2	-2	1
			-u2	-x1
		-3	1	0
	x2	3	-1	1
	u1	2	-2	1

Rozwiązanie: Zbiór optymalnych rozwiązań leży na prostej f(x) = x₁ + x₂, między punktami
x' = (2, 1) i x'' = (0, 3). Optymalna wartość funkcji celu wynosi x₀ = 3.

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

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

Funkcja celu: min x₀ = x₁

Ograniczenia:

Interpretacja graficzna:

Rozwiązanie zadania tablicową metodą simpleks:

				↑
			-x1	-x2
		0	1	0
	u1	-3	-1	-1
←	u2	-4	-2	-1
			-x1	-u2
		0	1	0
	u1	1	1	-1
	x2	4	2	-1

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

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

Funkcja celu: min x₀ = x₁ + x₂

Ograniczenia:

Interpretacja graficzna:

Rozwiązanie zadania tablicową metodą simpleks:

				↑
			-x1	-x2
		0	1	1
←	u1	-12	4	-3
	u2	-2	-1	2
			-x1	-u2
		-4	2,33	0,33
	u1	4	-1,33	-0,33
	x2	-10	1,67	0,67

Rozwiązanie: zbiór pusty. Ograniczenia nie mają części wspólnej.

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

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

--> III. Wnioski[Author:M]

1.
, jedno optymalne rozwiązanie

W tym przypadku, malenie funkcji jest powstrzymywane ograniczeniami, którymi są 3 proste. Minimalna wartość funkcji celu znajduje się w punkcie o współrzędnych (1,5; 1) i ma wartość równą
x₀ = 2,5.

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ń. W naszym przykładzie drugie ograniczenie ogranicza zbiór. Zadanie to można w najprostszy sposób rozwiązać za pomocą jednej prostej ograniczanej przez osie x₁ i x₂ (przy założeniu, że x₁ i x₂ > 0). W minimum funkcja celu „pokrywa” się z ograniczeniem, dając w konsekwencji nieskończenie wiele rozwiązań. Minimalne punkty w naszym przykładzie możemy obliczyć ze wzoru:

gdzie λ
[0, 1]. Podczas wyliczania optymalnego punktu metodą tablicową, w zerowym wierszu pry jednym ze współczynników występuje `0' i kryteria wyjścia z bazy są spełnione. Oznacza to, że uzyskany punkt jest optymalny, ale nie jedyny. Istnieje więcej punktów optymalnych, dlatego tworzymy nową bazę, aby sprawdzić ile jest optymalnych rozwiązań. Wynika z niej, że funkcja celu osiąga wartości optymalne na prostej między wierzchołkami `I' i `II” (rys. 2).

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

Funkcja celu ma nieskończenie wiele rozwiązań, na zbiorze nieograniczonym, gdy jest równoległa do jednego z ograniczeń. Wartości optymalne osiągnie, gdy „pokryje się” z funkcją ograniczającą (w naszym przypadku z osia x₂ - rys. 3). W tablicy simpleksowej w zerowym wierszu występuje `0', jednak żadna zmienna nie spełnia kryteriów wyjścia z bazy. Oznacza to, że zbiór jest nieograniczony. Możemy wyznaczyć równanie parametryczne półprostej, na której znajdują się optymalne rozwiązania:

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

Zbiór pusty, występuje wtedy, gdy ograniczenia nie mają wspólnej części. W tablicy simpleksowej nie jest spełniony warunek na wyjście z bazy. W zerowej kolumnie znajduje się najmniejsza (ujemna) wartość ograniczenia, jednak współczynniki bazowe są dodatnie, oznacza to, że nie możemy wybrać zmiennej wchodzącej do bazy. Mamy do czynienie z zadaniem sprzecznym - zbiorem pustym.

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

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

Laboratorium Wydział Elektroniki	Technika optymalizacji
Autorzy: Dawid Tomasz (140517) Garbicz Marcin (140547) Kier: EiT Spec.: ESA	Wrocław, dnia 23.10.2006 Prowadzący: Dr inż. Ewa Szlachcic
Ćwiczenie I Zadanie programowania liniowego dla ograniczeń większościowych	Metoda dualna 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.

---