Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
Stránky: 1
Zdravím!
Mám z praxe zadání na kontrolu, zda se počet balíků s různými velikostmi vejde do rozměru konkrétního velkého balíku o daném maximálním rozměru.
Konkrétně, musí proběhnout kontrola, zda se balíky vejdou nebo nevejdou do krabice. Základní otázka tedy zní zda je vůbec úloha řešitelná matematicky..
praxe:
mám x balíků o různých rozměrech a zadání je ověřit, zda nějakým způsobem uložení baliků se vejdou do krabice s maximálním rozměrem každé strany 120cm, s tím, že součet stran ale nesmí přesáhnout 150cm.. příklad pro upřesnění, maximální strana může být 120 ve chvíli kdy ostatní strany budou mít délky 15 a 15 aby se nepřesáhl součet stran 150
Děkuju!
Offline
Ahoj,
takže součet stran jednoho balíku nesmí přesáhnout 150cm?
Je povoleno balíky umísťovat i tak, že jejich strany nebudou rovnoběžné se stranami velkého balíku?
Offline
Ahoj,
1. součet stran nejvetšího balíku nesmí přesáhnout 150cm, což znamená, ano, protože by se v tu chvíli vešel do toho balíku pouze jeden balík, když budu ignorovat tloušťku stran vnějšího balíku, což si v rámci tolerance můžeme dovolit.
2. Teoreticky ano, ale pro zjednodušení výpočtu bych toto vyloučil.
Díky
Offline
↑ lracek:
Ale balíků s rozměry 110x20x30 se do toho velkého vejde spousta a součet jejich stran přesahuje 150...
Offline
Ahoj,
"zda se počet balíků s různými velikostmi vejde do rozměru konkrétního velkého balíku o daném maximálním rozměru"
Aby se všechny vkládané balíky vešly do jednoho velkého balíku (dále krabice), zjevně musí platit (nutná podmínka), že součet jejich objemů není větší než objem krabice, do které je mám vložit.
Zkusím speciální případy, kdy si myslím, že lze zaskládat balíky do krabice "bez mezer", tj. objem všech balíků je roven objemu krabice:
1. Mám krychlovou krabici 8x8x8, tedy 512 objemových jednotek.
Stanovím si podmínku, že vkládané balíky jsou rovněž krychle. Jejich povolené velikosti jsou pouze 1x1x1, 2x2x2, 4x4x4.
Krychlí s délkou hrany je a, krychlí s délkou hrany 2 je b, krychlí s délkou hrany 4 je c.
Potom tvrdím, že všechny balíky se vejdou (dají se naskládat) do krabice právě tehdy, když
[mathjax]a+8*b+64*c=512[/mathjax]
Pro krabici 120x120x120 cm by přípustné velikosti balíků byly krychle o hraně 60, 30, 15 cm.
(Rovnice se dá zobecnit na libovolné další půlení délky hrany, 7,5 cm atd.)
Balíky mohu ukládat např. od největších k nejmenším tak, že když mi větší balíky dojdou, z 8 menších balíků seskládám 1 větší balík, který uložím na následující pozici většího balíku.
2. Krychlová krabice 120x120x120 cm.
Vkládané balíky budou hranoly s podstavou velikostí kreslicích čtvrtek: A4(30x20), A3(40x30), A2(60x40), a jednotnou výškou,(která dělí 120), např 10. Když budeme balíky pokládat na dno krabice podstavou dolů, bude rovnice pro úplné pokrytí jedné vrstvy balíků v krabici
[mathjax]a+2*b+4*c=24[/mathjax]
kde a je počet balíků velikosti A4, b je počet balíků velikosti A3, c je počet balíků velikosti A2. Rovnice pro naplnění celé krabice bude mít pravou stranu násobenou počtem vrstev, v případě jednotné výšky balíku 10 cm to bude
[mathjax]a+2*b+4*c=24*12[/mathjax]
------------------------------------------------------------------------------------------------------------------
Vstupní hromadu balíků roztřídím na tři hromádky podle velikosti, spočítám je a dosadím za a,b,c. Když mi vyjde levá strana menší než pravá, zbyde mi v bedně místo, v případě rovnosti bude bedna zaplněna bez mezer, jinak se balíky do bedny nevejdou.
Offline
Mám tady návrh řešení pokud dává smysl
1) Seřadit produkty od největšího k nejmenšímu
2) Vložení prvního produktu - nějvětší produkt
IF a1 + b2 + c3 < 150 cm AND a1 < 120 cm and b2 < 120 cm and c3 < 120 cm - vejde se do krabice
3) Vložení druhého produktu - druhý největší produkt - zbydou mi dvě možné volné krychle prostoru
Volné krychle obemu v krabici
IF (a - a1) > a2 and b > b2 and c > c2 OR a > a2 and (b - b1) > b2 and c > c2 - vejde se do krabice
4) Vložení třetího - zbydou mi tři volné krychle prostoru
IF (a - a1 - a2) > a3 and b > b3 and c > c3 OR a > a3 and (b - b1 - b2) > b3 and c > c3 OR a > a3 and > b3 and (c - c1 - C2) > c3 - vejde se do krabice
A tak dále s každou další položku
Offline
↑ lracek:
Ahoj, jak definuješ, že jeden balíček je větší než jiný?
Co myslím tím pojmem "volné krychle prostoru"?
Ale to co uvádíš bude nejspíš nějaká aproximace optimálního řešní (hladový algoritmus). O takových jde často určit odhad o kolik nejvíce se mohou lišit od optimálního řešení. A možná ani nebude existovat polynomiální optimalizační algoritmus...
Offline
Stránky: 1