PRZEBIEG ĆWICZENIA III

I. Metoda programowania liniowego PL - metoda dwufazowy simpleks

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

Metoda dwufazowego 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 (minimum):

przy ograniczeniach:

dim x= nx1, dim c=nx1,

Macierz A₁ jest to macierz tworzona przez współczynniki przy zmiennych decyzyjnych w kolejnych m₁ ograniczeniach większościowych, a macierz A₂ jest to macierz tworzona przez współczynniki przy zmiennych decyzyjnych w kolejnych m₂ ograniczeniach mniejszościowych, . Wektory b₁, b₂ nazywane są wektorami wyrazów wolnych w ograniczeniach i powinny przyjmować wartości nieujemne.

II. Zadania testowe

1.
, jedno optymalne rozwiązanie.

Postać standardowa układu:

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

Ograniczenia:

Postać kanoniczna układu:

Funkcja celu: x₀ = 2x₁ + x₂ + 0x₃ + 0x₄ + 0x₅ --> MAX

Ograniczenia: x₁ + 2x₂ - x₃ = 8 | *(-1)

4x₁ + 5x₂ + x₄ = 40

- x₁ + 2x₂ + x₅ = 4

--> Interpretacja graficzna:[Author:M]

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

				↑
		0	x1	x2
	0	0	-2	-1
	x3	-8	-1	-2
	x4	40	4	5
←	x5	4	-1	2
			↑
		0	x1	x5
	0	2	-2,5	0,5
	x3	-4	-2	1
←	x4	30	6,5	-2,5
	x2	2	-0,5	0,5
				↑
		0	x4	x5
	0	13,54	0,38	-0,46
	x3	5,23	0,31	0,23
	x1	4,62	-1,00	-0,38
←	x2	4,31	0,08	0,31
		0	x4	x2
	0	20	0,50	1,50
	x3	2	0,25	-0,75
	x1	10	-0,90	1,25
	x5	14	0,25	3,25

Rozwiązanie: x₁ = 10, x₂ = 0 - w punkcie o tych współrzędnych znajduje się maksimum funkcji celu, przy w/w ograniczeniach. Maksymalna wartość funkcji celu wynosi x₀ = 20.

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

Postać standardowa układu:

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

Ograniczenia:

Postać kanoniczna układu:

Funkcja celu: x₀ = x₁ + x₂ + 0x₃ + 0x₄ + 0x₅ --> MAX

Ograniczenia: x₁ + x₂ + x₃ = 6

x₁ + x₂ - x₄ = 2 | *(-1)

- x₁ + x₂ + x₅ = 2

Interpretacja graficzna:

Rozwiązanie zadania tablicową metodą simpleks:

			↑
		0	x1	x2
	0	0	-1	-1
←	x3	6	1	1
	x4	-2	-1	-1
	x5	2	-1	1
				↑
		0	x3	x2
	0	6	1	0
	x1	6	1	1
	x4	4	1	0
←	x5	8	1	2
		0	x3	x5
	0	6	1	0
	x1	2	0,5	-0,5
	x4	4	1	0
	x2	4	0,5	0,5

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

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.

Postać standardowa układu:

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

Ograniczenia:

Postać kanoniczna układu:

Funkcja celu: x₀ = - x₁ + x₂ + 0x₃ + 0x₄ --> MAX

Ograniczenia: x₁ + x₂ - x₃ = 7 | *(-1)

- x₁ + x₂ + x₄ = 3

Interpretacja graficzna:

Rozwiązanie zadania tablicową metodą simpleks:

				↑
		0	x1	x2
	0	0	1	-1
	x3	-7	-1	-1
←	x4	3	-1	1
			↑
		0	x1	x4
	0	3	0	1
←	x3	-4	-2	1
	x2	3	-1	1
			↑
		0	x1	x4
	0	3	0	1
	x1	2	-0,5	-0,5
	x2	5	-0,5	0,5

Rozwiązanie: nieskończenie wiele rozwiązań na zbiorze nieograniczonym. Rozwiązaniem jest półprosta, którą można zapisać w postaci równania parametrycznego (początek w punkcie (2, 5)):

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

Postać standardowa układu:

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

Ograniczenia:

Postać kanoniczna układu:

Funkcja celu: x₀ = 6x₁ + 5x₂ + 0x₃ + 0x₄ --> MAX

