lecture 3.pdf

METODA SYMPLEKS

Model zagadnienia programowania liniowego jest w postaci

standardowej :

max(min)z = c 1 x 1 + c 2 x 2 +···+ c n x n

a 11 x 1 + a 12 x 2 +···+ a 1n x n = b 1

. . .

a m1 x 1 + a m2 x 2 +···+ a mn x n = b m

x i 0, i = 1, . . . , n

Zbiór ograniczeń można zapisać w postaci macierzowej Ax = b, x 0.

Zakładamy, że rz¸ad macierzy A jest równy m, czyli żadne równanie

nie wynika z innych równań.

Każdy model liniowy można sprowadzić do równoważnej postaci

standardowej w następujący sposób:

1. Ograniczenie postaci a i1 x 1 + a i2 x 2 +···+ a in x n b i

zast¸epujemy dwoma ograniczeniami:

a i1 x 1 + a i2 x 2 +···+ a in x n + s i = b i , s i 0.

2. Ograniczenie postaci a i1 x 1 + a i2 x 2 +···+ a in x n b i

zast¸epujemy dwoma ograniczeniami:

a i1 x 1 + a i2 x 2 +···+ a in x n −s i = b i , s i 0.

3. Jeżeli zmienna x i może przyjmować wartości ujemne to

wykonujemy podstawienie: x i = u i −v i i dodajemy ograniczenia

u i 0, v i 0.

Przykład 1. Sprowadzić do postaci standardowej problem:

max z = 2x 1 + 3x 2 − x 3

x 1 − 2x 2 5

x 2 + 3x 3 3

x 1 + x 2 − 2x 3 = 20

x 1 , x 2 0

Przekształcamy ograniczenia 1 i 2 oraz wykonujemy podstawienie x 3 = u 3 − v 3 co daje postać standardową:

max z = 2x 1 + 3x 2 − u 3 + v 3

x 1 − 2x 2 + s 1 = 5

x 2 + 3u 3 + 3v 3 − s 2 = 3

x 1 + x 2 − 2u 3 + 2v 3 = 20

x 1 , x 2 , s 1 , s 2 , u 3 , v 3 0

Deﬁnicja 1. Rozpatrzmy układ ograniczeń Ax = b . Wybierzmy

dokładnie m zmiennych i nadajmy pozostałym n−m zmiennym

wartości zerowe. Otrzymujemy w ten sposób układ m równań o m

niewiadomych. Jednoznaczne rozwiazanie tego układu nazywamy

rozwiazaniem bazowym . Wybrane zmienne nazywamy

zmiennymi bazowymi i oznaczamy przez ZB natomiast pozostałe

zmienne (tj. te, którym przypisano wartości 0) nazywamy

zmiennymi niebazowymi i oznaczamy przez N B .

Uwaga: Wybrane zmienne s¸a bazowe wtedy i tylko wtedy, gdy

odpowiadaj¸ace im kolumny w macierzy A s¸a liniowo niezależne. Zbiór

tych kolumn nazywamy baza i oznaczamy przez B. Przez B będziemy

również oznaczać macierz utworzoną z tych kolumn.

Przykład 2. Wyznaczyć kilka rozwiazań bazowych układu

ograniczeń:

x 1 + x 2 + 2x 4 = 3

2x 1 −x 2 −x 3 + 4x 4 = 1

Układ ma 4 zmienne i 2 ograniczenia. Wybieramy zmienne bazowe

ZB ={x 1 , x 2 } . Podstawiamy x 3 = x 4 = 0 ( N B ={x 3 , x 4 } ).

Otrzymujemy układ:

x 1 + x 2 = 3

2x 1 −x 2 = 1

Rozwiazujac układ otrzymujemy rozwiazanie bazowe: x 1 = 3 ,

x 2 = 1 3 , x 3 = 0 , x 4 = 0 . Bazą są wektory współczynników macierzy

A układu równań przy zmiennych bazowych x 1 , x 2 tj.

B =

2−1.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: