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)