Ograniczenia: x₁ + x₂ - x₃ = 5 | *(-1)

3x₁ + 2x₂ + x₄ = 6

Interpretacja graficzna:

Rozwiązanie zadania tablicową metodą simpleks:

			↑
		0	x1	x2
	0	0	-6	-5
	x3	-5	-1	-1
←	x4	6	3	2
				↑
		0	x4	x2
	0	15	2	-1
	x3	-3	0,33	-0,33
←	x1	2	0,33	0,67
		0	x4	x1
	0	18	2,5	1,5
	x3	-2	0,50	0,50
	x2	3	0,50	1,50

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.

Postać standardowa układu:

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

Ograniczenia:

Postać kanoniczna układu:

Funkcja celu: x₀ = 2x₁ + 3x₂ + 0x₃ + 0x₄ --> MAX

Ograniczenia: 3x₁ + 2x₂ - x₃ = 6 | *(-1)

x₁ + 0x₂ + x₄ = 5

Interpretacja graficzna:

Rozwiązanie zadania tablicową metodą simpleks:

			↑
		0	x1	x2
	0	0	-2	-3
	x3	-6	-3	-2
←	x4	5	1	0
				↑
		0	x1	x2
	0	10	2	-3
	x3	9	3	-2
	x1	5	1	0

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

III. Wnioski

1.
, jedno optymalne rozwiązanie

W tym przypadku, mamy do czynienia ze zbiorem ograniczonym przez 3 proste, które powstrzymują wzrost funkcji celu. Maksymalna wartość funkcji celu znajduje się w punkcie o współrzędnych (10; 0) i ma wartość równą x₀ = 20.

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 zbiór jest ograniczony przez 3 proste. W maksimum funkcja celu „pokrywa” się z ograniczeniem, dając w konsekwencji nieskończenie wiele rozwiązań (podobna sytuacja miałaby miejsce, gdybyśmy badali minimum funkcji celu, jednak rozwiązania znajdowałyby się na innym odcinku). Maksymalne punkty w naszym przykładzie możemy obliczyć ze wzoru:

gdzie λ
[0, 1]. Podczas wyliczania optymalnego punktu metodą tablicową, w zerowym wierszu przy 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 ograniczeniem nr 2 - 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 y_i0 > 0, ponieważ w zerowej kolumnie znajduje się ujemna liczba przy zmiennej x₃. Nie można również stworzyć nowej bazy, ponieważ współczynniki przy zmiennych wyprowadzanych do bazy 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.

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. 5. W tablicy simpleksowej pojawia się brak możliwości wyjścia z bazy, przy najmniejszej (ujemnej) wartości współczynnika funkcji celu.

IV. Dodatek

--> 1. Przykład z instrukcji [Author:M]

Postać standardowa układu:

Funkcja celu: max x₀ = 8x₁ - 9x₂ - 18x₃

Ograniczenia:

Postać kanoniczna układu:

Funkcja celu: x₀ = 8x₁ - 9x₂ - 18x₃ + 0x₄ + 0x5 + 0x6 --> MAX

Ograniczenia: 5x₁ + 5x₂ + 6x₃ + x₄ = 12

8x₁ - 9x₂ - 18x₃ + x₅ = 40

x₁ + x₂ + 4x₃ + x₆ = 10 | *(-1)

Rozwiązanie zadania tablicową metodą simpleks:

					↑
		0	x1	x2	x3
	0	0	-8	9	18
←	x4	35	5	5	6
	x5	40	8	-9	-18
	x6	-10	-1	-1	-4
			↑
		0	x1	x2	x4
	0	-105	-23	-6	-3
	x3	5,83	0,83	0,83	0,17
	x5	145	23	6	3
←	x6	13,33	2,33	2,33	0,67
		0	x6	x2	x4
	0	26,43	9,86	17,00	3,57
	x3	1,07	-0,36	0,00	-0,07
	x5	13,57	-9,86	-3,86	-3,57
	x1	5,71	0,43	1,00	0,29

Rozwiązanie: jedno optymalne rozwiązanie znajduje się w punkcie x* = (5.71, 0, 1.07) i ma wartość równą x₀ = 26.43.

--> 2. Zadanie praktyczne[Author:M]

