To tylko jedna z 3 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
Lista zadań z programowania liniowego i całkowitego
Zadanie 1. Rozwiązać metodą graficzną zadania:
max z = 5x1 + 4x2 x1 + 2x2 ≤ 6
-2x1 + x2 ≤ 4
5x1 + 3x2 ≤15
x1, x2 ≥ 0
max z = x1 + x2 x1 + x2 ≤ 4
-x1 + x2 ≤ 2
x1 ≤ 3
x1, x2 ≥ 0
max z = 2x1 + x2 x1 + x2 ≤ 6
-x1 + 2x2 ≤ 2
x1, x2 ≥ 0
Rozwiązanie:
x1 + 2x2 ≤ 6, x1 = 0, x2 = 3
x2 = 0, x1 = 6
Funkcja celu:
20 = z = 5x1 + 4 x2 f (z) (0, 5)
(4, 0)
Układ dwóch równań o z niewiadomych rozwiązujemy, które mogą być wycinkiem lub punktem.
Zadanie 2. Rozwiązać wszystkie modele i zadania 1 algorytmem sympleks. Dla trzeciego modelu należy zastosować M-metodę. Dla drugiego modelu wyznaczyć alternatywne rozwiązanie optymalne.
Zadanie 3. Rozwiązać algorytmem sympleks następujące zadanie:
max z = 4x3 - x1 - x2 x1 + x2 + 2x3 ≤ 9
x1 + x2 - x3 ≤ 2
-x1 + x2 + x3 ≤ 4
x1, x2, x3 ≥ 0
Rozwiązanie metoda sympleks:
x1 + x2 + 2x3 + S1 = 9
x1 + x2 - x3 + S2= 2
-x1 + x2 + x3 + S3= 4
Z B = { S1, S2, S3}
ZB
Rozw.
x1 x2 x3 S1 S2 S3 S1 S2 S3 9
2
4
1
1
-1
1
1
1
2
-1
1
1
0
0
0
1
0
0
0
1
9/1=9
2/1=2
-
z
0
1
1
1
0
0
0
Która zmienna wchodzi do bazy?
Element centralny
ZB
Rozw.
x1 x2 x3 S1 S2 S3 0
4
0
4
2
0
0
3
1
-2
0
Zadanie 4. Rozwiązać algorytmem sympleks następujące zadanie:
max z = -x1 - 5x2 + 1x3 x1 + 4x2 - x3 ≤ 4 x1 + 2x2 + 4x3 ≤ 10
(…)
… algorytmem podziału i ograniczeń następujący problem plecakowy (zbuduj drzewo podziału i ograniczeń):
max z = 8x1 + 5x2 + 6x3 + 4x4 + 3x5 8x1 + 4x2 + 7x3 + 6x4 + 3x5 ≤ 20
-x1 + x3 ≤ 4
x3 ≥ 3
x1, x2, x3, x4, x5 z/-1 ← NIE!
← nie dzielimy przez ujemne
4/1
Wektor pkt
f (z)
…
... zobacz całą notatkę
Komentarze użytkowników (0)