Matematické Fórum

Cermix · 07. 06. 2012 16:15

Nevím jaký jsem měl zvolit nadpis. Někteří z nás hrají strategické PC hry a mě napadlo jak co nejlépe optimalizovat jeden problém..
Mám jednoho dělníka, který sklidí 1 kg ovoce za sekundu.
Jakmile budu mít 20 kg ovoce můžu si najmout dalšího dělníka který okamžitě začne pracovat taky s rychlostí sklizně 1 kg za sekundu ( Těch 20 kg ve chvíli najmutí ztratím )
(prostě... dělník pracuje 20 sekund a má 20 kg ovoce a hned v ten moment si "najme" dalšího dělníka, a tím ztratí těch 20 kg ovoce, a ten mu pomůže, takže jejich společná rychlost sklizně bude dvojnásobná, ale budou sklízet od nuly) a mě by zajímalo jakým způsobem by šlo spočítat kolik je třeba najmout dělníků aby bylo sklizeno 100 kg ovoce v co nekratším čase. ( Jiný způsob získání dělníka není než "koupení" za 20 kg ovoce)
Grafické řešení by sice šlo, ale v příkladech kde je mnohem více faktorů je to velmi náročné.
Děkuji za odpovědi.

Bati · 07. 06. 2012 17:35

Ahoj, nastíním postup, jak bych to řešil já.
Nechť tedy máme dělníky, každý pracuje rychlostí m kg za sekundu, chceme celkem nasbírat M kg a za p kg si můžeme koupit dalšího dělníka. n bude počet dělníků, které si přikoupím.
Nejprve provedeme pozorování: Pokud bude optimální řešení zahrnovat nakoupení nějakých dělníků, pak je nejvýhodnější tyto dělníky koupit hned, jakmile na ně budeme mít - tedy vždy jakmile nasbíráme p kg.
Teď si postupně vyjádříme časy v závislosti na n ... $t(n)$ , za které se nasbírá M kg:
$t(0)=\frac{M}m\\ t(1)=\frac{p}{m}+\frac{M}{2m}\\ t(2)=\frac{p}{m}+\frac{p}{2m}+\frac{M}{3m}\\ \vdots\quad\\ t(n)=\frac{p}m\cdot\sum\limits_{i=1}^n\frac1i+\frac{M}{(n+1)\cdot m}$
Částečné součty té sumy na konci jsou harmonická čísla a ty se dají spojitě aproximovat takto:
$\sum\limits_{i=1}^{[x]}\frac1i\sim\ln{x}+\gamma$ , kde gamma je konstanta. (viz. např. http://en.wikipedia.org/wiki/Harmonic_number).
Nyní už je to rutina - napsat si předpis pro spojitou funkci t(x), vypočítat derivaci, určit minimum a správně interpretovat výsledek.
Za povšimnutí přitom stojí, že optimální řešení nezávisí na m.

Cermix · 07. 06. 2012 17:49

První postup až do té Sumy mě napadl taky... akorát by to bylo komplikované, že bych musel řešit příliš mnoho rovnic... Díky za Tvůj postup.

Matematické Fórum

#1 07. 06. 2012 16:15

Optimalizace

#2 07. 06. 2012 17:35

Re: Optimalizace

#3 07. 06. 2012 17:49

Re: Optimalizace

Zápatí