Firma transportowa dysponuje dwoma samochodami: ciężarowym x₁ i osobowym x₂ oraz zatrudnia dwóch pracowników m₁ i m₂. Dziennie pierwszy kierowca m₁ spędza po 4h za kierownicą obu pojazdów. Drugi kierowca m₂ jeździ 2h pierwszym pojazdem x₁ i 8h drugim pojazdem x₂. Kierowca x₁ może maksymalnie spędzać 10h za kierownicą, zaś kierowca x₂ pracuje minimum 2h dziennie. Należy tak dobrać zmiany dla kierowców, żeby zapewnić maksymalny dochód firmie, wiedząc, że rozwożąc towary samochodem ciężarowym możemy zarobić 1000 zł, zaś samochodem osobowym 500 zł.

Postać standardowa układu:

Funkcja celu: max x₀ = 1000x₁ + 500x₂

Ograniczenia:

Postać kanoniczna układu:

F-cja celu: x₀ = 1000x₁ + 4x₂ + 0x₃ + 0x₄ --> MAX

Ograniczenia: 4x₁ + 4x₂ + x₃ = 10

2x₁ + 8x₂ - x₄ = 2

Rozwiązanie zadania tablicową metodą simpleks:

				↑
		0	x1	x2
	0	0	-1000	-500
←	x3	10	4	4
	x4	-2	-2	-8
			↑
		0	x1	x3
	0	1250	-500	125
←	x2	2,5	1	0,25
	x4	18	6	2
		0	x2	x3
	0	2500	500	250
	x1	2,5	1	0,25
	x4	3	6	0,5

Rozwiązanie: rozwiązaniem optymalnym będzie jazda samochodem ciężarowym po 2,5h w ciągu dnia, przy w/w dyspozycjach kierowców. Takie rozwiązanie da nam zysk wysokości 2500 zł dziennie.

--> 3. Analiza dwufazowej metody simplex[Author:M]

a) konstruowanie I rozwiązania bazowego dopuszczalnego

K1. szukamy y_i0 < 0

	0	x1	x2
0	0	-1	-1
x3	6	1	1
x4	-2	-1	-1
x5	2	-1	1

K2. wiersz 4 przyjmujemy jako pomocniczą funkcję celu

	0	x1	x2
0	0	-1	-1
x3	6	1	1
x4	-2	-1	-1
x5	2	-1	1

K3. z pomocniczej funkcji celu wybieramy kolumnę o minimalnej wartości { y_ij: j N_B, y_ij < 0 }

	0	x1	x2
0	0	-1	-1
x3	6	1	1
x4	-2	-1	-1
x5	2	-1	1

	0	x1	x2
0	0	-1	-1
x3	6	1	1
x4	-2	-1	-1
x5	2	-1	1

K4. dla „przyjętej” kolumny wybieramy wiersz zgodnie z regułami simplexu

	0	x1	x2
0	0	-1	-1
x3	6	1	1
x4	-2	-1	-1
x5	2	-1	1

K5. stosujemy metodę eliminacji Gaussa do uzyskania optymalnego rozwiązania

		0	x3	x2
	0	6	1	0
	x1	6	1	1
	x4	4	1	0
	x5	8	1	2
		0	x3	x5
	0	6	1	0
	x1	2	0,5	-0,5
	x4	4	1	0
	x2	4	0,5	0,5

Laboratorium Wydział Elektroniki	Technika optymalizacji
Autorzy: Dawid Tomasz (140517) Garbicz Marcin (140547) . Kier: EiT Spec.: ESA	Wrocław, dnia 30.10.2006 Prowadzący: Dr inż. Ewa Szlachcic
Ćwiczenie III Zadanie programowania liniowego dla ograniczeń mniejszościowych i większościowych	Dwufazowa metoda simpleks

15

Komentarz dotyczy wszystkich rysunków !!!

1. Zamalować obszar wspólny

2. Zaznaczyć wierzchołki simpleksu

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

Jedno przekształcenie tablic wyliczyć analitycznie

Dodatkowy OBOWIĄZKOWY przykład z instrukcji

Bzdurne pod względem treści i otrzymanych wyników zadanie praktyczne. No cóż … ważne, że jest .

Analiza i wytłumaczenie zasady postępowania w przypadku liczenia simpleksu dwufazowego metodą uproszczoną (bez zmiennej z₀).

---