ImiÄ™ Nazwisko: Grupa
Matematyka stosowana, Rok 2, Egzamin II 10.09.2011
PROGRAMOWANIE LINIOWE
1. Rozwiąż nastepujący PPL metodą sympleks (12pt)
Å„Å‚
ôÅ‚ -x1 + x2 -1
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚ -x1 - x2 -3
òÅ‚
-x1 + 2x2 2
ôÅ‚
ôÅ‚
ôÅ‚
x1 + 3x2 max,
ôÅ‚
ôÅ‚
ôÅ‚
ół
x1, x2 0
2. Czy macierz incydencji grafu zorientowanego jest totalnie unimodularna? Odpowiedz
uzasadnić
. (6pt)
3. Znajdż rozwiąnie bazowe x układu kanonicznego stowarzyszonego z następującym PPL ograniczonym.
(12pt)
Å„Å‚
ôÅ‚
2x1 + x2 - 3x3 - x4 4
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚ - 2x2 + x3 + 2x4 -3
x1
òÅ‚
cx max,
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚ -1 x1 2, 1 x2 2,
ôÅ‚
ôÅ‚
ół
-1 x3 1, 0 x4 1
4. Czy wektor (1, 0, 1, 0, 0) jest rozwiązaniem optymalnym następującego problemu PL. Odpowiedz

uzasadnić.(12pt)
Å„Å‚
ôÅ‚ -3x1 + 4x2 + x3 + 3x4 + x5 1
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚ 7x1 + 3x2 - 7x3 + x4 + x5 1
òÅ‚
4x1 + x2 + 5x3 + 3x4 + x5 9
ôÅ‚
ôÅ‚
ôÅ‚
4x1 + x2 + 5x3 + 2x4 + x5 max
ôÅ‚
ôÅ‚
ôÅ‚
ół
x1, x2, x3, x4, x5 0
5. Sformuluj twierdzenie o odstępach komplementarnych (6pt)
6. Wypowiedz
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