1. Przykłady
1.1. X ≠ φ, jedno rozwiązanie optymalne, n = 2
Funkcja celu:
max x = x + 4 x 0
1
2
.
1 − x + 2 x ≤ 4
1
2
Ograniczenia:
.
2 − x + x ≤ 1
, x ≥ 0
1
2
.
3 4 x + 5 x ≤ 36
1
2
Rys. 1. Ilustracja graficzna do przykładu pierwszego (Derive) Rozwiązanie z wykorzystaniem tablic simpleks Na podstawie wyżej przedstawionej funkcji celu i ograniczeniom zbudowano pierwszą tablicę.
Przykład 1 - Tablica 1
b
x1
x2
x0
0
-1
-4
x3
4
-1
2
x4
1
-1
1
x5
36
4
5
1. W kolumnie b brak jest elementów ujemnych.
2. W wierszu x0 występuje element ujemny – brak rozwiązania optymalnego.
3. Najmniejsza wartość wiersza x
−
−
= −
0 wynosi mi {
n ,
0
,
1
}
4
4 (kolumna x2).
4. Wyznaczenie punktu centralnego w kolumnie x2 (rozpatrywane tylko elementy
4 1 36
dodatnie) poprzez obliczenie min , ,
= mi {
n ,
2 ,
1 7
. }
2 = 1 .
2 1 5
5. Obliczenie nowych wartości do tablicy 2.
Przykład 1 – Tworzenie tablicy 2
b
x1
x2
1⋅ (−4)
−1⋅(−4)
− 4
x
−
− −
= −
−
=
0
0
= 4 1
5
4
1
1
1
1⋅ 2
−1⋅ 2
2
x
−
− −
− = −
3
4
= 2
1
=1
2
1
1
1
1
−1
1
x
=
= −
=
4
1
1
1
1
1
1
1⋅5
−1⋅5
5
x
−
−
−
5
36
= 31
4
= 9
1
1
1
W ten sposób otrzymano tablicę 2.
Przykład 1 - Tablica 2
b
x1
x4
x0
4
-5
4
x3
2
1
-2
x2
1
-1
1
x5
31
9
-5
W nowo utworzonej tablicy w wierszu x0 nadal znajduje się element ujemny w związku z czym obliczono kolejną tablicę stosując wcześniej podany algorytm.
Przykład 1 - Tworzenie tablicy 3
b
x1
x4
2 ⋅ (− )
5
− 5
− 2⋅(− )
5
x
−
−
=
−
=
0
4
=14
5 4
−6
1
1
1
2
1
− 2
x
=
=
= −
3
2
1
2
1
1
1
2 ⋅ (− )
1
−1
− 2⋅(− )
1
x
−
−
=
−
=
2
1
= 3
1 1
−1
1
1
1
2 ⋅9
9
− 2⋅9
x
−
− = −
− −
5
31
=13
9
5
=13
1
1
1
W powyższy sposób utworzono tablicę 3.
Przykład 1 - Tablica 3
b
x3
x4
x0
14
5
-6
x1
2
1
-2
x2
3
1
-1
x5
13
-9
13
Ponownie w wierszu x0 znalazł się element ujemnym w związku z czym rozwiązanie optymalne nadal nie zostało odnalezione.
Przykład 1 - Tworzenie tablicy 4
b
x3
x4
13⋅ ( 6
− )
− 9⋅(−6) 11
− 6
6
x
−
−
−
=
0
14
= 20 5
=
13
13
13
13
13
13⋅ (−2)
− 9⋅( 2
− )
5
− 2
2
x
−
−
=
−
=
1
2
= 4 1
−
13
13
13
13
13
13⋅ (− )
1
− 9⋅(− )
1
4
−1 1
x
−
−
−
=
2
3
= 4
1
=
13
13
13
13
13
13
− 9
9
1
x
=
= −
5
1
13
13
13
13
Ostatecznie otrzymano tablicę z rozwiązaniem.
Przykład 1 – Tablica 4
b
x3
x5
x0
20
0.85
0.46
x1
4
-0.38
0.15
x2
4
0.31
0.08
x4
1
-0.69
0.08
W wierszu x0 brak jest elementów ujemnych w związku z czym tablica 4 zawiera rozwiązanie optymalne.
x0 = 20
x1 = 4
x2 = 4
Wyniki obliczeń (Matlab) x1 = 4
x2 = 4
fval = 20
iterations = 3
exitflag = 1 (Function converged to a solution x)