Politechnika Wrocławska.

Wydział: Elektroniki

Algorytmy optymalizacji - projekt

Temat: metoda simpleks dualny.

Autorzy:

Tomasz Kaczor 117643

Piotr Jacko 117574

pod kierunkiem:

Dr inż. Ewa Szlachcic

Wrocław 2004

1. Sformułowanie zadania optymalizacji.

Wektor zmienny decyzyjnych x:

X = [x₁ , x₂ , x₃ , .... , x_n ]^T

gdzie: n - ilość zmiennych decyzyjnych

Funkcja celu f(x):

f(x): Rⁿ R¹

oraz m funkcji ograniczeń g_i(x)

g_i(x) : Rⁿ R¹ dla i = 1,2, ... , m

Zadanie optymalizacji polega na znalezieniu wektora zmiennych decyzyjnych x, należącego do zbioru rozwiązań dopuszczalnych X w postaci:

X={x: g_i(x) <= 0 , i = 1 , 2 , .. , m}

takiego, że dla ∀ x∈X

f(
) <= f(x)

Co jest równoznaczne zapisowi :

= f(
)

• Omówienie algorytmu optymalizacji

Metoda simpleks jest metodą sekwencyjnego, ściśle określonego przeglądania rozwiązań bazowych. W kolejnych iteracjach poprawiamy bieżącą wartość funkcji celu i coraz bardziej zbliżamy się do rozwiązania optymalnego (o ile ono istnieje). Po przejściu skończonej liczby kroków można uzyskać rozwiązanie optymalne lub stwierdzić jego brak.

W metodzie simpleks stosujemy ukierunkowany przegląd zbioru rozwiązań bazowych, gdyż pełny przegląd jest w ogólnym przypadku nieefektywny, ze względu na liczbę rozwiązań oraz rozmiary każdego układu równań. W metodzie tej przechodzimy od jednego dopuszczalnego rozwiązania bazowego do drugiego, o którym wiemy, że jest nie gorsze od poprzedniego. Pomijamy więc rozwiązania bazowe niedopuszczalne oraz te, które są gorsze od aktualnie rozpatrywanego.

Wyróżniamy trzy metody (rozwiązywania) rozwiązywania zadań PL

• metoda prymalnego simpleksu

max x₀ = c^Tx x∈X

X = {x: Ax<=b , x>=0}

• metoda dualna simpleks

min x₀ = c^Tx x∈X

X = {x: Ax>=b , x>=0}

• metoda dwufazowa simpleks

max x₀ = c^Tx x∈X

X = {x: A₁x>=b₁ ∩ A₂x<=b₂ , x>=0}

W naszym sprawozdaniu ograniczymy się do opisu jedynie jednego algorytmu „metody dualnego simpleksu ” .

2. Metoda dualnego simpleksu.

Pojawił się nam problem postaci:

(2.1)

Problemem dualnym do (2.1) nazywamy problem programowania liniowego następującej postaci:

(2.2)

Problem (2.1) nazywamy wtedy problemem prymalnym (względem (2.2)).

Ogólna zasada dualności: Jeżeli problem prymalny (2.1) ma rozwiązanie optymalne, to także problem dualny (2.2) ma rozwiązanie optymalne i wartości funkcji celu obu tych rozwiązań są równe.

Zadanie dualne programowania liniowego posiada optymalne rozwiązanie gdy są spełnione:

1.Warunek dualnej dopuszczalności

y_oj>0 , ∀j ∈R

2.Warunek optymalności.

y_io > 0 dla i = 1 ,...,m

Algorytm:

Krok 1. (start). Rozpoczynamy algorytm od znalezienia pierwszej tablicy dualnie dopuszczalnej. Należy sprawdzić dualną dopuszczalność

rozwiązania: czy y_oj >= 0 dla j∈R Tak - idź do kroku 2, Nie - koniec

Krok 2. (test optymalności). Czy y_i0 >= 0 i= 1 , .... , m dla każdego ?

• Tak - to aktualne rozwiązanie jest optymalne.

• Nie - idź do kroku 3.

Krok 3. (Wybór zmiennej usuwanej z bazy). Wybierz jako zmienną usuwaną z bazy taką zmienną x_B dla której y_ro < 0 .

Typową regułą jest wybór zmiennej x_Br dla której:

y_ro = min{y_io , y_io < 0 , i=1..., m }

idź do kroku 4.

Krok 4. (wybór zmiennej wprowadzanej do bazy). Wybierz jako zmienną wchodzącą do bazy taką zmienną x_k dla której:

Jeśli wiele zmiennych spełnia ten warunek, wybierz arbitralnie jedną z nich.

Idż do kroku 5.

Krok 5. (eliminacja). Dokonaj dualną iterację simpleksową metodą eliminacji Gauss'a poprzez wprowadzenie x_k do bazy oraz usunięcie x_Br

Idź do kroku 2.

Przykładowe zadanie:

min x_o = 2x₁ + x₂

przy ograniczeniach:

x₁ + x₂ ≥ 3

x₁ + 2x₂ ≥ 4

x₁,x₂ >0

Powyższe zadanie przekształcamy do postaci:

max x_o = -2x₁ - x₂

