ImiÄ™ Nazwisko: Grupa
Matematyka stosowana, Rok , Egzamin II 10.09.2011
PROGRAMOWANIE LINIOWE
1. a) Sprawdzić, czy następująca macierz A jest totalnie unimodularna;
îÅ‚ Å‚Å‚
1 0 1 -1
ïÅ‚ śł
0 1 0 -1
ïÅ‚ śł
A = ïÅ‚ śł
ðÅ‚ -1 0 -1 0
ûÅ‚
0 -1 0 0
b) Mamy układ Ax = b, x 0, gdzie b = (1, 1, -2, -1)t. Czy istnieje całkowite rozwiązanie
bazowe danego układu? Odpowiedz
uzasadnić.(6+8pt)
2. Czy wektor (0, 1, 0, 0, 1) jest rozwiązaniem optymalnym następującego problemu PL? Odpowiedz

uzasadnić.(12pt)
Å„Å‚
ôÅ‚ - 3x2 + 4x3 + 3x4 + x5 1
2x1
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚ x1 + 7x2 + 3x3 + x4 - 7x5 1
òÅ‚
x1 + 4x2 + 2x3 + 3x4 + 5x5 9
ôÅ‚
ôÅ‚
ôÅ‚
x1 + 4x2 + x3 + 2x4 + 5x5 max
ôÅ‚
ôÅ‚
ôÅ‚
ół
x1, x2, x3, x4, x5 0
3. Zapisz problem przepływu maksymalnego w sieci S = (G, c), gdzie c: E(G) R+ jest funkcją
przepustowości, w postaci problemu programowania liniowego. (8pt)
4. Rozwiąż następujący PPL ograniczony metodą Sympleks, jeśli wiadome jest rozwiązanie bazowe
x = (0, 0, 2, 1, 1, 0) danego układu. (12pt)
Å„Å‚
ôÅ‚
x1 + 3x2 - 5x3 - 2x4 - 6x5 + 4x6 = -8
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚ -2x2 + 4x3 + x4 + 5x5 - 3x6 = 6
òÅ‚
-3x1 - x2 - x3 + x4 - 4x5 + x6 max,
ôÅ‚
ôÅ‚
ôÅ‚
0 x1 8, 0 x2 4, 0 x3 2,
ôÅ‚
ôÅ‚
ôÅ‚
ół
0 x4 10, 0 x5 3, 0 x6 10
5. Niech mamy PPL w postaci układu {Ax = b, cx max}. W terminach macierzy A, omów
warunek konieczny i wystarczący aby rozwiązanie bazowe danego układu było wierzchołkiem
odpowiedniego wielościanu ZRD. (6pt).
6. Omów problem inicjalizacji dla algorytmu sympleks w przypadku zadania PL ograniczonego i
sposób jego rozwiązania. (8pt).
7. Sformuluj zasadę dualności dla problemów PL. Co można powiedzieć o rozwiązaniach PPL
dualnego, jeśli wiadomo, że układ prymalny jest nieograniczony? (6+4pt).
1