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 |
|
|
1 |
1 |
1 |
|
VI |
|
|
1 |
1 |
1 |
1 |
|
4 |
5 |
7 |
6 |
4 |
3 |
Algorytm heurystyczny: liczymy stosunek liczby 1 w macierzy/koszt, wybieramy daną kolumnę i aktualizujemy macierz.
Algorytm dokładny: zastosowanie w dowolnej kolejności, dopóki się da, jednej z reguł, potem pełen przegląd.
Jeśli w danym wierszu jest dokładnie jedna jedynka, wybierz odpowiednią kolumnę, zaktualizuj macierz
Jeśli dany wiersz jest „Większy lub równy” niż inny, wyeliminuj go
Jeśli dana kolumna jest „mniejsza lub równa” i nietańsza niż inna, wyeliminuj ją
Jeśli w danej kolumnie są same 0, wyeliminuj 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.