Imię Nazwisko:

Grupa

Matematyka stosowana, Rok 2, Egzamin II

10.09.2011

PROGRAMOWANIE LINIOWE

1. Rozwiąż nastepujący PPL metodą sympleks

(12pt)































−x

1

+ x

2

¬ −1

−x

1

− x

2

¬ −3

−x

1

+ 2x

2

¬ 2

x

1

+ 3x

2

→ max,

x

1

, x

2

­ 0

2. Czy macierz incydencji grafu zorientowanego jest totalnie unimodularna? Odpowiedź uzasadnić
. (6pt)

3. Znajdż rozwiąnie bazowe x układu kanonicznego stowarzyszonego z następującym PPL ograniczonym.
(12pt)































2x

1

+ x

2

− 3x

3

− x

4

¬ 4

x

1

− 2x

2

+ x

3

+ 2x

4

¬ −3

cx → max,
−1 ¬ x

1

¬ 2, 1 ¬ x

2

¬ 2,

−1 ¬ x

3

¬ 1, 0 ¬ x

4

¬ 1

4. Czy wektor (1, 0, 1, 0, 0) jest rozwiązaniem optymalnym następującego problemu PL. Odpowiedź
uzasadnić.(12pt)































−3x

1

+ 4x

2

+ x

3

+ 3x

4

+ x

5

¬ 1

7x

1

+ 3x

2

− 7x

3

+ x

4

+ x

5

¬ 1

4x

1

+ x

2

+ 5x

3

+ 3x

4

+ x

5

¬ 9

4x

1

+ x

2

+ 5x

3

+ 2x

4

+ x

5

→ max

x

1

, x

2

, x

3

, x

4

, x

5

­ 0

5. Sformuluj twierdzenie o odstępach komplementarnych

(6pt)

6. Wypowiedź problem zapętlania w algorytmie Sympleks i sformuluj regulę Blanda

(8pt).

7. Opisz jeden krok iteracyjny algorytmu algorytmu Forda-Fulkersona przepływu maksymalnego
w sieci. Czy zawsze istnieje taki przepływ w sieci?

(11+3pt).

1