To tylko jedna z 2 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
PROBLEM POKRYCIA:
Danych jest 10 różnych maszyn , które muszą zostać opakowane do transportu w drewniane skrzynie. Załóżmy, że koszt wykonania skrzyni dla maszyny i (wielkości i) wynosi ci , oraz że c1c2 c10. Przyjmijmy, że C = (32,30,20,17,15,10,9,5,3,2). Możemy zamówić skrzynie jedynie pięciu rozmiarów, a maszyny mają takie wielkości że skrzynia o wielkości t może zostać wykorzystana do zapakowania maszyny t oraz dowolnej maszyny mniejszej niż t tzn. maszyny j, gdzie jt. Maszyny zostaną wysłane jednym transportem, ale następnie trafił do różnych odbiorców , tzn. każda maszyna musi być zapakowana w oddzielną skrzynię. Określić, których rodzajów skrzynię należy zbudować i w jakich ilościach, aby zminimalizować koszt opakowania maszyn do transportu. Sformułowanie problemu:
Na etapie n zdecyduj jaką liczbę skrzyń xn rozmiaru n należy zamówić.
Stan systemu jest równy pozostającej jeszcze do wykorzystania liczbie rozmiarów skrzyń.
fn(s,xn) koszt najlepszej strategii dla maszyn n , ,10 jeżli zostało jeszcze do wykorzystania s typów skrzyń i zdecydowano zbudować xn skrzyń rodzaju n. fn(s) koszt najlepszej strategii dla maszyn n , ,10 jeżli zostało jeszcze do wykorzystania s typów skrzyń.
Poszukujemy f1(5)
Zależności rekurencyjne:
tzn. fn(s,xn) = Koszt zamówienia xn skrzyń typu n + Koszt najlepszego opakowania maszyn n+xn,....10 przy użyciu s-1 typów skrzyń
Rozwiązanie:
Obliczenie f10(s):
s
f10(s)
x10*
1
2
1
Obliczenie f9(s):
s
f9(s)
x9*
1
6
2
2
Obliczenie f8(s) f8(s ,x8) = 5x8 + f8+x8 (s - 1):
s
x8 = 1
x8 = 2
x8 = 3
f8(s)
x8*
1
*
*
15
15
3
2
5 + f9(1)
10 + f10(10
*
11
1
3
.....
....
....
....
....
Obliczenie f7(s) f7(s , x7)= 9x7 + f7 + x7 (s - 1):
s
x7 = 1
x7 = 2
X7 = 3
x7 = 4
f7(s)
x7*
1
*
*
*
36
... zobacz całą notatkę
Komentarze użytkowników (0)