programowanie liniowe - metoda simpleks, BADOP


IDEA METODY SIMPLEKS DLA ROZWIĄZYWANIA ZADAŃ

PROGRAMOWANIA LINIOWEGO

METODA SIMPLEKS

UWAGI WSTĘPNE

WIELOŚCIAN WYPUKŁY

0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic

0x08 graphic
0x08 graphic

0x08 graphic

0x08 graphic
0x08 graphic
a

b

0x08 graphic
0x08 graphic

WIELOŚCIENNY ZBIÓR WYPUKŁY (zbiór wypukły otwarty)

0x08 graphic

0x08 graphic

0x08 graphic

0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic

0x08 graphic
0x08 graphic
0x08 graphic

0x08 graphic

PUNKTY EKSTREMALNE - BAZA, ROZWIĄZANIA BAZOWE

Niech zadanie PL będzie w postaci bazowej:

cTx*maks,

Ax =b,

x * 0,

gdzie:

A - macierz współczynników o wymiarach m x n,

x - n-wymiarowy wektor zmiennych decyzyjnych,

b - n-wymiarowy wektor prawych stron,

c - n-wymiarowy wektor współczynników funkcji celu.

Niech B oznacza macierz kwadratową m-tego stopnia, składającą się z m liniowo niezależnych kolumn macierzy A. Wyznacznik tej macierzy jest, rzecz jasna różny od zera (detB # 0). Dla macierzy B istnieje zatem macierz odwrotna B-1 = C.

0x01 graphic

gdzie, I jest macierzą identycznościową (1 na głównej przekątnej i 0 poza nią).

0x01 graphic
,

gdzie, D = [Aij]T, przy czym Aij jest kofaktorem elementu aij.

Macierz B nazywa się bazą, jej kolumny - kolumnami bazowymi, a pozostałe kolumny macierzy A - kolumnami niebazowymi. Zmienne związane z kolumnami macierzy B nazywamy - zmiennymi bazowymi (oznaczenie xB), a pozostałe zmienne - zmiennymi niebazowymi (oznaczenie xA). Z każdą baza B układu Ax =b, jest związane rozwiazanie bazowe. Jeśli układ Ax =b, jest niesprzeczny i n > m, to układ ten ma nieskończenie wiele rozwiązań, ale skończoną liczbę rozwiązań bazowych. Układ m równań z n niewiadomymi ma co najwyżej 0x01 graphic
rozwiązań bazowych.

OZNACZENIA

A = (B, N), x = (xB, xN), c = (cB, cN).

Układ Ax =b można zapisać: BxB +NxN = b. Pomnóżmy ostatnią równość lewostronnie przez B-1, otrzymamy:

B-1BxB +B-1NxN = B-1b

lub, podstawiając: I = B-1B, W = B-1N i b* = B-1b,

IxB +WxN = b*.

Jeżeli przyjmiemy xN = 0, to mamy początkowe bazowe rozwiązanie układu równań:

xB = b*.

Jeżeli, xB = b* = B-1b > 0, to rozwiązanie bazowe jest rozwiązaniem dopuszczalnym zadania PL.

IDEA METODY SIMPLEKS

WAŻNE

PRZYKŁAD

0x01 graphic

POSTAĆ BAZOWA:

Otrzymujemy ją dodając do lewej strony każdego ograniczenia zmienną bilansującą.

0x01 graphic

W obliczeniach posługujemy się tablicą simpleksową

Tablica początkowa:

cTxmaks

x1

x2

x3

x4

x5

b

BAZA

cB

2

3

0

0

0

x3

0

2

2

1

0

0

14

x4

0

1

2

0

1

0

8

x5

0

4

0

0

0

1

16

cj - zj

2

3

0

0

0

Zmienne x3, x4, x5 - zmienne bilansujące - muszą spełniać warunek nieujemności Ich współczynniki w funkcji celu mają wartość zero: c3 = c4 = c5 = 0.

Pierwsze rozwiązanie bazowe otrzymujemy natychmiast:

x1 = 0, x2 = 0, x3 = 14, x4 = 8, x5 = 16.

Bazę tworzą zmienne x3, x4, x5. Zmienne x1, x2 są zmiennymi niebazowymi.

Różnicę cj - zj nazywamy wskaźnikiem optymalności. Wiersz z tymi współczynnikami nazywany jest także wierszem zerowym i objaśniamy go następująco:

cj - jest to współczynnik funkcji celu dla zmiennej o indeksie j,

zj - jest liczbą pokazującą o ile zmniejszy się wartość funkcji celu jeżeli wprowadzimy do bazy zmienną xj = 1.

cj - zj = cBaj, gdzie aj jest j-tą kolumną macierzy A w aktualnej tablicy simpleksowej

Weźmy zmienną x1 z naszego przykładu.

Jeżeli x1 = 1, to nowe wartości dla zmiennych x3, x4 , x5 wynoszą: x3 = 14 -2 = 12, x4 = 8 - 1 = 7, x5 = 16 - 4 =12.

Ponieważ współczynniki funkcji celu dla tych zmiennych maja wartość zero, to zj = 0 dla wszystkich indeksów j i cj - zj = cj.

KRYTERIUM OPTYMALNOŚCI

Jeżeli wartości wszystkich wskaźników optymalności są ujemne lub równe zero, to rozpatrywane rozwiązanie bazowe jest rozwiązaniem optymalnym. Wartość funkcji celu można zwiększyć kiedy choć jeden współczynnik optymalności ma wartość dodatnią.

KRYTERIUM WEJŚCIA

Do bazy wprowadzamy tę zmienną niebazową, dla której wartość współczynnika optymalności jest największa.

KRYTERIUM WYJŚCIA

Obliczamy ilorazy kolejnych wyrazów wolnych przez odpowiadające im elementy kolumny wchodzącej do bazy (bi / aij ), dla aij > 0. Bazę opuszcza ta zmienna, dla której odpowiadający jej iloraz jest najmniejszy.

Przejście od starej bazy do nowej jest nazywane iteracją i jest ono dokonywane na drodze normalnych przekształceń algebraicznych polegających na zamianie zmiennych w układzie równań liniowych.

Tablica po 1-szej iteracji (zmieniamy bazę początkową na bazę sąsiednią):

cTxmaks

x1

x2

x3

x4

x5

b

BAZA

cB

2

3

0

0

0

x3

0

2

0

1

-1

0

6

x2

3

1/2

1

0

1/2

0

4

x5

0

4

0

0

0

1

16

cj - zj

1/2

0

0

-3/2

0

Dodatnia wartość c1 - z1 wskazuje, że zwiększenie wartości funkcji celu jest możliwe - stąd nazwa wskaźnik optymalności dla cj - zj.

Dalsze iteracje są niezbędne.

Ogólna postać tablicy simpleksowej w zapisie macierzowym, dla dowolnej iteracji.

BAZA

c

b

xB

cB

B-1A B-1

0x01 graphic

cj - zj

0x01 graphic
0x01 graphic

0x01 graphic

B-1 jest odwrotnością macierzy współczynników ograniczeń, które stoją przy aktualnych, dla danej iteracji, zmiennych bazowych. W początkowej macierzy simpleksowej tą macierzą jest macierz jednostkowa I.

ZMIENNE SZTUCZNE

Zmodyfikujmy nasz przykład następująco:

0x01 graphic

Ponieważ w nowym zadaniu pojawiła się nierówność x1 + x2 * 3, to od jej lewej strony odejmujemy nieujemną zmienną x6 i dla utrzymania początkowego rozwiązania bazowego, dodajemy nieujemną zmienną x7. Zmienną x7 nazywa się zmienną sztuczną i wprowadzamy ją do funkcji celu (maksymalizowanej) ze współczynnikiem liczbowym -M, przy czym M jest b. dużą liczbą dodatnią (np. M = ).

Mamy zatem postać bazową nowego zadania:

0x01 graphic

Tablica wyjściowa nowego zadania (M = 100):

cTxmaks

x1

x2

x3

x4

x5

x6

x7

b

BAZA

cB

2

3

0

0

0

0

100

x3

0

2

2

1

0

0

0

0

14

x4

0

1

2

0

1

0

0

0

8

x5

0

4

0

0

0

1

0

0

16

x7

-100

1

1

0

0

0

-1

1

3

cj - zj

102

103

0

0

0

-100

0

Dalsze postępowanie jest standardowe.

SPRZECZNOŚĆ

Jeżeli zbiór rozwiązań dopuszczalnych zadania PL jest zbiorem pustym, to o zadaniu mówimy, że jest zadaniem sprzecznym. W tablicy simpleksowej sprzeczność zadania uwidacznia się tym, że gdy wszystkie współczynniki optymalności są niedodatnie (co wskazuje, że znaleziono maksimum funkcji), to współczynnik w macierzy ograniczeń przy zmiennej sztucznej pozostaje dodatni, co wskazuje na niemożliwość znalezienia rozwiązania dopuszczalnego (zmienna sztuczna musi mieć wartość 0).

Wróćmy do początkowego przykładu:

0x01 graphic

i zmodyfikujmy go następująco:

0x01 graphic

Łatwo sprawdzić metodą geometryczną lub algebraiczną (tradycyjną), że zadanie jest sprzeczne.

Końcowa tablica simpleksowa (proszę sprawdzić) przyjmie postać:

cTxmaks

x1

x2

x3

x4

x5

x6

x7

b

BAZA

cB

2

3

0

0

0

0

100

x3

0

0

0

1

-1

-1/4

0

0

2

x2

3

0

1

0

1/2

-1/8

0

0

2

x1

2

1

0

0

0

1/4

0

0

4

x7

-100

0

0

0

-1/8

0

-1

1

2

cj - zj

0

0

0

-51/2

-60/8

-100

0

NIEOGRANICZONOŚĆ

Rozważmy zadanie:

0x01 graphic

Bez trudu sprawdzimy sprzeczność tego zadania.

Zmienne bilansujące i zmienna sztuczna (dla 2-go ograniczenia) zmieniają zadanie do postaci bazowej:

0x01 graphic

Początkowa tablica simpleksowa:

cTxmaks

x1

x2

x3

x4

x5

b

BAZA

cB

2

3

0

0

-100

x3

0

4

0

1

0

0

16

x5

-100

1

1

0

-1

1

3

cj - zj

102

103

0

-100

0

Po jednej iteracji mamy:

cTxmaks

x1

x2

x3

x4

x5

b

BAZA

cB

2

3

0

0

-100

x3

0

4

0

1

0

0

16

x2

3

1

1

0

-1

1

3

cj - zj

-1

0

0

3

-103

Kandydatem do bazy jest x4, ale współczynniki przy zmiennych x3 i x2 są niedodatnie, zatem można dowolnie zwiększać wartość funkcji celu przez zwiększanie wartości x2 bez naruszenia ograniczeń.

10



Wyszukiwarka

Podobne podstrony:
Opracowanie Programowanie liniowe metoda sympleks
Rozwiązywanie zadań programowania liniowego metoda geometryczna, Zadania
Opracowanie Programowanie liniowe metoda sympleks
programowanie liniowe 1, BADOP
BO WYK2 Program liniowe optymalizacja
Metody układania algorytmów rekurencja, metoda dziel i zwyciężaj, programowanie dynamiczne, metoda
,Laboratorium podstaw fizyki, WYZNACZANIE WSPÓŁCZYNNIKA ROZSZERZALNOŚCI LINIOWEJ METODĄ
metoda SIMPLEX
programowanie liniowe teoria
badania operacyjne, w5 Metoda Simpleks
Dwufazowa prymarna metoda simplex
PL (programowanie liniowe), semestr 8, Matematyka, Teoria i praktyka decyzji ekonomicznych
konspekt cw 3 1 programowanie liniowe
Wyznaczanie współczynnika rozszerzalności liniowej metodą elektryczną 1 (2)
algorytm transportowy, metoda simplex XJJRAUUERJVV5AUF7SO4M6PNICAPSRDHZNPH7FQ
programowanie liniowe zadanie 1 wmzghak5ktjjzelzmpatqlx6iahqoqrauoxjgtq WMZGHAK5KTJJZELZMPATQLX6IA
WOLFEstud, Programowanie Kwadratowe - metoda Wolfe'a
badania operacyjne, w3 Zagadnienia Dualne Programowania Liniowego

więcej podobnych podstron