-x₁ - x₂ ≤ -3

-x₁ - 2x₂ ≤ -4

Następnie tworzymy tablice simpleksową i postępujemy zgodnie z podanym wcześniej algorytmem:

		-x1	-x2
xo	0	2	1
x3	-3	-1	-1
x4	-4	-1	-2

		-x1	-x4
xo	-2	1,5	0,5
x3	-1	-0,5	-0,5
x2	2	0,5	-0,5

		-x1	-x3
xo	-3	1	1
x4	2	1	-2
x2	3	1	-1

Ostatnia tablica przedstawia rozwiązanie optymalne (y_oj>0 , ∀j ∈R oraz y_io > 0 dla i = 1 ,...,m):

Wartość optymalna f(x)=3 w punkcie x₁ = 0 , x₂= 3.

3. Działanie programu.

Program rozwiązuje zadania postaci:

min x₀ = c^Tx x∈X

X = {x: Ax>=b , x>=0}

Dane wprowadzamy kolejno, zaczynając od ograniczeń (najpierw współczynniki, następnie wyrazy wolne) i kończąc na funkcji celu. Jeszcze przed wprowadzeniem danych, użytkownik jest pytany, czy wszystkie zmienne są dodatnie. Jeśli tak nie algorytm przerywa prace i powracamy do menu głównego. Algorytm ten nie jest bowiem w stanie rozwiązać zadania, w którym jakaś zmienna jest ujemna (w funkcji celu pojawia się wtedy `-` i nie jest spełnione kryterium dualnej dopuszczalności). Po wprowadzeniu danych tworzona jest tablica simpleksowa sprawdzane kryterium dualnej dopuszczalności (zabezpieczenie przed wprowadzaniem niepoprawnych danych wejściowych). Jeśli kryterium nie jest spełnione, program przerywa prace. Jeżeli kryterium zostało spełnione, program wybiera element wychodzący i wchodzący do bazy (zgodnie z kryteriami przedstawionymi w opisie algorytmu). Następnie tablica jest przekształcana metodą eliminacji Gaussa. Cykl powtarza się do momentu znalezienia rozwiązania optymalnego lub stwierdzenia wystąpienia innego przypadku (zadanie sprzeczne, nieskończona liczba rozwiązań).

W programie możemy obejrzeć kolejne tablice simpleksowe, wybierając z menu opcje „pokaż tablice”. Jeśli chcemy zobaczyć postać rozwiązania wybieramy „pokaż rozwiązanie”. W programie dostępna jest także opcja rysowania wykresów („Wykres”) dla zadań 2-wymiarowych.

4. Przykłady testowe.

1. zbiór rozwiązań dopuszczalnych X nie jest zbiorem pustym i istnieje jedno rozwiązanie optymalne PL

Min x₀ = 0,3x₁ +0,6x₂+0,2x₃

Przy ograniczeniach:

Wynik działania programu:

Znaleziono rozwiazanie optymalne po 2 iteracjach

x1 = 300

x2 = 0

x3 = 600

Wartosc optymalna funkcji celu wynosi: 210

2. zbiór rozwiązań dopuszczalnych X nie jest zbiorem pustym i istnieje nieskończona ilość rozwiązań optymalnych.

Min x₀ = 0,1x₁ +0,2x₂+ 0,2x₃ +0,3x₄+0,4x₅

Przy ograniczeniach:

Min x_o = 2x₁ + 2x₂

przy ograniczeniach:

2x₁ + 4x₂ ≥ 1

x₁ + x₂ ≥ 2

2x₁ + x₂ ≥ 3

x ≥ 0

Wynik działania programu:

Rozpoznano 2 wierzcholkow:

1 wierzcholek ma wspolrzedne:

X1 = 2

X2 = 0

2 wierzcholek ma wspolrzedne:

X1 = 1

X2 = 1

Wartosc optymalna funkcji celu wynosi: 4

Obszar rozwiazan optymalnych ma zatem postac:

X' = {x: x = dx1 + (1 - d)x2, d=[0,1] }

3. zbiór rozwiązań dopuszczalnych X jest zbiorem pustym, zadanie nieograniczone.

Min x_o = 2x₁ + x₂

przy ograniczeniach:

-x₁ + x₂ ≥ 3

-x₁ - 2x₂ ≥ 5

x ≥ 0

5. Podsumowanie.

Program został napisany w C++ Borland 3.11. Zaimplementowany algorytm realizuje wszystkie typy zadań z równoczesną sygnalizacją błędu. Na ekranie możemy prześledzić kolejne iteracje simpleksowe, co daje nam możliwość dokładnego przeanalizowania danego zadania, lub też od razu wyświetlić rozwiązanie zadania. Po zapoznaniu się z algorytmami simpleksowymi, możemy stwierdzić, że są one stosunkowo proste w obliczeniach i implementacji (w porównaniu do np. algorytmów ewolucyjnych). Dobrze nadają się do rozwiązywania podstawowych problemów z zakresu optymalizacji.

6. Literatura.

1. D.G. Luenberger , „Teoria optymalizacji” BNI

2. Materiały dostarczone przez Dr inż. E. Szlachcic

3. Notatki z wykładu

8

---