02.pdf

Badania operacyjne

dr inż. W. Zalewski

Badania operacyjne

dr inż. W. Zalewski

METODA SIMPLEKS

Rozpatrzmy dane zadanie PL w postaci standardowej

wyrażonej zależnością macierzową:

Jeżeli każda zmienna bazowa jest różna od zera, to takie

rozwiązanie bazowe jest niezdegenerowane. Jeżeli chociaż jedna

zmienna bazowa jest zerowa, to mamy do czynienia z rozwiąza-

niem bazowym zdegenerowanym.

max

Ax = b

Metoda simpleks polega na przechodzeniu od jednego

dopuszczalnego rozwiązania bazowego do drugiego, o którym

wiemy, że jest nie gorsze od poprzedniego.

gdzie:

A – macierz współczynników o wymiarach ( m

n ),

x – n -wymiarowy wektor zmiennych,

b – m -wymiarowy wektor wyrazów wolnych,

c – n -wymiarowy wektor wag funkcji celu.

Jeżeli układ Ax = b jest niesprzeczny oraz n > m , to istnieje

nieskończenie wiele rozwiązań, ale istnieje skończona liczba

rozwiązań bazowych. Układ m równań z n zmiennymi ma co

Możemy wyznaczyć macierz kwadratową B o wyznaczniku

różnym od zera, która składa się z m liniowo niezależnych kolumn

macierzy A .

najwyżej

Macierz B nazywać będziemy bazą , jej kolumny –

kolumnami bazowymi , a pozostałe kolumny macierzy A –

kolumnami niebazowymi .

Postępowanie przy szukaniu rozwiązań bazowych w metodzie

simpleks polega na realizacji następujących kroków:

Z każdą bazą B układu Ax = b związane jest rozwiązanie

bazowe, które można uzyskać w następujący sposób:

É wybrać m liniowo niezależnych kolumn macierzy A , czyli

bazę B ,

1. Wyznaczenie rozwiązania wyjściowego, dopuszczalnego i

bazowego.

2. Sprawdzenie, czy aktualne rozwiązanie bazowe jest

optymalne. Jeżeli tak, to zakończenie obliczeń. Jeżeli nie, to

przejście do kroku 3.

3. Rozpatrzenie sąsiedniego rozwiązania bazowego, o którym

wiemy, że jest nie gorsze od poprzedniego i powrót do kroku 2.

É zmienne niebazowe przyjąć równe zero ( x N = 0 ),

É wartość zmiennych bazowych ustalić rozwiązując układ

m równań z m niewiadomymi: Bx B = b .

HACKED BY VIPER :)

Badania operacyjne

dr inż. W. Zalewski

Badania operacyjne

dr inż. W. Zalewski

Postać bazowa zadania programowania liniowego

Tablica simpleksowa

Przy danej bazie B wektor współczynników X oraz macierz

współczynników A można przedstawić jako:

Elementy j-tej kolumny tablicy simpleksowej oraz kolumny

wartości zmiennych bazowych definiujemy w następujący sposób:

x = (x B , x N ) ,

A = (B, N),

Ax = b

Bx B + Nx N = b ,

stąd

-1 Bx B + B -1 Nx N = B -1 b ,

Ix B + Wx N = b * ,

Rozwiązanie bazowe jest równe x B = b * przy x N = 0 .

__________

______

Dwie bazy B i B’ nazywamy sąsiednimi jeżeli różnią się

tylko jedną kolumna macierzy A .

Dwa rozwiązania bazowe nazywamy sąsiednimi, jeżeli różnią

się tylko jedną zmienną bazową.

gdzie A j – j-ta kolumna macierzy współczynników A .

Układ równań będzie miał postać:

∑ ∈

(i = 1, 2, ..., m)

( )

Oznaczając przez x 0 wartość funkcji celu oraz wektor c dla

danej bazy B jako c = ( c B , c N ) można zapisać:

Wartość funkcji celu:

x 0 = c B x B + c N x N = c B ( b * - Wx N ) + c N x N = c B b * + ( c N – c B W ) x N .

∑ ∈

j x

Kryterium optymalności rozwiązania bazowego jest warunek:

Wskaźnik kryterium optymalności stojący przy j-tej zmiennej:

c N – c B W

∑ ∈

c B

Oznacza on, że każdy przyrost zmiennej niebazowej nie zwiększy

wartości funkcji celu, czyli rozwiązanie jest optymalne.

HACKED BY VIPER :)

Badania operacyjne

dr inż. W. Zalewski

Badania operacyjne

dr inż. W. Zalewski

Postać tablicy simpleksowej dla postaci bazowej, w której

