3582326898

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 c;, oraz że ci>C2>l >cio. 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ż ttzn. maszyny j, gdzie j>t. 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ń *n rozmiaru u należy zamówić.

Stan systemu jest równy pozostającej jeszcze do wykorzystania liczbie rozmiarów skrzyń fn(s,x_n) — koszt najlepszej strategii dla maszyn n,... ,10 jeżli zostało jeszcze do wykorzystania s typów skrzyń i zdecydowano zbudować x_n skrzyń rodzaju il

fnfr) — koszt najlepszej strategii dla maszyn n,... ,10 jeżli zostało jeszcze do wykorzystania s typów skrzyń.

Poszukujemy fi(5)

Zależności rekurencyjne:

/»0.x_R) = c.x. +    0 - 1)

tzn. f„(s,x_n) = Koszt zamówienia x„ skrzyń typu n + Koszt najlepszego opakowania maszyn

n+x„.„„.10 przy użyciu s-1 typów

skrzyń

Rozwiązanie:

Ob]	iczenie	w
s	fio(s)	*10*
1	2	1

Obliczenie fa(s):

s	fs(s)	*9*
1	6	2
2	1	1

Ob	liczenie fg(s) fg(s ,Xs) = Sx8 + fBtx8 (s -1):
s	xa = 1	*a ^= 2	Xa = 3	fc(s)		Xa*
1	*	*	15	15		3
2	5 + f9(l)	10 + fio(io	*	11		1
3		....	....	....		....
Obliczenie f^s) frfs, x7j= 9x7 + f7+ *7 (s -1):
s	8 n	X7 = 2	X7 = 3		11 £		f7(s)	x7*
1	*	*	Hi		36		36	4
2		18 + f„(l)	27 + f10(l)		Hi		24	13 2