Zadanie programowania liniwego:
Zmienne decyzyjne (symbole oznaczające wielkości, których nie znamy, a których szukamy, potrzebne na początku procesu, też logiczne TAK lub NIE (1 lub 0)
funkcja celu - funkcja liniowa zmiennych decyzyjnych, kryterium oceny, ma przyjąć jak najmniejszą bądź jak największą wartość
ograniczenia - nierówności lub równości liniowe (lewa strona jest funkcją liniową zmiennych decyzyjnych), opisujące wymagania, warunki działania itp.
W problemie najkrótszej drogi zmienne decyzyjne: dla każdego łuku jedna, może przyjąć wartość 1 (łuk należy do drogi) lub 0 (łuk nie należy do drogi), f. celu - długość drogi, ograniczenia zapewniają, że to będzie droga od początku do końca, spójna, bez odgałęzień.
Problem najtańszego pokrycia A
B
C
D
E
F
I
1
1
1
II
1
1
III
1
1
IV
1
1
V
1
1
VI
1
1
4
5
7
6
8
3
lokalizacja
Koszt
Okręgi obsługiwane
S1
4
L1,l3,l5,l7,l8,l10,l12,l14
S2
7
L2,l4,l11
S3
11
L1,l6,l8,l9,l13,l14,l15
S4
6
L1,l2,l4,l8,l10,l11,l14
S5
10
L3,l5,l6,l7,l9,l12,l13,l15
A
B
C
D
E
F
I
1
1
II
1
1
1
1
III
1
1
IV
1
1
1
1
1
V
(…)
… ją
Jeśli w danym wierszu są same 0, nie ma rozwiązania - KONIEC
Sformułowanie jako zadanie programowania liniowego: zmienne decyzyjne - 0-1 - dla każdej kolumny (wybrana - niewybrana), f. celu - koszty, ograniczenia - pokrycie.
…
... zobacz całą notatkę
Komentarze użytkowników (0)