przy n zmiennych pierwsze m zmiennych jest zmiennymi

bazowymi

Początkowe rozwiązanie bazowe

Postać bazowa powinna zawierać nieujemny wektor

wyrazów wolnych. Przyjęcie jako zmiennych bazowych

zmiennych związanych z wektorami jednostkowymi prowadzi do

początkowego rozwiązania bazowego w postaci:

c j

c 1 , c 2 , ..., c m

m+1 , c m+2 , ..., c n

b *

x B = b,

x N = 0 .

c i

zmienna

bazowa

x 1 , x 2 , ..., x m

x m+1 , x m+2 , ..., x n

Gdy macierz współczynników w postaci standardowej nie

zawiera macierzy jednostkowej należy:

É tak przekształcić układ równań, stosując reguły metody

eliminacji Gaussa, aby zawierał on macierz jednostkową,

lub

É sztucznie utworzyć macierz jednostkową, uzupełniając macierz

współczynników A o odpowiednią liczbę brakujących

wektorów jednostkowych (metoda sztucznej bazy).

c 1

x 1

1, 0, ..., 0

t 1,m+1 , t 1,m+2 , ..., t 1,n

t 10

c 2

x 2

0, 1, ..., 0

t 2,m+1 , t 2,m+2 , ..., t 2,n

t 20

c m

x m

0, 0, ..., 1

t m,m+1 , t m,m+2 , ..., t m,n

t m0

z j

z 1 , z 2 , ..., z m

m+1 , z m+2 , ..., z n

x 0

t 0j = c j - z j

t 01 , t 02 , ..., t 0m

t 0,m+1 , t 0,m+2 , ..., t0,n

t 00

Wprowadzając sztuczne zmienne uzyskujemy nowe,

Element t ij > 0 określa, o ile zmniejszy się wartość zmiennej

równoważne, pomocnicze zadanie programowania liniowego.

bazowej x (i) , jeżeli zmienna niebazowa x j przyjmie wartość jeden.

Optymalne rozwiązanie zadania pomocniczego wyznacza

Podobnie element t ij < 0 określa, o ile zwiększy się wartość

optymalne rozwiązanie zadania wyjściowego, jeżeli wszystkie

zmiennej bazowej x (i) , jeżeli zmienna niebazowa x j przyjmie

zmienne sztuczne w rozwiązaniu optymalnym są równe zero.

wartość jeden.

Jeżeli chociaż jedna zmienna sztuczna jest dodatnia, to wyjściowe

zadanie jest sprzeczne.

HACKED BY VIPER :)

Badania operacyjne

dr inż. W. Zalewski

Badania operacyjne

dr inż. W. Zalewski

Reguła wyboru zmiennej usuwanej z bazy – określa, którą

Kryterium simpleksowe

zmienną należy usunąć z bazy aby nowe rozwiązanie bazowe było

Z każdą zmienną x j związany jest wskaźnik kryterium

optymalności t 0j . Wskaźnik ten dla zmiennych bazowych zawsze

jest zerowy.

dopuszczalne.

min

ędzie to zmienna x r dla której:

Przy pomocy kryterium simpleksowego można ocenić:

Reguła wyznaczania nowej tablicy simpleksowej – służy do

É czy rozwiązanie bazowe jest optymalne,

określenia elementów nowej tablicy związanej z nową bazą po

É którą zmienną niebazową należy wprowadzić do bazy,

ustaleniu zmiennej wprowadzanej i usuwanej z bazy.

É czy istnieje jedno, czy więcej rozwiązań optymalnych.

Nowe elementy ustala się korzystając z poprzedniej tablicy

simpleksowej na podstawie zależności:

Kryterium optymalności – sprawdza czy dane dopuszczalne

rozwiązanie bazowe jest optymalne.

≠

;

Rozwiązanie jest optymalne jeżeli: t 0j

0 (j

Z N )

Degeneracja rozwiązania bazowego - sytuacja, w której chociaż

Kryterium wyboru zmiennej bazowej – ustala, którą zmienną

jedna zmienna bazowa jest zerowa. Mogą wystąpić martwe kroki

niebazową należy wprowadzić do nowej bazy aby uzyskać

związane z tym samym punktem rozwiązania bazowego. Wartość

największą poprawę wartości funkcji celu.

zmiennych i funkcji celu nie ulega zmianie.

Jeżeli dane rozwiązanie bazowe nie jest optymalne, to istnieje

przynajmniej jeden dodatni wskaźnik optymalności. Do nowej

bazy należy wprowadzić zmienną x k o maksymalnym wskaźniku

optymalności, dla której: t 0k = max {t 0j

Z N }.

HACKED BY VIPER :)

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: