Uniwersytet Kardynała Stefana Wyszyńskiego
Wydział Matematyczno-Przyrodniczy
Szkoła Nauk Ścisłych
Egzamin z przedmiotu: Badania Operacyjne
13-06-2006
ZADANIA
1 Zadanie
Rozwiązać następujące zagadnienie optymalizacyjne (przekształcić do zagadnienia programowania liniowego i
rozwiązać metodą sympleksów)
1
max f(x) = - x1 + x2 (1)
2
przy ograniczeniach
x2 d" 5 (2)
-2x1 + x2 d" 3 (3)
|x1 - 2| d" x2 (4)
xi e" 0, i = 1, 2 (5)
1
TEST
2 Zadanie
Dane jest następujące Zagadnienie Programowania Liniowego
1 1
max f(x) = x1 + x2 (6)
Ä… ²
gdzie Ä…, ² " R oraz Ä…, ² > 0 przy ograniczeniach
1
x1 + x2 d" 4 (7)
2
-2x1 + x2 e" -6 (8)
xi e" 0, i = 1, 2 (9)
" Wykorzystując metodę graficzną rozwiązywania zaganień programowania liniowego wyznacz rozwiązanie
optymalne danego zagadnienia w zależnoÅ›ci od parametrów Ä… oraz ².
" Dla jakich wartości tych parametrów ilość rozwiązań ZPL będzie nieskończona?
3 Zadanie
Pokazać, że jeÅ›li X ‚" Rn jest zbiorem wypukÅ‚ym oraz f : X Rm jest funkcjÄ… liniowÄ…, to obraz zbioru X,
tzn.
f(X) = {y : y = f(x), x " X} (10)
jest zbiorem wypukłym.
4 Zadanie
Wykonać dwa kroki (rozwiązanie początkowe oraz jedno przekształcenie tablicy) w algorytmie dla zagadnienia
trasportowego. Odpowiednie stany magazynów ai, zapotrzebowania odbiorców bj oraz macierz kosztów są
postaci:
a1 = 8, a2 = 4, a3 = 6, b1 = 2, b2 = 4, b3 = 6, b4 = 6 (11)
îÅ‚ Å‚Å‚
3 8 4 1
ðÅ‚ ûÅ‚
cij = 6 2 1 5 (12)
4 6 4 3
2