Matematické Fórum

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
! 2.11.2020 (L) Vykreslete si svůj první matematický výraz přes MathJax!
! 04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17.01.2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17.01.2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
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

#1 10. 02. 2021 12:28

lracek
Zelenáč
Příspěvky: 5
Škola: VUT FEKT
Pozice: student
Reputace:   
 

Kontrola velikosti kombinace baliku v jednom velkem baliku

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

 

#2 10. 02. 2021 17:06

check_drummer
Příspěvky: 3127
Reputace:   81 
 

Re: Kontrola velikosti kombinace baliku v jednom velkem baliku

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?


Popelka - pohádka o neprosté funkci nabývající minima v jediném bodě

Offline

 

#3 11. 02. 2021 12:37

lracek
Zelenáč
Příspěvky: 5
Škola: VUT FEKT
Pozice: student
Reputace:   
 

Re: Kontrola velikosti kombinace baliku v jednom velkem baliku

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

 

#4 11. 02. 2021 20:50

check_drummer
Příspěvky: 3127
Reputace:   81 
 

Re: Kontrola velikosti kombinace baliku v jednom velkem baliku

↑ lracek:
Ale balíků s rozměry 110x20x30 se do toho velkého vejde spousta a součet jejich stran přesahuje 150...


Popelka - pohádka o neprosté funkci nabývající minima v jediném bodě

Offline

 

#5 14. 02. 2021 22:58 — Editoval osman (14. 02. 2021 23:15)

osman
Zelenáč
Příspěvky: 14
Pozice: v.v.
Reputace:   
 

Re: Kontrola velikosti kombinace baliku v jednom velkem baliku

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

 

#6 16. 02. 2021 14:21 — Editoval lracek (16. 02. 2021 16:10)

lracek
Zelenáč
Příspěvky: 5
Škola: VUT FEKT
Pozice: student
Reputace:   
 

Re: Kontrola velikosti kombinace baliku v jednom velkem baliku

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

 

#7 16. 02. 2021 19:19

check_drummer
Příspěvky: 3127
Reputace:   81 
 

Re: Kontrola velikosti kombinace baliku v jednom velkem baliku

↑ 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...


Popelka - pohádka o neprosté funkci nabývající minima v jediném bodě

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson