2013-10-25
Badania operacyjne
Badania operacyjne
Wykład 2:
Wykład 2:
Zadania dualne PL i jego własności
Zadania dualne PL i jego własności
Algorytm simpleks
Algorytm simpleks
[e-mail]
Zadania dualne PL
Zadania dualne PL
i jego własności
i jego własności
ID,2013/2014
1
2013-10-25
Ogólna postać ZPL
Ogólna postać ZPL
n
n
xj MIN
c x MAX
"cj
" j j
j=1
j =1
n n
xj d" bi xj e" bi
(i = 1,2,..., m) (i = 1,2,..., m)
"aij "aij
j=1 j=1
x e" 0
j ( j = 1,2,..., n) ( j = 1,2,..., n)
x e" 0
j
bi e" 0
bi e" 0
Nierówność d" dla zadania na maksimum oraz nierówność e" dla zadania
na minimum nazywamy nierównościami typowymi
nierównościami typowymi.
ID,2013/2014
Zasady konstrukcji zadań dualnych (1)
Zasady konstrukcji zadań dualnych (1)
Zadanie pierwotne (ZP) Zadanie dualne (ZD)
m
n
bi y MIN
c x MAX " i
" j j
i =1
j =1
m
n
( j =1,2,...,n)
yi e" c
xj d" bi (i = 1,2,..., m)
"aij j
"aij
i=1
j=1
( j = 1,2 ,..., n )
(i = 1,2,..., m)
y e" 0
x e" 0
i
j
ID,2013/2014
2
2013-10-25
Zasady konstrukcji zadań dualnych (2)
Zasady konstrukcji zadań dualnych (2)
Zadanie pierwotne (ZP) Zadanie dualne (ZD)
n m
xj MIN bi yi MAX
"
"cj
i =1
j=1
n
m
xj e" bi
(i = 1,2,..., m) ( j = 1,2,..., n)
yi d" cj
"aij
"aij
j=1
i=1
(i = 1,2,..., m)
y e" 0
x e" 0 ( j = 1,2,..., n) i
j
ID,2013/2014
Zasady konstrukcji zadań dualnych (3)
Zasady konstrukcji zadań dualnych (3)
1. W ZD jest tyle zmiennych, ile nierówności w ZP
(każdemu warunkowi ZP odpowiada jedna
zmienna ZD) i odwrotnie;
2. Współczynniki funkcji celu ZP są wyrazami
wolnymi w ZD i odwrotnie;
3. Macierz współczynników ZD jest transpozycją
macierzy współczynników ZP,
4. Kierunek optymalizacji w ZD jest przeciwny do
kierunku optymalizacji w ZP.
ID,2013/2014
3
2013-10-25
Zasady konstrukcji zadań dualnych (4)
Zasady konstrukcji zadań dualnych (4)
Funkcja celu dąży do
 warunki znakowe
 warunki znakowe Warunek
MAX MIN
Typowy d" e"
Nietypowy e" d"
Jeżeli w problemie pierwotnym występują ograniczenia
typowe (nietypowe) dla kierunku optymalizacji, to w
problemie dualnym na zmienne odpowiadajÄ…ce tym
warunkom nakłada się warunki nieujemności
(niedodatniości) i odwrotnie.
Jeżeli na zmienne w zadaniu pierwotnym nie są
nałożone ograniczenia znakowe, to wtedy
odpowiadające im warunki przyjmują postać równości i
odwrotnie.
ID,2013/2014
Zasady konstrukcji zadań dualnych (5)
Zasady konstrukcji zadań dualnych (5)
 warunki znakowe
 warunki znakowe
Zadanie pierwotne
Zadanie pierwotne
Zadanie dualne
Zadanie dualne
MAX
MAX
MIN
MIN
Ograniczenia
Zmienne
i-te: e"
yi d" 0
i-te: d"
yi e" 0
i-te: =
yi dowolne
Zmienne
Ograniczenia
xj e" 0
j-te: e"
xj d"0
j-te: d"
xj dowolne
j-te: =
ID,2013/2014
4
2013-10-25
Zasady konstrukcji zadań dualnych (6)
Zasady konstrukcji zadań dualnych (6)
 warunki znakowe
 warunki znakowe
Zadanie pierwotne
Zadanie pierwotne
Zadanie dualne
Zadanie dualne
MIN
MIN
MAX
MAX
Ograniczenia
Zmienne
i-te: e"
yi e" 0
i-te: d"
yi d" 0
i-te: =
yi dowolne
Zmienne
Ograniczenia
xj e" 0
j-te: d"
xj d"0
j-te: e"
xj dowolne
j-te: =
ID,2013/2014
Przykład 1: Utwórz ZD do danego ZP
Przykład 1: Utwórz ZD do danego ZP
Zadanie pierwotne (ZP) Zadanie dualne (ZD)
F(x1,x2,x3) = 2x1+3x2+x3MIN G(y1,y2) 4y1+7
F(x1,x2,x3) G(y1,y2) = 4 7y2MAX
y1 x1
(1) 4x1-6x2+5x3e"4 (1) 4y1+1y2d"2
(1) 4 (1)
y2 x2
(2) x1+2x2+4x3e"7 (2) -6y1+2y2 d"3
(2) 7 (2)
x3
(3) x1e"0 (3) 5y1+4y2 d"1
(3) (3)
(4) x2e"0 (4) y1e"0
(4) (4)
(5) x3e"0 (5) y2e"0
(5) (5)
ID,2013/2014
5
2013-10-25
Przykład 2: Utwórz ZD do danego ZP
Przykład 2: Utwórz ZD do danego ZP
Zadanie pierwotne (ZP) Zadanie dualne (ZD)
F(x1,x2,x3,x4) = G(y1,y2) = 160y1+40y2MIN
F(x1,x2,x3,x4) G(y1,y2)
16x1+32x2+12x3+8x4MAX
x1
(1) 4 16
(1) 4y1+2y2e"16
(1) 4x1+6x2+3x3d"160
(1) 160
y1
x2
(2) 6 32
(2) 6y1+8y2e"32
(2) 2x1+8x2+8x3+2x4=40 y2
(2) 40
x3
(3) 3y1+8y2e"12
(3) 3
(3) x1e"0
(3)
(4)
(4) 2y2d"8
(4) x2e"0
(4) x4
(5) y1e"0
(5)
(5) x3e"0
(5)
(6) y2õR
(6) x4d"0
ID,2013/2014
Twierdzenia o dualności (1)
Twierdzenia o dualności (1)
1. W rozwiązaniach optymalnych obu zadań wartości funkcji
celu są sobie równe.
2. a) Jeżeli i-ty warunek ZP jest (chociaż w jednym)
optymalnym rozwiązaniu tego zadania spełniony
nierównością (ostro), to odpowiadająca mu i-ta zmienna 
yi w (dowolnym) optymalnym rozwiÄ…zaniu ZD przyjmuje
wartość zero;
b) Jeżeli j-ty warunek ZD jest (chociaż w jednym)
optymalnym rozwiązaniu tego zadania spełniony
nierównością (ostro), to odpowiadająca mu j-ta zmienna 
xj w (dowolnym) optymalnym rozwiÄ…zaniu ZP przyjmuje
wartość zero;
Jest to tzw. twierdzenie o równowadze.
twierdzenie o równowadze.
ID,2013/2014
6
2013-10-25
Twierdzenia o dualności (2)
Twierdzenia o dualności (2)
3. Jeżeli ZD ma jedno rozwiązanie optymalne, to
optymalna wartość i-tej zmiennej dualnej (yi) informuje
jak wielki przyrost (spadek) wartości funkcji celu ZP
przypada na zwiększenie (zmniejszenie) wyrazu
wolnego w i-tym ograniczeniu (bi) o jednostkÄ™, przy
niezmienionych pozostałych b.
Jest to tzw. twierdzenie o optymalności.
twierdzenie o optymalności.
ID,2013/2014
Interpretacja ekonomiczna ZD (1)
Interpretacja ekonomiczna ZD (1)
ZP opisuje problem maksymalizacji przychodu
osiąganego z produkcji n wyrobów. Zużycie środków
produkcji nie może przekroczyć zasobów, jakimi
dysponujemy. Waga ci oznacza cenÄ™ j-tego wyrobu,
współczynnik aij  wielkość zużycia i-tego środka na
produkcjÄ™ jednostki j-tego wyrobu, wyraz wolny bi 
zasób i-tego środka produkcji, a zmienna xj  wielkość
produkcji j-tego wyrobu.
n
c x MAX
" j j
j =1
(i = 1,2,..., m)
n
xj d" bi
"aij
j=1
( j = 1,2,..., n )
x e" 0
j
ID,2013/2014
7
2013-10-25
Interpretacja ekonomiczna ZD (2)
Interpretacja ekonomiczna ZD (2)
ZD do ZP ma postać:
m
bi yi MIN (1)
"
i =1
przy warunkach:
m
(2)
( j =1,2,...,n)
yi e" c
"aij j
i=1
(i = 1,2,..., m)
(3)
y e" 0
i
W celu określenia interpretacji ekonomicznej ZD (1)-(3) określić należy
miano zmiennych dualnych. Miano można określić z nierówności (2),
miano zmiennych dualnych
wiedząc, że cj wyrażają zysk jednostkowy ze sprzedaży j-tego wyrobu.
Wobec tego występują one z mianem:
jednostki pieniężne
ilość wytworzonego wyrobu
ID,2013/2014
Interpretacja ekonomiczna ZD (3)
Interpretacja ekonomiczna ZD (3)
Parametry aij w ZD wyrażają zużycie i-tego środka na produkcję
jednostki j-tego wyrobu, mianem będzie:
zużycie i-tego środka
ilość wytworzonego wyrobu
Aby nierówności (2) miały sens ekonomiczny, to zmienne dualne muszą
mieć mano:
jednostki pieniężne
zużycie i-tego środka
Z miana zmiennej dualnej yi wynika, że wyraża ona w jednostkach
pieniężnych produktywność z zaangażowania jednostki środka i.
Warunki ograniczające (2) oznaczają, że suma tych produktywności
wyrażona jednostkowymi nakładami surowców na jeden wyrób j musi
być równa co najmniej zyskowi jednostkowemu ze sprzedaży j-tego
wyrobu.
Funkcja celu ZD wyraża łączny efekt z wykorzystania wszystkich
środków. Jest ona minimalizowana, ponieważ szukamy minimalnej
sumarycznej produktywności wszystkich użytych środków.
ID,2013/2014
8
2013-10-25
Przykład 3  wybór optymalnego
Przykład 3  wybór optymalnego
planu produkcji
planu produkcji
Zakład produkujący ustala plan produkcyjny, który może
obejmować produkcję mebli: szaf, regałów, stołów kuchennych.
Można je sprzedać odpowiednio za 500, 180, 90 PLN. Do
produkcji mebli zużywane są ograniczone zasoby drewna i listew:
Ustalić plan produkcji na przyszły rok tak, aby zmaksymalizować
zysk ze sprzedaży mebli.
Zbudować model matematyczny tego zagadnienia i zastosować
metodÄ™ geometrycznÄ….
ID,2013/2014
Przykład 3  rozwiązanie
Przykład 3  rozwiązanie
Model matematyczny
ZP ZD
Zmienne decyzyjne: Zmienne decyzyjne:
x1  wielkość produkcji szaf y1  cena drewna
x2  wielkość produkcji regałów y2  cena listew
x3  wielkość produkcji stołów
Warunki ograniczajÄ…ce: Warunki ograniczajÄ…ce:
[drewno] 4x1+2,5x2+1,5x3 d" 1000 4y1+8y2e"500
[listwy] 8x1+12x2+3x3 d" 2500 2,5y1+12y2e"180
1,5y1+3y2e"90
Warunki brzegowe:
x1,x2,x3e"0
Warunki brzegowe:
y1,y2 e"0
Funkcja celu:
Funkcja celu:
F(x1,x2,x3) = 500x1+180x2+90x3MAX
G(y1,y2) = 1000y1+2500y2MIN
ID,2013/2014
9
2013-10-25
Przykład 3  rozwiązanie (2)
Przykład 3  rozwiązanie (2)
Biorąc dowolną wspólną wielokrotność
parametrów funkcji celu, tj. 1000 i 2500 np. 50000
wyznaczamy liniÄ™ jednakowego przychodu.
y2
G(y1,y2) = 1000y1+2500y2MIN
80
(1) 4y1 + 8y2 e" 500
A
A
(2) 2,5y1 + 12y2 e" 180
60
(3) 1,5y1 + 3y2 e" 90
40
20
B
B
0
20 40 60 100 y1
ID,2013/2014 80 120
Przykład 3  rozwiązanie (3)
Przykład 3  rozwiązanie (3)
y2
Następnie linię tę przesuwamy równolegle w celu
znalezienia punktu(ów) znajdujących się jak najbliżej od
80
początku układu współrzędnych
(1) 4y1 + 8y2 e" 500
A
A
(2) 2,5y1 + 12y2 e" 180
60
(3) 1,5y1 + 3y2 e" 90
G(y1,y2) = 1000y1+2500y2MIN
40
20
B
B
0
20 40 60 100 y1
ID,2013/2014 80 120
10
2013-10-25
Przykład 3  rozwiązanie (4)
Przykład 3  rozwiązanie (4)
y2
80
G(y1,y2) = 1000y1+2500y2MIN
A
A
G(y1,y2) = 125 000 zł
60
40
RozwiÄ…zanie optymalne
20
ZD
B=(125,0)
B=(125,0)
0
20 40 60 100 y1
ID,2013/2014 80 120
Przykład 3  rozwiązanie (5)
Przykład 3  rozwiązanie (5)
Sprawdzamy, w jaki sposób optymalne rozwiązanie ZD
spełnia jego warunki ograniczające
B=(125,0)
B=(125,0)
(1) 4y1 + 8y2 e" 500 (2) 2,5y1 + 12y2 e" 180 (3) 1,5y1 + 3y2 e" 90
500=500 312,5e"180 187,5e"90
Warunek (1) jest słabo spełniony (zachodzi równość)
Warunek (2) i (3) jest ostro spełniony (zachodzi nierówność)
& stąd wniosek, że zmienna w ZP o nr 2 i 3 (czyli x2 i x3) jest
równa 0
Tak więc, dla rozwiązana ZP można zapisać układ równań:
4x1 = 1000
8x1 = 2500
F(x1,x2,x3) = 500x1+180x2+90x3= 125000 zł
x1 = 250
ID,2013/2014
11
2013-10-25
Przykład 3  rozwiązanie (6)
Przykład 3  rozwiązanie (6)
Z twierdzenia 1 wynika, że:
G(y1,y2) = 125 000 zł = F(x1,x2,x3) = 500x1+180x2+90x3= 125000 zł
Z twierdzenia 3 wynika, że optymalna wartość zmiennej yi
określa nam, o ile wzrośnie (zmniejszy się) przychód, jeżeli
zwiększymy (zmniejszymy) zasób i-tego środka produkcji o
jednostkÄ™.
Sprawdz
my:
4x1 = 1001 F(x1,x2,x3) = 500x1+180x2+90x3= 125125 zł
8x1 = 2500
x1 = 250,25
RozwiÄ…zanie optymalne: ZD (y1=125, y2=0)
ID,2013/2014
Metoda simpleks
(uniwersalna metoda rozwiÄ…zywania ZPL)
ID,2013/2014
12
2013-10-25
Kiedy stosować metodę simpleks?
Kiedy stosować metodę simpleks?
Liczba zmiennych decyzyjnych jest większa niż 2
Duża liczba ograniczeń utrudnia dokładne
wyznaczenie zbioru rozwiązań dopuszczalnych
metodÄ… graficznÄ…
Metoda simpleks - metoda iteracyjnego
poprawiania wstępnego rozwiązania
ID,2013/2014
Wyznaczenie startowego rozwiÄ…zania
Czy to jest
T
Koniec
rozwiÄ…zanie
optymalne?
N
Czy można
N
wyznaczyć
lepsze
rozwiÄ…zanie?
T
Wyznaczenie nowego
rozwiÄ…zania
Schemat postępowania w przypadku wyznaczania rozwiązań za
Schemat postępowania w przypadku wyznaczania rozwiązań za
pomocą metod iteracyjnych o skończonej liczbie kroków
pomocą metod iteracyjnych o skończonej liczbie kroków
ID,2013/2014
13
2013-10-25
Istota algorytmu simpleks
Istota algorytmu simpleks
Polega na badaniu kolejnych rozwiązań bazowych
(rozwiązań dopuszczalnych) programu liniowego w
postaci kanonicznej w taki sposób, że :
znajdujemy (dowolne) rozwiÄ…zanie bazowe zadania;
sprawdzamy, czy jest ono optymalne czy nie.
jeżeli dane rozwiązanie nie jest optymalne,
znajdujemy następne rozwiązanie bazowe lepsze
(lub przynajmniej nie gorsze od poprzedniego), z
którym to rozwiązaniem postępujemy tak samo jak z
rozwiązaniem wyjściowym - aż do momentu
znalezienia rozwiÄ…zania optymalnego.
ID,2013/2014
Sprowadzenie ZPL do postaci kanonicznej
Sprowadzenie ZPL do postaci kanonicznej
Przekształcamy warunki ograniczające w równania dopisując do
nich tzw. zmienne swobodne i zmienne sztuczne
w następujący sposób:
do każdego warunku w postaci  d" dodaje się zmienną
swobodną z parametrem równym 1,
do każdego warunku w postaci  e" dodaje się zmienną
swobodną ze współczynnikiem -1 oraz tzw. zmienną
sztuczną z parametrem równym 1.
Zmienne swobodne posiadajÄ… interpretacjÄ™ ekonomicznÄ…
wynikajÄ…cÄ… z informacji zawartej w warunkach ograniczajÄ…cych,
do których zostały wprowadzone.
Dodane zmienne wchodzą również do nowej funkcji kryterium
(celu), gdzie parametry przy zmiennych swobodnych przyjmujÄ…
wartość zero, natomiast zmienne sztuczne wartość M (duża
liczba dążąca do nieskończoności).
ID,2013/2014
14
2013-10-25
Ile należy wykonać iteracji, aby
osiągnąć rozwiązanie optymalne?
Dokładnej liczby iteracji, które należy wykonać
rozwiązując model nie da się precyzyjnie określić.
Dla układu n zmiennych decyzyjnych i m
warunków ograniczających jest co najwyżej
n
ëÅ‚ öÅ‚ n!
ìÅ‚
ìÅ‚m÷Å‚ = m!(n - m)!
÷Å‚
íÅ‚ Å‚Å‚
rozwiązań dopuszczalnych.
Metoda simpleks nie przeszukuje wszystkich
rozwiązań bazowych, lecz tylko wybrane.
ID,2013/2014
Tablica simpleksowa  postać macierzowa
Tablica simpleksowa  postać macierzowa
Wektor wierszowy
zmiennych Macierz jednostkowa
Wektor wierszowy
współczynników funkcji celu
Macierz współczynników
występujących po lewej stronie
warunków ograniczających Wektor kolumnowy
cj
wyrazów wolnych
xj
Wektor kolumnowy
xb cb bi
współczynników funkcji
celu dla zmiennych A I
bazowych
k
zj
z = cbi
j "aij
"j=cj-zj
i=1
Wektor kolumnowy
zmiennych bazowych Suma iloczynów współczynników
odpowiadających poszczególnym
zmiennym (aij) i współczynników
Wiersz zerowy funkcji celu dla zmiennych
(kryterium simpleks) bazowych (cb)
ID,2013/2014
15
2013-10-25
Wiersz zerowy
Wiersz zerowy
Jeżeli funkcja celu jest MAX
funkcja celu jest MAX, rozwiÄ…zanie bazowe
dotąd nie będzie optymalne, dopóki w wierszu
zerowym będą występować liczby nieujemne
liczby nieujemne
(dodatnie liczby świadczą, iż wprowadzenie do bazy
zmiennej, której odpowiada dodatni współczynnik
zwiększy wartość funkcji celu);
Jeżeli funkcja celu jest MIN
funkcja celu jest MIN, kolejne rozwiÄ…zania
bazowe dotąd nie są optymalne, dopóki w wierszu
zerowym występują wielkości niedodatnie (co
wielkości niedodatnie
znaczy, że wartość funkcji celu można obniżyć).
ID,2013/2014
Schemat postępowania
Schemat postępowania
w algorytmie simpleks
w algorytmie simpleks
yik  wektor
odpowiadajÄ…cy
zmiennej , która ma
wejść do nowej bazy
16
2013-10-25
Przykład 4
Przykład 4
Zakład produkuje trzy wyroby przy użyciu dwóch
surowców. Zasoby surowców, jednostkowe nakłady i
ceny produktów podane są w tabeli:
Wyrób A Wyrób B Wyrób C Zasób
Surowiec 1 2 1 1 10
Surowiec 2 1 3 2 12
Cena 3 2 5
Wyznacz metodÄ… simpleks plan produkcji
maksymalizujący przychód przedsiębiorstwa.
Wyznacz i zinterpretuj wartości zmiennych dualnych.
ID,2013/2014
Przykład 4  rozwiązanie
Przykład 4  rozwiązanie
Krok 1 - Zapisanie modelu liniowego problemu w postaci standardowej
Krok 1 - Zapisanie modelu liniowego problemu w postaci standardowej
Zmienne decyzyjne:
x1  wielkość produkcji wyrobu A
x2  wielkość produkcji wyrobu B
x3  wielkość produkcji wyrobu C
Warunki ograniczajÄ…ce:
[s1] 2x1+1x2+1x3d"10
[s2] 1x1+3x2+2x3d"12
Warunki brzegowe:
x1,x2, x3e"0
Funkcja celu:
F(x1,x2) = 3x1+2x2+5x3MAX
ID,2013/2014
17
2013-10-25
Przykład 4  rozwiązanie (2)
Przykład 4  rozwiązanie (2)
Krok 2 - Sprowadzenie zadania z postaci standardowej do kanonicznej
Krok 2 - Sprowadzenie zadania z postaci standardowej do kanonicznej
Postać standardowa Postać kanoniczna
Zmienne decyzyjne:
Zmienne decyzyjne:
x1  wielkość produkcji wyrobu A
x1  wielkość produkcji wyrobu A,
x2  wielkość produkcji wyrobu B
x2  wielkość produkcji wyrobu B,
x3  wielkość produkcji wyrobu C
x3  wielkość produkcji wyrobu C,
x4  niewykorzystany zasób surowca 1
Warunki ograniczajÄ…ce:
x5  niewykorzystany zasób surowca 2
[s1] 2x1+1x2+1x3d"10
Warunki ograniczajÄ…ce:
[s2] 1x1+3x2+2x3d"12
[s1] 2x1+1x2+1x3+x4=10
[s2] 1x1+3x2+2x3 +x5=12
Warunki brzegowe:
Warunki brzegowe:
x1,x2, x3e"0
x1,x2, x3, x4, x5e"0
Funkcja celu:
Funkcja celu:
F(x1,x2, x3,x4,x5) = 3x1+2x2+5x3+0x4+0x5MAX
F(x1,x2, x3) = 3x1+2x2+5x3MAX
ID,2013/2014
Przykład 4  rozwiązanie (3)
Przykład 4  rozwiązanie (3)
Krok 3  Wstępne dopuszczane rozwiązanie modelu
Krok 3  Wstępne dopuszczane rozwiązanie modelu
Rozpoczynamy od przyjęcia, że te zmienne, które występują w
więcej niż jednym ograniczeniu, są równe zero, tj.
x1,x2,x3=0
W efekcie tego założenia wszystkie zmienne dodatkowe mają
wartości takie jak wyrazy wolne stojące po prawej stronie
odpowiednich ograniczeń. Dla rozważanego modelu otrzymujemy
więc:
x4=10, x5=12
Wstępnie określone rozwiązanie dopuszczalne nazywa się
wstępnym rozwiązaniem bazowym, natomiast zmienne
wchodzące w jego skład (x4, x5) nazywamy zmiennymi
bazowymi lub krótko - bazą. Pozostałe zmienne nazywa się
zmiennymi niebazowymi.
ID,2013/2014
18
2013-10-25
Przykład 4  rozwiązanie (4)
Przykład 4  rozwiązanie (4)
Krok 3  Wstępne dopuszczane rozwiązanie modelu (2)
Krok 3  Wstępne dopuszczane rozwiązanie modelu (2)
F(x1,x2, x3,x4,x5) = 3x1+2x2+5x3+0x4+0x5MAX
Tablica simpleks 1
[s1] 2x1+1x2+1x3+x4 =10
[s2] 1x1+3x2+2x3 +x5=12
xj x1 x2 x3 x4 x5
xb bi ¸i
cb/cj 3 2 5 0 0
x4 0 2 1 1 1 0 10
x5 0 1 3 2 0 1 12
zj 0 0 0 0 0
cj-zj 3 2 5 0 0
Wartości wiersza zj dla wszystkich zmiennych są równe zeru, bo współczynniki przy zmiennych bazowych
są równe zeru, np. x1: z1=2" 0+1" 0=0, dla x2: z2=1" 0+3" 0 itd.
ID,2013/2014
Przykład 4  rozwiązanie (5)
Przykład 4  rozwiązanie (5)
Krok 3  Wstępne dopuszczane rozwiązanie modelu (3)
Krok 3  Wstępne dopuszczane rozwiązanie modelu (3)
Tablica simpleks 1
xj x1 x2 x3 x4 x5
xb bi ¸i
cb/cj 3 2 5 0 0
x4 0 2 1 1 1 0 10
x5 0 1 3 2 0 1 12
zj 0 0 0 0 0
0
cj-zj 3 2 5 0 0
Wartości wiersza zj dla wszystkich zmiennych są równe zeru, bo współczynniki funkcji celu przy
zmiennych bazowych są równe zeru, np. x1: z1=2" 0+1" 0=0, dla x2: z2=1" 0+3" 0 itd. Jak łatwo się przekonać,
zaproponowane wstępne rozwiązanie dopuszczalne daje zysk FC=10" 0+12" 0=0.
ID,2013/2014
19
2013-10-25
Kryterium optymalności
Kryterium optymalności
Rozwiązanie jest optymalne, jeżeli wartości wszystkich
wskaz
ników optymalności są niedodatnie.
RozwiÄ…zanie w bazie [x4, x5] nie jest rozwiÄ…zaniem
optymalnym.
Należy przejść do następnej bazy
ID,2013/2014
Przykład 4  rozwiązanie (6)
Przykład 4  rozwiązanie (6)
Krok 4  Zmiana bazy/ kryterium wejścia do bazy
Krok 4  Zmiana bazy/ kryterium wejścia do bazy
Tablica simpleks 1 Kolumna kluczowa
xj x1 x2 x3 x4 x5
xb bi ¸i
cb/cj 3 2 5 0 0
x4 0 2 1 1 1 0 10
x5 0 1 3 2 0 1 12
zj 0 0 0 0 0
0
cj-zj 3 2 5 0 0
Ponieważ FC jest maksymalizowana, do kolejnego rozwiązania wejdzie zmienna o największej
wartości kryterium simpleks.
Jeżeli największa wartość wskaz
nika optymalności odpowiada więcej niż jednej zmiennej,
wybieramy zmienną o niższym indeksie.
W przykładzie kryterium wejścia spełnia zmienna x3.
ID,2013/2014
20
2013-10-25
Przykład 4  rozwiązanie (7)
Przykład 4  rozwiązanie (7)
Krok 5  Zmiana bazy/ kryterium wyjścia z bazy
Krok 5  Zmiana bazy/ kryterium wyjścia z bazy
Tablica simpleks 1 Kolumna kluczowa
xj x1 x2 x3 x4 x5
xb bi ¸i
cb/cj 3 2 5 0 0
x4: 10:1=10
x4 0 2 1 1 1 0 10 10
x5 0 1 3 2 0 1 12 6 x5: 12:2=6
zj 0 0 0 0 0
0
cj-zj 3 2 5 0 0
Obliczamy ilorazy wyrazów wolnych (kolumna bi) przez elementy (tylko dodatnie) kolumny
zmiennej wchodzÄ…cej do bazy.
Bazę opuszcza ta zmienna, dla której obliczony iloraz jest najmniejszy.
Jeżeli najmniejsza wartość ilorazu występuje dla więcej niż jednej zmiennej, to jako zmienną
opuszczającą bazę można wybrać dowolną z nich.
ID,2013/2014
W przykładzie kryterium wyjścia spełnia zmienna x5.
Przykład 4  rozwiązanie (8)
Przykład 4  rozwiązanie (8)
Kolumna kluczowa
Tablica simpleks 1
xj x1 x2 x3 x4 x5
xb bi ¸i
cb/cj 3 2 5 0 0
Wiersz
kluczowy
x4 0 2 1 1 1 0 10 10
x5 0 1 3 2 0 1 12 6
zj 0 0 0 0 0
0
cj-zj 3 2 5 0 0
ID,2013/2014
21
2013-10-25
Przykład 4  rozwiązanie (9)
Przykład 4  rozwiązanie (9)
Kolumna kluczowa
Tablica simpleks 1
xj x1 x2 x3 x4 x5
xb bi ¸i
cb/cj 3 2 5 0 0
Wiersz
kluczowy
x4 0 2 1 1 1 0 10 10
x5 0 1 3 2 0 1 12 6
zj 0 0 0 0 0
0
Element
cj-zj 3 2 5 0 0
rozwiÄ…zujÄ…cy
(centralny)
ID,2013/2014
Algorytm simpleks
Algorytm simpleks
Metoda zamiany zmiennych
Metoda zamiany zmiennych
Elementy nowej tablicy simpleksowej wyznaczamy
stosując się do następujących zasad:
1. Elementy  wiersza kluczowego wchodzÄ… do nowej
tablicy po podzieleniu przez element rozwiÄ…zujÄ…cy.
2. Pozostałe elementy tablicy simpleks wyznacza się ze
wzoru:
EWK Å" EKK
NE = WE -
gdzie:
ER
NE  nowy element
WE  wybrany element
EWK  element wiersza kluczowego
WKK  element kolumny kluczowej
ER  element rozwiÄ…zujÄ…cy
ID,2013/2014
22
2013-10-25
Przykład 4  rozwiązanie (10)
Przykład 4  rozwiązanie (10)
Tablica simpleks 1
Krok 6 - Zamiana zmiennych
Krok 6 - Zamiana zmiennych
xj x1 x2 x3 x4 x5
xb bi ¸i
cb/cj 3 2 5 0 0
x4 0 2 1 1 1 0 10 10
x5 0 1 3 2 0 1 12 6
zj 0 0 0 0 0
0
cj-zj 3 2 5 0 0
Tablica simpleks 2
xj x1 x2 x3 x4 x5
xb bi ¸i
cb/cj 3 2 5 0 0
x4 0
x3 5
zj
cj-zj
ID,2013/2014
Przykład 4  rozwiązanie (11)
Przykład 4  rozwiązanie (11)
Tablica simpleks 1
Krok 6 - Zamiana zmiennych (2)
Krok 6 - Zamiana zmiennych (2)
xj x1 x2 x3 x4 x5
xb bi ¸i
cb/cj 3 2 5 0 0
x4 0 2 1 1 1 0 10 10
x5 0 1 3 2 0 1 12 6
zj 0 0 0 0 0
0
cj-zj 3 2 5 0 0
Tablica simpleks 2
xj x1 x2 x3 x4 x5
xb bi ¸i
cb/cj 3 2 5 0 0
x4 0
x3 5 1/2 3/2 1 0 1/2 6
zj
cj-zj
ID,2013/2014
23
2013-10-25
Przykład 4  rozwiązanie (12)
Przykład 4  rozwiązanie (12)
Tablica simpleks 1
Krok 6 - Zamiana zmiennych (3)
Krok 6 - Zamiana zmiennych (3)
xj x1 x2 x3 x4 x5
xb bi ¸i
cb/cj 3 2 5 0 0
x4 0 2 1 1 1 0 10 10
x5 0 1 3 2 0 1 12 6
zj 0 0 0 0 0
0
cj-zj 3 2 5 0 0
Tablica simpleks 2
xj x1 x2 x3 x4 x5
xb bi ¸i
cb/cj 3 2 5 0 0
x4 0 3/2 -1/2 0 1 -1/2 4
x3 5 1/2 3/2 1 0 1/2 6
zj
cj-zj
ID,2013/2014
Przykład 4  rozwiązanie (13)
Przykład 4  rozwiązanie (13)
Tablica simpleks 2
xj x1 x2 x3 x4 x5
xb bi ¸i
cb/cj 3 2 5 0 0
x4 0 3/2 -1/2 0 1 -1/2 4
x3 5 1/2 3/2 1 0 1/2 6
zj 5/2 15/2 5 0 5/2
cj-zj
Współczynniki zj oraz wiersza zerowego (cj-zj) obliczamy tak, jak w
przypadku 1-szej tablicy simpleksowej
ID,2013/2014
24
2013-10-25
Przykład 4  rozwiązanie (14)
Przykład 4  rozwiązanie (14)
Tablica simpleks 2
xj x1 x2 x3 x4 x5
xb bi ¸i
cb/cj 3 2 5 0 0
x4 0 3/2 -1/2 0 1 -1/2 4
x3 5 1/2 3/2 1 0 1/2 6
zj 5/2 15/2 5 0 5/2
30
cj-zj
ID,2013/2014
Przykład 4  rozwiązanie (15)
Przykład 4  rozwiązanie (15)
Tablica simpleks 2
xj x1 x2 x3 x4 x5
xb bi ¸i
cb/cj 3 2 5 0 0
x4 0 3/2 -1/2 0 1 -1/2 4
x3 5 1/2 3/2 1 0 1/2 6
zj 5/2 15/2 5 0 5/2
30
cj-zj 1/2 -11/2 0 0 -5/2
RozwiÄ…zanie w bazie [x4, x3,] nie jest rozwiÄ…zaniem optymalnym.
ID,2013/2014
25
2013-10-25
Przykład 4  rozwiązanie (16)
Przykład 4  rozwiązanie (16)
Krok 4*  Zmiana bazy/ kryterium wejścia do bazy
Krok 4*  Zmiana bazy/ kryterium wejścia do bazy
Tablica simpleks 2
xj x1 x2 x3 x4 x5
xb bi ¸i
cb/cj 3 2 5 0 0
x4 0 3/2 -1/2 0 1 -1/2 4
x3 5 1/2 3/2 1 0 1/2 6
zj 5/2 15/2 5 0 5/2
30
cj-zj 1/2 -11/2 0 0 -5/2
Do bazy wchodzi zmienna x1.
ID,2013/2014
Przykład 4  rozwiązanie (17)
Przykład 4  rozwiązanie (17)
Krok 5*  Zmiana bazy/ kryterium wyjścia z bazy
Krok 5*  Zmiana bazy/ kryterium wyjścia z bazy
Tablica simpleks 2
xj x1 x2 x3 x4 x5
xb bi ¸i
cb/cj 3 2 5 0 0
x4 0 3/2 -1/2 0 1 -1/2 4 8/3
x3 5 1/2 3/2 1 0 1/2 6 12
zj 5/2 15/2 5 0 5/2
30
cj-zj 1/2 -11/2 0 0 -5/2
Z bazy wychodzi zmienna: x4
ID,2013/2014
26
2013-10-25
Przykład 4  rozwiązanie (18)
Przykład 4  rozwiązanie (18)
Kolumna kluczowa
Tablica simpleks 2
xj x1 x2 x3 x4 x5
Wiersz
xb bi ¸i
kluczowy
cb/cj 3 2 5 0 0
x4 0 3/2 -1/2 0 1 -1/2 4 8/3
x3 5 1/2 3/2 1 0 1/2 6 12
zj 5/2 15/2 5 0 5/2
30
cj-zj 1/2 -11/2 0 0 -5/2
Element
rozwiÄ…zujÄ…cy
(centralny)
ID,2013/2014
Przykład 4  rozwiązanie (19)
Przykład 4  rozwiązanie (19)
Tablica simpleks 2
Krok 6* - Zamiana zmiennych
Krok 6* - Zamiana zmiennych
xj x1 x2 x3 x4 x5
xb bi ¸i
cb/cj 3 2 5 0 0
x4 0 3/2 -1/2 0 1 -1/2 4 8/3
x3 5 1/2 3/2 1 0 1/2 6 12
zj 5/2 15/2 5 0 5/2
30
cj-zj 1/2 -11/2 0 0 -5/2
Tablica simpleks 3
xj x1 x2 x3 x4 x5
xb bi ¸i
cb/cj 3 2 5 0 0
x1 3
x3 5
zj
cj-zj
ID,2013/2014
27
2013-10-25
Przykład 4  rozwiązanie (20)
Przykład 4  rozwiązanie (20)
Tablica simpleks 2
Krok 6* - Zamiana zmiennych (2)
Krok 6* - Zamiana zmiennych (2)
xj x1 x2 x3 x4 x5
xb bi ¸i
cb/cj 3 2 5 0 0
x4 0 3/2 -1/2 0 1 -1/2 4 8/3
x3 5 1/2 3/2 1 0 1/2 6 12
zj 5/2 15/2 5 0 5/2
30
cj-zj 1/2 -11/2 0 0 -5/2
Tablica simpleks 3
xj x1 x2 x3 x4 x5
xb bi ¸i
cb/cj 3 2 5 0 0
x1 3 1 -1/3 0 2/3 -1/3 8/3
x3 5
zj
cj-zj
ID,2013/2014
Przykład 4  rozwiązanie (21)
Przykład 4  rozwiązanie (21)
Tablica simpleks 2
Krok 6* - Zamiana zmiennych (3)
Krok 6* - Zamiana zmiennych (3)
xj x1 x2 x3 x4 x5
xb bi ¸i
cb/cj 3 2 5 0 0
x4 0 3/2 -1/2 0 1 -1/2 4 8/3
x3 5 1/2 3/2 1 0 1/2 6 12
zj 5/2 15/2 5 0 5/2
30
cj-zj 1/2 -11/2 0 0 -5/2
Tablica simpleks 3
xj x1 x2 x3 x4 x5
xb bi ¸i
cb/cj 3 2 5 0 0
x1 3 1 -1/3 0 2/3 -1/3 8/3
x3 5 0 5/3 1 -1/3 2/3 14/3
zj
cj-zj
ID,2013/2014
28
2013-10-25
Przykład 4  rozwiązanie (22)
Przykład 4  rozwiązanie (22)
Tablica simpleks 3
xj x1 x2 x3 x4 x5
xb bi ¸i
cb/cj 3 2 5 0 0
x1 3 1 -1/3 0 2/3 -1/3 8/3
x3 5 0 5/3 1 -1/3 2/3 14/3
zj 3 22/3 5 1/3 7/3
cj-zj
ID,2013/2014
Przykład 4  rozwiązanie (23)
Przykład 4  rozwiązanie (23)
Tablica simpleks 3
xj x1 x2 x3 x4 x5
xb bi ¸i
cb/cj 3 2 5 0 0
x1 3 1 -1/3 0 2/3 -1/3 8/3
x3 5 0 5/3 1 -1/3 2/3 14/3
zj 3 22/3 5 1/3 7/3
94/3
cj-zj
ID,2013/2014
29
2013-10-25
Przykład 4  rozwiązanie (24)
Przykład 4  rozwiązanie (24)
Tablica simpleks 3
xj x1 x2 x3 x4 x5
xb bi ¸i
cb/cj 3 2 5 0 0
x1 3 1 -1/3 0 2/3 -1/3 8/3
x3 5 0 5/3 1 -1/3 2/3 14/3
zj 3 22/3 5 1/3 7/3
94/3
cj-zj 0 -16/3 0 -1/3 -7/3
RozwiÄ…zanie w bazie [x1, x3,] jest rozwiÄ…zaniem optymalnym.
ID,2013/2014
Przykład 4  rozwiązanie (25)
Przykład 4  rozwiązanie (25)
Tablica simpleks 3
xj x1 x2 x3 x4 x5
xb bi ¸i
cb/cj 3 2 5 0 0
x1 3 1 -1/3 0 2/3 -1/3 8/3
x3 5 0 5/3 1 -1/3 2/3 14/3
zj 3 22/3 5 1/3 7/3
94/3
cj-zj 0 -16/3 0 -1/3 -7/3
Zmienne bazowe: x1=8/3 i x3=14/3
Zmienne niebazowe: x2=0, x4=0, x5=0.
ID,2013/2014
30
2013-10-25
Przykład 4  rozwiązanie (26)
Przykład 4  rozwiązanie (26)
Tablica simpleks 3
xj x1 x2 x3 x4 x5
xb bi ¸i
cb/cj 3 2 5 0 0
x1 3 1 -1/3 0 2/3 -1/3 8/3
x3 5 0 5/3 1 -1/3 2/3 14/3
zj 3 22/3 5 1/3 7/3
94/3
cj-zj 0 -16/3 0 -1/3 -7/3
RozwiÄ…zanie: x1=8/3, x2=0, x3=14/3, x4=0 i x5=0 F(x1, x2, x3,x4,x5) = 94/3
Odp. Przedsiębiorstwo osiągnie maksymalny przychód równy 94/3 jednostek, jeśli
będzie produkowało 8/3 jednostki wyrobu A i 14/3 jednostki wyrobu C. Wyrobu B nie
należy produkować, zaś zasoby obu surowców zostaną w pełni wykorzystane .
ID,2013/2014
Przykład 4  rozwiązanie (27)
Przykład 4  rozwiązanie (27)
Wartości zmiennych dualnych odczytujemy w wierszu zj w
tych kolumnach, które odpowiadały zmiennym bazowym w
pierwszej tablicy,
xj x1 x2 x3 x4 x5
xb bi ¸i
cb/cj 3 2 5 0 0
x1 3 1 -1/3 0 2/3 -1/3 8/3
x3 5 0 5/3 1 -1/3 2/3 14/3
zj 3 22/3 5 1/3 7/3
94/3
cj-zj 0 -16/3 0 -1/3 -7/3
& a więc w kolumnie zmiennej x4 i zmiennej x5. Wynika stąd,
że y1=1/3 oraz y2=7/3
ID,2013/2014
31
2013-10-25
Przykład 5
Przykład 5
Racjonalna hodowla drobiu wymaga dostarczenia miesięcznie
każdej sztuce dwóch składników odżywczych: S1  co najmniej
30 jednostek, S2  co najmniej 50 jednostek, zawartych w
trzech paszach. Dane o zawartości składników i cenie
poszczególnych pasz przedstawia tabela.
Zawartość składnika w 1
Cena
Pasze kg paszy
paszy
S1 S2
P1 2 10 10
P2 7,5 2,5 15
P3 3 4 12
Ile paszy poszczególnego gatunku należy dostarczyć, aby
zapewnić właściwą kombinację składników odżywczych przy
możliwie najniższych kosztach wyżywienia.
ID,2013/2014
Przykład 5  rozwiązanie (1)
Przykład 5  rozwiązanie (1)
Krok 1 i 2 - Zapisanie modelu liniowego problemu w postaci
Krok 1 i 2 - Zapisanie modelu liniowego problemu w postaci
standardowej i kanonicznej
standardowej i kanonicznej
Zmienne decyzyjne: Zmienne decyzyjne:
x1  ilość paszy P1, którą należy zakupić x1  ilość paszy P1, którą należy zakupić
x2  ilość paszy P2, którą należy zakupić x2  ilość paszy P2, którą należy zakupić
x3  ilość paszy P3, którą należy zakupić x3  ilość paszy P3, którą należy zakupić
x4, x5   ilość składnika s1 i s2
Warunki ograniczajÄ…ce:
dostarczona ponad wymagane minimum
u1,u2  zmienne sztuczne
[s1] 2x1+7,5x2+3x3e"30
[s2] 10x1+2,5x2+4x3e"50
Warunki ograniczajÄ…ce:
[s1] 2x1+7,5x2+3x3-x4 +u1 =30
Warunki brzegowe: [s2] 10x1+2,5x2+4x3 -x5 +u2 =50
Warunki brzegowe:
x1,x2, x3e"0
x1,x2, x3,x4,x5,u1,u2e"0
Funkcja celu:
Funkcja celu:
F(x1,x2,x3) = 10x1+15x2+12x3MIN
F(x1,x2,x3,x4,x5,u1,u2) =
10x1+15x2+12x3+0x4+0x5+Mu1+Mu2MIN
ID,2013/2014
32
2013-10-25
Przykład 5  rozwiązanie (2)
Przykład 5  rozwiązanie (2)
Krok 3  Wstępne dopuszczane rozwiązanie modelu
Krok 3  Wstępne dopuszczane rozwiązanie modelu
Rozpoczynamy od przyjęcia, że te zmienne, które występują w więcej niż
jednym ograniczeniu, są równe zero
x1,x2,x3=0
W efekcie tego założenia wszystkie zmienne dodatkowe mają wartości
takie jak wyrazy wolne stojÄ…ce po prawej stronie odpowiednich
ograniczeń. Dla rozważanego modelu otrzymujemy więc:
x4=-30, x5=-50
Z uwagi na to, że zmienne x4 i x5 są ujemne to nie tworzą one bazowego
rozwiÄ…zania dopuszczalnego.
Dodajemy zmienne sztuczne (u1 i u2)  otrzymamy wstępne
rozwiÄ…zanie bazowe.
Dalsze postępowanie jest identyczne jak przy rozwiązywaniu zadania
metodÄ… simpleks.
ID,2013/2014
Parametry funkcji celu zmiennych sztucznych zależą
od kryteriów optymalności:
Jeśli funkcja celu jest minimalizowana to parametr
minimalizowana
wynosi +M;
Jeśli funkcja celu jest maksymalizowana to
maksymalizowana
parametr wynosi  M.
M  bardzo duża liczba dodatnia!!!
ID,2013/2014
33
2013-10-25
Przykład 5  rozwiązanie (3)
Przykład 5  rozwiązanie (3)
Krok 3,4,5
Krok 3,4,5
[s1] 2x1+7,5x2+3x3-x4 +u1 =30
[s2] 10x1+2,5x2+4x3 -x5 +u2 =50
F(x1,x2,x3,x4,x5,u1,u2) =
Tablica simpleks 1 10x1+15x2+12x3+0x4+0x5+Mu1+Mu2MIN
RozwiÄ…zanie w bazie [u1, u2] nie jest rozwiÄ…zaniem optymalnym.
ID,2013/2014
Przykład 5  rozwiązanie (4)
Przykład 5  rozwiązanie (4)
Krok 4,5,6
Krok 4,5,6
Tablica simpleks 2
RozwiÄ…zanie w bazie [u1, x1] nie jest rozwiÄ…zaniem optymalnym.
ID,2013/2014
34
2013-10-25
Przykład 5  rozwiązanie (5)
Przykład 5  rozwiązanie (5)
Krok 4,5,6; rozwiÄ…zanie optymalne
Krok 4,5,6; rozwiÄ…zanie optymalne
Tablica simpleks 3
RozwiÄ…zanie: x1=4,29, x2=2,86 F(x1,x2,x3,x4,x5,u1,u2) =85,71
Odp. Należy zakupić (dostarczyć) 4,29 kg paszy P1 oraz 2,86 kg paszy P2, aby
zapewnić właściwą kombinację składników odżywczych przy możliwie najniższych
kosztach wyżywienia, które wyniosą 85,71 zł.
ID,2013/2014
Różnice w algorytmie metody
Różnice w algorytmie metody
simpleks na MAX i MIN
simpleks na MAX i MIN
ID,2013/2014
35
2013-10-25
Postać bazowa
Postać bazowa
Wszystkie ograniczenia w postaci równań;
W każdym ograniczeniu znajduje się zmienna, która po
wyzerowaniu pozostałych zmiennych ma wartość
nieujemnÄ…;
Współczynnik przy zmiennej swobodnej ma wartość 1;
Wprowadzone zmienne swobodne wprowadza siÄ™ do
funkcji celu z zerowymi współczynnikami;
Wprowadzone zmienne sztuczne uwzględnia się w funkcji
celu ze współczynnikami M, których znak zależy od
kierunku optymalizacji.
Dla zmiennych bazowych wskaz
niki optymalności zawsze
są równe zero.
ID,2013/2014
Kryterium wejścia do bazy
Kryterium wejścia do bazy
MAX:
Zmienna z największą wartością wiersza
zerowego
MIN:
Zmienna z najmniejszą wartością wiersza
zerowego
ID,2013/2014
36
2013-10-25
Kryterium wyjścia z bazy
Kryterium wyjścia z bazy
MAX:
Zmienna, dla której iloraz elementu z wektora
wyrazów wolnych przez współczynnik z kolumny
zmiennej wchodzÄ…cej do bazy ma najmniejszÄ…
wartość.
MIN:
Identycznie jak w zadaniu na MAX.
ID,2013/2014
Degeneracja w algorytmie simpleksowym!!!
Degeneracja w algorytmie simpleksowym!!!
Gdy dwa lub więcej wskaz
ników ¸i posiada
jednakową minimalną wartość.
Pomocnicze wskaz
niki ¸i - ich wartoÅ›ci
powstają poprzez podzielenie współczynników
stojÄ…cych w pierwszej kolumnie odpowiadajÄ…cej
wektorom jednostkowym przez odpowiednie
współczynniki wektora zmiennych
wprowadzanej do bazy.
Z bazy zostanie usunięta zmienna, dla której
obliczony wskaz
nik pomocniczy ¸i ma
najmniejszą wartość.
37
2013-10-25
RozwiÄ…zanie optymalne
RozwiÄ…zanie optymalne
MAX:
Wszystkie wartości wiersza zerowego muszą być
niedodatnie
MIN:
Wszystkie wartości wiersza zerowego muszą być
nieujemne.
ID,2013/2014
Na dzisiaj wystarczy& ;)
Na dzisiaj wystarczy& ;)
ID,2013/2014
38