To tylko jedna z 3 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
PROGRAMOWANIE CAŁKOWITOLICZBOWE LINIOWE
Na etapie n zdecyduj jaką liczbę skrzyń xnproduktu n , należy załadować na samochód.
Stan systemu jest równy pozostającej jeszcze do wykorzystania pojemności samochodu.
fn(s,xn) maksymalny zysk z przewozu dla produktów n , , 4 jeżli pozostaje do wykorzystania s jednostek pojemności i postanowiono załadować xn skrzyń produktu n.
fn(s) maksymalny zysk z przewozu dla produktów n , , 4 jeżli pozostaje do wykorzystania s jednostek pojemności.
Określenie etapów wyobrażenie sobie rzeczywistego procesu ładowania samochodu. Określenie stanu analiza jedynego ograniczonego zasobu pozostającej do wykorzystania przestrzeni samochodu. Strategia załadunku ciąg wartości x1 , x2 , x3 , x4 , która określa liczbe wybranych skrzyni kolejnych produktów. Jeżli jesteśmy na ostatnim etapie (tzn. mamy zadecydować o liczbie skrzyni produktu 4) to rozwiązanie jest oczywiste należy wziąć tyle skrzyn ile zmieści się w pozostającej do wykorzystania przestrzeni (ładowności) samochodu. Poszukujemy:
f1(10) wartość najlepszej strategii dla produktów 1, , 4 przy pozostającej do wykorzystania pojemności samochodu wynoszącej 10 ton.
fn(s,xn) = vnxn + fn+1(s - wnxn)
fn(s) = max {fn(s,xn) dla wszystkich xn}
Rozwiązanie:
Obliczenie f4(s)
s
f4(s)
x4*
0
0
0
1
0
0
2
0
0
3
0
0
4
8
1
5
8
1
6
8
1
7
8
1
8
16
2
9
16
2
10
16
2
Obliczenie f3(s) f3(s,x3) = 6x3 + f4(s - 3x3)
s
x3 = 0
x3 = 1
x3 = 2
x3 = 3
f3(s)
x3*
0
0 + f4(0)
*
*
*
0
0
1
0 + f4(1)
*
*
*
0
0
2
0 + f4(2)
*
*
*
0
... zobacz całą notatkę
Komentarze użytkowników (0)